Arrow Research search

Author name cluster

Larry J. Stockmeyer

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.

25 papers
2 author rows

Possible papers

25

FOCS Conference 1999 Conference Paper

Magic Functions

  • Cynthia Dwork
  • Moni Naor
  • Omer Reingold
  • Larry J. Stockmeyer

In this paper we show that three apparently unrelated problems are in fact very closely related. We sketch these problems at a high level. The selective decommitment problem first arose in a slightly different form, selective decryption, in the context of Byzantine agreement, no later than 1985. Instead of seeing encryptions of plaintexts the adversary is given commitments to the plaintexts. This problem is poorly understood even in strong-receiver commitments, which leak no information about the plaintext values information-theoretically. The second problem is in complexity theory: what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument (interactive proof in which the prover is polynomial-time bounded)? The Fiat-Shamir Methodology is cryptographic, and addresses a methodology suggested by Fiat and Shamir (1987) to construct a (non-interactive) signature scheme from any 3-round (not necessarily zero-knowledge) public-coin identification scheme.

Details

TCS Journal 1996 Journal Article

The complexity of PDL with interleaving

  • Alain J. Mayer
  • Larry J. Stockmeyer

To provide a logic for reasoning about concurrently executing programs, Abrahamson has defined an extension of propositional dynamic logic (PDL) by allowing interleaving as an operator for combining programs, in addition to the regular PDL operators union, concatenation, and star. We show that the satisfiability problem for interleaving PDL is complete for deterministic double-exponential time, and that this problem requires time double-exponential in cn log n for some positive constant c. Moreover, this lower bound holds even when restricted to formulas where each program appearing in the formula has the form a1¦a2¦ … ¦ak where ¦ denotes the interleaving operator and where a 1, …, a k are regular programs, i. e. , programs built from atomic programs using only the regular operators. Another consequence of the method used to prove this result is that the equivalence problem for regular expressions with interleaving requires space 2 cn log n and that this lower bound holds even to decide whether (E1¦E2¦ … ¦Ek) ∪ F ≡ ∑∗ where E 1, …, E k, F are ordinary regular expressions; this improves a previous result of the authors. Moreover, the same lower bound holds for the containment problem for expressions of the form E1¦E2¦ … ¦Ek.

Details DOI

FOCS Conference 1992 Conference Paper

Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)

  • Noga Alon
  • Gil Kalai
  • Moty Ricklin
  • Larry J. Stockmeyer

The authors prove a lower bound of Omega (log n/log log n) on the competitive ratio of any (deterministic or randomised) distributed algorithm for solving the mobile user problem on certain networks of n processors. The lower bound holds for various networks, including the hypercube, any network with sufficiently large girth, and any highly expanding graph. A similar Omega (log n/log log n) lower bound is proved for the competitive ratio of the maximum job delay of any distributed algorithm for solving a distributed scheduling problem on any of these networks. The proofs combine combinatorial techniques with tools from linear algebra and harmonic analysis and apply, in particular, a generalization of the vertex isoperimetric problem on the hypercube, which may be of independent interest. >

Details

FOCS Conference 1989 Conference Paper

On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract)

  • Cynthia Dwork
  • Larry J. Stockmeyer

The recognition power of two-way probabilistic finite-state automata (2PFAs) is studied. It is shown that any 2PFA recognizing a nonregular language must use exponential expected time infinitely often. The power of interactive proof systems (IPSs) where the verifier is a 2PFA is also investigated. It is shown that (1) IPSs in which the verifier uses private randomization are strictly more powerful than IPSs in which the random choices of the verifier are made public to the prover. (2) IPSs in which the verifier uses public randomization are strictly more powerful than 2PFAs alone, that is, without a prover; (3) every language accepted by some deterministic Turing machine in exponential time can be accepted by some IPS. Other results concern IPSs with 2PFA verifiers that run in polynomial expected time. >

Details

FOCS Conference 1986 Conference Paper

Flipping Persuasively in Constant Expected Time (Preliminary Version)

  • Cynthia Dwork
  • David B. Shmoys
  • Larry J. Stockmeyer

We present a distributed protocol for achieving a distributed coin in the presence of an extremely powerful adversary in constant time. The protocol can tolerate up to n/log n malicious processor failures where n is the number of processors in the system. The protocol needs only a fixed constant number of rounds of message exchange; no preprocessing is required. As a corollary we obtain an (n/log n)-resilient probabilistic protocol for Byzantine agreement running in constant expected time. Combining this with a generalization of a technique of Bracha, we obtain a probabilistic Byzantine agreement protocol tolerant of almost n/3 failures with O(log log n) expected running time.

Details

FOCS Conference 1983 Conference Paper

On the Minimal Synchronism Needed for Distributed Consensus

  • Danny Dolev
  • Cynthia Dwork
  • Larry J. Stockmeyer

Reaching agreement is a primitive of distributed computing. While this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: a system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer, Lynch and Paterson [FLP] have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper we extend their work, identifying several critical system parameters, including various synchronicity conditions, and examine how varying these affects the number of faults which can be tolerated. Our proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.

Details

FOCS Conference 1982 Conference Paper

A Complexity Theory for Unbounded Fan-In Parallelism

  • Ashok K. Chandra
  • Larry J. Stockmeyer
  • Uzi Vishkin

A complexity theory for unbounded fan-in parallelism is developed where the complexity measure is the simultaneous measure (number of processors, parallel time). Two models of unbounded fan-in parallelism are (1) parallel random access machines that allow simultaneous reading from or writing to the same common memory location, and (2) circuits containing AND's, OR's and NOT's with no bound placed on the fan-in of gates. It is shown that these models can simulate one another with the number of processors preserved to within a polynomial and parallel time preserved to within a constant factor. Reducibilities that preserve the measure in this sense are defined and several reducibilities and equivalences among problems are given. New upper bounds on the (unbounded fan-in) circuit complexity of symmetric Boolean functions are proved.

Details

TCS Journal 1980 Journal Article

Uniform data encodings

  • Arnold L. Rosenberg
  • Larry J. Stockmeyer
  • Lawrence Snyder

Given two finite, directed, edge-labeled graphs, G (the guest) and H (the host) an encoding of G into H is an injection of guest-graph edges into host-graph paths that induces an injection of G vertices into H vertices. An encoding is uniform if like-labeled edges map to like-labeled paths. Encodings and uniform encodings are motivated by data structure representation issues. Although uniform encodings are economically expressed, three types of analysis indicate diseconomies introduced by the uniformity condition. First, space usage (i. e. , the size of the host as a function of the size of the guest) can be exponential for ‘natural’ encodings such as uniform encodings of arrays into trees. By contrast, strongly connected hosts of size equal to the guests are adequate for nonuniform encodings. Secondly, the edge dilation under uniform encodings can be nonpolynomial in the size of the guest. By contrast, the same graphs can be nonuniformly encoded with edges mapping to paths of unit length. Thirdly, finding uniform encodings, even when the guest is a line, is PSPACE-complete. By contrast, there is a linear time algorithm for nonuniform encoding of lines in graphs. Additional upper and lower bounds amplify the limitations of uniform data encodings.

Details DOI

FOCS Conference 1976 Conference Paper

Alternation

  • Ashok K. Chandra
  • Larry J. Stockmeyer

We define alternating Turing Machines which are like nondeterministic Turing Machines, except that existential and universal quantifiers alternate. Alternation links up time and space complexities rather well, in that alternating polynomial time equals deterministic polynomial space, and alternating linear space equals deterministic exponential time. Such considerations lead to a two-person game complete in polynomial time, and other games complete in exponential time. We also find that computability on a parallel processing machine is a rather rugged notion, and present two parallel processing models that are polynomially equivalent in their running times. We also show that while n-state alternating finite automata accept only regular sets that can be accepted by 22n-O(logn) state deterministic automata, alternating pushdown automata accept all languages accepted by Turing machines in deterministic exponential time.

Details

TCS Journal 1976 Journal Article

The polynomial-time hierarchy

  • Larry J. Stockmeyer

The polynomial-time hierarchy is that subrecursive analog of the Kleene arithmetical hierarchy in which deterministic (nondeterministic) polynomial time plays the role of recursive (recursively enumerable) time. Known properties of the polynomial-time hierarchy are summarized. A word problem which is complete in the second stage of the hierarchy is exhibited. In the analogy between the polynomial-time hierarchy and the arithmetical hierarchy, the first order theory of equality plays the role of elementary arithmetic (as the ω-jump of the hierarchy). The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established.

Details DOI

STOC Conference 1975 Conference Paper

Hashing Schemes for Extendible Arrays (Extended Arrays)

  • Arnold L. Rosenberg
  • Larry J. Stockmeyer

The use of hashing schemes for storing extendible arrays is investigated. It is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely, hashing schemes that utilize storage too conservatively are inevitably poor in expected access time. If requirements on the utilization of storage are relaxed slightly, then one can find rather efficient extendible hashing schemes. Specifically, for any dimensionality of arrays, one can find extendible hashing schemes which at once utilize storage well [fewer than 2p storage locations need be set aside for storing arrays having p or fewer positions] and enjoy good access characteristics [expected access time is 0(1), and worst-case access time is 0(log log p) for p- or fewer-position arrays]. Moreover, at the cost of only an additive increase in access time, storage demands can be decreased to (l+ε)p locations for arbitrary ε>0. In fact, if one will abide a more drastic degradation of access efficiency, one can lower storage demands to p+o(p) locations.

Details

STOC Conference 1974 Conference Paper

A Characterization of the Power of Vector Machines

  • Vaughan R. Pratt
  • Michael O. Rabin
  • Larry J. Stockmeyer

Random access machines (RAMs) are usually defined to have registers that hold integers. While this captures in part the structure of a commercial computer, it overlooks an implementation-dependent feature of most binary oriented machines, namely their ability to operate bit by bit on the bit vectors used to represent integers. Typical operations are bit-wise Boolean operations ( and, or, not , etc.) and shifts by an amount specified in some register. These operations are ideal for certain problems, such as dealing with sets represented as bit vectors, some parsing algorithms [4], propositional calculus theorem proving, and analysis of sorting networks. A RAM so implemented we shall call a vector machine .

Details

STOC Conference 1974 Conference Paper

Some Simplified NP-Complete Problems

  • M. R. Garey
  • David S. Johnson 0001
  • Larry J. Stockmeyer

It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. First we show the completeness of SIMPLE MAX CUT (MAX CUT with edge weights restricted to value 1), and, as a corollary, the completeness of the OPTIMAL LINEAR ARRANGEMENT problem. We then show that even if the domains of the NODE COVER and DIRECTED HAMILTONIAN PATH problems are restricted to planar graphs, the two problems remain NP-complete, and that these and other graph problems remain NP-complete even when their domains are restricted to graphs with low node degrees. For GRAPH 3-COLORABILITY, NODE COVER, and UNDIRECTED HAMILTONIAN CIRCUIT, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP-complete.

Details

STOC Conference 1973 Conference Paper

Fast On-Line Integer Multiplication

  • Michael J. Fischer
  • Larry J. Stockmeyer

A Turing machine multiplies on-line if it receives its inputs low order digits first and it produces the k-th output digit before reading in the (k+1)-st inputs. We present a general method for converting any off-line multiplication algorithm which forms the product of two n-bit binary numbers in time F(n) into an on-line method, and the new algorithm requires time only 0(F(n) log n). Applying this technique to the fast multiplication algorithm of Schönhage and Strassen gives an upper bound of 0(n (log n) 2 log log n) for on-line multiplication of integers. Other applications are to the on-line problems of products of polynomials over a finite ring, recognition of palindromes, and multiplication by a constant.

Details

STOC Conference 1973 Conference Paper

Word Problems Requiring Exponential Time: Preliminary Report

  • Larry J. Stockmeyer
  • Albert R. Meyer

The equivalence problem for Kleene's regular expressions has several effective solutions, all of which are computationally inefficient. In [1], we showed that this inefficiency is an inherent property of the problem by showing that the problem of membership in any arbitrary context-sensitive language was easily reducible to the equivalence problem for regular expressions. We also showed that with a squaring abbreviation ( writing (E) 2 for E×E) the equivalence problem for expressions required computing space exponential in the size of the expressions. In this paper we consider a number of similar decidable word problems from automata theory and logic whose inherent computational complexity can be precisely characterized in terms of time or space requirements on deterministic or nondeterministic Turing machines. The definitions of the word problems and a table summarizing their complexity appears in the next section. More detailed comments and an outline of some of the proofs follows in the remaining sections. Complete proofs will appear in the forthcoming papers [9, 10, 13]. In the final section we describe some open problems.

Details
v2026.09.13