Electronic Colloquium on Computational Complexity, Volume 13, 2006

Volume 13, 2006

Ran Raz, Iddo Tzameret:
The Strength of Multilinear Proofs.
Eyal Kaplan, Moni Naor, Omer Reingold:
Derandomized Constructions of k-Wise (Almost) Independent Permutations.
Joshua Buresh-Oppenheim, Rahul Santhanam:
Making Hard Problems Harder.
Jesper Torp Kristensen, Peter Bro Miltersen:
Finding small OBDDs for incompletely specified truth tables is hard.
Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg:
Nash Equilibria in Graphical Games on Trees Revisited.
Alexander Shen:
Multisource algorithmic information theory.
Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
Approximating Buy-at-Bulk k-Steiner trees.
Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk.
Nutan Limaye, Meena Mahajan, Jayalal M. N. Sarma:
Evaluating Monotone Circuits on Cylinders, Planes and Tori.
Réka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag:
Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs.
Yijia Chen, Martin Grohe:
An Isomorphism between Subexponential and Parameterized Complexity Theory.
Bruno Codenotti, Mauro Leoncini, Giovanni Resta:
Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games .
Luca Trevisan:
Pseudorandomness and Combinatorial Constructions.
Argimiro Arratia, Carlos E. Ortiz:
On a syntactic approximation to logics that capture complexity classes.
Tomás Feder, Carlos S. Subi:
On Barnette's conjecture.
Tomás Feder, Carlos S. Subi:
Partition into k-vertex subgraphs of k-partite graphs.
Toshiya Itoh:
Improved Lower Bounds for Families of epsilon-Approximate k-Restricted Min-Wise Independent Permutations.
Jin-yi Cai, Vinay Choudhary:
On the Theory of Matchgate Computations.
Janka Chlebíková, Miroslav Chlebík:
Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems.
Akinori Kawachi, Tomoyuki Yamakami:
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding.
Tomás Feder:
Constraint satisfaction: a personal perspective.
Danny Harnik, Moni Naor:
On the Compressibility of NP Instances and Cryptographic Applications.
Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Computing Nash Equilibria: Approximation and Smoothed Complexity.
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting onto functions might not be hard.
Leonid Gurvits:
Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : \\ Sharper Bounds , Simpler Proofs and Algorithmic Applications.
Ronen Gradwohl, Salil P. Vadhan, David Zuckerman:
Random Selection with an Adversarial Majority.
Hermann Gruber, Markus Holzer:
Finding Lower Bounds for Nondeterministic State Complexity is Hard.
Jonathan Katz, Chiu-Yuen Koo:
On Expected Constant-Round Protocols for Byzantine Agreement.
Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani:
Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.
Piotr Berman, Jieun K. Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar:
Packing to angles and sectors.
Li-Sha Huang, Shang-Hua Teng:
On the Approximation and Smoothed Complexity of Leontief Market Equilibria.
Vitaly Feldman:
Optimal Hardness Results for Maximizing Agreements with Monomials.
Amit Agarwal, Elad Hazan:
Efficient Algorithms for Online Game Playing and Universal Portfolio Management.
Moni Naor, Guy N. Rothblum:
The Complexity of Online Memory Checking.
Till Tantau:
The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
Tobias Riege, Jörg Rothe:
Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.
Xi Chen, Xiaotie Deng:
On the Complexity of 2D Discrete Fixed Point Problem.
David Doty, Jack H. Lutz, Satyadev Nandakumar:
Finite-State Dimension and Real Arithmetic.
John M. Hitchcock, Aduri Pavan:
Comparing Reductions to NP-Complete Sets.
Tomás Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu:
Channel assignment in wireless networks and classification of minimum graph homomorphism.
Tomás Feder, Rajeev Motwani, An Zhu:
k-connected spanning subgraphs of low degree.
Amit Deshpande, Santosh Vempala:
Adaptive Sampling and Fast Low-Rank Matrix Approximation.
Eran Ofek, Uriel Feige:
Random 3CNF formulas elude the Lovasz theta function.
Andreas Björklund, Thore Husfeldt:
Inclusion-Exclusion Based Algorithms for Graph Colouring.
Jan Arpe, Bodo Manthey:
Approximability of Minimum AND-Circuits.
Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev:
A Complete Public-Key Cryptosystem.
María López-Valdés:
Scaled Dimension of Individual Strings.
Jin-yi Cai, Vinay Choudhary:
Some Results on Matchgates and Holographic Algorithms.
Guy Wolfovitz:
The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions.
Alexander A. Razborov, Sergey Yekhanin:
An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval.
Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel:
Infinitely-Often Universal Languages and Diagonalization.
Wenbin Chen, Jiangtao Meng:
Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm.
Eldar Fischer, Orly Yahalom:
Testing Convexity Properties of Tree Colorings.
Alex Samorodnitsky:
Low-degree tests at large distances.
Scott Aaronson, Greg Kuperberg:
Quantum Versus Classical Proofs and Advice.
Salil P. Vadhan:
An Unconditional Study of Computational Zero Knowledge.
Adam R. Klivans, Alexander A. Sherstov:
Cryptographic Hardness Results for Learning Intersections of Halfspaces.
Alexander Healy:
Randomness-Efficient Sampling within NC^1.
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami:
New Results for Learning Noisy Parities and Halfspaces.
Ran Raz, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise.
Subhas Kumar Ghosh:
Unique k-SAT is as Hard as k-SAT.
Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Approximation Algorithm for the Max k-CSP Problem.
Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Note on MAX 2SAT.
Jan Arpe, Rüdiger Reischuk:
When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---.
Vitaly Feldman:
On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
Heiner Ackermann, Heiko Röglin, Berthold Vöcking:
On the Impact of Combinatorial Structure on Congestion Games.
Patrick Briest, Piotr Krysta:
Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing.
Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner:
The Complexity of Unions of Disjoint Sets.
Ludwig Staiger:
The Kolmogorov complexity of infinite words.
John M. Hitchcock, Aduri Pavan:
Hardness Hypotheses, Derandomization, and Circuit Complexity.
Henning Fernau:
Parameterized Algorithms for Hitting Set: the Weighted Case.
Andrej Bogdanov, Luca Trevisan:
Average-Case Complexity.
Shahar Dobzinski, Noam Nisan:
Approximations by Computationally-Efficient VCG-Based Mechanisms.
Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan:
Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
Noam Nisan:
A Note on the computational hardness of evolutionary stable strategies.
María López-Valdés:
Lempel-Ziv Dimension for Lempel-Ziv Compression.
Tobias Riege, Jörg Rothe:
Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
Kristoffer Arnsfelt Hansen:
Lower Bounds for Circuits with Few Modular Gates using Exponential Sums.
David Doty:
Dimension Extractors.
Spyros C. Kontogiannis, Panagiota N. Panagopoulou, Paul G. Spirakis:
Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games.
Prabhu Manyem:
Polynomial-Time Maximisation Classes: Syntactic Hierarchy.
Nils Hebbinghaus, Benjamin Doerr, Frank Neumann:
Speeding up Evolutionary Algorithms by Restricted Mutation Operators.
Frank Neumann, Carsten Witt:
Runtime Analysis of a Simple Ant Colony Optimization Algorithm.
Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry:
Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment.
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function.
Iordanis Kerenidis, Ran Raz:
The one-way communication complexity of the Boolean Hidden Matching Problem.
Per Austrin:
Balanced Max 2-Sat might not be the hardest.
Sofya Raskhodnikova, Adam Smith:
A Note on Adaptivity in Testing Properties of Bounded Degree Graphs.
Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang:
Non-Mitotic Sets.
Felix Brandt, Felix A. Fischer, Markus Holzer:
Symmetries and the Complexity of Pure Nash Equilibrium.
Matthias Englert, Heiko Röglin, Berthold Vöcking:
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP.
Takeshi Koshiba, Yoshiharu Seri:
Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme.
Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti:
Concurrent Non-Malleable Witness Indistinguishability and its Applications.
Iftach Haitner, Omer Reingold:
A New Interactive Hashing Theorem.
Emanuele Viola:
New correlation bounds for GF(2) polynomials using Gowers uniformity.
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.
Oded Goldreich:
On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits.
Meena Mahajan, Jayalal M. N. Sarma:
On the Complexity of Rank and Rigidity.
Wenceslas Fernandez de la Vega, Marek Karpinski:
Approximation Complexity of Nondense Instances of MAX-CUT.
Luis Rademacher, Santosh Vempala:
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.
Oded Lachish, Ilan Newman, Asaf Shapira:
Space Complexity vs. Query Complexity.
Wenceslas Fernandez de la Vega, Marek Karpinski:
On the Sample Complexity of MAX-CUT.
Avi Wigderson, David Xiao:
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications.
Scott Aaronson:
The Learnability of Quantum States.
Arkadev Chattopadhyay:
An improved bound on correlation between polynomials over Z_m and MOD_q.
Dan Gutfreund, Amnon Ta-Shma:
New connections between derandomization, worst-case complexity and average-case complexity.
Julia Chuzhoy, Sanjeev Khanna:
Hardness of Directed Routing with Congestion.
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai:
Improved Algorithms for Optimal Embeddings.
Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas:
Faster algorithms for finding lowest common ancestors in directed acyclic graphs.
Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang:
Strip Packing vs. Bin Packing.
Peter Bürgisser:
On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity.
Carl Bosley, Yevgeniy Dodis:
Does Privacy Require True Randomness?.
Artur Czumaj, Andrzej Lingas:
Finding a Heaviest Triangle is not Harder than Matrix Multiplication.
Amin Coja-Oghlan:
Graph partitioning via adaptive spectral techniques.
Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien:
Languages with Bounded Multiparty Communication Complexity.
Irit Dinur, Madhu Sudan, Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes.
Noga Alon, Oded Schwartz, Asaf Shapira:
An Elementary Construction of Constant-Degree Expanders.
Leslie G. Valiant:
Evolvability.
Charanjit S. Jutla:
A Simple Biased Distribution for Dinur's Construction.
Noam Livne:
All Natural NPC Problems Have Average-Case Complete Versions.
Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey).
Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Approximation of Global MAX-CSP Problems.
Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto:
Low-Depth Witnesses are Easy to Find.
Piotr Indyk:
Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1.
Sergey Yekhanin:
New Locally Decodable Codes and Private Information Retrieval Schemes.
Shankar Kalyanaraman, Christopher Umans:
On obtaining pseudorandomness from error-correcting codes..
Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf:
The polynomially bounded perfect matching problem is in NC^2.
Tanmoy Chakraborty, Samir Datta:
One-input-face MPCVP is Hard for L, but in LogDCFL.
Konstantin Pervyshev:
On Heuristic Time Hierarchies.
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.
Alexander Hertel, Alasdair Urquhart:
The Resolution Width Problem is EXPTIME-Complete.
Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Extractors and condensers from univariate polynomials.
Jin-yi Cai, Pinyan Lu:
On Symmetric Signatures in Holographic Algorithms.
Mihir Bellare, Oded Goldreich:
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
Wolfgang Maass, Prashant Joshi, Eduardo D. Sontag:
Computational aspects of feedback in neural circuits.
Wolfgang Maass, Kei Uchizawa, Rodney J. Douglas:
Energy Complexity and Entropy of Threshold Circuits.
Shien Jin Ong, Salil P. Vadhan:
Zero Knowledge and Soundness are Symmetric.
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL.
Venkatesan Guruswami, Kunal Talwar:
Hardness of Low Congestion Routing in Directed Graphs.
Olaf Beyersdorff:
On the Deduction Theorem and Complete Disjoint NP-Pairs.
Frank Neumann, Carsten Witt:
Ant Colony Optimization and the Minimum Spanning Tree Problem.
Claire Kenyon-Mathieu, Warren Schudy:
How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments.
Jin-yi Cai, Pinyan Lu:
Holographic Algorithms: From Art to Science.
Christoph Buchheim, Peter J. Cameron, Taoyang Wu:
On the Subgroup Distance Problem.
Chris Peikert, Alon Rosen:
Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors.
Chris Peikert:
Limits on the Hardness of Lattice Problems in $\ell_p$ Norms.
Lance Fortnow, Rakesh Vohra:
The Complexity of Forecast Testing.
Patrick Briest:
Towards Hardness of Envy-Free Pricing.
Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan:
The communication complexity of correlation.
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.
Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer:
The Complexity of Generalized Satisfiability for Linear Temporal Logic.
Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam:
Uniform Hardness Amplification in NP via Monotone Codes.
Wenceslas Fernandez de la Vega, Marek Karpinski:
Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP.
Tomás Feder, Rajeev Motwani:
Finding large cycles in Hamiltonian graphs.
Lance Fortnow, Rahul Santhanam:
Fixed-Polynomial Size Circuit Bounds.
Gyula Györ:
Representing Boolean OR function by quadratic polynomials modulo 6.
Predrag T. Tosic:
Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata.
Tomás Feder, Phokion G. Kolaitis:
Closures and dichotomies for quantified constraints.