All reports in year 2007:

__
TR07-001
| 19th November 2006
__

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider#### Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution

Revisions: 2

__
TR07-002
| 8th November 2006
__

Moti Yung, Yunlei Zhao#### Concurrent Knowledge-Extraction in the Public-Key Model

Comments: 2

__
TR07-003
| 5th January 2007
__

Jin-Yi Cai, Pinyan Lu#### Bases Collapse in Holographic Algorithms

__
TR07-004
| 12th January 2007
__

Lance Fortnow, Rahul Santhanam#### Time Hierarchies: A Survey

__
TR07-005
| 17th January 2007
__

Rahul Santhanam#### Circuit Lower Bounds for Merlin-Arthur Classes

__
TR07-006
| 12th January 2007
__

David P. Woodruff#### New Lower Bounds for General Locally Decodable Codes

__
TR07-007
| 17th January 2007
__

Jan Krajicek#### An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams

__
TR07-008
| 27th November 2006
__

Philipp Weis, Neil Immerman#### Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words

__
TR07-009
| 8th January 2007
__

Nathan Segerlind#### Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

Revisions: 1
,
Comments: 1

__
TR07-010
| 4th January 2007
__

Arist Kojevnikov#### Improved Lower Bounds for Resolution over Linear Inequalities

Revisions: 1

__
TR07-011
| 19th December 2006
__

Bodo Manthey#### On Approximating Restricted Cycle Covers

__
TR07-012
| 22nd January 2007
__

Shachar Lovett, Sasha Sodin#### Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Revisions: 1

__
TR07-013
| 6th February 2007
__

Andris Ambainis, Joseph Emerson#### Quantum t-designs: t-wise independence in the quantum world

__
TR07-014
| 23rd January 2007
__

Amit Chakrabarti#### Lower Bounds for Multi-Player Pointer Jumping

__
TR07-015
| 1st March 2007
__

Oded Goldreich, Or Sheffet#### On the randomness complexity of property testing

__
TR07-016
| 13th February 2007
__

Prasad Raghavendra#### A Note on Yekhanin's Locally Decodable Codes

Revisions: 1

__
TR07-017
| 18th January 2007
__

Ashish Rastogi, Richard Cole#### Indivisible Markets with Good Approximate EquilibriumPrices

Revisions: 1

__
TR07-018
| 1st March 2007
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### The Informational Content of Canonical Disjoint NP-Pairs

__
TR07-019
| 10th March 2007
__

Jin-Yi Cai, Pinyan Lu#### On Block-wise Symmetric Signatures for Matchgates

__
TR07-020
| 11th March 2007
__

Jin-Yi Cai, Pinyan Lu#### Holographic Algorithms: The Power of Dimensionality Resolved

__
TR07-021
| 5th March 2007
__

Brett Hemenway, Rafail Ostrovsky#### Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code

Revisions: 3

__
TR07-022
| 20th February 2007
__

Rafail Ostrovsky, William Skeith#### Algebraic Lower Bounds for Computing on Encrypted Data

__
TR07-023
| 26th February 2007
__

Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor#### The Complexity of Problems for Quantified Constraints

__
TR07-024
| 5th March 2007
__

Laszlo Egri, Benoit Larose, Pascal Tesson#### Symmetric Datalog and Constraint Satisfaction Problems in Logspace

__
TR07-025
| 5th March 2007
__

Benoit Larose, Pascal Tesson, Pascal Tesson#### Universal Algebra and Hardness Results for Constraint Satisfaction Problems

__
TR07-026
| 21st November 2006
__

Dana Moshkovitz, Ran Raz#### Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size

__
TR07-027
| 2nd February 2007
__

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt#### Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models

__
TR07-028
| 12th February 2007
__

Daniel Sawitzki#### Implicit Simulation of FNC Algorithms

__
TR07-029
| 20th January 2007
__

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto#### A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem

Revisions: 1

__
TR07-030
| 29th March 2007
__

Kai-Min Chung, Omer Reingold, Salil Vadhan#### S-T Connectivity on Digraphs with a Known Stationary Distribution

__
TR07-031
| 26th March 2007
__

Yael Tauman Kalai, Ran Raz#### Interactive PCP

__
TR07-032
| 27th March 2007
__

Pavel Pudlak#### Quantum deduction rules

__
TR07-033
| 14th February 2007
__

Michael Navon, Alex Samorodnitsky#### Linear programming bounds for codes via a covering argument

__
TR07-034
| 29th March 2007
__

Anup Rao#### An Exposition of Bourgain's 2-Source Extractor

__
TR07-035
| 3rd April 2007
__

Mark Braverman, Raghav Kulkarni, Sambuddha Roy#### Parity Problems in Planar Graphs

__
TR07-036
| 6th April 2007
__

Ryan Williams#### Time-Space Tradeoffs for Counting NP Solutions Modulo Integers

__
TR07-037
| 2nd February 2007
__

Leonid Gurvits#### Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

Revisions: 1

__
TR07-038
| 23rd April 2007
__

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev#### Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

__
TR07-039
| 27th March 2007
__

Bodo Manthey, Till Tantau#### Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Revisions: 1

__
TR07-040
| 12th April 2007
__

Kiran Kedlaya, Sergey Yekhanin#### Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers

__
TR07-041
| 20th April 2007
__

Nicola Galesi, Massimo Lauria#### Extending Polynomial Calculus to $k$-DNF Resolution

Revisions: 1

__
TR07-042
| 7th May 2007
__

Zohar Karnin, Amir Shpilka#### Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in

Revisions: 2
,
Comments: 1

__
TR07-043
| 7th May 2007
__

Uriel Feige, Guy Kindler, Ryan O'Donnell#### Understanding Parallel Repetition Requires Understanding Foams

__
TR07-044
| 23rd April 2007
__

Philipp Hertel#### Black-White Pebbling is PSPACE-Complete

__
TR07-045
| 24th April 2007
__

Heribert Vollmer#### The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

__
TR07-046
| 23rd April 2007
__

Philipp Hertel#### An Exponential Time/Space Speedup For Resolution

Comments: 1

__
TR07-047
| 15th May 2007
__

Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum#### A (De)constructive Approach to Program Checking

__
TR07-048
| 3rd April 2007
__

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer#### Earth Mover Distance over High-Dimensional Spaces

__
TR07-049
| 1st June 2007
__

Beate Bollig, Niko Range, Ingo Wegener#### Exact OBDD Bounds for some Fundamental Functions

__
TR07-050
| 25th May 2007
__

Arkadev Chattopadhyay#### Discrepancy and the power of bottom fan-in in depth-three circuits

__
TR07-051
| 18th April 2007
__

Pilar Albert, Elvira Mayordomo, Philippe Moser#### Bounded Pushdown dimension vs Lempel Ziv information density

__
TR07-052
| 7th May 2007
__

Li Chen, Bin Fu#### Linear and Sublinear Time Algorithms for the Basis of Abelian Groups

Revisions: 2

__
TR07-053
| 27th April 2007
__

Jens Groth, Amit Sahai#### Efficient Non-interactive Proof Systems for Bilinear Groups

__
TR07-054
| 25th May 2007
__

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur#### Testing Properties of Constraint-Graphs

__
TR07-055
| 22nd May 2007
__

Oliver Kullmann#### Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability

Revisions: 1

__
TR07-056
| 10th July 2007
__

Zeev Dvir, Ariel Gabizon, Avi Wigderson#### Extractors and Rank Extractors for Polynomial Sources

__
TR07-057
| 11th July 2007
__

Oded Goldreich#### On the Average-Case Complexity of Property Testing

Revisions: 1

__
TR07-058
| 9th June 2007
__

Dmytro Gavinsky#### Classical Interaction Cannot Replace a Quantum Message

Revisions: 1

__
TR07-059
| 6th July 2007
__

Shankar Kalyanaraman, Chris Umans#### Algorithms for Playing Games with Limited Randomness

__
TR07-060
| 11th July 2007
__

Tali Kaufman, Madhu Sudan#### Sparse Random Linear Codes are Locally Decodable and Testable

__
TR07-061
| 12th July 2007
__

Or Meir#### On the Rectangle Method in proofs of Robustness of Tensor Products

Revisions: 4

__
TR07-062
| 15th July 2007
__

Oded Goldreich, Or Meir#### The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable

Revisions: 2

__
TR07-063
| 2nd July 2007
__

Tomas Feder, Carlos Subi#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations

__
TR07-064
| 19th June 2007
__

Rahul Jain, Hartmut Klauck, Ashwin Nayak#### Direct Product Theorems for Communication Complexity via Subdistribution Bounds

__
TR07-065
| 13th July 2007
__

Jonathan Katz#### Which Languages Have 4-Round Zero-Knowledge Proofs?

__
TR07-066
| 24th April 2007
__

Maciej Liskiewicz, Christian Hundt#### A Combinatorial Geometric Approach to Linear Image Matching

__
TR07-067
| 22nd May 2007
__

Paul Spirakis, haralampos tsaknakis#### Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.

Revisions: 2

__
TR07-068
| 24th July 2007
__

Thomas Thierauf, Fabian Wagner#### The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace

__
TR07-069
| 29th July 2007
__

Ronen Shaltiel, Chris Umans#### Low-end uniform hardness vs. randomness tradeoffs for AM

__
TR07-070
| 11th June 2007
__

Nir Ailon, Edo Liberty#### Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

__
TR07-071
| 1st August 2007
__

Jacobo Toran#### Reductions to Graph Isomorphism

__
TR07-072
| 2nd July 2007
__

Alexander A. Sherstov#### Communication Complexity under Product and Nonproduct Distributions

__
TR07-073
| 3rd August 2007
__

Parikshit Gopalan, Subhash Khot, Rishi Saket#### Hardness of Reconstructing Multivariate Polynomials over Finite Fields

__
TR07-074
| 7th August 2007
__

Dmytro Gavinsky, Pavel Pudlak#### Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

__
TR07-075
| 9th August 2007
__

Shachar Lovett#### Unconditional pseudorandom generators for low degree polynomials

__
TR07-076
| 25th July 2007
__

Satyen Kale, C. Seshadhri#### Testing Expansion in Bounded Degree Graphs

Revisions: 1

__
TR07-077
| 7th August 2007
__

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan#### Testing for Concise Representations

__
TR07-078
| 11th August 2007
__

Ran Raz, Iddo Tzameret#### Resolution over Linear Equations and Multilinear Proofs

__
TR07-079
| 11th August 2007
__

Emanuele Viola, Avi Wigderson#### One-way multi-party communication lower bound for pointer jumping with applications

__
TR07-080
| 7th August 2007
__

Chris Peikert, Brent Waters#### Lossy Trapdoor Functions and Their Applications

__
TR07-081
| 10th August 2007
__

Andrej Bogdanov, Emanuele Viola#### Pseudorandom bits for polynomials

__
TR07-082
| 27th July 2007
__

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou#### The Myth of the Folk Theorem

__
TR07-083
| 23rd August 2007
__

Artur Czumaj, Asaf Shapira, Christian Sohler#### Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs

__
TR07-084
| 4th September 2007
__

Brendan Juba, Madhu Sudan#### Universal Semantic Communication I

__
TR07-085
| 2nd September 2007
__

Ran Raz, Amir Yehudayoff#### Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

__
TR07-086
| 7th September 2007
__

Venkatesan Guruswami, James R. Lee, Alexander Razborov#### Almost Euclidean subspaces of $\ell_1^N$ via expander codes

__
TR07-087
| 11th July 2007
__

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao#### Arithmetizing classes around NC^1 and L

__
TR07-088
| 7th September 2007
__

Elad Hazan, C. Seshadhri#### Adaptive Algorithms for Online Decision Problems

Revisions: 1

__
TR07-089
| 13th September 2007
__

Parikshit Gopalan, Venkatesan Guruswami#### Deterministic Hardness Amplification via Local GMD Decoding

__
TR07-090
| 11th September 2007
__

Shachar Lovett#### Tight lower bounds for adaptive linearity tests

Revisions: 1
,
Comments: 1

__
TR07-091
| 10th September 2007
__

Martin Grohe#### Logic, Graphs, and Algorithms

__
TR07-092
| 10th July 2007
__

Piotr Berman, Bhaskar DasGupta#### Approximating the Online Set Multicover Problems Via Randomized Winnowing

__
TR07-093
| 27th July 2007
__

Andrei A. Bulatov#### The complexity of the counting constraint satisfaction problem

Revisions: 1

__
TR07-094
| 3rd August 2007
__

Christian Glaßer, Heinz Schmitz, Victor Selivanov#### Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

__
TR07-095
| 13th July 2007
__

Vikraman Arvind, Partha Mukhopadhyay#### The Ideal Membership Problem and Polynomial Identity Testing

Revisions: 2

__
TR07-096
| 8th October 2007
__

Lance Fortnow, Rahul Santhanam#### Infeasibility of Instance Compression and Succinct PCPs for NP

__
TR07-097
| 8th October 2007
__

Miklos Ajtai, Cynthia Dwork#### The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.

__
TR07-098
| 2nd October 2007
__

Tali Kaufman, Simon Litsyn, Ning Xie#### Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

__
TR07-099
| 30th September 2007
__

Dieter van Melkebeek#### A Survey of Lower Bounds for Satisfiability and Related Problems

__
TR07-100
| 25th September 2007
__

Alexander A. Sherstov#### The Pattern Matrix Method for Lower Bounds on Quantum Communication

__
TR07-101
| 10th September 2007
__

Patrick Briest, Martin Hoefer, Piotr Krysta#### Stackelberg Network Pricing Games

Revisions: 1

__
TR07-102
| 4th October 2007
__

Andrej Bogdanov, Muli Safra#### Hardness amplification for errorless heuristics

__
TR07-103
| 28th September 2007
__

Emanuele Viola#### Selected Results in Additive Combinatorics: An Exposition

__
TR07-104
| 15th September 2007
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### On the Advantage over Random for Maximum Acyclic Subgraph

__
TR07-105
| 21st September 2007
__

Jelani Nelson#### A Note on Set Cover Inapproximability Independent of Universe Size

Revisions: 1

__
TR07-106
| 10th September 2007
__

Yijia Chen, Martin Grohe, Magdalena Grüber#### On Parameterized Approximability

__
TR07-107
| 26th October 2007
__

Nathan Segerlind#### Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures

__
TR07-108
| 27th October 2007
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Local Global Tradeoffs in Metric Embeddings

__
TR07-109
| 7th October 2007
__

Venkatesan Guruswami, Atri Rudra#### Better Binary List-Decodable Codes via Multilevel Concatenation

__
TR07-110
| 24th October 2007
__

Beate Bollig#### The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function

__
TR07-111
| 1st November 2007
__

Tali Kaufman, Madhu Sudan#### Algebraic Property Testing: The Role of Invariance

__
TR07-112
| 25th September 2007
__

Alexander A. Sherstov#### Unbounded-Error Communication Complexity of Symmetric Functions

__
TR07-113
| 15th November 2007
__

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang#### Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

__
TR07-114
| 28th September 2007
__

Jakob Nordström#### A Simplified Way of Proving Trade-off Results for Resolution

__
TR07-115
| 19th November 2007
__

Or Meir#### Combinatorial Construction of Locally Testable Codes

__
TR07-116
| 25th September 2007
__

Alexander A. Sherstov#### Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

Comments: 1

__
TR07-117
| 8th November 2007
__

Edward Hirsch, Dmitry Itsykson#### An infinitely-often one-way function based on an average-case assumption

__
TR07-118
| 27th November 2007
__

Asaf Nachmias, Asaf Shapira#### Testing the Expansion of a Graph

__
TR07-119
| 5th December 2007
__

Piotr Berman, Bhaskar DasGupta, Marek Karpinski#### Approximating Transitive Reductions for Directed Networks

__
TR07-120
| 5th October 2007
__

Sharon Feldman, Guy Kortsarz, Zeev Nutov#### Improved approximation algorithms for directed Steiner forest

__
TR07-121
| 21st November 2007
__

Zeev Dvir, Amir Shpilka, Amir Yehudayoff#### Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

__
TR07-122
| 22nd November 2007
__

Zeev Dvir, Amir Shpilka#### Towards Dimension Expanders Over Finite Fields

__
TR07-123
| 21st November 2007
__

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky#### Inverse Conjecture for the Gowers norm is false

Revisions: 2

__
TR07-124
| 23rd November 2007
__

Nitin Saxena#### Diagonal Circuit Identity Testing and Lower Bounds

__
TR07-125
| 11th October 2007
__

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka#### The black-box query complexity of polynomial summation

__
TR07-126
| 5th November 2007
__

Nathan Segerlind#### On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs

__
TR07-127
| 22nd November 2007
__

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish#### Sound 3-query PCPPs are Long

__
TR07-128
| 10th November 2007
__

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio#### Testing Halfspaces

__
TR07-129
| 25th October 2007
__

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan#### Learning Random Monotone DNF

__
TR07-130
| 3rd December 2007
__

Ronen Shaltiel, Emanuele Viola#### Hardness amplification proofs require majority

__
TR07-131
| 16th November 2007
__

Satyen Kale#### Boosting and hard-core set constructions: a simplified approach

__
TR07-132
| 8th December 2007
__

Emanuele Viola#### The sum of d small-bias generators fools polynomials of degree d

__
TR07-133
| 20th November 2007
__

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan#### Trapdoors for Hard Lattices and New Cryptographic Constructions

__
TR07-134
| 14th December 2007
__

Jeff Kinne, Dieter van Melkebeek#### Space Hierarchy Results for Randomized and Other Semantic Models

Revisions: 1

__
TR07-135
| 26th December 2007
__

Paul Valiant, Paul Valiant#### Testing Symmetric Properties of Distributions

__
TR07-136
| 28th November 2007
__

Felix Brandt, Felix Fischer, Markus Holzer#### Equilibria of Graphical Games with Symmetries

__
TR07-137
| 6th November 2007
__

Yijia Chen, Jörg Flum, Moritz Müller#### Lower Bounds for Kernelizations

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>

Moti Yung, Yunlei Zhao

Knowledge extraction is a fundamental notion, modeling knowledge possession in a computational complexity sense. The notion provides a tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players. We define and

investigate the relative power of the notion of ``concurrent knowledge-extraction'' ...
more >>>

Jin-Yi Cai, Pinyan Lu

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This ... more >>>

Lance Fortnow, Rahul Santhanam

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

more >>>Rahul Santhanam

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

David P. Woodruff

For any odd integer q > 1, we improve the lower bound for general q-query locally decodable codes C: {0,1}^n -> {0,1}^m from m = Omega(n/log n)^{(q+1)/(q-1)} to m = Omega(n^{(q+1)/(q-1)})/log n. For example, for q = 3 we improve the previous bound from Omega(n^2/log^2 n) to Omega(n^2/log n). For ... more >>>

Jan Krajicek

We prove an exponential lower bound on the size of proofs

in the proof system operating with ordered binary decision diagrams

introduced by Atserias, Kolaitis and Vardi. In fact, the lower bound

applies to semantic derivations operating with sets defined by OBDDs.

We do not assume ...
more >>>

Philipp Weis, Neil Immerman

It is well-known that every first-order property on words is expressible

using at most three variables. The subclass of properties expressible with

only two variables is also quite interesting and well-studied. We prove

precise structure theorems that characterize the exact expressive power of

first-order logic with two variables on words. ...
more >>>

Nathan Segerlind

We demonstrate a family of propositional formulas in conjunctive normal form

so that a formula of size $N$ requires size $2^{\Omega(\sqrt[7]{N/logN})}$

to refute using the tree-like OBDD refutation system of

Atserias, Kolaitis and Vardi

with respect to all variable orderings.

All known symbolic quantifier elimination algorithms for satisfiability

generate ...
more >>>

Arist Kojevnikov

We continue a study initiated by Krajicek of

a Resolution-like proof system working with clauses of linear

inequalities, R(CP). For all proof systems of this kind

Krajicek proved an exponential lower bound that depends

on the maximal absolute value of coefficients in the given proof and

the maximal clause width.

Bodo Manthey

A cycle cover of a graph is a set of cycles such that every vertex is

part of exactly one cycle. An L-cycle cover is a cycle cover in which

the length of every cycle is in the set L. The weight of a cycle cover

of an edge-weighted graph ...
more >>>

Shachar Lovett, Sasha Sodin

It is well known that $\R^N$ has subspaces of dimension

proportional to $N$ on which the $\ell_1$ norm is equivalent to the

$\ell_2$ norm; however, no explicit constructions are known.

Extending earlier work by Artstein--Avidan and Milman, we prove that

such a subspace can be generated using $O(N)$ random bits.

Andris Ambainis, Joseph Emerson

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t.

We then show that an ... more >>>

Amit Chakrabarti

We consider the $k$-layer pointer jumping problem in the one-way

multi-party number-on-the-forehead communication model. In this problem,

the input is a layered directed graph with each vertex having outdegree

$1$, shared amongst $k$ players: Player~$i$ knows all layers {\em

except} the $i$th. The players must communicate, in the order

$1,2,\ldots,k$, ...
more >>>

Oded Goldreich, Or Sheffet

We initiate a general study of the randomness complexity of

property testing, aimed at reducing the randomness complexity of

testers without (significantly) increasing their query complexity.

One concrete motovation for this study is provided by the

observation that the product of the randomness and query complexity

of a tester determine ...
more >>>

Prasad Raghavendra

Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors.

In a recent breakthrough, Yekhanin designed $3$-query LDCs that hugely improve over earlier constructions. Specifically, for a Mersenne prime $p ... more >>>

Ashish Rastogi, Richard Cole

This paper considers the tradeoff between divisibility and the hardness of approximating

equilibrium prices. Tight bounds are obtained for smooth Fisher markets that obey a relaxed

weak gross substitutes property (WGS). A smooth market is one in which small changes in

prices cause only proportionately small changes ...
more >>>

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

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: Where does the implication [can(f) \le_m can(g) => f \le_s ... more >>>

Jin-Yi Cai, Pinyan Lu

We give a classification of block-wise symmetric signatures

in the theory of matchgate computations. The main proof technique

is matchgate identities, a.k.a. useful Grassmann-Pl\"{u}cker

identities.

Jin-Yi Cai, Pinyan Lu

Valiant's theory of holographic algorithms is a novel methodology

to achieve exponential speed-ups in computation. A fundamental

parameter in holographic algorithms is the dimension of the linear basis

vectors.

We completely resolve the problem of the power of higher dimensional

bases. We prove that 2-dimensional bases are universal for

holographic ...
more >>>

Brett Hemenway, Rafail Ostrovsky

In this paper, we introduce the notion of a Public-Key Encryption (PKE) Scheme that is also a Locally-Decodable Error-Correcting Code.

In particular, our construction simultaneously satisfies all of the following properties:

\begin{itemize}

\item

Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption

...
more >>>

Rafail Ostrovsky, William Skeith

In cryptography, there has been tremendous success in building

primitives out of homomorphic semantically-secure encryption

schemes, using homomorphic properties in a black-box way. A few

notable examples of such primitives include items like private

information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general

methodology for ...
more >>>

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

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

Laszlo Egri, Benoit Larose, Pascal Tesson

We introduce symmetric Datalog, a syntactic restriction of linear

Datalog and show that its expressive power is exactly that of

restricted symmetric monotone Krom SNP. The deep result of

Reingold on the complexity of undirected

connectivity suffices to show that symmetric Datalog queries can be

evaluated in logarithmic space. We ...
more >>>

Benoit Larose, Pascal Tesson, Pascal Tesson

We present algebraic conditions on constraint languages \Gamma

that ensure the hardness of the constraint satisfaction problem

CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL.

These criteria also give non-expressibility results for various

restrictions of Datalog. Furthermore, we show that if

CSP(\Gamma) is not first-order definable then it ...
more >>>

Dana Moshkovitz, Ran Raz

We show a construction of a PCP with both sub-constant error and

almost-linear size. Specifically, for some constant alpha in (0,1),

we construct a PCP verifier for checking satisfiability of

Boolean formulas that on input of size n uses log n + O((log

n)^{1-alpha}) random bits to query a constant ...
more >>>

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject.

We consider the approximation ability of randomized search for the class of ...
more >>>

Daniel Sawitzki

Implicit algorithms work on their input's characteristic functions and should solve problems heuristically by as few and as efficient functional operations as possible. Together with an appropriate data structure to represent the characteristic functions they yield heuristics which are successfully applied in numerous areas. It is known that implicit algorithms ... more >>>

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou

studied in [Gopalan et al., ICALP2006] connectivity properties of the

solution-space of Boolean formulas, and investigated complexity issues

on connectivity problems in Schaefer's framework [Schaefer, STOC1978].

A set S of logical relations is Schaefer if all relations in ...
more >>>

Kai-Min Chung, Omer Reingold, Salil Vadhan

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace ... more >>>

Yael Tauman Kalai, Ran Raz

An interactive-PCP (say, for the membership $x \in L$) is a

proof that can be verified by reading only one of its bits, with the

help of a very short interactive-proof.

We show that for membership in some languages $L$, there are

interactive-PCPs that are significantly shorter than the known

more >>>

Pavel Pudlak

We define propositional quantum Frege proof systems and compare it

with classical Frege proof systems.

Michael Navon, Alex Samorodnitsky

We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, ... more >>>

Anup Rao

A construction of Bourgain gave the first 2-source

extractor to break the min-entropy rate 1/2 barrier. In this note,

we write an exposition of his result, giving a high level way to view

his extractor construction.

We also include a proof of a generalization of Vazirani's XOR lemma

that seems ...
more >>>

Mark Braverman, Raghav Kulkarni, Sambuddha Roy

We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2^k, for constant k. ... more >>>

Ryan Williams

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>>

Leonid Gurvits

We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets.

Our main result is a poly-time algorithm which approximates $V(K_1,...,K_n)$ with multiplicative error $e^n$ and

with better rates if the affine dimensions of most of the sets $K_i$ are small.\\

Our approach is ...
more >>>

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme ... more >>>

Bodo Manthey, Till Tantau

Binary search trees are a fundamental data structure and their height

plays a key role in the analysis of divide-and-conquer algorithms like

quicksort. Their worst-case height is linear; their average height,

whose exact value is one of the best-studied problems in average-case

complexity, is logarithmic. We analyze their smoothed height ...
more >>>

Kiran Kedlaya, Sergey Yekhanin

A k-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 k bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The major ... more >>>

Nicola Galesi, Massimo Lauria

We introduce an algebraic proof system Pcrk, which combines together {\em Polynomial Calculus} (Pc) and {\em $k$-DNF Resolution} (Resk).

This is a natural generalization to Resk of the well-known {\em Polynomial Calculus with Resolution} (Pcr) system which combines together Pc and Resolution.

We study the complexity of proofs in such ... more >>>

Zohar Karnin, Amir Shpilka

In this paper we consider the problem of determining whether an

unknown arithmetic circuit, for which we have oracle access,

computes the identically zero polynomial. Our focus is on depth-3

circuits with a bounded top fan-in. We obtain the following

results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>

Uriel Feige, Guy Kindler, Ryan O'Donnell

Motivated by the study of Parallel Repetition and also by the Unique

Games Conjecture, we investigate the value of the ``Odd Cycle Games''

under parallel repetition. Using tools from discrete harmonic

analysis, we show that after $d$ rounds on the cycle of length $m$,

the value of the game is ...
more >>>

Philipp Hertel

The complexity of the Black-White Pebbling Game has remained an open problem for 30 years. It was devised to capture the power of non-deterministic space bounded computation. Since then it has been continuously studied and applied to problems in diverse areas of computer science including VLSI design and more recently ... more >>>

Heribert Vollmer

We study the complexity of the following algorithmic problem: Given a Boolean function $f$ and a finite set of Boolean functions $B$, decide if there is a circuit with basis $B$ that computes $f$. We show that if both $f$ and all functions in $B$ are given by their truth-table, ... more >>>

Philipp Hertel

Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and diagnosis problems. The main reason for the success is due to highly optimized algorithms for SAT based on resolution. The most successful of these ... more >>>

Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum

Program checking, program self-correcting and program self-testing

were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in

the mid eighties as a new way to gain confidence in software, by

considering program correctness on an input by input basis rather than

full program verification. Work in ...
more >>>

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

The Earth Mover Distance (EMD) between two equal-size sets

of points in R^d is defined to be the minimum cost of a

bipartite matching between the two pointsets. It is a natural metric

for comparing sets of features, and as such, it has received

significant interest in computer vision. Motivated ...
more >>>

Beate Bollig, Niko Range, Ingo Wegener

Ordered binary decision diagrams (OBDDs) are nowadays the most common

dynamic data structure or representation type for Boolean functions.

Among the many areas of application are verification, model checking,

computer aided design, relational algebra, and symbolic graph algorithms.

Although many even exponential lower bounds on the OBDD size of Boolean ...
more >>>

Arkadev Chattopadhyay

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). ... more >>>

Pilar Albert, Elvira Mayordomo, Philippe Moser

In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol ... more >>>

Li Chen, Bin Fu

It is well known that every finite Abelian group $G$ can be

represented as a product of cyclic groups: $G=G_1\times

G_2\times\cdots G_t$, where each $G_i$ is a cyclic group of size

$p^j$ for some prime $p$ and integer $j\ge 1$. If $a_i$ is the

generator of the cyclic group of ...
more >>>

Jens Groth, Amit Sahai

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as ... more >>>

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

We study a model of graph related formulae that we call

the \emph{Constraint-Graph model}. A

constraint-graph is a labeled multi-graph (a graph where loops

and parallel edges are allowed), where each edge $e$ is labeled

by a distinct Boolean variable and every vertex is

associate with a Boolean function over ...
more >>>

Oliver Kullmann

We consider the next step from boolean conjunctive normal forms to

arbitrary constraint satisfaction problems (with arbitrary constraints), namely "generalised clause-sets" (or "sets of no-goods"), which allow negative literals "v <> e" for variables v and values e --- this level of generality appears to be the right level for ...
more >>>

Zeev Dvir, Ariel Gabizon, Avi Wigderson

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

Oded Goldreich

Motivated by a recent study of Zimand (22nd CCC, 2007),

we consider the average-case complexity of property testing

(focusing, for clarity, on testing properties of Boolean strings).

We make two observations:

1) In the context of average-case analysis with respect to

the uniform distribution (on all strings of ...
more >>>

Dmytro Gavinsky

We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (two-way) model.

more >>>Shankar Kalyanaraman, Chris Umans

We study multiplayer games in which the participants have access to

only limited randomness. This constrains both the algorithms used to

compute equilibria (they should use little or no randomness) as well

as the mixed strategies that the participants are capable of playing

(these should be sparse). We frame algorithmic ...
more >>>

Tali Kaufman, Madhu Sudan

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

Or Meir

Given linear two codes R,C, their tensor product $R \otimes C$

consists of all matrices whose rows are codewords of R and whose

columns are codewords of C. The product $R \otimes C$ is said to

be robust if for every matrix M that is far from $R \otimes C$

more >>>

Oded Goldreich, Or Meir

Given two codes R,C, their tensor product $R \otimes C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R \otimes C$ is said to be robust if for every matrix M that is far from $R \otimes C$ it ... more >>>

Tomas Feder, Carlos Subi

We conjecture that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$

such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the

$d$-dimensional hypercube. We prove this conjecture in the case where there are

two dimensions ...
more >>>

Rahul Jain, Hartmut Klauck, Ashwin Nayak

A basic question in complexity theory is whether the computational

resources required for solving k independent instances of the same

problem scale as k times the resources required for one instance.

We investigate this question in various models of classical

communication complexity.

We define a new measure, the subdistribution bound, ... more >>>

Jonathan Katz

We show that if a language $L$ has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then $\bar L \in MA$. Assuming the polynomial hierarchy does not collapse, this means, in particular, that $NP$-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box ... more >>>

Maciej Liskiewicz, Christian Hundt

The problem of image matching is to find for two given digital images $A$ and $B$

an admissible transformation that converts image $A$ as close as possible to $B$.

This problem becomes hard if the space of admissible transformations is too complex.

Consequently, in many real applications, like the ones ...
more >>>

Paul Spirakis, haralampos tsaknakis

In this paper we propose a methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and, based on that, we provide a polynomial time algorithm that computes $\frac{1}{3} + \frac{1}{p(n)} $ -approximate equilibria, where $p(n)$ is a polynomial controlled by our algorithm and proportional to its running time. The ... more >>>

Thomas Thierauf, Fabian Wagner

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class AC^1.

In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to ... more >>>

Ronen Shaltiel, Chris Umans

In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the {\em uniform setting}, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved ... more >>>

Nir Ailon, Edo Liberty

\begin{abstract}

The Fast Johnson-Lindenstrauss Transform was recently discovered by

Ailon and Chazelle as a technique for performing fast dimension

reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d,

k^3\})$, where $k$ is the target lower dimension. This beats the

naive $O(dk)$ achieved by multiplying by random dense matrices, as

noticed ...
more >>>

Jacobo Toran

We show that several reducibility notions coincide when applied to the

Graph Isomorphism (GI) problem. In particular we show that if a set is

many-one logspace reducible to GI, then it is in fact many-one AC^0

reducible to GI. For the case of Turing reducibilities we show that ...
more >>>

Alexander A. Sherstov

We solve an open problem of Kushilevitz and Nisan

(1997) in communication complexity. Let $R_{eps}(f)$

and $D^{mu}_{eps}(f)$ denote the randomized and

$mu$-distributional communication complexities of

f, respectively ($eps$ a small constant). Yao's

well-known Minimax Principle states that

R_{eps}(f) = max_{mu} { D^{mu}_{eps}(f) }.

Kushilevitz and Nisan (1997) ask whether ...
more >>>

Parikshit Gopalan, Subhash Khot, Rishi Saket

We study the polynomial reconstruction problem for low-degree

multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values $f(x)$ for each of these points, with the promise that there is a polynomial over GF[2] of ...
more >>>

Dmytro Gavinsky, Pavel Pudlak

We give the first exponential separation between quantum and

classical multi-party

communication complexity in the (non-interactive) one-way and

simultaneous message

passing settings.

For every k, we demonstrate a relational communication problem

between k parties

that can be solved exactly by a quantum simultaneous message passing

protocol of

cost ...
more >>>

Shachar Lovett

We give an explicit construction of pseudorandom

generators against low degree polynomials over finite fields. We

show that the sum of $2^d$ small-biased generators with error

$\epsilon^{2^{O(d)}}$ is a pseudorandom generator against degree $d$

polynomials with error $\epsilon$. This gives a generator with seed

length $2^{O(d)} \log{(n/\epsilon)}$. Our construction follows ...
more >>>

Satyen Kale, C. Seshadhri

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>

Ran Raz, Iddo Tzameret

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. ... more >>>

Emanuele Viola, Avi Wigderson

In this paper we study the one-way multi-party communication model,

in which every party speaks exactly once in its turn. For every

fixed $k$, we prove a tight lower bound of

$\Omega{n^{1/(k-1)}}$ on the probabilistic communication

complexity of pointer jumping in a $k$-layered tree, where the

pointers of the $i$-th ...
more >>>

Chris Peikert, Brent Waters

We propose a new general primitive called lossy trapdoor

functions (lossy TDFs), and realize it under a variety of different

number theoretic assumptions, including hardness of the decisional

Diffie-Hellman (DDH) problem and the worst-case hardness of

standard lattice problems.

Using lossy TDFs, we develop a new approach for constructing ... more >>>

Andrej Bogdanov, Emanuele Viola

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$:

\begin{enumerate}

\item a ...
more >>>

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou

The folk theorem suggests that finding Nash Equilibria

in repeated games should be easier than in one-shot games. In

contrast, we show that the problem of finding any (epsilon) Nash

equilibrium for a three-player infinitely-repeated game is

computationally intractable (even when all payoffs are in

{-1,0,-1}), unless all of PPAD ...
more >>>

Artur Czumaj, Asaf Shapira, Christian Sohler

We study property testing in the model of bounded degree graphs. It

is well known that in this model many graph properties cannot be

tested with a constant number of queries and it seems reasonable to

conjecture that only few are testable with o(sqrt{n}) queries.

Therefore in this paper ...
more >>>

Brendan Juba, Madhu Sudan

Is it possible for two intelligent beings to communicate meaningfully, without any common language or background? This question has interest on its own, but is especially relevant in the context of modern computational infrastructures where an increase in the diversity of computers is making the task of inter-computer interaction increasingly ... more >>>

Ran Raz, Amir Yehudayoff

We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,...,xn}:

1. Noise-resistant. A syntactically multilinear ... more >>>

Venkatesan Guruswami, James R. Lee, Alexander Razborov

We give an explicit (in particular, deterministic polynomial time)

construction of subspaces $X

\subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,

$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$

If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits

and ...
more >>>

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

The parallel complexity class NC^1 has many equivalent models such as

polynomial size formulae and bounded width branching

programs. Caussinus et al. \cite{CMTV} considered arithmetizations of

two of these classes, #NC^1 and #BWBP. We further this study to

include arithmetization of other classes. In particular, we show that

counting paths ...
more >>>

Elad Hazan, C. Seshadhri

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>>

Parikshit Gopalan, Venkatesan Guruswami

We study the average-case hardness of the class NP against

deterministic polynomial time algorithms. We prove that there exists

some constant $\mu > 0$ such that if there is some language in NP

for which no deterministic polynomial time algorithm can decide L

correctly on a $1- (log n)^{-\mu}$ fraction ...
more >>>

Shachar Lovett

Linearity tests are randomized algorithms which have oracle access to the truth table of some function $f$,

which are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by Blum, Luby and Rubenfeld in \cite{BLR93}, and were later used in the ...
more >>>

Martin Grohe

Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic ... more >>>

Piotr Berman, Bhaskar DasGupta

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family SS of subsets of V with a positive real cost for every S\in SS, and a ``coverage factor'' (positive integer) k. A subset \{i_0,i_1,\ldots\ \subseteq V of ... more >>>

Andrei A. Bulatov

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite

relational structure H can be expressed as follows: given a

relational structure G over the same vocabulary,

determine the number of homomorphisms from G to H.

In this paper we characterize relational structures H for which

#CSP(H) can be solved in ...
more >>>

Christian Glaßer, Heinz Schmitz, Victor Selivanov

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results:

1. The classes of ... more >>>

Vikraman Arvind, Partha Mukhopadhyay

\begin{abstract}

Given a monomial ideal $I=\angle{m_1,m_2,\cdots,m_k}$ where $m_i$

are monomials and a polynomial $f$ as an arithmetic circuit the

\emph{Ideal Membership Problem } is to test if $f\in I$. We study

this problem and show the following results.

\begin{itemize}

\item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a

more >>>

Lance Fortnow, Rahul Santhanam

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there

is a polynomial-time computable function $f$ and a set $A$ such that

for each instance ...
more >>>

Miklos Ajtai, Cynthia Dwork

We describe a public-key cryptosystem with worst-case/average case

equivalence. The cryptosystem has an amortized plaintext to

ciphertext expansion of $O(n)$, relies on the hardness of the

$\tilde O(n^2)$-unique shortest vector problem for lattices, and

requires a public key of size at most $O(n^4)$ bits. The new

cryptosystem generalizes a conceptually ...
more >>>

Tali Kaufman, Simon Litsyn, Ning Xie

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>>

Dieter van Melkebeek

Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time, logarithmic-space algorithm for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by ... more >>>

Alexander A. Sherstov

In a breakthrough result, Razborov (2003) gave optimal

lower bounds on the communication complexity of every function f

of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in

the bounded-error quantum model with and without prior entanglement.

This was proved by the _multidimensional_ discrepancy method. We

give an entirely ...
more >>>

Patrick Briest, Martin Hoefer, Piotr Krysta

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m pricable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization ... more >>>

Andrej Bogdanov, Muli Safra

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol "I don't know." A central question in average-case complexity is whether every distributional decision problem in NP has an errorless heuristic scheme: This is an algorithm that, for every δ > ... more >>>

Emanuele Viola

We give a self-contained exposition of selected results in additive

combinatorics over the group {0,1}^n. In particular, we prove the

celebrated theorems known as the Balog-Szemeredi-Gowers theorem ('94 and '98) and

the

Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result

by Samorodnitsky ('07) that linear transformations are efficiently ...
more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains (1/2 + delta) fraction of all edges, our algorithm finds an acyclic subgraph with (1/2 + Omega(delta/ log n)) fraction of all edges.

more >>>Jelani Nelson

In the set cover problem we are given a collection of $m$ sets whose union covers $[n] = \{1,\ldots,n\}$ and must find a minimum-sized subcollection whose union still covers $[n]$. We investigate the approximability of set cover by an approximation ratio that depends only on $m$ and observe that, for ... more >>>

Yijia Chen, Martin Grohe, Magdalena Grüber

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability.

The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.

Nathan Segerlind

The matrix cuts of Lov{\'{a}}sz and Schrijver are methods for tightening linear relaxations of zero-one programs by the addition of new linear inequalities. We address the question of how many new inequalities are necessary to approximate certain combinatorial problems with strong guarantees, and to solve certain instances of Boolean satisfiability.

... more >>>Moses Charikar, Konstantin Makarychev, Yury Makarychev

Suppose that every k points in a n point metric space X are D-distortion embeddable into l_1. We give upper and lower bounds on the distortion required to embed the entire space X into l_1. This is a natural mathematical question and is also motivated by the study of relaxations ... more >>>

Venkatesan Guruswami, Atri Rudra

We give a polynomial time construction of binary codes with the best

currently known trade-off between rate and error-correction

radius. Specifically, we obtain linear codes over fixed alphabets

that can be list decoded in polynomial time up to the so called

Blokh-Zyablov bound. Our work ...
more >>>

Beate Bollig

Branching programs are computation models

measuring the space of (Turing machine) computations.

Read-once branching programs (BP1s) are the

most general model where each graph-theoretical path is the computation

path for some input. Exponential lower bounds on the size of read-once

branching programs are known since a long time. Nevertheless, there ...
more >>>

Tali Kaufman, Madhu Sudan

We argue that the symmetries of a property being tested play a

central role in property testing. We support this assertion in the

context of algebraic functions, by examining properties of functions

mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$.

We consider $\F$-linear properties that ...
more >>>

Alexander A. Sherstov

The sign-rank of a real matrix M is the least rank

of a matrix R in which every entry has the same sign as the

corresponding entry of M. We determine the sign-rank of every

matrix of the form M=[ D(|x AND y|) ]_{x,y}, where

D:{0,1,...,n}->{-1,+1} is given and ...
more >>>

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

In the undirected Edge-Disjoint Paths problem with Congestion

(EDPwC), we are given an undirected graph with $V$ nodes, a set of

terminal pairs and an integer $c$. The objective is to route as many

terminal pairs as possible, subject to the constraint that at most

$c$ demands can be routed ...
more >>>

Jakob Nordström

We present a greatly simplified proof of the length-space

trade-off result for resolution in Hertel and Pitassi (2007), and

also prove a couple of other theorems in the same vein. We point

out two important ingredients needed for our proofs to work, and

discuss possible conclusions to be drawn regarding ...
more >>>

Or Meir

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>>

Alexander A. Sherstov

Let A_1,...,A_n be events in a probability space. The

approximate inclusion-exclusion problem, due to Linial and

Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given

Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve

this problem optimally for each k. We study the following more

general question: ...
more >>>

Edward Hirsch, Dmitry Itsykson

We assume the existence of a function f that is computable in polynomial time but its inverse function is not computable in randomized average-case polynomial time. The cryptographic setting is, however, different: even for a weak one-way function, every possible adversary should fail on a polynomial fraction of inputs. Nevertheless, ... more >>>

Asaf Nachmias, Asaf Shapira

We study the problem of testing the expansion of

graphs with bounded degree d in sublinear time. A graph is said to

be an \alpha-expander if every vertex set U \subset V of size at

most |V|/2 has a neighborhood of size at least \alpha|U|.

We show that the algorithm ... more >>>

Piotr Berman, Bhaskar DasGupta, Marek Karpinski

We consider <i>minimum equivalent digraph</i> (<i>directed network</i>) problem (also known as the <i>strong transitive reduction</i>), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>>

Sharon Feldman, Guy Kortsarz, Zeev Nutov

We consider the k-Directed Steiner Forest} (k-dsf) problem:

given a directed graph G=(V,E) with edge costs, a collection D subseteq V \times V

of ordered node pairs, and an integer k leq |D|, find a minimum cost subgraph

H of G

that contains an st-path for (at least) k ...
more >>>

Zeev Dvir, Amir Shpilka, Amir Yehudayoff

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x_1,...,x_m) that cannot be computed by a depth d arithmetic circuit of small size then there exists ... more >>>

Zeev Dvir, Amir Shpilka

In this paper we study the problem of explicitly constructing a

{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$

be the $n$ dimensional linear space over the field $\mathbb{F}$.

Find a small (ideally constant) set of linear transformations from

$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear

more >>>

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky

Let $p$ be a fixed prime number, and $N$ be a large integer.

The 'Inverse Conjecture for the Gowers norm' states that if the "$d$-th Gowers norm" of a function $f:\F_p^N \to \F_p$ is non-negligible, that is larger than a constant independent of $N$, then $f$ can be non-trivially ...
more >>>

Nitin Saxena

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-$3$ circuit $C(\arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only ... more >>>

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can

efficiently construct (using \emph{arithmetization}) a low-degree

polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all

points in the Boolean cube $\{0,1\}^n$; the constructed polynomial

$p$ can be interpreted as a polynomial over an arbitrary field

$\mathbb{F}$. The problem ...
more >>>

Nathan Segerlind

We show that tree-like OBDD proofs of unsatisfiability require an exponential increase ($s \mapsto 2^{s^{\Omega(1)}}$) in proof size to simulate unrestricted resolution, and that unrestricted OBDD proofs of unsatisfiability require an almost-exponential increase ($s \mapsto 2^{ 2^{\left( \log s \right)^{\Omega(1)}}}$) in proof size to simulate $\Res{O(\log n)}$. The ``OBDD proof ... more >>>

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

We initiate the study of the tradeoff between the {\em length} of a

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
more >>>

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

We give an algorithm that with high probability properly learns random monotone t(n)-term

DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ...
more >>>

Ronen Shaltiel, Emanuele Viola

Hardness amplification is the fundamental task of

converting a $\delta$-hard function $f : {0,1}^n ->

{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,

where $f$ is $\gamma$-hard if small circuits fail to

compute $f$ on at least a $\gamma$ fraction of the

inputs. Typically, $\eps,\delta$ are small (and

$\delta=2^{-k}$ captures the case ...
more >>>

Satyen Kale

We revisit the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. We present a boosting algorithm with a certain smoothness property that is necessary for hard-core set constructions: the distributions it generates do not put too much weight on any single example. We then use ... more >>>

Emanuele Viola

We prove that the sum of $d$ small-bias generators $L

: \F^s \to \F^n$ fools degree-$d$ polynomials in $n$

variables over a prime field $\F$, for any fixed

degree $d$ and field $\F$, including $\F = \F_2 =

{0,1}$.

Our result improves on both the work by Bogdanov and

Viola ...
more >>>

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

We show how to construct a variety of ``trapdoor'' cryptographic tools

assuming the worst-case hardness of standard lattice problems (such as

approximating the shortest nonzero vector to within small factors).

The applications include trapdoor functions with \emph{preimage

sampling}, simple and efficient ``hash-and-sign'' digital signature

schemes, universally composable oblivious transfer, ...
more >>>

Jeff Kinne, Dieter van Melkebeek

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following.

Let <i>s</i>(<i>n</i>) ... more >>>

Paul Valiant, Paul Valiant

We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and

general enough that ``a property is testable if and only if the

Canonical Tester tests it''. We construct a Canonical Tester

for the class of symmetric properties of one or two

more >>>

Felix Brandt, Felix Fischer, Markus Holzer

We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>>

Yijia Chen, Jörg Flum, Moritz Müller

Among others, refining the methods of [Fortnow and Santhanam, ECCC Report TR07-096] we improve a result of this paper and show for any parameterized problem with a ``linear weak OR'' and with NP-hard underlying classical problem that there is no polynomial reduction from the problem to itself that assigns to ... more >>>