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 updated on Sat May 25 06:37:39 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page