Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 1997:
All reports in year 1997:
TR97-001 | 8th January 1997
Marco Cesati, Luca Trevisan

#### On the Efficiency of Polynomial Time Approximation Schemes

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 >>> TR97-002 | 28th January 1997 Richard Beigel, Alexis Maciel #### Upper and Lower Bounds for Some Depth-3 Circuit Classes 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 >>> TR97-003 | 29th January 1997 Sanjeev Arora, Madhu Sudan #### Improved low-degree testing and its applications 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 >>> TR97-004 | 19th February 1997 Marek Karpinski, Alexander Zelikovsky #### Approximating Dense Cases of Covering Problems Comments: 1 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 >>> TR97-005 | 17th February 1997 Moni Naor, Omer Reingold #### On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited 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 >>> TR97-006 | 31st January 1997 Marco Cesati, Miriam Di Ianni #### Parameterized Parallel Complexity Comments: 1 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 >>> TR97-007 | 21st February 1997 Stasys Jukna #### Exponential Lower Bounds for Semantic Resolution 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 >>> TR97-008 | 16th March 1997 Noam Nisan, Ziv Bar-Yossef #### Pointer Jumping Requires Concurrent Read 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 >>> TR97-009 | 12th March 1997 Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit #### The Computational Complexity of Some Problems of Linear Algebra 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 >>> TR97-010 | 2nd April 1997 Marcos Kiwi #### Testing and Weight Distributions of Dual Codes 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 >>> 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 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 >>> TR97-012 | 19th March 1997 Luca Trevisan #### On Local versus Global Satisfiability 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 >>> TR97-013 | 13th February 1997 Bernd Borchert, Dietrich Kuske, Frank Stephan #### On Existentially First-Order Definable Languages and their Relation to NP 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 >>> TR97-014 | 25th April 1997 Klaus Reinhardt, Eric Allender #### Making Nondeterminism Unambiguous 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 >>> TR97-015 | 21st April 1997 Jan Krajicek #### Interpolation by a game 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 >>> TR97-016 | 29th April 1997 Manindra Agrawal, Eric Allender, Samir Datta #### On TC^0, AC^0, and Arithmetic Circuits 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 >>> TR97-017 | 5th May 1997 Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky #### An Approximation Algorithm for the Bandwidth Problem on Dense Graphs 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 >>> TR97-018 | 8th May 1997 Oded Goldreich, Shai Halevi #### Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem. 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 >>> TR97-019 | 5th May 1997 Martin Sauerhoff #### A Lower Bound for Randomized Read-k-Times Branching Programs 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 >>> TR97-020 | 15th May 1997 Oded Goldreich #### A Sample of Samplers -- A Computational Perspective on Sampling (survey). 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 >>> TR97-021 | 16th May 1997 Farid Ablayev #### Randomization and nondeterminsm are incomparable for ordered read-once branching programs 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 >>> 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 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 >>> TR97-024 | 9th June 1997 Marek Karpinski #### Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems 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. more >>> TR97-025 | 26th May 1997 Harald Hempel, Gerd Wechsung #### The Operators min and max on the Polynomial Hierarchy 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 >>> TR97-026 | 18th June 1997 Jochen Me\3ner, Jacobo Toran #### Optimal proof systems for Propositional Logic and complete sets 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 >>> TR97-027 | 29th April 1997 Johannes Merkle, Ralph Werchner #### On the Security of Server aided RSA protocols Revisions: 1 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 >>> TR97-028 | 12th July 1997 Scott E. Decatur, Oded Goldreich, Dana Ron #### Computational Sample Complexity 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 >>> 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 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 >>> TR97-030 | 25th August 1997 Martin Sauerhoff #### On Nondeterminism versus Randomness for Read-Once Branching Programs 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 >>> TR97-031 | 9th September 1997 Oded Goldreich #### On the Limits of Non-Approximability of Lattice Problems Revisions: 2 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 >>> TR97-032 | 11th July 1997 Jan Johannsen #### Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes 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. more >>> TR97-033 | 1st August 1997 Meena Mahajan, Venkatesh Raman #### Parametrizing Above Guaranteed Values: MaxSat and MaxCut 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 >>> TR97-034 | 3rd September 1997 Jui-Lin Lee #### Counting in uniform$TC^0$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 >>> TR97-035 | 31st July 1997 Richard Chang #### Bounded Queries, Approximations and the Boolean Hierarchy Revisions: 1 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 >>> TR97-036 | 1st August 1997 Meena Mahajan, V. Vinay #### Determinant: Combinatorics, Algorithms, and Complexity 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 >>> TR97-039 | 11th September 1997 Pierluigi Crescenzi, Luca Trevisan #### MAX NP-Completeness Made Easy 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 >>> TR97-040 | 17th September 1997 Dorit Dor, Shay Halperin, Uri Zwick #### All Pairs Almost Shortest Paths 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 >>> TR97-041 | 18th September 1997 Marek Karpinski, Juergen Wirtgen #### On Approximation Hardness of the Bandwidth Problem The bandwidth problem is the problem of enumerating the vertices of a given graph$G$such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications and is ... more >>> TR97-042 | 22nd September 1997 Russell Impagliazzo, Pavel Pudlak, Jiri Sgall #### Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm 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 >>> 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 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 >>> 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 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 >>> TR97-045 | 29th September 1997 Oded Goldreich, David Zuckerman #### Another proof that BPP subseteq PH (and more). Comments: 1 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 >>> TR97-046 | 3rd October 1997 Alexander Barg #### Complexity Issues in Coding Theory 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 >>> TR97-047 | 20th October 1997 Miklos Ajtai #### The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions. Revisions: 1 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 >>> TR97-048 | 13th October 1997 Soren Riis, Meera Sitharam #### Non-constant Degree Lower Bounds imply linear Degree Lower Bounds 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 >>> TR97-049 | 22nd October 1997 Michael Schmitt #### On the Complexity of Learning for Spiking Neurons with Temporal Coding 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 >>> TR97-050 | 27th October 1997 Stanislav Zak #### A subexponential lower bound for branching programs restricted with regard to some semantic aspects 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 >>> TR97-051 | 11th November 1997 Pekka Orponen #### On the Effect of Analog Noise in Discrete-Time Analog Computations 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 >>> TR97-052 | 11th November 1997 Eduardo D. Sontag #### Analog Neural Nets with Gaussian or other Common Noise Distributions cannot Recognize Arbitrary Regular Languages 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 >>> 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 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 >>> TR97-054 | 17th November 1997 Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin #### Arthur-Merlin Games in Boolean Decision Trees 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 >>> TR97-055 | 22nd September 1997 Bruce Edward Litow #### A Decision Method for the Rational Sequence Problem We give a method to decide whether or not an ordinary finite order linear recurrence with constant, rational coefficients ever generates zero. more >>> TR97-056 | 1st December 1997 Oded Goldreich #### Combinatorial Property Testing (a survey). Comments: 1 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 >>> TR97-057 | 3rd November 1997 Petr Savicky #### Complexity and Probability of some Boolean Formulas 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 >>> TR97-058 | 2nd December 1997 Oded Goldreich #### Notes on Levin's Theory of Average-Case Complexity. 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. more >>> 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 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 >>>

TR97-060 | 2nd December 1997
Manindra Agrawal, Thomas Thierauf

#### The Satisfiability Problem for Probabilistic Ordered Branching Programs

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

TR97-061 | 12th November 1997
Eli Biham, Dan Boneh, Omer Reingold

#### Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring

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

ISSN 1433-8092 | Imprint