Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2000:
All reports in year 2000:
TR00-001 | 14th January 2000
Piotr Berman, Moses Charikar, Marek Karpinski

#### On-Line Load Balancing for Related Machines

We consider the problem of scheduling permanent jobs on related machines
in an on-line fashion. We design a new algorithm that achieves the
competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic
version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,
improving the previous competitive ratios ... more >>>

TR00-002 | 23rd December 1999
Michael Schmitt

#### Lower Bounds on the Complexity of Approximating Continuous Functions by Sigmoidal Neural Networks

We calculate lower bounds on the size of sigmoidal neural networks
that approximate continuous functions. In particular, we show that
for the approximation of polynomials the network size has to grow
as $\Omega((\log k)^{1/4})$ where $k$ is the degree of the polynomials.
This bound is ... more >>>

TR00-003 | 26th November 1999
Matthias Krause, Hans Ulrich Simon

#### Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography

This paper shows that the largest possible contrast C(k,n)
in a k-out-of-n secret sharing scheme is approximately
4^(-(k-1)). More precisely, we show that
4^(-(k-1)) <= C_{k,n} <= 4^(-(k-1))}n^k/(n(n-1)...(n-(k-1))).
This implies that the largest possible contrast equals
4^(-(k-1)) in the limit when n approaches ... more >>>

TR00-004 | 14th January 2000
Oded Goldreich, Salil Vadhan, Avi Wigderson

#### Simplified derandomization of BPP using a hitting set generator.

A hitting-set generator is a deterministic
algorithm which generates a set of strings that intersects
every dense set recognizable by a small circuit.
A polynomial time hitting-set generator readily implies $RP=P$.
Andreev \etal\/ (ICALP'96, and JACM 1998)
showed that if polynomial-time hitting-set
generator in fact implies ... more >>>

TR00-005 | 17th January 2000
Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

#### Near-Optimal Separation of Treelike and General Resolution

We present the best known separation
between tree-like and general resolution, improving
on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.
This is done by constructing a natural family of contradictions, of
size $n$, that have $O(n)$-size resolution
refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.
This result ... more >>>

TR00-006 | 26th January 2000
E.A. Okol'nishnikiva

#### On operations of geometrical projection and monotone extension

Some operations over Boolean functions are considered. It is shown that
the operation of the geometrical projection and the operation of the
monotone extension can increase the complexity of Boolean functions for
formulas in each finite basis, for switching networks, for branching
programs, and read-$k$-times ... more >>>

TR00-007 | 14th December 1999
Pavlos S. Efraimidis, Paul Spirakis

#### Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

The problem of Scheduling $n$ Independent Jobs
on $m$ Unrelated Parallel Machines, when $m$
is fixed, is considered. The standard problem
of minimizing the makespan of the schedule
(SUM) and the bicriteria problem of scheduling
with bounded makespan and cost (SUMC), are
addressed, and randomized fully linear time
more >>>

TR00-008 | 20th January 2000
Albert Atserias, Nicola Galesi, Ricard Gavaldà

#### Monotone Proofs of the Pigeon Hole Principle

We study the complexity of proving the Pigeon Hole
Principle (PHP) in a monotone variant of the Gentzen Calculus, also
known as Geometric Logic. We show that the standard encoding
of the PHP as a monotone sequent admits quasipolynomial-size proofs
in this system. This result is a consequence of ... more >>>

TR00-009 | 21st February 2000
Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

#### Extractors and pseudo-random generators with optimal seed length

We give the first construction of a pseudo-random generator with
optimal seed length that uses (essentially) arbitrary hardness.
It builds on the novel recursive use of the NW-generator in
a previous paper by the same authors, which produced many optimal
generators one of which was pseudo-random. This is achieved ... more >>>

TR00-010 | 12th January 2000
Amitabha Roy, Christopher Wilson

#### Supermodels and Closed Sets

A {\em supermodel} is a satisfying assignment of a boolean formula
for which any small alteration, such as a single bit flip, can be
repaired by another small alteration, yielding a nearby
satisfying assignment. We study computational problems associated
with super models and some generalizations thereof. For general
formulas, ... more >>>

TR00-011 | 27th January 2000
Sotiris Nikoletseas, Paul Spirakis

#### Efficient Communication Establishment in Extremely Unreliable Large Networks

We consider here a large network of $n$ nodes which supports
only the following unreliable basic communication primitive:
when a node requests communication then this request
{\em may fail}, independently of other requests, with probability
$f<1$. Even if it succeeds, the request is answered by returning
a stable link to ... more >>>

TR00-012 | 14th February 2000
Ke Yang

#### Integer Circuit Evaluation is PSPACE-complete

In this paper, we address the problem of evaluating the
Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over
the set of natural numbers. The problem is a natural extension
to the integer expression by Stockmeyer and Mayer, and is also studied
by Mckenzie, Vollmer and Wagner in ... more >>>

TR00-013 | 14th February 2000
Daniel Král

#### Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

Ordered binary decision diagrams (OBDDs) and parity ordered binary
decision diagrams have proved their importance as data structures
representing Boolean functions. In addition to parity OBDDs we study
their generalization which we call parity AOBDDs, give the algebraic
characterization theorem and compare their minimal size to the size
more >>>

TR00-014 | 16th February 2000
Matthias Krause, Stefan Lucks

#### On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators

\begin{abstract}
A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator
(PRFG) if communicating
with a randomly chosen secret function from $F$ cannot be
efficiently distinguished from communicating with a truly random function.
We ask for the minimal hardware complexity of a PRFG. This question ... more >>>

TR00-015 | 16th February 2000
Andrej Muchnik, Alexej Semenov

#### Multi-conditional Descriptions and Codes in Kolmogorov Complexity

TR00-016 | 29th February 2000
Mikhail V. Vyugin

#### Information Distance and Conditional Complexities

C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, and W.H.~Zurek
have defined information distance between two strings $x$, $y$
as
$$d(x,y)=\max\{ K(x|y), K(y|x) \}$$
where $K(x|y)$ is the conditional Kolmogorov complexity.
It is easy to see that for any string $x$ and any integer $n$
there is a string $y$ ... more >>>

TR00-017 | 3rd March 2000
Valentin E. Brimkov, Stefan S. Dantchev

#### On the Algebraic Complexity of Integer Programming

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ... more >>> TR00-018 | 16th February 2000 Oliver Kullmann #### An application of matroid theory to the SAT problem A basic property of minimally unsatisfiable clause-sets F is that c(F) >= n(F) + 1 holds, where c(F) is the number of clauses, and n(F) the number of variables. Let MUSAT(k) be the class of minimally unsatisfiable clause-sets F with c(F) <= n(F) + k. Poly-time decision algorithms are known ... more >>> TR00-019 | 20th March 2000 Edward Hirsch #### Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search During the past three years there was an explosion of algorithms solving MAX-SAT and MAX-2-SAT in worst-case time of the order c^K, where c<2 is a constant, and K is the number of clauses in the input formula. Such bounds w.r.t. the number of variables instead of the number of ... more >>> TR00-020 | 27th March 2000 Oded Goldreich, Dana Ron #### On Testing Expansion in Bounded-Degree Graphs We consider testing graph expansion in the bounded-degree graph model. Specifically, we refer to algorithms for testing whether the graph has a second eigenvalue bounded above by a given threshold or is far from any graph with such (or related) property. We present a natural algorithm aimed ... more >>> TR00-021 | 19th April 2000 Uriel Feige, Marek Karpinski, Michael Langberg #### Improved Approximation of MAX-CUT on Graphs of Bounded Degree We analyze the addition of a simple local improvement step to various known randomized approximation algorithms. Let$\alpha \simeq 0.87856$denote the best approximation ratio currently known for the Max Cut problem on general graphs~\cite{GW95}. We consider a semidefinite relaxation of the Max Cut problem, round it using the ... more >>> TR00-022 | 2nd May 2000 Rosario Gennaro, Luca Trevisan #### Lower bounds on the efficiency of generic cryptographic constructions We present lower bounds on the efficiency of constructions for Pseudo-Random Generators (PRGs) and Universal One-Way Hash Functions (UOWHFs) based on black-box access to one-way permutations. Our lower bounds are tight as they match the efficiency of known constructions. A PRG (resp. UOWHF) construction based on black-box access is a ... more >>> TR00-023 | 11th May 2000 Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson #### Pseudorandom Generators in Propositional Proof Complexity We call a pseudorandom generator$G_n:\{0,1\}^n\to \{0,1\}^m${\em hard} for a propositional proof system$P$if$P$can not efficiently prove the (properly encoded) statement$G_n(x_1,\ldots,x_n)\neq b$for {\em any} string$b\in\{0,1\}^m$. We consider a variety of combinatorial'' pseudorandom generators inspired by the Nisan-Wigderson generator on the one hand, and ... more >>> TR00-024 | 16th May 2000 Amihood Amir, Richard Beigel, William Gasarch #### Some Connections between Bounded Query Classes and Non-Uniform Complexity Let A(x) be the characteristic function of A. Consider the function F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be computed with fewer than k queries to some set X, then A can be computed by polynomial size circuits. A generalization of this result has applications to bounded query ... more >>> TR00-025 | 20th May 2000 Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee #### Super-linear time-space tradeoff lower bounds for randomized computation We prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques are an extension of those used by Ajtai in his ... more >>> TR00-026 | 11th April 2000 Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin #### Combinatorial Interpretation of Kolmogorov Complexity The very first Kolmogorov's paper on algorithmic information theory was entitled Three approaches to the definition of the quantity of information'. These three approaches were called combinatorial, probabilistic and algorithmic. Trying to establish formal connections between combinatorial and algorithmic approaches, we prove that any ... more >>> TR00-027 | 11th April 2000 Pavol Duris, Juraj Hromkovic, Katsushi Inoue #### A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory. In this paper for the first time a "strong" separation between the power of determinism, Las Vegas randomization, and nondeterminism for a compu- ting model is proved. The computing ... more >>> TR00-028 | 17th April 2000 Lance Fortnow, Dieter van Melkebeek #### Time-Space Tradeoffs for Nondeterministic Computation We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time$n^{1.618}$and space$n^{o(1)}$. This improves recent results of Lipton and Viglas and Fortnow. more >>> TR00-029 | 30th April 2000 Ran Raz, Amir Shpilka #### Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates Revisions: 1 We prove super-linear lower bounds for the number of edges in constant depth circuits with$n$inputs and up to$n$outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits, constant depth threshold circuits ... more >>> TR00-030 | 31st May 2000 #### A Simple Model for Neural Computation with Firing Rates and Firing Correlations A simple extension of standard neural network models is introduced that provides a model for neural computations that involve both firing rates and firing correlations. Such extension appears to be useful since it has been shown that firing correlations play a significant computational role in many biological neural systems. Standard ... more >>> TR00-031 | 31st May 2000 Eduardo D. Sontag #### Neural Systems as Nonlinear Filters Experimental data show that biological synapses behave quite differently from the symbolic synapses in all common artificial neural network models. Biological synapses are dynamic, i.e., their weight'' changes on a short time scale by several hundred percent in dependence of the past input to the synapse. ... more >>> TR00-032 | 31st May 2000 #### On the Computational Power of Winner-Take-All In this paper the computational power of a new type of gate is studied: winner-take-all gates. This work is motivated by the fact that the cost of implementing a winner-take-all gate in analog VLSI is about the same as that of implementing a threshold gate. We show that ... more >>> TR00-033 | 22nd May 2000 Jan Krajicek #### Tautologies from pseudo-random generators Revisions: 1 We consider tautologies formed from a pseudo-random number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99} and in Alekhnovich et.al. \cite{ABRW}. We explain a strategy of proving their hardness for EF via a conjecture about bounded arithmetic formulated in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a purely finitary statement, in a ... more >>> TR00-034 | 5th June 2000 Valentine Kabanets, Charles Rackoff, Stephen Cook #### Efficiently Approximable Real-Valued Functions We consider a class, denoted APP, of real-valued functions f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to within any epsilon>0, by a probabilistic Turing machine running in time poly(n,1/epsilon). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete ... more >>> TR00-035 | 6th June 2000 Nikolay Vereshchagin, Mikhail V. Vyugin #### Independent minimum length programs to translate between given strings A string$p$is called a program to compute$y$given$x$if$U(p,x)=y$, where$U$denotes universal programming language. Kolmogorov complexity$K(y|x)$of$y$relative to$x$is defined as minimum length of a program to compute$y$given$x$. Let$K(x)$denote$K(x|\text{empty string})$(Kolmogorov complexity of$x$) ... more >>> TR00-036 | 29th May 2000 Carsten Damm, Markus Holzer, Pierre McKenzie #### The Complexity of Tensor Calculus Tensor calculus over semirings is shown relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas with explicit tensor entries is shown complete for$\olpus\P$, for$\NP$, and for$\#\P$as the semiring varies. Indeed the permanent of a matrix is shown expressible as ... more >>> TR00-037 | 26th May 2000 Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith #### New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT The maximum 2-satisfiability problem (MAX-2-SAT) is: given a Boolean formula in$2$-CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-2-SAT is MAXSNP-complete. Recently, this problem received much attention in the contexts of approximation (polynomial-time) algorithms ... more >>> TR00-038 | 24th May 2000 #### On Computation with Pulses We explore the computational power of formal models for computation with pulses. Such models are motivated by realistic models for biological neurons, and by related new types of VLSI (pulse stream VLSI''). In preceding work it was shown that the computational power of formal models for computation with pulses is ... more >>> TR00-039 | 25th April 2000 Yevgeniy Dodis #### Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping Collective Coin-Flipping is a classical problem where n computationally unbounded processors are trying to generate a random bit in a setting where only a single broadcast channel is available for communication. The protocol is said to be b(n)-resilient if any adversary that can corrupt up to b(n) players, still cannot ... more >>> TR00-040 | 19th May 2000 Maria Isabel Gonzalez Vasco, Igor E. Shparlinski #### Security of the Most Significant Bits of the Shamir Message Passing Scheme Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a hidden'' element$\alpha$of a finite field$\F_p$of$p$elements from rather short strings of the most significant bits of the remainder mo\-du\-lo$p$of$\alpha t$for several values of$t$selected uniformly at random ... more >>> TR00-041 | 19th May 2000 Igor E. Shparlinski #### Security of Polynomial Transformations of the Diffie--Hellman Key D. Boneh and R. Venkatesan have recently proposed an approach to proving that a reasonably small portions of most significant bits of the Diffie--Hellman key modulo a prime are as secure the the whole key. Some further improvements and generalizations have been obtained by I. M. Gonzales Vasco ... more >>> TR00-042 | 21st June 2000 Lars Engebretsen #### Lower Bounds for non-Boolean Constraint Satisfaction Revisions: 1 We show that the k-CSP problem over a finite Abelian group G cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for any constant epsilon>0, unless P=NP. This lower bound matches well with the best known upper bound, |G|^{k-1}, of Serna, Trevisan and Xhafa. The proof uses a combination of PCP techniques---most notably a ... more >>> TR00-043 | 21st June 2000 Uriel Feige, Marek Karpinski, Michael Langberg #### A Note on Approximating MAX-BISECTION on Regular Graphs We design a$0.795$approximation algorithm for the Max-Bisection problem restricted to regular graphs. In the case of three regular graphs our results imply an approximation ratio of$0.834$. more >>> TR00-044 | 26th June 2000 Tzvika Hartman, Ran Raz #### On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors Weak designs were defined by Raz, Reingold and Vadhan (1999) and are used in constructions of extractors. Roughly speaking, a weak design is a collection of subsets satisfying some near-disjointness properties. Constructions of weak designs with certain parameters are given in [RRV99]. These constructions are explicit in the sense that more >>> TR00-045 | 23rd June 2000 Maria Isabel Gonzalez Vasco, Igor E. Shparlinski #### On the Security of Diffie--Hellman Bits Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a hidden'' element$\alpha$of a finite field$\F_p$of$p$elements from rather short strings of the most significant bits of the remainder mo\-du\-lo$p$of$\alpha t$for several values of$t$selected uniformly at ... more >>> TR00-046 | 19th June 2000 Philipp Woelfel #### New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing Ordered binary decision diagrams (OBDDs) belong to the most important representation types for Boolean functions. Although they allow important operations such as satisfiability test and equality test to be performed efficiently, their limitation lies in the fact, that they may require exponential size for important functions. Bryant ... more >>> TR00-047 | 29th June 2000 Tobias Polzin, Siavash Vahdati Daneshmand #### Primal-Dual Approaches to the Steiner Problem We study several old and new algorithms for computing lower and upper bounds for the Steiner problem in networks using dual-ascent and primal-dual strategies. These strategies have been proven to be very useful for the algorithmic treatment of the Steiner problem. We show that none of the known algorithms ... more >>> TR00-048 | 3rd July 2000 Beate Bollig #### Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, i.e., the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once more >>> TR00-050 | 13th July 2000 Peter Auer, Philip M. Long, Gerhard J. Woeginger #### On the Complexity of Function Learning The majority of results in computational learning theory are concerned with concept learning, i.e. with the special case of function learning for classes of functions with range {0,1}. Much less is known about the theory of learning functions with a larger range such as N or R. In ... more >>> TR00-051 | 14th July 2000 Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas #### Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree$k$-regular graphs for ... more >>> TR00-052 | 3rd July 2000 Beate Bollig, Ingo Wegener #### Approximability and Nonapproximability by Binary Decision Diagrams Many BDD (binary decision diagram) models are motivated by CAD applications and have led to complexity theoretical problems and results. Motivated by applications in genetic programming Krause, Savick\'y, and Wegener (1999) have shown that for the inner product function IP$_n$and the direct storage access function DSA$_n$... more >>> TR00-053 | 5th May 2000 Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim #### Parallel Read Operations Without Memory Contention We address the problem of organizing a set$T$of shared data into the memory modules of a Distributed Memory Machine (DMM) in order to minimize memory access conflicts (i.e. memory contention) during read operations. Previous solutions for this problem can be found as fundamental ... more >>> TR00-054 | 5th May 2000 Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri #### On the power assignment problem in radio networks Given a finite set$S$of points (i.e. the stations of a radio network) on a$d$-dimensional Euclidean space and a positive integer$1\le h \le |S|-1$, the \minrangeh{d} problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption, provided ... more >>> TR00-055 | 14th July 2000 Peter Auer, Stephen Kwek, Manfred K. Warmuth #### Learning of Depth Two Neural Networks with Constant Fan-in at the Hidden Nodes We present algorithms for learning depth two neural networks where the hidden nodes are threshold gates with constant fan-in. The transfer function of the output node might be more general: we have results for the cases when the threshold function, the logistic function or the identity function is ... more >>> TR00-056 | 20th July 2000 Oded Goldreich, Avi Wigderson #### On Pseudorandomness with respect to Deterministic Observers. In the theory of pseudorandomness, potential (uniform) observers are modeled as probabilistic polynomial-time machines. In fact many of the central results in that theory are proven via probabilistic polynomial-time reductions. In this paper we show that analogous deterministic reductions are unlikely to hold. We conclude that randomness ... more >>> TR00-057 | 25th July 2000 Martin Sauerhoff #### An Improved Hierarchy Result for Partitioned BDDs One of the great challenges of complexity theory is the problem of analyzing the dependence of the complexity of Boolean functions on the resources nondeterminism and randomness. So far, this problem could be solved only for very few models of computation. For so-called partitioned binary decision diagrams, which are a ... more >>> TR00-058 | 1st August 2000 Martin Sauerhoff #### Approximation of Boolean Functions by Combinatorial Rectangles This paper deals with the number of monochromatic combinatorial rectangles required to approximate a Boolean function on a constant fraction of all inputs, where each rectangle may be defined with respect to its own partition of the input variables. The main result of the paper is that the number of ... more >>> TR00-059 | 11th August 2000 Omer Reingold, Ronen Shaltiel, Avi Wigderson #### Extracting Randomness via Repeated Condensing On an input probability distribution with some (min-)entropy an {\em extractor} outputs a distribution with a (near) maximum entropy rate (namely the uniform distribution). A natural weakening of this concept is a condenser, whose output distribution has a higher entropy rate than the input distribution (without losing much of ... more >>> TR00-060 | 17th August 2000 Uri Zwick #### All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication We present two new algorithms for solving the {\em All Pairs Shortest Paths\/} (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms. The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in ... more >>> TR00-061 | 14th August 2000 Prahladh Harsha, Madhu Sudan #### Small PCPs with low query complexity Most known constructions of probabilistically checkable proofs (PCPs) either blow up the proof size by a large polynomial, or have a high (though constant) query complexity. In this paper we give a transformation with slightly-super-cubic blowup in proof size, with a low query complexity. Specifically, the verifier probes the proof ... more >>> TR00-062 | 25th August 2000 Venkatesan Guruswami, Johan Hastad, Madhu Sudan #### Hardness of approximate hypergraph coloring We introduce the notion of covering complexity of a probabilistic verifier. The covering complexity of a verifier on a given input is the minimum number of proofs needed to `satisfy'' the verifier on every random string, i.e., on every random string, at least one of the given proofs must be ... more >>> TR00-063 | 13th July 2000 Peter Auer #### On-line Learning of Rectangles in Noisy Environments We investigate the implications of noise in the equivalence query model. Besides some results for general target and hypotheses classes, we prove bounds on the learning complexity of d-dimensional discretized rectangles in the case where only rectangles are allowed as hypotheses. Our noise model assumes ... more >>> TR00-064 | 29th August 2000 Klaus Jansen, Marek Karpinski, Andrzej Lingas #### A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs The Max-Bisection and Min-Bisection are the problems of finding partitions of the vertices of a given graph into two equal size subsets so as to maximize or minimize, respectively, the number of edges with exactly one endpoint in each subset. In this paper we design the first ... more >>> TR00-065 | 7th September 2000 Eric Allender, David Mix Barrington #### Uniform Circuits for Division: Consequences and Problems Comments: 2 The essential idea in the fast parallel computation of division and related problems is that of Chinese remainder representation (CRR) -- storing a number in the form of its residues modulo many small primes. Integer division provides one of the few natural examples of problems for which ... more >>> TR00-066 | 14th July 2000 Peter Auer #### On Learning from Ambiguous Information We investigate a variant of the Probably Almost Correct learning model where the learner has to learn from ambiguous information. The ambiguity is introduced by assuming that the learner does not receive single instances with their correct labels as training data, but that the learner receives ... more >>> TR00-067 | 13th July 2000 Peter Auer, Philip M. Long #### Simulating Access to Hidden Information while Learning We introduce a new technique which enables a learner without access to hidden information to learn nearly as well as a learner with access to hidden information. We apply our technique to solve an open problem of Maass and Turan, showing that for any concept class F the least ... more >>> TR00-068 | 13th July 2000 Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, Robert E. Schapire #### Gambling in a rigged casino: The adversarial multi-armed bandit problem In the multi-armed bandit problem, a gambler must decide which arm of K non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration ... more >>> TR00-069 | 14th July 2000 Peter Auer #### Learning Nested Differences in the Presence of Malicious Noise We present a PAC-learning algorithm and an on-line learning algorithm for nested differences of intersection-closed classes. Examples of intersection-closed classes include axis-parallel rectangles, monomials, and linear sub-spaces. Our PAC-learning algorithm uses a pruning technique that we rigorously proof correct. As a result we show that ... more >>> TR00-070 | 14th July 2000 Peter Auer, Manfred K. Warmuth #### Tracking the best disjunction Littlestone developed a simple deterministic on-line learning algorithm for learning$k$-literal disjunctions. This algorithm (called Winnow) keeps one weight for each variable and does multiplicative updates to its weights. We develop a randomized version of Winnow and prove bounds for an adaptation of the algorithm ... more >>> TR00-071 | 14th July 2000 Peter Auer, Nicolo Cesa-Bianchi #### On-line Learning with Malicious Noise and the Closure Algorithm We investigate a variant of the on-line learning model for classes of {0,1}-valued functions (concepts) in which the labels of a certain amount of the input instances are corrupted by adversarial noise. We propose an extension of a general learning strategy, known as "Closure Algorithm", to this noise ... more >>> TR00-072 | 14th July 2000 Peter Auer, Philip M. Long, Aravind Srinivasan #### Approximating Hyper-Rectangles: Learning and Pseudo-random Sets The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for several applied learning problems. Also, pseudorandom sets for rectangles have been actively studied recently because (i) they are a subproblem common to the derandomization of depth-2 (DNF) ... more >>> TR00-073 | 28th August 2000 Venkatesan Guruswami, Sanjeev Khanna #### On the Hardness of 4-coloring a 3-colorable Graph We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known (Khanna, Linial, Safra 1992), but our proof is novel as it does not rely on the PCP theorem, while the earlier one does. This ... more >>> TR00-074 | 12th July 2000 Daniele Micciancio, Bogdan Warinschi #### A Linear Space Algorithm for Computing the Hermite Normal Form Computing the Hermite Normal Form of an$n\times n$matrix using the best current algorithms typically requires$O(n^3\log M)$space, where$M$is a bound on the length of the columns of the input matrix. Although polynomial in the input size (which ... more >>> TR00-075 | 7th September 2000 Andreas Klein, Martin Kutrib #### Deterministic Turing Machines in the Range between Real-Time and Linear-Time Deterministic k-tape and multitape Turing machines with one-way, two-way and without a separated input tape are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form n+r(n) where r in o(n) is a sublinear function. It is shown that there ... more >>> TR00-076 | 24th August 2000 Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert #### Measures of Nondeterminism in Finite Automata While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the ... more >>> TR00-077 | 24th August 2000 Till Tantau #### On the Power of Extra Queries to Selective Languages Revisions: 1 A language is \emph{selective} if there exists a selection algorithm for it. Such an algorithm selects from any two words one, which is an element of the language whenever at least one of them is. Restricting the complexity of selection algorithms yields different \emph{selectivity classes} ... more >>> TR00-078 | 18th July 2000 Jean-Pierre Seifert #### Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation} While quantum computers might speed up in principle certain computations dramatically, in pratice, though quantum computing technology is still in its infancy. Even we cannot clearly envison at present what the hardware of that machine will be like. Nevertheless, we can be quite confident that it will be more >>> TR00-079 | 12th September 2000 Mark Jerrum, Eric Vigoda #### A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries. more >>> TR00-080 | 24th July 2000 Marco Cesati #### Perfect Code is W[1]-complete We show that the parameterized problem Perfect Code belongs to W[1]. This result closes an old open question, because it was often conjectured that Perfect Code could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership of the parameterized problem Weighted more >>> TR00-081 | 5th September 2000 Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe #### On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P neq NP. As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT using a version of the standard distribution ... more >>> TR00-082 | 17th August 2000 Lefteris Kirousis, Phokion G. Kolaitis #### The Complexity of Minimal Satisfiability Problems Revisions: 2 A dichotomy theorem for a class of decision problems is a result asserting that certain problems in the class are solvable in polynomial time, while the rest are NP-complete. The first remarkable such dichotomy theorem was proved by T.J. Schaefer in 1978. It concerns the ... more >>> TR00-083 | 18th September 2000 Eldar Fischer #### Testing graphs for colorability properties Revisions: 1 Let$P$be a property of graphs. An$\epsilon$-test for$P$is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph$G$with$n$vertices are adjacent or not, distinguishes, with high probability, between the case of$G$satisfying ... more >>> TR00-084 | 6th November 2000 Salil Vadhan, Amit Sahai #### A Complete Problem for Statistical Zero Knowledge We present the first complete problem for SZK, the class of (promise) problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called STATISTICAL DIFFERENCE, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes ... more >>> TR00-085 | 19th September 2000 Rustam Mubarakzjanov #### Probabilistic OBDDs: on Bound of Width versus Bound of Error Ordered binary decision diagrams (OBDDs) are well established tools to represent Boolean functions. There are a lot of results concerning different types of generalizations of OBDDs. The same time, the power of the most general form of OBDD, namely probabilistic (without bounded error) OBDDs, is not studied enough. In ... more >>> TR00-086 | 26th September 2000 Michael Schmitt #### On the Complexity of Computing and Learning with Multiplicative Neural Networks In a great variety of neuron models neural inputs are combined using the summing operation. We introduce the concept of multiplicative neural networks which contain units that multiply their inputs instead of summing them and, thus, allow inputs to interact nonlinearly. The class of multiplicative networks comprises such widely known ... more >>> TR00-087 | 14th November 2000 Albert Atserias, Nicola Galesi, Pavel Pudlak #### Monotone simulations of nonmonotone propositional proofs We show that an LK proof of size$m$of a monotone sequent (a sequent that contains only formulas in the basis$\wedge,\vee$) can be turned into a proof containing only monotone formulas of size$m^{O(\log m)}$and with the number of proof lines polynomial in$m\$. Also we show

... more >>>

TR00-088 | 28th November 2000
Meena Mahajan, V Vinay

#### A note on the hardness of the characteristic polynomial

In this note, we consider the problem of computing the
coefficients of the characteristic polynomial of a given
matrix, and the related problem of verifying the
coefficents.

Santha and Tan [CC98] show that verifying the determinant
(the constant term in the characteristic polynomial) is
complete for the class C=L, ... more >>>

TR00-089 | 1st December 2000
Lars Engebretsen, Marek Karpinski

#### Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

The general asymmetric (and metric) TSP is known to be approximable
only to within an O(log n) factor, and is also known to be
approximable within a constant factor as soon as the metric is
bounded. In this paper we study the asymmetric and symmetric TSP
problems with bounded metrics ... more >>>

TR00-090 | 3rd December 2000
Oded Goldreich

#### Candidate One-Way Functions Based on Expander Graphs

We suggest a candidate one-way function using combinatorial
constructs such as expander graphs. These graphs are used to
determine a sequence of small overlapping subsets of input bits,
to which a hard-wired random predicate is applied.
Thus, the function is extremely easy to evaluate:
all that is needed ... more >>>

TR00-091 | 21st December 2000
Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

#### Approximability of Dense Instances of NEAREST CODEWORD Problem

We give a polynomial time approximation scheme (PTAS) for dense
instances of the NEAREST CODEWORD problem.

more >>>

ISSN 1433-8092 | Imprint