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.
  

Last update Fri May 24 16:37:03 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page