SIAM Journal on Computing, Volume 38

Volume 38, Number 1, 2008

• Nir Halman:
  On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model. 1-45
  
• Sophie Laplante, Frédéric Magniez:
  Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. 46-62
  
• Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
  Minimizing Disjunctive Normal Form Formulas and AC⁰ Circuits Given a Truth Table. 63-84
  
• Anna Pagh, Rasmus Pagh:
  Uniform Hashing in Constant Time and Optimal Space. 85-96
  
• Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith:
  Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. 97-139
  
• Dana Moshkovitz, Ran Raz:
  Sub-Constant Error Low Degree Test of Almost-Linear Size. 140-180
  
• Bodo Manthey:
  On Approximating Restricted Cycle Covers. 181-206
  
• Eldar Fischer, Arie Matsliah:
  Testing Graph Isomorphism. 207-225
  
• Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson:
  Improving the Stretch Factor of a Geometric Network by Edge Augmentation. 226-240
  
• Kamal Jain, Vijay V. Vazirani:
  Equitable Cost Allocations via Primal--Dual-Type Algorithms. 241-256
  
• Mark de Berg, Chris Gray:
  Vertical Ray Shooting and Computing Depth Orders for Fat Objects. 257-275
  
• Reuven Cohen, David Peleg:
  Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements. 276-302
  
• Vasco Brattka:
  Plottable Real Number Functions and the Computable Graph Theorem. 303-328
  
• Peter Jonsson, Fredrik Kuivinen, Gustav Nordh:
  MAX ONES Generalized to Larger Domains. 329-365
  
• Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
  Exponential Separation of Quantum and Classical One-Way Communication Complexity. 366-384
  
• Ke Chen, Sariel Har-Peled:
  The Euclidean Orienteering Problem Revisited. 385-397
  
• János Balogh, József Békési, Gábor Galambos, Gerhard Reinelt:
  Lower Bound for the Online Bin Packing Problem with Restricted Repacking. 398-410
  
• Leah Epstein, Asaf Levin:
  An APTAS for Generalized Cost Variable-Sized Bin Packing. 411-428
  
• Csaba D. Tóth:
  Binary Space Partitions for Axis-Aligned Fat Rectangles. 429-447
  

Volume 38, Number 2, 2008

• Vladimir Trifonov:
  An O(logn loglogn) Space Algorithm for Undirected st-Connectivity. 449-483
  
• Ben Morris:
  The Mixing Time of the Thorp Shuffle. 484-504
  
• Noga Alon, Asaf Shapira:
  Every Monotone Graph Property Is Testable. 505-522
  
• Saurabh Sanghvi, Salil P. Vadhan:
  The Round Complexity of Two-Party Random Selection. 523-550
  
• Eli Ben-Sasson, Madhu Sudan:
  Short PCPs with Polylog Query Complexity. 551-607
  
• Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
  Lower-Stretch Spanning Trees. 608-628
  
• Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee:
  Improved Approximation Algorithms for Minimum Weight Vertex Separators. 629-657
  
• Mikolaj Bojanczyk, Thomas Colcombet:
  Tree-Walking Automata Do Not Recognize All Regular Languages. 658-701
  
• Rafael Pass, Alon Rosen:
  New and Improved Constructions of Nonmalleable Cryptographic Protocols. 702-752
  

Volume 38, Number 3, 2008

• Yaoyun Shi, Yufan Zhu:
  Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement. 753-766
  
• Anil Maheshwari, Norbert Zeh:
  I/O-Efficient Planar Separators. 767-801
  
• Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
  Approximate Shortest Paths in Anisotropic Regions. 802-824
  
• Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio:
  A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover. 825-840
  
• Marcelo Arenas, Wenfei Fan, Leonid Libkin:
  On the Complexity of Verifying Consistency of XML Specifications. 841-880
  
• Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen:
  Competitive Online Approximation of the Optimal Search Ratio. 881-898
  
• Boris Aronov, Sariel Har-Peled:
  On Approximating the Depth and Related Problems. 899-921
  
• Àngel J. Gil, Miki Hermann, Gernot Salzer, Bruno Zanuttini:
  Efficient Algorithms for Description Problems over Finite Totally Ordered Domains. 922-945
  
• C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, Louxin Zhang:
  Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment. 946-962
  
• Igor L. Markov, Yaoyun Shi:
  Simulating Quantum Computation by Contracting Tensor Networks. 963-981
  
• Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin:
  Efficient Colored Orthogonal Range Counting. 982-1011
  
• Petr Hlinený, Sang-il Oum:
  Finding Branch-Decompositions and Rank-Decompositions. 1012-1032
  
• Parikshit Gopalan:
  Query-Efficient Algorithms for Polynomial Interpolation over Composites. 1033-1057
  
• Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger:
  Exact Algorithms for Treewidth and Minimum Fill-In. 1058-1079
  
• Jack H. Lutz, Elvira Mayordomo:
  Dimensions of Points in Self-Similar Fractals. 1080-1112
  
• Jordi Levy, Manfred Schmidt-Schauß, Mateu Villaret:
  The Complexity of Monadic Second-Order Unification. 1113-1140
  
• Ravindran Kannan, Hadi Salmasian, Santosh Vempala:
  The Spectral Method for General Mixture Models. 1141-1156
  
• Nikhil Bansal, Don Coppersmith, Maxim Sviridenko:
  Improved Approximation Algorithms for Broadcast Scheduling. 1157-1174
  
• Ketan Mulmuley, Milind A. Sohoni:
  Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. 1175-1206
  

Volume 38, Number 4, 2008

• Dorit Aharonov, Michael Ben-Or:
  Fault-Tolerant Quantum Computation with Constant Error Rate. 1207-1282
  
• Sanjay Jain, Frank Stephan:
  Mitotic Classes in Inductive Inference. 1283-1299
  
• Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung:
  On Monotone Formula Composition of Perfect Zero-Knowledge Languages. 1300-1329
  
• Jon M. Kleinberg, Mark Sandler, Aleksandrs Slivkins:
  Network Failure Detection and Graph Connectivity. 1330-1346
  
• Michael Alekhnovich, Alexander A. Razborov:
  Resolution Is Not Automatizable Unless W[P] Is Tractable. 1347-1363
  
• Albert Atserias, Anuj Dawar, Martin Grohe:
  Preservation under Extensions on Well-Behaved Finite Structures. 1364-1381
  
• Dániel Marx:
  Closest Substring Problems with Small Distances. 1382-1410
  
• Ivan D. Baev, Rajmohan Rajaraman, Chaitanya Swamy:
  Approximation Algorithms for Data Placement Problems. 1411-1429
  
• Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn:
  Faster Algorithms for Minimum Cycle Basis in Directed Graphs. 1430-1447
  
• Subhash Khot, Assaf Naor:
  Linear Equations Modulo 2 and the L₁ Diameter of Convex Bodies. 1448-1463
  
• Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour:
  Combination Can Be Hard: Approximability of the Unique Coverage Problem. 1464-1483
  
• Shuji Kijima, Tomomi Matsui:
  Approximation Algorithm and Perfect Sampler for Closed Jackson Networks with Single Servers. 1484-1503
  
• Lusheng Wang, Yu Lin, Xiaowen Liu:
  Approximation Algorithms for Biclustering Problems. 1504-1518
  
• Marcin Jurdzinski, Mike Paterson, Uri Zwick:
  A Deterministic Subexponential Algorithm for Solving Parity Games. 1519-1532
  
• Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert Endre Tarjan, Jeffery Westbrook:
  Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems. 1533-1573
  
• Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers:
  The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. 1574-1601
  
• Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden:
  The Price of Stability for Network Design with Fair Cost Allocation. 1602-1623
  
• Ran Raz, Amir Shpilka, Amir Yehudayoff:
  A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. 1624-1647
  
• Adam Meyerson, Kamesh Munagala, Serge A. Plotkin:
  Cost-Distance: Two Metric Network Design. 1648-1659
  

Volume 38, Number 5, 2008

• Boaz Barak, Oded Goldreich:
  Universal Arguments and their Applications. 1661-1694
  
• Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf:
  Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. 1695-1708
  
• Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang:
  Graph Distances in the Data-Stream Model. 1709-1727
  
• Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb:
  Private Approximation of Search Problems. 1728-1760
  
• Yuval Emek, David Peleg:
  Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs. 1761-1781
  

Volume 38, Number 5, 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). 1782-1802
  
• Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid:
  Spanners of Complete k-Partite Geometric Graphs. 1803-1820
  
• GaHyun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski:
  Profiles of Tries. 1821-1880
  
• 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. 1881-1911
  
• Ulrich Schmid, Bettina Weiss, Idit Keidar:
  Impossibility Results and Lower Bounds for Consensus under Link Failures. 1912-1951
  
• Kiran S. Kedlaya, Sergey Yekhanin:
  Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. 1952-1969
  
• Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
  The Complexity of Weighted Boolean CSP. 1970-1986
  
• Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
  On the Complexity of Numerical Analysis. 1987-2006
  
• Yngve Villanger, Pinar Heggernes, Christophe Paul, Jan Arne Telle:
  Interval Completion Is Fixed Parameter Tractable. 2007-2020
  
• Wouter Gelade, Wim Martens, Frank Neven:
  Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. 2021-2043
  
• Sudipto Guha, Andrew McGregor:
  Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams. 2044-2059
  
• Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney:
  Sampling Algorithms and Coresets for $\ell_p Regression. 2060-2078
  
• Holger Spakowski, Rahul Tripathi:
  Hierarchical Unambiguity. 2079-2112
  

Volume 38, Number 6, 2009

• Alexander A. Sherstov:
  SeparatingAC⁰ from Depth-2 Majority Circuits. 2113-2129
  
• Amir Shpilka:
  Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. 2130-2161
  
• Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung:
  Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. 2162-2178
  
• 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. 2179-2197
  
• 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. 2198-2219
  
• Louay M. J. Bazzi:
  Polylogarithmic Independence Can Fool DNF Formulas. 2220-2272
  
• Susanne Albers:
  On the Value of Coordination in Network Design. 2273-2302
  
• T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Aleksandrs Slivkins:
  Metric Embeddings with Relaxed Guarantees. 2303-2329
  
• Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
  The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. 2330-2355
  
• 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. 2356-2381
  
• David J. Aldous, Charles Bordenave, Marc Lelarge:
  Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions. 2382-2410
  
• Luc Devroye, James King, Colin McDiarmid:
  Random Hyperplane Search Trees. 2411-2425
  
• Sudipto Guha, Adam Meyerson, Kamesh Munagala:
  A Constant Factor Approximation for the Single Sink Edge Installation Problem. 2426-2442
  
• Marcin Kozik:
  A 2EXPTIME Complete Varietal Membership Problem. 2443-2467
  
• Baruch Awerbuch, Rohit Khandekar:
  Stateless Distributed Gradient Descent for Positive Linear Programs. 2468-2486
  
• Robert Krauthgamer, Yuval Rabani:
  Improved Lower Bounds for Embeddings intoL₁$. 2487-2498
  
• Artur Czumaj, Asaf Shapira, Christian Sohler:
  Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. 2499-2510
  

Last update Sat May 26 07:00:44 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page