All reports in year 2001:

__
TR01-001
| 31st December 2000
__

Jin-Yi Cai#### Essentially every unimodular matrix defines an expander

__
TR01-002
| 6th December 2000
__

Venkatesan Guruswami#### Constructions of Codes from Number Fields

__
TR01-004
| 13th October 2000
__

Tobias Gärtner, Günter Hotz#### Recursive analytic functions of a complex variable

__
TR01-005
| 27th October 2000
__

Pascal Tesson, Denis Thérien#### The Computing Power of Programs over Finite Monoids

__
TR01-006
| 18th October 2000
__

Rocco Servedio#### On Learning Monotone DNF under Product Distributions

__
TR01-007
| 7th December 2000
__

Vered Rosen#### On the Security of Modular Exponentiation

Comments: 1

__
TR01-008
| 6th November 2000
__

Eldar Fischer#### On the strength of comparisons in property testing

__
TR01-009
| 5th January 2001
__

Ronen Shaltiel#### Towards proving strong direct product theorems

__
TR01-010
| 25th January 2001
__

Oded Goldreich, Luca Trevisan#### Three Theorems regarding Testing Graph Properties.

Revisions: 1

__
TR01-011
| 21st January 2001
__

Dima Grigoriev, Edward Hirsch#### Algebraic proof systems over formulas

__
TR01-012
| 4th January 2001
__

Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov#### Algorithms for SAT and Upper Bounds on Their Complexity

__
TR01-013
| 2nd February 2001
__

Michal Koucky#### Log-space Constructible Universal Traversal Sequences for Cycles of Length $O(n^{4.03})$

__
TR01-014
| 7th February 2001
__

Marcos Kiwi, Frederic Magniez, Miklos Santha#### Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey

__
TR01-015
| 9th February 2001
__

Amos Beimel, Yuval Ishai#### Information-Theoretic Private Information Retrieval: A Unified Construction

__
TR01-016
| 22nd December 2000
__

Ran Canetti#### A unified framework for analyzing security of protocols

Revisions: 5

__
TR01-017
| 14th February 2001
__

Petr Savicky, Detlef Sieling#### A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

__
TR01-018
| 23rd February 2001
__

Omer Reingold, Salil Vadhan, Avi Wigderson#### Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

__
TR01-019
| 2nd March 2001
__

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet#### The Communication Complexity of Enumeration, Elimination, and Selection

__
TR01-020
| 20th February 2001
__

N. S. Narayanaswamy, C.E. Veni Madhavan#### Lower Bounds for OBDDs and Nisan's pseudorandom generator

__
TR01-021
| 7th March 2001
__

Ran Raz#### Resolution Lower Bounds for the Weak Pigeonhole Principle

Revisions: 1

__
TR01-022
| 15th February 2001
__

Rahul Santhanam#### On segregators, separators and time versus space

__
TR01-023
| 13th March 2001
__

Jochen Alber, Henning Fernau, Rolf Niedermeier#### Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revisions: 1

__
TR01-024
| 1st March 2001
__

Stephen Cook, Antonina Kolokolova#### A second-order system for polynomial-time reasoning based on Graedel's theorem

__
TR01-025
| 28th March 2001
__

Piotr Berman, Marek Karpinski#### Approximating Minimum Unsatisfiability of Linear Equations

__
TR01-026
| 3rd April 2001
__

Piotr Berman, Marek Karpinski#### Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

__
TR01-027
| 23rd March 2001
__

Marius Zimand#### Probabilistically Checkable Proofs The Easy Way

__
TR01-028
| 16th March 2001
__

Thanh Minh Hoang, Thomas Thierauf#### The Complexity of the Minimal Polynomial

__
TR01-029
| 27th March 2001
__

Denis Xavier Charles#### A Note on Subgroup Membership Problem for PSL(2,p).

Comments: 1

__
TR01-030
| 25th April 2001
__

Jin-Yi Cai#### S_2^p \subseteq ZPP^{NP}

__
TR01-031
| 5th April 2001
__

Eli Ben-Sasson, Nicola Galesi#### Space Complexity of Random Formulae in Resolution

__
TR01-032
| 3rd April 2001
__

A. Pavan, Alan L. Selman#### Separation of NP-completeness Notions

__
TR01-033
| 27th April 2001
__

Eric Allender, David Mix Barrington, William Hesse#### Uniform Circuits for Division: Consequences and Problems

__
TR01-034
| 30th April 2001
__

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski#### Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction

__
TR01-035
| 15th April 2001
__

Amir Shpilka#### Affine Projections of Symmetric Polynomials

__
TR01-036
| 2nd May 2001
__

Amnon Ta-Shma, David Zuckerman, Shmuel Safra#### Extractors from Reed-Muller Codes

__
TR01-037
| 21st February 2001
__

Rustam Mubarakzjanov#### Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable

__
TR01-038
| 14th May 2001
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Approximating Schedules for Dynamic Graphs Efficiently

__
TR01-039
| 18th May 2001
__

Stasys Jukna, Stanislav Zak#### On Uncertainty versus Size in Branching Programs

Revisions: 1

__
TR01-040
| 16th May 2001
__

Pierre Péladeau, Denis Thérien#### On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

__
TR01-041
| 23rd May 2001
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay#### Time-Space Tradeoffs in the Counting Hierarchy

__
TR01-042
| 31st May 2001
__

Marek Karpinski#### Approximating Bounded Degree Instances of NP-Hard Problems

__
TR01-043
| 26th April 2001
__

Mikhail V. Vyugin, Vladimir Vyugin#### Predictive complexity and information

__
TR01-044
| 14th June 2001
__

Pavel Pudlak#### On reducibility and symmetry of disjoint NP-pairs

__
TR01-045
| 26th April 2001
__

Michael Schmitt#### Neural Networks with Local Receptive Fields and Superlinear VC Dimension

__
TR01-046
| 2nd July 2001
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### On Interactive Proofs with a Laconic Prover

__
TR01-047
| 3rd July 2001
__

Piotr Berman, Sridhar Hannenhalli, Marek Karpinski#### 1.375-Approximation Algorithm for Sorting by Reversals

__
TR01-048
| 3rd June 2001
__

Jui-Lin Lee#### Branching program, commutator, and icosahedron, part I

__
TR01-049
| 11th July 2001
__

Stasys Jukna, Georg Schnitger#### On Multi-Partition Communication Complexity of Triangle-Freeness

Comments: 2

__
TR01-050
| 24th June 2001
__

Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen#### Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

__
TR01-051
| 4th May 2001
__

Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont#### Probabilistic abstraction for model checking: An approach based on property testing

Revisions: 1

__
TR01-052
| 26th April 2001
__

Mikhail V. Vyugin, Vladimir Vyugin#### Non-linear Inequalities between Predictive and Kolmogorov Complexity

__
TR01-053
| 17th July 2001
__

Piotr Berman, Marek Karpinski#### Efficient Amplifiers and Bounded Degree Optimization

__
TR01-054
| 12th April 2001
__

Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir#### On the Complexity of Positional Sequencing by Hybridization

__
TR01-055
| 26th July 2001
__

Alexander Razborov#### Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

__
TR01-056
| 6th August 2001
__

Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart#### An Exponential Separation between Regular and General Resolution

__
TR01-057
| 15th August 2001
__

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang#### On the (Im)possibility of Obfuscating Programs

__
TR01-058
| 28th August 2001
__

Stasys Jukna#### A Note on the Minimum Number of Negations Leading to Superpolynomial Savings

__
TR01-059
| 20th July 2001
__

Elvira Mayordomo#### A Kolmogorov complexity characterization of constructive Hausdorff dimension

Revisions: 3

__
TR01-060
| 23rd August 2001
__

Amir Shpilka#### Lower bounds for matrix product

__
TR01-061
| 13th July 2001
__

Mitsunori Ogihara, Seinosuke Toda#### The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs

Revisions: 2

__
TR01-062
| 9th September 2001
__

Moni Naor, Kobbi Nissim#### Communication Complexity and Secure Function Evaluation

__
TR01-063
| 5th August 2001
__

Michal Parnas, Dana Ron, Alex Samorodnitsky#### Proclaiming Dictators and Juntas or Testing Boolean Formulae

Revisions: 1

__
TR01-064
| 10th September 2001
__

Moni Naor, Omer Reingold, Alon Rosen#### Pseudo-Random Functions and Factoring

__
TR01-065
| 10th August 2001
__

Chandra Chekuri, Sanjeev Khanna#### Approximation Schemes for Preemptive Weighted Flow Time

__
TR01-066
| 28th September 2001
__

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger#### On Multipartition Communication Complexity

__
TR01-067
| 18th September 2001
__

Hubie Chen#### Polynomial Programs and the Razborov-Smolensky Method

__
TR01-068
| 19th September 2001
__

Philippe Moser#### Relative to P, APP and promise-BPP are the same

Revisions: 1

__
TR01-069
| 24th October 2001
__

Robert Albin Legenstein#### Optimizing the Layout of a Balanced Tree

Revisions: 1

__
TR01-070
| 24th October 2001
__

Robert Albin Legenstein#### Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing

__
TR01-071
| 24th October 2001
__

Robert Albin Legenstein#### Neural Circuits for Pattern Recognition with Small Total Wire Length

__
TR01-072
| 18th October 2001
__

Ronald Cramer, Victor Shoup#### Universal Hash Proofs and and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption

Revisions: 2

__
TR01-073
| 24th October 2001
__

Beate Bollig, Philipp Woelfel, Stephan Waack#### Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Revisions: 1

__
TR01-074
| 12th October 2001
__

Joshua Buresh-Oppenheim, David Mitchell#### Linear and Negative Resolution are Weaker than Resolution

Comments: 1

__
TR01-075
| 2nd November 2001
__

Alexander Razborov#### Resolution Lower Bounds for the Weak Functional Pigeonhole Principle

__
TR01-076
| 24th October 2001
__

Robert Albin Legenstein#### On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets

__
TR01-077
| 24th September 2001
__

Andrei Krokhin, Peter Jeavons, Peter Jonsson#### The complexity of constraints on intervals and lengths

__
TR01-078
| 6th November 2001
__

Matthias Krause#### BDD-based Cryptanalysis of Keystream Generators

__
TR01-079
| 6th September 2001
__

Michele Zito#### An Upper Bound on the Space Complexity of Random Formulae in Resolution

__
TR01-080
| 14th November 2001
__

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan#### Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3

__
TR01-081
| 8th August 2001
__

Palash Sarkar#### Pushdown Automaton with the Ability to Flip its Stack

__
TR01-082
| 24th September 2001
__

Tsuyoshi Morioka#### Classification of Search Problems and Their Definability in Bounded Arithmetic

__
TR01-083
| 29th October 2001
__

Nikolay Vereshchagin#### An enumerable undecidable set with low prefix complexity: a simplified proof

Revisions: 1

__
TR01-084
| 1st October 2001
__

Gerhard J. Woeginger#### When does a dynamic programming formulation guarantee the existence of an FPTAS?

__
TR01-085
| 1st October 2001
__

Gerhard J. Woeginger#### Resource augmentation for online bounded space bin packing

__
TR01-086
| 29th October 2001
__

Nikolay Vereshchagin#### Kolmogorov Complexity Conditional to Large Integers

__
TR01-087
| 29th October 2001
__

Bruno Durand, Alexander Shen, Nikolay Vereshchagin#### Descriptive complexity of computable sequences

__
TR01-088
| 29th October 2001
__

Alexander Shen, Nikolay Vereshchagin#### Logical operations and Kolmogorov complexity

__
TR01-089
| 29th October 2001
__

Andrej Muchnik, Nikolay Vereshchagin#### Logical operations and Kolmogorov complexity. II

__
TR01-090
| 28th November 2001
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Dynamic Process Graphs and the Complexity of Scheduling

__
TR01-091
| 27th November 2001
__

Oded Goldreich#### Concurrent Zero-Knowledge With Timing, Revisited

__
TR01-092
| 2nd October 2001
__

Till Tantau#### A Note on the Complexity of the Reachability Problem for Tournaments

__
TR01-093
| 2nd December 2001
__

Boaz Barak, Oded Goldreich#### Universal Arguments and their Applications

__
TR01-094
| 3rd December 2001
__

Jonas Holmerin#### Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon

__
TR01-095
| 12th November 2001
__

Hubie Chen#### Arithmetic Versions of Constant Depth Circuit Complexity Classes

__
TR01-096
| 21st November 2001
__

Jörg Rothe#### Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial

Revisions: 1

__
TR01-097
| 11th December 2001
__

Piotr Berman, Marek Karpinski#### Improved Approximations for General Minimum Cost Scheduling

__
TR01-098
| 19th November 2001
__

Ke Yang#### On Learning Correlated Boolean Functions Using Statistical Query

__
TR01-099
| 1st October 2001
__

Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis#### The Range of Stability for Heterogeneous and FIFO Queueing Networks

__
TR01-100
| 14th December 2001
__

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Random Sampling and Approximation of MAX-CSP Problems

__
TR01-101
| 14th December 2001
__

Philipp Woelfel#### A Lower Bound Technique for Restricted Branching Programs and Applications

__
TR01-102
| 18th December 2001
__

Oded Goldreich#### Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.

__
TR01-103
| 14th December 2001
__

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik#### Complexity of semi-algebraic proofs

Revisions: 3

__
TR01-104
| 17th December 2001
__

Irit Dinur, Shmuel Safra#### The Importance of Being Biased

Jin-Yi Cai

We generalize the construction of Gabber and Galil

to essentially every unimodular matrix in $SL_2(\Z)$. It is shown that

every parabolic

or hyperbolic fractional linear transformation explicitly

defines an expander of bounded degree

and constant expansion. Thus all but a vanishingly small fraction

of unimodular matrices define expanders.

Venkatesan Guruswami

We define number-theoretic error-correcting codes based on algebraic

number fields, thereby providing a generalization of Chinese Remainder

Codes akin to the generalization of Reed-Solomon codes to

Algebraic-geometric codes. Our construction is very similar to

(and in fact less general than) the one given by (Lenstra 1986), but

the ...
more >>>

Tobias Gärtner, Günter Hotz

We extend the concept of recursive definition on analytic functions. For special cases of linear primitive recursive definitions we show the existence of natural continuations of the over $\N$ primitive recursive functions to analytic functions. Especially, we show that solutions exist if the coefficients of the linear recursive equation are ... more >>>

Pascal Tesson, Denis Thérien

The formalism of programs over monoids has been studied for its close

connection to parallel complexity classes defined by small-depth

boolean circuits. We investigate two basic questions about this

model. When is a monoid rich enough that it can recognize arbitrary

languages (provided no restriction on length is imposed)? When ...
more >>>

Rocco Servedio

We show that the class of monotone $2^{O(\sqrt{\log n})}$-term DNF

formulae can be PAC learned in polynomial time under the uniform

distribution. This is an exponential improvement over previous

algorithms in this model, which could learn monotone

$o(\log^2 n)$-term DNF, and is the first efficient algorithm

for ...
more >>>

Vered Rosen

Assuming the inractability of factoring, we show that the

output of the exponentiation modulo a composite function

$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,

even when its input is restricted to be half the size.

This result is equivalent to the simultaneous hardness of

the ...
more >>>

Eldar Fischer

An $\epsilon$-test for a property $P$ of functions from

${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized

algorithm, which makes queries on the value of an input function at

specified locations, and distinguishes with high probability between the

case of the function satisfying $P$, and the case that it ...
more >>>

Ronen Shaltiel

A fundamental question of complexity theory is the direct product

question. Namely weather the assumption that a function $f$ is hard on

average for some computational class (meaning that every algorithm from

the class has small advantage over random guessing when computing $f$)

entails that computing $f$ on ...
more >>>

Oded Goldreich, Luca Trevisan

Property testing is a relaxation of decision problems

in which it is required to distinguish {\sc yes}-instances

(i.e., objects having a predetermined property) from instances

that are far from any {\sc yes}-instance.

We presents three theorems regarding testing graph

properties in the adjacency matrix representation. ...
more >>>

Dima Grigoriev, Edward Hirsch

We introduce two algebraic propositional proof systems F-NS

and F-PC. The main difference of our systems from (customary)

Nullstellensatz and Polynomial Calculus is that the polynomials

are represented as arbitrary formulas (rather than sums of

monomials). Short proofs of Tseitin's tautologies in the

constant-depth version of F-NS provide ...
more >>>

Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

We survey recent algorithms for the propositional

satisfiability problem, in particular algorithms

that have the best current worst-case upper bounds

on their complexity. We also discuss some related

issues: the derandomization of the algorithm of

Paturi, Pudlak, Saks and Zane, the Valiant-Vazirani

Lemma, and random walk ...
more >>>

Michal Koucky

The paper presents a simple construction of polynomial length universal

traversal sequences for cycles. These universal traversal sequences are

log-space (even $NC^1$) constructible and are of length $O(n^{4.03})$. Our

result improves the previously known upper-bound $O(n^{4.76})$ for

log-space constructible universal traversal sequences for cycles.

Marcos Kiwi, Frederic Magniez, Miklos Santha

In the late 80's Blum, Luby, Rubinfeld, Kannan et al. pioneered

the theory of self-testing as an alternative way of dealing with

the problem of software reliability.

Over the last decade this theory played a crucial role in

the construction of probabilistically checkable proofs and

the ...
more >>>

Amos Beimel, Yuval Ishai

A Private Information Retrieval (PIR) protocol enables a user to

retrieve a data item from a database while hiding the identity of the

item being retrieved. In a $t$-private, $k$-server PIR protocol the

database is replicated among $k$ servers, and the user's privacy is

protected from any collusion of up ...
more >>>

Ran Canetti

Building on known definitions, we present a unified general framework for

defining and analyzing security of cryptographic protocols. The framework

allows specifying the security requirements of a large number of

cryptographic tasks, such as signature, encryption, authentication, key

exchange, commitment, oblivious transfer, zero-knowledge, secret sharing,

general function evaluation, and ...
more >>>

Petr Savicky, Detlef Sieling

Restricted branching programs are considered in complexity theory in

order to study the space complexity of sequential computations and

in applications as a data structure for Boolean functions. In this

paper (\oplus,k)-branching programs and (\vee,k)-branching

programs are considered, i.e., branching programs starting with a

...
more >>>

Omer Reingold, Salil Vadhan, Avi Wigderson

The main contribution of this work is a new type of graph product, which we call the zig-zag

product. Taking a product of a large graph with a small graph, the resulting graph inherits

(roughly) its size from the large one, its degree from the small one, and ...
more >>>

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

Normally, communication Complexity deals with how many bits

Alice and Bob need to exchange to compute f(x,y)

(Alice has x, Bob has y). We look at what happens if

Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n

and they want to compute f(x_1,y_1)... f(x_n,y_n).

THis seems hard. We look at various ...
more >>>

N. S. Narayanaswamy, C.E. Veni Madhavan

We present a new boolean function for which any Ordered Binary

Decision Diagram (OBDD) computing it has an exponential number

of nodes. This boolean function is obtained from Nisan's

pseudorandom generator to derandomize space bounded randomized

algorithms. Though the relation between hardness and randomness for

computational models is well ...
more >>>

Ran Raz

We prove that any Resolution proof for the weak

pigeon hole principle, with $n$ holes and any number of

pigeons, is of length $\Omega(2^{n^{\epsilon}})$,

(for some global constant $\epsilon > 0$).

Rahul Santhanam

We give the first extension of the result due to Paul, Pippenger,

Szemeredi and Trotter that deterministic linear time is distinct from

nondeterministic linear time. We show that DTIME(n \sqrt(log^{*}(n)))

\neq NTIME(n \sqrt(log^{*}(n))). We show that atleast one of the

following statements holds: (1) P \neq L ...
more >>>

Jochen Alber, Henning Fernau, Rolf Niedermeier

A parameterized problem is called fixed parameter tractable

if it admits a solving algorithm whose running time on

input instance $(I,k)$ is $f(k) \cdot |I|^\alpha$, where $f$

is an arbitrary function depending only on~$k$. Typically,

$f$ is some exponential function, e.g., $f(k)=c^k$ for ...
more >>>

Stephen Cook, Antonina Kolokolova

We introduce a second-order system V_1-Horn of bounded arithmetic

formalizing polynomial-time reasoning, based on Graedel's

second-order Horn characterization of P. Our system has

comprehension over P predicates (defined by Graedel's second-order

Horn formulas), and only finitely many function symbols. Other

systems of polynomial-time reasoning either ...
more >>>

Piotr Berman, Marek Karpinski

We consider the following optimization problem:

given a system of m linear equations in n variables over a certain field,

a feasible solution is any assignment of values to the variables, and the

minimized objective function is the number of equations that are not

satisfied. For ...
more >>>

Piotr Berman, Marek Karpinski

We consider bounded occurrence (degree) instances of a minimum

constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for

graphs. MIN-LIN2 is an optimization problem for a given system of linear

equations mod 2 to construct a solution that satisfies the minimum number

of them. E3-OCC-MIN-E3-LIN2 ...
more >>>

Marius Zimand

We present a weaker variant of the PCP Theorem that admits a

significantly easier proof. In this

variant the prover only has $n^t$ time to compute each

bit of his answer, for an arbitray but fixed constant

$t$, in contrast to

being all powerful. We show that

3SAT ...
more >>>

Thanh Minh Hoang, Thomas Thierauf

We investigate the computational complexity

of the minimal polynomial of an integer matrix.

We show that the computation of the minimal polynomial

is in AC^0(GapL), the AC^0-closure of the logspace

counting class GapL, which is contained in NC^2.

Our main result is that the problem is hard ...
more >>>

Denis Xavier Charles

We show that there are infinitely many primes $p$, such

that the subgroup membership problem for PSL(2,p) belongs

to $\NP \cap \coNP$.

Jin-Yi Cai

We show that the class ${\rm S}_2^p$ is a subclass of

${{\rm ZPP}^{\rm NP}}$. The proof uses universal hashing, approximate counting

and witness sampling. As a consequence, a collapse first noticed by

Samik Sengupta that the assumption NP has small circuits collapses

PH to ${\rm S}_2^p$

becomes the strongest version ...
more >>>

Eli Ben-Sasson, Nicola Galesi

We study the space complexity of refuting unsatisfiable random $k$-CNFs in

the Resolution proof system. We prove that for any large enough $\Delta$,

with high probability a random $k$-CNF over $n$ variables and $\Delta n$

clauses requires resolution clause space of

$\Omega(n \cdot \Delta^{-\frac{1+\epsilon}{k-2-\epsilon}})$,

for any $0<\epsilon<1/2$. For constant $\Delta$, ...
more >>>

A. Pavan, Alan L. Selman

We use hypotheses of structural complexity theory to separate various

NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we ...
more >>>

Eric Allender, David Mix Barrington, William Hesse

Integer division has been known to lie in P-uniform TC^0 since

the mid-1980's, and recently this was improved to DLOG-uniform

TC^0. At the time that the results in this paper were proved and

submitted for conference presentation, it was unknown whether division

lay in DLOGTIME-uniform TC^0 (also known as ...
more >>>

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

It is known that large fragments of the class of dense

Minimum Constraint Satisfaction (MIN-CSP) problems do not have

polynomial time approximation schemes (PTASs) contrary to their

Maximum Constraint Satisfaction analogs. In this paper we prove,

somewhat surprisingly, that the minimum satisfaction of dense

instances of kSAT-formulas, ...
more >>>

Amir Shpilka

In this paper we introduce a new model for computing=20

polynomials - a depth 2 circuit with a symmetric gate at the top=20

and plus gates at the bottom, i.e the circuit computes a=20

symmetric function in linear functions -

$S_{m}^{d}(\ell_1,\ell_2,...,\ell_m)$ ($S_{m}^{d}$ is the $d$'th=20

elementary symmetric polynomial in $m$ ...
more >>>

Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, ... more >>>

Rustam Mubarakzjanov

Restricted branching programs are considered by the investigation

of relationships between complexity classes of Boolean functions.

Read-once ordered branching programs (or OBDDs) form the most restricted class

of this computation model.

Since the problem of proving exponential lower bounds on the complexity

for general probabilistic OBDDs is open so ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

A model for parallel and distributed programs, the dynamic process graph (DPG),

is investigated under graph-theoretic and complexity aspects.

Such graphs embed constructors for parallel programs,

synchronization mechanisms as well as conditional branches.

They are capable of representing all possible executions of a

parallel or distributed program ...
more >>>

Stasys Jukna, Stanislav Zak

We propose an information-theoretic approach to proving lower

bounds on the size of branching programs. The argument is based on

Kraft-McMillan type inequalities for the average amount of

uncertainty about (or entropy of) a given input during the various

stages of computation. The uncertainty is measured by the average

more >>>

Pierre Péladeau, Denis Thérien

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality.

Translator's note: This is a translation of the ... more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay

We extend the lower bound techniques of [Fortnow], to the

unbounded-error probabilistic model. A key step in the argument

is a generalization of Nepomnjascii's theorem from the Boolean

setting to the arithmetic setting. This generalization is made

possible, due to the recent discovery of logspace-uniform TC^0

more >>>

Marek Karpinski

We present some of the recent results on computational complexity

of approximating bounded degree combinatorial optimization problems. In

particular, we present the best up to now known explicit nonapproximability

bounds on the very small degree optimization problems which are of

particular importance on the intermediate stages ...
more >>>

Mikhail V. Vyugin, Vladimir Vyugin

A new notion of predictive complexity and corresponding amount of

information are considered.

Predictive complexity is a generalization of Kolmogorov complexity

which bounds the ability of any algorithm to predict elements of

a sequence of outcomes. We consider predictive complexity for a wide class

of bounded loss functions which ...
more >>>

Pavel Pudlak

We consider some problems about pairs of disjoint $NP$ sets.

The theory of these sets with a natural concept of reducibility

is, on the one hand, closely related to the theory of proof

systems for propositional calculus, and, on the other, it

resembles the theory of NP completeness. Furthermore, such

more >>>

Michael Schmitt

Local receptive field neurons comprise such well-known and widely

used unit types as radial basis function neurons and neurons with

center-surround receptive field. We study the Vapnik-Chervonenkis

(VC) dimension of feedforward neural networks with one hidden layer

of these units. For several variants of local receptive field

neurons we show ...
more >>>

Oded Goldreich, Salil Vadhan, Avi Wigderson

We continue the investigation of interactive proofs with bounded

communication, as initiated by Goldreich and Hastad (IPL 1998).

Let $L$ be a language that has an interactive proof in which the prover

sends few (say $b$) bits to the verifier.

We prove that the complement $\bar L$ has ...
more >>>

Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

Analysis of genomes evolving by inversions leads to a general

combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of

sorting a permutation by a minimum number of reversals.

This combinatorial problem has a long history, and a number of other

motivations. It was studied in a great ...
more >>>

Jui-Lin Lee

In this paper we give a direct proof of $N_0=N_0^\prime$, i.e., the equivalence of

uniform $NC^1$ based on different recursion principles: one is OR-AND complete

binary tree (in depth $\log n$) and the other is the recursion on notation with value

bounded in $[0,k]$ and $|x|(=n)$ many ...
more >>>

Stasys Jukna, Georg Schnitger

We show that recognizing the $K_3$-freeness and $K_4$-freeness of

graphs is hard, respectively, for two-player nondeterministic

communication protocols with exponentially many partitions and for

nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to

Papadimitriou and Sipser, which says that for every ...
more >>>

Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

We show that any concurrent zero-knowledge protocol for a non-trivial

language (i.e., for a language outside $\BPP$), whose security is proven

via black-box simulation, must use at least $\tilde\Omega(\log n)$

rounds of interaction. This result achieves a substantial improvement

over previous lower bounds, and is the first bound to rule ...
more >>>

Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont

In model checking, program correctness on all inputs is verified

by considering the transition system underlying a given program.

In practice, the system can be intractably large.

In property testing, a property of a single input is verified

by looking at a small subset of that input.

We ...
more >>>

Mikhail V. Vyugin, Vladimir Vyugin

Predictive complexity is a generalization of Kolmogorov complexity

which gives a lower bound to ability of any algorithm to predict

elements of a sequence of outcomes. A variety of types of loss

functions makes it interesting to study relations between corresponding

predictive complexities.

Non-linear inequalities between predictive complexity of ... more >>>

Piotr Berman, Marek Karpinski

This paper studies the existence of efficient (small size)

amplifiers for proving explicit inaproximability results for bounded degree

and bounded occurrence combinatorial optimization problems, and gives

an explicit construction for such amplifiers. We use this construction

also later to improve the currently best known approximation lower bounds

more >>>

Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir

In sequencing by hybridization (SBH),

one has to reconstruct a sequence

from its $l$-long substrings.

SBH was proposed as

an alternative to

gel-based

DNA sequencing approaches, but in its original form the method

is

not competitive.

Positional SBH (PSBH) is a recently proposed

enhancement ...
more >>>

Alexander Razborov

Recently, Raz established exponential lower bounds on the size

of resolution proofs of the weak pigeonhole principle. We give another

proof of this result which leads to better numerical bounds. Specifically,

we show that every resolution proof of $PHP^m_n$ must have size

$\exp\of{\Omega(n/\log m)^{1/2}}$ which implies an

$\exp\of{\Omega(n^{1/3})}$ bound when ...
more >>>

Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart

This paper gives two distinct proofs of an exponential separation

between regular resolution and unrestricted resolution.

The previous best known separation between these systems was

quasi-polynomial.

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)

"compiler" that takes as input a program (or circuit) <b>P</b> and

produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>

yet is "unintelligible" in some sense. Obfuscators, if they exist,

would have a wide variety of cryptographic ...
more >>>

Stasys Jukna

In 1957 Markov proved that every circuit in $n$ variables

can be simulated by a circuit with at most $\log(n+1)$ negations.

In 1974 Fischer has shown that this can be done with only

polynomial increase in size.

In this note we observe that some explicit monotone functions ... more >>>

Elvira Mayordomo

We obtain the following full characterization of constructive dimension

in terms of algorithmic information content. For every sequence A,

cdim(A)=liminf_n (K(A[0..n-1])/n.

Amir Shpilka

We prove lower bounds on the number of product gates in bilinear

and quadratic circuits that

compute the product of two $n \times n$ matrices over finite fields.

In particular we obtain the following results:

1. We show that the number of product gates in any bilinear

(or quadratic) ...
more >>>

Mitsunori Ogihara, Seinosuke Toda

Valiant (SIAM Journal on Computing 8, pages 410--421) showed that the

roblem of counting the number of s-t paths in graphs (both in the case

of directed graphs and in the case of undirected graphs) is complete

for #P under polynomial-time one-Turing reductions (namely, some

post-computation is needed to ...
more >>>

Moni Naor, Kobbi Nissim

A secure function evaluation protocol allows two parties to jointly compute a function $f(x,y)$ of their inputs in a manner not leaking more information than necessary. A major result in this field is: ``any function $f$ that can be computed using polynomial resources can be computed securely using polynomial resources'' ... more >>>

Michal Parnas, Dana Ron, Alex Samorodnitsky

We consider the problem of determining whether a given

function f : {0,1}^n -> {0,1} belongs to a certain class

of Boolean functions F or whether it is far from the class.

More precisely, given query access to the function f and given

a distance parameter epsilon, we would ...
more >>>

Moni Naor, Omer Reingold, Alon Rosen

Factoring integers is the most established problem on which

cryptographic primitives are based. This work presents an efficient

construction of {\em pseudorandom functions} whose security is based

on the intractability of factoring. In particular, we are able to

construct efficient length-preserving pseudorandom functions where

each evaluation requires only a ...
more >>>

Chandra Chekuri, Sanjeev Khanna

We present the first approximation schemes for minimizing weighted flow time

on a single machine with preemption. Our first result is an algorithm that

computes a $(1+\eps)$-approximate solution for any instance of weighted flow

time in $O(n^{O(\ln W \ln P/\eps^3)})$ time; here $P$ is the ratio ...
more >>>

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

We study k-partition communication protocols, an extension

of the standard two-party best-partition model to k input partitions.

The main results are as follows.

1. A strong explicit hierarchy on the degree of

non-obliviousness is established by proving that,

using k+1 partitions instead of k may decrease

the communication complexity from ...
more >>>

Hubie Chen

Representations of boolean functions as polynomials (over rings) have

been used to establish lower bounds in complexity theory. Such

representations were used to great effect by Smolensky, who

established that MOD q \notin AC^0[MOD p] (for distinct primes p, q)

by representing AC^0[MOD p] functions as low-degree multilinear

polynomials over ...
more >>>

Philippe Moser

We show that for determinictic polynomial time computation, oracle access to

$\mathbf{APP}$, the class of real functions

approximable by probabilistic Turing machines, is the same as having oracle access to

promise-$\mathbf{BPP}$. First

we construct a mapping that maps every function in $\mathbf{APP}$ to a promise problem

more >>>

Robert Albin Legenstein

It is shown that the total wire length of layouts of a

balanced binary tree on a 2-dimensional grid can be reduced by 33%

if one does not choose the obvious ``symmetric'' layout strategy.

Furthermore it is shown that the more efficient layout strategy that

is presented in this article ...
more >>>

Robert Albin Legenstein

We introduce em total wire length as salient complexity measure

for analyzing the circuit complexity of sensory processing in

biological neural systems and neuromorphic engineering. The new

complexity measure is applied in this paper to two basic

computational problems that arise in translation- and

scale-invariant pattern recognition, and hence appear ...
more >>>

Robert Albin Legenstein

One of the most basic pattern recognition problems is whether a

certain local feature occurs in some linear array to the left of

some other local feature. We construct in this article circuits that

solve this problem with an asymptotically optimal number of

threshold gates. Furthermore it is shown that ...
more >>>

Ronald Cramer, Victor Shoup

We present several new and fairly practical public-key encryption

schemes and prove them secure against

adaptive chosen ciphertext attack. One scheme is based on Paillier's

Decision Composite Residuosity (DCR) assumption,

while another is based in the classical Quadratic Residuosity (QR)

assumption. The analysis is in the standard ...
more >>>

Beate Bollig, Philipp Woelfel, Stephan Waack

Branching programs are a well-established computation model

for Boolean functions, especially read-once branching programs

have been studied intensively. Exponential lower bounds for

deterministic and nondeterministic read-once branching programs

are known for a long time. On the other hand, the problem of

proving superpolynomial lower bounds ...
more >>>

Joshua Buresh-Oppenheim, David Mitchell

We prove exponential separations between the sizes of

particular refutations in negative, respectively linear, resolution and

general resolution. Only a superpolynomial separation between negative

and general resolution was previously known. Our examples show that there

is no strong relationship between the size and width of refutations in

negative and ...
more >>>

Alexander Razborov

We show that every resolution proof of the {\em functional} version

$FPHP^m_n$ of the pigeonhole principle (in which one pigeon may not split

between several holes) must have size $\exp\of{\Omega\of{\frac n{(\log

m)^2}}}$. This implies an $\exp\of{\Omega(n^{1/3})}$ bound when the number

of pigeons $m$ is arbitrary.

Robert Albin Legenstein

In this article we consider a basic problem in the layout of

VLSI-circuits, the channel-routing problem in the knock-knee mode.

We show that knock-knee channel routing with 3-terminal nets is

NP-complete and thereby settling a problem that was open for more

than a decade. In 1987, Sarrafzadeh showed that knock-knee ...
more >>>

Andrei Krokhin, Peter Jeavons, Peter Jonsson

We study interval-valued constraint satisfaction problems (CSPs),

in which the aim is to find an assignment of intervals to a given set of

variables subject to constraints on the relative positions of intervals.

Many well-known problems such as Interval Graph Recognition

and Interval Satisfiability can be considered as examples of ...
more >>>

Matthias Krause

Many of the keystream generators which are used in practice are LFSR-based in the sense

that they produce the keystream according to a rule $y=C(L(x))$,

where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel

linear feedback shift registers (LFSRs),

and $C$ denotes ...
more >>>

Michele Zito

We prove that, with high probability, the space complexity of refuting

a random unsatisfiable boolean formula in $k$-CNF on $n$

variables and $m = \Delta n$ clauses is

$O(n \cdot \Delta^{-\frac{1}{k-2}})$.

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

We prove that if a linear error correcting code

$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can

be probabilistically reconstructed by looking at two entries of a

corrupted codeword, then $m = 2^{\Omega(n)}$. We also present

several extensions of this result.

We show a reduction from the ... more >>>

Palash Sarkar

We introduce the idea of pushdown automata with the ability to flip

its stack. By bounding the number of times the stack can be flipped

we obtain a hierarchy of language classes from the context free

languages to the recursively enumerable languages. We show that each

class in ...
more >>>

Tsuyoshi Morioka

We present a new framework for the study of search problems and their

definability in bounded arithmetic. We identify two notions of

complexity of search problems: verification complexity and

computational complexity. Notions of exact solvability and exact

reducibility are developed, and exact $\Sigma^b_i$-definability of

search problems in bounded arithmetic ...
more >>>

Nikolay Vereshchagin

We present a simplified proof of Solovay-Calude-Coles theorem

stating that there is an enumerable undecidable set with the

following property: prefix

complexity of its initial segment of length n is bounded by prefix

complexity of n (up to an additive constant).

Gerhard J. Woeginger

We derive results of the following flavor:

If a combinatorial optimization problem can be formulated via a dynamic

program of a certain structure and if the involved cost and transition

functions satisfy certain arithmetical and structural conditions, then

the optimization problem automatically possesses a fully polynomial time

approximation scheme (FPTAS).

Gerhard J. Woeginger

We study online bounded space bin packing in the resource

augmentation model of competitive analysis.

In this model, the online bounded space packing algorithm has

to pack a list L of items in (0,1] into a small number of

bins of size b>=1.

Its performance is measured by comparing the ...
more >>>

Nikolay Vereshchagin

Assume that for almost all n Kolmogorov complexity

of a string x conditional to n is less than m.

We prove that in this case

there is a program of size m+O(1) that given any sufficiently large

n outputs x.

Bruno Durand, Alexander Shen, Nikolay Vereshchagin

We study different notions of descriptive complexity of

computable sequences. Our main result states that if for almost all

n the Kolmogorov complexity of the n-prefix of an infinite

binary sequence x conditional to n

is less than m then there is a program of length

m^2+O(1) that for ...
more >>>

Alexander Shen, Nikolay Vereshchagin

We define Kolmogorov complexity of a set of strings as the minimal

Kolmogorov complexity of its element. Consider three logical

operations on sets going back to Kolmogorov

and Kleene:

(A OR B) is the direct sum of A,B,

(A AND B) is the cartesian product of A,B,

more >>>

Andrej Muchnik, Nikolay Vereshchagin

We invistigate what is the minimal length of

a program mapping A to B and at the same time

mapping C to D (where A,B,C,D are binary strings). We prove that

it cannot be expressed

in terms of Kolmogorv complexity of A,B,C,D, their pairs (A,B), (A,C),

..., their ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

In parallel and distributed computing scheduling low level tasks

on the available hardware is a fundamental problem.

Traditionally, one has assumed that the set of tasks to be executed

is known beforehand.

Then the scheduling constraints are given by a precedence graph.

Nodes represent the elementary tasks ...
more >>>

Oded Goldreich

Following Dwork, Naor, and Sahai (30th STOC, 1998),

we consider concurrent execution of protocols in a

semi-synchronized network. Specifically, we assume that each party

holds a local clock such that a constant bound on the relative rates

of these clocks is a-priori known, and consider protocols that

employ ...
more >>>

Till Tantau

Deciding whether a vertex in a graph is reachable from another

vertex has been studied intensively in complexity theory and is

well understood. For common types of graphs like directed graphs,

undirected graphs, dags or trees it takes a (possibly

nondeterministic) logspace machine to decide the reachability

problem, and ...
more >>>

Boaz Barak, Oded Goldreich

We put forward a new type of

computationally-sound proof systems, called universal-arguments,

which are related but different from both CS-proofs (as defined

by Micali) and arguments (as defined by Brassard, Chaum and

Crepeau). In particular, we adopt the instance-based

prover-efficiency paradigm of CS-proofs, but follow the

computational-soundness condition of ...
more >>>

Jonas Holmerin

We prove that Minimum vertex cover on 4-regular hyper-graphs (or

in other words, hitting set where all sets have size exactly 4),

is hard to approximate within 2 - \epsilon.

We also prove that the maximization version, in which we

are allowed to pick ...
more >>>

Hubie Chen

The boolean circuit complexity classes

AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied

intensely. Other than NC^1, they are defined by constant-depth

circuits of polynomial size and unbounded fan-in over some set of

allowed gates. One reason for interest in these classes is that they

contain the ...
more >>>

Jörg Rothe

In this tutorial, selected topics of cryptology and of

computational complexity theory are presented. We give a brief overview

of the history and the foundations of classical cryptography, and then

move on to modern public-key cryptography. Particular attention is

paid to cryptographic protocols and the problem of constructing ...
more >>>

Piotr Berman, Marek Karpinski

We give improved trade-off results on approximating general

minimum cost scheduling problems.

Ke Yang

In this paper, we study the problem of using statistical

query (SQ) to learn highly correlated boolean functions, namely, a

class of functions where any

pair agree on significantly more than a fraction 1/2 of the inputs.

We give a limit on how well ...
more >>>

Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis

In this paper, we investigate and analyze for the first time the

stability properties of heterogeneous networks, which use a

combination of different universally stable queueing policies for

packet routing, in the Adversarial Queueing model. We

interestingly prove that the combination of SIS and LIS policies,

LIS and NTS policies, ...
more >>>

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating

r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on

n variables up to an additive error \epsilon n^r.We prove a new

general paradigm in that it suffices, for a given set of constraints,

to pick a small uniformly random ...
more >>>

Philipp Woelfel

We present a new lower bound technique for two types of restricted

Branching Programs (BPs), namely for read-once BPs (BP1s) with

restricted amount of nondeterminism and for (1,+k)-BPs. For this

technique, we introduce the notion of (strictly) k-wise l-mixed

Boolean functions, which generalizes the concept of l-mixedness ...
more >>>

Oded Goldreich

Using known results regarding PCP,

we present simple proofs of the inapproximability

of vertex cover for hypergraphs.

Specifically, we show that

(1) Approximating the size of the minimum vertex cover

in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.

(2) Approximating the size ...
more >>>

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

It is a known approach to translate propositional formulas into

systems of polynomial inequalities and to consider proof systems

for the latter ones. The well-studied proof systems of this kind

are the Cutting Planes proof system (CP) utilizing linear

inequalities and the Lovasz-Schrijver calculi (LS) utilizing

quadratic ...
more >>>

Irit Dinur, Shmuel Safra

We show Minimum Vertex Cover NP-hard to approximate to within a factor

of 1.3606. This improves on the previously known factor of 7/6.