Summary: Zero-knowledge proofs (ZKPs) are one of the most striking innovations in theoretical computer science. In practice, the prevalent ZKP methods are, at times, too complicated to be useful for real-life applications. In this paper we present a practically efficient method for ZKPs which has a wide range applications. Specifically, motivated by the need to provide an upon-demand efficient validation of various financial transactions (e.g., the high-volume Internet auctions), we have developed a novel secure and highly efficient method for validating correctness of the output of a transaction while keeping input values secret. The method applies to input values which are publicly committed to by employing generic commitment functions (even input values submitted using tamper-proof hardware solely with input/output access can be used.) We call these: strictly black box (SBB) commitments. Hence these commitments are typically much faster than public-key ones, and are the only cryptographic/security tool we give the poly-time players, throughout. The general problem we solve in this work is: Let SLC be a publicly known staight line computation on n$n$ input values taken from a finite field and having k$k$ output values. The inputs are publicly committed to in a SBB manner. An evaluator performs the SLC on the inputs and announces the output values. Upon demand the evaluator, or a prover acting on his behalf, can present to a Verifier a proof of correctness of the announced output values. This is done in a manner that (1) The input values as well as all intermediate values of the SLC remain information theoretically secret. (2) The probability that the verifier will accept a false claim of correctness of the output values can be made exponentially small. (3) The prover can supply any required number of proofs of correctness to multiple verifiers. (4) The method is highly efficient. The application to financial processes is straight forward. To this end (1) we first use a novel technique for representation of values from a finite field which we call “split representation”, the two coordinates of the split representation are generically committed to; (2) next, the SLC is augmented by the prover into a “translation” which is presented to the Verifier as a sequence of generically committed split representations of values; (3) using the translation, the prover and verifier conduct a secrecy preserving proof of correctness of the announced SLC output values; (4) in order to exponentially reduce the probability of cheating by the prover and also to enable multiple proofs, a novel highly efficient method for preparation of any number of committed-to split representations of the n$n$ input values is employed. The extreme efficiency of these ZK methods is of decisive importance for large volume applications. Secrecy preserving validation of announced results of Vickrey auctions is our demonstrative example.
For the entire collection see [Zbl 1268.68011].

Summary: We present a cryptographic protocol for conducting efficient, provably correct and secrecy-preserving combinatorial clock-proxy auctions. The “clock phase” functions as a trusted auction despite price discovery: bidders submit encrypted bids, and prove for themselves that they meet activity rules, and can compute total demand and thus verify price increases without revealing any information about individual demands. In the sealed-bid “proxy phase”, all bids are revealed the auctioneer via time-lapse cryptography and a branch-and-bound algorithm is used to solve the winner-determination problem. Homomorphic encryption is used to prove the correctness of the solution, and establishes the correctness of the solution to any interested party. Still an NP-hard optimization problem, the use of homomorphic encryption imposes additional computational time on winner-determination that is linear in the size of the branch-and-bound search tree, and thus roughly linear in the original (search-based) computational time. The result is a solution that avoids, in the usual case, the exponential complexity of previous cryptographically-secure combinatorial auctions.
For the entire collection see [Zbl 1178.94005].

Summary: We introduce and define the notion of identity-based zero-knowledge, concentrating on the non-interactive setting. In this setting, our notion allows any prover to widely disseminate a proof of a statement while protecting the prover from plagiarism in the following sense: although proofs are transferable (i.e., publicly verifiable), they are also bound to the identity of the prover in a way which is recognizable to any verifier. Furthermore, an adversary is unable to change this identity (i.e., to claim the proof as his own, or to otherwise change the authorship), unless he could have proved the statement on his own.
While we view the primary contribution of this work as a formal definition of the above notion, we also explore the relation of this notion to that of non-malleable (non-interactive) zero-knowledge. On the one hand, we show that these two notions are incomparable: that is, there are proof systems which are non-malleable but not identity-based, and vice versa. On the other hand, we show that a proof system of either type essentially implies a proof system of the other type.
For the entire collection see [Zbl 1067.68002].

For the entire collection see [Zbl 1568.68003].

Summary: A fundamental problem in cryptography is that of secure communication over an insecure channel, where a sender Alice wishes to communicate with a receiver Bob, in the presence of a powerful Adversary AD$\mathcal{A}D$. The primary goal of encryption is to protect the privacy of the conversation between Alice and Bob against AD$\mathcal{A}D$. Modern cryptographic research has identified additional essentially important criteria for a secure encryption scheme. Namely that the encryption be non-malleable, be resistant to various chosen plaintext and ciphertext attacks, and if so desired, will allow the receiver to authenticate the received message and its sender. All these issues are now settled for the case that the Adversary AD$\mathcal{A}D$ is computationally unbounded.
For the entire collection see [Zbl 1020.00018].

Summary: We present substantial extensions of work by Y. Aumann and the second author [Lect. Notes Comput. Sci. 1666, 65–79 (1999; Zbl 0940.94007)], by Y. Aumann and the authors [IEEE Trans. Inf. Theory 48, No. 6, 1668–1680 (2002)] and all previous works on encryption in the bounded storage model introduced by U. Maurer [Lect. Notes Comput. Sci. 1046, 387–398 (1996)]. The major new result is that the shared secret key employed by the sender Alice and the receiver Bob can be re-used to send an exponential number of messages, against strong adaptive attacks. This essential step enhances the usability of the encryption method, and also allows strong authentication and non-malleability described below.
We give an encryption scheme that is provably secure against adaptive attacks by a computationally unbounded adversary in the bounded storage model. In the model, a sender Alice and a receiver Bob have access to a public random string α$\alpha$, and share a secret key s$s$. Alice and Bob observe α$\alpha$ on the fly, and by use of s$s$ extract bits from which they create a one-time pad X$X$ used to encrypt M$M$ as C=X⊕M$C=X\oplus M$. The size of the secret key s$s$ is |s|=klog2|α|$|s|=k{\log }_2|\alpha |$, where k$k$ is a security parameter. An Adversary AD$\mathcal{A}\mathcal{D}$ can compute and store any function A1(α)=η$A_1(\alpha )=\eta$, subject to the bound on storage |η|≤γ⋅|α|$|\eta |\le \gamma \cdot |\alpha |$, γ<1$\gamma <1$, and captures C$C$. Even if AD$\mathcal{A}\mathcal{D}$ later gets the key s$s$ and is computationally unbounded, the encryption is provably secure. Assume that the key s$s$ is repeatedly used with successive strings α1,α2,…${\alpha }_1,{\alpha }_2,\dots$ to produce encryptions C1,C2,…$C_1,C_2,\dots$ of messages M1,M2,…$M_1,M_2,\dots$. AD$\mathcal{A}\mathcal{D}$ computes η1=A1(α1)${\eta }_1=A_1({\alpha }_1)$, obtains C1$C_1$, and gets to see the first message M1$M_1$. Using these he computes and stores η2=A1(α2,η1,C1,M1)${\eta }_2=A_1({\alpha }_2,{\eta }_1,C_1,M_1)$, and so on. When he has stored ηl${\eta }_l$ and captured Cl$C_l$, he gets the key s$s$ (but not Ml)$M_l)$. The main result is that the encryption Cl$C_l$ is provably secure against this adaptive attack, where l$l$, the number of time the secret key s$s$ is re-used, is exponentially large in the security parameter k$k$. On this we base non-interactive protocols for authentication and non-malleability. Again, the shared secret key used in these protocols can be securely re-used an exponential number of times against adaptive attacks. The method of proof is stronger than the one in the previous papers [loc. cit.], and yields ergodic results of independent interest. We discuss in the Introduction the feasibility of the bounded storage model, and outline a solution. Furthermore, the existence of an encryption scheme with the provable strong security properties presented here, may prompt other implementations of the bounded storage model.
For the entire collection see [Zbl 0989.00048].

Summary: We study the problem of executing parallel programs, in particular Cilk programs, on a collection of processors of different speeds. We consider a model in which each processor maintains an estimate of its own speed, where communication between processors has a cost, and where all scheduling must be online. This problem has been considered previously in the fields of asynchronous parallel computing and scheduling theory. Our model is a bridge between the assumptions in these fields. We provide a new more accurate analysis of an old scheduling algorithm called the maximum utilization scheduler. Based on this analysis, we generalize this scheduling policy and define the high utilization scheduler. We next focus on the Cilk platform and introduce a new algorithm for scheduling Cilk multithreaded parallel programs on heterogeneous processors. This scheduler is inspired by the high utilization scheduler and is modified to fit in a Cilk context. A crucial aspect of our algorithm is that it keeps the original spirit of the Cilk scheduler. In fact, when our new algorithm runs on homogeneous processors, it exactly mimics the dynamics of the original Cilk scheduler.

Summary: We extend the notion of linearity testing to the task of checking linear consistency of multiple functions. Informally, functions are “linear” if their graphs form straight lines on the plane. Two such functions are “consistent” if the lines have the same slope. We propose a variant of a test of M. Blum, M. Luby and R. Rubinfeld [J. Comput. Syst. Sci. 47, 549–595 (1993; Zbl 0795.68131)] to check the linear consistency of three functions f1,f2,f3$f_1,f_2,f_3$ mapping a finite Abelian group G$G$ to an Abelian group H$H$: Pick x,y∈G$x,y\in G$ uniformly and independently at random and check if f1(x)+f2(y)=f3(x+y)$f_1(x)+f_2(y)=f_3(x+y)$. We analyze this test for two cases: (1) G$G$ and H$H$ are arbitrary Abelian groups and (2) G=Fn2$G={\mathbb{F}}_2^n$ and H=F2$H={\mathbb{F}}_2$. Questions bearing close relationship to linear-consistency testing seem to have been implicitly considered in recent work on the construction of PCPs and in particular in the work of J. Håstad [Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, Texas, 4–6 May 1997, 1–10 (1999; Zbl 0963.68193)]. It is abstracted explicitly for the first time here. As an application of our results we give yet another new and tight characterization of NP, namely ∀ε>0$\mathrm{\forall }\epsilon >0$, NP = MIP1−ε,1/2[O(logn),3,1]${}_{1-\epsilon ,1/2}[O(\log n),3,1]$. That is, every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(logn)$O(\log n)$ coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts instance of the language with probability 1−ε$1-\epsilon$ and rejects noninstances with probability at least 12$\frac{1}{2}$. Such a result is of some interest in the study of probabilistically checkable proofs.

For the entire collection see [Zbl 1058.68002].

Summary: The authors provide a simple secret-key two-party secure communication scheme [see also U. M. Maurer, J. Cryptology 5, 53-66 (1992; Zbl 0746.94013)], which is provably information-theoretically secure in the limited-storage-space model. The limited-storage-space model postulates an eavesdropper who can execute arbitrarily complex computations, and is only limited in the total amount of storage space (not computation space) available to him. The bound on the storage space can be arbitrarily large (e.g. terabytes), as long as it is fixed. Given this bound, the protocol guarantees that the probability of the eavesdropper of gaining any information on the message is exponentially small. The proof of the main results utilizes a novel combination of linear algebra and Kolmogorov complexity considerations.
For the entire collection see [Zbl 0921.00042].

Summary: We extend the notion of linearity testing to the task of checking linear-consistency of multiple functions. Informally, functions are “linear” if their graphs form straight lines on the plane. Two such functions are “consistent” if the lines have the same slope. We propose a variant of a test of M. Blum, M. Luby and R. Rubinfeld [J. Comput. Syst. Sci. 47, No. 3, 549-595 (1993; Zbl 0795.68131)] to check the linear-consistency of three function f1$f_1$, f2$f_2$, f3$f_3$ mapping a finite Abelian group G$G$ to an Abelian group H$H$: Pick x,y∈G$x,y\in G$ uniformly and independently at random and check if f1(x)+f2(y)=f3(x+y)$f_1(x)+f_2(y)=f_3(x+y)$. We analyze this test for two cases: (1) G$G$ and H$H$ are arbitrary Abelian groups and (2) G=Fn2$G={\mathbb{F}}_2^n$ and H=F2$H={\mathbb{F}}_2$.
Questions bearing close relationship to linear-consistency testing seem to have been implicitly considered in recent work on the construction of PCPs. It is abstracted explicitly for the first time here. We give an application of this problem (and of our results): A (yet another) new and tight characterization of NP, namely ∀ε>0$\mathrm{\forall }\epsilon >0$, NP=MIP1−ε,12[O(logn),3,1]$\text{NP}={\text{MIP}}_{1-\epsilon ,\frac{1}{2}}[O(\log n),3,1]$. I.e., every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(logn)$O(\log n)$ coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts instance of the language with probability 1−ε$1-\epsilon$ and rejects non-instances with probability at least 12$\frac{1}{2}$. Such a result is of some interest in the study of probabilistically checkable proofs.
For the entire collection see [Zbl 0921.00035].

Summary: We propose a new way to use DNA computations. This will allow us to use DNA computations to solve important and potentially killer applications. The potential applications include: 1. DNA sequencing; 2. DNA fingerprinting; 3. DNA mutation detection or population screening; 4. Other fundamental operations on DNA. The key new idea is to use DNA computation to operate on unknown pieces of DNA. This is a fundamental change in the way that we use DNA computation.
For the entire collection see [Zbl 0914.00083].

For the entire collection see [Zbl 1320.68006].

Summary: In electronic communications and in access to systems, the issue of authentication of the sender S$S$ of a message M$M$, as well as of the message itself, is of paramount importance. Recently S. Goldwasser has raised the additional issue of deniable authentication where the sender S$S$ authenticates the message M$M$ to the receiver’s (R$R$) satisfaction, but can later deny his authorship of M$M$ even to an inquisitor INQ who has listened to the exchange between S$S$ and R$R$ and who gains access to all of the the secret information used by S$S$ and R$R$. The authors present two practical schemes for deniable authentication of messages M$M$ of arbitrary length n$n$. In both schemes the receiver R$R$ is assured with probability greater than 1−2−k$1-2^{-k}$, where k$k$ is a chosen security parameter, that M$M$ originated with the sender S$S$. Deniability is absolute in the information theoretic sense. The first scheme requires 2.4kn$2.4kn$ XOR operations on bits and one public key encoding and decoding of a short message. The second scheme requires the same number of XOR operations and k$k$ multiplications mod N$\text{mod }N$, where N$N$ is some fixed product of two large primes.
A key new feature of their method is the use of a Shannon-style error correction code. Traditional authentication for a long message M$M$ starts by hashing M$M$ down to a standard word-size. The authors expand M$M$ through error correction. The first deniable authentication method is provably valid for any encryption scheme with minimal security properties, i.e. this method is generic. The second deniable authentication method is provably valid under the usual assumption that factorization is intractable.
For the entire collection see [Zbl 0895.00067].

Summary: We establish, for the first time, lower bounds for randomized mutual exclusion algorithms (with a read-modify-write operation). Our main result is that a constant-size shared variable cannot guarantee strong fairness, even if randomization is allowed. In fact, we prove a lower bound of Ω(loglogn)$\mathrm{\Omega }(\log \log n)$ bits on the size of the shared variable, which is also tight.
We investigate weaker fairness conditions and derive tight (upper and lower) bounds for them as well. Surprisingly, it turns out that slightly weakening the fairness condition results in an exponential reduction in the size of the required shared variable. Our lower bounds rely on an analysis of Markov chains that may be of interest on its own and may have applications elsewhere.

Reprint from: Complexity of computation, Proc. Symp. Appl. Math., New York City 1973, 27-41 (1974; Zbl 0319.68024).
For the entire collection see [Zbl 0906.03033].

Summary: Lotteries with the unique maximum property and the unique winner property are considered. Tight lower bounds are proven on the domain size of such lotteries.

Summary: We consider the problem of simulating synchronous computations on asynchronous shared memory systems. The systems we consider allow for arbitrary asynchronous behavior of the processors. In addition, we make very limited (and in some cases no) assumptions about the atomicity of read and write operations to shared memory. We provide detailed definitions of these asynchronous systems and their atomicity properties.
The first construction in this paper is a novel clock for asynchronous systems. The clock is a basic tool for synchronization in the asynchronous environment. The construction we give is extremely robust, and can be implemented in a system with no atomicity assumptions, and in the presence of an adaptive adversary scheduler. The correct behavior of the clock is obtained with overwhelming probability (>1−2−αn,α>0)$(>1-2^{-\alpha n},\alpha >0)$.
We then show how to harness this clock to drive an efficient PRAM simulation on an asynchronous system. The simulation requires an O(log2n)$O({\log }^{2}n)$ work, and O(logn)$O(\log n)$ space, overhead. This improves by a logn$\log n$ factor on the efficiency of previously obtained simulation results, while relaxing the assumptions on the underlying asynchronous system.

Summary: We present an optimal parallel pattern matching algorithm for d$d$-dimensional patterns. Namely, for two d$d$-dimensional arrays A$A$ and B$B$, |A|=md=M$|A|=m^d=M$, |B|=nd=N$|B|=n^d=N$, and k≤N/log2m$k\le N/{\log }_{2}m$ processors, all occurrences of A$A$ in B$B$ can be found in time d⋅cN/k+log2k$d\cdot cN/k+{\log }_{2}k$ on an exclusive real exclusive write (EREW) PRAM, or in time d⋅cN/k$d\cdot cN/k$ on a concurrent read exclusive write (CREW) PRAM. In the CREW algorithm, concurrent read is invoked just once. The main tools are parallel prefix computation and randomization. All previous results in this area employed a concurrent read concurrent write (CRCW) PRAM model. As a demonstration of the power of this method, we provide a simple optimally efficient algorithm for the suffix-prefix matching problem of Z. M. Kedem, G. M. Landau and K. V. Palem [“Optimal parallel suffix-prefix matching algorithm and applications”, Proc. of the 1989 ACM Symp. on Parallel Algorithms and Architectures, 388-399] again for an EREW rather than for a CRCW machine.
For the entire collection see [Zbl 0811.00037].

For the entire collection see [Zbl 1285.68003].

Summary: Let q$q$ be a prime power. It is shown that for any hypergraph F={F1,…,Fd(q−1)+1}$\mathcal{F}=\{F_1,\dots ,F_{d(q-1)+1}\}$ whose maximal degree is d$d$, there exists ∅≠F0⊂F$\varnothing \ne {\mathcal{F}}_0\subset \mathcal{F}$, such that |⋃F∈F0F|≡0(modq)$|\bigcup _{F\in {\mathcal{F}}_0}F|\equiv 0(\mathrm{mod}q)$.

Summary: [For the entire collection see Zbl 0685.00004.]
We present the Information Dispersal Algorithm (IDA) which breaks a file F of length L=|F|$L=|F|$ into n pieces Fi$F_i$, 1≤i≤n$1\le i\le n$, each of length |Fi|=L/m$|F_i|=L/m$, so that every m pieces suffice for reconstructing F. Dispersal and reconstruction are computationally efficient. The sum of lengths |Fi|$|F_i|$ is (n/m)⋅L$\cdot L$. Since n/m can be chosen to be close to 1, the IDA is space efficient. IDA has numerous applications to secure and reliable storage of information in computer networks and even on single disks, to fault-tolerant and efficient transmission of information in networks, and to communications between processors in parallel computers. Here we also give applications to the problem of data consistency and availability in distributed systems, and to a distributed pattern matching algorithm.

Summary: A new randomized algorithm for the maximum matching problem is presented. Unlike conventional matching algorithms which are combinatorial, our algorithm is algebraic and works on the Tutte matrix of the given raph. Although slower than the best known matching algorith, our algorithm has the advantage of being conceptually simple and easy to program.

Summary: We present randomized algorithms to solve the following string-matching problem and some of its generalizations: Given a string X of length n (the pattern) and a string Y (the text), find the first occurrence of X as a consecutive block within Y. The algorithms represent strings of length n by much shorter strings called fingerprints, and achieve their efficiency by manipulating fingerprints instead of longer strings. The algorithms require a constant number of storage locations, and essentially run in real time. They are conceptually simple and easy to implement. The method readily generalizes to higher-dimensional pattern- matching problems.

The modal system LL considered here has S4-necessity G, T-possibility L and axioms and rules for these connectives as well as implication Gp→∼L∼p$\to \sim L\sim p$ (G is stronger than L). Yet another modal connetive L∗$L^{\ast }$ (iteration of L) is characterised by the axiom L∗p↔p∨LL∗p$L^{\ast }p\leftrightarrow p\vee L{L}^{\ast }p$ and the rule (∼p→∼Lp)/∼p→∼L∗p$\sim p\to \sim Lp)/\sim p\to \sim L^{\ast }p$. Completeness proof and exponential decision algorithm (for the language without L∗)$L^{\ast })$ are given along the familiar lines. L is interpreted as likelihood and it is claimed that the logic might be used in areas such as medical diagnosis where decision making in the presence of uncertainties is crucial. A lot of place is devoted to the proof in the LL of correctness of some aspects of a protocol for exchanging secrets.

The authors give a selection of randomized algorithms in number theory. They are called randomized because some random choices are made in the course of the execution. Usually this means that the run time of the algorithms can become infinitely long. However, the expected run time is finite. Often most executions have a run time that is near the expected value. Randomized algorithms are used when the calculated expected run time, and the observed run time in practice, is shorter than that of deterministic algorithms.
In this paper the authors present a selection of randomized algorithms to find representations of natural numbers as sums of two, three or four squares, or as sums of three triangular numbers. Most of these algorithms are already published at other places. This paper is meant to give an overview of what is available. The authors give expected run times for the algorithms, all of which are polynomial in the logarithm of the number to be represented. In some cases the expected run time is dependent on the truth of some unproven conjectures. In practice the given algorithms are fast. In any case the expected run time is (in the limit) faster than deterministic algorithms performing the same task.

[For the entire collection see Zbl 0564.00027.]
In the present paper we employ the fingerprinting method to solve the following string matching problem. Given a string y we want to find the earliest repetition, i.e. the shortest w and x such that y=wxxz$y=wxxz$. We call this the repetition problem.
We give a very simple algorithm for discovering repetitions by use of fingerprints. If y∈Σ∗$y\in {\mathrm{\Sigma }}^{\ast }$, |Σ|=s$|\mathrm{\Sigma }|=s$, |y|=m$|y|=m$ then the expected running time is O(m log2mlogsm)${}_{2}m{\log }_{s}m)$. But by further use of the power of encoding several operations into one machine-word operation, the running time can be reduced to O(m log2m)${}_{2}m)$, and perhaps even further. An additional feature of this algorithm is its parallelizability. An n≤m$n\le m$ processor machine would produce approximately an n−1$n^{-1}$ reduction in running time. This would produce practical improvements even for small values of n.

Summary: Protocols for implementing contract signing, confidential disclosures, and certified mail in an electronic mail system are proposed. These transactions are provably impossible without a trusted intermediary. However, they can be implemented with just a small probability of a participant cheating his partner, by use of a beacon emitting random integers. Applications include privacy protection of personal information in data banks, as well as the protection of business transactions.

In the paper a new proof is given of some known lower bounds for the computational complexity of arithmetic expressions [cf. D. Yu. G r$r$ i g∘r′ev$g\circ r^{\mathrm{\prime }}ev$, Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 118, 25-82 (1982)]. The proof uses the notion of linear disjointness of subfields of a field and is based on the following theorem: Let the fields E$E$ and K$K$ be linearly disjoint over the ground field F$F$, F⊆K,E⊆Ω$F\subseteq K,E\subseteq \mathrm{\Omega }$. Let d1,∈K,1≤i≤m,1≤j≤p$d_1,\in K,1\le i\le m,1\le j\le p$ be such that the degree of transcendence of D={d1,∣1≤i≤m,1≤j≤p}$D=\left\{d_1,\mid 1\le i\le m,1\le j\le p\right\}$ over F$F$ is t$t$. If π$\pi$ is any straight-line algorithm in (Ω,E∪K)$(\mathrm{\Omega },E\cup K)$ which computes all the m$m$ elements d11+…+d1p,…,d11+…+dmp$d_{11}+\dots +d_{1p},\dots ,d_{11}+\dots +d_{mp}$, then π$\pi$ has at least ⌈t/2⌉$\lceil t/2\rceil$ multiplications/divisions.

In the course of a concurrent computation, processes P1,…$P1,\dots$, Pn must reach a common choice of one out of k$k$ alternatives A1,…,Ak$A_1,\dots ,A_k$. They do this by protocols using k$k$ shared variables, one for each alternative. If the range of the variables has m$m$ values then 12n−−√3≤m$\frac{1}{2}\sqrt[3]{n}\le m$ is necessary, and n+2≤m$n+2\le m$ is sufficient, for deterministic protocols solving the choice coordination problem (C.C.P.). We introduce very simple randomizing protocols which, independently of n$n$, solve the C.C.P. by use of a fixed alphabet. A single-byte (256-valued) alphabet permits a solution with nontermination probability smaller than 2−127$2^{-127}$. Many software and hardware tasks involving concurrency can be interpreted as choice coordination problems. Choice coordination problems occur also in nature.

Let n$\mathrm{n}$ be an integer to be tested for primality and let b$\mathrm{b}$ be an integer such that 1≤b<n$1\le b<n$, and either bn−1≠1(modn)$b^{n-1}\ne 1(modn)$ or 1i$1i$ such that 2i∣(n−1)$2^i\mid (n-1)$ and 1<(b(n−1)/21−1,n)<n$1<\left(b^{(n-1)/2^1}-1,n\right)<n$. Such ab$ab$ is called a witness to the compositeness of n$n$ : If any such witness exists then n$n$ is composite. It is shown that the number of b′s$b^{\mathrm{\prime }}s$ that are not witnesses is at most n+34$\frac{n+3}{4}$ and so if k$k$ independent choices of b$b$ give no witness, then n$n$ is prime with probability >1−4−k$>1-4^{-k}$ asymptotically. It is assumed that if the b’s are chosen randomly then the tests as to whether or not ab$ab$ is a witness are independent. As one would expect, Carmichael numbers give the least proportion of witnesses. As an application, let M=∏1p1$M=\prod _1{p}_1$ : then 338M+821$338M+821$ and 338M+823$338\mathrm{M}+823$ are ”probably” a prime pair (taking k=30$\mathrm{k}=30$ ).

The framework for research in the theory of complexity of computations is described, emphasizing the interrelation between seemingly diverse problems and methods. Illustrative examples of practical and theoretical significance are given. Directions for new research are discussed.

The author constructs an algorithm AL involving a random step r$r$ so that for every instance I of the problem, the expected computation time will be brief. In this approach, the author does not assume any probability distribution and he has applied his approach to find the nearest pair in a set of n$n$ points in Rk$R^k$ and to determine the primality of a number.

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, propositional calculus theorem proving, and analysis of sorting networks. A RAM so implemented we shall call a vector machine.

Lower bounds are established on the computational complexity of the decision problem and on the inherent lengths of proofs for two classical decidable theories of logic: the first-order theory of the real numbers under addition, and Presburger arithmetic - the first-order theory of addition on the natural numbers. There is a fixed constant c>0$c>0$ such that for every (non-deterministic) decision procedure for determining the truth of sentences of real addition and for all sufficiently large n$n$, there is a sentence of length n$n$ for which the decision procedure runs for more than 2cn$2^{\mathrm{c}\mathrm{n}}$ steps. In the case of Presburger arithmetic, the corresponding bound is 22n$2^{2^n}$. These bounds apply also to the minimal lengths of proofs for any complete axiomatization in which the axioms are easily recognized.

In this talk we present some recent striking results concerning inherent exponential and super-exponential computational complexity of certain algorithmic problems in elementary logic. The results apply to situations where theorem proving computer programs were attempted. We present other results, which, though not conclusive, strongly suggest that many of the most basic combinatorial problems are inherently of exponential computational complexity. Since many AI projects involve as essential sub-programs algorithms for problems of the kind proved exponentially complex and hence practically unfeasible, the complexity results point to a need for careful examination of goals and methods in AI. Several possibilities for side-stepping and avoiding these difficulties are outlined.

Übersetzung von Commun. pure appl. Math. 25, 433-458 (1972; Zbl. 226.12002).

From the introduction: We shall state and solve a problem proposed by R. Brent and P. Wolfe concerning the solution of a system of linear equations by algorithms where the only operation permitted on the coefficient vectors a1,a2,…$a_1,a_2,\dots$, is the formation of scalar products ai⋅v$a_i\cdot v$. Each such calculation is called a test. The objective is to solve the equations using a minimum number of tests.
For the entire collection see [Zbl 1467.68010].

It is well known that by calculating beforehand certain auxiliary functions of the coefficients of a polynomial P$P$, every subsequent evaluation of P$P$ can be performed with about half the number of multiplications that would be otherwise required. However, the auxiliary functions involved were obtained from the coefficients of P$P$ by solving high-degreed algebraic equations. Here we show that near optimal results can be obtained by use of rational auxiliary functions. We develop a variety of such rational preparation schemes for a variety of problems.

Übersetzung von Trans. Amer. math. Soc. 141, 1-35 (1969; dies. Zb1. 221.02031).

The author presents a summary of his work on the decidability of second order theories [Trans. Amer. math. Soc. 141, 1-35 (1969; this Zbl. 221.02031)] and on weak definability and special automata [Math. Logic Found. Set Theory, Proc. internat. Colloqu., Jerusalem 1968, 1-23 (1970; this Zbl. 214, 22)]. Open problems and directions for further research are indicated.

Dieser Artikel erschien in dem in diesem Zbl. 223, 02029 angezeigten Sammelwerk. Übersetzung von Israel J. Math. 1, 203-211 (1963; dies. ZbI. 156, 256).

The author continues his highly interesting research [Trans. Amer. math. Soc. 141, 1-35 (1969)] about definability in monadic second-order theories. This paper and its predecessor provide first examples of how automata theory can be applied to solve certain problems in logic. The basic structure studied by the author is N2=⟨T,r0,r1⟩${\mathrm{N}}_2=⟨\mathrm{T},{\mathrm{r}}_0,{\mathrm{r}}_1⟩$, where T$\mathrm{T}$ is the infinite binary tree of all finite words over the alphabet {0,1}$\{0,1\}$, and r0,r1$r_0,r_1$ are the two successor functions, intuitively corresponding to the catenation of the letters 0 and 1. Let L$L$ be the monadic second-order language appropriate for N2${\mathrm{N}}_2$. An n$n$-ary relation H$H$ on the subsets of T$T$ is termed weakly definable if and only if, for some formula F$F$ containing quantifiers only over individual and finite-set varlables The author introduces the notion of a special finite automaton (s.f.a.) on infinite trees and uses it to characterize the weakly definable relations. It turns out that a relation H$\mathrm{H}$ is weakly definable if and only if both H$\mathrm{H}$ and its complement are representable by s.f.a. On the other hand, not every relation representable by s.f.a. is weakly definable. The family of s.f.a. representable relations is closed under union and intersection but not under complementation. A formula F$\mathrm{F}$ is equivalent (in N2${\mathrm{N}}_2$ ) with some formula G$\mathrm{G}$ containing only finite-set quantifiers if and only if F$F$ is equivalent to some prenex formula F1$F_1$ having only existential arbitrary-set quantifiers, and also to some prenex formula F2${\mathrm{F}}_2$ having only universal arbitrary-set quantifiers. As a by-product, the solution of certain decision problems is obtained.