Search For:

Displaying 1-42 out of 42 total
Alternating pushdown automata
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer
Issue Date:October 1978
pp. 92-106
No summary available.
 
Polynomials That Sign Represent Parity and Descartes Rule of Signs
Found in: Computational Complexity, Annual IEEE Conference on
By Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
Issue Date:June 2004
pp. 223-235
<p>We study the sparsity of real polynomials that sign represent parity on n variables, each of which takes values from some finite subset A of integers. While the degree of such polynomials has been well studied [15, 1], relatively little is known a...
 
Random walks, universal traversal sequences, and the complexity of maze problems
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, Charles Rackoff
Issue Date:October 1979
pp. 218-223
No summary available.
 
A System Architecture to Support a Verifiably Secure Multilevel Security System
Found in: Security and Privacy, IEEE Symposium on
By George I. Davida, Richard A. DeMillo, Richard J. Lipton
Issue Date:April 1980
pp. 137
Technology that allows significant sharing of computer resources carries with it an increased responsibility to protect these resources from un-authorized, malicioua, irresponsible, or unintended use or disclosure. The years have seen a progression of incr...
 
Protecting Shared Cryptographic Keys
Found in: Security and Privacy, IEEE Symposium on
By George I. Davida, Richard A. DeMillo, Richard J. Lipton
Issue Date:April 1980
pp. 0100
In this paper, we present a scheme for distributing a key to n users in such a way as to require at least k of them (k < n) to be present to construct the original key. The scheme has the property that up to k - 1 defections can be tolerated. It can be ...
 
The design of a prototype mutation system for program testing
Found in: Managing Requirements Knowledge, International Workshop on
By Timothy A. Budd, Richard J. Lipton, Richard DeMillo, Frederick Sayward
Issue Date:June 1978
pp. 623
No summary available.
   
Applications of a planar separator theorem
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Richard J. Lipton, Robert Endre Tarjan
Issue Date:October 1977
pp. 162-170
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 pla...
 
On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas
Found in: Computational Complexity, Annual IEEE Conference on
By Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi
Issue Date:June 2005
pp. 112-119
<p>We study the following question: What is the smallest t such that every symmetric boolean function on k variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t?</p> <p...
 
Census functions: An approach to VLSI upper bounds
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Richard J. Lipton, Jacobo Valdes
Issue Date:October 1981
pp. 13-22
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 descri...
 
Representative skylines using threshold-based preference distributions
Found in: Data Engineering, International Conference on
By Atish Das Sarma,Ashwin Lall,Danupon Nanongkai,Richard J. Lipton,Jim Xu
Issue Date:April 2011
pp. 387-398
The study of skylines and their variants has received considerable attention in recent years. Skylines are essentially sets of most interesting (undominated) tuples in a database. However, since the skyline is often very large, much research effort has bee...
 
Model theoretic aspects of computational complexity
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Richard J. Lipton
Issue Date:October 1978
pp. 193-200
No summary available.
 
Amplifying Circuit Lower Bounds against Polynomial Time with Applications
Found in: 2012 IEEE Conference on Computational Complexity (CCC)
By Richard J. Lipton,Ryan Williams
Issue Date:June 2012
pp. 1-9
We give a self-reduction for the Circuit Evaluation problem, and prove the following consequences. \begin{itemize} \item {\bf Amplifying Size-Depth Lower Bounds.} If $\Circ Eval \in \SIZEDEPTH[n^k, n^{1-\delta}]$ for some $k$ and $\delta$, then for every $...
 
Polynomials with 0-1 coefficients that are hard to evaluate
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Richard J. Lipton
Issue Date:October 1975
pp. 6-10
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.
 
A necessary and sufficient condition for the existence of hoare logics
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Richard J. Lipton
Issue Date:October 1977
pp. 1-6
No summary available.
 
On the Complexity of SAT
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Richard J. Lipton, Anastasios Viglas
Issue Date:October 1999
pp. 459
In this work we show that non-deterministic time NTIME(n) is not contained in deterministic time \math and poly-logarithmic space, for any \math. This implies that (infinitely often) satisfiability cannot be solved in time \math and poly-logarithmic space....
 
Might Turing Have Won a Turing Award?
Found in: Computer
By Richard J. Lipton
Issue Date:June 2012
pp. 96-97
A provocative tale highlights Alan Turing's special ability to provide clarity to complex computing issues.
 
Symmetric Polynomials over \mathbb{Z}_m and Simultaneous Communication Protocols
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
Issue Date:October 2003
pp. 450
<p>We study the problem of representing symmetric Boolean functions as symmetric polynomials over \mathbb{Z}_m. We show an equivalence between such representations and simultaneous communication protocols. Computing a function f on 0 - 1 inputs with ...
 
On the Complexity of Intersecting Finite State Automata
Found in: Computational Complexity, Annual IEEE Conference on
By George Karakostas, Anastasios Viglas, Richard J. Lipton
Issue Date:July 2000
pp. 229
We consider the problem of testing whether the intersection of a collection of k automata is empty. The straightforward algorithm for solving this problem runs in time s k where s is the size of the automata. In this work, we prove that the assumption that...
 
Clock Buffer Placement Algorithm for Wire-Delay-Dominated Timing Model
Found in: Great Lakes Symposium on VLSI
By Masato Edahiro, Richard J. Lipton
Issue Date:March 1996
pp. 0143
A clock buffer placement algorithm is proposed for future technologies in which wire delay dominates signal delay. In such technologies, buffers need to be placed so as to minimize the maximum wire delay. We formulate the problem into a non-linear programm...
 
On the Complexity of a Set-Union Problem
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Richard J. Lipton, Paul J. Martino, Andy Neitzke
Issue Date:October 1997
pp. 110
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 ...
 
Social processes and proofs of theorems and programs
Found in: Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '77)
By Alan J. Perlis, Richard A. DeMillo, Richard J. Lipton
Issue Date:January 1977
pp. 206-214
Structuring can be defined independently of what is being structured, and can be applied profitably to more than one domain. Using one mechanism to structure both values and assignments, we obtain equivalents for a variety of data and control structures. S...
     
Some connections between nonuniform and uniform complexity classes
Found in: Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80)
By Richard J. Lipton, Richard M. Karp
Issue Date:April 1980
pp. 302-309
It is well known that every set in P has small circuits [13]. Adleman [1] has recently proved the stronger result that every set accepted in polynomial time by a randomized Turing machine has small circuits. Both these results are typical of the known rela...
     
The consistency of “P &equil; NP” and related problems with fragments of number theory
Found in: Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80)
By Richard A. DeMillo, Richard J. Lipton
Issue Date:April 1980
pp. 45-57
The main results of this paper demonstrate the consistency of “P &equil; NP” and a variant of “NP @@@@ coNP” with certain natural fragments of number theory to be defined precisely in the sequel.@@@@ Consistency results represent an...
     
Theoretical and empirical studies on using program mutation to test the functional correctness of programs
Found in: Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '80)
By Frederick G. Sayward, Richard A. DeMillo, Richard J. Lipton, Timothy A. Budd
Issue Date:January 1980
pp. 220-233
In testing for program correctness, the standard approaches[11,13,21,22,23,24,34] have centered on finding data D, a finitesubset of all possible inputs to program P, such that1) if for all x in D, P(x) = f(x), then P* = fwhere f is a partial recursive fun...
     
Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem
Found in: Journal of the ACM (JACM)
By Richard A. DeMillo, Richard J. Lipton, Stanley C. Eisenstat
Issue Date:January 1980
pp. 123-127
A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are of nondete...
     
Some connections between mathematical logic and complexity theory
Found in: Proceedings of the eleventh annual ACM symposium on Theory of computing (STOC '79)
By Richard A. DeMillo, Richard J. Lipton
Issue Date:April 1979
pp. 153-159
However difficult the fundamental problems of theoretical computer science may seem, there is very little to suggest that they are anything more than knotty combinatorial problems. So, when we look for reasons for our inability to resolve P &equil; NP and ...
     
Evaluation of polynomials with super-preconditioning
Found in: Proceedings of the eighth annual ACM symposium on Theory of computing (STOC '76)
By Larry J. Stockmeyer, Richard J. Lipton
Issue Date:May 1976
pp. 174-180
In an effort to understand the complexity of arithmetic computation, a number of researchers [1,5,7,8,9,11] have studied the following question: Given a polynomial f(x), Find a minimal cost straightline program that computes f(x).@@@@ In this paper this qu...
     
Playing large games using simple strategies
Found in: Proceedings of the conference on Electronic commerce (EC '03)
By Aranyak Mehta, Evangelos Markakis, Richard J. Lipton
Issue Date:June 2003
pp. 36-41
We prove the existence of ε-Nash equilibrium strategies with support logarithmic in the number of pure strategies. We also show that the payoffs to all players in any (exact) Nash equilibrium can be ε-approximated by the payoffs to the players in...
     
On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms
Found in: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM '02)
By Jun Xu, Richard J. Lipton
Issue Date:August 2002
pp. 279-292
In this work, we clarify, extend and solve an open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a s...
     
Simple strategies for large zero-sum games with applications to complexity theory
Found in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (STOC '94)
By Neal E. Young, Richard J. Lipton
Issue Date:May 1994
pp. 734-740
We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP-hard discrete optimization problem. Without any constraint v...
     
Amplification of weak learning under the uniform distribution
Found in: Proceedings of the sixth annual conference on Computational learning theory (COLT '93)
By Dan Boneh, Richard J. Lipton
Issue Date:July 1993
pp. 347-351
The algorithm for pac learning k-DNF or k-CNF in the presence of malicious attribute noise in polynomial time claimed by Sloan [Slo88] does not work. It is currently open whether such an algorithm exists.
     
Query size estimation by adaptive sampling (extended abstract)
Found in: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (PODS '90)
By Jeffrey F. Naughton, Richard J. Lipton
Issue Date:April 1990
pp. 40-46
We present an adaptive, random sampling algorithm for estimating the size of general queries. The algorithm can be used for any query Q over a database D such that 1) for some n, the answer to Q can be partitioned into n disjoint subsets Q1, Q2, …, Q...
     
Multi-party protocols
Found in: Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC '83)
By Ashok K. Chandra, Merrick L. Furst, Richard J. Lipton
Issue Date:December 1983
pp. 94-99
Many different types of inter-process communication have been examined from a complexity point of view [SP, Y]. We study a new model, in which a collection of processes P0, ..., Pk−1 that share information about a set of integers {a0, ...,ak−...
     
Programming aspects of VLSI: (preliminary version)
Found in: Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '82)
By Jacobo Valdes, Richard J. Lipton, Robert Sedgewick
Issue Date:January 1982
pp. 57-65
Two components of a VLSI design environment being built at Princeton are described. The general theme of this effort is to make the design of VLSI circuits as similar to programming as possible. A conscious attempt is being made to apply experience in the ...
     
Lower bounds for VLSI
Found in: Proceedings of the thirteenth annual ACM symposium on Theory of computing (STOC '81)
By Richard J. Lipton, Robert Sedgewick
Issue Date:May 1981
pp. 300-307
Increased use of Very Large Scale Integration (VLSI) for the fabrication of digital circuits has led to increased interest in complexity results on the inherent VLSI difficulty of various problems. Lower bounds have been obtained for problems such as integ...
     
The orbit problem is decidable
Found in: Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80)
By Ravindran Kannan, Richard J. Lipton
Issue Date:April 1980
pp. 252-261
The “accessibility problem” for linear sequential machines (Harrison [7]) is the problem of deciding whether there is an input x that sends such a machine from a given state q1 to a given state q2. Harrison [7] showed that this problem is reduc...
     
External Hashing Schemes for Collections of Data Structures
Found in: Journal of the ACM (JACM)
By Andrew C. Yao, Arnold L. Rosenberg, Richard J. Lipton
Issue Date:January 1980
pp. 81-95
A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are of nondete...
     
Secure databases: protection against user influence
Found in: ACM Transactions on Database Systems (TODS)
By Anita K. Jones, David Dobkin, Richard J. Lipton
Issue Date:March 1979
pp. 97-106
Users may be able to compromise databases by asking a series of questions and then inferring new information from the answers. The complexity of protecting a database against this technique is discussed here.
     
Word Problems Solvable in Logspace
Found in: Journal of the ACM (JACM)
By Richard J. Lipton, Yechezkel Zalcstein
Issue Date:July 1977
pp. 522-526
A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are of nondete...
     
The enforcement of security policies for computation
Found in: Proceedings of the fifth symposium on Operating systems principles (SOSP '75)
By Anita K. Jones, Richard J. Lipton
Issue Date:November 1975
pp. 197-206
Security policies define who may use what information in a computer system. Protection mechanisms are built into a system to enforce security policies. In most systems, however, it is quite unclear what policies a mechanism can or does enforce. This paper ...
     
Complexity measures and hierarchies for the evaluation of integers, polynomials, and n-linear forms
Found in: Proceedings of seventh annual ACM symposium on Theory of computing (STOC '75)
By David Dobkin, Richard J. Lipton
Issue Date:May 1975
pp. 1-5
The difficulty of evaluating integers and polynomials has been studied in various frameworks ranging from the addition-chain approach [5] to integer evaluation to recent efforts aimed at generating polynomials that are hard to evaluate [2,8,10]. Here we co...
     
Reduction: a new method of proving properties of systems of processes
Found in: Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '75)
By Richard J. Lipton
Issue Date:January 1975
pp. 78-86
When proving that a system of processes has a given property it is often convenient to assume that a routine is uninterruptible, i.e. that the routine cannot be interleaved with the rest of the system. Here sufficient conditions are obtained to show that t...
     
 1