Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

REPORTS > 2001:
All reports in year 2001:
TR01-001 | 31st December 2000
Jin-Yi Cai

Essentially every unimodular matrix defines an expander

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.

more >>>

TR01-002 | 6th December 2000
Venkatesan Guruswami

Constructions of Codes from Number Fields

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 >>>

TR01-004 | 13th October 2000
Tobias Gärtner, Günter Hotz

Recursive analytic functions of a complex variable

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 >>>

TR01-005 | 27th October 2000
Pascal Tesson, Denis Thérien

The Computing Power of Programs over Finite Monoids

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 >>>

TR01-006 | 18th October 2000
Rocco Servedio

On Learning Monotone DNF under Product Distributions

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 >>>

TR01-007 | 7th December 2000
Vered Rosen

On the Security of Modular Exponentiation

Comments: 1

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 >>>

TR01-008 | 6th November 2000
Eldar Fischer

On the strength of comparisons in property testing

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 >>>

TR01-009 | 5th January 2001
Ronen Shaltiel

Towards proving strong direct product theorems

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 >>>

TR01-010 | 25th January 2001
Oded Goldreich, Luca Trevisan

Three Theorems regarding Testing Graph Properties.

Revisions: 1

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 >>>

TR01-011 | 21st January 2001
Dima Grigoriev, Edward Hirsch

Algebraic proof systems over formulas

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 >>>

TR01-012 | 4th January 2001
Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

Algorithms for SAT and Upper Bounds on Their Complexity

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 >>>

TR01-013 | 2nd February 2001
Michal Koucky

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

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.

more >>>

TR01-014 | 7th February 2001
Marcos Kiwi, Frederic Magniez, Miklos Santha

Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey

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 >>>

TR01-015 | 9th February 2001
Amos Beimel, Yuval Ishai

Information-Theoretic Private Information Retrieval: A Unified Construction

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 >>>

TR01-016 | 22nd December 2000
Ran Canetti

A unified framework for analyzing security of protocols

Revisions: 5

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 >>>

TR01-017 | 14th February 2001
Petr Savicky, Detlef Sieling

A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

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 >>>

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

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 >>>

TR01-019 | 2nd March 2001
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

The Communication Complexity of Enumeration, Elimination, and Selection

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 >>>

TR01-020 | 20th February 2001
N. S. Narayanaswamy, C.E. Veni Madhavan

Lower Bounds for OBDDs and Nisan's pseudorandom generator

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 >>>

TR01-021 | 7th March 2001
Ran Raz

Resolution Lower Bounds for the Weak Pigeonhole Principle

Revisions: 1

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$).

more >>>

TR01-022 | 15th February 2001
Rahul Santhanam

On segregators, separators and time versus space

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 >>>

TR01-023 | 13th March 2001
Jochen Alber, Henning Fernau, Rolf Niedermeier

Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revisions: 1

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 >>>

TR01-024 | 1st March 2001
Stephen Cook, Antonina Kolokolova

A second-order system for polynomial-time reasoning based on Graedel's theorem

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 >>>

TR01-025 | 28th March 2001
Piotr Berman, Marek Karpinski

Approximating Minimum Unsatisfiability of Linear Equations

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 >>>

TR01-026 | 3rd April 2001
Piotr Berman, Marek Karpinski

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

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 >>>

TR01-027 | 23rd March 2001
Marius Zimand

Probabilistically Checkable Proofs The Easy Way

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 >>>

TR01-028 | 16th March 2001
Thanh Minh Hoang, Thomas Thierauf

The Complexity of the Minimal Polynomial

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 >>>

TR01-029 | 27th March 2001
Denis Xavier Charles

A Note on Subgroup Membership Problem for PSL(2,p).

Comments: 1

We show that there are infinitely many primes $p$, such
that the subgroup membership problem for PSL(2,p) belongs
to $\NP \cap \coNP$.

more >>>

TR01-030 | 25th April 2001
Jin-Yi Cai

S_2^p \subseteq ZPP^{NP}

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 >>>

TR01-031 | 5th April 2001
Eli Ben-Sasson, Nicola Galesi

Space Complexity of Random Formulae in Resolution

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 >>>

TR01-032 | 3rd April 2001
A. Pavan, Alan L. Selman

Separation of NP-completeness Notions

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 >>>

TR01-033 | 27th April 2001
Eric Allender, David Mix Barrington, William Hesse

Uniform Circuits for Division: Consequences and Problems

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 >>>

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

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 >>>

TR01-035 | 15th April 2001
Amir Shpilka

Affine Projections of Symmetric Polynomials

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 >>>

TR01-036 | 2nd May 2001
Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Extractors from Reed-Muller Codes

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 >>>

TR01-037 | 21st February 2001
Rustam Mubarakzjanov

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

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 >>>

TR01-038 | 14th May 2001
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

Approximating Schedules for Dynamic Graphs Efficiently

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 >>>

TR01-039 | 18th May 2001
Stasys Jukna, Stanislav Zak

On Uncertainty versus Size in Branching Programs

Revisions: 1

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 >>>

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")

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 >>>

TR01-041 | 23rd May 2001
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay

Time-Space Tradeoffs in the Counting Hierarchy

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 >>>

TR01-042 | 31st May 2001
Marek Karpinski

Approximating Bounded Degree Instances of NP-Hard Problems

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 >>>

TR01-043 | 26th April 2001
Mikhail V. Vyugin, Vladimir Vyugin

Predictive complexity and information

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 >>>

TR01-044 | 14th June 2001
Pavel Pudlak

On reducibility and symmetry of disjoint NP-pairs

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 >>>

TR01-045 | 26th April 2001
Michael Schmitt

Neural Networks with Local Receptive Fields and Superlinear VC Dimension

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 >>>

TR01-046 | 2nd July 2001
Oded Goldreich, Salil Vadhan, Avi Wigderson

On Interactive Proofs with a Laconic Prover

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 >>>

TR01-047 | 3rd July 2001
Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

1.375-Approximation Algorithm for Sorting by Reversals

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 >>>

TR01-048 | 3rd June 2001
Jui-Lin Lee

Branching program, commutator, and icosahedron, part I

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 >>>

TR01-049 | 11th July 2001
Stasys Jukna, Georg Schnitger

On Multi-Partition Communication Complexity of Triangle-Freeness

Comments: 2

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 >>>

TR01-050 | 24th June 2001
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

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 >>>

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

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 >>>

TR01-052 | 26th April 2001
Mikhail V. Vyugin, Vladimir Vyugin

Non-linear Inequalities between Predictive and Kolmogorov Complexity

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 >>>

TR01-053 | 17th July 2001
Piotr Berman, Marek Karpinski

Efficient Amplifiers and Bounded Degree Optimization

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 >>>

TR01-054 | 12th April 2001
Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir

On the Complexity of Positional Sequencing by Hybridization

In sequencing by hybridization (SBH),
one has to reconstruct a sequence
from its $l$-long substrings.
SBH was proposed as
an alternative to
DNA sequencing approaches, but in its original form the method
not competitive.
Positional SBH (PSBH) is a recently proposed
enhancement ... more >>>

TR01-055 | 26th July 2001
Alexander Razborov

Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

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 >>>

TR01-056 | 6th August 2001
Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart

An Exponential Separation between Regular and General Resolution

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

more >>>

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

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 >>>

TR01-058 | 28th August 2001
Stasys Jukna

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

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 >>>

TR01-059 | 20th July 2001
Elvira Mayordomo

A Kolmogorov complexity characterization of constructive Hausdorff dimension

Revisions: 3

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.

more >>>

TR01-060 | 23rd August 2001
Amir Shpilka

Lower bounds for matrix product

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 >>>

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

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 >>>

TR01-062 | 9th September 2001
Moni Naor, Kobbi Nissim

Communication Complexity and Secure Function Evaluation

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 >>>

TR01-063 | 5th August 2001
Michal Parnas, Dana Ron, Alex Samorodnitsky

Proclaiming Dictators and Juntas or Testing Boolean Formulae

Revisions: 1

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 >>>

TR01-064 | 10th September 2001
Moni Naor, Omer Reingold, Alon Rosen

Pseudo-Random Functions and Factoring

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 >>>

TR01-065 | 10th August 2001
Chandra Chekuri, Sanjeev Khanna

Approximation Schemes for Preemptive Weighted Flow Time

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 >>>

TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

On Multipartition Communication Complexity

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 >>>

TR01-067 | 18th September 2001
Hubie Chen

Polynomial Programs and the Razborov-Smolensky Method

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 >>>

TR01-068 | 19th September 2001
Philippe Moser

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

Revisions: 1

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 >>>

TR01-069 | 24th October 2001
Robert Albin Legenstein

Optimizing the Layout of a Balanced Tree

Revisions: 1

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 >>>

TR01-070 | 24th October 2001
Robert Albin Legenstein

Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing

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 >>>

TR01-071 | 24th October 2001
Robert Albin Legenstein

Neural Circuits for Pattern Recognition with Small Total Wire Length

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 >>>

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

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 >>>

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

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 >>>

TR01-074 | 12th October 2001
Joshua Buresh-Oppenheim, David Mitchell

Linear and Negative Resolution are Weaker than Resolution

Comments: 1

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 >>>

TR01-075 | 2nd November 2001
Alexander Razborov

Resolution Lower Bounds for the Weak Functional Pigeonhole Principle

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.

more >>>

TR01-076 | 24th October 2001
Robert Albin Legenstein

On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets

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 >>>

TR01-077 | 24th September 2001
Andrei Krokhin, Peter Jeavons, Peter Jonsson

The complexity of constraints on intervals and lengths

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 >>>

TR01-078 | 6th November 2001
Matthias Krause

BDD-based Cryptanalysis of Keystream Generators

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 >>>

TR01-079 | 6th September 2001
Michele Zito

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

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}})$.

more >>>

TR01-080 | 14th November 2001
Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3

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 >>>

TR01-081 | 8th August 2001
Palash Sarkar

Pushdown Automaton with the Ability to Flip its Stack

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 >>>

TR01-082 | 24th September 2001
Tsuyoshi Morioka

Classification of Search Problems and Their Definability in Bounded Arithmetic

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 >>>

TR01-083 | 29th October 2001
Nikolay Vereshchagin

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

Revisions: 1

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).

more >>>

TR01-084 | 1st October 2001
Gerhard J. Woeginger

When does a dynamic programming formulation guarantee the existence of an FPTAS?

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).

... more >>>

TR01-085 | 1st October 2001
Gerhard J. Woeginger

Resource augmentation for online bounded space bin packing

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 >>>

TR01-086 | 29th October 2001
Nikolay Vereshchagin

Kolmogorov Complexity Conditional to Large Integers

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.

more >>>

TR01-087 | 29th October 2001
Bruno Durand, Alexander Shen, Nikolay Vereshchagin

Descriptive complexity of computable sequences

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 >>>

TR01-088 | 29th October 2001
Alexander Shen, Nikolay Vereshchagin

Logical operations and Kolmogorov complexity

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 >>>

TR01-089 | 29th October 2001
Andrej Muchnik, Nikolay Vereshchagin

Logical operations and Kolmogorov complexity. II

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 >>>

TR01-090 | 28th November 2001
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

Dynamic Process Graphs and the Complexity of Scheduling

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 >>>

TR01-091 | 27th November 2001
Oded Goldreich

Concurrent Zero-Knowledge With Timing, Revisited

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 >>>

TR01-092 | 2nd October 2001
Till Tantau

A Note on the Complexity of the Reachability Problem for Tournaments

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 >>>

TR01-093 | 2nd December 2001
Boaz Barak, Oded Goldreich

Universal Arguments and their Applications

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 >>>

TR01-094 | 3rd December 2001
Jonas Holmerin

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

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 >>>

TR01-095 | 12th November 2001
Hubie Chen

Arithmetic Versions of Constant Depth Circuit Complexity Classes

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 >>>

TR01-096 | 21st November 2001
Jörg Rothe

Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial

Revisions: 1

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 >>>

TR01-097 | 11th December 2001
Piotr Berman, Marek Karpinski

Improved Approximations for General Minimum Cost Scheduling

We give improved trade-off results on approximating general
minimum cost scheduling problems.

more >>>

TR01-098 | 19th November 2001
Ke Yang

On Learning Correlated Boolean Functions Using Statistical Query

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 >>>

TR01-099 | 1st October 2001
Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis

The Range of Stability for Heterogeneous and FIFO Queueing Networks

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 >>>

TR01-100 | 14th December 2001
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Random Sampling and Approximation of MAX-CSP Problems

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 >>>

TR01-101 | 14th December 2001
Philipp Woelfel

A Lower Bound Technique for Restricted Branching Programs and Applications

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 >>>

TR01-102 | 18th December 2001
Oded Goldreich

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

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 >>>

TR01-103 | 14th December 2001
Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

Complexity of semi-algebraic proofs

Revisions: 3

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 >>>

TR01-104 | 17th December 2001
Irit Dinur, Shmuel Safra

The Importance of Being Biased

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.

more >>>

ISSN 1433-8092 | Imprint