Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

REPORTS > 1998:
All reports in year 1998:
TR98-001 | 17th December 1997
Detlef Sieling

On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization

Revisions: 1

The size of Ordered Binary Decision Diagrams (OBDDs) is
determined by the chosen variable ordering. A poor choice may cause an
OBDD to be too large to fit into the available memory. The decision
variant of the variable ordering problem is known to be
NP-complete. We strengthen this result by ... more >>>

TR98-002 | 8th January 1998
Jayram S. Thathachar

On Separating the Read-k-Times Branching Program Hierarchy

We obtain an exponential separation between consecutive
levels in the hierarchy of classes of functions computable by
polynomial-size syntactic read-$k$-times branching programs, for
{\em all\/} $k>0$, as conjectured by various
authors~\cite{weg87,ss93,pon95b}. For every $k$, we exhibit two
explicit functions that can be computed by linear-sized
read-$(\kpluso)$-times branching programs but ... more >>>

TR98-003 | 3rd November 1997
I. Cahit, M. Tezer

Irregular Assignments of the Forest of Paths

An irregular assignement of $G$ is labelling $f: E \ra
\{1,2,...,m\}$ of the
edge-set of $G$ such that all of the induced vertex labels computed as
$\sigma_{v\in e}f(e)$ are distinct. The minimal number $m$ for which this
is possible is called the minimal irregularity strength $s_{m}(G)$ of $G$.
The ... more >>>

TR98-004 | 13th January 1998
Farid Ablayev, Marek Karpinski

On the Power of Randomized Ordered Branching Programs

We introduce a model of a {\em randomized branching program}
in a natural way similar to the definition of a randomized circuit.
We exhibit an explicit boolean function
$f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that:

1) $f_{n}$ can be computed by a polynomial size randomized
... more >>>

TR98-005 | 27th January 1998
Jin-Yi Cai

A new transference theorem and applications to Ajtai's connection factor

We prove a new transference theorem in the geometry of numbers,
giving optimal bounds relating the successive minima of a lattice
with the minimal length of generating vectors of its dual.
It generalizes the transference theorem due to Banaszczyk.
We also prove a stronger bound for the special class of ... more >>>

TR98-006 | 27th January 1998
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

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

TR98-007 | 12th January 1998
Luca Trevisan

Recycling Queries in PCPs and in Linearity Tests

We study query-efficient Probabilistically Checkable
Proofs (PCPs) and linearity tests. We focus on the number
of amortized query bits. A testing algorithm uses $q$ amortized
query bits if, for some constant $k$, it reads $qk$ bits and has
error probability at most $2^{-k}$. The best known ... more >>>

TR98-008 | 15th January 1998
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

Proof verification and the hardness of approximation problems.

We show that every language in NP has a probablistic verifier
that checks membership proofs for it using
logarithmic number of random bits and by examining a
<em> constant </em> number of bits in the proof.
If a string is in the language, then there exists a proof ... more >>>

TR98-009 | 25th November 1997
Bruce Edward Litow

Parallel complexity of integer coprimality

Comments: 3

It is shown that integer coprimality is in NC.

more >>>

TR98-010 | 22nd January 1998
Phong Nguyen, Jacques Stern

A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications

Revisions: 1

Recently, Ajtai discovered a fascinating connection
between the worst-case complexity and the average-case
complexity of some well-known lattice problems.
Later, Ajtai and Dwork proposed a cryptosystem inspired
by Ajtai's work, provably secure if a particular lattice
problem is difficult. We show that there is a converse
to the ... more >>>

TR98-011 | 29th January 1998
Farid Ablayev, Marek Karpinski

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the
size of any randomized ordered read-once branching program
computing integer multiplication. Our proof depends on proving
a new lower bound on Yao's randomized one-way communication
complexity of certain boolean functions. It generalizes to some
other ... more >>>

TR98-012 | 2nd February 1998
Meena Mahajan, V. Vinay

Determinant: Old Algorithms, New Insights

In this paper we approach the problem of computing the characteristic
polynomial of a matrix from the combinatorial viewpoint. We present
several combinatorial characterizations of the coefficients of the
characteristic polynomial, in terms of walks and closed walks of
different kinds in the underlying graph. We develop algorithms based
more >>>

TR98-013 | 3rd March 1998
Nader H. Bshouty

A New Composition Theorem for Learning Algorithms

We present a new approach to the composition
of learning algorithms (in various models) for
classes of constant VC-dimension into learning algorithms for
more complicated classes.
We prove that if a class $\CC$ is learnable
in time $t$ from a hypothesis class $\HH$ of constant VC-dimension
then the class ... more >>>

TR98-014 | 6th February 1998
Gunter Blache, Marek Karpinski, Juergen Wirtgen

On Approximation Intractability of the Bandwidth Problem

The bandwidth problem is the problem of enumerating
the vertices of a given graph $G$ such that the maximum difference
between the numbers of adjacent vertices is minimal. The problem
has a long history and a number of applications.
There was not ... more >>>

TR98-015 | 16th January 1998
Valentin E. Brimkov, Stefan S. Dantchev

Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)
$a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework
of the Blum-Shub-Smale real number computational model \cite{BSS}.
We obtain a new lower bound
$\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time
complexity ... more >>>

TR98-016 | 24th March 1998
Daniele Micciancio

The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.

We show that computing the approximate length of the shortest vector
in a lattice within a factor c is NP-hard for randomized reductions
for any constant c<sqrt(2). We also give a deterministic reduction
based on a number theoretic conjecture.

more >>>

TR98-017 | 29th March 1998
Oded Goldreich, Madhu Sudan

Computational Indistinguishability: A Sample Hierarchy.

We consider the existence of pairs of probability ensembles which
may be efficiently distinguished given $k$ samples
but cannot be efficiently distinguished given $k'<k$ samples.
It is well known that in any such pair of ensembles it cannot be that
both are efficiently computable
(and that such phenomena ... more >>>

TR98-018 | 27th March 1998
Martin Sauerhoff

Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

Comments: 1

We extend the tools for proving lower bounds for randomized branching
programs by presenting a new technique for the read-once case which is
applicable to a large class of functions. This technique fills the gap
between simple methods only applicable for OBDDs and the well-known
"rectangle technique" of Borodin, Razborov ... more >>>

TR98-019 | 5th April 1998
Eric Allender, Klaus Reinhardt

Isolation, Matching, and Counting

We show that the perfect matching problem is in the
complexity class SPL (in the nonuniform setting).
This provides a better upper bound on the complexity of the
matching problem, as well as providing motivation for studying
the complexity class SPL.

Using similar ... more >>>

TR98-020 | 10th April 1998
Andris Ambainis, David Mix Barrington, Huong LeThanh

On Counting $AC^0$ Circuits with Negative Constants

Continuing the study of the relationship between $TC^0$,
$AC^0$ and arithmetic circuits, started by Agrawal et al.
(IEEE Conference on Computational Complexity'97),
we answer a few questions left open in this
paper. Our main result is that the classes Diff$AC^0$ and
Gap$AC^0$ ... more >>>

TR98-021 | 7th April 1998
Shai Ben-David, Anna Gringauze.

On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic.

Revisions: 1

We investigate sufficient conditions for the existence of
optimal propositional proof systems (PPS).
We concentrate on conditions of the form CoNF = NF.
We introduce a purely combinatorial property of complexity classes
- the notions of {\em slim} vs. {\em fat} classes.
These notions partition the ... more >>>

TR98-022 | 14th April 1998
Steffen Reith, Heribert Vollmer

The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

We consider the problems of finding the lexicographically
minimal (or maximal) satisfying assignment of propositional
formulae for different restricted formula classes. It turns
out that for each class from our framework, the above problem
is either polynomial time solvable or complete for ... more >>>

TR98-023 | 16th April 1998
Eric Allender, Shiyu Zhou

Uniform Inclusions in Nondeterministic Logspace

We show that the complexity class LogFew is contained
in NL $\cap$ SPL. Previously, this was known only to
hold in the nonuniform setting.

more >>>

TR98-024 | 28th April 1998
Wenceslas Fernandez de la Vega, Marek Karpinski

On Approximation Hardness of Dense TSP and other Path Problems

TSP(1,2), the Traveling Salesman Problem with distances 1 and 2, is
the problem of finding a tour of minimum length in a complete
weighted graph where each edge has length 1 or 2. Let $d_o$ satisfy
$0<d_o<1/2$. We show that TSP(1,2) has no PTAS on the set ... more >>>

TR98-026 | 5th May 1998
Richard Beigel

Gaps in Bounded Query Hierarchies

Prior results show that most bounded query hierarchies cannot
contain finite gaps. For example, it is known that
P<sub>(<i>m</i>+1)-tt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup> implies P<sub>btt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup>
and for all sets <i>A</i>
<li> FP<sub>(<i>m</i>+1)-tt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies FP<sub>btt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>
<li> P<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies P<sub>bT</sub><sup><i>A</i></sup> = ... more >>>

TR98-027 | 15th April 1998
Vikraman Arvind, Jacobo Toran

Sparse sets, approximable sets, and parallel queries to NP

We relate the existence of disjunctive hard sets for NP to
other well studied hypotheses in complexity theory showing
that if an NP-complete set or a coNP-complete set is
polynomial-time disjunctively reducible
to a sparse set then FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$. Using
a similar argument we obtain also that ... more >>>

TR98-028 | 28th May 1998
Paul Beame, Faith Fich

On Searching Sorted Lists: A Near-Optimal Lower Bound

We obtain improved lower bounds for a class of static and dynamic
data structure problems that includes several problems of searching
sorted lists as special cases.

These lower bounds nearly match the upper bounds given by recent
striking improvements in searching algorithms given by Fredman and
Willard's ... more >>>

TR98-029 | 27th May 1998
Piotr Berman, Marek Karpinski

On Some Tighter Inapproximability Results

We prove a number of improved inaproximability results,
including the best up to date explicit approximation
thresholds for MIS problem of bounded degree, bounded
occurrences MAX-2SAT, and bounded degree Node Cover. We
prove also for the first time inapproximability of the
problem of Sorting by ... more >>>

TR98-030 | 9th June 1998
Stasys Jukna, Stanislav Zak

On Branching Programs With Bounded Uncertainty

We propose an information-theoretic approach to proving
lower bounds on the size of branching programs (b.p.). The argument
is based on Kraft-McMillan type inequalities for the average amount of
uncertainty about (or entropy of) a given input during various
stages of the computation. ... more >>>

TR98-031 | 4th May 1998
Dimitris Fotakis, Paul Spirakis

Graph Properties that Facilitate Travelling

In this work, we study two special cases of the metric Travelling Salesman
Problem, Graph TSP and TSP(1,2). At first, we show that dense instances of
TSP(1,2) and Graph TSP are essentially as hard to approximate as general
instances of TSP(1,2).

Next, we present an NC algorithm for TSP(1,2) that ... more >>>

TR98-032 | 10th June 1998
Mihir Bellare, Oded Goldreich, Erez Petrank

Uniform Generation of NP-witnesses using an NP-oracle.

A Uniform Generation procedure for $NP$ is an
algorithm which given any input in a fixed NP-language, outputs a uniformly
distributed NP-witness for membership of the input in the language.
We present a Uniform Generation procedure for $NP$ that runs in probabilistic
polynomial-time with an NP-oracle. This improves upon ... more >>>

TR98-033 | 12th June 1998
C.P. Schnorr

Security of Allmost ALL Discrete Log Bits

Let G be a finite cyclic group with generator \alpha and with
an encoding so that multiplication is computable in polynomial time. We
study the security of bits of the discrete log x when given \exp_{\alpha}(x),
assuming that the exponentiation function \exp_{\alpha}(x) = \alpha^x is one-way.
... more >>>

TR98-034 | 23rd June 1998
Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

A tight characterization of NP with 3 query PCPs

It is known that there exists a PCP characterization of NP
where the verifier makes 3 queries and has a {\em one-sided}
error that is bounded away from 1; and also that 2 queries
do not suffice for such a characterization. Thus PCPs with
3 ... more >>>

TR98-035 | 8th May 1998
Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

We prove an exponential lower bound for tree-like Cutting Planes
refutations of a set of clauses which has polynomial size resolution
refutations. This implies an exponential separation between tree-like
and dag-like proofs for both Cutting Planes and resolution; in both
cases only superpolynomial separations were known before.
In order to ... more >>>

TR98-036 | 11th June 1998
Vince Grolmusz, Gábor Tardos

Lower Bounds for (MOD p -- MOD m) Circuits

Modular gates are known to be immune for the random
restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and
Hastad. We demonstrate here a random clustering technique which
overcomes this difficulty and is capable to prove generalizations of
several known modular circuit lower bounds of Barrington, Straubing,
Therien; Krause ... more >>>

TR98-037 | 29th June 1998
Johannes Köbler, Rainer Schuler

Average-Case Intractability vs. Worst-Case Intractability

We use the assumption that all sets in NP (or other levels
of the polynomial-time hierarchy) have efficient average-case
algorithms to derive collapse consequences for MA, AM, and various
subclasses of P/poly. As a further consequence we show for
C in {P(PP), PSPACE} that ... more >>>

TR98-038 | 9th July 1998
Marek Karpinski

On the Computational Power of Randomized Branching Programs

We survey some upper and lower bounds established recently on
the sizes of randomized branching programs computing explicit
boolean functions. In particular, we display boolean
functions on which randomized read-once ordered branching
programs are exponentially more powerful than deterministic
or nondeterministic read-$k$-times branching programs for ... more >>>

TR98-039 | 14th July 1998
Christoph Meinel, Thorsten Theobald

Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey

Many problems in computer-aided design of highly integrated circuits
(CAD for VLSI) can be transformed to the task of manipulating objects
over finite domains. The efficiency of these operations depends
substantially on the chosen data structures. In the last years,
ordered binary decision diagrams (OBDDs) have ... more >>>

TR98-040 | 24th July 1998
Madhu Sudan, Luca Trevisan

Probabilistically checkable proofs with low amortized query complexity

The error probability of Probabilistically Checkable Proof (PCP)
systems can be made exponentially small in the number of queries
by using sequential repetition. In this paper we are interested
in determining the precise rate at which the error goes down in
an optimal protocol, and we make substantial progress toward ... more >>>

TR98-041 | 27th July 1998
Stasys Jukna

Combinatorics of Monotone Computations

We consider a general model of monotone circuits, which
we call d-local. In these circuits we allow as gates:
(i) arbitrary monotone Boolean functions whose minterms or
maxterms (or both) have length at most <i>d</i>, and
(ii) arbitrary real-valued non-decreasing functions on ... more >>>

TR98-042 | 27th July 1998
Pavel Pudlak

A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits

Comments: 1

We consider computations of linear forms over {\bf R} by
circuits with linear gates where the absolute values
coefficients are bounded by a constant. Also we consider a
related concept of restricted rigidity of a matrix. We prove
some lower bounds on the size of such circuits and the
more >>>

TR98-043 | 27th July 1998
Venkatesan Guruswami, Madhu Sudan

Improved decoding of Reed-Solomon and algebraic-geometric codes.

We present an improved list decoding algorithm for decoding
Reed-Solomon codes. Given an arbitrary string of length n, the
list decoding problem is that of finding all codewords within a
specified Hamming distance from the input string.

It is well-known that this decoding problem for Reed-Solomon
codes reduces to the ... more >>>

TR98-044 | 31st July 1998
Jiri Sgall

Bounds on Pairs of Families with Restricted Intersections

We study pairs of families ${\cal A},{\cal B}\subseteq
2^{\{1,\ldots,r\}}$ such that $|A\cap B|\in L$ for any
$A\in{\cal A}$, $B\in{\cal B}$. We are interested in the maximal
product $|{\cal A}|\cdot|{\cal B}|$, given $r$ and $L$. We give
asymptotically optimal bounds for $L$ containing only elements
of $s<q$ residue classes modulo ... more >>>

TR98-045 | 17th July 1998
Detlef Sieling

A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs

For (1,+k)-branching programs and read-k-times branching
programs syntactic and nonsyntactic variants can be distinguished. The
nonsyntactic variants correspond in a natural way to sequential
computations with restrictions on reading the input while lower bound
proofs are easier or only known for the syntactic variants. In this
paper it is shown ... more >>>

TR98-047 | 21st August 1998
Salil Vadhan

Extracting All the Randomness from a Weakly Random Source

Revisions: 1 , Comments: 1

In this paper, we give explicit constructions of extractors which work for
a source of any min-entropy on strings of length $n$. The first
construction extracts any constant fraction of the min-entropy using
O(log^2 n) additional random bits. The second extracts all the
min-entropy using O(log^3 n) additional random ... more >>>

TR98-048 | 6th July 1998
Irit Dinur, Guy Kindler, Shmuel Safra

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

This paper shows finding the closest vector in a lattice
to be NP-hard to approximate to within any factor up to
$2^{(\log{n})^{1-\epsilon}}$ where
$\epsilon = (\log\log{n})^{-\alpha}$
and $\alpha$ is any positive constant $<{1\over 2}$.

more >>>

TR98-049 | 10th July 1998
Dimitris Fotakis, Paul Spirakis

Random Walks, Conditional Hitting Sets and Partial Derandomization

In this work we use random walks on expanders in order to
relax the properties of hitting sets required for partially
derandomizing one-side error algorithms. Building on a well-known
probability amplification technique [AKS87,CW89,IZ89], we use
random walks on expander graphs of subexponential (in the
random bit complexity) size so as ... more >>>

TR98-050 | 6th July 1998
Farid Ablayev, Svetlana Ablayeva

A Discrete Approximation and Communication Complexity Approach to the Superposition Problem

The superposition (or composition) problem is a problem of
representation of a function $f$ by a superposition of "simpler" (in a
different meanings) set $\Omega$ of functions. In terms of circuits
theory this means a possibility of computing $f$ by a finite circuit
with 1 fan-out gates $\Omega$ of functions. ... more >>>

TR98-051 | 20th July 1998
Petr Savicky

A probabilistic nonequivalence test for syntactic (1,+k)-branching programs

Branching programs are a model for representing Boolean
functions. For general branching programs, the
satisfiability and nonequivalence tests are NP-complete.
For read-once branching programs, which can test each
variable at most once in each computation, the satisfiability
test is trivial and there is also a probabilistic polynomial
time test ... more >>>

TR98-052 | 5th August 1998
Boris Hemkemeier, Frank Vallentin

On the decomposition of lattices

Revisions: 1

A lattice in euclidean space which is an orthogonal sum of
nontrivial sublattices is called decomposable. We present an algorithm
to construct a lattice's decomposition into indecomposable sublattices.
Similar methods are used to prove a covering theorem for generating
systems of lattices and to speed up variations of the LLL ... more >>>

TR98-053 | 30th August 1998
Paul Beame, Michael Saks, Jayram S. Thathachar

Time-Space Tradeoffs for Branching Programs

Comments: 1

We obtain the first non-trivial time-space tradeoff lower bound for
functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a
Boolean function f that requires exponential size to be computed by any
branching program of length cn, for some constant c>1. We also give the first
separation result between the ... more >>>

TR98-054 | 26th August 1998
Igor E. Shparlinski

On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

Lower bounds are obtained on the degree and the number of monomials of
Boolean functions, considered as a polynomial over $GF(2)$,
which decide if a given $r$-bit integer is square-free.
Similar lower bounds are also obtained for polynomials
over the reals which provide a threshold representation
more >>>

TR98-055 | 4th September 1998
Luca Trevisan

Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

Comments: 1

We introduce a new approach to construct extractors -- combinatorial
objects akin to expander graphs that have several applications.
Our approach is based on error correcting codes and on the Nisan-Wigderson
pseudorandom generator. An application of our approach yields a
construction that is simple to ... more >>>

TR98-056 | 31st August 1998
Anna Bernasconi, Igor E. Shparlinski

Circuit Complexity of Testing Square-Free Numbers

In this paper we extend the area of applications of
the Abstract Harmonic Analysis to the field of Boolean function complexity.
In particular, we extend the class of functions to which
a spectral technique developed in a series of works of the first author
can be applied.
This extension ... more >>>

TR98-057 | 10th September 1998
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Characterizing Small Depth and Small Space Classes by Operators of Higher Types

Motivated by the question of how to define an analog of interactive
proofs in the setting of logarithmic time- and space-bounded
computation, we study complexity classes defined in terms of
operators quantifying over oracles. We obtain new
characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ... more >>>

TR98-058 | 2nd August 1998
H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem

We introduce "resource-bounded betting games", and propose
a generalization of Lutz's resource-bounded measure in which the choice
of next string to bet on is fully adaptive. Lutz's martingales are
equivalent to betting games constrained to bet on strings in lexicographic
order. We show that if strong pseudo-random number generators exist,
more >>>

TR98-059 | 15th September 1998
C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer

The Descriptive Complexity Approach to LOGCFL

Building upon the known generalized-quantifier-based first-order
characterization of LOGCFL, we lay the groundwork for a deeper
investigation. Specifically, we examine subclasses of LOGCFL arising
from varying the arity and nesting of groupoidal quantifiers. Our
work extends the elaborate theory relating monoidal quantifiers to
NC^1 and its subclasses. In the ... more >>>

TR98-060 | 8th October 1998
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

Learning polynomials with queries -- The highly noisy case.

This is a revised version of work which has appeared
in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field
$F$ into $F$,
we consider the task of reconstructing a list of all $n$-variate
degree $d$ polynomials which agree with $f$
more >>>

TR98-061 | 29th September 1998
Robert H. Sloan, Ken Takata, György Turán

On frequent sets of Boolean matrices

Given a Boolean matrix and a threshold t, a subset of the
columns is frequent if there are at least t rows having a 1 entry in
each corresponding position. This concept is used in the algorithmic,
combinatorial approach to knowledge discovery and data mining. We
consider the complexity aspects ... more >>>

TR98-062 | 28th October 1998
Oded Goldreich, Dana Ron, Madhu Sudan

Chinese Remaindering with Errors

Revisions: 4 , Comments: 1

The Chinese Remainder Theorem states that a positive
integer m is uniquely specified by its remainder modulo
k relatively prime integers p_1,...,p_k, provided
m < \prod_{i=1}^k p_i. Thus the residues of m modulo
relatively prime integers p_1 < p_2 < ... < p_n
form a redundant representation of m if ... more >>>

TR98-063 | 4th November 1998
Oded Goldreich, Salil Vadhan

Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

We consider the following (promise) problem, denoted ED (for Entropy
Difference): The input is a pairs of circuits, and YES instances (resp.,
NO instances) are such pairs in which the first (resp., second) circuit
generates a distribution with noticeably higher entropy.

On one hand we show that any language ... more >>>

TR98-064 | 6th November 1998
Wenceslas Fernandez de la Vega, Marek Karpinski

Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

We give the first polynomial time approximability characterization
of dense weighted instances of MAX-CUT, and some other dense
weighted NP-hard problems in terms of their empirical weight
distributions. This gives also the first almost sharp
characterization of inapproximability of unweighted 0,1
MAX-BISECTION instances ... more >>>

TR98-065 | 6th November 1998
Piotr Berman, Marek Karpinski

On Some Tighter Inapproximability Results, Further Improvements

Improved inaproximability results are given, including the
best up to date explicit approximation thresholds for bounded
occurence satisfiability problems, like MAX-2SAT and E2-LIN-2,
and problems in bounded degree graphs, like MIS, Node Cover
and MAX CUT. We prove also for the first time inapproximability
more >>>

TR98-066 | 3rd November 1998
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

This paper strengthens the low-error PCP characterization of NP, coming
closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for
membership in any NP language can be verified with a constant
number of accesses, and with an error probability exponentially
small in the ... more >>>

TR98-067 | 12th November 1998
Paul Beame

Propositional Proof Complexity: Past, Present and Future

Proof complexity, the study of the lengths of proofs in
propositional logic, is an area of study that is fundamentally connected
both to major open questions of computational complexity theory and
to practical properties of automated theorem provers. In the last
decade, there have been a number of significant advances ... more >>>

TR98-068 | 12th November 1998
Petr Savicky

On Random Orderings of Variables for Parity OBDDs

There are Boolean functions such that almost all orderings of
its variables yield an OBDD of polynomial size, but there are
also some exceptional orderings, for which the size is exponential.
We prove that for parity OBDDs the size for a random ordering
... more >>>

TR98-069 | 7th December 1998
Rüdiger Reischuk, Thomas Zeugmann

An Average-Case Optimal One-Variable Pattern Language Learner

A new algorithm for learning one-variable pattern languages from positive data
is proposed and analyzed with respect to its average-case behavior.
We consider the total learning time that takes into account all
operations till convergence to a correct hypothesis is achieved.

For almost all meaningful distributions
defining how ... more >>>

TR98-070 | 7th December 1998
Rüdiger Reischuk

Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?

For ordinary circuits with a fixed upper bound on the maximal fanin
of gates it has been shown that logarithmic redundancy is necessary and
sufficient to overcome random hardware faults.
Here, we consider the same question for unbounded fanin circuits that
in the noiseless case can compute ... more >>>

TR98-071 | 26th November 1998
Itsik Pe'er, Ron Shamir

The median problems for breakpoints are NP-complete

The breakpoint distance between two $n$-permutations is the number
of pairs that appear consecutively in one but not in the other. In
the median problem for breakpoints one is given a set of
permutations and has to construct a permutation that minimizes the
sum of breakpoint ... more >>>

TR98-072 | 14th December 1998
Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

Deterministic Amplification of Space Bounded Probabilistic Algorithms.

This paper initiates the study of deterministic amplification of space
bounded probabilistic algorithms. The straightforward implementations of
known amplification methods cannot be used for such algorithms, since they
consume too much space. We present a new implementation of the
Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$ ... more >>>

TR98-073 | 14th December 1998
Tomoyuki Yamakami, Andrew Chi-Chih Yao

NQP = co-C_{=}P

Revisions: 2

Adleman, DeMarrais, and Huang introduced the
nondeterministic quantum polynomial-time complexity class NQP as an
analogue of NP. It is known that, with restricted amplitudes, NQP is
characterized in terms of the classical counting complexity class
C_{=}P. In this paper we prove that, with unrestricted amplitudes,
NQP indeed coincides with the ... more >>>

TR98-074 | 16th December 1998
Madhu Sudan, Luca Trevisan, Salil Vadhan

Pseudorandom generators without the XOR Lemma

Revisions: 2

Impagliazzo and Wigderson have recently shown that
if there exists a decision problem solvable in time $2^{O(n)}$
and having circuit complexity $2^{\Omega(n)}$
(for all but finitely many $n$) then $\p=\bpp$. This result
is a culmination of a series of works showing
connections between the existence of hard predicates
and ... more >>>

TR98-075 | 9th December 1998
Adam Klivans, Dieter van Melkebeek

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
size oracle circuits with access to satisfiability. We show that every
language with ... more >>>

TR98-076 | 13th November 1998
Nader H. Bshouty, Jeffrey J. Jackson, Christino Tamon

Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution

We study attribute efficient learning in the PAC learning model with
membership queries. First, we give an {\it attribute efficient}
PAC-learning algorithm for DNF with membership queries under the
uniform distribution. Previous algorithms for DNF have sample size
polynomial in the number of attributes $n$. Our algorithm is the
first ... more >>>

TR98-077 | 19th December 1998
Miklos Ajtai

Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Revisions: 1

Our computational model is a random access machine with $n$
read only input registers each containing $ c \log n$ bits of
information and a read and write memory. We measure the time by the
number of accesses to the input registers. We show that for all $k$
there is ... more >>>

TR98-078 | 1st December 1998
Vikraman Arvind, K.V. Subrahmanyam, Vinodchandran Variyam

The Query Complexity of Program Checking by Constant-Depth Circuits

In this paper we study program checking (in the
sense of Blum and Kannan) using constant-depth circuits as
checkers. Our focus is on the number of queries made by the
checker to the program being checked and we term this as the
query complexity of the checker for the given ... more >>>

ISSN 1433-8092 | Imprint