Electronic Colloquium on Computational Complexity, Volume 12, 2005
: Near optimality of the priority sampling procedure.
: Quantum Computing, Postselection, and Probabilistic Polynomial-Time.
: Constraint Satisfaction on Finite Groups with Near Subgroups.
: Recognizing permutation functions in polynomial time.
: Theory and Application of Width Bounded Geometric Separator.
: On Promise Problems (a survey in memory of Shimon Even [1935-2004]).
: On the Lattice of Clones Below the Polynomial Time Functions.
, Marco Laumanns
: Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization.
: Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms.
: Quantum Information and the PCP Theorem.
: (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids.
: Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates.
, Amir Shpilka
: Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits.
Predrag T. Tosic
: On Complexity of Counting Fixed Points in Certain Classes of Graph Automata.
: Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
: Simple extractors via constructions of cryptographic pseudo-random generators.
: Expanders and time-restricted branching programs.
: Learning Juntas in the Presence of Noise.
Predrag T. Tosic
: Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs .
, Dana Ron
: On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms.
, Amit Sahai
: How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation.
: Bravely, Moderately: A Common Theme in Four Recent Results.
: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number.
: A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification.
: Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources.
: On the expansion of the giant component in percolated (n,d,lambda) graphs.
: A nonlinear bound on the number of wires in bounded depth circuits.
: Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries.
: The normal form of reversible circuits consisting of CNOT and NOT gates.
: QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols.
: Constructions of low-degree and error-correcting epsilon-biased sets.