Volume 37,
Number 1,
2007
- Frank Harary, Wolfgang Slany, Oleg Verbitsky:
On the Computational Complexity of the Forcing Chromatic Number.
1-19
Electronic Edition (link) BibTeX
- Hartmut Klauck:
Lower Bounds for Quantum Communication Complexity.
20-46
Electronic Edition (link) BibTeX
- Dorit Aharonov, Amnon Ta-Shma:
Adiabatic Quantum State Generation.
47-82
Electronic Edition (link) BibTeX
- Phillip G. Bradford, Michael N. Katehakis:
A Probabilistic Study on Combinatorial Expanders and Hashing.
83-111
Electronic Edition (link) BibTeX
- Matthew Andrews, Lisa Zhang:
Hardness of the Undirected Congestion Minimization Problem.
112-131
Electronic Edition (link) BibTeX
- Florent R. Madelaine, Iain A. Stewart:
Constraint Satisfaction, Logic and Forbidden Patterns.
132-163
Electronic Edition (link) BibTeX
- Dimitris Achlioptas, Vladlen Koltun:
Special Section on Foundations of Computer Science.
165 BibTeX
- Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev:
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation.
166-194
Electronic Edition (link) BibTeX
- Qi Cheng, Daqing Wan:
On the List and Bounded Distance Decodability of Reed-Solomon Codes.
195-209
Electronic Edition (link) BibTeX
- Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness.
210-239
Electronic Edition (link) BibTeX
- Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality - Almost.
240-251
Electronic Edition (link) BibTeX
- Steve Chien, Alistair Sinclair:
Algebras with Polynomial Identities and Computing the Determinant.
252-266
Electronic Edition (link) BibTeX
- Daniele Micciancio, Oded Regev:
Worst-Case to Average-Case Reductions Based on Gaussian Measures.
267-302
Electronic Edition (link) BibTeX
- Kamal Jain:
A Polynomial Time Algorithm for Computing an Arrow-Debreu Market Equilibrium for Linear Utilities.
303-318
Electronic Edition (link) BibTeX
- Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.
319-357
Electronic Edition (link) BibTeX
Volume 37,
Number 2,
2007
- A. Pavan, Srikanta Tirthapura:
Range-Efficient Counting of Distinct Elements in a Massive Data Stream.
359-379
Electronic Edition (link) BibTeX
- Boaz Barak, Shien Jin Ong, Salil P. Vadhan:
Derandomization in Cryptography.
380-400
Electronic Edition (link) BibTeX
- Gregory Mounie, Christophe Rapine, Denis Trystram:
A 3/2-Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks.
401-412
Electronic Edition (link) BibTeX
- Frédéric Magniez, Miklos Santha, Mario Szegedy:
Quantum Algorithms for the Triangle Problem.
413-424
Electronic Edition (link) BibTeX
- Yuri Gurevich, Paul Schupp:
Membership Problem for the Modular Group.
425-459
Electronic Edition (link) BibTeX
- Anna Moss, Yuval Rabani:
Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems.
460-481
Electronic Edition (link) BibTeX
- Eldar Fischer, Ilan Newman:
Testing versus Estimation of Graph Properties.
482-501
Electronic Edition (link) BibTeX
- Amitabha Roy, Howard Straubing:
Definability of Languages by Generalized First-Order Formulas over N+.
502-521
Electronic Edition (link) BibTeX
- Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sue Whitesides:
Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra.
522-551
Electronic Edition (link) BibTeX
- Hartmut Klauck:
One-Way Communication Complexity and the Ne[c-caron]iporuk Lower Bound on Formula Size.
552-583
Electronic Edition (link) BibTeX
- Sunil Arya, Theocharis Malamatos, David M. Mount, Ka Chun Wong:
Optimal Expected-Case Planar Point Location.
584-610
Electronic Edition (link) BibTeX
- Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha:
Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates.
611-629
Electronic Edition (link) BibTeX
- Naveen Garg, Jochen Könemann:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
630-652
Electronic Edition (link) BibTeX
- Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff:
Approximation Algorithms for Orienteering and Discounted-Reward TSP.
653-670
Electronic Edition (link) BibTeX
Volume 37,
Number 3,
2007
- Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo:
Effective Strong Dimension in Algorithmic Information and Computational Complexity.
671-705
Electronic Edition (link) BibTeX
- Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, Martin Skutella:
New Approaches for Virtual Private Network Design.
706-721
Electronic Edition (link) BibTeX
- Partha Dutta, Rachid Guerraoui, Bastian Pochon:
The Time-Complexity of Local Decision in Distributed Agreement.
722-756
Electronic Edition (link) BibTeX
- Stavros G. Kolliopoulos, Satish Rao:
A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem.
757-782
Electronic Edition (link) BibTeX
- William Aiello, Frank Thomson Leighton:
Hamming Codes, Hypercube Embeddings, and Fault Tolerance.
783-803
Electronic Edition (link) BibTeX
- Assaf Naor, Gideon Schechtman:
Planar Earthmover Is Not in L1.
804-826
Electronic Edition (link) BibTeX
- Ryan O'Donnell, Rocco A. Servedio:
Learning Monotone Decision Trees in Polynomial Time.
827-844
Electronic Edition (link) BibTeX
- Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
845-869
Electronic Edition (link) BibTeX
- José R. Correa, Michel X. Goemans:
Improved Bounds on Nonblocking 3-Stage Clos Networks.
870-894
Electronic Edition (link) BibTeX
- Michael Molloy, Mohammad R. Salavatipour:
The Resolution Complexity of Random Constraint Satisfaction Problems.
895-922
Electronic Edition (link) BibTeX
- Xujin Chen, Xiaodong Hu, Wenan Zang:
A Min-Max Theorem on Tournaments.
923-937
Electronic Edition (link) BibTeX
- Cristopher Moore, Daniel N. Rockmore, Alexander Russell, Leonard J. Schulman:
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts.
938-958
Electronic Edition (link) BibTeX
- Noga Alon, Eldar Fischer, Ilan Newman:
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs.
959-976
Electronic Edition (link) BibTeX
Volume 37,
Number 4,
2007
Volume 37,
Number 5,
2008
- Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, Vijaya Ramachandran:
Oracles for Distances Avoiding a Failed Node or Link.
1299-1318
Electronic Edition (link) BibTeX
- Jochen Könemann, Stefano Leonardi, Guido Schäfer, Stefan H. M. van Zwam:
A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game.
1319-1341
Electronic Edition (link) BibTeX
- Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer:
The Forgetron: A Kernel-Based Perceptron on a Budget.
1342-1372
Electronic Edition (link) BibTeX
- Bradford G. Nickerson, Qingxiu Shi:
On k-d Range Search with Patricia Tries.
1373-1386
Electronic Edition (link) BibTeX
- Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum Property Testing.
1387-1400
Electronic Edition (link) BibTeX
- Karl Rubin, Alice Silverberg:
Compression in Finite Fields and Torus-Based Cryptography.
1401-1428
Electronic Edition (link) BibTeX
- Ivona Bezáková, Daniel Stefankovic, Vijay V. Vazirani, Eric Vigoda:
Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems.
1429-1454
Electronic Edition (link) BibTeX
- Liam Roditty, Uri Zwick:
Improved Dynamic Reachability Algorithms for Directed Graphs.
1455-1471
Electronic Edition (link) BibTeX
- Aaron Archer, Asaf Levin, David P. Williamson:
A Faster, Better Approximation Algorithm for the Minimum Latency Problem.
1472-1498
Electronic Edition (link) BibTeX
- John Augustine, Sandy Irani, Chaitanya Swamy:
Optimal Power-Down Strategies.
1499-1516
Electronic Edition (link) BibTeX
- Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang:
Splitting NP-Complete Sets.
1517-1535
Electronic Edition (link) BibTeX
- Jon Feldman, Ryan O'Donnell, Rocco A. Servedio:
Learning Mixtures of Product Distributions over Discrete Domains.
1536-1564
Electronic Edition (link) BibTeX
- Leslie G. Valiant:
Holographic Algorithms.
1565-1594
Electronic Edition (link) BibTeX
- Ho-Leung Chan, Tak Wah Lam, Kin-Shing Liu:
Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling.
1595-1612
Electronic Edition (link) BibTeX
- Hagit Attiya, David Hay:
Randomization Does Not Reduce the Average Delay in Parallel Packet Switches.
1613-1636
Electronic Edition (link) BibTeX
- Andrew V. Goldberg:
A Practical Shortest Path Algorithm with Linear Expected Time.
1637-1655
Electronic Edition (link) BibTeX
- Elliot Anshelevich, David Kempe, Jon M. Kleinberg:
Stability of Load Balancing Algorithms in Dynamic Adversarial Systems.
1656-1673
Electronic Edition (link) BibTeX
- Hubie Chen:
The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case.
1674-1701
Electronic Edition (link) BibTeX
Volume 37,
Number 6,
2008
- Irit Dinur, Éva Tardos:
Special Issue on Foundations of Computer Science.
BibTeX
- Noga Alon, Asaf Shapira:
A Characterization of the (Natural) Graph Properties Testable with One-Sided Error.
1703-1727
Electronic Edition (link) BibTeX
- Penny E. Haxell, Brendan Nagle, Vojtech Rödl:
An Algorithmic Version of the Hypergraph Regularity Method.
1728-1776
Electronic Edition (link) BibTeX
- Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio:
Agnostically Learning Halfspaces.
1777-1805
Electronic Edition (link) BibTeX
- Navin Goyal, Guy Kindler, Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem.
1806-1841
Electronic Edition (link) BibTeX
- Cristopher Moore, Alexander Russell, Leonard J. Schulman:
The Symmetric Group Defies Strong Fourier Sampling.
1842-1864
Electronic Edition (link) BibTeX
- Ivan Damgård, Serge Fehr, Louis Salvail, Christian Schaffner:
Cryptography in the Bounded-Quantum-Storage Model.
1865-1890
Electronic Edition (link) BibTeX
- Rafael Pass, Alon Rosen:
Concurrent Nonmalleable Commitments.
1891-1925
Electronic Edition (link) BibTeX
- Philip N. Klein:
A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights.
1926-1952
Electronic Edition (link) BibTeX
Copyright © Wed Jul 23 16:33:10 2008
by Michael Ley (ley@uni-trier.de)
