Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

REPORTS > 1996:
All reports in year 1996:
TR96-001 | 10th January 1996
Manindra Agrawal, Richard Beigel, Thomas Thierauf

Modulo Information from Nonadaptive Queries to NP

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

TR96-002 | 10th January 1996
Manindra Agrawal, Eric Allender

An Isomorphism Theorem for Circuit Complexity

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

TR96-003 | 4th December 1995
Alexei Kitaev

Quantum measurements and the Abelian Stabilizer Problem

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

TR96-004 | 18th January 1996
Shiva Chaudhuri, Jaikumar Radhakrishnan

Deterministic Restrictions in Circuit Complexity

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

TR96-005 | 9th January 1996
Hans-Joerg Burtschick, Heribert Vollmer

Lindstroem Quantifiers and Leaf Language Definability

Revisions: 1

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

TR96-006 | 24th January 1996
Bernd Borchert, Antoni Lozano

Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept

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

TR96-007 | 29th January 1996
Miklos Ajtai

Generating Hard Instances of Lattice Problems

Comments: 1

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

TR96-008 | 22nd January 1996
F. Bergadano, N.H. Bshouty, Stefano Varricchio

Learning Multivariate Polynomials from Substitution and Equivalence Queries

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

TR96-009 | 17th January 1996
Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio

On Learning Branching Programs and Small Depth Circuits

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

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

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

TR96-011 | 29th January 1996
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

Sharply Bounded Alternation within P

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

TR96-012 | 14th December 1995
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson

Visual Cryptography for General Access Structures

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

TR96-013 | 14th February 1996
Mitsunori Ogihara

The PL Hierarchy Collapses

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

more >>>

TR96-014 | 14th February 1996
Mitsunori Ogihara

Sparse Hard Sets for P Yields Space-Efficient Algorithms

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

more >>>

TR96-015 | 12th December 1995
Edoardo Amaldi, Viggo Kann

On the approximability of some NP-hard minimization problems for linear systems

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

TR96-016 | 6th February 1996
Andrea E. F. Clementi, Luca Trevisan

Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints

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

TR96-017 | 19th February 1996
Christoph Meinel, Stephan Waack

The ``Log Rank'' Conjecture for Modular Communication Complexity

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

TR96-018 | 23rd February 1996
Oded Goldreich, Johan Håstad

On the Message Complexity of Interactive Proof Systems

Revisions: 2

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

TR96-019 | 6th March 1996
C.P. Schnorr

Security of 2^t-Root Identification and Signatures

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

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

TR96-022 | 15th March 1996
Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

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

TR96-023 | 21st March 1996
Eric Allender

A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

Comments: 1

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

TR96-024 | 21st March 1996
Eric Allender, Robert Beals, Mitsunori Ogihara

The complexity of matrix rank and feasible systems of linear equations

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

TR96-025 | 22nd March 1996
Berthold Ruf

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

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

TR96-026 | 25th March 1996
Stasys Jukna

Finite Limits and Monotone Computations

Revisions: 1 , Comments: 1

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

TR96-027 | 20th February 1996
Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Computing Solutions Uniquely Collapses the Polynomial Hierarchy

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

TR96-028 | 9th April 1996
Sanjeev Khanna, Madhu Sudan

The Optimization Complexity of Constraint Satisfaction Problems

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

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

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

TR96-030 | 31st March 1996
Meera Sitharam

Approximation from linear spaces and applications to complexity

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

TR96-031 | 30th April 1996

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

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

TR96-032 | 12th March 1996
Manindra Agrawal, Thomas Thierauf

The Boolean Isomorphism Problem

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

TR96-033 | 6th March 1996
Bernd Borchert, Desh Ranjan, Frank Stephan

On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

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.

more >>>

TR96-034 | 28th March 1996
Vasken Bohossian, Jehoshua Bruck

On Neural Networks with Minimal Weights

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

TR96-035 | 27th March 1996
Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

Probabilistic Type-2 Operators and ``Almost''-Classes

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

TR96-036 | 28th May 1996
Petr Savicky, Stanislav Zak

A large lower bound for 1-branching programs

Revisions: 1

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

TR96-037 | 14th June 1996
Stasys Jukna, Alexander Razborov

Neither Reading Few Bits Twice nor Reading Illegally Helps Much

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

TR96-039 | 27th June 1996
Carme Alvarez, Raymond Greenlaw

A Compendium of Problems Complete for Symmetric Logarithmic Space

Comments: 2

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

TR96-040 | 21st May 1996
Thomas Thierauf

The Isomorphismproblem for One-Time-Only Branching Programs

Revisions: 1 , Comments: 1

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

TR96-041 | 24th July 1996
Oded Goldreich, Avi Wigderson

On the Circuit Complexity of Perfect Hashing

Revisions: 1 , Comments: 2

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.

more >>>

TR96-042 | 26th July 1996
Oded Goldreich, Shai Halevi

Collision-Free Hashing from Lattice Problems

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.

more >>>

TR96-043 | 16th August 1996
Edmund Ihler

On polynomial time approximation schemes and approximation preserving reductions

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

TR96-044 | 6th August 1996
Yosi Ben-Asher, Ilan Newman

Optimal Search in Trees

Revisions: 1

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

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

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

TR96-046 | 27th August 1996
Luca Trevisan

On the Approximability of the Multi-dimensional Euclidean TSP

Revisions: 1

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

TR96-047 | 2nd September 1996
Oded Goldreich, Muli Safra

A Combinatorial Consistency Lemma with application to the PCP Theorem

Revisions: 1

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

TR96-048 | 12th September 1996
Eric Allender, Klaus-Joern Lange

StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

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.

more >>>

TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

Stable basis families and complexity lower bounds

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

TR96-050 | 23rd September 1996
Petr Savicky, Stanislav Zak

A hierarchy for (1,+k)-branching programs with respect to k

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

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

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.

more >>>

TR96-052 | 2nd October 1996
Martin Dietzfelbinger

Gossiping and Broadcasting versus Computing Functions in Networks

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

TR96-053 | 6th August 1996
Yosi Ben-Asher, Ilan Newman

Geometric Approach for Optimal Routing on Mesh with Buses

Revisions: 1

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

TR96-054 | 2nd November 1996
Oded Goldreich

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Comments: 1

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

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

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

TR96-056 | 12th November 1996
Oded Goldreich, Shai Halevi

Public-Key Cryptosystems from Lattice Reduction Problems

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

TR96-057 | 18th November 1996
Oded Goldreich, Dana Ron

Property Testing and its connection to Learning and Approximation

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

TR96-058 | 25th November 1996
Dima Grigoriev, Marek Karpinski

Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

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

TR96-059 | 12th November 1996
Shai Ben-David, Nader Bshouty, Eyal Kushilevitz

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

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

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

TR96-060 | 19th November 1996
Bernd Borchert, Frank Stephan

Looking for an Analogue of Rice's Theorem in Complexity Theory

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.

more >>>

TR96-061 | 27th November 1996
Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener

Optimal attribute-efficient learning of disjunction, parity, and threshold functions

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

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

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

TR96-063 | 6th November 1996
Martin Dietzfelbinger

The Linear-Array Problem in Communication Complexity Resolved

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

TR96-064 | 11th December 1996
Sanjeev Khanna, Madhu Sudan, Luca Trevisan

Constraint satisfaction: The approximability of minimization problems.

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

TR96-065 | 13th December 1996
Miklos Ajtai, Cynthia Dwork

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Revisions: 1 , Comments: 1

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

TR96-066 | 21st November 1996
Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan

Structure in Approximation Classes

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

TR96-067 | 20th December 1996
Oded Goldreich, Bernd Meyer

Computational Indistinguishability -- Algorithms vs. Circuits.

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

ISSN 1433-8092 | Imprint