All reports in year 1997:

__
TR97-001
| 8th January 1997
__

Marco Cesati, Luca Trevisan#### On the Efficiency of Polynomial Time Approximation Schemes

__
TR97-002
| 28th January 1997
__

Richard Beigel, Alexis Maciel#### Upper and Lower Bounds for Some Depth-3 Circuit Classes

__
TR97-003
| 29th January 1997
__

Sanjeev Arora, Madhu Sudan#### Improved low-degree testing and its applications

__
TR97-004
| 19th February 1997
__

Marek Karpinski, Alexander Zelikovsky#### Approximating Dense Cases of Covering Problems

Comments: 1

__
TR97-005
| 17th February 1997
__

Moni Naor, Omer Reingold#### On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

__
TR97-006
| 31st January 1997
__

Marco Cesati, Miriam Di Ianni#### Parameterized Parallel Complexity

Comments: 1

__
TR97-007
| 21st February 1997
__

Stasys Jukna#### Exponential Lower Bounds for Semantic Resolution

__
TR97-008
| 16th March 1997
__

Noam Nisan, Ziv Bar-Yossef#### Pointer Jumping Requires Concurrent Read

__
TR97-009
| 12th March 1997
__

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit#### The Computational Complexity of Some Problems of Linear Algebra

__
TR97-010
| 2nd April 1997
__

Marcos Kiwi#### Testing and Weight Distributions of Dual Codes

__
TR97-011
| 7th April 1997
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan#### Weak Random Sources, Hitting Sets, and BPP Simulations

__
TR97-012
| 19th March 1997
__

Luca Trevisan#### On Local versus Global Satisfiability

__
TR97-013
| 13th February 1997
__

Bernd Borchert, Dietrich Kuske, Frank Stephan#### On Existentially First-Order Definable Languages and their Relation to NP

__
TR97-014
| 25th April 1997
__

Klaus Reinhardt, Eric Allender#### Making Nondeterminism Unambiguous

__
TR97-015
| 21st April 1997
__

Jan Krajicek#### Interpolation by a game

__
TR97-016
| 29th April 1997
__

Manindra Agrawal, Eric Allender, Samir Datta#### On TC^0, AC^0, and Arithmetic Circuits

__
TR97-017
| 5th May 1997
__

Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky#### An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

__
TR97-018
| 8th May 1997
__

Oded Goldreich, Shai Halevi#### Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.

__
TR97-019
| 5th May 1997
__

Martin Sauerhoff#### A Lower Bound for Randomized Read-k-Times Branching Programs

__
TR97-020
| 15th May 1997
__

Oded Goldreich#### A Sample of Samplers -- A Computational Perspective on Sampling (survey).

__
TR97-021
| 16th May 1997
__

Farid Ablayev#### Randomization and nondeterminsm are incomparable for ordered read-once branching programs

__
TR97-023
| 3rd June 1997
__

S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener#### On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs

__
TR97-024
| 9th June 1997
__

Marek Karpinski#### Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems

__
TR97-025
| 26th May 1997
__

Harald Hempel, Gerd Wechsung#### The Operators min and max on the Polynomial Hierarchy

__
TR97-026
| 18th June 1997
__

Jochen Me\3ner, Jacobo Toran#### Optimal proof systems for Propositional Logic and complete sets

__
TR97-027
| 29th April 1997
__

Johannes Merkle, Ralph Werchner#### On the Security of Server aided RSA protocols

Revisions: 1

__
TR97-028
| 12th July 1997
__

Scott E. Decatur, Oded Goldreich, Dana Ron#### Computational Sample Complexity

__
TR97-029
| 20th August 1997
__

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger#### On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

__
TR97-030
| 25th August 1997
__

Martin Sauerhoff#### On Nondeterminism versus Randomness for Read-Once Branching Programs

__
TR97-031
| 9th September 1997
__

Oded Goldreich#### On the Limits of Non-Approximability of Lattice Problems

Revisions: 2

__
TR97-032
| 11th July 1997
__

Jan Johannsen#### Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes

__
TR97-033
| 1st August 1997
__

Meena Mahajan, Venkatesh Raman#### Parametrizing Above Guaranteed Values: MaxSat and MaxCut

__
TR97-034
| 3rd September 1997
__

Jui-Lin Lee#### Counting in uniform $TC^0$

__
TR97-035
| 31st July 1997
__

Richard Chang#### Bounded Queries, Approximations and the Boolean Hierarchy

Revisions: 1

__
TR97-036
| 1st August 1997
__

Meena Mahajan, V Vinay#### Determinant: Combinatorics, Algorithms, and Complexity

__
TR97-039
| 11th September 1997
__

Pierluigi Crescenzi, Luca Trevisan#### MAX NP-Completeness Made Easy

__
TR97-040
| 17th September 1997
__

Dorit Dor, Shay Halperin, Uri Zwick#### All Pairs Almost Shortest Paths

__
TR97-041
| 18th September 1997
__

Marek Karpinski, Juergen Wirtgen#### On Approximation Hardness of the Bandwidth Problem

__
TR97-042
| 22nd September 1997
__

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall#### Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

__
TR97-043
| 25th September 1997
__

Bruno Codenotti, Pavel Pudlak, Giovanni Resta#### Some structural properties of low rank matrices related to computational complexity

Revisions: 1
,
Comments: 1

__
TR97-044
| 26th September 1997
__

David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum#### Searching constant width mazes captures the AC^0 hierarchy

__
TR97-045
| 29th September 1997
__

Oded Goldreich, David Zuckerman#### Another proof that BPP subseteq PH (and more).

Comments: 1

__
TR97-046
| 3rd October 1997
__

Alexander Barg#### Complexity Issues in Coding Theory

__
TR97-047
| 20th October 1997
__

Miklos Ajtai#### The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

Revisions: 1

__
TR97-048
| 13th October 1997
__

Soren Riis, Meera Sitharam#### Non-constant Degree Lower Bounds imply linear Degree Lower Bounds

__
TR97-049
| 22nd October 1997
__

Michael Schmitt#### On the Complexity of Learning for Spiking Neurons with Temporal Coding

__
TR97-050
| 27th October 1997
__

Stanislav Zak#### A subexponential lower bound for branching programs restricted with regard to some semantic aspects

__
TR97-051
| 11th November 1997
__

Pekka Orponen#### On the Effect of Analog Noise in Discrete-Time Analog Computations

__
TR97-052
| 11th November 1997
__

Eduardo D. Sontag#### Analog Neural Nets with Gaussian or other Common Noise Distributions cannot Recognize Arbitrary Regular Languages

__
TR97-053
| 10th November 1997
__

Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim#### Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs

Revisions: 2

__
TR97-054
| 17th November 1997
__

Ran Raz, GĂˇbor Tardos, Oleg Verbitsky, Nikolay Vereshchagin#### Arthur-Merlin Games in Boolean Decision Trees

__
TR97-055
| 22nd September 1997
__

Bruce Edward Litow#### A Decision Method for the Rational Sequence Problem

__
TR97-056
| 1st December 1997
__

Oded Goldreich#### Combinatorial Property Testing (a survey).

Comments: 1

__
TR97-057
| 3rd November 1997
__

Petr Savicky#### Complexity and Probability of some Boolean Formulas

__
TR97-058
| 2nd December 1997
__

Oded Goldreich#### Notes on Levin's Theory of Average-Case Complexity.

__
TR97-059
| 22nd December 1997
__

Jin-Yi Cai, Ajay Nerurkar#### Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions

__
TR97-060
| 2nd December 1997
__

Manindra Agrawal, Thomas Thierauf#### The Satisfiability Problem for Probabilistic Ordered Branching Programs

__
TR97-061
| 12th November 1997
__

Eli Biham, Dan Boneh, Omer Reingold#### Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring

Marco Cesati, Luca Trevisan

A polynomial time approximation scheme (PTAS) for an optimization

problem $A$ is an algorithm that on input an instance of $A$ and

$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time

that is polynomial for each fixed $\epsilon$. Typical running times

are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ...
more >>>

Richard Beigel, Alexis Maciel

We investigate the complexity of depth-3 threshold circuits

with majority gates at the output, possibly negated AND

gates at level two, and MODm gates at level one. We show

that the fan-in of the AND gates can be reduced to O(log n)

in the case where ...
more >>>

Sanjeev Arora, Madhu Sudan

NP = PCP(log n, 1) and related results crucially depend upon

the close connection between the probability with which a

function passes a ``low degree test'' and the distance of

this function to the nearest degree d polynomial. In this

paper we study a test ...
more >>>

Marek Karpinski, Alexander Zelikovsky

We study dense instances of several covering problems. An instance of

the set cover problem with $m$ sets is dense if there is $\epsilon>0$

such that any element belongs to at least $\epsilon m$ sets. We show

that the dense set cover problem can be approximated with ...
more >>>

Moni Naor, Omer Reingold

Luby and Rackoff showed a method for constructing a pseudo-random

permutation from a pseudo-random function. The method is based on

composing four (or three for weakened security) so called Feistel

permutations each of which requires the evaluation of a pseudo-random

function. We reduce somewhat the complexity ...
more >>>

Marco Cesati, Miriam Di Ianni

We consider the framework of Parameterized Complexity, and we

investigate the issue of which problems do admit efficient fixed

parameter parallel algorithms by introducing two different

degrees of efficiently parallelizable parameterized problems, PNC

and FPP. We sketch both some FPP-algorithms solving natural

parameterized problems and ...
more >>>

Stasys Jukna

In a semantic resolution proof we operate with clauses only

but allow {\em arbitrary} rules of inference:

C_1 C_2 ... C_m

__________________

C

Consistency is the only requirement. We prove a very simple

exponential lower bound for the size ...
more >>>

Noam Nisan, Ziv Bar-Yossef

We consider the well known problem of determining the k'th

vertex reached by chasing pointers in a directed graph of

out-degree 1. The famous "pointer doubling" technique

provides an O(log k) parallel time algorithm on a

Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ...
more >>>

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

We consider the computational complexity of some problems

dealing with matrix rank. Let E,S be subsets of a

commutative ring R. Let x_1, x_2, ..., x_t be variables.

Given a matrix M = M(x_1, x_2, ..., x_t) with entries

chosen from E union {x_1, x_2, ..., ...
more >>>

Marcos Kiwi

We study the testing problem, that is, the problem of determining (maybe

probabilistically) if a function to which we have oracle access

satisfies a given property.

We propose a framework in which to formulate and carry out the analyzes

of several known tests. This framework establishes a connection between

more >>>

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

We show how to simulate any BPP algorithm in polynomial time

using a weak random source of min-entropy $r^{\gamma}$

for any $\gamma >0$.

This follows from a more general result about {\em sampling\/}

with weak random sources.

Our result matches an information-theoretic lower bound ...
more >>>

Luca Trevisan

We prove an extremal combinatorial result regarding

the fraction of satisfiable clauses in boolean CNF

formulae enjoying a locally checkable property, thus

solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint

satisfaction ...
more >>>

Bernd Borchert, Dietrich Kuske, Frank Stephan

Pin & Weil [PW95] characterized the automata of existentially

first-order definable languages. We will use this result for the following

characterization of the complexity class NP. Assume that the

Polynomial-Time Hierarchy does not collapse. Then a regular language

L characterizes NP as an unbalanced polynomial-time leaf language

if and ...
more >>>

Klaus Reinhardt, Eric Allender

We show that in the context of nonuniform complexity,

nondeterministic logarithmic space bounded computation can be made

unambiguous. An analogous result holds for the class of problems

reducible to context-free languages. In terms of complexity classes,

this can be stated as:

NL/poly = UL/poly

LogCFL/poly ...
more >>>

Jan Krajicek

We introduce a notion of a "real game"

(a generalization of the Karchmer - Wigderson game),

and "real communication complexity",

and relate them to the size of monotone real formulas

and circuits. We give an exponential lower bound

for tree-like monotone protocols of small real

communication complexity ...
more >>>

Manindra Agrawal, Eric Allender, Samir Datta

Continuing a line of investigation that has studied the

function classes #P, #SAC^1, #L, and #NC^1, we study the

class of functions #AC^0. One way to define #AC^0 is as the

class of functions computed by constant-depth polynomial-size

arithmetic circuits of unbounded fan-in addition ...
more >>>

Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

The bandwidth problem is the problem of numbering 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

is known to be NP-complete Papadimitriou [Pa76]. Only few special

cases ...
more >>>

Oded Goldreich, Shai Halevi

Following Ajtai's lead, Ajtai and Dwork have recently introduced a

public-key encryption scheme which is secure under the assumption

that a certain computational problem on lattices is hard on the

worst-case. Their encryption method may cause decryption errors,

though with small probability (i.e., inversely proportional to the

more >>>

Martin Sauerhoff

In this paper, we are concerned with randomized OBDDs and randomized

read-k-times branching programs. We present an example of a Boolean

function which has polynomial size randomized OBDDs with small,

one-sided error, but only non-deterministic read-once branching

programs of exponential size. Furthermore, we discuss a lower bound

technique for randomized ...
more >>>

Oded Goldreich

We consider the problem of estimating the average of a huge set of values.

That is,

given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,

we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$

upto an additive error of $\epsilon$.

We are allowed to employ a randomized algorithm which may ...
more >>>

Farid Ablayev

In the manuscript F. Ablayev and M. Karpinski, On the power of

randomized branching programs (generalization of ICALP'96 paper

results for the case of pure boolean function, available at

http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions

$f_n$ in $n$ variables such that:

1) $f_{n}$ can be computed ... more >>>

S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

It is known that if a Boolean function f in n variables

has a DNF and a CNF of size at most N then f also has a

(deterministic) decision tree of size $\exp(O(\log n\log^2 N)$.

We show that this simulation {\em cannot} be ...
more >>>

Marek Karpinski

We survey recent results on the existence of polynomial time

approximation schemes for some dense instances of NP-hard

optimization problems. We indicate further some inherent limits

for existence of such schemes for some other dense instances of

the optimization problems.

Harald Hempel, Gerd Wechsung

We define a general maximization operator max and a general minimization

operator min for complexity classes and study the inclusion structure of

the classes max.P, max.NP, max.coNP, min.P, min.NP, and min.coNP.

It turns out that Krentel's class OptP fits naturally into this frame-

work (it can be ...
more >>>

Jochen Me\3ner, Jacobo Toran

A polynomial time computable function $h:\Sigma^*\to\Sigma^*$ whose range

is the set of tautologies in Propositional Logic (TAUT), is called

a proof system. Cook and Reckhow defined this concept

and in order to compare the relative strenth of different proof systems,

they considered the notion ...
more >>>

Johannes Merkle, Ralph Werchner

In this paper we investigate the security of the server aided

RSA protocols RSA-S1 and RSA-S1M proposed by Matsumoto, Kato and Imai

resp. Matsumoto, Imai, Laih and Yen. We prove lower bounds for the

complexity of attacks on these protocols and show that the bounds are

sharp by describing attacks ...
more >>>

Scott E. Decatur, Oded Goldreich, Dana Ron

In a variety of PAC learning models, a tradeoff between time and

information seems to exist: with unlimited time, a small amount of

information suffices, but with time restrictions, more information

sometimes seems to be required.

In addition, it has long been known that there are

concept classes ...
more >>>

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

The study of the computational power of randomized

computations is one of the central tasks of complexity theory. The

main goal of this paper is the comparison of the power of Las Vegas

computation and deterministic respectively nondeterministic

computation. We investigate the power of Las Vegas computation for ...
more >>>

Martin Sauerhoff

Randomized branching programs are a probabilistic model of computation

defined in analogy to the well-known probabilistic Turing machines.

In this paper, we present complexity theoretic results for randomized

read-once branching programs.

Our main result shows that nondeterminism can be more powerful than

randomness for read-once branching programs. We present a ...
more >>>

Oded Goldreich

We show simple constant-round interactive proof systems for

problems capturing the approximability, to within a factor of $\sqrt{n}$,

of optimization problems in integer lattices; specifically,

the closest vector problem (CVP), and the shortest vector problem (SVP).

These interactive proofs are for the ``coNP direction'';

that is, ...
more >>>

Jan Johannsen

Using a notion of real communication complexity recently

introduced by J. Krajicek, we prove a lower bound on the depth of

monotone real circuits and the size of monotone real formulas for

st-connectivity. This implies a super-polynomial speed-up of dag-like

over tree-like Cutting Planes proofs.

Meena Mahajan, Venkatesh Raman

In this paper we investigate the parametrized

complexity of the problems MaxSat and MaxCut using the

framework developed by Downey and Fellows.

Let $G$ be an arbitrary graph having $n$ vertices and $m$

edges, and let $f$ be an arbitrary CNF formula with $m$

clauses on $n$ variables. We improve ...
more >>>

Jui-Lin Lee

In this paper we first give a uniform $AC^0$ algorithm which uses

partial sums to compute multiple addition. Then we use it to show

that multiple addition is computable in uniform $TC^0$ by using

$count$ only once sequentially. By constructing bit matrix for

multiple addition, ...
more >>>

Richard Chang

This paper introduces a new model of computation for describing the

complexity of NP-approximation problems. The results show that the

complexity of NP-approximation problems can be characterized by classes of

multi-valued functions computed by nondeterministic polynomial time Turing

machines with a bounded number of oracle queries to an NP-complete

language. ...
more >>>

Meena Mahajan, V Vinay

We prove a new combinatorial characterization of the

determinant. The characterization yields a simple

combinatorial algorithm for computing the

determinant. Hitherto, all (known) algorithms for

determinant have been based on linear algebra. Our

combinatorial algorithm requires no division and works over

arbitrary commutative rings. It also lends itself to

more >>>

Pierluigi Crescenzi, Luca Trevisan

We introduce a simple technique to obtain reductions

between optimization constraint satisfaction problems. The

technique uses the probabilistic method to reduce the size of

disjunctions. As a first application, we prove the

MAX NP-completeness of MAX 3SAT without using the PCP theorem

(thus solving an open ...
more >>>

Dorit Dor, Shay Halperin, Uri Zwick

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple

argument shows that computing all distances in G with an additive

one-sided error of at most 1 is as hard as Boolean matrix

multiplication. Building on recent work of Aingworth, Chekuri and

Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time

more >>>

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

and is ...
more >>>

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Razborov~\cite{Razborov96} recently proved that polynomial

calculus proofs of the pigeonhole principle $PHP_n^m$ must have

degree at least $\ceiling{n/2}+1$ over any field. We present a

simplified proof of the same result. The main

idea of our proof is the same as in the original proof

of Razborov: we want to describe ...
more >>>

Bruno Codenotti, Pavel Pudlak, Giovanni Resta

We consider the conjecture stating that a matrix with rank

$o(n)$ and ones on the main diagonal must contain nonzero

entries on a $2\times 2$ submatrix with one entry on the main

diagonal. We show that a slightly stronger conjecture implies

that ...
more >>>

David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum

We show that searching a width k maze is complete for \Pi_k, i.e., for

the k'th level of the AC^0 hierarchy. Equivalently, st-connectivity

for width k grid graphs is complete for \Pi_k. As an application,

we show that there is a data structure solving dynamic st-connectivity

for constant ...
more >>>

Oded Goldreich, David Zuckerman

We provide another proof of the Sipser--Lautemann Theorem

by which $BPP\subseteq MA$ ($\subseteq PH$).

The current proof is based on strong

results regarding the amplification of $BPP$, due to Zuckerman.

Given these results, the current proof is even simpler than previous ones.

Furthermore, extending the proof leads ...
more >>>

Alexander Barg

This is a research-expository paper. It deals with

complexity issues in the theory of linear block codes. The main

emphasis is on the theoretical performance limits of the

best known codes. Therefore, the main subject of the paper are

families of asymptotically good codes, i.e., codes whose rate and

relative ...
more >>>

Miklos Ajtai

We show that the shortest vector problem in lattices

with L_2 norm is NP-hard for randomized reductions. Moreover we

also show that there is a positive absolute constant c, so that to

find a vector which is longer than the shortest non-zero vector by no

more than a factor of ...
more >>>

Soren Riis, Meera Sitharam

The semantics of decision problems are always essentially independent of the

underlying representation. Thus the space of input data (under appropriate

indexing) is closed

under action of the symmetrical group $S_n$ (for a specific data-size)

and the input-output relation is closed under the action of $S_n$.

more >>>

Michael Schmitt

Spiking neurons are models for the computational units in

biological neural systems where information is considered to be encoded

mainly in the temporal pattern of their activity. In a network of

spiking neurons a new set of parameters becomes relevant which has no

counterpart in traditional ...
more >>>

Stanislav Zak

Branching programs (b.p.s) or binary 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. The restrictions based on the number of tests of

more >>>

Pekka Orponen

We introduce a model for analog computation with discrete

time in the presence of analog noise

that is flexible enough to cover the most important concrete

cases, such as noisy analog neural nets and networks of spiking neurons.

This model subsumes the classical ...
more >>>

Eduardo D. Sontag

We consider recurrent analog neural nets where the output of each

gate is subject to Gaussian noise, or any other common noise

distribution that is nonzero on a large set.

We show that many regular languages cannot be recognized by

networks of this type, and

more >>>

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

We show the following Reduction Lemma: any

$\epsilon$-biased sample space with respect to (Boolean) linear

tests is also $2\epsilon$-biased with respect to

any system of independent linear tests. Combining this result with

the previous constructions of $\epsilon$-biased sample space with

respect to linear tests, we obtain the first efficient

more >>>

Ran Raz, GĂˇbor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

It is well known that probabilistic boolean decision trees

cannot be much more powerful than deterministic ones (N.~Nisan, SIAM

Journal on Computing, 20(6):999--1007, 1991). Motivated by a question

if randomization can significantly speed up a nondeterministic

computation via a boolean decision tree, we address structural

properties of Arthur-Merlin games ...
more >>>

Bruce Edward Litow

We give a method to decide whether or not an

ordinary finite order linear recurrence with constant, rational

coefficients ever generates zero.

Oded Goldreich

We consider the question of determining whether

a given object has a predetermined property or is ``far'' from any

object having the property.

Specifically, objects are modeled by functions,

and distance between functions is measured as the fraction

of the domain on which the functions differ.

We ...
more >>>

Petr Savicky

For any Boolean function $f$ let $L(f)$ be its formula size

complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and

every $k\le n/2$, we describe a probabilistic distribution

on formulas in the basis $\{\land,\oplus,1\}$ in some given set of

$n$ variables and of the ...
more >>>

Oded Goldreich

In 1984, Leonid Levin has initiated a theory of average-case complexity.

We provide an exposition of the basic definitions suggested by Levin,

and discuss some of the considerations underlying these definitions.

Jin-Yi Cai, Ajay Nerurkar

Recently Ajtai showed that

to approximate the shortest lattice vector in the $l_2$-norm within a

factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large

constant $k$, is NP-hard under randomized reductions.

We improve this result to show that

to approximate a shortest lattice vector within a

factor $(1+ \mbox{dim}^{-\epsilon})$, for any

$\epsilon>0$, ...
more >>>

Manindra Agrawal, Thomas Thierauf

We show that the satisfiability problem for

bounded error probabilistic ordered branching programs is NP-complete.

If the error is very small however

(more precisely,

if the error is bounded by the reciprocal of the width of the branching program),

then we have a polynomial-time algorithm for the satisfiability problem.

more >>>

Eli Biham, Dan Boneh, Omer Reingold

The Diffie-Hellman key-exchange protocol may naturally be

extended to k>2 parties. This gives rise to the generalized

Diffie-Hellman assumption (GDH-Assumption).

Naor and Reingold have recently shown an efficient construction

of pseudo-random functions and reduced the security of their

construction to the GDH-Assumption.

In this note, we ...
more >>>