Under the auspices of the Computational Complexity Foundation (CCF)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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