The classes of languages accepted by nondeterministic polynomial-time
Turing machines (NP machines, in short) that have restricted access to
an NP oracle --- the machines can ask k queries to the NP oracle and
the answer they receive is the number of queries ... more >>>

We show that all sets complete for NC$^1$ under AC$^0$
reductions are isomorphic under AC$^0$-computable isomorphisms.

Although our proof does not generalize directly to other
complexity classes, we do show that, for all complexity classes C
closed under NC$^1$-computable many-one reductions, the sets ... more >>>

We present a polynomial quantum algorithm for the Abelian stabilizer problem
which includes both factoring and the discrete logarithm. Thus we extend famous
Shor's results. Our method is based on a procedure for measuring an eigenvalue
of a unitary operator. Another application of this
procedure is a polynomial ... more >>>

We study the complexity of computing Boolean functions using AND, OR
and NOT gates. We show that a circuit of depth $d$ with $S$ gates can
be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where
$\epsilon(d) = 4^{-d}$) of its input values. This implies a
superlinear size lower bound ... more >>>

We show that examinations of the expressive power of logical formulae
enriched by Lindstroem quantifiers over ordered finite structures
have a well-studied complexity-theoretic counterpart: the leaf
language approach to define complexity classes. Model classes of
formulae with Lindstroem quantifiers are nothing else than leaf
language definable sets. Along the ... more >>>

This note connects two topics of Complexity Theory: The
topic of succinct circuit representations initiated by
Galperin and Wigderson and the topic of leaf languages
initiated by Bovet, Crescenzi, and Silvestri. It will be
shown for any language that its succinct version is
more >>>

We give a random class of n dimensional lattices so that, if
there is a probabilistic polynomial time algorithm which finds a short
vector in a random lattice with a probability of at least 1/2
then there is also a probabilistic polynomial time algorithm which
solves the following three ... more >>>

It has been shown in previous recent work that
multiplicity automata are predictable from multiplicity
and equivalence queries. In this paper we generalize
related notions in a matrix representation
and obtain a basis for the solution
of a number of open problems in learnability theory.
Membership queries are generalized ... more >>>

This paper studies the learnability of branching programs and small depth
circuits with modular and threshold gates in both the exact and PAC learning
models with and without membership queries. Some of the results extend earlier
works in [GG95,ERR95,BTW95]. The main results are as follows. For
branching programs we ... more >>>

Reducibility concepts are fundamental in complexity theory.
Usually, they are defined as follows: A problem P is reducible
to a problem S if P can be computed using a program or device
for S as a subroutine. However, in the case of such restricted
models as ... more >>>

We define the sharply bounded hierarchy, SBHQL, a hierarchy of
classes within P, using quasilinear-time computation and
quantification over values of length log n. It generalizes the
limited nondeterminism hierarchy introduced by Buss and Goldsmith,
while retaining the invariance properties. The new hierarchy has
several alternative characterizations.

We define ... more >>>

A visual cryptography scheme for a
set $\cal P $ of $n$ participants is a method to encode a secret
image $SI$ into $n$ shadow images called shares, where each participant in
$\cal P$ receives one share. Certain qualified subsets of participants
can ``visually'' recover the secret image, but
other, ... more >>>

It is shown that the PL hierarchy defined in terms of the
standard Ruzzo-Simon-Tompa relativization collapses to PL.

In 1978, Hartmanis conjectured that there exist no sparse complete sets
for P under logspace many-one reductions. In this paper, in support of
the conjecture, it is shown that if P has sparse hard sets under logspace
many-one reductions, then P is included in DPSPACE[log^2 n].

We investigate the computational complexity of two classes of
combinatorial optimization problems related to linear systems
and study the relationship between their approximability properties.
In the first class (MIN ULR) one wishes, given a possibly infeasible
system of linear relations, to find ... more >>>

We provide new non-approximability results for the restrictions
of the min-VC problem to bounded-degree, sparse and dense graphs.
We show that for a sufficiently large B, the recent 16/15 lower
bound proved by Bellare et al. extends with negligible
loss to graphs with bounded ... more >>>

The ``log rank'' conjecture consists in the question how exact
the deterministic communication complexity of a problem can be
determinied in terms of algebraic invarants of the communication
matrix of this problem. In the following, we answer this question
in the context of modular communication complexity. ... more >>>

We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time ... more >>>

We show that the class of sets which can be polynomial
time truth table reduced to some $p$-superterse sets has
$p$-measure 0. Hence, no $P$-selective set is $\le_{tt}^p$-hard
for $E$. Also we give a partial affirmative answer to
the conjecture by Beigel, Kummer and ... more >>>

Many Boolean functions have short representations by OBDDs (ordered
binary decision diagrams) if appropriate variable orderings are used.
For tree-like circuits, which may contain EXOR-gates, it is proved
that some depth first traversal leads to an optimal variable ordering.
Moreover, an optimal variable ordering and the resulting OBDD
can ... more >>>

A very recent paper by Caussinus, McKenzie, Therien, and Vollmer
[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0
is properly contained in the counting hierarchy. Thus, [CMTV] shows
that there are problems in ModPH that require superpolynomial-size
uniform ACC^0 ... more >>>

We characterize the complexity of some natural and important
problems in linear algebra. In particular, we identify natural
complexity classes for which the problems of (a) determining if a
system of linear equations is feasible and (b) computing the rank of
an integer matrix, ... more >>>

Recently one has started to investigate the
computational power of spiking neurons (also called ``integrate and
fire neurons''). These are neuron models that are substantially
more realistic from the biological point of view than the
ones which are traditionally employed in artificial neural nets.
It has turned out that the ... more >>>

We prove a general combinatorial lower bound on the
size of monotone circuits. The argument is different from
Razborov's method of approximation, and is based on Sipser's
notion of `finite limit' and Haken's `counting bottlenecks' idea.
We then apply this criterion to the ... more >>>

Is there an NP function that, when given a satisfiable formula
as input, outputs one satisfying assignment uniquely? That is, can a
nondeterministic function cull just one satisfying assignment from a
possibly exponentially large collection of assignments? We show that if
there is such a nondeterministic function, then the polynomial ... more >>>

In 1978, Schaefer considered a subclass of languages in
NP and proved a ``dichotomy theorem'' for this class. The subclass
considered were problems expressible as ``constraint satisfaction
problems'', and the ``dichotomy theorem'' showed that every language in
this class is either in P, or is NP-hard. This result is in ... more >>>

The efficient construction of Hitting Sets for non trivial classes
of boolean functions is a fundamental problem in the theory
of derandomization. Our paper presents a new method to efficiently
construct Hitting Sets for the class of systems of boolean linear
functions. Systems of boolean linear functions ... more >>>

We develop an analytic framework based on
linear approximation and point out how a number of complexity
related questions --
on circuit and communication
complexity lower bounds, as well as
pseudorandomness, learnability, and general combinatorics
of Boolean functions --
fit neatly into this framework. ... more >>>

The computational power of formal models for
networks of spiking neurons is compared with
that of other neural network models based on
McCulloch Pitts neurons (i.e. threshold gates)
respectively sigmoidal gates. In particular it
is shown that networks of spiking neurons are
... more >>>

We investigate the computational complexity of the Boolean Isomorphism problem (BI):
on input of two Boolean formulas F and G decide whether there exists a permutation of
the variables of G such that F and G become equivalent.

Our main result is a one-round interactive proof ... more >>>

The paper analyzes in terms of polynomial time many-one reductions
the computational complexity of several natural equivalence
relations on Boolean functions which derive from replacing
variables by expressions. Most of these computational problems
turn out to be between co-NP and Sigma^p_2.

Linear threshold elements are the basic building blocks of artificial neural
networks. A linear threshold element computes a function that is a sign of a
weighted sum of the input variables. The weights are arbitrary integers;
actually, they can be very big integers---exponential in the number of the
input variables. ... more >>>

We define and examine several probabilistic operators ranging over sets
(i.e., operators of type 2), among them the formerly studied
ALMOST-operator. We compare their power and prove that they all coincide
for a wide variety of classes. As a consequence, we characterize the
ALMOST-operator which ranges over infinite objects ... more >>>

Branching programs (b.p.'s) or decision diagrams are a general
graph-based model of sequential computation. B.p.'s of polynomial
size are a nonuniform counterpart of LOG. Lower bounds for
different kinds of restricted b.p.'s are intensively investigated.
An important restriction are so called 1-b.p.'s, where each
computation reads each input bit at ... more >>>

We first consider so-called {\em $(1,+s)$-branching programs}
in which along every consistent path at most $s$ variables are tested
more than once. We prove that any such program computing a
characteristic function of a linear code $C$ has size at least
more >>>

We provide a compendium of problems that are complete for
symmetric logarithmic space (SL). Complete problems are one method
of studying this class for which programming is nonintuitive. A
number of the problems in the list were not previously known to be
complete. A ... more >>>

We investigate the computational complexity of the
isomorphism problem for one-time-only branching programs (BP1-Iso):
on input of two one-time-only branching programs B and B',
decide whether there exists a permutation of the variables of B'
such that it becomes equivalent to B.

Our main result is a two-round interactive ... more >>>

We consider the size of circuits which perfectly hash
an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$
into $\bitset^m$.
We observe that, in general, the size of such circuits is
exponential in $2k-m$,
and provide a matching upper bound.

Recently Ajtai described a construction of one-way functions whose
security is equivalent to the difficulty of some well known approximation
problems in lattices. We show that essentially the same
construction can also be used to obtain collision-free hashing.

We show that a fully polynomial time approximation scheme given
for an optimization problem can always be simply modified to a
polynomial time algorithm solving the problem optimally if the
computation model is the deterministic Turing Machine or the
logarithmic cost RAM and ... more >>>

It is well known that the optimal solution for
searching in
a finite total order set is the binary search.
In the binary search we
divide the set into two ``halves'', by querying the middle
element, and continue the search on the suitable half.
What is the equivalent of binary ... more >>>

We study EP, the subclass of NP consisting of those
languages accepted by NP machines that when they accept always have a
number of accepting paths that is a power of two. We show that the
negation equivalence problem for OBDDs (ordered binary decision
diagrams) ... more >>>

We consider the Traveling Salesperson Problem (TSP) restricted
to Euclidean spaces of dimension at most k(n), where n is the number of
cities. We are interested in the relation between the asymptotic growth of
k(n) and the approximability of the problem. We show that the problem is ... more >>>

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))
is very complicated.
One source of difficulty is the technically involved
analysis of low-degree tests.
Here, we refer to the difficulty of obtaining strong results
regarding low-degree tests; namely, results of the type obtained and
used by ... more >>>

We present a deterministic algorithm running in space
O((log^2 n)/loglog n) solving the connectivity problem
on strongly unambiguous graphs. In addition, we present
an O(log n) time-bounded algorithm for this problem
running on a parallel pointer machine.

--
Scalar product estimates have so far been used in
proving several unweighted threshold lower bounds.
We show that if a basis set of Boolean functions satisfies
certain weak stability conditions, then
scalar product estimates
yield lower bounds for the size of weighted thresholds
of these basis functions.
Stable ... more >>>

Branching programs (b.p.'s) or decision diagrams are a general
graph-based model of sequential computation. The b.p.'s of
polynomial size are a nonuniform counterpart of LOG. Lower bounds
for different kinds of restricted b.p.'s are intensively
investigated. An important restriction are so called $k$-b.p.'s,
where each computation reads each input ... more >>>

We demonstrate the use of Kolmogorov complexity in average case
analysis of algorithms through a classical example: adding two $n$-bit
numbers in $\ceiling{\log_2{n}}+2$ steps on average. We simplify the
analysis of Burks, Goldstine, and von Neumann in 1946 and
(in more complete forms) of Briley and of Schay.

The fundamental assumption in the classical theory of
dissemination of information in interconnection networks
(gossiping and broadcasting) is that atomic pieces of information
are communicated. We show that, under suitable assumptions about
the way processors may communicate, computing an n-ary function
that has a "critical input" (e.g., ... more >>>

The architecture of 'mesh of buses' is an important model in parallel computing. Its main advantage is that the additional broadcast capability can be used to overcome the main disadvantage of the mesh, namely its relatively large diameter. We show that the addition of buses indeed accelerates routing times. Furthermore, ... more >>>

The Graph Clustering Problem is parameterized by a sequence
of positive integers, $m_1,...,m_t$.
The input is a sequence of $\sum_{i=1}^{t}m_i$ graphs,
and the question is whether the equivalence classes
under the graph isomorphism relation have sizes which match
the sequence of parameters.
In this note
we show ... more >>>

We present the first worst-case hardness conditions
on the circuit complexity of EXP functions which are
sufficient to obtain P=BPP. In particular, we show that
from such hardness conditions it is possible to construct
quick Hitting Sets Generators with logarithmic prize.
... more >>>

We present a new proposal for a trapdoor one-way function,
from which we derive public-key encryption and digital
signatures. The security of the new construction is based
on the conjectured computational difficulty of lattice-reduction
problems, providing a possible alternative to existing
more >>>

In this paper, we consider the question of determining whether
a function $f$ has property $P$ or is $\e$-far from any
function with property $P$.
The property testing algorithm is given a sample of the value
of $f$ on instances drawn according to some distribution.
In some cases,
more >>>

We prove $\Omega (n^2)$ complexity \emph{lower bound} for the
general model of \emph{randomized computation trees} solving
the \emph{Knapsack Problem}, and more generally \emph{Restricted
Integer Programming}. This is the \emph{first nontrivial} lower
bound proven for this model of computation. The method of the ... more >>>

This paper solves the open problem of exact learning
geometric objects bounded by hyperplanes (and more generally by any constant
degree algebraic surfaces) in the constant
dimensional space from equivalence queries only (i.e., in the on-line learning
model).

We present a novel approach that allows, under ... more >>>

Rice's Theorem says that every nontrivial semantic property
of programs is undecidable. It this spirit we show the following:
Every nontrivial absolute (gap, relative) counting property of circuits
is UP-hard with respect to polynomial-time Turing reductions.

Decision trees are a very general computation model.
Here the problem is to identify a Boolean function $f$ out of a given
set of Boolean functions $F$ by asking for the value of $f$ at adaptively
chosen inputs.
For classes $F$ consisting of functions which may be obtained from one
more >>>

In this paper we study the approximability of boolean constraint
satisfaction problems. A problem in this class consists of some
collection of ``constraints'' (i.e., functions
$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set
of constraints applied to specified subsets of $n$ boolean
variables. Schaefer earlier ... more >>>

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,
connected by k links to form a linear array, compute a function f(x,y), for
inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and
y is only known to P_k; the intermediate ... more >>>

This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F ... more >>>

We present a probabilistic public key cryptosystem which is
secure unless the following worst-case lattice problem can be solved in
polynomial time:
"Find the shortest nonzero vector in an n dimensional lattice
L where the shortest vector v is unique in the sense that any other
vector whose ... more >>>

The study of the approximability properties of NP-hard
optimization problems has recently made great advances mainly due
to the results obtained in the field of proof checking. In a
recent breakthrough the APX-completeness of several important
optimization problems is proved, thus reconciling `two distinct
views of ... more >>>

We present a simple proof to the existence of a probability ensemble
with tiny support which cannot be distinguished from the uniform ensemble
by any recursive computation.
Since the support is tiny (i.e, sub-polynomial),
this ensemble can be distinguish from the uniform ensemble
by a (non-uniform) family ... more >>>