All reports in year 1996:

__
TR96-001
| 10th January 1996
__

Manindra Agrawal, Richard Beigel, Thomas Thierauf#### Modulo Information from Nonadaptive Queries to NP

__
TR96-002
| 10th January 1996
__

Manindra Agrawal, Eric Allender#### An Isomorphism Theorem for Circuit Complexity

__
TR96-003
| 4th December 1995
__

Alexei Kitaev#### Quantum measurements and the Abelian Stabilizer Problem

__
TR96-004
| 18th January 1996
__

Shiva Chaudhuri, Jaikumar Radhakrishnan#### Deterministic Restrictions in Circuit Complexity

__
TR96-005
| 9th January 1996
__

Hans-Joerg Burtschick, Heribert Vollmer#### Lindstroem Quantifiers and Leaf Language Definability

Revisions: 1

__
TR96-006
| 24th January 1996
__

Bernd Borchert, Antoni Lozano#### Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept

__
TR96-007
| 29th January 1996
__

Miklos Ajtai#### Generating Hard Instances of Lattice Problems

Comments: 1

__
TR96-008
| 22nd January 1996
__

F. Bergadano, N.H. Bshouty, Stefano Varricchio#### Learning Multivariate Polynomials from Substitution and Equivalence Queries

__
TR96-009
| 17th January 1996
__

Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio#### On Learning Branching Programs and Small Depth Circuits

__
TR96-010
| 9th February 1996
__

Christoph Meinel, Anna Slobodova#### An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams

Revisions: 1

__
TR96-011
| 29th January 1996
__

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith#### Sharply Bounded Alternation within P

__
TR96-012
| 14th December 1995
__

Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson#### Visual Cryptography for General Access Structures

__
TR96-013
| 14th February 1996
__

Mitsunori Ogihara#### The PL Hierarchy Collapses

__
TR96-014
| 14th February 1996
__

Mitsunori Ogihara#### Sparse Hard Sets for P Yields Space-Efficient Algorithms

__
TR96-015
| 12th December 1995
__

Edoardo Amaldi, Viggo Kann#### On the approximability of some NP-hard minimization problems for linear systems

__
TR96-016
| 6th February 1996
__

Andrea E. F. Clementi, Luca Trevisan#### Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints

__
TR96-017
| 19th February 1996
__

Christoph Meinel, Stephan Waack#### The ``Log Rank'' Conjecture for Modular Communication Complexity

__
TR96-018
| 23rd February 1996
__

Oded Goldreich, Johan Håstad#### On the Message Complexity of Interactive Proof Systems

Revisions: 2

__
TR96-020
| 6th March 1996
__

C.P. Schnorr, Carsten Rössner#### An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension

__
TR96-021
| 13th February 1996
__

Yongge Wang#### NP-hard Sets Are Superterse unless NP Is Small

__
TR96-022
| 15th March 1996
__

Martin Sauerhoff, Ingo Wegener, Ralph Werchner#### Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

__
TR96-023
| 21st March 1996
__

Eric Allender#### A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

Comments: 1

__
TR96-024
| 21st March 1996
__

Eric Allender, Robert Beals, Mitsunori Ogihara#### The complexity of matrix rank and feasible systems of linear equations

__
TR96-025
| 22nd March 1996
__

Berthold Ruf#### The Computational Power of Spiking Neurons Depends on the Shape of the Postsynaptic Potentials

__
TR96-026
| 25th March 1996
__

Stasys Jukna#### Finite Limits and Monotone Computations

Revisions: 1
,
Comments: 1

__
TR96-027
| 20th February 1996
__

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman#### Computing Solutions Uniquely Collapses the Polynomial Hierarchy

__
TR96-028
| 9th April 1996
__

Sanjeev Khanna, Madhu Sudan#### The Optimization Complexity of Constraint Satisfaction Problems

__
TR96-029
| 16th April 1996
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim#### Towards efficient constructions of hitting sets that derandomize BPP

__
TR96-030
| 31st March 1996
__

Meera Sitharam#### Approximation from linear spaces and applications to complexity

__
TR96-031
| 30th April 1996
__

#### Networks of Spiking Neurons: The Third Generation of Neural Network Models

__
TR96-032
| 12th March 1996
__

Manindra Agrawal, Thomas Thierauf#### The Boolean Isomorphism Problem

__
TR96-033
| 6th March 1996
__

Bernd Borchert, Desh Ranjan, Frank Stephan#### On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

__
TR96-034
| 28th March 1996
__

Vasken Bohossian, Jehoshua Bruck#### On Neural Networks with Minimal Weights

__
TR96-035
| 27th March 1996
__

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner#### Probabilistic Type-2 Operators and ``Almost''-Classes

__
TR96-036
| 28th May 1996
__

Petr Savicky, Stanislav Zak#### A large lower bound for 1-branching programs

Revisions: 1

__
TR96-037
| 14th June 1996
__

Stasys Jukna, Alexander Razborov#### Neither Reading Few Bits Twice nor Reading Illegally Helps Much

__
TR96-039
| 27th June 1996
__

Carme Alvarez, Raymond Greenlaw#### A Compendium of Problems Complete for Symmetric Logarithmic Space

Comments: 2

__
TR96-040
| 21st May 1996
__

Thomas Thierauf#### The Isomorphismproblem for One-Time-Only Branching Programs

Revisions: 1
,
Comments: 1

__
TR96-041
| 24th July 1996
__

Oded Goldreich, Avi Wigderson#### On the Circuit Complexity of Perfect Hashing

Revisions: 1
,
Comments: 2

__
TR96-042
| 26th July 1996
__

Oded Goldreich, Shai Halevi#### Collision-Free Hashing from Lattice Problems

__
TR96-043
| 16th August 1996
__

Edmund Ihler#### On polynomial time approximation schemes and approximation preserving reductions

__
TR96-044
| 6th August 1996
__

Yosi Ben-Asher, Ilan Newman#### Optimal Search in Trees

Revisions: 1

__
TR96-045
| 28th August 1996
__

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe#### Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems

Comments: 2

__
TR96-046
| 27th August 1996
__

Luca Trevisan#### On the Approximability of the Multi-dimensional Euclidean TSP

Revisions: 1

__
TR96-047
| 2nd September 1996
__

Oded Goldreich, Muli Safra#### A Combinatorial Consistency Lemma with application to the PCP Theorem

Revisions: 1

__
TR96-048
| 12th September 1996
__

Eric Allender, Klaus-Joern Lange#### StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

__
TR96-049
| 9th September 1996
__

Per Enflo, Meera Sitharam#### Stable basis families and complexity lower bounds

__
TR96-050
| 23rd September 1996
__

Petr Savicky, Stanislav Zak#### A hierarchy for (1,+k)-branching programs with respect to k

__
TR96-051
| 1st October 1996
__

Richard Beigel, William Gasarch, Ming Li, Louxin Zhang#### Addition in $\log_2{n}$ + O(1)$ Steps on Average: A Simple Analysis

__
TR96-052
| 2nd October 1996
__

Martin Dietzfelbinger#### Gossiping and Broadcasting versus Computing Functions in Networks

__
TR96-053
| 6th August 1996
__

Yosi Ben-Asher, Ilan Newman#### Geometric Approach for Optimal Routing on Mesh with Buses

Revisions: 1

__
TR96-054
| 2nd November 1996
__

Oded Goldreich#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Comments: 1

__
TR96-055
| 22nd October 1996
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim#### Hitting Properties of Hard Boolean Operators and their Consequences on BPP

Revisions: 1
,
Comments: 1

__
TR96-056
| 12th November 1996
__

Oded Goldreich, Shai Halevi#### Public-Key Cryptosystems from Lattice Reduction Problems

__
TR96-057
| 18th November 1996
__

Oded Goldreich, Dana Ron#### Property Testing and its connection to Learning and Approximation

__
TR96-058
| 25th November 1996
__

Dima Grigoriev, Marek Karpinski#### Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

__
TR96-059
| 12th November 1996
__

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz#### A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

__
TR96-060
| 19th November 1996
__

Bernd Borchert, Frank Stephan#### Looking for an Analogue of Rice's Theorem in Complexity Theory

__
TR96-061
| 27th November 1996
__

Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener#### Optimal attribute-efficient learning of disjunction, parity, and threshold functions

__
TR96-062
| 3rd December 1996
__

Sanjeev Khanna, Madhu Sudan, David P. Williamson#### A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

__
TR96-063
| 6th November 1996
__

Martin Dietzfelbinger#### The Linear-Array Problem in Communication Complexity Resolved

__
TR96-064
| 11th December 1996
__

Sanjeev Khanna, Madhu Sudan, Luca Trevisan#### Constraint satisfaction: The approximability of minimization problems.

__
TR96-065
| 13th December 1996
__

Miklos Ajtai, Cynthia Dwork#### A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Revisions: 1
,
Comments: 1

__
TR96-066
| 21st November 1996
__

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan#### Structure in Approximation Classes

__
TR96-067
| 20th December 1996
__

Oded Goldreich, Bernd Meyer#### Computational Indistinguishability -- Algorithms vs. Circuits.

Manindra Agrawal, Richard Beigel, Thomas Thierauf

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

Manindra Agrawal, Eric Allender

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

Alexei Kitaev

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

Shiva Chaudhuri, Jaikumar Radhakrishnan

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

Hans-Joerg Burtschick, Heribert Vollmer

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

Bernd Borchert, Antoni Lozano

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

Miklos Ajtai

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

F. Bergadano, N.H. Bshouty, Stefano Varricchio

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

Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio

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

Christoph Meinel, Anna Slobodova

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

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

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

Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson

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

Mitsunori Ogihara

It is shown that the PL hierarchy defined in terms of the

standard Ruzzo-Simon-Tompa relativization collapses to PL.

Mitsunori Ogihara

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

Edoardo Amaldi, Viggo Kann

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

Andrea E. F. Clementi, Luca Trevisan

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

Christoph Meinel, Stephan Waack

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

Oded Goldreich, Johan Håstad

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

C.P. Schnorr, Carsten Rössner

Yongge Wang

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

Martin Sauerhoff, Ingo Wegener, Ralph Werchner

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

Eric Allender

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

Eric Allender, Robert Beals, Mitsunori Ogihara

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

Berthold Ruf

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

Stasys Jukna

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

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

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

Sanjeev Khanna, Madhu Sudan

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

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

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

Meera Sitharam

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

Manindra Agrawal, Thomas Thierauf

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

Bernd Borchert, Desh Ranjan, Frank Stephan

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.

Vasken Bohossian, Jehoshua Bruck

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

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

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

Petr Savicky, Stanislav Zak

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

Stasys Jukna, Alexander Razborov

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

Carme Alvarez, Raymond Greenlaw

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

Thomas Thierauf

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

Oded Goldreich, Avi Wigderson

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.

Oded Goldreich, Shai Halevi

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.

Edmund Ihler

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

Yosi Ben-Asher, Ilan Newman

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

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe

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

Luca Trevisan

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

Oded Goldreich, Muli Safra

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

Eric Allender, Klaus-Joern Lange

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.

Per Enflo, Meera Sitharam

--

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

Petr Savicky, Stanislav Zak

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

Richard Beigel, William Gasarch, Ming Li, Louxin Zhang

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.

Martin Dietzfelbinger

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

Yosi Ben-Asher, Ilan Newman

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

Oded Goldreich

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

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

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

Oded Goldreich, Shai Halevi

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

Oded Goldreich, Dana Ron

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

Dima Grigoriev, Marek Karpinski

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

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz

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

Bernd Borchert, Frank Stephan

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.

Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener

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

Sanjeev Khanna, Madhu Sudan, David P. Williamson

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

Martin Dietzfelbinger

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

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

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

Miklos Ajtai, Cynthia Dwork

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

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan

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

Oded Goldreich, Bernd Meyer

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