Electronic Colloquium on Computational Complexity, Volume 13, 2006
: Improved Lower Bounds for Families of epsilon-Approximate k-Restricted Min-Wise Independent Permutations.
: Constraint satisfaction: a personal perspective.
: Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : \\ Sharper Bounds , Simpler Proofs and Algorithmic Applications.
: Optimal Hardness Results for Maximizing Agreements with Monomials.
: The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
, Jörg Rothe
: Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.
: The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions.
, Jiangtao Meng
: Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm.
, Rüdiger Reischuk
: When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---.
: On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
: Parameterized Algorithms for Hitting Set: the Weighted Case.
: A Note on the computational hardness of evolutionary stable strategies.
, Jörg Rothe
: Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
: Polynomial-Time Maximisation Classes: Syntactic Hierarchy.
: Balanced Max 2-Sat might not be the hardest.
: New correlation bounds for GF(2) polynomials using Gowers uniformity.
: On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits.
, David Xiao
: Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications.
: On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity.
: All Natural NPC Problems Have Average-Case Complete Versions.
: Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1.
: New Locally Decodable Codes and Private Information Retrieval Schemes.