It is a longstanding open problem whether there is an algorithm to decide the Skolem Problem for linear recurrence sequences (LRS) over the integers, namely whether a given such sequence has a zero term (i.e., whether un = 0 for some n). A major breakthrough in the early 1980s established decidability for LRS of order 4 or less, i.e., for LRS in which every new term depends linearly on the previous four (or fewer) terms. The Skolem Problem for LRS of order 5 or more, in particular, remains a major open challenge to this day.

The Skolem Problem asks, given a linear recurrence sequence (un), whether there exists n ∈ N such that un = 0. In this paper we consider the following specialisation of the problem: given in addition c ∈ N, determine whether there exists n ∈ N of the form n = lpk, with k, l ≤ c and p any prime number, such that un = 0.

Protecting software from malware injection is one of the biggest challenges of modern computer science. Despite intensive efforts by the scientific and engineering community, the number of successful attacks continues to increase. This work sets first footsteps towards a provably secure investigation of malware detection. We provide a formal model and cryptographic security definitions of attestation for systems with dynamic memory, and suggest novel provably secure attestation schemes. The key idea underlying our schemes is to use the very insertion of the malware itself to allow for the systems to detect it. This is, in our opinion, close in spirit to the quantum Observer Effect. The attackers, no matter how clever, no matter when they insert their malware, change the state of the system they are attacking. This fundamental idea can be a game changer. And our system does not rely on heuristics; instead, our scheme enjoys the unique property that it is proved secure in a formal and precise mathematical sense and with minimal and realistic CPU modification achieves strong provable security guarantees. We envision such systems with a formal mathematical security treatment as a venue for new directions in software protection.

We give a self-reduction for the Circuit Evaluation problem (CircEval), and prove the following consequences. · Amplifying Size-Depth Lower Bounds. If CIRCEVAL ϵ SIZEDEPTH [nk, n1-δ] for some k and δ, then for every ε >; 0, there is a δ >; 0, there is a δ' >; 0 such that CIRCEVAL ϵ SIZEDEPTH [nk, n1-δ']. Moreover, the resulting circuits require only O(nε) bits of non-uniformity to construct. As a consequence, strong enough depth lower bounds for Circuit Evaluation imply a full separation of P and NC (even with a weak size lower bound). · Lower Bounds for Quantified Boolean Formulas. Let c,d >; 1 and e <; 1 satisfy c <; (1 - e + d)/d. Either the problem of recognizing valid quantified Boolean formulas (QBF) is not solvable in TIME[nc], or the Circuit Evaluation problem cannot be solved with circuits of nd size and ne depth. This implies unconditional polynomial-time uniform circuit lower bounds for solving QBF.

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 been devoted to identifying a smaller subset of (say k) “representative skyline” points. Several different definitions of representative skylines have been considered. Most of these formulations are intuitive in that they try to achieve some kind of clustering “spread” over the entire skyline, with k points. In this work, we take a more principled approach in defining the representative skyline objective. One of our main contributions is to formulate the problem of displaying k representative skyline points such that the probability that a random user would click on one of them is maximized. Two major research questions arise naturally from this formulation. First, how does one mathematically model the likelihood with which a user is interested in and will "click" on a certain tuple? Second, how does one negotiate the absence of the knowledge of an explicit set of target users; in particular what do we mean by "a random user"? To answer the first question, we model users based on a novel formulation of threshold preferences which we will motivate further in the paper. To answer the second question, we assume a probability distribution of users instead of a fixed set of users. While this makes the problem harder, it lends more mathematical structures that can be exploited as well, as one can now work with probabilities of thresholds and handle cumulative density functions. On the theoretical front, our objective is NP-hard. For the case of a finite set of users with known thresholds, we present a simple greedy algorithm that attains an approximation ratio of (1 - 1/e) of the optimal. For the case of user distributions, we show that a careful yet similar greedy algorithm achieves the same approximation ratio. Unfortunately, it turns out that this algorithm is rather involved and computationally expensive. So we present a threshold sampling based algorithm that is more computationally affordable and, for any fixed ∈ >; 0, has an approximation ratio of (1 - 1/e - ∈). We perform experiments on both real and synthetic data to show that our algorithm significantly outperforms previously proposed approaches.

Given a single program (i.e., bit string), one may assume that the program's behaviors can be determined by first identifying the native runtime architecture and then executing the program on that architecture. In this paper, we challenge the notion that programs run on a single architecture by developing techniques that automatically create a single program string that a) runs on different architectures, and b) potentially has different behaviors depending upon which architecture it runs on. At a high level, a primary security implication is that any program analysis done on a program must only be considered valid for the assumed architecture. Our techniques also introduce a new type of steganography that hides execution behaviors. In order to demonstrate our techniques, we implement a system for generating platform-independent programs for x86, ARM, and MIPS. We use our system to generate real platform-independent programs.

We propose the k -representative regret minimization query ( k -regret) as an operation to support multi-criteria decision making. Like top- k , the k -regret query assumes that users have some utility or scoring functions; however, it never asks the users to provide such functions. Like skyline, it filters out a set of interesting points from a potentially large database based on the users' criteria; however, it never overwhelms the users by outputting too many tuples. In particular, for any number k and any class of utility functions, the k -regret query outputs k tuples from the database and tries to minimize the maximum regret ratio . This captures how disappointed a user could be had she seen k representative tuples instead of the whole database. We focus on the class of linear utility functions, which is widely applicable. The first challenge of this approach is that it is not clear if the maximum regret ratio would be small, or even bounded. We answer this question affirmatively. Theoretically, we prove that the maximum regret ratio can be bounded and this bound is independent of the database size. Moreover, our extensive experiments on real and synthetic datasets suggest that in practice the maximum regret ratio is reasonably small. Additionally, algorithms developed in this paper are practical as they run in linear time in the size of the database and the experiments show that their running time is small when they run on top of the skyline operation which means that these algorithm could be integrated into current database systems.

Message Ferrying is a mobility assisted technique for working around the disconnectedness and sparsity of Mobile ad hoc networks. One of the importantquestions which arise in this context is to determine the routing of the ferry,so as to minimize the buffers used to store data at the nodes in thenetwork. We introduce a simple model to capture the ferry routingproblem. We characterize {\em stable} solutions of the system andprovide efficient approximation algorithms for the {\sc Min-Max Buffer Problem} for the case when the nodes are onhierarchically separated metric spaces.

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? We exclude the constant functions for which there is no such t and the parity functions for which t has to be k. Let τ(k) be the smallest such t. The main contribution of this paper is a proof of the following self similar nature of this question: If τ(l) ≤ s, then for any ɛ> 0 and � for k ≥ k0(l, ɛ), τ(k) ≤ k s+1 l+1 + ɛ Coupling this result with a computer based search which establishes τ(30) = 2, one obtains that for large enough k, τ(k) ≤ 3k/31. The motivation for our work is to understand the complexity of learning symmetric juntas. A k-junta is a boolean function of n variables that depends only on an unknown subset of k variables. If f is symmetric in the variables it depends on, it is called a symmetric k-junta. Our results imply an algorithm to learn the class of symmetric k-juntas, in the uniform PAC learning model, in time approximately n 3k 31. This improves on a result of Mossel, O’Donnell and Servedio in [11], who show that symmetric k-juntas can be ∗ Research supported by NSF grants CCR-0002299 and CCF-0431023.

We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive constant d such that no deterministic random-access Turing machine can solve satisfiability in time n c and space n d , where d approaches 1 when c does. On conondeterministic instead of deterministic machines, we prove the same for any constant c less than √2.Our lower bounds apply to nondeterministic linear time and almost all natural NP-complete problems known. In fact, they even apply to the class of languages that can be solved on a nondeterministic machine in linear time and space n 1/c .Our proofs follow the paradigm of indirect diagonalization. We also use that paradigm to prove time-space lower bounds for languages higher up in the polynomial-time hierarchy.

We clarify, extend, and solve a long-standing 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 scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is /spl Omega/(logn). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(n/sup a/) for 0<a<1. This implies that the delay-complexity tradeoff curve is flat in the "interval" [O(1),O(n)). We later conditionally extend both complexity results (for O(1) or O(n/sup a/) delay) to a much stronger computational model, the linear decision tree. Finally, we show that the same complexity lower bounds are conditionally applicable to guaranteeing tight end-to-end delay bounds, if the delay bounds are provided through the Latency Rate (LR) framework.

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 by M. Minsky and S. Papert (1968) and J. Aspnes (1994), relatively little is known about their sparsity. We study this problem using Descartes rule of signs, a classical result in algebra, relating the sparsity of a polynomial to its number of real roots. We show that sign representing parity over {0,1,..., m - 1}/sup n/ with the degree in each variable at most m - 1 requires sparsity at least m/sup n/. We show a bound of (m - l)/sup n/ for weak representations. We show that a tradeoff exists between sparsity and degree, by constructing a sign representation that has higher degree but lower sparsity. In some cases, the difference in sparsities is exponential. We show a lower bound of n(m - 2) + 1 on the sparsity of polynomials of any degree representing parity over {0, 1, ..., m -1 }/sup n/. We prove exact bounds on the sparsity of such polynomials for any two element subset A. We show that for depth-two and-or-not circuits with a threshold gate at the top, the minimum circuit size for a function f equals the minimum sparsity of a polynomial sign representing f over a certain basis. We use this to give a simple proof that such circuits need size (3/2)/sup n/ to compute parity, which improves on previous bounds by M. Goldmann (1997). We also show a tight lower bound of 2/sup n/ for the inner product function over {0,1}/sup n/ /spl times/ {0,1}/sup n/. The main technical tool used is Descartes rule of signs. Our bounds hold for various bases where Descartes sign rule is valid.

We study the problem of fairly allocating a set of indivisible goods to a set of people from an algorithmic perspective. fair division has been a central topic in the economic literature and several concepts of fairness have been suggested. The criterion that we focus on is envy-freeness. In our model, a monotone utility function is associated with every player specifying the value of each subset of the goods for the player. An allocation is envy-free if every player prefers her own share than the share of any other player. When the goods are divisible, envy-free allocations always exist. In the presence of indivisibilities, we show that there exist allocations in which the envy is bounded by the maximum marginal utility, and present a simple algorithm for computing such allocations. We then look at the optimization problem of finding an allocation with minimum possible envy. In the general case the problem is not solvable or approximable in polynomial time unless P = NP. We consider natural special cases (e.g.additive utilities) which are closely related to a class of job scheduling problems. Approximation algorithms as well as inapproximability results are obtained. Finally we investigate the problem of designing truthful mechanisms for producing allocations with bounded envy.

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.

Mandatory human participation (MHP) is a novel authentication scheme that asks the question "are you human?" (Instead of "who are you?"), and upon the correct answer to this question, can prove a principal to be a human being instead of a computer program. MHP helps solve old and new problems in computer security that existing security measures cannot address properly, including password (or PIN number) guessing attacks and application-level denial of service. A key component of this "are you human?" authentication process is a character morphing algorithm that transforms a character string into its graphical form in such a way that a human being won't have any problem recognizing the original string, while a computer program (e.g., an optical character recognition program), will not be able to decipher it or make a correct guess with nonnegligible probability. The basic idea of the MHP scheme is to ask an agent to recognize the string before its login attempts or transaction requests can be honored. Here a protocol is needed to send a puzzle to an agent, check if the answer supplied by the agent is correct, and most importantly make sure that the agent cannot cheat in the process. A number of system and security issues that relate to the protocol need to be addressed for the protocol to be secure, efficient, robust, and user-friendly. The MHP scheme contributes to the foundation of the computer security by faithfully implementing novel security semantics, "human," which existing cryptographic measures cannot express accurately. As many real-world security applications involve the interaction between a human and a computer, which naturally contains "human" as a part of its protocol semantics, we believe that the MHP scheme will find many new applications in the future.

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 some such logarithmic support ε-Nash equilibrium. These strategies are also uniform on a multiset of logarithmic size and therefore this leads to a quasi-polynomial algorithm for computing an ε-Nash equilibrium. To our knowledge this is the first subexponential algorithm for finding an ε-Nash equilibrium. Our results hold for any multiple-player game as long as the number of players is a constant (i.e., it is independent of the number of pure strategies). A similar argument also proves that for a fixed number of players m, the payoffs to all players in any m-tuple of mixed strategies can be ε-approximated by the payoffs in some m-tuple of constant support strategies.We also prove that if the payoff matrices of a two person game have low rank then the game has an exact Nash equilibrium with small support. This implies that if the payoff matrices can be well approximated by low rank matrices, the game has an ε-equilibrium with small support. It also implies that if the payoff matrices have constant rank we can compute an exact Nash equilibrium in polynomial time.

In this paper, we present the GAMMA system, which facilitates remote monitoring of deployed software using a new approach that exploits the opportunities presented by a software product being used by many users connected through a network. GAMMA splits monitoring tasks across different instances of the software, so that partial information can be collected from different users by means of light-weight instrumentation, and integrated to gather the overall monitoring information. This system enables software producers (1) to perform continuous, minimally intrusive analyses of their software's behavior, and (2) to use the information thus gathered to improve and evolve their software.

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 scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is Ω (log2 n) (widely believed as a "folklore theorem" but never proved). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(na) for 0‹a⋵1. This implies that the delay-complexity tradeoff curve is "flat" in the "interval" [O(1), O(n)). We later extend both complexity results (for O(1) or O(na) delay) to a much stronger computational model. Finally, we show that the same complexity lower bounds are conditionally applicable to guaranteeing tight end-to-end delay bounds. This is done by untangling the relationship between the GPS-relative delay bound and the end-to-end delay bound.

The deployment of several client-server applications over the Internet and emerging networks requires the establishment of the client's integrity. This is necessary for the protection of copyright of distributed material and, in general, for protection from loss of "sensitive" (secret) information. Clients are vulnerable to powerful man-in-the-middle attacks through viruses, which are undetectable by conventional anti-virus technology. We describe such powerful viruses and show their ability to lead to compromised clients, that cannot protect copyrighted or "sensitive " information. We introduce a methodology based on simple hardware devices, called "spies", which enables servers to establish client integrity, and leads to a successful defense against viruses that use man-in-the-middle attacks.

1 Introduction While computing power and memory size have been steadily increasing as predicted by Moore's Law, they are still dwarfed by the size of massive data sets resultant from a number of applications. Many problems arising from astrophysics, computational biology, telecommunications, and the Internet often have an amount of accompanying data in the terabyte range. The analysis of this data by classical algorithms is often prohibitively expensive. Thus new ideas are necessary to create algorithms to deal with these massive data sets.

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 /spl sigma//sup k/ where a is the size of the automata. In this work we prove that the assumption that there exists a better algorithm solving the FSA intersection emptiness problem implies that nondeterministic time is in subexponential deterministic time and also separates NL from P. Furthermore, under a (more general) non-uniform variant of the assumption mentioned above we can prove that NL/spl ne/NP.

We present a deterministic polynomial-time algorithm for the A B C 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.

We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an /spl epsiv/ fraction of the bits in a satisfying assignment to a 3-CNF formula easier than computing the whole assignment? For several important problems in NP we show that obtaining only a small fraction of the solution is as hard as finding the full solution. This can be interpreted in two ways: On the positive side, it is enough to look for an efficient algorithm that only recovers a small part of the solution, in order to completely solve any of these problems. On the negative side, any partial solution to these problems may be hard to find Some of our results can also be interpreted as robust proofs of membership.

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.

We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is given access to an unknown function f that is represented by a black box, or an oracle, which can be queried for the value of f at any input. Given a guarantee that this unknown function f is some nice algebraicfunction, say a polynomial in its input of degree bound d, the goal of the reconstruction problem is to explicitly determine the coefficients of the unknown polynomial. All work on polynomial interpolation, especially sparse ones, are or may be presented in such a setting. The work of Kaltofen and Trager [Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators, in Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science, 1988, pp. 296--305], for instance, highlights the utility of this setting, by performing numerous manipulations on polynomials presented as black boxes. The variant considered in this paper differs from the traditional setting in that our black boxes represent several algebraic functions f 1 ,...,f k , where at each input x, the box arbitrarily chooses a subset of f 1 (x),...,f k (x) to output and we do not know which subset it outputs. We show how to reconstruct the functions f 1 ,...,f k from the black box, provided the black box outputs according to these functions "often." This allows us to group the sample points into sets, such that for each set, all outputs to points in the set are from the same algebraic function. Our methods are robust in the presence of a small fraction of arbitrary errors in the black box. Our 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.

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.

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 programming, and solve it by an iteration method with a randomized technique. We applied our buffer placement algorithm with a zero-skew router to several benchmark data, and show that our algorithm achieves 30% less delay time than a H-tree based algorithm.

Ever since Adleman's seminal paper (1994) there has been a flood of ideas on how one could use DNA to compute. There have been many papers on using DNA to solve various computational problems. At the top-most level all these papers use DNA in the same way. Each strand of DNA encodes the state of a processor. Each processor operates independently: there is no communication from one processor to another. Processors each search their own part of a large space. The papers differ in the details of how they encode the state into the DNA. They all, however, perform independent searches. Our new result is that we can allow, for the first time, global memory. That is, we show that the individual DNA strands can communication with each other. This changes everything. The point is that DNA can do much more general parallel computations than previously realized. The class of computations that allow global memory are much more powerful than independent searches. For example, one of the main ways to search large spaces is the so called branch-and-bound method. In this method the search in one part of the space is pruned by values found in other parts of the space. Previously, it was not possible to even imagine how DNA computations could do this: now we know how. Our method is based on the same bio-technology operations that we have used previously. We use no new bio-operations. Thus, our addition of global memory to DNA computations has all the promise and difficulties that previous DNA computations had. The key is that we use nothing new: we just exploit the power of the existing methods in a new way.

Formal demonstration of equivalence or nonequivalence of different security models helps identify the fundamental constructs and principles in such models. In this paper, we demonstrate the nonequivalence of two monotonic access control models that differ only in the creation operation for new subj ects and/or objects; in particular, we show that single-parent creation is less expressive than multi-parent creation. The nature of the proof indicates that this result will apply to any monotonic access control model. The nonequivalence proof is carried out on an abstract access control model, following which the results are interpreted in standard formulations. In particular, we apply the results to demonstrate nonequivalence of the Schematic Protection Model (SPM) and the Extended Schematic Protection Model (ESPM). We also show how the results apply to the typed access matrix model (TAM), which is an extension of the well known access matrix model formalized by Harrison, Ruzzo and Ullman (HRU). The results in this paper offer theoretical justification for regarding single-parent and multi-parent creation as fundamentally different operations in a monotonic context. The paper also demonstrates that in nonmonotonic models, multi-parent creation can be reduced to single-parent creation, thereby neutralizing the difference in expressive power.

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

Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. This paper gives an elementary proof that each player has a near-optimal mixed strategy that chooses uniformly at random from a multiset of pure strategies of size logarithmic in the number of pure strategies available to the opponent. For exponentially large games, for which even representing an optimal mixed strategy can require exponential space, it follows that there are near-optimal, linear-size strategies. These strategies are easy to play and serve as small witnesses to the approximate value of the game. As a corollary, it follows that every language has small ``hard'' multisets of inputs certifying that small circuits can't decide the language. For example, if SAT does not have polynomial-size circuits, then, for each n and c, there is a set of n^(O(c)) Boolean formulae of size n such that no circuit of size n^c (or algorithm running in time n^c) classifies more than two-thirds of the formulae succesfully.

This paper considers Boolean formulae and their simulations by bounded width branching programs. It is shown that every balanced Boolean formula of size s can be simulated by a constant width (width 5) branching program of length $s^{1.811 \ldots } $. A lower bound for the translational cost from formulae to permutation branching programs is also presented.

Article Free Access Share on Amplification of weak learning under the uniform distribution Authors: Dan Boneh View Profile , Richard J. Lipton View Profile Authors Info & Claims COLT '93: Proceedings of the sixth annual conference on Computational learning theoryAugust 1993 Pages 347–351https://doi.org/10.1145/168304.168372Published:01 August 1993Publication History 9citation219DownloadsMetricsTotal Citations9Total Downloads219Last 12 Months22Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let A be an $n \times n$ matrix with 0-1 valued entries, and let ${\operatorname{per}}(A)$ be the permanent of A. This paper describes a Monte-Carlo algorithm that produces a “good in the relative sense” estimate of ${\operatorname{per}}(A)$ and has running time ${\operatorname{poly}}(n)2^{{n / 2}} $, where ${\operatorname{poly}}(n)$ denotes a function that grows polynomially with n.

Formal demonstration of equivalence or nonequivalence of different security models helps identify the fundamental constructs and principles in such models. The authors demonstrate the nonequivalence of two monotonic access control models that differ only in the creation operation for new subjects and/or objects; in particular, they show that single-parent creation is less expressive than multi-parent creation in monotonic models. The paper also demonstrates that in nonmonotonic models, multi-parent creation can be reduced to single-parent creation, thereby neutralizing the difference in expressive power. The nonequivalence proof is carried out on an abstract access control model, following which the results are interpreted in standard formulations. In particular, they apply the results to demonstrate nonequivalence of the schematic protection model (SPM) and the extended schematic protection model (ESPM). They also show how the results apply to the typed access matrix model (TAM).>

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

The authors present several techniques to identify, or diagnose, hot spots in a database. All of them are probabilistic in the sense that they will classify the items as hot or cold and exhibit a non-zero probability of false diagnoses. Each technique is analysed to identify the tradeoffs of time and space involved in maintaining a low probability of false diagnosis. Each of the techniques is presented. The analyses of the techniques is considered to determine how likely they are to diagnose without error. The techniques are compared. A numerical comparison based on the analyses is included.>

The problem of storing a triangular matrix so that each row and column is stored as a vector, i.e. the locations form an arithmetic progression, is discussed. Storing rows and columns as vectors can speed up access significantly. It is shown that there is no such storage method that does not waste approximately one-half of the computer memory.>

The study of self-testing/correcting programs was introduced in [8] in order to allow one to use program P to compute function f without trusting that P works correctly. A self-tester for f estimates the fraction of x for which P (x) = f(x); and a self-corrector for f takes a program that is correct on most inputs and turns it into a program that is correct on every input with high probability 1. Both access P only as a black-box and in some precise way are not allowed to compute the function f. Self-correcting is usually easy when the function has the random self-reducibility property. One class of such functions that has this property is the class of multivariate polynomials over finite fields [4] [12]. We extend this result in two directions. First, we show that polynomials are random self-reducible over more general domains: specifically, over the rationals and over noncommutative rings. Second, we show that one can get self-correctors even when the program satisfies weaker conditions, i.e. when the program has more errors, or when the program behaves in a more adversarial manner by changing the function it computes between successive calls. Self-testing is a much harder task. Previously it was known how to self-test for a few special examples of functions, such as the class of linear functions. We show that one can self-test the whole class of polynomial functions over Zp for prime p.

A class of algorithms that use randomized signatures to compare remotely located file copies is presented. A simple technique that sends on the order of 4/sup f/log(n) bits, where f is the number of differing pages that are to be diagnosed and n is the number of pages in the file, is described. A method to improve the bound in the number of bits sent, making them grow with f as flog(f) and with n as log(n)log(log(n)), and a class of algorithms in which the number of signatures grows with f as fr/sup f/, where r can be made to approach 1, are also presented. A comparison of these techniques is discussed.>

A simple proof is given, showing that for every operational description of a software system expressed as a discrete state transition function on a virtual machine, there is a continuous smooth function on the reals that agrees with the state transition function on all legal states and has exactly the same complexity. It is suggested that an implication of this result is that there is no reason, in principle, that the methods of classical analysis cannot be used in software engineering.>

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, …, Qn, and 2) for 1 ≤ i ≤ n, the size of Qi is bounded by some function b(D, Q), and 3) there is some algorithm by which we can compute the size of Qi, where i is chosen randomly. We consider the performance of the algorithm on three special cases of the algorithm: join queries, transitive closure queries, and general recursive Datalog queries.

Recently we have proposed an adaptive, random sampling algorithm for general query size estimation. In earlier work we analyzed the asymptotic efficiency and accuracy of the algorithm, in this paper we investigate its practicality as applied to selects and joins. First, we extend our previous analysis to provide significantly improved bounds on the amount of sampling necessary for a given level of accuracy. Next, we provide “sanity bounds” to deal with queries for which the underlying data is extremely skewed or the query result is very small. Finally, we report on the performance of the estimation algorithm as implemented in a host language on a commercial relational system. The results are encouraging, even with this loose coupling between the estimation algorithm and the DBMS.

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

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

A technique for file comparison is presented that is based in a set of signatures that are selected by a randomized algorithm. The sites performing the comparison agree on this randomized set of signatures before any comparison takes place. This technique proves to be very competitive with previously published algorithms. It has an advantage over previous techniques in that one can set up the algorithm to diagnose up to a given number of different pages. This is done by changing the total number of bits sent to guarantee that the expected number of falsely diagnosed pages remains under a given level. A metric for comparing the complexity of file comparison techniques is introduced, based on the number of bits that the algorithm needs to send in order to diagnose a given number of differing pages while keeping the probability of false diagnosis under a certain level of confidence.>

Paging performance can be a dominant factor in a program's running time. Many seemingly efficient data structures and algorithms lose orders of magnitude in performance because they generate an excessive number of page faults. This study shows that tradeoffs exist between average row access speed S/sub r/ (which is defined as the number of row elements retrieved divided by the number of blocks accessed) and average column access speed S/sub c/ (defined similarly). The authors prove that the S/sub r/S/sub c/ product is optimally bounded by the block size N and generalize to other access patterns. Practical array access strategies are developed, and extensions to these results are discussed.>

The accessibility problem for linear sequential machines [12] is the problem of deciding whether there is an input x such that on x the machine starting in a given state q 1 goes to a given state q 2 . Harrison shows that this problem is reducible to the following simply stated linear algebra problem, which we call the "orbit problem": Given ( n, A, x, y ), where n is a natural number and A, x, and y are n x n , n x 1, and n x 1 matrices of rationals, respectively, decide whether there is a natural number I such that A i x = y . He conjectured that the orbit problem is decidable. No progress was made on the conjecture for ten years until Shank [22] showed that if n is fixed at 2, then the problem is decidable. This paper shows that the orbit problem for general n is decidable and indeed decidable in polynomial time. The orbit problem arises in several contexts; two of these, linear recurrences and the discrete logarithm problem for polynomials, are discussed, and we apply our algorithm for the orbit problem in these contexts.

Article Free Access Share on A method for drawing graphs Authors: R. J. Lipton Princeton University, Princeton, NJ Princeton University, Princeton, NJView Profile , S. C. North AT&T Bell Laboratories, Murray Hill, New Jersey AT&T Bell Laboratories, Murray Hill, New JerseyView Profile , J. S. Sandberg AT&T Bell Laboratories, Murray Hill, New Jersey AT&T Bell Laboratories, Murray Hill, New JerseyView Profile Authors Info & Claims SCG '85: Proceedings of the first annual symposium on Computational geometryJune 1985 Pages 153–160https://doi.org/10.1145/323233.323254Online:01 June 1985Publication History 40citation611DownloadsMetricsTotal Citations40Total Downloads611Last 12 Months14Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The classes of languages accepted by alternating pushdown automata, alternating stack automata, and alternating nonerasing stack automata, both with and without an auxiliary space bounded worktape, are characterized in terms of complexity classes defined by time bounded deterministic Turing machines. It is also shown that alternating 2-way finite state machines accept only regular languages.

This paper argues the case for a computer with massive amounts of primary storage, on the order of tens of billions of bytes. We argue that such a machine, even with a relatively slow processor, can outperform all other super-computers on memory bound computations. This machine would be simple to program. In addition, it could lead to new and highly efficient programs which traded the available space for running time. We present a novel architecture for such a machine, and show how it can lead to reduced memory access times and higher reliability.

We consider the computation of finite semigroups using unbounded fan-in circuits. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f, circuits of size O(nf−1(n)) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f. The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n-bit numbers.

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

The first component of a VLSI (very large-scale integration) design environment being built at Princeton University is described.The general theme of this effort is to make the design of VLSI circuits as similar to programming as possible.The attempt is to build tools that do for the VLSI circuit designer what the best software tools do for the implementer of large software systems.

In the last few years there has been a great deal of basic research into computational complexity. This research has focused on the discovery of efficient algorithms for a wide range of problems. These problems include ones from number theory, geometry, graph theory, combinatorics, organizational research, and many other areas. Major progress has been made in both finding new fast and efficient algorithms and in showing for certain problems that no such algorithms can exist.

ALI is a procedural language to specify VLSI layouts. It allows the designer to describe layouts without reference to the sizes and positions of the layout elements or to the distances between them. Among the interesting characteristics of ALI are that it does not need design rule checking, is easy to extend, facilitates the division of labor and permits the easy update of a layout to new design rules or to new processes. The general features of the language and the experience gained with a preliminary implementation of it are described.

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 design of large software systems to the creation of an appropriate environment for VLSI circuits. The two components described are a procedural language to specify circuit layouts and a switch-level circuit simulator for layout produced with this language. They have been chosen for presentation because many issues in their design are very similar to the issues that arise in the design of programming languages and software environments.

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.

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 integer multiplication [1,2], matrix multiplication [7], sorting [8], and discrete Fourier transform [9], all within VLSI models similar to one originally developed by Thompson [8,9]. The lower bound results all pertain to a space-time trade-off measure that arises naturally within this model. In this paper, we extend the model and the class of functions for which non-trivial bounds can be proved. In Section 2, we give a more general model than has been proposed previously. In Section 3 we show how to reduce the derivation of lower bounds within the model to a problem in distributed computing In Section 4, we consider lower bounds for a number of predicates: n-input, l-output functions (as contrasted with the n-input, n-output functions which have been studied previously). In Section 5, we show that previous lower bound results (for n-input, n-output functions) also apply even when the model is extended to allow nondeterminism, randomness, and multiple arrivials. Finally, the full details of the results presented here will appear in the final version of this paper.

We show that any biconnected graph with n nodes and m edges can be covered by simple circuits whose total length is at most $\min (3m,m + 6n)$. Our proof suggests an efficient algorithm for finding such a cover.

In testing for program correctness, the standard approaches [11,13,21,22,23,24,34] have centered on finding data D, a finite subset of all possible inputs to program P, such that

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 implemented simply and efficiently.

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 increasingly sensitive information made available in increasingly less supervised modes to a variety of users. Commercial users routinely store valuable financial information and conduct cashless transactions electronically. University professors maintain class grading forms and examinations on departmental computers. Government agencies keep extensive databases of sensitive information regarding employees, foreign nationals, U.S. citizens. The military and intelligence communities continue to press for more powerful techniques to enhance their information gathering and processing capabilities. In spite of the clear need for guarantees of security, all practical schemes to protect information stored or manipulated by such systems are either seriously flawed or reduce ultimately to a collection of physical security protocols (ace [1] for an overview of the state of the art).

@ Consistency results represent an approach to the lower bound problems of complexity theory which points to a number of interesting lines of inquiry. Our ultimate goal is to make precise the difficulty of proving certain nontrivial lower bounds. Among the possibilities which follow from this approach are: (1) that logical techniques may help us resolve the P e NP question, (2) that showing why certain arguments must fail may lead to mathematical tools capable of resolving the problems, and (3) that the special character of model theoretic methods in complexity theory may lead to new results which are of purely logical interest. We will address these possibilities below.

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 reducible to the “orbit problem:” Given AεQn×n does there exist iεN such that Aix =y.* We will call this the “orbit problem” because the question can be rephrased as: Does y belong to the orbit of x under A where the “orbit of x under A” is the set {Aix: i = 0,1,2,...}. (A0 is the identity matrix I.) In Harrison's original problem the elements of A,x, and y were members of an arbitrary “computable” field. In view of the lack of structure of such fields, we study only the rationals. Shank [13] proves that the orbit problem is decidable for the rational case when n=2. The current paper establishes that for the general rational case, the problem is decidable - and in fact polynomial-time decidable.

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 relationships between uniform and nonuniform complexity bounds. They obtain a nonuniform upper bound as a consequence of a uniform upper bound.

AnSTRACT Let G and G* be programs represented by directed graphs There is defined a relation ~-s.r between G and G* that formahzes the notton of G* simulating G with Sffold loss of space efficiency and T-fold loss of time efficiency, ~t is proved that ff G - lo B n + O(Iog2 logz n) KEY WORDS AND PHRASES ancestor tree, complexity, control structure, dtrected graph, embedding CR CATEGORIES 4 22, 4 34, 5 24, 5 32 IntroducttonIn a previous paper [1] we made precise some intuitwe observations concerning the efficiency of structured programs by defining a combinatorial relation that corresponds to the notion of uniform szrnulatton between programs.Informally, we say that a program G* uniformly simulates a program G ff G* carries out the computation of G (and possibly addRlonal computation which might be regarded as "bookkeeping") in such a way that the space-time efficiency of G is degraded by a factor that is independent of the size of G.The main results of [ 1] indicate that the nonexistence of uniform simulations among many well-known classes of control structures is at least in part due to the combinatorial aspects of program structure and not to such details of program orgamzation as choice of data structures or limitations on the form of Boolean expressions.Indeed, the main result of [1, Th. 5.1] provides a nontrivml lower bound on the loss of space-time efficiency in any structured simulation of a goto program.This short note extends that result, improving the space-time inequality of [1, Th. 5.1] by an exponentml.Thus we now show that there are goto programs with n statements such that for any structured simulation either Pernnsslon to copy wtthout fee all or part of this matenal is granted provided that the copies are not made or distnbuted for direct commercial advantage, the ACM copyright notice and the tttle of the pubhcation and Rs date appear, and notice is gwen that copying ts by permission of the AssoclaUon for Computing Machinery To copy otherwise, or to republish, requires a fee and/or specific permission These results were announced at the 1976 Johns Hopkins Conference on Information Sciences and Systems

The use of external hashing schemes for storing broad classes of data structures is studied The general framework of the paper considers a class of data structures parutioned into smaller classes by the number of positions m the structure For instance, one could start with the class of all binary trees and partiuon that class into the subclasses ~, % ..... each q¢~ comprising all n-node binary trees.The mare results establish nonconstructively the existence of an external hashing scheme h,, with O(n) storage demand and O(1) expected access time that will store any structure in % O q¢2 U ... U %, provtded ten contains a number of structures growing at most exponenttally m n Classes of data structures subsumed by these results include ragged arrays, binary trees, stringindexed arrays, and refmable arrays

Addition chains are considered for specific polynomials. It is shown that for a wide class of polynomials the evaluation of their first n terms requires at least $n + O(n^{2/3} )$ additions. Included in this class are the first n squares, the first n cubes, $ \cdots $, the first nkth powers. The results are established by making contact with results in combinatorics.

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only $O(\sqrt 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.

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 = NP and related questions, we most likely find them dealing with a lack of understanding of particular computational problems and their lower bounds. This is the sense of Hopcroft's prediction: “...within the next five years, nobody will prove that any of these problems takes more than let's say n2 time. I think that's a reasonably safe conjecture and it also illustrates how little we know about lower bounds.” [MT]. Hopcroft's guess is uncanny in its accuracy—after six years and considerable effort by many researchers, his conjecture remains unchallenged.

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.

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.

The concept of reduction between problems is strengthened. Certain standard problems are shown to be complete in the new and stronger sense. Applications to the number of solutions of particular problems are presented.

Users can compromise data bases by asking a series of questions, even when the data bases are allowed to lie.

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.

Article Free Access Share on Social processes and proofs of theorems and programs Authors: Richard A. DeMillo Georgia Institute of Technology Georgia Institute of TechnologyView Profile , Richard J. Lipton Yale University Yale UniversityView Profile , Alan J. Perlis Yale University Yale UniversityView Profile Authors Info & Claims POPL '77: Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languagesJanuary 1977 Pages 206–214https://doi.org/10.1145/512950.512970Online:01 January 1977Publication History 22citation680DownloadsMetricsTotal Citations22Total Downloads680Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A particular protection mechanism from the protection hterature-the take and grant system--is presented For this particular mechanism, it is shown that the safety problem can be solved in linear time Moreover the security policies that this mechanism can enforce are characterized KEY WORDS AND PHRASES protection,

Extending a result of Rabin, It Is shown that the word problem for hnear groups (groups of matrices) over a field of characteristic 0 is solvable in (deterministic) logspace As an apphcatlon of this result, it follows that the word problem for free groups and hence the membership problem for the two-sided Dyck language are solvable in logspace

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.

The uniform word problem for commutative semigroups (UWCS) is the problem of determining from any given finite set of defining relations and any pair of words, whether the words describe the same element in the commutative semigroup defined by the relations. The effective decidability of this classical algebraic problem was first explicitly noted by Malcev [1958] and Emilichev [1958], though in retrospect this result can be seen to be contained in the earlier work of König [1903] and Hermann [1926] on polynomial ideals.

@In this paper this question is generalized to the following question:Given a polynomial f(x) and an operator D that maps polynomials to sets of polynomials,Find a minimal cost straightline program that computes some h(x) e D(f(x)).

Control structures and data structures are modeled by directed graphs. In the control case nodes represent executable statements and arcs represent possible flow of control; in the data case nodes represent memory locations and arcs represent logical adjacencies in the data structure. Classes of graphs are compared by a relation ≤ S.T where G ≤ S.T H if G can be embedded in H with at most a T -fold increase in distance between embedded nodes by making at most S “copies” of any node in G . For both control structures and data structures, S and T are interpreted as space and time constants, respectively. Results are presented that establish hierarchies with respect to ≤ S.T for (1) data structures, (2) sequential program schemata normal forms, and (3) sequential control structures.

Classic binary search is extended to multidimensional search problems. This extension yields efficient algorithms for a number of tasks such as a secondary searching problem of Knuth, region location in planar graphs, and speech recognition.

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

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 the assumption that a routine is uninterruptible can be relaxed and still preserve basic properties such as halting and determinacy. Thus correctness proofs of a system of processes can often be greatly simplified. This technique - called reduction - is viewed as the replacement of an interruptible routine by an uninterruptible one.

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.

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 consider the classes of integers and polynomials that can be evaluated within given complexity bounds and prove the existence of proper hierarchies of complexity classes. The framework in which our problems are cast is general enough to allow any finite set of binary operations rather than just addition, subtraction, multiplication, and division. The motivation for studying complexity classes rather than specific integers or polynomials is analogous to why complexity classes are studied in automata-based complexity: (i) the immense difficulty associated with computing the complexity of a specific integer or polynomial; (ii) the important insight obtained from discovering the structure of the complexity classes.

The running time or computational complexity of a sequential process is usually determined by summing weights attached to the basic operations from which the process is derived. In practice, however, the complexity is often limited by how efficiently it can access its data structures and how efficiently it can control program flow. Furthermore, it has been extensively argued [4] that certain limitations on the process sequencing mechanisms available to the programmer result in more “efficient” representations for the underlying processes. In this paper we will examine these issues in an attempt to assess the “power” of various data and control structures.

Classic binary search is extended to multidimensional search problems. These new search methods can efficiently solve several important problems of computer science. Applications of these results to an open problem in the theory of computation are discussed yielding new insight into the Lba problem.

A formal model of the process concept is presented. This model can represent sets of processes that use the synchronization primitive PV or one of the many generalizations of PV. The study of synchronization problems is then reduced to the study of relations between sets of processes. For one relation— “simulate”—it is possible to show that there are differences between several synchronization primitives. These differences show that the relative “power” of these synchronization primitives is not the same.