- 2009
- Leonard M. Adleman, Jarkko Kari, Lila Kari, Dustin Reishus, Petr Sosík:
The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly. SIAM J. Comput. 38(6): 2356-2381 (2009) - Susanne Albers:
On the Value of Coordination in Network Design. SIAM J. Comput. 38(6): 2273-2302 (2009) - David J. Aldous, Charles Bordenave, Marc Lelarge:
Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions. SIAM J. Comput. 38(6): 2382-2410 (2009) - Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. SIAM J. Comput. 38(5): 1987-2006 (2009) - Baruch Awerbuch, Rohit Khandekar:
Stateless Distributed Gradient Descent for Positive Linear Programs. SIAM J. Comput. 38(6): 2468-2486 (2009) - Libor Barto, Marcin Kozik, Todd Niven:
The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38(5): 1782-1802 (2009) - Louay M. J. Bazzi:
Polylogarithmic Independence Can Fool DNF Formulas. SIAM J. Comput. 38(6): 2220-2272 (2009) - Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid:
Spanners of Complete k-Partite Geometric Graphs. SIAM J. Comput. 38(5): 1803-1820 (2009) - Mee Yee Chan, Wun-Tat Chan, Francis Y. L. Chin, Stanley P. Y. Fung, Ming-Yang Kao:
Linear-Time Haplotype Inference on Pedigrees without Recombinations and Mating Loops. SIAM J. Comput. 38(6): 2179-2197 (2009) - T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Aleksandrs Slivkins:
Metric Embeddings with Relaxed Guarantees. SIAM J. Comput. 38(6): 2303-2329 (2009) - Artur Czumaj, Asaf Shapira, Christian Sohler:
Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. SIAM J. Comput. 38(6): 2499-2510 (2009) - Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney:
Sampling Algorithms and Coresets for $\ellp Regression. SIAM J. Comput. 38(5): 2060-2078 (2009) - Luc Devroye, James King, Colin McDiarmid:
Random Hyperplane Search Trees. SIAM J. Comput. 38(6): 2411-2425 (2009) - Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
The Complexity of Weighted Boolean #CSP. SIAM J. Comput. 38(5): 1970-1986 (2009) - Wouter Gelade, Wim Martens, Frank Neven:
Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. SIAM J. Comput. 38(5): 2021-2043 (2009) - Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. SIAM J. Comput. 38(6): 2330-2355 (2009) - Sudipto Guha, Andrew McGregor:
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams. SIAM J. Comput. 38(5): 2044-2059 (2009) - Sudipto Guha, Adam Meyerson, Kamesh Munagala:
A Constant Factor Approximation for the Single Sink Edge Installation Problem. SIAM J. Comput. 38(6): 2426-2442 (2009) - Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung:
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. SIAM J. Comput. 38(6): 2162-2178 (2009) - Kiran S. Kedlaya, Sergey Yekhanin:
Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. SIAM J. Comput. 38(5): 1952-1969 (2009) - Marcin Kozik:
A 2EXPTIME Complete Varietal Membership Problem. SIAM J. Comput. 38(6): 2443-2467 (2009) - Robert Krauthgamer, Yuval Rabani:
Improved Lower Bounds for Embeddings intoL1$. SIAM J. Comput. 38(6): 2487-2498 (2009) - GaHyun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski:
Profiles of Tries. SIAM J. Comput. 38(5): 1821-1880 (2009) - Ulrich Schmid, Bettina Weiss, Idit Keidar:
Impossibility Results and Lower Bounds for Consensus under Link Failures. SIAM J. Comput. 38(5): 1912-1951 (2009) - Alexander A. Sherstov:
SeparatingAC0 from Depth-2 Majority Circuits. SIAM J. Comput. 38(6): 2113-2129 (2009) - Amir Shpilka:
Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. SIAM J. Comput. 38(6): 2130-2161 (2009) - Holger Spakowski, Rahul Tripathi:
Hierarchical Unambiguity. SIAM J. Comput. 38(5): 2079-2112 (2009) - Umberto Straccia, Manuel Ojeda-Aciego, Carlos Viegas Damásio:
On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs. SIAM J. Comput. 38(5): 1881-1911 (2009) - Yngve Villanger, Pinar Heggernes, Christophe Paul, Jan Arne Telle:
Interval Completion Is Fixed Parameter Tractable. SIAM J. Comput. 38(5): 2007-2020 (2009) - Jing Xiao, Lan Liu, Lirong Xia, Tao Jiang:
Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations. SIAM J. Comput. 38(6): 2198-2219 (2009)