All reports in year 2005:

__
TR05-001
| 1st January 2005
__

Mario Szegedy#### Near optimality of the priority sampling procedure

__
TR05-002
| 6th January 2005
__

Magnus Bordewich, Martin Dyer, Marek Karpinski#### Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

__
TR05-003
| 23rd December 2004
__

Scott Aaronson#### Quantum Computing, Postselection, and Probabilistic Polynomial-Time

__
TR05-004
| 3rd January 2005
__

Leslie G. Valiant#### Memorization and Association on a Realistic Neural Model

__
TR05-005
| 20th December 2004
__

Tomas Feder#### Constraint Satisfaction on Finite Groups with Near Subgroups

__
TR05-006
| 28th December 2004
__

Edward Hirsch, Sergey I. Nikolenko#### Simulating Cutting Plane proofs with restricted degree of falsity by Resolution

Comments: 1

__
TR05-007
| 15th December 2004
__

Vadim Lyubashevsky#### On Random High Density Subset Sums

__
TR05-008
| 11th December 2004
__

Neeraj Kayal#### Recognizing permutation functions in polynomial time.

__
TR05-009
| 14th December 2004
__

David P. Woodruff, Sergey Yekhanin#### A Geometric Approach to Information-Theoretic Private Information Retrieval

__
TR05-010
| 8th December 2004
__

Olivier Powell#### Almost Completeness in Small Complexity Classes

__
TR05-011
| 21st December 2004
__

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang#### Autoreducibility, Mitoticity, and Immunity

__
TR05-012
| 17th January 2005
__

Luca Trevisan, Salil Vadhan, David Zuckerman#### Compression of Samplable Sources

__
TR05-013
| 22nd December 2004
__

Bin Fu#### Theory and Application of Width Bounded Geometric Separator

__
TR05-014
| 30th January 2005
__

Oded Goldreich#### Short Locally Testable Codes and Proofs (Survey)

__
TR05-015
| 27th January 2005
__

Andrej Bogdanov, Luca Trevisan#### On Worst-Case to Average-Case Reductions for NP Problems

__
TR05-016
| 13th January 2005
__

Tomas Feder, Daniel Ford#### Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

__
TR05-017
| 28th January 2005
__

Phong Nguyen#### Two-Sorted Theories for L, SL, NL and P

__
TR05-018
| 6th February 2005
__

Oded Goldreich#### On Promise Problems (a survey in memory of Shimon Even [1935-2004])

__
TR05-019
| 9th February 2005
__

Venkatesan Guruswami, Atri Rudra#### Tolerant Locally Testable Codes

__
TR05-020
| 22nd November 2004
__

Sourav Chakraborty#### On the Sensitivity of Cyclically-Invariant Boolean Functions

__
TR05-021
| 14th February 2005
__

Stasys Jukna#### Disproving the single level conjecture

Revisions: 2
,
Comments: 1

__
TR05-022
| 19th February 2005
__

Omer Reingold, Luca Trevisan, Salil Vadhan#### Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

__
TR05-023
| 16th February 2005
__

Robert H. Sloan, Balázs Szörényi, György Turán#### On k-term DNF with largest number of prime implicants

__
TR05-024
| 8th February 2005
__

Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer#### Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

__
TR05-025
| 20th February 2005
__

Zeev Dvir, Ran Raz#### Analyzing Linear Mergers

__
TR05-026
| 15th February 2005
__

Scott Aaronson#### NP-complete Problems and Physical Reality

__
TR05-027
| 19th February 2005
__

Daniel Rolf#### Derandomization of PPSZ for Unique-$k$-SAT

__
TR05-028
| 12th February 2005
__

Elmar Böhler#### On the Lattice of Clones Below the Polynomial Time Functions

__
TR05-029
| 2nd March 2005
__

Frank Neumann, Marco Laumanns#### Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization

Revisions: 1

__
TR05-030
| 12th February 2005
__

Evgeny Dantsin, Alexander Wolpert#### An Improved Upper Bound for SAT

__
TR05-031
| 1st March 2005
__

Carme Alvarez, Joaquim Gabarro, Maria Serna#### Pure Nash equilibria in games with a large number of actions

__
TR05-032
| 16th March 2005
__

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen#### Reviewing Bounds on the Circuit Size of the Hardest Functions

__
TR05-033
| 5th March 2005
__

Martin Furer, Shiva Prasad Kasiviswanathan#### Algorithms for Counting 2-SAT Solutions and Colorings with Applications

__
TR05-034
| 5th April 2005
__

Luca Trevisan#### Approximation Algorithms for Unique Games

Revisions: 1
,
Comments: 1

__
TR05-035
| 24th March 2005
__

Christian Glaßer, Stephen Travers, Klaus W. Wagner#### A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

__
TR05-036
| 28th March 2005
__

Hubie Chen#### Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms

__
TR05-037
| 8th April 2005
__

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen#### On the Complexity of Numerical Analysis

Revisions: 1
,
Comments: 1

__
TR05-038
| 10th April 2005
__

Ran Raz#### Quantum Information and the PCP Theorem

__
TR05-039
| 13th April 2005
__

Irit Dinur, Elchanan Mossel, Oded Regev#### Conditional Hardness for Approximate Coloring

__
TR05-040
| 13th April 2005
__

Scott Aaronson#### Oracles Are Subtle But Not Malicious

__
TR05-041
| 12th April 2005
__

Shengyu Zhang#### (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

Revisions: 2

__
TR05-042
| 15th April 2005
__

Lance Fortnow, Adam Klivans#### Linear Advice for Randomized Logarithmic Space

Revisions: 1

__
TR05-043
| 5th April 2005
__

Emanuele Viola#### Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates

__
TR05-044
| 6th April 2005
__

Zeev Dvir, Amir Shpilka#### Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

__
TR05-045
| 12th April 2005
__

Philippe Moser#### Martingale Families and Dimension in P

Revisions: 1

__
TR05-046
| 17th April 2005
__

Irit Dinur#### The PCP theorem by gap amplification

Revisions: 1
,
Comments: 3

__
TR05-047
| 10th April 2005
__

Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri#### Weak Composite Diffie-Hellman is not Weaker than Factoring

__
TR05-048
| 11th April 2005
__

Moti Yung, Yunlei Zhao#### Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model

Revisions: 3

__
TR05-049
| 1st April 2005
__

Joan Boyar, rene peralta#### The Exact Multiplicative Complexity of the Hamming Weight Function

__
TR05-050
| 18th April 2005
__

Uriel Feige, Eran Ofek#### Finding a Maximum Independent Set in a Sparse Random Graph

Revisions: 1

__
TR05-051
| 18th March 2005
__

Predrag Tosic#### On Complexity of Counting Fixed Points in Certain Classes of Graph Automata

Revisions: 2

__
TR05-052
| 5th May 2005
__

Grant Schoenebeck, Salil Vadhan#### The Computational Complexity of Nash Equilibria in Concisely Represented Games

__
TR05-053
| 4th May 2005
__

Paul Beame, Nathan Segerlind#### Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity

__
TR05-054
| 19th May 2005
__

Konstantin Pervyshev#### Time Hierarchies for Computations with a Bit of Advice

__
TR05-055
| 19th May 2005
__

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye#### Leontief Economies Encode Nonzero Sum Two-Player Games

__
TR05-056
| 25th April 2005
__

Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis#### The Price of Optimum in Stackelberg Games

__
TR05-057
| 19th May 2005
__

Venkatesan Guruswami, Valentine Kabanets#### Hardness amplification via space-efficient direct products

__
TR05-058
| 24th May 2005
__

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra#### On Non-Approximability for Quadratic Programs

__
TR05-059
| 9th May 2005
__

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien#### Tractable Clones of Polynomials over Semigroups

__
TR05-060
| 30th May 2005
__

Philippe Moser#### Generic Density and Small Span Theorem

__
TR05-061
| 15th June 2005
__

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma#### On the Error Parameter of Dispersers

__
TR05-062
| 17th June 2005
__

A. Pavan, N. V. Vinodchandran#### 2-Local Random Reductions to 3-Valued Functions

__
TR05-063
| 24th June 2005
__

Bodo Manthey, Rüdiger Reischuk#### Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

__
TR05-064
| 26th June 2005
__

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani#### On earthmover distance, metric labeling, and 0-extension

__
TR05-065
| 26th June 2005
__

Alexander Barvinok, Alex Samorodnitsky#### Random Weighting, Asymptotic Counting, and Inverse Isoperimetry

__
TR05-066
| 4th June 2005
__

Jakob Nordström#### Narrow Proofs May Be Spacious: Separating Space and Width in Resolution

Revisions: 2
,
Comments: 1

__
TR05-067
| 28th June 2005
__

Zeev Dvir, Amir Shpilka#### An Improved Analysis of Mergers

Mergers are functions that transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate $\delta$ then the output has min-entropy rate close to $\delta$. Mergers have proven to be a very useful tool in ... more >>>

__
TR05-068
| 7th July 2005
__

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang#### Redundancy in Complete Sets

__
TR05-069
| 11th July 2005
__

Piotr Berman, Marek Karpinski#### 8/7-Approximation Algorithm for (1,2)-TSP

Revisions: 2

__
TR05-070
| 6th July 2005
__

Mahdi Cheraghchi#### On Matrix Rigidity and the Complexity of Linear Forms

__
TR05-071
| 29th June 2005
__

Marius Zimand#### Simple extractors via constructions of cryptographic pseudo-random generators

__
TR05-072
| 11th July 2005
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems

__
TR05-073
| 14th July 2005
__

Oded Goldreich, Dana Ron#### Approximating Average Parameters of Graphs.

__
TR05-074
| 8th June 2005
__

Li-Sha Huang, Xiaotie Deng#### On Complexity of Market Equilibria with Maximum Social Welfare

__
TR05-075
| 4th July 2005
__

Martin Dyer, Leslie Ann Goldberg, Mark Jerrum#### Dobrushin conditions and Systematic Scan

Revisions: 1

__
TR05-076
| 2nd July 2005
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### Time hierarchies for cryptographic function inversion with advice

__
TR05-077
| 15th July 2005
__

Zenon Sadowski#### On a D-N-optimal acceptor for TAUT

__
TR05-078
| 25th May 2005
__

Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz#### A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme

Revisions: 1

__
TR05-079
| 25th July 2005
__

Stasys Jukna#### Expanders and time-restricted branching programs

__
TR05-080
| 21st July 2005
__

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider#### Proving NP-hardness for clique-width I: non-approximability of sequential clique-width

Revisions: 1

__
TR05-081
| 21st July 2005
__

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider#### Proving NP-hardness for clique-width II: non-approximability of clique-width

Revisions: 1

__
TR05-082
| 3rd June 2005
__

Jorge Castro#### On the Query Complexity of Quantum Learners

__
TR05-083
| 24th July 2005
__

Olaf Beyersdorff#### Disjoint NP-Pairs from Propositional Proof Systems

__
TR05-084
| 31st July 2005
__

Mickey Brautbar, Alex Samorodnitsky#### Approximating the entropy of large alphabets

__
TR05-085
| 5th August 2005
__

Asaf Shapira, Noga Alon#### Homomorphisms in Graph Property Testing - A Survey

__
TR05-086
| 14th August 2005
__

Dana Moshkovitz, Ran Raz#### Sub-Constant Error Low Degree Test of Almost Linear Size

Revisions: 1

__
TR05-087
| 9th August 2005
__

Alexander Healy, Emanuele Viola#### Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

__
TR05-088
| 3rd August 2005
__

Jan Arpe#### Learning Juntas in the Presence of Noise

__
TR05-089
| 30th July 2005
__

Xiaoyang Gu, Jack H. Lutz, Philippe Moser#### Dimensions of Copeland-Erdos Sequences

__
TR05-090
| 17th August 2005
__

Paul Goldberg, Christos H. Papadimitriou#### Reducibility Among Equilibrium Problems

__
TR05-091
| 11th August 2005
__

Predrag Tosic#### Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs

Revisions: 1

__
TR05-092
| 23rd August 2005
__

Eyal Rozenman, Salil Vadhan#### Derandomized Squaring of Graphs

__
TR05-093
| 24th August 2005
__

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan#### Concurrent Zero Knowledge without Complexity Assumptions

__
TR05-094
| 9th August 2005
__

Michal Parnas, Dana Ron#### On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms

Revisions: 1

__
TR05-095
| 26th August 2005
__

Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin#### Partitioning multi-dimensional sets in a small number of ``uniform'' parts

__
TR05-096
| 26th August 2005
__

Boaz Barak, Amit Sahai#### How To Play Almost Any Mental Game Over The Net --- Concurrent Composition via Super-Polynomial Simulation

__
TR05-097
| 31st August 2005
__

Jens Groth, Rafail Ostrovsky, Amit Sahai#### Perfect Non-Interactive Zero Knowledge for NP

__
TR05-098
| 4th September 2005
__

Oded Goldreich#### Bravely, Moderately: A Common Theme in Four Recent Results

__
TR05-099
| 9th September 2005
__

Leslie G. Valiant#### Holographic Algorithms

__
TR05-100
| 30th August 2005
__

David Zuckerman#### Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

__
TR05-101
| 20th September 2005
__

Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel#### Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

__
TR05-102
| 13th September 2005
__

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert#### Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms

__
TR05-103
| 17th August 2005
__

Leonid Gurvits#### A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification

__
TR05-104
| 16th September 2005
__

Don Coppersmith, Atri Rudra#### On the Robust Testability of Product of Codes

__
TR05-105
| 24th September 2005
__

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang#### Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

__
TR05-106
| 26th September 2005
__

Anup Rao#### Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources

Revisions: 1

__
TR05-107
| 28th September 2005
__

Avi Wigderson, David Xiao#### A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

Revisions: 1

__
TR05-108
| 28th September 2005
__

Ariel Gabizon, Ran Raz#### Deterministic Extractors for Affine Sources over Large Fields

__
TR05-109
| 28th September 2005
__

Ariel Gabizon, Ran Raz, Ronen Shaltiel#### Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed

__
TR05-110
| 3rd October 2005
__

Saurabh Sanghvi, Salil Vadhan#### The Round Complexity of Two-Party Random Selection

__
TR05-111
| 3rd October 2005
__

Dieter van Melkebeek, Konstantin Pervyshev#### A Generic Time Hierarchy for Semantic Models With One Bit of Advice

__
TR05-112
| 12th September 2005
__

Eran Ofek#### On the expansion of the giant component in percolated $(n,d,\lambda)$ graphs

Revisions: 1

__
TR05-113
| 12th September 2005
__

Bernhard Fuchs#### On the Hardness of Range Assignment Problems

__
TR05-114
| 9th October 2005
__

Boaz Barak, Shien Jin Ong, Salil Vadhan#### Derandomization in Cryptography

__
TR05-115
| 27th September 2005
__

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou#### The complexity of computing a Nash equilibrium

__
TR05-116
| 12th October 2005
__

Alex Samorodnitsky, Luca Trevisan#### Gowers Uniformity, Influence of Variables, and PCPs

__
TR05-117
| 17th September 2005
__

Piotr Indyk, David P. Woodruff#### Polylogarithmic Private Approximations and Efficient Matching

__
TR05-118
| 16th October 2005
__

Jin-Yi Cai, Vinay Choudhary#### Valiant's Holant Theorem and Matchgate Tensors

__
TR05-119
| 15th September 2005
__

Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini#### Preferred representations of Boolean relations

__
TR05-120
| 14th October 2005
__

Sashka Davis, Russell Impagliazzo#### Models of Greedy Algorithms for Graph Problems

__
TR05-121
| 17th October 2005
__

Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson#### On counting homomorphisms to directed acyclic graphs

__
TR05-122
| 31st October 2005
__

Pavel Pudlak#### A nonlinear bound on the number of wires in bounded depth circuits

__
TR05-123
| 25th October 2005
__

Olaf Beyersdorff#### Tuples of Disjoint NP-Sets

__
TR05-124
| 2nd November 2005
__

Kooshiar Azimian#### Breaking Diffie-Hellman is no Easier than Root Finding

__
TR05-125
| 2nd November 2005
__

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith#### Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

__
TR05-126
| 5th November 2005
__

Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks#### Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

Comments: 2

__
TR05-127
| 5th November 2005
__

Vitaly Feldman#### Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries

Revisions: 1

__
TR05-128
| 27th October 2005
__

Miroslava Sotáková#### The normal form of reversible circuits consisting of CNOT and NOT gates

__
TR05-129
| 30th October 2005
__

Scott Aaronson#### QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

__
TR05-130
| 31st October 2005
__

Ahuva Mu'alem#### A Note on Testing Truthfulness

__
TR05-131
| 7th November 2005
__

Don Coppersmith, Lisa Fleischer, Atri Rudra#### Ordering by weighted number of wins gives a good ranking for weighted tournaments

__
TR05-132
| 8th November 2005
__

Venkatesan Guruswami#### Algebraic-geometric generalizations of the Parvaresh-Vardy codes

__
TR05-133
| 17th November 2005
__

Venkatesan Guruswami, Atri Rudra#### Explicit Capacity-Achieving List-Decodable Codes

Revisions: 1

__
TR05-134
| 17th November 2005
__

Xi Chen, Xiaotie Deng#### 3-NASH is PPAD-Complete

__
TR05-135
| 19th November 2005
__

Iftach Haitner, Danny Harnik, Omer Reingold#### On the Power of the Randomized Iterate

__
TR05-136
| 14th November 2005
__

Anna Gal, Michal Koucky, Pierre McKenzie#### Incremental branching programs

__
TR05-137
| 21st November 2005
__

Emanuele Viola#### On Probabilistic Time versus Alternating Time

__
TR05-138
| 22nd November 2005
__

Peter Bürgisser, Felipe Cucker#### Exotic quantifiers, complexity classes, and complete problems

__
TR05-139
| 21st November 2005
__

Constantinos Daskalakis, Christos H. Papadimitriou#### Three-Player Games Are Hard

__
TR05-140
| 30th November 2005
__

Xi Chen, Xiaotie Deng#### Settling the Complexity of 2-Player Nash-Equilibrium

Revisions: 1

__
TR05-141
| 29th November 2005
__

Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb#### Private Approximation of Search Problems

__
TR05-142
| 1st December 2005
__

Vadim Lyubashevsky, Daniele Micciancio#### Generalized Compact Knapsacks are Collision Resistant

__
TR05-143
| 29th November 2005
__

Parikshit Gopalan#### Constructing Ramsey Graphs from Boolean Function Representations

__
TR05-144
| 5th December 2005
__

Lance Fortnow, Luis Antunes#### Time-Bounded Universal Distributions

__
TR05-145
| 5th December 2005
__

Ronen Shaltiel#### How to get more mileage from randomness extractors

__
TR05-146
| 25th November 2005
__

Gábor Erdèlyi, Tobias Riege, Jörg Rothe#### Quantum Cryptography: A Survey

Revisions: 2

__
TR05-147
| 5th December 2005
__

Christian Glaßer, Stephen Travers#### Machines that can Output Empty Words

__
TR05-148
| 6th December 2005
__

Eric Allender, Samir Datta, Sambuddha Roy#### The Directed Planar Reachability Problem

Revisions: 1

__
TR05-149
| 7th December 2005
__

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy#### Grid Graph Reachability Problems

Revisions: 1

__
TR05-150
| 5th December 2005
__

Neeraj Kayal, Nitin Saxena#### Polynomial Identity Testing for Depth 3 Circuits

__
TR05-151
| 7th December 2005
__

Magnus Bordewich, Martin Dyer, Marek Karpinski#### Metric Construction, Stopping Times and Path Coupling.

__
TR05-152
| 9th December 2005
__

Oded Lachish, Ilan Newman#### Languages that are Recognized by Simple Counter Automata are not necessarily Testable

__
TR05-153
| 9th December 2005
__

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur#### Testing Orientation Properties

__
TR05-154
| 11th December 2005
__

Albert Atserias#### Non-Uniform Hardness for NP via Black-Box Adversaries

__
TR05-155
| 10th December 2005
__

Amir Shpilka#### Constructions of low-degree and error-correcting epsilon-biased sets

__
TR05-156
| 13th December 2005
__

Jonathan A. Kelner, Daniel A. Spielman#### A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)

__
TR05-157
| 10th December 2005
__

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo#### Points on Computable Curves

__
TR05-158
| 12th December 2005
__

Chris Peikert, Alon Rosen#### Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

__
TR05-159
| 14th November 2005
__

Daniel Rolf#### Improved Bound for the PPSZ/Schöning-Algorithm for $3$-SAT

__
TR05-160
| 10th December 2005
__

Xiaoyang Gu, Jack H. Lutz#### Dimension Characterizations of Complexity Classes

__
TR05-161
| 13th December 2005
__

John Hitchcock#### Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

__
TR05-162
| 23rd December 2005
__

Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Feng Dengguo#### Generic yet Practical ZK Arguments from any Public-Coin HVZK

Revisions: 1

__
TR05-163
| 19th December 2005
__

Dvir Falik, Alex Samorodnitsky#### Edge-isoperimetric inequalities and influences

Mario Szegedy

Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured

that the variance of their highly successful priority sampling procedure

is not larger than the variance of the threshold sampling procedure with sample size one smaller.

The conjecture's significance is that the latter procedure is provably optimal ...
more >>>

Magnus Bordewich, Martin Dyer, Marek Karpinski

We give a new method for analysing the mixing time of a Markov chain using

path coupling with stopping times. We apply this approach to two hypergraph

problems. We show that the Glauber dynamics for independent sets in a

hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ...
more >>>

Scott Aaronson

I study the class of problems efficiently solvable by a quantum computer, given the ability to "postselect" on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or Probabilistic Polynomial-Time. Using this result, I show that several simple changes to the axioms ... more >>>

Leslie G. Valiant

A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This paper addresses the simultaneous challenges of realizing these two distinct tasks with the same data ... more >>>

Tomas Feder

Constraint satisfaction on finite groups, with subgroups and their cosets

described by generators, has a polynomial time algorithm. For any given

group, a single additional constraint type that is not a coset of a near

subgroup makes the problem NP-complete. We consider constraint satisfaction on

groups with subgroups, near subgroups, ...
more >>>

Edward Hirsch, Sergey I. Nikolenko

Goerdt (1991) considered a weakened version of the Cutting Plane proof system with a restriction on the degree of falsity of intermediate inequalities. (The degree of falsity of an inequality written in the form $\sum a_ix_i+\sum b_i(1-x_i)\ge c,\ a_i,b_i\ge0$ is its constant term $c$.) He proved a superpolynomial lower bound ... more >>>

Vadim Lyubashevsky

In the Subset Sum problem, we are given n integers a_1,...,a_n

and a target number t, and are asked to find the subset of the

a_i's such that the sum is t. A version of the subset sum

problem is the Random Modular Subset Sum problem. In this version,

the ...
more >>>

Neeraj Kayal

Let $\mathbb{F}_q$ be a finite field and $f(x) \in \mathbb{F}_q(x)$ be a rational function over $\mathbb{F}_q$.

The decision problem {\bf PermFunction} consists of deciding whether $f(x)$ induces a permutation on

the elements of $\mathbb{F}_q$. That is, we want to decide whether the corresponding map

$f : \mathbb{F}_q ...
more >>>

David P. Woodruff, Sergey Yekhanin

A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR, and obtain (1) A t-private ... more >>>

Olivier Powell

We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems ... more >>>

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

We show the following results regarding complete sets:

NP-complete sets and PSPACE-complete sets are many-one

autoreducible.

Complete sets of any level of PH, MODPH, or

the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

... more >>>Luca Trevisan, Salil Vadhan, David Zuckerman

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).

1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).

Our next ... more >>>

Bin Fu

We introduce the notion of width bounded geometric separator,

develop the techniques for its existence as well as algorithm, and

apply it to obtain a $2^{O(\sqrt{n})}$ time exact algorithm for the

disk covering problem, which seeks to determine the minimal number

of fixed size disks to cover $n$ points on ...
more >>>

Oded Goldreich

We survey known results regarding locally testable codes

and locally testable proofs (known as PCPs),

with emphasis on the length of these constructs.

Locally testability refers to approximately testing

large objects based on a very small number of probes,

each retrieving a single bit in the ...
more >>>

Andrej Bogdanov, Luca Trevisan

We show that if an NP-complete problem has a non-adaptive

self-corrector with respect to a samplable distribution then

coNP is contained in NP/poly and the polynomial

hierarchy collapses to the third level. Feigenbaum and

Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion

under the stronger assumption that an

more >>>

Tomas Feder, Daniel Ford

Matroid intersection has a known polynomial time algorithm using an

oracle. We generalize this result to delta-matroids that do not have

equality as a restriction, and give a polynomial time algorithm for

delta-matroid intersection on delta-matroids without equality using an

oracle. We note that when equality is present, delta-matroid intersection

more >>>

Phong Nguyen

We introduce ``minimal'' two--sorted first--order theories VL, VSL, VNL and VP

that characterize the classes L, SL, NL and P in the same

way that Buss's $S^i_2$ hierarchy characterizes the polynomial time hierarchy.

Our theories arise from natural combinatorial problems, namely the st-Connectivity

Problem and the Circuit Value Problem.

It ...
more >>>

Oded Goldreich

The notion of promise problems was introduced and initially studied

by Even, Selman and Yacobi

(Information and Control, Vol.~61, pages 159-173, 1984).

In this article we survey some of the applications that this

notion has found in the twenty years that elapsed.

These include the notion ...
more >>>

Venkatesan Guruswami, Atri Rudra

An error-correcting code is said to be {\em locally testable} if it has an

efficient spot-checking procedure that can distinguish codewords

from strings that are far from every codeword, looking at very few

locations of the input in doing so. Locally testable codes (LTCs) have

generated ...
more >>>

Sourav Chakraborty

In this paper we construct a cyclically invariant Boolean function

whose sensitivity is $\Theta(n^{1/3})$. This result answers two

previously published questions. Tur\'an (1984) asked if any

Boolean function, invariant under some transitive group of

permutations, has sensitivity $\Omega(\sqrt{n})$. Kenyon and Kutin

(2004) asked whether for a ``nice'' function the product ...
more >>>

Stasys Jukna

We consider the minimal number of AND and OR gates in monotone

circuits for quadratic boolean functions, i.e. disjunctions of

length-$2$ monomials. The single level conjecture claims that

monotone single level circuits, i.e. circuits which have only one

level of AND gates, for quadratic functions ...
more >>>

Omer Reingold, Luca Trevisan, Salil Vadhan

Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>

Robert H. Sloan, Balázs Szörényi, György Turán

It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating ... more >>>

Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>

Zeev Dvir, Ran Raz

Mergers are functions that transform k (possibly dependent)

random sources into a single random source, in a way that ensures

that if one of the input sources has min-entropy rate $\delta$

then the output has min-entropy rate close to $\delta$. Mergers

have proven to be a very useful tool in ...
more >>>

Scott Aaronson

Can NP-complete problems be solved efficiently in the physical universe?

I survey proposals including soap bubbles, protein folding, quantum

computing, quantum advice, quantum adiabatic algorithms,

quantum-mechanical nonlinearities, hidden variables, relativistic time

dilation, analog computing, Malament-Hogarth spacetimes, quantum

gravity, closed timelike curves, and "anthropic computing." The ...
more >>>

Daniel Rolf

The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formulas can be found in expected running time at most $\Oc(1.3071^n).$ Using the technique of limited independence, we can derandomize this algorithm yielding $\Oc(1.3071^n)$ ... more >>>

Elmar Böhler

A clone is a set of functions that is closed under generalized substitution.

The set FP of functions being computable deterministically in polynomial

time is such a clone. It is well-known that the set of subclones of every

clone forms a lattice. We study the lattice below FP, which ...
more >>>

Frank Neumann, Marco Laumanns

We give faster approximation algorithms for the

generalization of two NP-hard spanning tree problems. First,

we investigate the problem of minimizing the degree of

minimum spanning forests. The task is to compute for each

number of connected components a minimum spanning forest

whose degree is as small as possible. Fischer

more >>>

Evgeny Dantsin, Alexander Wolpert

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most $2^{n(1-1/\alpha)}$ up to a polynomial factor, where $\alpha = \ln(m/n) + O(\ln \ln m)$ and $n$, $m$ are respectively the number of variables ... more >>>

Carme Alvarez, Joaquim Gabarro, Maria Serna

We study the computational complexity of deciding the existence of a

Pure Nash Equilibrium in multi-player strategic games.

We address two fundamental questions: how can we represent a game?, and

how can we represent a game with polynomial pay-off functions?

Our results show that the computational complexity of

deciding ...
more >>>

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen

In this paper we review the known bounds for $L(n)$, the circuit size

complexity of the hardest Boolean function on $n$ input bits. The

best known bounds appear to be $$\frac{2^n}{n}(1+\frac{\log

n}{n}-O(\frac{1}{n})) \leq L(n) \leq\frac{2^n}{n}(1+3\frac{\log

n}{n}+O(\frac{1}{n}))$$ However, the bounds do not seem to be

explicitly stated in the literature. We ...
more >>>

Martin Furer, Shiva Prasad Kasiviswanathan

An algorithm is presented for counting the number of maximum weight satisfying assignments of a 2SAT formula. The worst case running time of $O(\mbox{poly($n$)} \cdot 1.2461^n)$ for formulas with $n$ variables improves on the previous bound of $O(\mbox{poly($n$)} \cdot 1.2561^n)$ by Dahll\"of, Jonsson, and Wahlstr\"om . The weighted 2SAT counting ... more >>>

Luca Trevisan

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an ... more >>>

Christian Glaßer, Stephen Travers, Klaus W. Wagner

We introduce the polynomial-time tree reducibility

(ptt-reducibility). Our main result states that for

languages $B$ and $C$ it holds that

$B$ ptt-reduces to $C$ if and only if

the unbalanced leaf-language class of $B$ is robustly contained in

the unbalanced leaf-language class of $C$.

...
more >>>

Hubie Chen

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the quantified constraint satisfaction problem (QCSP), ... more >>>

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

We study two quite different approaches to understanding the complexity

of fundamental problems in numerical analysis. We show that both hinge

on the question of understanding the complexity of the following problem,

which we call PosSLP:

Given a division-free straight-line program

producing an integer N, decide whether N>0.

more >>>

Ran Raz

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$

by a single quantum state $|\Psi \rangle$ of size $O(n)$ qubits,

such that:

for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$,

the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved

from $|\Psi \rangle$ by a one-round Arthur-Merlin interactive ...
more >>>

Irit Dinur, Elchanan Mossel, Oded Regev

We study the approximate-coloring(q,Q) problem: Given a graph G, decide

whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional

hardness for this problem for any constant 3\le q < Q. For q \ge

4, our result is based on Khot's 2-to-1 conjecture [Khot'02].

For q=3, we base our hardness ...
more >>>

Scott Aaronson

Theoretical computer scientists have been debating the role of

oracles since the 1970's. This paper illustrates both that oracles

can give us nontrivial insights about the barrier problems in

circuit complexity, and that they need not prevent us from trying to

solve those problems.

First, we ... more >>>

Shengyu Zhang

The Local Search problem, which finds a

local minimum of a black-box function on a given graph, is of both

practical and theoretical importance to many areas in computer

science and natural sciences. In this paper, we show that for the

Boolean hypercube $\B^n$, the randomized query complexity of Local

more >>>

Lance Fortnow, Adam Klivans

We show that RL is contained in L/O(n), i.e., any language computable

in randomized logarithmic space can be computed in deterministic

logarithmic space with a linear amount of non-uniform advice. To

prove our result we show how to take an ultra-low space walk on

the Gabber-Galil expander graph.

Emanuele Viola

We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

Zeev Dvir, Amir Shpilka

In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... more >>>

Philippe Moser

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families,

that get rid of some drawbacks of previous measure notions:

martingale families can make money on all strings,

and yield random sequences with an equal frequency of 0's and 1's.

As applications to F-measure,

more >>>

Irit Dinur

Let C={c_1,...,c_n} be a set of constraints over a set of

variables. The {\em satisfiability-gap} of C is the smallest

fraction of unsatisfied constraints, ranging over all possible

assignments for the variables.

We prove a new combinatorial amplification lemma that doubles the

satisfiability-gap of a constraint-system, with only a linear ...
more >>>

Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri

In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an

RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. ...
more >>>

Moti Yung, Yunlei Zhao

We present constant-round concurrently secure (sound) resettable

zero-knowledge (rZK-CS) arguments in the bare public-key (BPK)

model. Our constructions deal with general NP ZK-arguments as well

as with highly efficient ZK-arguments for number-theoretic

languages, most relevant to identification scenarios. These are the

first constant-round protocols of ...
more >>>

Joan Boyar, rene peralta

We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>>

Uriel Feige, Eran Ofek

We consider the problem of finding a maximum independent set in a

random graph. The random graph $G$ is modelled as follows. Every

edge is included independently with probability $\frac{d}{n}$, where

$d$ is some sufficiently large constant. Thereafter, for some

constant $\alpha$, a subset $I$ of $\alpha n$ vertices is ...
more >>>

Predrag Tosic

We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean ... more >>>

Grant Schoenebeck, Salil Vadhan

Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number ... more >>>

Paul Beame, Nathan Segerlind

We prove that an \omega(log^3 n) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an n^\omega(1) size lower bound for tree-like Lovasz-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an n^\Omega(1) lower bound for the (k+1)-party NOF communication complexity of set-disjointness ... more >>>

Konstantin Pervyshev

A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1.

The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>>

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

We give a reduction from any two-player game to a special case of

the Leontief exchange economy, with the property that the Nash equilibria of the game and the

equilibria of the market are in one-to-one correspondence.

Our reduction exposes a potential hurdle inherent in solving certain

families of market ...
more >>>

Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>>

Venkatesan Guruswami, Valentine Kabanets

We prove a version of the derandomized Direct Product Lemma for

deterministic space-bounded algorithms. Suppose a Boolean function

$g:\{0,1\}^n\to\{0,1\}$ cannot be computed on more than $1-\delta$

fraction of inputs by any deterministic time $T$ and space $S$

algorithm, where $\delta\leq 1/t$ for some $t$. Then, for $t$-step

walks $w=(v_1,\dots, v_t)$ ...
more >>>

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

This paper studies the computational complexity of the following type of

quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ...
more >>>

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

It is well known that coset-generating relations lead to tractable

constraint satisfaction problems. These are precisely the relations closed

under the operation $xy^{-1}z$ where the multiplication is taken in

some finite group. Bulatov et al. have on the other hand shown that

any clone containing the multiplication of some ``block-group'' ...
more >>>

Philippe Moser

We refine the genericity concept of Ambos-Spies et al, by assigning a real number in $[0,1]$ to every generic set, called its generic density.

We construct sets of generic density any E-computable real in $[0,1]$.

We also introduce strong generic density, and show that it is related to packing ...
more >>>

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

Optimal dispersers have better dependence on the error than

optimal extractors. In this paper we give explicit disperser

constructions that beat the best possible extractors in some

parameters. Our constructions are not strong, but we show that

having such explicit strong constructions implies a solution

to the Ramsey graph construction ...
more >>>

A. Pavan, N. V. Vinodchandran

Yao (in a lecture at DIMACS Workshop on structural complexity and

cryptography) showed that if a language L is 2-locally-random

reducible to a Boolean functio, then L is in PSPACE/poly.

Fortnow and Szegedy quantitatively improved Yao's result to show that

such languages are in fact in NP/poly (Information Processing Letters, ...
more >>>

Bodo Manthey, Rüdiger Reischuk

Binary search trees are one of the most fundamental data structures. While the

height of such a tree may be linear in the worst case, the average height with

respect to the uniform distribution is only logarithmic. The exact value is one

of the best studied problems in average case ...
more >>>

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>>

Alexander Barvinok, Alex Samorodnitsky

For a family X of k-subsets of the set 1...n, let |X| be the cardinality of X and let Gamma(X, mu) be the expected maximum weight of a subset from X when the weights of 1...n are chosen independently at random from a symmetric probability distribution mu on R. We ... more >>>

Jakob Nordström

The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>>

Zeev Dvir, Amir Shpilka

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>>

Piotr Berman, Marek Karpinski

We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor of 7/6 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarily ... more >>>

Mahdi Cheraghchi

The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower ... more >>>

Marius Zimand

Trevisan has shown that constructions of pseudo-random generators from

hard functions (the Nisan-Wigderson approach) also produce extractors.

We show that constructions of pseudo-random generators from one-way permutations

(the Blum-Micali-Yao approach) can be used for building extractors as well.

Using this new technique we build extractors that ...
more >>>

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

We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus.

more >>>Oded Goldreich, Dana Ron

Inspired by Feige ({\em 36th STOC}, 2004),

we initiate a study of sublinear randomized algorithms

for approximating average parameters of a graph.

Specifically, we consider the average degree of a graph

and the average distance between pairs of vertices in a graph.

Since our focus is on sublinear algorithms, ...
more >>>

Li-Sha Huang, Xiaotie Deng

We consider the computational complexity of the market equilibrium

problem by exploring the structural properties of the Leontief

exchange economy. We prove that, for economies guaranteed to have

a market equilibrium, finding one with maximum social welfare or

maximum individual welfare is NP-hard. In addition, we prove that

counting the ...
more >>>

Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

We consider Glauber dynamics on finite spin systems.

The mixing time of Glauber dynamics can be bounded

in terms of the influences of sites on each other.

We consider three parameters bounding these influences ---

$\alpha$, the total influence on a site, as studied by Dobrushin;

$\alpha'$, the total influence ...
more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

We prove a time hierarchy theorem for inverting functions

computable in polynomial time with one bit of advice.

In particular, we prove that if there is a strongly

one-way function, then for any k and for any polynomial p,

there is a function f computable in linear time

with one ...
more >>>

Zenon Sadowski

The notion of an optimal acceptor for TAUT (the optimality

property is stated only for input strings from TAUT) comes from the line

of research aimed at resolving the question of whether optimal

propositional proof systems exist. In this paper we introduce two new

types of optimal acceptors, a D-N-optimal ...
more >>>

Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz

In this paper, firstly we propose two new concepts concerning the notion of key escrow encryption schemes: provable partiality and independency. Roughly speaking we say that a scheme has provable partiality if existing polynomial time algorithm for recovering the secret knowing escrowed information implies a polynomial time algorithm that can ... more >>>

Stasys Jukna

The \emph{replication number} of a branching program is the minimum

number R such that along every accepting computation at most R

variables are tested more than once. Hence 0\leq R\leq n for every

branching program in n variables. The best results so far were

exponential ...
more >>>

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Clique-width is a graph parameter, defined by a composition mechanism

for vertex-labeled graphs, which measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic, that includes NP-hard

problems) can be solved efficiently for graphs of certified small

clique-width. It ...
more >>>

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Clique-width is a graph parameter that measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic with second-order

quantification on vertex sets, that includes NP-hard problems) can be

solved efficiently for graphs of certified small clique-width. It is

widely ...
more >>>

Jorge Castro

This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general ... more >>>

Olaf Beyersdorff

For a proof system P we introduce the complexity class DNPP(P)

of all disjoint NP-pairs for which the disjointness of the pair is

efficiently provable in the proof system P.

We exhibit structural properties of proof systems which make the

previously defined canonical NP-pairs of these proof systems hard ...
more >>>

Mickey Brautbar, Alex Samorodnitsky

We consider the problem of approximating the entropy of a discrete distribution P on a domain of size q, given access to n independent samples from the distribution. It is known that n > q is necessary, in general, for a good additive estimate of the entropy. A problem of ... more >>>

Asaf Shapira, Noga Alon

Property-testers are fast randomized algorithms for distinguishing

between graphs (and other combinatorial structures) satisfying a

certain property, from those that are far from satisfying it. In

many cases one can design property-testers whose running time is in

fact {\em independent} of the size of the input. In this paper we

more >>>

Dana Moshkovitz, Ran Raz

Given a function f:F^m \rightarrow F over a finite

field F, a low degree tester tests its proximity to

an m-variate polynomial of total degree at most d

over F. The tester is usually given access to an oracle

A providing the supposed restrictions of f to

affine subspaces of ...
more >>>

Alexander Healy, Emanuele Viola

We study the complexity of arithmetic in finite fields of characteristic two, $\F_{2^n}$.

We concentrate on the following two problems:

Iterated Multiplication: Given $\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute $\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$.

Exponentiation: Given $\alpha \in \F_{2^n}$ and a $t$-bit integer $k$, compute $\alpha^k \in \F_{2^n}$.

... more >>>Jan Arpe

The combination of two major challenges in machine learning is investigated: dealing with large amounts of irrelevant information and learning from noisy data. It is shown that large classes of Boolean concepts that depend on a small number of variables---so-called juntas---can be learned efficiently from random examples corrupted by random ... more >>>

Xiaoyang Gu, Jack H. Lutz, Philippe Moser

The base-$k$ {\em Copeland-Erd\"os sequence} given by an infinite

set $A$ of positive integers is the infinite

sequence $\CE_k(A)$ formed by concatenating the base-$k$

representations of the elements of $A$ in numerical

order. This paper concerns the following four

quantities.

\begin{enumerate}[$\bullet$]

\item

The {\em finite-state dimension} $\dimfs (\CE_k(A))$,

a finite-state ...
more >>>

Paul Goldberg, Christos H. Papadimitriou

We address the fundamental question of whether the Nash equilibria of

a game can be computed in polynomial time. We describe certain

efficient reductions between this problem for

normal form games with a fixed number of players

and graphical games with fixed degree. Our main result is that ...
more >>>

Predrag Tosic

We study counting various types of con gurations in certain classes of graph

automata viewed as discrete dynamical systems. The graph automata models

of our interest are Sequential and Synchronous Dynamical Systems (SDSs and

SyDSs, respectively). These models have been proposed as a mathematical foun-

dation for a theory of ...
more >>>

Eyal Rozenman, Salil Vadhan

We introduce a "derandomized" analogue of graph squaring. This

operation increases the connectivity of the graph (as measured by the

second eigenvalue) almost as well as squaring the graph does, yet only

increases the degree of the graph by a constant factor, instead of

squaring the degree.

One application of ... more >>>

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

We provide <i>unconditional</i> constructions of <i>concurrent</i>

statistical zero-knowledge proofs for a variety of non-trivial

problems (not known to have probabilistic polynomial-time

algorithms). The problems include Graph Isomorphism, Graph

Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a

restricted version of Statistical Difference, and approximate

versions of the (<b>coNP</b> forms of the) Shortest Vector ...
more >>>

Michal Parnas, Dana Ron

We consider the problem of estimating the size, $VC(G)$, of a

minimum vertex cover of a graph $G$, in sublinear time,

by querying the incidence relation of the graph. We say that

an algorithm is an $(\alpha,\eps)$-approximation algorithm

if it outputs with high probability an estimate $\widehat{VC}$

such that ...
more >>>

Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>

Boaz Barak, Amit Sahai

We construct a secure protocol for any multi-party functionality

that remains secure (under a relaxed definition of security) when

executed concurrently with multiple copies of itself and other

protocols. We stress that we do *not* use any assumptions on

existence of trusted parties, common reference string, honest

majority or synchronicity ...
more >>>

Jens Groth, Rafail Ostrovsky, Amit Sahai

Non-interactive zero-knowledge (NIZK) systems are

fundamental cryptographic primitives used in many constructions,

including CCA2-secure cryptosystems, digital signatures, and various

cryptographic protocols. What makes them especially attractive, is

that they work equally well in a concurrent setting, which is

notoriously hard for interactive zero-knowledge protocols. However,

while for interactive zero-knowledge we ...
more >>>

Oded Goldreich

We highlight a common theme in four relatively recent works

that establish remarkable results by an iterative approach.

Starting from a trivial construct,

each of these works applies an ingeniously designed

sequence of iterations that yields the desired result,

which is highly non-trivial. Furthermore, in each iteration,

more >>>

Leslie G. Valiant

Complexity theory is built fundamentally on the notion of efficient

reduction among computational problems. Classical

reductions involve gadgets that map solution fragments of one problem to

solution fragments of another in one-to-one, or

possibly one-to-many, fashion. In this paper we propose a new kind of

reduction that allows for gadgets ...
more >>>

David Zuckerman

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>>

Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\GW + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>>

Leonid Gurvits

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables .

Assume that this polynomial satisfies the property : \\

$|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n) : Re(z_i) \geq 0 , 1 \leq i \leq n \}$ . \\

We prove that ... more >>>

Don Coppersmith, Atri Rudra

Ben-Sasson and Sudan in~\cite{BS04} asked if the following test

is robust for the tensor product of a code with another code--

pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that ...
more >>>

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang

We apply recent results on extracting randomness from independent

sources to ``extract'' Kolmogorov complexity. For any $\alpha,

\epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show

how to use a constant number of advice bits to efficiently

compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) >

(1-\epsilon)|y|$. ...
more >>>

Anup Rao

We consider the problem of bit extraction from independent sources. We

construct an extractor that can extract from a constant number of

independent sources of length $n$, each of which have min-entropy

$n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our

constructions are different from recent extractor constructions

more >>>

Avi Wigderson, David Xiao

In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>>

Ariel Gabizon, Ran Raz

An $(n,k)$-affine source over a finite field $F$ is a random

variable $X=(X_1,...,X_n) \in F^n$, which is uniformly

distributed over an (unknown) $k$-dimensional affine subspace of $

F^n$. We show how to (deterministically) extract practically all

the randomness from affine sources, for any field of size larger

than $n^c$ (where ...
more >>>

Ariel Gabizon, Ran Raz, Ronen Shaltiel

An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that

there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly

distributed and independent of each other, and the remaining $n-k$ variables

are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n

\ar \B^m$ which on ...
more >>>

Saurabh Sanghvi, Salil Vadhan

We study the round complexity of two-party protocols for

generating a random $n$-bit string such that the output is

guaranteed to have bounded bias (according to some measure) even

if one of the two parties deviates from the protocol (even using

unlimited computational resources). Specifically, we require that

the output's ...
more >>>

Dieter van Melkebeek, Konstantin Pervyshev

We show that for any reasonable semantic model of computation and for

any positive integer $a$ and rationals $1 \leq c < d$, there exists a language

computable in time $n^d$ with $a$ bits of advice but not in time $n^c$

with $a$ bits of advice. A semantic ...
more >>>

Eran Ofek

Let $d \geq d_0$ be a sufficiently large constant. A $(n,d,c

\sqrt{d})$ graph $G$ is a $d$ regular graph over $n$ vertices whose

second largest eigenvalue (in absolute value) is at most $c

\sqrt{d}$. For any $0 < p < 1, ~G_p$ is the graph induced by

retaining each edge ...
more >>>

Bernhard Fuchs

We investigate the computational hardness of the {\sc Connectivity},

the {\sc Strong Connectivity} and the {\sc Broadcast} type of Range

Assignment Problems in $\R^2$ and $\R^3$.

We present new reductions for the {\sc Connectivity} problem, which

are easily adapted to suit the other two problems. All reductions

are considerably simpler ...
more >>>

Boaz Barak, Shien Jin Ong, Salil Vadhan

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... more >>>

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

We resolve the question of the complexity of Nash equilibrium by

showing that the problem of computing a Nash equilibrium in a game

with 4 or more players is complete for the complexity class PPAD.

Our proof uses ideas from the recently-established equivalence

between polynomial-time solvability of normal-form games and

more >>>

Alex Samorodnitsky, Luca Trevisan

Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f)

of a function f: G -> \C, where G is a finite abelian group and \C are the

complex numbers. Roughly speaking, if a function has small Gowers uniformity

of dimension d, then it ``looks random'' on ...
more >>>

Piotr Indyk, David P. Woodruff

A private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about the input x other than what can be deduced from f(x). We give the first two-party private approximation of the Euclidean distance ... more >>>

Jin-Yi Cai, Vinay Choudhary

We propose matchgate tensors as a natural and proper language

to develop Valiant's new theory of Holographic Algorithms.

We give a treatment of the central theorem in this theory---the Holant

Theorem---in terms of matchgate tensors.

Some generalizations are presented.

Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini

We introduce the notion of a plain basis for a co-clone in Post's lattice. Such a basis is a set of relations B such that every constraint C over a relation in the co-clone is logically equivalent to a conjunction of equalities and constraints over B and the same variables ... more >>>

Sashka Davis, Russell Impagliazzo

Borodin, Nielsen, and Rackoff gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin extended their work to facility location and set cover problems. We generalize their notion to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an ... more >>>

Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson

We give a dichotomy theorem for the problem of counting homomorphisms to

directed acyclic graphs. $H$ is a fixed directed acyclic graph.

The problem is, given an input digraph $G$, how many homomorphisms are there

from $G$ to $H$. We give a graph-theoretic classification, showing that

for some digraphs $H$, ...
more >>>

Pavel Pudlak

We shall prove a lower bound on the number of edges in some bounded

depth graphs. This theorem is stronger than lower bounds proved on

bounded depth superconcentrators and enables us to prove a lower bound

on certain bounded depth circuits for which we cannot use

superconcentrators: we prove that ...
more >>>

Olaf Beyersdorff

Disjoint NP-pairs are a well studied complexity theoretic concept with

important applications in cryptography and propositional proof

complexity.

In this paper we introduce a natural generalization of the notion of

disjoint NP-pairs to disjoint k-tuples of NP-sets for k>1.

We define subclasses of ...
more >>>

Kooshiar Azimian

In this paper we compare hardness of two well known problems: the Diffie-Hellman problem and the root finding problem. We prove that in any cyclic group computing Diffie-Hellman is not weaker than root finding if certain circumstances are met. As will be discussed in the paper this theorem can affect ... more >>>

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith

We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>>

Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

For circuit classes R, the fundamental computational problem, Min-R,

asks for the minimum R-size of a boolean function presented as a truth

table. Prominent examples of this problem include Min-DNF, and

Min-Circuit (also called MCSP). We begin by presenting a new reduction

proving that Min-DNF is NP-complete. It is significantly ...
more >>>

Vitaly Feldman

Producing a small DNF expression consistent with given data is a

classical problem in computer science that occurs in a number of forms and

has numerous applications. We consider two standard variants of this

problem. The first one is two-level logic minimization or finding a minimal

more >>>

Miroslava Sotáková

This paper deals with the reversible circuits with n input and

output nodes, consisting of the reversible gates FAN-IN=FAN-OUT<3.

We define a normal form of such type of circuits and describe a reduction

algorithm to transform a circuit in this form. Furthermore we use it for

checking whether two circuits ...
more >>>

Scott Aaronson

This paper introduces a new technique for removing existential quantifiers

over quantum states. Using this technique, we show that there is no way

to pack an exponential number of bits into a polynomial-size quantum

state, in such a way that the value of any one of those bits ...
more >>>

Ahuva Mu'alem

This work initiates the study of algorithms

for the testing of monotonicity of mechanisms.

Such testing algorithms are useful for

searching dominant strategy mechanisms.

An $\e$-tester for monotonicity

is given a query access to a mechanism,

accepts if monotonicity is satisfied,

and rejects with high probability if more than $\e$-fraction

more >>>

Don Coppersmith, Lisa Fleischer, Atri Rudra

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints}

(for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ...
more >>>

Venkatesan Guruswami

This paper is concerned with a new family of error-correcting codes

based on algebraic curves over finite fields, and list decoding

algorithms for them. The basic goal in the subject of list decoding is

to construct error-correcting codes $C$ over some alphabet $\Sigma$

which have good rate $R$, and at ...
more >>>

Venkatesan Guruswami, Atri Rudra

For every $0 < R < 1$ and $\eps > 0$, we present an explicit

construction of error-correcting codes of rate $R$ that can be list

decoded in polynomial time up to a fraction $(1-R-\eps)$ of errors.

These codes achieve the ``capacity'' for decoding from {\em ...
more >>>

Xi Chen, Xiaotie Deng

In this paper, we improve a recent result of Daskalakis, Goldberg and Papadimitriou on PPAD-completeness of 4-Nash, showing that 3-Nash is PPAD-complete.

more >>>Iftach Haitner, Danny Harnik, Omer Reingold

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>

Anna Gal, Michal Koucky, Pierre McKenzie

In this paper we propose the study of a new model of restricted

branching programs which we call incremental branching programs.

This is in line with the program proposed by Cook in 1974 as an

approach for separating the class of problems solvable in logarithmic

space from problems solvable ...
more >>>

Emanuele Viola

We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>

Peter Bürgisser, Felipe Cucker

We introduce some operators defining new complexity classes from existing ones in the Blum-Shub-Smale theory of computation over the reals. Each one of these operators is defined with the help of a quantifier differing from the usual ones, $\forall$ and $\exists$, and yet having a precise geometric meaning. Our agenda ... more >>>

Constantinos Daskalakis, Christos H. Papadimitriou

We prove that computing a Nash equilibrium in a 3-player

game is PPAD-complete, solving a problem left open in our recent result on the complexity of Nash equilibria.

Xi Chen, Xiaotie Deng

We prove that finding the solution of two player Nash Equilibrium is PPAD-complete.

more >>>Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb

Many approximation algorithms have been presented in the last decades

for hard search problems. The focus of this paper is on cryptographic

applications, where it is desired to design algorithms which do not

leak unnecessary information. Specifically, we are interested in

private approximation algorithms -- efficient algorithms ...
more >>>

Vadim Lyubashevsky, Daniele Micciancio

The generalized knapsack problem is the following: given $m$ random

elements $a_1,\ldots,a_m\in R$ for some ring $R$, and a target $t\in

R$, find elements $z_1,\ldots,z_m\in D$ such that $\sum{a_iz_i}=t$

where $D$ is some given subset of $R$. In (Micciancio, FOCS 2002),

it was proved that for appropriate choices of $R$ ...
more >>>

Parikshit Gopalan

Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions ... more >>>

Lance Fortnow, Luis Antunes

We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions.

more >>>Ronen Shaltiel

Let $\cal C$ be a class of distributions over $\B^n$. A deterministic randomness extractor for $\cal C$ is a function $E:\B^n \ar \B^m$ such that for any $X$ in $\cal C$ the distribution $E(X)$ is statistically close to the uniform distribution. A long line of research deals with explicit constructions ... more >>>

Gábor Erdèlyi, Tobias Riege, Jörg Rothe

We survey some results in quantum cryptography. After a brief

introduction to classical cryptography, we provide the physical and

mathematical background needed and present some fundamental protocols

from quantum cryptography, including quantum key distribution and

quantum bit commitment protocols.

Christian Glaßer, Stephen Travers

We propose the e-model for leaf languages which generalizes the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words.

The paper explains several advantages of the new model. A central aspect is that it allows us ... more >>>

Eric Allender, Samir Datta, Sambuddha Roy

We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since

* reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and

* reachability on certain classes of grid graphs gives ...
more >>>

Neeraj Kayal, Nitin Saxena

We study the identity testing problem for depth $3$ arithmetic circuits ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\Sigma\Pi\Sigma$ circuits with bounded top fanin. We also show that the {\em rank} of a minimal and simple $\Sigma\Pi\Sigma$ circuit with bounded top fanin, computing zero, can ... more >>>

Magnus Bordewich, Martin Dyer, Marek Karpinski

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... more >>>

Oded Lachish, Ilan Newman

Combinatorial property testing deals with the following relaxation of

decision problems: Given a fixed property and an input $f$, one wants

to decide whether $f$ satisfies the property or is `far' from satisfying

the property.

It has been shown that regular languages are testable,

and that there exist context free ...
more >>>

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

We propose a new model for studying graph related problems

that we call the \emph{orientation model}. In this model, an undirected

graph $G$ is fixed, and the input is any possible edge orientation

of $G$. A property is now a property of the directed graph that is

obtained by a ...
more >>>

Albert Atserias

We may believe SAT does not have small Boolean circuits.

But is it possible that some language with small circuits

looks indistiguishable from SAT to every polynomial-time

bounded adversary? We rule out this possibility. More

precisely, assuming SAT does not have small circuits, we

show that ...
more >>>

Amir Shpilka

In this work we give two new constructions of $\epsilon$-biased

generators. Our first construction answers an open question of

Dodis and Smith, and our second construction

significantly extends a result of Mossel et al.

In particular we obtain the following results:

1. We construct a family of asymptotically good binary ... more >>>

Jonathan A. Kelner, Daniel A. Spielman

We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input.

We begin by reducing the input linear program to a special form in which we ... more >>>

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

The ``analyst's traveling salesman theorem'' of geometric

measure theory characterizes those subsets of Euclidean

space that are contained in curves of finite length.

This result, proven for the plane by Jones (1990) and

extended to higher-dimensional Euclidean spaces by

Okikiolu (1991), says that a bounded set $K$ is contained

more >>>

Chris Peikert, Alon Rosen

The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i

a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$

elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists

of $m$ coefficients from a specified subset $S \subseteq R$.

Micciancio ...
more >>>

Daniel Rolf

The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formula can be found in expected running time at most $O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, Schöning proved ... more >>>

Xiaoyang Gu, Jack H. Lutz

We use derandomization to show that sequences of positive $\pspace$-dimension -- in fact, even positive $\Delta^\p_k$-dimension

for suitable $k$ -- have, for many purposes, the full power of random oracles. For example, we show that, if $S$ is any binary sequence whose $\Delta^p_3$-dimension is positive, then $\BPP\subseteq \P^S$ and, moreover, ...
more >>>

John Hitchcock

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one ... more >>>

Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Feng Dengguo

In this work, we present a generic yet practical transformation from any public-coin honest-verifier zero-knowledge (HVZK) protocols to normal zero-knowledge (ZK) arguments. By ``generic", we mean that the transformation is applicable to any public-coin HVZK protocol under any one-way function (OWF) admitting Sigma-protocols. By ``practical" we mean that the transformation ... more >>>

Dvir Falik, Alex Samorodnitsky

We give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least Omega(log(n)/n).The methods of the proof are then used to recover additional isoperimetric results for the cube, with ... more >>>