- 2008
- Dorit Aharonov, Michael Ben-Or:
Fault-Tolerant Quantum Computation with Constant Error Rate. SIAM J. Comput. 38(4): 1207-1282 (2008) - Michael Alekhnovich, Alexander A. Razborov:
Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38(4): 1347-1363 (2008) - Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM J. Comput. 38(1): 63-84 (2008) - Noga Alon, Asaf Shapira:
Every Monotone Graph Property Is Testable. SIAM J. Comput. 38(2): 505-522 (2008) - Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden:
The Price of Stability for Network Design with Fair Cost Allocation. SIAM J. Comput. 38(4): 1602-1623 (2008) - Marcelo Arenas, Wenfei Fan, Leonid Libkin:
On the Complexity of Verifying Consistency of XML Specifications. SIAM J. Comput. 38(3): 841-880 (2008) - Boris Aronov, Sariel Har-Peled:
On Approximating the Depth and Related Problems. SIAM J. Comput. 38(3): 899-921 (2008) - Albert Atserias, Anuj Dawar, Martin Grohe:
Preservation under Extensions on Well-Behaved Finite Structures. SIAM J. Comput. 38(4): 1364-1381 (2008) - Ivan D. Baev, Rajmohan Rajaraman, Chaitanya Swamy:
Approximation Algorithms for Data Placement Problems. SIAM J. Comput. 38(4): 1411-1429 (2008) - János Balogh, József Békési, Gábor Galambos, Gerhard Reinelt:
Lower Bound for the Online Bin Packing Problem with Restricted Repacking. SIAM J. Comput. 38(1): 398-410 (2008) - Nikhil Bansal, Don Coppersmith, Maxim Sviridenko:
Improved Approximation Algorithms for Broadcast Scheduling. SIAM J. Comput. 38(3): 1157-1174 (2008) - Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
Exponential Separation of Quantum and Classical One-Way Communication Complexity. SIAM J. Comput. 38(1): 366-384 (2008) - Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. SIAM J. Comput. 38(5): 1661-1694 (2008) - Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb:
Private Approximation of Search Problems. SIAM J. Comput. 38(5): 1728-1760 (2008) - Eli Ben-Sasson, Madhu Sudan:
Short PCPs with Polylog Query Complexity. SIAM J. Comput. 38(2): 551-607 (2008) - Mark de Berg, Chris Gray:
Vertical Ray Shooting and Computing Depth Orders for Fat Objects. SIAM J. Comput. 38(1): 257-275 (2008) - Mikolaj Bojanczyk, Thomas Colcombet:
Tree-Walking Automata Do Not Recognize All Regular Languages. SIAM J. Comput. 38(2): 658-701 (2008) - Vasco Brattka:
Plottable Real Number Functions and the Computable Graph Theorem. SIAM J. Comput. 38(1): 303-328 (2008) - Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert Endre Tarjan, Jeffery R. Westbrook:
Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems. SIAM J. Comput. 38(4): 1533-1573 (2008) - Ke Chen, Sariel Har-Peled:
The Euclidean Orienteering Problem Revisited. SIAM J. Comput. 38(1): 385-397 (2008) - Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
Approximate Shortest Paths in Anisotropic Regions. SIAM J. Comput. 38(3): 802-824 (2008) - Reuven Cohen, David Peleg:
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements. SIAM J. Comput. 38(1): 276-302 (2008) - Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour:
Combination Can Be Hard: Approximability of the Unique Coverage Problem. SIAM J. Comput. 38(4): 1464-1483 (2008) - Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam D. Smith:
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1): 97-139 (2008) - Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
Lower-Stretch Spanning Trees. SIAM J. Comput. 38(2): 608-628 (2008) - Yuval Emek, David Peleg:
Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs. SIAM J. Comput. 38(5): 1761-1781 (2008) - Leah Epstein, Asaf Levin:
An APTAS for Generalized Cost Variable-Sized Bin Packing. SIAM J. Comput. 38(1): 411-428 (2008) - Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson:
Improving the Stretch Factor of a Geometric Network by Edge Augmentation. SIAM J. Comput. 38(1): 226-240 (2008) - Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee:
Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38(2): 629-657 (2008) - Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang:
Graph Distances in the Data-Stream Model. SIAM J. Comput. 38(5): 1709-1727 (2008)