Sublinear Time Algorithms
Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a very small portion of the input. We discuss the types of answers that one can hope to achieve in this setting.
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/70521 https://orcid.org/0000-0002-4353-7639 |
| _version_ | 1826207225944735744 |
|---|---|
| author | Rubinfeld, Ronitt Shapira, Asaf |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Rubinfeld, Ronitt Shapira, Asaf |
| author_sort | Rubinfeld, Ronitt |
| collection | MIT |
| description | Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a very small portion of the input. We discuss the types of answers that one can hope to achieve in this setting. |
| first_indexed | 2024-09-23T13:46:00Z |
| format | Article |
| id | mit-1721.1/70521 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:46:00Z |
| publishDate | 2012 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/705212022-09-28T16:02:35Z Sublinear Time Algorithms Rubinfeld, Ronitt Shapira, Asaf Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Rubinfeld, Ronitt Rubinfeld, Ronitt Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a very small portion of the input. We discuss the types of answers that one can hope to achieve in this setting. National Science Foundation (U.S.) (grant 0732334) National Science Foundation (U.S.) (grant 0728645) Marie Curie International Reintegration Grants (grant PIRG03-GA-2008-231077) Israel Science Foundation (grant 1147/09) Israel Science Foundation (grant 1675/09) National Science Foundation (U.S.) (grant DMS-0901355) Israel Science Foundation (grant 224/11) 2012-05-04T22:25:23Z 2012-05-04T22:25:23Z 2011-11 2011-02 Article http://purl.org/eprint/type/JournalArticle 0895-4801 1095-7146 http://hdl.handle.net/1721.1/70521 Rubinfeld, Ronitt, and Asaf Shapira. “Sublinear Time Algorithms.” SIAM Journal on Discrete Mathematics 25.4 (2011): 1562. Web. 4 May 2012. © 2011 Society for Industrial and Applied Mathematics https://orcid.org/0000-0002-4353-7639 en_US http://dx.doi.org/10.1137/100791075 SIAM Journal on Discrete Mathematics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Rubinfeld, Ronitt Shapira, Asaf Sublinear Time Algorithms |
| title | Sublinear Time Algorithms |
| title_full | Sublinear Time Algorithms |
| title_fullStr | Sublinear Time Algorithms |
| title_full_unstemmed | Sublinear Time Algorithms |
| title_short | Sublinear Time Algorithms |
| title_sort | sublinear time algorithms |
| url | http://hdl.handle.net/1721.1/70521 https://orcid.org/0000-0002-4353-7639 |
| work_keys_str_mv | AT rubinfeldronitt sublineartimealgorithms AT shapiraasaf sublineartimealgorithms |