Arrow Research search

Author name cluster

Richard J. Lipton

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

42 papers
2 author rows

Possible papers

42

MFCS Conference 2011 Conference Paper

Symmetric Functions Capture General Functions

  • Richard J. Lipton
  • Kenneth W. Regan
  • Atri Rudra

Abstract We show that the set of all functions is equivalent to the set of all symmetric functions (possibly over a larger domain) up to deterministic time complexity. In particular, for any function f, there is an equivalent symmetric function f sym such that f can be computed from f sym and vice-versa (modulo an extra deterministic linear time computation). For f over finite fields, f sym is (necessarily) over an extension field. This reduction is optimal in size of the extension field. For polynomial functions, the degree of f sym is not optimal. We present another reduction that has optimal degree “blowup” but is worse in the other parameters.

Details

MFCS Conference 2010 Conference Paper

Improved Simulation of Nondeterministic Turing Machines

  • Subrahmanyam Kalyanasundaram
  • Richard J. Lipton
  • Kenneth W. Regan
  • Farbod Shokrieh

Abstract The standard simulation of a nondeterministic Turing machine (NTM) by a deterministic one essentially searches a large bounded-degree graph whose size is exponential in the running time of the NTM. The graph is the natural one defined by the configurations of the NTM. All methods in the literature have required time linear in the size S of this graph. This paper presents a new simulation method that runs in time \(\tilde{O}(\sqrt{S})\). The search savings exploit the one-dimensional nature of Turing machine tapes. In addition, we remove most of the time-dependence on nondeterministic choice of states and tape head movements.

Details

FOCS Conference 2003 Conference Paper

Symmetric Polynomials over Z m and Simultaneous Communication Protocol

  • Nayantara Bhatnagar
  • Parikshit Gopalan
  • Richard J. Lipton

We study the problem of representing symmetric Boolean functions as symmetric polynomials over /spl Zopf//sub m/. We show an equivalence between such representations and simultaneous communication protocols. Computing a function f on 0 - 1 inputs with a polynomial of degree d modulo pq is equivalent to a two player simultaneous protocol for computing f where one player is given the first [log/sub p/d] digits of the weight in base q. This reduces the problem of proving bounds on the degree of symmetric polynomials to proving bounds on simultaneous communication protocols. We use this equivalence to show lower bounds of /spl Omega/(n) on symmetric polynomials weakly representing classes of Mod/sub r/ and Threshold functions. We show there exist symmetric polynomials over /spl Zopf//sub m/ of degree o(n) strongly representing Threshold c for c constant, using the fact that the number of solutions of certain exponential Diophantine equations are finite. Conversely, the fact that the degree is o(n) implies that some classes of Diophantine equations can have only finitely many solutions. Our results give simplifications of many previously known results and show that polynomial representations are intimately related to certain questions in number theory.

Details

FOCS Conference 1999 Conference Paper

On the Complexity of SAT

  • Richard J. Lipton
  • Anastasios Viglas

We show that non-deterministic time NTIME(n) is not contained in deterministic time n/sup 2-/spl epsiv// and polylogarithmic space, for any /spl epsiv/>0. This implies that (infinitely often), satisfiability cannot be solved in time O(n/sup 2-/spl epsiv//) and polylogarithmic space. A similar result is presented for uniform circuits; a log-space uniform circuit of polylogarithmic width computing satisfiability requires infinitely often almost quadratic size.

Details

FOCS Conference 1997 Conference Paper

On the Complexity of a Set-Union Problem

  • Richard J. Lipton
  • Paul J. Martino
  • Andy Neitzke

We consider a simple data structure supporting the following operations: (i) create a new singleton set; (ii) create a new set which is the union of two pre-existing sets; (iii) determine whether a given element is in a particular set. We prove both lower and upper bounds for an implementation of such a data structure. In a restricted model we show that no deterministic implementation can be better than the "trivial" one that takes O(n/sup 2/) time. In a parallel model where the operations come in at most O(1g n) stages we exhibit a sub-quadratic implementation.

Details

FOCS Conference 1994 Conference Paper

The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices

  • Jin-Yi Cai
  • Richard J. Lipton
  • Yechezkel Zalcstein

We present a deterministic polynomial-time algorithm for the ABC problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial time algorithm, for the (easier) membership problem, for 2-generated abelian linear groups. Furthermore, we provide a polynomial-sized encoding for the set of all solutions. >

Details

FOCS Conference 1992 Conference Paper

Reconstructing Algebraic Functions from Mixed Data

  • Sigal Ar
  • Richard J. Lipton
  • Ronitt Rubinfeld
  • Madhu Sudan 0001

The authors consider the task of reconstructing algebraic functions given by black boxes. Unlike traditional settings, they are interested in black boxes which represent several algebraic functions-f/sub 1/, .. ., f/sub k/, where at each input x, the box arbitarrily chooses a subset of f/sub 1/(x), .. ., f/sub k/(x) to output. They show how to reconstruct the functions f/sub 1/, .. ., f/sub k/ from the black box. This allows them to group the same points into sets, such that for each set, all outputs to points in the set are from the same algebraic function. The methods are robust in the presence of errors in the black box. The model and techniques can be applied in the areas of computer vision, machine learning, curve fitting and polynomial approximation, self-correcting programs and bivariate polynomial factorization. >

Details

FOCS Conference 1989 Conference Paper

On the Complexity of Space Bounded Interactive Proofs (Extended Abstract)

  • Anne Condon
  • Richard J. Lipton

Two results on interactive proof systems with two-way probabilistic finite-state verifiers are proved. The first is a lower bound on the power of such proof systems if they are not required to halt with high probability on rejected inputs: it is shown that they can accept any recursively enumerable language. The second is an upper bound on the power of interactive proof systems that halt with high probability on all inputs. The proof method for the lower bound also shows that the emptiness problem for one-way probabilistic finite-state machines is undecidable. In the proof of the upper bound some results of independent interest on the rate of convergence of time-varying Markov chains to their halting states are obtained. >

Details

FOCS Conference 1989 Conference Paper

Subquadratic Simulations of Circuits by Branching Programs

  • Jin-Yi Cai
  • Richard J. Lipton

Boolean circuits and their simulations by bounded-width branching programs are considered. It is shown that every NC/sup 1/ circuit of size s can be simulated by a constant-width branching program of length s/sup 1. 811. .. /. Some related group-theoretic results are presented. >

Details

FOCS Conference 1981 Conference Paper

Census Functions: an Approach to VLSI Upper Bounds (Preliminary Version)

  • Richard J. Lipton
  • Jacobo Valdes

A model of VLSI computation suitable for the description of algorithms at a high level is introduced. The model is basically a language to express parallel computations which can be efficiently implemented by a VLSI circuit. This language is used to describe area-time efficient algorithms for a few well known graph problems. The exact complexity of these algorithms and their relevance to recent work on the inherent limitations of VLSI computations are also presented.

Details

FOCS Conference 1977 Conference Paper

Application of a Planar Separator Theorem

  • Richard J. Lipton
  • Robert Endre Tarjan

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(√n) vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results.

Details

FOCS Conference 1976 Conference Paper

A Linear Time Algorithm for Deciding Security

  • Anita K. Jones
  • Richard J. Lipton
  • Lawrence Snyder 0001

The Folklore is replete with stories of "secure" protection systems being compromised in a matter of hours. This is quite astounding since one is not likely to claim that a system is secure without some sort of proof to support the claim. In practice, proof is not provided and one reason for this is clear: although the protection primitives are apparently quite simple, they may potentially interact in extremely complex ways. Vague and informal arguments, therefore, often overlook subtleties that an adversary can exploit. Precision is not merely desirable for protection systems, it is mandatory.

Details

FOCS Conference 1975 Conference Paper

Polynomials with 0-1 Coefficients that Are Hard to Evaluate

  • Richard J. Lipton

We show the existence of polynomials with 0-1 coefficients that are hard to evaluate even when arbitrary preconditioning is allowed. Further we show that there are power series with 0-1 coefficients such that their initial segments are hard to evaluate.

Details

FOCS Conference 1975 Conference Paper

Synchronization and Computing Capabilities of Linear Asynchronous Structures

  • Richard J. Lipton
  • Raymond E. Miller
  • Lawrence Snyder 0001

A model is defined in which questions concerning delay bounded asynchronous parallel systems may be investigated. Persistence and determinacy are introduced for this model. These two conditions are shown to be sufficient to guarantee that a synchronous execution policy can be relaxed to an asynchronous execution policy with no change to the result of the computation. In addition, the asynchronous execution time is only (D+1) times the synchronous execution time, where D is the delay bound. A wide class of recognition problems is identified which can be solved by linear asynchronous structures. Also, it is shown that synchronization problems, similar to the "firing squad synchronization problem, " cannot be solved by delay bounded asynchronous systems.

Details