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

__
TR98-002
| 8th January 1998
__

Jayram S. Thathachar#### On Separating the Read-k-Times Branching Program Hierarchy

__
TR98-003
| 3rd November 1997
__

I. Cahit, M. Tezer#### Irregular Assignments of the Forest of Paths

__
TR98-004
| 13th January 1998
__

Farid Ablayev, Marek Karpinski#### On the Power of Randomized Ordered Branching Programs

__
TR98-005
| 27th January 1998
__

Jin-Yi Cai#### A new transference theorem and applications to Ajtai's connection factor

__
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

__
TR98-007
| 12th January 1998
__

Luca Trevisan#### Recycling Queries in PCPs and in Linearity Tests

__
TR98-008
| 15th January 1998
__

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy#### Proof verification and the hardness of approximation problems.

__
TR98-009
| 25th November 1997
__

Bruce Edward Litow#### Parallel complexity of integer coprimality

Comments: 3

__
TR98-010
| 22nd January 1998
__

Phong Nguyen, Jacques Stern#### A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications

Revisions: 1

__
TR98-011
| 29th January 1998
__

Farid Ablayev, Marek Karpinski#### A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs

__
TR98-012
| 2nd February 1998
__

Meena Mahajan, V Vinay#### Determinant: Old Algorithms, New Insights

__
TR98-013
| 3rd March 1998
__

Nader Bshouty#### A New Composition Theorem for Learning Algorithms

__
TR98-014
| 6th February 1998
__

Gunter Blache, Marek Karpinski, Juergen Wirtgen#### On Approximation Intractability of the Bandwidth Problem

__
TR98-015
| 16th January 1998
__

Valentin E. Brimkov, Stefan S. Dantchev#### Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients

__
TR98-016
| 24th March 1998
__

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

__
TR98-017
| 29th March 1998
__

Oded Goldreich, Madhu Sudan#### Computational Indistinguishability: A Sample Hierarchy.

__
TR98-018
| 27th March 1998
__

Martin Sauerhoff#### Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

Comments: 1

__
TR98-019
| 5th April 1998
__

Eric Allender, Klaus Reinhardt#### Isolation, Matching, and Counting

__
TR98-020
| 10th April 1998
__

Andris Ambainis, David Mix Barrington, Huong LeThanh#### On Counting $AC^0$ Circuits with Negative Constants

__
TR98-021
| 7th April 1998
__

Shai Ben-David, Anna Gringauze.#### On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic.

Revisions: 1

__
TR98-022
| 14th April 1998
__

Steffen Reith, Heribert Vollmer#### The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

__
TR98-023
| 16th April 1998
__

Eric Allender, Shiyu Zhou#### Uniform Inclusions in Nondeterministic Logspace

__
TR98-024
| 28th April 1998
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### On Approximation Hardness of Dense TSP and other Path Problems

__
TR98-026
| 5th May 1998
__

Richard Beigel#### Gaps in Bounded Query Hierarchies

__
TR98-027
| 15th April 1998
__

Vikraman Arvind, Jacobo Toran#### Sparse sets, approximable sets, and parallel queries to NP

__
TR98-028
| 28th May 1998
__

Paul Beame, Faith Fich#### On Searching Sorted Lists: A Near-Optimal Lower Bound

__
TR98-029
| 27th May 1998
__

Piotr Berman, Marek Karpinski#### On Some Tighter Inapproximability Results

__
TR98-030
| 9th June 1998
__

Stasys Jukna, Stanislav Zak#### On Branching Programs With Bounded Uncertainty

__
TR98-031
| 4th May 1998
__

Dimitris Fotakis, Paul Spirakis#### Graph Properties that Facilitate Travelling

__
TR98-032
| 10th June 1998
__

Mihir Bellare, Oded Goldreich, Erez Petrank#### Uniform Generation of NP-witnesses using an NP-oracle.

__
TR98-033
| 12th June 1998
__

C.P. Schnorr#### Security of Allmost ALL Discrete Log Bits

__
TR98-034
| 23rd June 1998
__

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan#### A tight characterization of NP with 3 query PCPs

__
TR98-035
| 8th May 1998
__

Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen#### Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

__
TR98-036
| 11th June 1998
__

Vince Grolmusz, Gábor Tardos#### Lower Bounds for (MOD p -- MOD m) Circuits

__
TR98-037
| 29th June 1998
__

Johannes Köbler, Rainer Schuler#### Average-Case Intractability vs. Worst-Case Intractability

__
TR98-038
| 9th July 1998
__

Marek Karpinski#### On the Computational Power of Randomized Branching Programs

__
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

__
TR98-040
| 24th July 1998
__

Madhu Sudan, Luca Trevisan#### Probabilistically checkable proofs with low amortized query complexity

__
TR98-041
| 27th July 1998
__

Stasys Jukna#### Combinatorics of Monotone Computations

__
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

__
TR98-043
| 27th July 1998
__

Venkatesan Guruswami, Madhu Sudan#### Improved decoding of Reed-Solomon and algebraic-geometric codes.

__
TR98-044
| 31st July 1998
__

Jiri Sgall#### Bounds on Pairs of Families with Restricted Intersections

__
TR98-045
| 17th July 1998
__

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

__
TR98-047
| 21st August 1998
__

Salil Vadhan#### Extracting All the Randomness from a Weakly Random Source

Revisions: 1
,
Comments: 1

__
TR98-048
| 6th July 1998
__

Irit Dinur, Guy Kindler, Shmuel Safra#### Approximating CVP to Within Almost Polynomial Factor is NP-Hard

__
TR98-049
| 10th July 1998
__

Dimitris Fotakis, Paul Spirakis#### Random Walks, Conditional Hitting Sets and Partial Derandomization

__
TR98-050
| 6th July 1998
__

Farid Ablayev, Svetlana Ablayeva#### A Discrete Approximation and Communication Complexity Approach to the Superposition Problem

__
TR98-051
| 20th July 1998
__

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

__
TR98-052
| 5th August 1998
__

Boris Hemkemeier, Frank Vallentin#### On the decomposition of lattices

Revisions: 1

__
TR98-053
| 30th August 1998
__

Paul Beame, Michael Saks, Jayram S. Thathachar#### Time-Space Tradeoffs for Branching Programs

Comments: 1

__
TR98-054
| 26th August 1998
__

Igor E. Shparlinski#### On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

__
TR98-055
| 4th September 1998
__

Luca Trevisan#### Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

Comments: 1

__
TR98-056
| 31st August 1998
__

Anna Bernasconi, Igor E. Shparlinski#### Circuit Complexity of Testing Square-Free Numbers

__
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

__
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

__
TR98-059
| 15th September 1998
__

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer#### The Descriptive Complexity Approach to LOGCFL

__
TR98-060
| 8th October 1998
__

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan#### Learning polynomials with queries -- The highly noisy case.

__
TR98-061
| 29th September 1998
__

Robert H. Sloan, Ken Takata, György Turán#### On frequent sets of Boolean matrices

__
TR98-062
| 28th October 1998
__

Oded Goldreich, Dana Ron, Madhu Sudan#### Chinese Remaindering with Errors

Revisions: 4
,
Comments: 1

__
TR98-063
| 4th November 1998
__

Oded Goldreich, Salil Vadhan#### Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

__
TR98-064
| 6th November 1998
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

__
TR98-065
| 6th November 1998
__

Piotr Berman, Marek Karpinski#### On Some Tighter Inapproximability Results, Further Improvements

__
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

__
TR98-067
| 12th November 1998
__

Paul Beame#### Propositional Proof Complexity: Past, Present and Future

__
TR98-068
| 12th November 1998
__

Petr Savicky#### On Random Orderings of Variables for Parity OBDDs

__
TR98-069
| 7th December 1998
__

Rüdiger Reischuk, Thomas Zeugmann#### An Average-Case Optimal One-Variable Pattern Language Learner

__
TR98-070
| 7th December 1998
__

Rüdiger Reischuk#### Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?

__
TR98-071
| 26th November 1998
__

Itsik Pe'er, Ron Shamir#### The median problems for breakpoints are NP-complete

__
TR98-072
| 14th December 1998
__

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson#### Deterministic Amplification of Space Bounded Probabilistic Algorithms.

__
TR98-073
| 14th December 1998
__

Tomoyuki Yamakami, Andrew Chi-Chih Yao#### NQP = co-C_{=}P

Revisions: 2

__
TR98-074
| 16th December 1998
__

Madhu Sudan, Luca Trevisan, Salil Vadhan#### Pseudorandom generators without the XOR Lemma

Revisions: 2

__
TR98-075
| 9th December 1998
__

Adam Klivans, Dieter van Melkebeek#### Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

__
TR98-076
| 13th November 1998
__

Nader Bshouty, Jeffrey J. Jackson, Christino Tamon#### Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution

__
TR98-077
| 19th December 1998
__

Miklos Ajtai#### Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Revisions: 1

__
TR98-078
| 1st December 1998
__

Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran#### The Query Complexity of Program Checking by Constant-Depth Circuits

Detlef Sieling

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

Jayram S. Thathachar

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

I. Cahit, M. Tezer

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

Farid Ablayev, Marek Karpinski

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

Jin-Yi Cai

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

Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

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

Luca Trevisan

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

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

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

Bruce Edward Litow

It is shown that integer coprimality is in NC.

more >>>Phong Nguyen, Jacques Stern

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

Farid Ablayev, Marek Karpinski

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

Meena Mahajan, V Vinay

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

Nader Bshouty

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

Gunter Blache, Marek Karpinski, Juergen Wirtgen

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

Valentin E. Brimkov, Stefan S. Dantchev

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

Daniele Micciancio

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.

Oded Goldreich, Madhu Sudan

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

Martin Sauerhoff

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

Eric Allender, Klaus Reinhardt

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

Andris Ambainis, David Mix Barrington, Huong LeThanh

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

Shai Ben-David, Anna Gringauze.

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

Steffen Reith, Heribert Vollmer

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

Eric Allender, Shiyu Zhou

We show that the complexity class LogFew is contained

in NL $\cap$ SPL. Previously, this was known only to

hold in the nonuniform setting.

Wenceslas Fernandez de la Vega, Marek Karpinski

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

Richard Beigel

<html>

Prior results show that most bounded query hierarchies cannot

contain finite gaps. For example, it is known that

<center>

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>

</center>

and for all sets <i>A</i>

<ul>

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

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

Vikraman Arvind, Jacobo Toran

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

Paul Beame, Faith Fich

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

Piotr Berman, Marek Karpinski

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

Stasys Jukna, Stanislav Zak

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

Dimitris Fotakis, Paul Spirakis

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

Mihir Bellare, Oded Goldreich, Erez Petrank

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

C.P. Schnorr

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

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

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

Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

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

Vince Grolmusz, Gábor Tardos

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

Johannes Köbler, Rainer Schuler

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

Marek Karpinski

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

Christoph Meinel, Thorsten Theobald

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

Madhu Sudan, Luca Trevisan

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

Stasys Jukna

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

Pavel Pudlak

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

Venkatesan Guruswami, Madhu Sudan

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

Jiri Sgall

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

Detlef Sieling

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

Salil Vadhan

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

Irit Dinur, Guy Kindler, Shmuel Safra

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}$.

Dimitris Fotakis, Paul Spirakis

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

Farid Ablayev, Svetlana Ablayeva

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

Petr Savicky

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

Boris Hemkemeier, Frank Vallentin

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

Paul Beame, Michael Saks, Jayram S. Thathachar

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

Igor E. Shparlinski

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

Luca Trevisan

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

Anna Bernasconi, Igor E. Shparlinski

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

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

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

H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

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

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer

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

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

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

Robert H. Sloan, Ken Takata, György Turán

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

Oded Goldreich, Dana Ron, Madhu Sudan

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

Oded Goldreich, Salil Vadhan

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

Wenceslas Fernandez de la Vega, Marek Karpinski

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

Piotr Berman, Marek Karpinski

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

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

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

Paul Beame

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

Petr Savicky

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

Rüdiger Reischuk, Thomas Zeugmann

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

Rüdiger Reischuk

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

Itsik Pe'er, Ron Shamir

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

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

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

Tomoyuki Yamakami, Andrew Chi-Chih Yao

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

Madhu Sudan, Luca Trevisan, Salil Vadhan

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

Adam Klivans, Dieter van Melkebeek

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

Nader Bshouty, Jeffrey J. Jackson, Christino Tamon

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

Miklos Ajtai

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

Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran

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