All reports in year 2004:

__
TR04-001
| 11th December 2003
__

Lance Fortnow, Russell Impagliazzo, Chris Umans#### On the complexity of succinct zero-sum games

__
TR04-002
| 8th January 2004
__

Troy Lee, Dieter van Melkebeek, Harry Buhrman#### Language Compression and Pseudorandom Generators

__
TR04-003
| 22nd December 2003
__

Pascal Koiran#### Valiant's model and the cost of computing integers

__
TR04-004
| 13th January 2004
__

Ramamohan Paturi, Pavel Pudlak#### Circuit lower bounds and linear codes

__
TR04-005
| 19th January 2004
__

Stasys Jukna#### On Graph Complexity

Revisions: 1
,
Comments: 1

__
TR04-006
| 6th January 2004
__

Günter Hotz#### A remark on nondecidabilities of the initial value problem of ODEs

__
TR04-007
| 13th January 2004
__

Alan L. Selman, Samik Sengupta#### Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy

Revisions: 1
,
Comments: 1

__
TR04-008
| 27th November 2003
__

Vikraman Arvind, Jacobo Toran#### Solvable Group Isomorphism is (almost) in NP\cap coNP

__
TR04-009
| 22nd January 2004
__

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda#### Randomly coloring constant degree graphs

__
TR04-010
| 26th January 2004
__

Michal Parnas, Dana Ron, Ronitt Rubinfeld#### Tolerant Property Testing and Distance Approximation

__
TR04-011
| 16th January 2004
__

Christian Glaßer#### Counting with Counterfree Automata

__
TR04-012
| 19th December 2003
__

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore#### The Resolution Complexity of Random Graph $k$-Colorability

__
TR04-013
| 10th February 2004
__

Oded Goldreich, Dana Ron#### On Estimating the Average Degree of a Graph.

__
TR04-014
| 26th November 2003
__

Chris Pollett#### Languages to diagonalize against advice classes

__
TR04-015
| 24th February 2004
__

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet#### Enumerations of the Kolmogorov Function

__
TR04-016
| 3rd March 2004
__

Michael Alekhnovich, Eli Ben-Sasson#### Linear Upper Bounds for Random Walk on Small Density Random 3CNFs

__
TR04-017
| 22nd February 2004
__

Evgeny Dantsin, Alexander Wolpert#### Derandomization of Schuler's Algorithm for SAT

__
TR04-018
| 24th January 2004
__

Jan Krajicek#### Diagonalization in proof complexity

__
TR04-019
| 15th January 2004
__

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta#### Properties of NP-Complete Sets

__
TR04-020
| 8th March 2004
__

Emanuele Viola#### The Complexity of Constructing Pseudorandom Generators from Hard Functions

__
TR04-021
| 23rd March 2004
__

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan#### Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

__
TR04-022
| 31st March 2004
__

Nayantara Bhatnagar, Parikshit Gopalan#### The Degree of Threshold Mod 6 and Diophantine Equations

__
TR04-023
| 21st January 2004
__

Yaoyun Shi#### Quantum and Classical Tradeoffs

__
TR04-024
| 26th March 2004
__

Thomas Thierauf, Thanh Minh Hoang#### On Closure Properties of GapL

Revisions: 1
,
Comments: 1

__
TR04-025
| 24th January 2004
__

John Hitchcock, A. Pavan, Vinodchandran Variyam#### Partial Bi-Immunity and NP-Completeness

__
TR04-026
| 17th February 2004
__

Scott Aaronson#### Limitations of Quantum Advice and One-Way Communication

__
TR04-027
| 20th February 2004
__

Henning Fernau#### Parametric Duality: Kernel Sizes and Algorithmics

__
TR04-028
| 19th March 2004
__

Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker#### Aggregates with Component Size One Characterize Polynomial Space

__
TR04-029
| 7th April 2004
__

John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo#### Scaled dimension and the Kolmogorov complexity of Turing hard sets

__
TR04-030
| 9th March 2004
__

Nikolay Vereshchagin#### Kolmogorov complexity of enumerating finite sets

__
TR04-031
| 22nd March 2004
__

Troy Lee, Andrei Romashchenko#### On Polynomially Time Bounded Symmetry of Information

__
TR04-032
| 5th February 2004
__

Ryan Williams#### A new algorithm for optimal constraint satisfaction and its implications

__
TR04-033
| 23rd January 2004
__

Michael Schmitt#### On the sample complexity of learning for networks of spiking neurons with nonlinear synaptic interactions

__
TR04-034
| 12th April 2004
__

April Rasala Lehman, Eric Lehman#### Network Coding: Does the Model Need Tuning?

__
TR04-035
| 10th April 2004
__

Scott Contini, Ernie Croot, Igor E. Shparlinski#### Complexity of Inverting the Euler Function

__
TR04-036
| 27th March 2004
__

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis#### Exponential Separation of Quantum and Classical One-Way Communication Complexity

__
TR04-037
| 14th April 2004
__

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner#### Generation Problems

__
TR04-038
| 27th April 2004
__

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann#### A Polynomial Time Learner for a Subclass of Regular Patterns

__
TR04-039
| 21st April 2004
__

Andrzej Lingas, Martin Wahlén#### On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems

__
TR04-040
| 4th May 2004
__

Venkatesan Guruswami, Alexander Vardy#### Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

__
TR04-041
| 18th May 2004
__

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson#### Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

__
TR04-042
| 21st May 2004
__

Ran Raz#### Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$

__
TR04-043
| 20th May 2004
__

Luca Trevisan#### Some Applications of Coding Theory in Computational Complexity

__
TR04-044
| 1st June 2004
__

Eric Allender, Harry Buhrman, Michal Koucky#### What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

__
TR04-045
| 15th April 2004
__

Hartmut Klauck, Robert Spalek, Ronald de Wolf#### Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

__
TR04-046
| 4th June 2004
__

Eli Ben-Sasson, Madhu Sudan#### Robust Locally Testable Codes and Products of Codes

__
TR04-047
| 22nd April 2004
__

Xiaoyang Gu#### A note on dimensions of polynomial size circuits

__
TR04-048
| 21st April 2004
__

André Lanka, Andreas Goerdt#### An approximation hardness result for bipartite Clique

__
TR04-049
| 15th June 2004
__

Piotr Berman, Marek Karpinski, Yakov Nekrich#### Optimal Trade-Off for Merkle Tree Traversal

__
TR04-050
| 13th June 2004
__

Michelle Effros, Leonard Schulman#### Deterministic clustering with data nets

__
TR04-051
| 10th June 2004
__

Zdenek Dvorák, Daniel Král, Ondrej Pangrác#### Locally consistent constraint satisfaction problems

__
TR04-052
| 14th June 2004
__

Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld#### Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

__
TR04-053
| 17th June 2004
__

A. Pavan, Vinodchandran Variyam#### Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

__
TR04-054
| 5th June 2004
__

Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin#### Non-reducible descriptions for conditional Kolmogorov complexity

__
TR04-055
| 27th May 2004
__

Kousha Etessami, Andreas Lochbihler#### The computational complexity of Evolutionarily Stable Strategies

__
TR04-056
| 1st July 2004
__

Vinodchandran Variyam#### A note on the circuit complexity of PP

__
TR04-057
| 16th May 2004
__

Monica del Pilar Canales Chacon, Michael Johannes Vielhaber#### Structural and Computational Complexity of Isometries and their Shift Commutators

__
TR04-058
| 28th May 2004
__

John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan#### Identifying Clusters from Positive Data

__
TR04-059
| 21st June 2004
__

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler#### Randomized Quicksort and the Entropy of the Random Number Generator

__
TR04-060
| 22nd July 2004
__

Eli Ben-Sasson, Madhu Sudan#### Simple PCPs with Poly-log Rate and Query Complexity

__
TR04-061
| 30th June 2004
__

Scott Aaronson#### The Complexity of Agreement

__
TR04-062
| 28th July 2004
__

Stasys Jukna#### A note on the P versus NP intersected with co-NP question in communication complexity

Revisions: 1
,
Comments: 1

__
TR04-063
| 23rd July 2004
__

Yehuda Lindell, Benny Pinkas#### A Proof of Yao's Protocol for Secure Two-Party Computation

Revisions: 1

__
TR04-064
| 25th June 2004
__

Piotr Faliszewski#### Exponential time reductions and sparse languages in NEXP

__
TR04-065
| 28th July 2004
__

Luca Trevisan#### Inapproximability of Combinatorial Optimization Problems

Revisions: 1

__
TR04-066
| 6th July 2004
__

Tomoyuki Yamakami, Toshio Suzuki#### Resource Bounded Immunity and Simplicity

__
TR04-067
| 20th July 2004
__

hadi salmasian, ravindran kannan, Santosh Vempala#### The Spectral Method for Mixture Models

__
TR04-068
| 13th August 2004
__

Nir Ailon, Bernard Chazelle#### Information Theory in Property Testing and Monotonicity Testing in Higher Dimension

__
TR04-069
| 13th August 2004
__

Eran Rom, Amnon Ta-Shma#### Improving the alphabet size in high noise, almost optimal rate list decodable codes

Revisions: 2

__
TR04-070
| 22nd June 2004
__

Leonid Gurvits#### Combinatorial and algorithmic aspects of hyperbolic polynomials

__
TR04-071
| 11th August 2004
__

Marcus Schaefer, Stephen A. Fenner#### Simplicity and Strong Reductions

__
TR04-072
| 19th August 2004
__

John Hitchcock#### Hausdorff Dimension and Oracle Constructions

__
TR04-073
| 9th July 2004
__

Henning Fernau#### A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set

__
TR04-074
| 26th August 2004
__

Emanuele Viola#### On Parallel Pseudorandom Generators

Revisions: 1

__
TR04-075
| 21st July 2004
__

Michael Schmitt#### Some dichotomy theorems for neural learning problems

__
TR04-076
| 17th September 2004
__

Oliver Giel, Ingo Wegener#### Searching Randomly for Maximum Matchings

__
TR04-077
| 17th July 2004
__

Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford#### Reductions Between Classification Tasks

__
TR04-078
| 3rd August 2004
__

Henning Fernau#### Two-Layer Planarization: Improving on Parameterized Algorithmics

__
TR04-079
| 30th August 2004
__

John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn#### The Arithmetical Complexity of Dimension and Randomness

__
TR04-080
| 7th September 2004
__

Lance Fortnow, Troy Lee, Nikolay Vereshchagin#### Kolmogorov Complexity with Error

__
TR04-081
| 9th September 2004
__

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin#### Increasing Kolmogorov Complexity

__
TR04-082
| 9th September 2004
__

Olaf Beyersdorff#### Representable Disjoint NP-Pairs

Revisions: 1

__
TR04-083
| 8th September 2004
__

Boaz Barak, Yehuda Lindell, Salil Vadhan#### Lower Bounds for Non-Black-Box Zero Knowledge

__
TR04-084
| 28th September 2004
__

George Karakostas#### A better approximation ratio for the Vertex Cover problem

__
TR04-085
| 3rd October 2004
__

Erez Petrank, Guy Rothblum#### Selection from Structured Data Sets

__
TR04-086
| 12th October 2004
__

Ronen Shaltiel, Chris Umans#### Pseudorandomness for Approximate Counting and Sampling

__
TR04-087
| 13th October 2004
__

Alexander Healy, Salil Vadhan, Emanuele Viola#### Using Nondeterminism to Amplify Hardness

__
TR04-088
| 12th October 2004
__

Emanuele Viola, Dan Gutfreund#### Fooling Parity Tests with Parity Gates

__
TR04-089
| 26th October 2004
__

Ingo Wegener#### Simulated Annealing Beats Metropolis in Combinatorial Optimization

__
TR04-090
| 3rd November 2004
__

Kazuyuki Amano, Akira Maruoka#### Better Simulation of Exponential Threshold Weights by Polynomial Weights

__
TR04-091
| 29th September 2004
__

Ondrej Klíma, Pascal Tesson, Denis Thérien#### Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

__
TR04-092
| 3rd November 2004
__

Oded Lachish, Ilan Newman#### Testing Periodicity

__
TR04-093
| 9th November 2004
__

Oded Goldreich, Madhu Sudan, Luca Trevisan#### From logarithmic advice to single-bit advice

__
TR04-094
| 10th November 2004
__

Omer Reingold#### Undirected ST-Connectivity in Log-Space

__
TR04-095
| 3rd November 2004
__

Daniele Micciancio#### Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions

__
TR04-096
| 4th November 2004
__

Eldar Fischer, Frederic Magniez, Michel de Rougemont#### Property and Equivalence Testing on Strings

Revisions: 1

__
TR04-097
| 2nd November 2004
__

Víctor Dalmau#### Malt'sev Constraints made Simple

__
TR04-098
| 5th November 2004
__

Lance Fortnow, Rahul Santhanam, Luca Trevisan#### Promise Hierarchies

__
TR04-099
| 11th November 2004
__

Ran Raz#### Extractors with Weak Random Seeds

__
TR04-100
| 23rd November 2004
__

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer#### The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Revisions: 1

__
TR04-101
| 28th September 2004
__

Miroslav Chlebík, Janka Chlebíková#### Crown reductions for the Minimum Weighted Vertex Cover problem

__
TR04-102
| 20th October 2004
__

Thomas Holenstein#### Key Agreement from Weak Bit Agreement

__
TR04-103
| 19th November 2004
__

Lance Fortnow, Adam Klivans#### NP with Small Advice

__
TR04-104
| 19th November 2004
__

Maria Lopez-Valdes, Mayordomo Elvira#### Dimension is compression

__
TR04-105
| 19th November 2004
__

Eldar Fischer, Lance Fortnow#### Tolerant Versus Intolerant Testing for Boolean Properties

__
TR04-106
| 19th November 2004
__

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

__
TR04-107
| 24th November 2004
__

Ingo Wegener, Philipp Woelfel#### New Results on the Complexity of the Middle Bit of Multiplication

Revisions: 1

__
TR04-108
| 24th November 2004
__

Eric Allender, Samir Datta, Sambuddha Roy#### Topology inside NC^1

__
TR04-109
| 15th November 2004
__

Neeraj Kayal, Nitin Saxena#### On the Ring Isomorphism & Automorphism Problems

__
TR04-110
| 24th November 2004
__

Tomoyuki Yamakami, Harumichi Nishimura#### An Application of Quantum Finite Automata to Interactive Proof Systems

__
TR04-111
| 30th November 2004
__

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott#### Computational Complexity of Some Restricted Instances of 3SAT

__
TR04-112
| 26th November 2004
__

Neil Thapen, Nicola Galesi#### Resolution and pebbling games

__
TR04-113
| 19th November 2004
__

Mårten Trolin#### Lattices with Many Cycles Are Dense

__
TR04-114
| 21st November 2004
__

Vladimir Trifonov#### An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity

__
TR04-115
| 1st December 2004
__

Iftach Haitner, Ronen Shaltiel#### Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions

__
TR04-116
| 18th November 2004
__

PERRET ludovic#### On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields

__
TR04-117
| 1st December 2004
__

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis#### Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

__
TR04-118
| 21st December 2004
__

Marek Karpinski, Yakov Nekrich#### A Note on Traversing Skew Merkle Trees

__
TR04-119
| 8th December 2004
__

Uriel Feige, Daniel Reichman#### On The Hardness of Approximating Max-Satisfy

__
TR04-120
| 22nd November 2004
__

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis#### Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a

__
TR04-121
| 7th December 2004
__

Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan#### Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

Lance Fortnow, Russell Impagliazzo, Chris Umans

We study the complexity of solving succinct zero-sum games,

i.e., the

games whose payoff matrix $M$ is given implicitly by a Boolean circuit

$C$ such that $M(i,j)=C(i,j)$. We complement the known $\EXP$-hardness

of computing the \emph{exact} value of a succinct zero-sum game by

several results on \emph{approximating} the value. (1) ...
more >>>

Troy Lee, Dieter van Melkebeek, Harry Buhrman

The language compression problem asks for succinct descriptions of

the strings in a language A such that the strings can be efficiently

recovered from their description when given a membership oracle for

A. We study randomized and nondeterministic decompression schemes

and investigate how close we can get to the information ...
more >>>

Pascal Koiran

Let $\tau(k)$ be the minimum number of arithmetic operations

required to build the integer $k \in \N$ from the constant 1.

A sequence $x_k$ is said to be ``easy to compute'' if

there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$

for all $k \geq ...
more >>>

Ramamohan Paturi, Pavel Pudlak

In 1977 Valiant proposed a graph theoretical method for proving lower

bounds on algebraic circuits with gates computing linear functions.

He used this method to reduce the problem of proving

lower bounds on circuits with linear gates to to proving lower bounds

on the rigidity of a matrix, a ...
more >>>

Stasys Jukna

A boolean circuit $f(x_1,\ldots,x_n)$ \emph{represents} a graph $G$

on $n$ vertices if for every input vector $a\in\{0,1\}^n$ with

precisely two $1$'s in, say, positions $i$ and $j$, $f(a)=1$

precisely when $i$ and $j$ are adjacent in $G$; on inputs with more

or less than two ...
more >>>

Günter Hotz

We prove that it is not decidable on R-machines if for a fixed finite intervall [a,b) the solution of the initial value problems of systems of ordinary differetial equations have solutions over this interval. This result holds independly from assumptions about differentiability of the right sides of the ODEs. Futhermore ... more >>>

Alan L. Selman, Samik Sengupta

It is known \cite{BHZ87} that if every language in coNP has a

constant-round interactive proof system, then the polynomial hierarchy

collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that

#SAT, the #P-complete function that outputs the number of satisfying

assignments of a Boolean ...
more >>>

Vikraman Arvind, Jacobo Toran

The Group Isomorphism problem consists in deciding whether two input

groups $G_1$ and $G_2$ given by their multiplication tables are

isomorphic. We first give a 2-round Arthur-Merlin protocol for the

Group Non-Isomorphism problem such that on input groups $(G_1,G_2)$

of size $n$, Arthur uses ...
more >>>

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda

We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree Δ. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> ≥ <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>>

Michal Parnas, Dana Ron, Ronitt Rubinfeld

A standard property testing algorithm is required to determine

with high probability whether a given object has property

P or whether it is \epsilon-far from having P, for any given

distance parameter \epsilon. An object is said to be \epsilon-far

from having ...
more >>>

Christian Glaßer

We study the power of balanced regular leaf-languages.

First, we investigate (i) regular languages that are

polylog-time reducible to languages in dot-depth 1/2 and

(ii) regular languages that are polylog-time decidable.

For both classes we provide

- forbidden-pattern characterizations, and

- characterizations in terms of regular expressions.

Both ... more >>>

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.

For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ...
more >>>

Oded Goldreich, Dana Ron

Following Feige, we consider the problem of

estimating the average degree of a graph.

Using ``neighbor queries'' as well as ``degree queries'',

we show that the average degree can be approximated

arbitrarily well in sublinear time, unless the graph is extremely sparse

(e.g., unless the graph has a sublinear ...
more >>>

Chris Pollett

Variants of Kannan's Theorem are given where the circuits of

the original theorem are replaced by arbitrary recursively presentable

classes of languages that use advice strings and satisfy certain mild

conditions. These variants imply that $\DTIME(n^{k'})^{\NE}/n^k$

does not contain $\PTIME^{\NE}$, $\DTIME(2^{n^{k'}})/n^k$ does

not contain $\EXP$, $\SPACE(n^{k'})/n^k$ does not ...
more >>>

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

A recursive enumerator for a function $h$ is an algorithm $f$ which

enumerates for an input $x$ finitely many elements including $h(x)$.

$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$

is among the first $k(n)$ elements enumerated by $f$.

If there is a $k(n)$-enumerator for ...
more >>>

Michael Alekhnovich, Eli Ben-Sasson

We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time

of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the ...
more >>>

Evgeny Dantsin, Alexander Wolpert

Recently Schuler \cite{Sch03} presented a randomized algorithm that

solves SAT in expected time at most $2^{n(1-1/\log_2(2m))}$ up to a

polynomial factor, where $n$ and $m$ are, respectively, the number of

variables and the number of clauses in the input formula. This bound

is the best known ...
more >>>

Jan Krajicek

We study the diagonalization in the context of proof

complexity. We prove that at least one of the

following three conjectures is true:

1. There is a boolean function computable in E

that has circuit complexity $2^{\Omega(n)}$.

2. NP is not closed under the complement.

3. There is no ... more >>>

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta

We study several properties of sets that are complete for NP.

We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$

such ...
more >>>

Emanuele Viola

We study the complexity of building

pseudorandom generators (PRGs) from hard functions.

We show that, starting from a function f : {0,1}^l -> {0,1} that

is mildly hard on average, i.e. every circuit of size 2^Omega(l)

fails to compute f on at least a 1/poly(l)

fraction of inputs, we can ...
more >>>

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

We continue the study of the trade-off between the length of PCPs

and their query complexity, establishing the following main results

(which refer to proofs of satisfiability of circuits of size $n$):

We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$

that can be verified by making $o(\log\log n)$ Boolean queries.

more >>>

Nayantara Bhatnagar, Parikshit Gopalan

We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington, Beigel and Rudich. We use the framework established by the authors relating representations by symmetric polynomials to simultaneous protocols. We show that proving bounds on the degree of Threshold functions is equivalent to ... more >>>

Yaoyun Shi

We initiate the study of quantifying the quantumness of

a quantum circuit by the number of gates that do not preserve

the computational basis, as a means to understand the nature

of quantum algorithmic speedups.

Intuitively, a reduction in the quantumness requires

an increase in the amount of classical computation, ...
more >>>

Thomas Thierauf, Thanh Minh Hoang

We show necessary and sufficient conditions that

certain algebraic functions like the rank or the signature

of an integer matrix can be computed in GapL.

John Hitchcock, A. Pavan, Vinodchandran Variyam

The Turing and many-one completeness notions for $\NP$ have been

previously separated under {\em measure}, {\em genericity}, and {\em

bi-immunity} hypotheses on NP. The proofs of all these results rely

on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness ... more >>>

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones.

First, we show that BQP/qpoly is contained in ...
more >>>

Henning Fernau

We derive the first lower bound results on kernel sizes of parameterized problems. The same idea also allows us to sometimes "de-parameterize"

parameterized algorithms.

Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker

Aggregates are a computational model similar to circuits, but the

underlying graph is not necessarily acyclic. Logspace-uniform

polynomial-size aggregates decide exactly the languages in PSPACE;

without uniformity condition they decide the languages in

PSPACE/poly. As a measure of similarity to boolean circuits we

introduce the parameter component size. We ...
more >>>

John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo

Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE.

more >>>Nikolay Vereshchagin

Solovay has proven that

the minimal length of a program enumerating a set A

is upper bounded by 3 times the absolute value of the

logarithm of the

probability that a random program will enumerate A.

It is unknown whether one can replace the constant

3 by a smaller constant.

more >>>

Troy Lee, Andrei Romashchenko

The information contained in a string $x$ about a string $y$

is defined as the difference between the Kolmogorov complexity

of $y$ and the conditional Kolmogorov complexity of $y$ given $x$,

i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small ...
more >>>

Ryan Williams

We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm; more precisely, it is a constant factor improvement in the base of ... more >>>

Michael Schmitt

We study networks of spiking neurons that use the timing of pulses

to encode information. Nonlinear interactions model the spatial

groupings of synapses on the dendrites and describe the computations

performed at local branches. We analyze the question of how many

examples these networks must ...
more >>>

April Rasala Lehman, Eric Lehman

We consider the general network information flow problem, which was

introduced by Ahlswede et. al. We show a periodicity effect: for

every integer m greater than 1, there exists an instance of the

network information flow problem that admits a solution if and only if

the alphabet size is a ...
more >>>

Scott Contini, Ernie Croot, Igor E. Shparlinski

We present an algorithm to invert the Euler function $\varphi(m)$. The algorithm, for a given integer $n\ge 1$, in polynomial time ``on average'', finds theset $\Psi(n)$ of all solutions $m$ to the equation $\varphi(m) =n$. In fact, in the worst case the set $\Psi(n)$ is exponentially large and cannot be ... more >>>

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f.

For several subclasses of operations we prove tight upper and lower bounds for the ... more >>>

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann

Presented is an algorithm (for learning a subclass of erasing regular

pattern languages) which

can be made to run with arbitrarily high probability of

success on extended regular languages generated by patterns

$\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$

for unknown $m$ but known $c$,

more >>>

Andrzej Lingas, Martin Wahlén

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>

Venkatesan Guruswami, Alexander Vardy

Maximum-likelihood decoding is one of the central algorithmic

problems in coding theory. It has been known for over 25 years

that maximum-likelihood decoding of general linear codes is

NP-hard. Nevertheless, it was so far unknown whether maximum-

likelihood decoding remains hard for any specific family of

more >>>

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to tree-like resolution proofs. Therefore, lower bounds for tree-like resolution (which ... more >>>

Ran Raz

An arithmetic circuit or formula is multilinear if the polynomial

computed at each of its wires is multilinear.

We give an explicit example for a polynomial $f(x_1,...,x_n)$,

with coefficients in $\{0,1\}$, such that over any field:

1) $f$ can be computed by a polynomial-size multilinear circuit

of depth $O(\log^2 ...
more >>>

Luca Trevisan

Error-correcting codes and related combinatorial constructs

play an important role in several recent (and old) results

in computational complexity theory. In this paper we survey

results on locally-testable and locally-decodable error-correcting

codes, and their applications to complexity theory and to

cryptography.

Locally decodable codes are error-correcting codes ... more >>>

Eric Allender, Harry Buhrman, Michal Koucky

We investigate the question of whether one can characterize complexity

classes (such as PSPACE or NEXP) in terms of efficient

reducibility to the set of Kolmogorov-random strings R_C.

We show that this question cannot be posed without explicitly dealing

with issues raised by the choice of universal

machine in the ...
more >>>

Hartmut Klauck, Robert Spalek, Ronald de Wolf

A strong direct product theorem says that if we want to compute

k independent instances of a function, using less than k times

the resources needed for one instance, then our overall success

probability will be exponentially small in k.

We establish such theorems for the classical as well as ...
more >>>

Eli Ben-Sasson, Madhu Sudan

We continue the investigation of locally testable codes, i.e.,

error-correcting codes for whom membership of a given word in the

code can be tested probabilistically by examining it in very few

locations. We give two general results on local testability:

First, motivated by the recently proposed notion of robust

probabilistically ...
more >>>

Xiaoyang Gu

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>>

André Lanka, Andreas Goerdt

Assuming 3-SAT formulas are hard to refute

on average, Feige showed some approximation hardness

results for several problems like min bisection, dense

$k$-subgraph, max bipartite clique and the 2-catalog segmentation

problem. We show a similar result for

max bipartite clique, but under the assumption, 4-SAT formulas

are hard to refute ...
more >>>

Piotr Berman, Marek Karpinski, Yakov Nekrich

We prove upper and lower bounds for computing Merkle tree

traversals, and display optimal trade-offs between time

and space complexity of that problem.

Michelle Effros, Leonard Schulman

We consider the $K$-clustering problem with the $\ell_2^2$

distortion measure, also known as the problem of optimal

fixed-rate vector quantizer design. We provide a deterministic

approximation algorithm which works for all dimensions $d$ and

which, given a data set of size $n$, computes in time

more >>>

Zdenek Dvorák, Daniel Král, Ondrej Pangrác

An instance of a constraint satisfaction problem is $l$-consistent

if any $l$ constraints of it can be simultaneously satisfied.

For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the ...
more >>>

Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

In this paper, we study two questions related to

the problem of testing whether a function is close to a homomorphism.

For two finite groups $G,H$ (not necessarily Abelian),

an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,

say that $f$ is $\epsilon$-close to a homomorphism ...
more >>>

A. Pavan, Vinodchandran Variyam

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine

and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes.

Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

Let a program p on input a output b. We are looking for a

shorter program p' having the same property (p'(a)=b). In

addition, we want p' to be simple conditional to p (this

means that the conditional Kolmogorov complexity K(p'|p) is

negligible). In the present paper, we prove that ...
more >>>

Kousha Etessami, Andreas Lochbihler

Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ... more >>>

Vinodchandran Variyam

In this short note we show that for any integer k, there are

languages in the complexity class PP that do not have Boolean

circuits of size $n^k$.

Monica del Pilar Canales Chacon, Michael Johannes Vielhaber

{\bf Abstract}

Isometries on formal power series over the finite field $\ff_2$

or on $2$--adic integers can be

computed by invertible transducers on inputs from $\{0,1\}^\infty$.

We consider the structural complexity of an isometry $f$,

measured as {\it tree complexity} $T(f,h)$, $h$ the tree height

[H.~Niederreiter, M.~Vielhaber, {\it J.~Cpx.}, ...
more >>>

John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

The present work studies clustering from an abstract point of view

and investigates its properties in the framework of inductive inference.

Any class $S$ considered is given by a numbering

$A_0,A_1,...$ of nonempty subsets of the natural numbers

or the rational k-dimensional vector space as a hypothesis space.

A clustering ...
more >>>

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler

The worst-case complexity of an implementation of Quicksort depends

on the random number generator that is used to select the pivot

elements. In this paper we estimate the expected number of

comparisons of Quicksort as a function in the entropy of the random

source. We give upper and lower bounds ...
more >>>

Eli Ben-Sasson, Madhu Sudan

We give constructions of PCPs of length n*polylog(n) (with respect

to circuits of size n) that can be verified by making polylog(n)

queries to bits of the proof. These PCPs are not only shorter than

previous ones, but also simpler. Our (only) building blocks are

Reed-Solomon codes and the bivariate ...
more >>>

Scott Aaronson

A celebrated 1976 theorem of Aumann asserts that honest, rational

Bayesian agents with common priors will never "agree to disagree": if

their opinions about any topic are common knowledge, then those

opinions must be equal. Economists have written numerous papers

examining the assumptions behind this theorem. But two key questions

more >>>

Stasys Jukna

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and ... more >>>

Yehuda Lindell, Benny Pinkas

In the mid 1980's, Yao presented a constant-round protocol for

securely computing any two-party functionality in the presence of

semi-honest adversaries (FOCS 1986). In this paper, we provide a

complete description of Yao's protocol, along with a rigorous

proof of security. Despite the importance of Yao's protocol to the

field ...
more >>>

Piotr Faliszewski

In this paper we define a many-one reduction which is allowed to work in exponential time but may only output polynomially many symbols. We show that there are no NEXP-hard sparse languages under our reduction unless EXP=UEXP.

more >>>Luca Trevisan

We survey results on the hardness of approximating combinatorial

optimization problems.

Tomoyuki Yamakami, Toshio Suzuki

Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we ... more >>>

hadi salmasian, ravindran kannan, Santosh Vempala

We present an algorithm for learning a mixture of distributions.

The algorithm is based on spectral projection and

is efficient when the components of the mixture are logconcave

distributions.

Nir Ailon, Bernard Chazelle

In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped ... more >>>

Eran Rom, Amnon Ta-Shma

In this note we revisit the construction of high noise, almost

optimal rate list decodable code of Guruswami ("Better extractors for better codes?")

Guruswami showed that based on optimal extractors one can build a

$(1-\epsilon,O({1 \over \epsilon}))$ list decodable codes of rate

$\Omega({\epsilon \over {log{1 \over \epsilon}}})$ and alphabet

size ...
more >>>

Leonid Gurvits

Let $p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$

be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients.

The support of such polynomial $p(x_1,...,x_n)$

is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 ...
more >>>

Marcus Schaefer, Stephen A. Fenner

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>

John Hitchcock

Bennett and Gill (1981) proved that P^A != NP^A relative to a

random oracle A, or in other words, that the set

O_[P=NP] = { A | P^A = NP^A }

has Lebesgue measure 0. In contrast, we show that O_[P=NP] has

Hausdorff dimension 1.

... more >>>

Henning Fernau

In this paper, we show how to systematically

improve on parameterized algorithms and their

analysis, focusing on search-tree based algorithms

for d-Hitting Set, especially for d=3.

We concentrate on algorithms which are easy to implement,

in contrast with the highly sophisticated algorithms

which have been elsewhere designed to ...
more >>>

Emanuele Viola

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$

where $C$ is a polynomial-size constant depth circuit

and $C$ and the $q$'s are generated from $x$ arbitrarily.

more >>>

Michael Schmitt

The computational complexity of learning from binary examples is

investigated for linear threshold neurons. We introduce

combinatorial measures that create classes of infinitely many

learning problems with sample restrictions. We analyze how the

complexity of these problems depends on the values for the measures.

...
more >>>

Oliver Giel, Ingo Wegener

Many real-world optimization problems in, e.g., engineering

or biology have the property that not much is known about

the function to be optimized. This excludes the application

of problem-specific algorithms. Simple randomized search

heuristics are then used with surprisingly good results. In

order to understand the working principles behind such

more >>>

Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford

There are two approaches to solving a new supervised learning task: either

analyze the task independently or reduce it to a task that has already

been thoroughly analyzed. This paper investigates the latter approach for

classification problems. In addition to obvious theoretical motivations,

there is fairly strong empirical evidence that ...
more >>>

Henning Fernau

A bipartite graph is biplanar if the vertices can be

placed on two parallel lines in the plane such that there are

no edge crossings when edges are drawn as straight-line segments.

We study two variants of biplanarization problems:

- Two-Layer Planarization TLP: can $k$ edges be deleted from

a ...
more >>>

John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn

Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].

Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... more >>>

Lance Fortnow, Troy Lee, Nikolay Vereshchagin

We introduce the study of Kolmogorov complexity with error. For a

metric d, we define C_a(x) to be the length of a shortest

program p which prints a string y such that d(x,y) \le a. We

also study a conditional version of this measure C_{a,b}(x|y)

where the task is, given ...
more >>>

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

How much do we have to change a string to increase its Kolmogorov complexity. We show that we can

increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings

require

Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ...
more >>>

Olaf Beyersdorff

We investigate the class of disjoint NP-pairs under different reductions.

The structure of this class is intimately linked to the simulation order

of propositional proof systems, and we make use of the relationship between

propositional proof systems and theories of bounded arithmetic as the main

tool of our analysis.

more >>>

Boaz Barak, Yehuda Lindell, Salil Vadhan

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:

<ol>

<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ...
more >>>

George Karakostas

We reduce the approximation factor for Vertex Cover to $2-\Theta(1/\sqrt{logn})$

(instead of the previous $2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even,

and by Monien and Speckenmeyer in 1985. The improvement of the vanishing

factor comes as an application of the recent results of Arora, Rao, and Vazirani

that improved ...
more >>>

Erez Petrank, Guy Rothblum

A large body of work studies the complexity of selecting the

$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.

the select$(j)$ operation). In this work, we study the

complexity of select in data that is partially structured by

an initial preprocessing stage and in a data structure ...
more >>>

Ronen Shaltiel, Chris Umans

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to ``boost'' a given hardness assumption. One special ... more >>>

Alexander Healy, Salil Vadhan, Emanuele Viola

We revisit the problem of hardness amplification in $\NP$, as

recently studied by O'Donnell (STOC `02). We prove that if $\NP$

has a balanced function $f$ such that any circuit of size $s(n)$

fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then

$\NP$ has a function $f'$ such ...
more >>>

Emanuele Viola, Dan Gutfreund

We study the complexity of computing $k$-wise independent and

$\epsilon$-biased generators $G : \{0,1\}^n \to \{0,1\}^m$.

Specifically, we refer to the complexity of computing $G$ \emph{explicitly}, i.e.

given $x \in \{0,1\}^n$ and $i \in \{0,1\}^{\log m}$, computing the $i$-th output bit of $G(x)$.

Mansour, Nisan and Tiwari (1990) show that ...
more >>>

Ingo Wegener

The Metropolis algorithm is simulated annealing with a fixed temperature.Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all ... more >>>

Kazuyuki Amano, Akira Maruoka

We give an explicit construction of depth two threshold circuit with polynomial weights and $\tilde{O}(n^5)$ gates that computes an arbitrary threshold function. We also give the construction of such circuits with $O(n^3/\log n)$ gates computing the COMPARISON and CARRY functions, and that with $O(n^4/\log n)$ gates computing the ADDITION function. ... more >>>

Ondrej Klíma, Pascal Tesson, Denis Thérien

We consider the problem of testing whether a given system of equations

over a fixed finite semigroup S has a solution. For the case where

S is a monoid, we prove that the problem is computable in polynomial

time when S is commutative and is the union of its subgroups

more >>>

Oded Lachish, Ilan Newman

A string $\alpha\in\Sigma^n$ is called {\it p-periodic},

if for every $i,j \in \{1,\dots,n\}$, such that $i\equiv j \bmod p$,

$\alpha_i = \alpha_{j}$, where $\alpha_i$ is the $i$-th place of $\alpha$.

A string $\alpha\in\Sigma^n$ is said to be $period(\leq g)$,

if there exists $p\in \{1,\dots,g\}$ such that $\alpha$ ...
more >>>

Oded Goldreich, Madhu Sudan, Luca Trevisan

Building on Barak's work (Random'02),

Fortnow and Santhanam (FOCS'04) proved a time hierarchy

for probabilistic machines with one bit of advice.

Their argument is based on an implicit translation technique,

which allow to translate separation results for short (say logarithmic)

advice (as shown by Barak) into separations for ...
more >>>

Omer Reingold

We present a deterministic, log-space algorithm that solves

st-connectivity in undirected graphs. The previous bound on the

space complexity of undirected st-connectivity was

log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and

Zhou. As undirected st-connectivity is

complete for the class of problems solvable by symmetric,

non-deterministic, log-space computations (the class SL), ...
more >>>

Daniele Micciancio

We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 ... more >>>

Eldar Fischer, Frederic Magniez, Michel de Rougemont

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>

Víctor Dalmau

We give in this paper a different and simpler proof of the tractability of Mal'tsev contraints.

more >>>Lance Fortnow, Rahul Santhanam, Luca Trevisan

We show that for any constant a, ZPP/b(n) strictly contains

ZPTIME(n^a)/b(n) for some b(n) = O(log n log log n). Our techniques

are very general and give the same hierarchy for all the common

promise time classes including RTIME, NTIME \cap coNTIME, UTIME,

MATIME, AMTIME and BQTIME.

We show a ... more >>>

Ran Raz

We show how to extract random bits from two or more independent

weak random sources, in cases where only one source is of linear

min-entropy and all other sources are of logarithmic min-entropy.

We also give improved constructions of mergers and condensers.

In all that comes below, $\delta$ is an ...
more >>>

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer's dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are ... more >>>

Miroslav Chlebík, Janka Chlebíková

Thomas Holenstein

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S_A and S_B, respectively, such that with probability (1+eps)/2 these bits are equal. Further assume that conditioned on the event S_A = S_B no polynomial time bounded algorithm can predict the ... more >>>

Lance Fortnow, Adam Klivans

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>

Maria Lopez-Valdes, Mayordomo Elvira

Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes.

Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous ...
more >>>

Eldar Fischer, Lance Fortnow

A property tester with high probability accepts inputs satisfying a given property and rejects

inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron

and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We

construct properties of binary functions ...
more >>>

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

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to

the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is

identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ...
more >>>

Ingo Wegener, Philipp Woelfel

It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}.

This paper contains several new results on its complexity.

First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated.

A randomized algorithm for MUL_{n-1,n} with k=O(log ...
more >>>

Eric Allender, Samir Datta, Sambuddha Roy

We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.

We consider other generalizations of ...
more >>>

Neeraj Kayal, Nitin Saxena

We study the complexity of the isomorphism and automorphism problems for finite rings with unity.

We show that both integer factorization and graph isomorphism reduce to the problem of counting

automorphisms of rings. The problem is shown to be in the complexity class $\AM \cap co\AM$

and hence ...
more >>>

Tomoyuki Yamakami, Harumichi Nishimura

Quantum finite automata have been studied intensively since

their introduction in late 1990s as a natural model of a

quantum computer with finite-dimensional quantum memory space.

This paper seeks their direct application

to interactive proof systems in which a mighty quantum prover

communicates with a ...
more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>Neil Thapen, Nicola Galesi

We define a collection of Prover-Delayer games that characterize certain subsystems of resolution. This allows us to give some natural criteria which guarantee lower bounds on the resolution width of a formula, and to extend these results to formulas of unbounded initial width.

We also use games to give upper ... more >>>

Mårten Trolin

We give a method for approximating any $n$-dimensional

lattice with a lattice $\Lambda$ whose factor group

$\mathbb{Z}^n / \Lambda$ has $n-1$ cycles of equal length

with arbitrary precision. We also show that a direct

consequence of this is that the Shortest Vector Problem and the Closest

Vector Problem cannot ...
more >>>

Vladimir Trifonov

We present a deterministic O(log n log log n) space algorithm for

undirected s,t-connectivity. It is based on the deterministic EREW

algorithm of Chong and Lam (SODA 93) and uses the universal

exploration sequences for trees constructed by Kouck\'y (CCC 01).

Our result improves the O(log^{4/3} n) bound of Armoni ...
more >>>

Iftach Haitner, Ronen Shaltiel

A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another

polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any

additional information but the validity of the claim.

Naor ... more >>>

PERRET ludovic

We study in this paper the computational complexity of some

equivalence relations on polynomial systems of equations over finite

fields. These problems are analyzed with respect to polynomial-time

many-one reductions (resp. Turing reductions, Levin reductions). In

particular, we show that some of these problems are between ...
more >>>

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT).

We prove strong nonapproximability results in this model for well-known problems such ... more >>>

Marek Karpinski, Yakov Nekrich

We consider the problem of traversing skew (unbalanced) Merkle

trees and design an algorithm for traversing a skew Merkle tree

in time O(log n/log t) and space O(log n (t/log t)), for any choice

of parameter t\geq 2.

This algorithm can be of special interest in situations when

more >>>

Uriel Feige, Daniel Reichman

Max-Satisfy is the problem of finding an assignment that satisfies

the maximum number of equations in a system of linear equations

over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no

polynomial time algorithm for the problem achieving an

approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number

of ...
more >>>

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis

Alice and Bob want to know if two strings of length $n$ are

almost equal. That is, do they differ on at most $a$ bits?

Let $0\le a\le n-1$.

We show that any deterministic protocol, as well as any

error-free quantum protocol ($C^*$ version), for this problem

requires at ...
more >>>

Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

In this paper we study the complexity of Bounded Color

Multiplicity Graph Isomorphism (BCGI): the input is a pair of

vertex-colored graphs such that the number of vertices of a given

color in an input graph is bounded by $b$. We show that BCGI is in the

#L hierarchy ...
more >>>