All reports in year 2006:

__
TR06-001
| 1st January 2006
__

Ran Raz, Iddo Tzameret#### The Strength of Multilinear Proofs

__
TR06-002
| 4th January 2006
__

Eyal Kaplan, Moni Naor, Omer Reingold#### Derandomized Constructions of k-Wise (Almost) Independent Permutations

__
TR06-003
| 8th January 2006
__

Joshua Buresh-Oppenheim, Rahul Santhanam#### Making Hard Problems Harder

__
TR06-004
| 6th January 2006
__

Jesper Torp Kristensen, Peter Bro Miltersen#### Finding small OBDDs for incompletely specified truth tables is hard

__
TR06-005
| 13th December 2005
__

Edith Elkind, Leslie Ann Goldberg, Paul Goldberg#### Nash Equilibria in Graphical Games on Trees Revisited

__
TR06-006
| 16th December 2005
__

Alexander Shen#### Multisource algorithmic information theory

__
TR06-007
| 23rd November 2005
__

MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour#### Approximating Buy-at-Bulk $k$-Steiner trees

__
TR06-008
| 23rd November 2005
__

MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour#### Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk

__
TR06-009
| 10th January 2006
__

Nutan Limaye, Meena Mahajan, Jayalal Sarma#### Evaluating Monotone Circuits on Cylinders, Planes and Tori

__
TR06-010
| 1st December 2005
__

Reka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag#### Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

__
TR06-011
| 2nd January 2006
__

Yijia Chen, Martin Grohe#### An Isomorphism between Subexponential and Parameterized Complexity Theory

__
TR06-012
| 17th January 2006
__

Bruno Codenotti, Mauro Leoncini, Giovanni Resta#### Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games

__
TR06-013
| 24th January 2006
__

Luca Trevisan#### Pseudorandomness and Combinatorial Constructions

__
TR06-014
| 20th December 2005
__

Argimiro Arratia, Carlos E. Ortiz#### On a syntactic approximation to logics that capture complexity classes

__
TR06-015
| 1st February 2006
__

Tomas Feder, Carlos Subi#### On Barnette's conjecture

__
TR06-016
| 1st February 2006
__

Tomas Feder, Carlos Subi#### Partition into $k$-vertex subgraphs of $k$-partite graphs

__
TR06-017
| 12th January 2006
__

Toshiya Itoh#### Improved Lower Bounds for Families of $\varepsilon$-Approximate k$-Restricted Min-Wise Independent Permutations

__
TR06-018
| 8th February 2006
__

Jin-Yi Cai, Vinay Choudhary#### On the Theory of Matchgate Computations

__
TR06-019
| 24th November 2005
__

Janka Chlebíková, Miroslav Chlebík#### Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

__
TR06-020
| 10th February 2006
__

Akinori Kawachi, Tomoyuki Yamakami#### Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Revisions: 1

__
TR06-021
| 10th February 2006
__

Tomas Feder#### Constraint satisfaction: a personal perspective

__
TR06-022
| 17th February 2006
__

Danny Harnik, Moni Naor#### On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

__
TR06-023
| 7th February 2006
__

Xi Chen, Xiaotie Deng, Shang-Hua Teng#### Computing Nash Equilibria: Approximation and Smoothed Complexity

__
TR06-024
| 18th February 2006
__

Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin#### Inverting onto functions might not be hard

__
TR06-025
| 19th January 2006
__

Leonid Gurvits#### Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\\ Sharper Bounds , Simpler Proofs and Algorithmic Applications

__
TR06-026
| 27th February 2006
__

Ronen Gradwohl, Salil Vadhan, David Zuckerman#### Random Selection with an Adversarial Majority

__
TR06-027
| 22nd February 2006
__

Hermann Gruber, Markus Holzer#### Finding Lower Bounds for Nondeterministic State Complexity is Hard

__
TR06-028
| 21st February 2006
__

Jonathan Katz, Chiu-Yuen Koo#### On Expected Constant-Round Protocols for Byzantine Agreement

__
TR06-029
| 21st February 2006
__

Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani#### Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity

__
TR06-030
| 17th January 2006
__

Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar#### Packing to angles and sectors

__
TR06-031
| 27th February 2006
__

Li-Sha Huang, Shang-Hua Teng#### On the Approximation and Smoothed Complexity of Leontief Market Equilibria

__
TR06-032
| 25th February 2006
__

Vitaly Feldman#### Optimal Hardness Results for Maximizing Agreements with Monomials

__
TR06-033
| 2nd March 2006
__

Amit Agarwal, Elad Hazan#### Efficient Algorithms for Online Game Playing and Universal Portfolio Management

__
TR06-034
| 9th March 2006
__

Moni Naor, Guy Rothblum#### The Complexity of Online Memory Checking

__
TR06-035
| 19th January 2006
__

Till Tantau#### The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters

__
TR06-036
| 7th February 2006
__

Tobias Riege, Jörg Rothe#### Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems

Revisions: 1

__
TR06-037
| 10th February 2006
__

Xi Chen, Xiaotie Deng#### On the Complexity of 2D Discrete Fixed Point Problem

__
TR06-038
| 10th February 2006
__

David Doty, Jack H. Lutz, Satyadev Nandakumar, Satyadev Nandakumar#### Finite-State Dimension and Real Arithmetic

__
TR06-039
| 28th February 2006
__

John Hitchcock, A. Pavan#### Comparing Reductions to NP-Complete Sets

__
TR06-040
| 6th March 2006
__

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu#### Channel assignment in wireless networks and classification of minimum graph homomorphism

__
TR06-041
| 6th March 2006
__

Tomas Feder, Rajeev Motwani, An Zhu#### k-connected spanning subgraphs of low degree

__
TR06-042
| 16th March 2006
__

Amit Deshpande, Santosh Vempala#### Adaptive Sampling and Fast Low-Rank Matrix Approximation

__
TR06-043
| 22nd March 2006
__

Eran Ofek, Uriel Feige#### Random 3CNF formulas elude the Lovasz theta function

__
TR06-044
| 24th January 2006
__

Andreas Björklund, Thore Husfeldt#### Inclusion-Exclusion Based Algorithms for Graph Colouring

__
TR06-045
| 13th March 2006
__

Jan Arpe, Bodo Manthey#### Approximability of Minimum AND-Circuits

Revisions: 1

__
TR06-046
| 1st April 2006
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### A Complete Public-Key Cryptosystem

Comments: 1

__
TR06-047
| 11th February 2006
__

Maria Lopez-Valdes#### Scaled Dimension of Individual Strings

__
TR06-048
| 9th April 2006
__

Jin-Yi Cai, Vinay Choudhary#### Some Results on Matchgates and Holographic Algorithms

__
TR06-049
| 9th April 2006
__

Guy Wolfovitz#### The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions

__
TR06-050
| 18th April 2006
__

Alexander Razborov, Sergey Yekhanin#### An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

__
TR06-051
| 8th April 2006
__

Alan Nash, Russell Impagliazzo, Jeff Remmel#### Infinitely-Often Universal Languages and Diagonalization

__
TR06-052
| 15th April 2006
__

Wenbin Chen, Jiangtao Meng#### Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm

__
TR06-053
| 6th April 2006
__

Eldar Fischer, Orly Yahalom#### Testing Convexity Properties of Tree Colorings

__
TR06-054
| 16th April 2006
__

Alex Samorodnitsky#### Low-degree tests at large distances

__
TR06-055
| 10th April 2006
__

Scott Aaronson, Greg Kuperberg#### Quantum Versus Classical Proofs and Advice

__
TR06-056
| 27th April 2006
__

Salil Vadhan#### An Unconditional Study of Computational Zero Knowledge

__
TR06-057
| 19th April 2006
__

Adam Klivans, Alexander A. Sherstov#### Cryptographic Hardness Results for Learning Intersections of Halfspaces

__
TR06-058
| 25th April 2006
__

Alexander Healy#### Randomness-Efficient Sampling within NC^1

Revisions: 1

__
TR06-059
| 3rd May 2006
__

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami#### New Results for Learning Noisy Parities and Halfspaces

__
TR06-060
| 4th May 2006
__

Ran Raz, Amir Shpilka, Amir Yehudayoff#### A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

__
TR06-061
| 5th May 2006
__

Venkatesan Guruswami, Prasad Raghavendra#### Hardness of Learning Halfspaces with Noise

__
TR06-062
| 24th April 2006
__

Subhas Kumar Ghosh#### Unique k-SAT is as Hard as k-SAT

Revisions: 1
,
Comments: 3

__
TR06-063
| 1st May 2006
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Approximation Algorithm for the Max k-CSP Problem

__
TR06-064
| 1st May 2006
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Note on MAX 2SAT

__
TR06-065
| 24th May 2006
__

Jan Arpe, Rüdiger Reischuk#### When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---

__
TR06-066
| 5th May 2006
__

Vitaly Feldman#### On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions

Revisions: 1

__
TR06-067
| 12th April 2006
__

Heiner Ackermann, Heiko Röglin, Berthold Vöcking#### On the Impact of Combinatorial Structure on Congestion Games

__
TR06-068
| 6th April 2006
__

Patrick Briest, Piotr Krysta#### Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing

__
TR06-069
| 11th May 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner#### The Complexity of Unions of Disjoint Sets

__
TR06-070
| 23rd May 2006
__

Ludwig Staiger#### The Kolmogorov complexity of infinite words

__
TR06-071
| 25th April 2006
__

John Hitchcock, A. Pavan#### Hardness Hypotheses, Derandomization, and Circuit Complexity

__
TR06-072
| 25th February 2006
__

Henning Fernau#### Parameterized Algorithms for Hitting Set: the Weighted Case

__
TR06-073
| 8th June 2006
__

Andrej Bogdanov, Luca Trevisan#### Average-Case Complexity

Revisions: 1

__
TR06-074
| 24th April 2006
__

Shahar Dobzinski, Noam Nisan#### Approximations by Computationally-Efficient VCG-Based Mechanisms

__
TR06-075
| 19th June 2006
__

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan#### Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

__
TR06-076
| 4th May 2006
__

Noam Nisan#### A Note on the computational hardness of evolutionary stable strategies

__
TR06-077
| 12th June 2006
__

Maria Lopez-Valdes#### Lempel-Ziv Dimension for Lempel-Ziv Compression

__
TR06-078
| 12th June 2006
__

Tobias Riege, Jörg Rothe#### Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem

Revisions: 1

__
TR06-079
| 12th June 2006
__

Kristoffer Arnsfelt Hansen#### Lower Bounds for Circuits with Few Modular Gates using Exponential Sums

__
TR06-080
| 16th June 2006
__

David Doty#### Dimension Extractors

__
TR06-081
| 19th May 2006
__

Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis#### Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games

__
TR06-082
| 18th June 2006
__

Prabhu Manyem#### Polynomial-Time Maximisation Classes: Syntactic Hierarchy

__
TR06-083
| 16th May 2006
__

Nils Hebbinghaus, Benjamin Doerr, Frank Neumann#### Speeding up Evolutionary Algorithms by Restricted Mutation Operators

__
TR06-084
| 19th June 2006
__

Frank Neumann, Carsten Witt#### Runtime Analysis of a Simple Ant Colony Optimization Algorithm

__
TR06-085
| 15th May 2006
__

Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry#### Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment

Revisions: 1

__
TR06-086
| 25th July 2006
__

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf#### Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

__
TR06-087
| 25th July 2006
__

Iordanis Kerenidis, Ran Raz#### The one-way communication complexity of the Boolean Hidden Matching Problem

__
TR06-088
| 9th July 2006
__

Per Austrin#### Balanced Max 2-Sat might not be the hardest

__
TR06-089
| 16th July 2006
__

Sofya Raskhodnikova, Adam Smith#### A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

__
TR06-090
| 22nd June 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang#### Non-Mitotic Sets

__
TR06-091
| 29th May 2006
__

Felix Brandt, Felix Fischer, Markus Holzer#### Symmetries and the Complexity of Pure Nash Equilibrium

__
TR06-092
| 5th July 2006
__

Matthias Englert, Heiko Röglin, Berthold Vöcking#### Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

__
TR06-093
| 27th July 2006
__

Takeshi Koshiba, Yoshiharu Seri#### Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme

__
TR06-094
| 29th July 2006
__

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou#### The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Revisions: 1

__
TR06-095
| 25th July 2006
__

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti#### Concurrent Non-Malleable Witness Indistinguishability and its Applications

Revisions: 1

__
TR06-096
| 10th August 2006
__

Iftach Haitner, Omer Reingold#### A New Interactive Hashing Theorem

__
TR06-097
| 9th August 2006
__

Emanuele Viola#### New correlation bounds for GF(2) polynomials using Gowers uniformity

__
TR06-098
| 17th August 2006
__

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani#### A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

__
TR06-099
| 17th August 2006
__

Oded Goldreich#### On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits

Revisions: 1

__
TR06-100
| 17th July 2006
__

Meena Mahajan, Jayalal Sarma#### On the Complexity of Rank and Rigidity

__
TR06-101
| 22nd August 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Approximation Complexity of Nondense Instances of MAX-CUT

__
TR06-102
| 15th August 2006
__

Luis Rademacher, Santosh Vempala#### Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

__
TR06-103
| 5th July 2006
__

Oded Lachish, Ilan Newman, Asaf Shapira#### Space Complexity vs. Query Complexity

__
TR06-104
| 25th August 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### On the Sample Complexity of MAX-CUT

__
TR06-105
| 23rd August 2006
__

Avi Wigderson, David Xiao#### Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

__
TR06-106
| 18th August 2006
__

Scott Aaronson#### The Learnability of Quantum States

__
TR06-107
| 26th August 2006
__

Arkadev Chattopadhyay#### An improved bound on correlation between polynomials over Z_m and MOD_q

Revisions: 1

__
TR06-108
| 24th August 2006
__

Dan Gutfreund, Amnon Ta-Shma#### New connections between derandomization, worst-case complexity and average-case complexity

__
TR06-109
| 29th August 2006
__

Julia Chuzhoy, Sanjeev Khanna#### Hardness of Directed Routing with Congestion

__
TR06-110
| 15th August 2006
__

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai#### Improved Algorithms for Optimal Embeddings

__
TR06-111
| 18th July 2006
__

Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas#### Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Revisions: 2

__
TR06-112
| 22nd August 2006
__

Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang#### Strip Packing vs. Bin Packing

__
TR06-113
| 25th August 2006
__

Peter Buergisser#### On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity

__
TR06-114
| 22nd August 2006
__

Carl Bosley, Yevgeniy Dodis#### Does Privacy Require True Randomness?

__
TR06-115
| 26th July 2006
__

Artur Czumaj, Artur Czumaj, Andrzej Lingas#### Finding a Heaviest Triangle is not Harder than Matrix Multiplication

__
TR06-116
| 19th July 2006
__

Amin Coja-Oghlan#### Graph partitioning via adaptive spectral techniques

__
TR06-117
| 31st August 2006
__

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien#### Languages with Bounded Multiparty Communication Complexity

__
TR06-118
| 2nd September 2006
__

Irit Dinur, Madhu Sudan, Avi Wigderson#### Robust Local Testability of Tensor Products of LDPC Codes

__
TR06-119
| 13th September 2006
__

Noga Alon, Oded Schwartz, Asaf Shapira#### An Elementary Construction of Constant-Degree Expanders

__
TR06-120
| 12th September 2006
__

Leslie G. Valiant#### Evolvability

__
TR06-121
| 14th September 2006
__

Charanjit Jutla#### A Simple Biased Distribution for Dinur's Construction

__
TR06-122
| 20th September 2006
__

Noam Livne#### All Natural NPC Problems Have Average-Case Complete Versions

Revisions: 1

__
TR06-123
| 15th September 2006
__

Venkatesan Guruswami, Venkatesan Guruswami#### Iterative Decoding of Low-Density Parity Check Codes (A Survey)

__
TR06-124
| 25th September 2006
__

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Approximation of Global MAX-CSP Problems

__
TR06-125
| 20th September 2006
__

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto#### Low-Depth Witnesses are Easy to Find

__
TR06-126
| 2nd October 2006
__

Piotr Indyk#### Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

__
TR06-127
| 7th October 2006
__

Sergey Yekhanin#### New Locally Decodable Codes and Private Information Retrieval Schemes

__
TR06-128
| 5th October 2006
__

Shankar Kalyanaraman, Chris Umans#### On obtaining pseudorandomness from error-correcting codes.

__
TR06-129
| 6th October 2006
__

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf#### The polynomially bounded perfect matching problem is in NC^2

__
TR06-130
| 27th September 2006
__

Tanmoy Chakraborty, Samir Datta#### One-input-face MPCVP is Hard for L, but in LogDCFL

__
TR06-131
| 6th October 2006
__

Konstantin Pervyshev#### On Heuristic Time Hierarchies

__
TR06-132
| 17th October 2006
__

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani#### Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

Revisions: 1

__
TR06-133
| 14th October 2006
__

Alex Hertel, Alasdair Urquhart#### The Resolution Width Problem is EXPTIME-Complete

__
TR06-134
| 18th October 2006
__

Venkatesan Guruswami, Chris Umans, Salil Vadhan#### Extractors and condensers from univariate polynomials

Revisions: 1

__
TR06-135
| 22nd October 2006
__

Jin-Yi Cai, Pinyan Lu#### On Symmetric Signatures in Holographic Algorithms

__
TR06-136
| 22nd October 2006
__

Mihir Bellare, Oded Goldreich#### On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge

__
TR06-137
| 13th November 2006
__

Prashant Joshi, Eduardo D. Sontag#### Computational aspects of feedback in neural circuits

__
TR06-138
| 13th November 2006
__

Kei Uchizawa, Rodney Douglas#### Energy Complexity and Entropy of Threshold Circuits

__
TR06-139
| 14th November 2006
__

Shien Jin Ong, Salil Vadhan#### Zero Knowledge and Soundness are Symmetric

Revisions: 1

__
TR06-140
| 8th November 2006
__

Paul Beame, Russell Impagliazzo, Nathan Segerlind#### Formula Caching in DPLL

__
TR06-141
| 22nd November 2006
__

Venkatesan Guruswami, Kunal Talwar#### Hardness of Low Congestion Routing in Directed Graphs

__
TR06-142
| 26th October 2006
__

Olaf Beyersdorff#### On the Deduction Theorem and Complete Disjoint NP-Pairs

__
TR06-143
| 15th November 2006
__

Frank Neumann, Carsten Witt#### Ant Colony Optimization and the Minimum Spanning Tree Problem

__
TR06-144
| 21st November 2006
__

Claire Kenyon-Mathieu, Warren Schudy#### How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments

__
TR06-145
| 1st December 2006
__

Jin-Yi Cai, Pinyan Lu#### Holographic Algorithms: From Art to Science

__
TR06-146
| 30th September 2006
__

Christoph Buchheim, Peter J Cameron, Taoyang Wu#### On the Subgroup Distance Problem

__
TR06-147
| 27th November 2006
__

Chris Peikert, Alon Rosen#### Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Revisions: 1

__
TR06-148
| 4th December 2006
__

Chris Peikert#### Limits on the Hardness of Lattice Problems in $\ell_p$ Norms

Revisions: 1

__
TR06-149
| 7th December 2006
__

Lance Fortnow, Rakesh Vohra#### The Complexity of Forecast Testing

__
TR06-150
| 4th December 2006
__

Patrick Briest#### Towards Hardness of Envy-Free Pricing

__
TR06-151
| 10th December 2006
__

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan#### The communication complexity of correlation

__
TR06-152
| 6th December 2006
__

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis#### Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

__
TR06-153
| 19th October 2006
__

Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer#### The Complexity of Generalized Satisfiability for Linear Temporal Logic

Revisions: 1

__
TR06-154
| 13th December 2006
__

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam#### Uniform Hardness Amplification in NP via Monotone Codes

__
TR06-155
| 15th December 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP

Revisions: 1

__
TR06-156
| 7th December 2006
__

Tomas Feder, Rajeev Motwani#### Finding large cycles in Hamiltonian graphs

__
TR06-157
| 14th December 2006
__

Lance Fortnow, Rahul Santhanam#### Fixed-Polynomial Size Circuit Bounds

__
TR06-158
| 8th December 2006
__

Gyula Gyôr#### Representing Boolean OR function by quadratic polynomials modulo 6

__
TR06-159
| 3rd October 2006
__

Predrag Tosic#### Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata

__
TR06-160
| 17th December 2006
__

Tomas Feder, Phokion G. Kolaitis#### Closures and dichotomies for quantified constraints

Ran Raz, Iddo Tzameret

We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>

Eyal Kaplan, Moni Naor, Omer Reingold

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... more >>>

Joshua Buresh-Oppenheim, Rahul Santhanam

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

Jesper Torp Kristensen, Peter Bro Miltersen

We present an efficient reduction mapping undirected graphs

G with n = 2^k vertices for integers k

to tables of partially specified Boolean functions

g: {0,1}^(4k+1) -> {0,1,*} so that for any integer m,

G has a vertex colouring using m colours if and only if g ...
more >>>

Edith Elkind, Leslie Ann Goldberg, Paul Goldberg

Graphical games have been proposed as a game-theoretic model of large-scale

distributed networks of non-cooperative agents. When the number of players is

large, and the underlying graph has low degree, they provide a concise way to

represent the players' payoffs. It has recently been shown that the problem of

finding ...
more >>>

Alexander Shen

Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity.

more >>>MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

In the buy-at-bulk $k$-Steiner tree (or rent-or-buy

$k$-Steiner tree) problem we are given a graph $G(V,E)$ with a set

of terminals $T\subseteq V$ including a particular vertex $s$ called

the root, and an integer $k\leq |T|$. There are two cost functions

on the edges of $G$, a buy cost $b:E\longrightarrow ...
more >>>

MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

We consider the non-uniform multicommodity buy-at-bulk network

design problem. In this problem we are given a graph $G(V,E)$ with

two cost functions on the edges, a buy cost $b:E\longrightarrow \RR^+$ and a rent cost

$r:E\longrightarrow\RR^+$, and a set of source-sink pairs $s_i,t_i\in V$ ($1\leq i\leq \alpha$)

with each pair $i$ ...
more >>>

Nutan Limaye, Meena Mahajan, Jayalal Sarma

We re-examine the complexity of evaluating monotone planar circuits

MPCVP, with special attention to circuits with cylindrical

embeddings. MPCVP is known to be in NC^3, and for the special

case of upward stratified circuits, it is known to be in

LogDCFL. We characterize cylindricality, which ...
more >>>

Reka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag

In this paper we consider the p-ary transitive reduction (TR<sub>p</sub>) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. ... more >>>

Yijia Chen, Martin Grohe

We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.

more >>>Bruno Codenotti, Mauro Leoncini, Giovanni Resta

It is known that finding a Nash equilibrium for win-lose bimatrix

games, i.e., two-player games where the players' payoffs are zero

and one, is complete for the class PPAD.

We describe a linear time algorithm which computes a Nash

equilibrium for win-lose bimatrix games where the number of winning

positions ...
more >>>

Luca Trevisan

In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science,

probabilistic algorithms are sometimes simpler and more efficient

than the best known ...
more >>>

Argimiro Arratia, Carlos E. Ortiz

We formulate a formal syntax of approximate formulas for the logic with counting

quantifiers, $\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the

following facts:

$(i)$ In the presence of a built--in (linear) order, $\mathcal{SOLP}$ can

describe {\bf NP}--complete problems and fragments of it capture classes like

{\bf P} ...
more >>>

Tomas Feder, Carlos Subi

Barnette's conjecture is the statement that every 3-connected cubic

planar bipartite graph is Hamiltonian. Goodey showed that the conjecture

holds when all faces of the graph have either 4 or 6 sides. We

generalize Goodey's result by showing that when the faces of such a

graph are 3-colored, with adjacent ...
more >>>

Tomas Feder, Carlos Subi

The $H$-matching problem asks to partition the vertices of an input graph $G$

into sets of size $k=|V(H)|$, each of which induces a subgraph of $G$

isomorphic to $H$. The $H$-matching problem has been classified as polynomial

or NP-complete depending on whether $k\leq 2$ or not. We consider a variant

more >>>

Toshiya Itoh

A family ${\cal F}$ of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer $n>0$, let $S_{n}$ be the family of al permutations on $[1,n]=\{1,2,\ldots, n\}$.

For any integer $k \in [1,n]$ and any real $\varepsilon >0$, we ...
more >>>

Jin-Yi Cai, Vinay Choudhary

Valiant has proposed a new theory of algorithmic

computation based on perfect matchings and the Pfaffian.

We study the properties of {\it matchgates}---the basic

building blocks in this new theory. We give a set of

algebraic identities

which completely characterize these objects in terms of

the ...
more >>>

Janka Chlebíková, Miroslav Chlebík

Recently Bansal and Sviridenko (Proc. of the 15th SODA'04, 189-196)

proved that for

2-dimensional Orthogonal Rectangle

Bin Packing without rotations allowed there is no asymptotic PTAS, unless P=NP. We show that similar

approximation hardness results hold for several rectangle packing and covering problems even if rotations by ninety

more >>>

Akinori Kawachi, Tomoyuki Yamakami

We present three new quantum hardcore functions for any quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.

Our technical tool is ...
more >>>

Tomas Feder

Attempts at classifying computational problems as polynomial time

solvable, NP-complete, or belonging to a higher level in the polynomial

hierarchy, face the difficulty of undecidability. These classes, including

NP, admit a logic formulation. By suitably restricting the formulation, one

finds the logic class MMSNP, or monotone monadic strict NP without

more >>>

Danny Harnik, Moni Naor

We initiate the study of the compressibility of NP problems. We

consider NP problems that have long instances but relatively

short witnesses. The question is, can one efficiently compress an

instance and store a shorter representation that maintains the

information of whether the original input is in the language or

more >>>

Xi Chen, Xiaotie Deng, Shang-Hua Teng

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times ... more >>>

Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin

The class TFNP, defined by Megiddo and Papadimitriou, consists of

multivalued functions with values that are polynomially verifiable

and guaranteed to exist. Do we have evidence that such functions are

hard, for example, if TFNP is computable in polynomial-time does

this imply the polynomial-time hierarchy collapses?

We give a relativized ... more >>>

Leonid Gurvits

Let $p(x_1,...,x_n) = p(X) , X \in R^{n}$ be a homogeneous polynomial of degree $n$ in $n$ real variables ,

$e = (1,1,..,1) \in R^n$ be a vector of all ones . Such polynomial $p$ is

called $e$-hyperbolic if for all real vectors $X \in R^{n}$ the univariate polynomial

equation ...
more >>>

Ronen Gradwohl, Salil Vadhan, David Zuckerman

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

Hermann Gruber, Markus Holzer

We investigate the following lower bound methods for regular

languages: The fooling set technique, the extended fooling set

technique, and the biclique edge cover technique. It is shown that

the maximal attainable lower bound for each of the above mentioned

techniques can be algorithmically deduced from ...
more >>>

Jonathan Katz, Chiu-Yuen Koo

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>

Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani

We study the structure of EG[2], the class of Eisenberg-Gale markets

with two agents. We prove that all markets in this class are rational and they

admit strongly polynomial algorithms whenever

the polytope containing the set of feasible utilities of the two agents can be described

via a combinatorial LP. ...
more >>>

Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar

In our problem we are given a set of customers, their positions on the

plane and their demands. Geometrically, directional antenna with

parameters $\alpha,\rho,R$ is a set

of points with radial coordinates $(\theta,r)$ such that

$\alpha \le \theta \le \alpha+\rho$ and $r \le R$. Given a set of

possible directional ...
more >>>

Li-Sha Huang, Shang-Hua Teng

We show that the problem of finding an \epsilon-approximate Nash equilibrium af an n*n two-person game can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange ... more >>>

Vitaly Feldman

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

Amit Agarwal, Elad Hazan

A natural algorithmic scheme in online game playing is called `follow-the-leader', first proposed by Hannan in the 1950's. Simply stated, this method advocates the use of past history to make future predictions, by using the optimal strategy so far as the strategy for the next game iteration. Randomized variations on ... more >>>

Moni Naor, Guy Rothblum

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and ... more >>>

Till Tantau

The reachability problem for graphs cannot be described, in the

sense of descriptive complexity theory, using a single first-order

formula. This is true both for directed and undirected graphs, both

in the finite and infinite. However, if we restrict ourselves to

graphs in which a certain graph parameter is fixed ...
more >>>

Tobias Riege, Jörg Rothe

This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>

Xi Chen, Xiaotie Deng

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive ... more >>>

David Doty, Jack H. Lutz, Satyadev Nandakumar, Satyadev Nandakumar

We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+alpha, and q*alpha all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives ... more >>>

John Hitchcock, A. Pavan

Under the assumption that NP does not have p-measure 0, we

investigate reductions to NP-complete sets and prove the following:

- Adaptive reductions are more powerful than nonadaptive

reductions: there is a problem that is Turing-complete for NP but

not truth-table-complete.

- Strong nondeterministic reductions are more powerful ... more >>>

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

We study the problem of assigning different communication channels to

acces points in a wireless Local Area Network. Each access point will

be assigned a specific radio frequency channel. Since channels with

similar frequencies interfere, it is desirable to assign far apart

channels (frequencies) to nearby access points. Our goal ...
more >>>

Tomas Feder, Rajeev Motwani, An Zhu

We consider the problem of finding a $k$-vertex ($k$-edge)

connected spanning subgraph $K$ of a given $n$-vertex graph $G$

while minimizing the maximum degree $d$ in $K$. We give a

polynomial time algorithm for fixed $k$ that achieves an $O(\log

n)$-approximation. The only known previous polynomial algorithms

achieved degree $d+1$ ...
more >>>

Amit Deshpande, Santosh Vempala

We prove that any real matrix $A$ contains a subset of at most

$4k/\eps + 2k \log(k+1)$ rows whose span ``contains" a matrix of

rank at most $k$ with error only $(1+\eps)$ times the error of the

best rank-$k$ approximation of $A$. This leads to an algorithm to

find such ...
more >>>

Eran Ofek, Uriel Feige

Let $\phi$ be a 3CNF formula with n variables and m clauses. A

simple nonconstructive argument shows that when m is

sufficiently large compared to n, most 3CNF formulas are not

satisfiable. It is an open question whether there is an efficient

refutation algorithm that for most such formulas proves ...
more >>>

Andreas Björklund, Thore Husfeldt

We present a deterministic algorithm producing the number of

$k$-colourings of a graph on $n$ vertices in time

$2^nn^{O(1)}$.

We also show that the chromatic number can be found by a

polynomial space algorithm running in time $O(2.2461^n)$.

Finally, we present a family of ...
more >>>

Jan Arpe, Bodo Manthey

Given a set of monomials, the Minimum AND-Circuit problem asks for a

circuit that computes these monomials using AND-gates of fan-in two and

being of minimum size. We prove that the problem is not polynomial time

approximable within a factor of less than 1.0051 unless P = NP, even if

more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal, this class contains probabilistic encryption of Goldwasser-Micali as well as Ajtai-Dwork and NTRU cryptosystems. The latter two are known to make errors with ... more >>>

Maria Lopez-Valdes

We define a new discrete version of scaled dimension and we find

connections between the scaled dimension of a string and its Kolmogorov

complexity and predictability. We give a new characterization

of constructive scaled dimension by Kolmogorov complexity, and prove

a new result about scaled dimension and prediction.

Jin-Yi Cai, Vinay Choudhary

We establish a 1-1 correspondence between Valiant's

character theory of matchgate/matchcircuit

and his signature theory of planar-matchgate/matchgrid,

thus unifying the two theories in expressibility.

Previously we had established a complete characterization

of general matchgates, in terms of a set of

useful Grassmann-Pl{\"u}cker identities.

With this correspondence,

we give a corresponding ...
more >>>

Guy Wolfovitz

We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin $k$ which computes the Boolean function $EXACT_{n/(k+1)}^{n}$, has at least $(1+1/k)^{n+\O(\log n)}$ gates. We show that this lower bound is tight, by ... more >>>

Alexander Razborov, Sergey Yekhanin

A two server private information retrieval (PIR) scheme

allows a user U to retrieve the i-th bit of an

n-bit string x replicated between two servers while each

server individually learns no information about i. The main

parameter of interest in a PIR scheme is its communication

complexity, namely the ...
more >>>

Alan Nash, Russell Impagliazzo, Jeff Remmel

Diagonalization is a powerful technique in recursion theory and in

computational complexity \cite{For00}. The limits of this technique are

not clear. On the one hand, many people argue that conflicting

relativizations mean a complexity question cannot be resolved using only

diagonalization. On the other hand, it is not clear that ...
more >>>

Wenbin Chen, Jiangtao Meng

We show that the Closest Vector

Problem with Preprocessing over infty Norm

is NP-hard to approximate to within a factor of $(\log

n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their

reductions are based on norm embeddings. However, ...
more >>>

Eldar Fischer, Orly Yahalom

A coloring of a graph is {\it convex} if it

induces a partition of the vertices into connected subgraphs.

Besides being an interesting property from a theoretical point of

view, tests for convexity have applications in various areas

involving large graphs. Our results concern the important subcase

of testing for ...
more >>>

Alex Samorodnitsky

We define tests of boolean functions which

distinguish between linear (or quadratic) polynomials, and functions

which are very far, in an appropriate sense, from these

polynomials. The tests have optimal or nearly optimal trade-offs

between soundness and the number of queries.

In particular, we show that functions with small ... more >>>

Scott Aaronson, Greg Kuperberg

This paper studies whether quantum proofs are more powerful than

classical proofs, or in complexity terms, whether QMA=QCMA. We prove

two results about this question. First, we give a "quantum oracle

separation" between QMA and QCMA. More concretely, we show that any

quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ...
more >>>

Salil Vadhan

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist.

We establish several new characterizations of ZK, and use these characterizations to ... more >>>

Adam Klivans, Alexander A. Sherstov

We give the first representation-independent hardness results for

PAC learning intersections of halfspaces, a central concept class

in computational learning theory. Our hardness results are derived

from two public-key cryptosystems due to Regev, which are based on the

worst-case hardness of well-studied lattice problems. Specifically, we

prove that a polynomial-time ...
more >>>

Alexander Healy

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC^1. For example, we obtain the following results:

... more >>>Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

Ran Raz, Amir Shpilka, Amir Yehudayoff

We construct an explicit polynomial $f(x_1,...,x_n)$, with

coefficients in ${0,1}$, such that the size of any syntactically

multilinear arithmetic circuit computing $f$ is at least

$\Omega( n^{4/3} / log^2(n) )$. The lower bound holds over any field.

Venkatesan Guruswami, Prasad Raghavendra

Learning an unknown halfspace (also called a perceptron) from

labeled examples is one of the classic problems in machine learning.

In the noise-free case, when a halfspace consistent with all the

training examples exists, the problem can be solved in polynomial

time using linear programming. ...
more >>>

Subhas Kumar Ghosh

In this work we show that Unique k-SAT is as Hard as k-SAT for every $k \in {\mathds N}$. This settles a conjecture by Calabro, Impagliazzo, Kabanets and Paturi \cite{CIKP03}. To provide an affirmative answer to this conjecture, we develop a randomness optimal construction of Isolation Lemma(see Valiant and Vazirani ... more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

We present a c.k/2^k approximation algorithm for the Max k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of Omega(k/(2^k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up ... more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

In this note we present an approximation algorithm for MAX 2SAT that given a (1 - epsilon) satisfiable instance finds an assignment of variables satisfying a 1 - O(sqrt{epsilon}) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture.

The best previously known result, due ... more >>>

Jan Arpe, Rüdiger Reischuk

Detecting the relevant attributes of an unknown target concept

is an important and well studied problem in algorithmic learning.

Simple greedy strategies have been proposed that seem to perform reasonably

well in practice if a sufficiently large random subset of examples of the target

concept is provided.

Introducing a ... more >>>

Vitaly Feldman

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over $\{0,1\}^n$. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem ... more >>>

Heiner Ackermann, Heiko Röglin, Berthold Vöcking

We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show, if the strategy space ... more >>>

Patrick Briest, Piotr Krysta

We investigate non-parametric unit-demand pricing problems, in which the goal is to find revenue maximizing prices for a set of products based on consumer profiles obtained, e.g., from an e-Commerce website. A consumer profile consists of a number of non-zero budgets and a ranking of all the products the consumer ... more >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

This paper is motivated by the open question

whether the union of two disjoint NP-complete sets always is

NP-complete. We discover that such unions retain

much of the complexity of their single components. More precisely,

they are complete with respect to more general reducibilities.

Ludwig Staiger

We present a brief survey of results on relations between the Kolmogorov

complexity of infinite strings and several measures of information content

(dimensions) known from dimension theory, information theory or fractal

geometry.

Special emphasis is laid on bounds on the complexity of strings in

more >>>

John Hitchcock, A. Pavan

We consider hypotheses about nondeterministic computation that

have been studied in different contexts and shown to have interesting

consequences:

1. The measure hypothesis: NP does not have p-measure 0.

2. The pseudo-NP hypothesis: there is an NP language that can be

distinguished from any DTIME(2^n^epsilon) language by an ...
more >>>

Henning Fernau

We are going to analyze simple search tree algorithms

for Weighted d-Hitting Set. Although the algorithms are simple, their analysis is technically rather involved. However, this approach allows us to even improve on elsewhere published algorithm running time estimates for the more restricted case of (unweighted) d-Hitting Set.

Andrej Bogdanov, Luca Trevisan

We survey the theory of average-case complexity, with a

focus on problems in NP.

Shahar Dobzinski, Noam Nisan

We consider computationally-efficient incentive-compatible

mechanisms that use the VCG payment scheme, and study how well they

can approximate the social welfare in auction settings. We obtain a

$2$-approximation for multi-unit auctions, and show that this is

best possible, even though from a purely computational perspective

an FPTAS exists. For combinatorial ...
more >>>

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan

We show that every language in NP has a *statistical* zero-knowledge

argument system under the (minimal) complexity assumption that

one-way functions exist. In such protocols, even a computationally

unbounded verifier cannot learn anything other than the fact that the

assertion being proven is true, whereas a polynomial-time prover

cannot convince ...
more >>>

Noam Nisan

We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k. Formally this shows that existence of evolutionary stable strategies is hard ... more >>>

Maria Lopez-Valdes

This paper describes the Lempel-Ziv dimension (Hausdorff like

dimension inspired in the LZ78 parsing), its fundamental properties

and relation with Hausdorff dimension.

It is shown that in the case of individual infinite sequences, the

Lempel-Ziv dimension matches with the asymptotical Lempel-Ziv

compression ratio.

This fact is used to describe results ... more >>>

Tobias Riege, Jörg Rothe

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the ... more >>>

Kristoffer Arnsfelt Hansen

We prove that any AC0 circuit augmented with {epsilon log^2 n}

MOD_m gates and with a MAJORITY gate at the output, require size

n^{Omega(log n)} to compute MOD_l, when l has a prime

factor not dividing m and epsilon is sufficiently small. We

also obtain ...
more >>>

David Doty

A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily ... more >>>

Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis

We focus on the problem of computing an $\epsilon$-Nash equilibrium of a bimatrix game, when $\epsilon$ is an absolute constant.

We present a simple algorithm for computing a $\frac{3}{4}$-Nash equilibrium for any bimatrix game in strongly polynomial time and

we next show how to extend this algorithm so as to ...
more >>>

Prabhu Manyem

In Descriptive Complexity, there is a vast amount of literature on

decision problems, and their classes such as \textbf{P, NP, L and NL}. ~

However, research on the descriptive complexity of optimisation problems

has been limited. In a previous paper [Man], we characterised

the optimisation versions of \textbf{P} via expressions ...
more >>>

Nils Hebbinghaus, Benjamin Doerr, Frank Neumann

We investigate the effect of restricting the mutation operator in

evolutionary algorithms with respect to the runtime behavior.

Considering the Eulerian cycle problem we present runtime bounds on

evolutionary algorithms with a restricted operator that are much

smaller than the best upper bounds for the ...
more >>>

Frank Neumann, Carsten Witt

Ant Colony Optimization (ACO) has become quite popular in recent

years. In contrast to many successful applications, the theoretical

foundation of this randomized search heuristic is rather weak.

Building up such a theory is demanded to understand how these

heuristics work as well as to ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry

It is well known that unconditionally secure bit commitment is impossible

even in the quantum world. In this paper a weak variant of quantum bit

commitment, introduced independently by Aharonov et al. and Hardy and Kent

is investigated. In this variant, the parties require some nonzero probability

more >>>

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>

Iordanis Kerenidis, Ran Raz

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for ... more >>>

Per Austrin

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.

This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. ... more >>>

Sofya Raskhodnikova, Adam Smith

We show that in the bounded degree model for graph property testing,

adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ...
more >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>

<ul>

<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>

<li>1-tt-reducibility and m-reducibility differ on NP.</li>

<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ...
more >>>

Felix Brandt, Felix Fischer, Markus Holzer

Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... more >>>

Matthias Englert, Heiko Röglin, Berthold Vöcking

2-Opt is probably the most basic and widely used local search

heuristic for the TSP. This heuristic achieves amazingly good

results on "real world" Euclidean instances both with respect to

running time and approximation ratio. There are numerous

experimental studies on the performance of 2-Opt. However, the

theoretical knowledge about ...
more >>>

Takeshi Koshiba, Yoshiharu Seri

We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider ... more >>>

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

One of the central questions in Cryptography today is proving security of the protocols ``on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called ``man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, ... more >>>

Iftach Haitner, Omer Reingold

Interactive hashing, introduced by Naor et al. [NOVY98], plays

an important role in many cryptographic protocols. In particular, it

is a major component in all known constructions of

statistically-hiding commitment schemes and of zero-knowledge

arguments based on general one-way permutations and on one-way

functions. Interactive hashing with respect to a ...
more >>>

Emanuele Viola

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

We study semidefinite programming relaxations of Vertex Cover arising from

repeated applications of the LS+ ``lift-and-project'' method of Lovasz and

Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality

gap remains arbitrarily close to 2. Charikar proves an integrality ...
more >>>

Oded Goldreich

This paper concerns the possibility of developing a coherent

theory of security when feasibility is associated

with expected probabilistic polynomial-time (expected PPT).

The source of difficulty is that

the known definitions of expected PPT strategies

(i.e., expected PPT interactive machines)

do not support natural results of the ...
more >>>

Meena Mahajan, Jayalal Sarma

Given a matrix $M$ over a ring \Ringk, a target rank $r$ and a bound

$k$, we want to decide whether the rank of $M$ can be brought down to

below $r$ by changing at most $k$ entries of $M$. This is a decision

version of the well-studied notion of ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove existence of approximation schemes for instances of MAX-CUT with $\Omega(\frac{n^2}{\Delta})$ edges which work in $2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$ time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with $\Omega(\frac{n^2}{\operatorname{polylog} n})$ edges. The result depends on new sampling method for smoothed linear programs that ... more >>>

Luis Rademacher, Santosh Vempala

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume ... more >>>

Oded Lachish, Ilan Newman, Asaf Shapira

Combinatorial property testing deals with the following relaxation

of decision problems: Given a fixed property and an input $x$, one

wants to decide whether $x$ satisfies the property or is ``far''

from satisfying it. The main focus of property testing is in

identifying large families of properties that can be ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

more >>>Avi Wigderson, David Xiao

Ahlswede and Winter introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>

Scott Aaronson

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

Arkadev Chattopadhyay

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>>

Dan Gutfreund, Amnon Ta-Shma

We show that a mild derandomization assumption together with the

worst-case hardness of NP implies the average-case hardness of a

language in non-deterministic quasi-polynomial time. Previously such

connections were only known for high classes such as EXP and

PSPACE.

There has been a long line of research trying to explain ... more >>>

Julia Chuzhoy, Sanjeev Khanna

Given a graph G and a collection of source-sink pairs in G, what is the least integer c such that each source can be connected by a path to its sink, with at most c paths going through an edge? This is known as the congestion minimization problem, and the ... more >>>

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

In the last decade, the notion of metric embeddings with

small distortion received wide attention in the literature, with

applications in combinatorial optimization, discrete mathematics, functional

analysis and bio-informatics. The notion of embedding is, given two metric

spaces on the same number of points, to find a bijection that minimizes

more >>>

Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

We present two new methods for finding a lowest common ancestor (LCA)

for each pair of vertices of a directed acyclic graph (dag) on

n vertices and m edges.

The first method is a natural approach that solves the all-pairs LCA

problem for the input dag in time O(nm).

The ... more >>>

Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang

In this paper

we establish a general algorithmic framework between bin packing

and strip packing, with which we achieve the same asymptotic

bounds by applying bin packing algorithms to strip packing. More

precisely we obtain the following results: (1) Any offline bin

packing algorithm can be applied to strip packing ...
more >>>

Peter Buergisser

Let $\tau(n)$ denote the minimum number of arithmetic operations sufficient to build the integer $n$ from the constant~$1$. We prove that if there are arithmetic circuits for computing the permanent of $n$ by $n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $\log n$. Under the ... more >>>

Carl Bosley, Yevgeniy Dodis

Most cryptographic primitives require randomness (for example, to generate their secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be true for many authentication applications, when entropy alone is typically sufficient. In contrast, ... more >>>

Artur Czumaj, Artur Czumaj, Andrzej Lingas

We show that for any $\epsilon > 0$, a maximum-weight triangle in an

undirected graph with $n$ vertices and real weights assigned to

vertices can be found in time $\O(n^{\omega} + n^{2 + \epsilon})$,

where $\omega $ is the exponent of fastest matrix multiplication

algorithm. By the currently best bound ...
more >>>

Amin Coja-Oghlan

We study the use of spectral techniques for graph partitioning. Let G=(V,E) be a graph whose vertex set has a ``latent'' partition V_1,...,V_k. Moreover, consider a ``density matrix'' E=(E_vw)_{v,w in V} such that for v in V_i and w in V_j the entry E_{vw} is the fraction of all possible ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

Irit Dinur, Madhu Sudan, Avi Wigderson

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

Noga Alon, Oded Schwartz, Asaf Shapira

We describe a short and easy to analyze construction of

constant-degree expanders. The construction relies on the

replacement-product, which we analyze using an elementary

combinatorial argument. The construction applies the replacement

product (only twice!) to turn the Cayley expanders of \cite{AR},

whose degree is polylog n, into constant degree

expanders.

Leslie G. Valiant

Living cells function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as a result of a random search guided by selection and realized by genetic mutations. However, as some observers have noted, there has existed no theory that would ... more >>>

Charanjit Jutla

Noam Livne

In 1984 Levin put forward a suggestion for a theory of {\em average

case complexity}. In this theory a problem, called a {\em

distributional problem}, is defined as a pair consisting of a

decision problem and a probability distribution over the instances.

Introducing adequate notions of simple distributions and average

more >>>

Venkatesan Guruswami, Venkatesan Guruswami

Much progress has been made on decoding algorithms for

error-correcting codes in the last decade. In this article, we give an

introduction to some fundamental results on iterative, message-passing

algorithms for low-density parity check codes. For certain

important stochastic channels, this line of work has enabled getting

very close to ...
more >>>

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the

notion of non-random information by computational depth, the

difference between the polynomial-time-bounded Kolmogorov

complexity and traditional Kolmogorov complexity We show how to

find satisfying assignments for formulas that have at least one

assignment of logarithmic depth. The converse holds under a

standard ...
more >>>

Piotr Indyk

We give an explicit construction of a constant-distortion embedding of an n-dimensional L_2 space into an n^{1+o(1)}-dimensional L_1 space.

more >>>Sergey Yekhanin

A q-query Locally Decodable Code (LDC) encodes an n-bit message

x as an N-bit codeword C(x), such that one can

probabilistically recover any bit x_i of the message

by querying only q bits of the codeword C(x), even after

some constant fraction of codeword bits has been corrupted.

We give ... more >>>

Shankar Kalyanaraman, Chris Umans

A number of recent results have constructed randomness extractors

and pseudorandom generators (PRGs) directly from certain

error-correcting codes. The underlying construction in these

results amounts to picking a random index into the codeword and

outputting $m$ consecutive symbols (the codeword is obtained from

the weak random source in the case ...
more >>>

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The perfect matching problem is known to

be in P, in randomized NC, and it is hard for NL.

Whether the perfect matching problem is in NC is one of

the most prominent open questions in complexity

theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem

more >>>

Tanmoy Chakraborty, Samir Datta

A monotone planar circuit (MPC) is a Boolean circuit that can be

embedded in a plane, and that has only AND and OR

gates. Yang showed that the one-input-face

monotone planar circuit value problem (MPCVP) is in NC^2, and

Limaye et. al. improved the bound to ...
more >>>

Konstantin Pervyshev

We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>>

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

We study linear programming relaxations of Vertex Cover and Max Cut

arising from repeated applications of the ``lift-and-project''

method of Lovasz and Schrijver starting from the standard linear

programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that

the integrality gap remains at least $2-\epsilon$ after

$\Omega_\epsilon(\log n)$ ...
more >>>

Alex Hertel, Alasdair Urquhart

The importance of {\em width} as a resource in resolution theorem proving

has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower

bounds on the size of resolution refutations can be proved in a uniform manner by

demonstrating lower bounds on the width ...
more >>>

Venkatesan Guruswami, Chris Umans, Salil Vadhan

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

Jin-Yi Cai, Pinyan Lu

The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P $\not =$ ... more >>>

Mihir Bellare, Oded Goldreich

This note points out a gap between two natural formulations of

the concept of a proof of knowledge, and shows that in all

natural cases (e.g., NP-statements) this gap can be closed.

The aforementioned formulations differ by whether they refer to

(all possible) probabilistic or deterministic prover strategies.

Unlike ...
more >>>

Prashant Joshi, Eduardo D. Sontag

It had previously been shown that generic cortical microcircuit

models can perform complex real-time computations on continuous

input streams, provided that these computations can be carried out

with a rapidly fading memory. We investigate in this article the

computational capability of such circuits in the ...
more >>>

Kei Uchizawa, Rodney Douglas

Circuits composed of threshold gates (McCulloch-Pitts neurons, or

perceptrons) are simplified models of neural circuits with the

advantage that they are theoretically more tractable than their

biological counterparts. However, when such threshold circuits are

designed to perform a specific computational task they usually

differ ...
more >>>

Shien Jin Ong, Salil Vadhan

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. ... more >>>

Paul Beame, Russell Impagliazzo, Nathan Segerlind

We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization, in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability. We formalize these methods by ... more >>>

Venkatesan Guruswami, Kunal Talwar

We prove a strong inapproximability result for routing on directed

graphs with low congestion. Given as input a directed graph on $N$

vertices and a set of source-destination pairs that can be connected

via edge-disjoint paths, we prove that it is hard, assuming NP

doesn't have $n^{O(\log\log n)}$ time randomized ...
more >>>

Olaf Beyersdorff

In this paper we ask the question whether the extended Frege proof

system EF satisfies a weak version of the deduction theorem. We

prove that if this is the case, then complete disjoint NP-pairs

exist. On the other hand, if EF is an optimal proof system, ...
more >>>

Frank Neumann, Carsten Witt

Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. ... more >>>

Claire Kenyon-Mathieu, Warren Schudy

Suppose you ran a chess tournament, everybody played everybody, and you wanted to use the results to rank everybody. Unless you were really lucky, the results would not be acyclic, so you could not just sort the players by who beat whom. A natural objective is to find a ranking ... more >>>

Jin-Yi Cai, Pinyan Lu

We develop the theory of holographic algorithms. We give

characterizations of algebraic varieties of realizable

symmetric generators and recognizers on the basis manifold,

and a polynomial time decision algorithm for the

simultaneous realizability problem.

Using the general machinery we are able to give

unexpected holographic algorithms for

some counting problems, ...
more >>>

Christoph Buchheim, Peter J Cameron, Taoyang Wu

We investigate the computational complexity of finding an element of

a permutation group~$H\subseteq S_n$ with a minimal distance to a

given~$\pi\in S_n$, for different metrics on~$S_n$. We assume

that~$H$ is given by a set of generators, such that the problem

cannot be solved in polynomial time ...
more >>>

Chris Peikert, Alon Rosen

We demonstrate an \emph{average-case} problem which is as hard as

finding $\gamma(n)$-approximate shortest vectors in certain

$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n)

= O(\sqrt{\log n})$. The previously best known factor for any class

of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>

Chris Peikert

We show that for any $p \geq 2$, lattice problems in the $\ell_p$

norm are subject to all the same limits on hardness as are known

for the $\ell_2$ norm. In particular, for lattices of dimension

$n$:

* Approximating the shortest and closest vector in ... more >>>

Lance Fortnow, Rakesh Vohra

Consider a weather forecaster predicting a probability of rain for

the next day. We consider tests that given a finite sequence of

forecast predictions and outcomes will either pass or fail the

forecaster. Sandroni (2003) shows that any test which passes a

forecaster who knows the distribution of nature, can ...
more >>>

Patrick Briest

We consider the envy-free pricing problem, in which we want to compute revenue maximizing prices for a set of products P assuming that each consumer from a set of consumer samples C will buy the product maximizing her personal utility, i.e., the difference between her respective budget and the product's ... more >>>

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

We examine the communication required for generating random variables

remotely. One party Alice will be given a distribution D, and she

has to send a message to Bob, who is then required to generate a

value with distribution exactly D. Alice and Bob are allowed

to share random bits generated ...
more >>>

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

more >>>Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

In a seminal paper from 1985, Sistla and Clarke showed

that satisfiability for Linear Temporal Logic (LTL) is either

NP-complete or PSPACE-complete, depending on the set of temporal

operators used

If, in contrast, the set of propositional operators is restricted, the

complexity may ...
more >>>

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

We consider the problem of amplifying uniform average-case hardness

of languages in $\NP$, where hardness is with respect to $\BPP$

algorithms. We introduce the notion of \emph{monotone}

error-correcting codes, and show that hardness amplification for

$\NP$ is essentially equivalent to constructing efficiently

\emph{locally} encodable and \emph{locally} list-decodable monotone

codes. The ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any $r \ge 2$ in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... more >>>

Tomas Feder, Rajeev Motwani

We show how to find in Hamiltonian graphs a cycle of length

$n^{\Omega(1/\log\log n)}$. This is a consequence of a more general

result in which we show that if $G$ has maximum degree $d$ and has a

cycle with $k$ vertices (or a 3-cyclable minor $H$ with $k$ vertices),

then ...
more >>>

Lance Fortnow, Rahul Santhanam

We explore whether various complexity classes can have linear or

more generally $n^k$-sized circuit families for some fixed $k$. We

show

1) The following are equivalent,

- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k

- P^NP|| is in SIZE(n^k) for some k

- ONP/1 is in ...
more >>>

Gyula Gyôr

We give an answer to the question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest n such that the OR function of n variable can be weakly represented by a quadratic polynomial modulo 6. More specially,we show that no 11-variable quadratic polynomial exists that is congruent to ... more >>>

Predrag Tosic

We study the computational complexity of counting the fixed point configurations (FPs), the predecessor configurations and the ancestor configurations in certain classes of graph or network automata viewed as discrete dynamical systems. Early results of this investigation are presented in two recent ECCC reports [39, 40]. In particular, it is ... more >>>

Tomas Feder, Phokion G. Kolaitis

Quantified constraint satisfaction is the generalization of

constraint satisfaction that allows for both universal and existential

quantifiers over constrained variables, instead

of just existential quantifiers.

We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes

a pattern of quantifier alternation ending in exists or the set of all possible

more >>>