Despite the advancements in large language models (LLMs) for mathematical reasoning, solving competition-level math problems remains a significant challenge, especially for open-source LLMs without external tools. We introduce the MMIQC dataset, comprising a mixture of processed web data and synthetic question-response pairs, aimed at enhancing the mathematical reasoning capabilities of base language models. Models fine-tuned on MMIQC consistently surpass their counterparts in performance on the MATH benchmark across various model sizes. Notably, Qwen-72B-MMIQC achieves a 45.0% accuracy, exceeding the previous open-source state-of-the-art by 8.2% and outperforming the initial version GPT-4 released in 2023. Extensive evaluation results on Hungarian high school finals suggest that such improvement can generalize to unseen data. Our ablation study on MMIQC reveals that a large part of the improvement can be attributed to our novel augmentation method, Iterative Question Composing (IQC), which involves iteratively composing new questions from seed problems using an LLM and applying rejection sampling through another LLM.

Large language models (LLMs) have shown promise in formal theorem proving, but their token-level processing often fails to capture the inherent hierarchical nature of mathematical proofs. We introduce Hierarchical Attention, a regularization method that aligns LLMs’ attention mechanisms with mathematical reasoning structures. Our approach establishes a five-level hierarchy from foundational elements to high-level concepts, ensuring structured information flow in proof generation. Experiments demonstrate that our method improves proof success rates by 2.05% on miniF2F and 1.69% on ProofNet while reducing proof complexity by 23.81% and 16.50% respectively. The code and models will be available.

The synergy between deep learning models and traditional automation tools, such as built-in tactics of the proof assistant and off-the-shelf automated theorem provers, plays a crucial role in developing robust and efficient neural theorem provers~(NTPs). However, for proof synthesis with LLMs, previous work applies automation tools either only when explicitly invoked by the model or at a single granularity level, failing to fully exploit their power. To solve this issue, we propose ProofAug, a procedure that equips LLMs with automation methods at various granularities through fine-grained structure analysis of model-generated proof proposals. ProofAug also serves as a versatile plug-and-play module that seamlessly integrates with any tree-search algorithm, enabling our construction of an efficient recursive proving (ERP) module to further enhance performance. The superiority of our method is validated on the miniF2F benchmark using the open-source deepseek-math-7b-base model and the Isabelle proof assistant. Notably, by additionally employing a mixed prompting strategy, we achieve a cumulative pass rate of 66.0% after curation of the dataset (61.9% for the original version) with 2100 queries to the model per problem (In contrast, the previous SOTA in Isabelle, Subgoal-XL, only achieves 56.1% using 16384 queries per problem). We also implement a Lean 4 version of ProofAug that can improve the pass@1 performance of Kimina-Prover-Preview-Distill-1.5B from 44.3% to 50.4% on miniF2F-test. Our code is available at https://github.com/haoxiongliu/ProofAug.

Scaling language models to handle longer input sequences typically necessitates large key-value (KV) caches, resulting in substantial memory overhead during inference. In this paper, we propose Tensor Product Attention (TPA), a novel attention mechanism that uses tensor decompositions to represent queries, keys, and values compactly, substantially shrinking the KV cache size at inference time. By factorizing these representations into contextual low-rank components and seamlessly integrating with Rotary Position Embedding (RoPE), TPA achieves improved model quality alongside memory efficiency. Based on TPA, we introduce the Tensor ProducT ATTenTion Transformer (T6), a new model architecture for sequence modeling. Through extensive empirical evaluation on language modeling tasks, we demonstrate that T6 surpasses or matches the performance of standard Transformer baselines including Multi-Head Attention (MHA), Multi-Query Attention (MQA), Grouped-Query Attention (GQA), and Multi-Head Latent Attention (MLA) across various metrics, including perplexity and a range of established evaluation benchmarks. Notably, TPA's memory efficiency and computational efficiency at decoding stage enables processing longer sequences under fixed resource constraints, addressing a critical scalability challenge in modern language models. Project Page: https://github.com/tensorgi/TPA.

One of the major open problems in machine learning is to characterize generalization in the overparameterized regime, where most traditional generalization bounds become inconsistent even for overparameterized linear regression. In many scenarios, this failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. This paper demonstrate that the generalization behavior of overparameterized model should be analyzed in a both data-relevant and algorithm-relevant manner. To make a formal characterization, We introduce a notion called data-algorithm compatibility, which considers the generalization behavior of the entire data-dependent training trajectory, instead of traditional last-iterate analysis. We validate our claim by studying the setting of solving overparameterized linear regression with gradient descent. Specifically, we perform a data-dependent trajectory analysis and derive a sufficient condition for compatibility in such a setting. Our theoretical results demonstrate that if we take early stopping iterates into consideration, generalization can hold with significantly weaker restrictions on the problem instance than the previous last-iterate analysis.

In the Bitcoin system, miners are incentivized to join the system and validate transactions through fees paid by the users. A simple "pay your bid" auction has been employed to determine the transaction fees. Recently, Lavi, Sattath and Zohar [LSZ17] proposed an alternative fee design, called the monopolistic price (MP) mechanism, aimed at improving the revenue for the miners. Although MP is not strictly incentive compatible (IC), they studied how close to IC the mechanism is for iid distributions, and conjectured that it is nearly IC asymptotically based on extensive simulations and some analysis. In this paper, we prove that the MP mechanism is nearly incentive compatible for any iid distribution as the number of users grows large. This holds true with respect to other attacks such as splitting bids. We also prove a conjecture in [LSZ17] that MP dominates the RSOP auction in revenue (originally defined in Goldberg et al. [GHKSW06] for digital goods). These results lend support to MP as a Bitcoin fee design candidate. Additionally, we explore some possible intrinsic correlations between incentive compatibility and revenue in general.

We address two related unanswered questions in maximum revenue multi-item auctions. Is dominant-strategy implementation equivalent to the semantically less stringent Bayesian one (as in the case of Myerson's 1-item auction)? Can one find explicit solutions for non-trivial families of multi-item auctions (as in the 1-item case)? In this paper, we present such natural families whose explicit solutions exhibit a revenue gap between the two implementations. More precisely, consider the k-item n-buyer maximum revenue auction where k, n >1 with additive valuation in the independent setting (i.e., the buyers i have independent private distributions Fij on items j). We derive exact formulas for the maximum revenue when k=2 and Fij are any IID distributions on support of size 2, for both the dominant-strategy (DIC) and the Bayesian (BIC) implementations. The formulas lead to the simple characterization that, the two models have identical maximum revenue if and only if selling-separately is optimal for the distribution. Our results also give the first demonstration, in this setting, of revenue gaps between the two models. For instance, if k=n=2 and Pr{X{F = 1} = Pr{XF =2 } = 1/2, then the maximum revenue in the Bayesian implementation exceeds that in the dominant-strategy by exactly 2%; the same gap exists for the continuous uniform distribution XF over [a, a+1] ∪ [2a, 2a+1] for all large a.

In this paper, we introduce a novel approach for reducing the k-item n-bidder auction with additive valuation to k-item 1-bidder auctions. This approach, called the Best-Guess reduction, can be applied to address several central questions in optimal revenue auction theory such as the relative strength of simple versus complex mechanisms, the power of randomization, and Bayesian versus dominant-strategy implementations. First, when the items have independent valuation distributions, we present a deterministic mechanism called Deterministic Best-Guess that yields at least a constant fraction of the optimal revenue by any randomized mechanism. This also gives the first simple mechanism that achieves constant fraction optimal revenue for such multi-buyer multi-item auctions. Second, if all the nk valuation random variables are independent, the optimal revenue achievable in dominant strategy incentive compatibility (DSIC) is shown to be at least a constant fraction of that achievable in Bayesian incentive compatibility (BIC). Third, when all the nk values are identically distributed according to a common one-dimensional distribution F, the optimal revenue is shown to be expressible in the closed form Θ(k(r+ ∫mr0 (1 – F(x)n)dx)) where r = supx≥0 x(1 – F(x)n) and m = [k/n]; this revenue is achievable by a simple mechanism called 2nd-Price Bundling. All our results apply to arbitrary distributions, regular or irregular.

Key-exchange, in particular Diffie-Hellman key-exchange (DHKE), is among the core cryptographic mechanisms for ensuring network security. For key-exchange over the Internet, both security and privacy are desired. In this paper, we develop a family of privacy-preserving authenticated DHKE protocols named deniable Internet key-exchange (DIKE), both in the traditional PKI setting and in the identity-based setting. The newly developed DIKE protocols are of conceptual clarity and practical (online) efficiency. They provide useful privacy protection to both protocol participants, and add novelty and new value to the IKE standard. To the best of our knowledge, our protocols are the first provably secure DHKE protocols that additionally enjoy all the following privacy protection advantages: 1) forward deniability, actually concurrent non-malleable statistical zero-knowledge, for both protocol participants simultaneously; 2) the session transcript and session-key can be generated merely from DH-exponents (together with some public values), which thus cannot be traced to the pair of protocol participants; and 3) exchanged messages do not bear peer's identity, and do not explicitly bear player role information.

Cryptographic algorithm standards play an important role both to the practice of information security and to cryptography theory research. Among them, the KEA and OPACITY (KEA/OPACITY, in short) protocols, and the MQV and HMQV ((H)MQV, in short) protocols, are a family of implicitly authenticated Diffie-Hellman key-exchange (IA-DHKE) protocols that are among the most efficient authenticated key-exchange protocols known and are widely standardized. In this work, from some new design insights, we develop a new family of practical IA-DHKE protocols, referred to as OAKE (standing for "optimal authenticated key-exchange" in brief). We show that the OAKE protocol family combines, in essence, the advantages of both (H)MQV and KEA/OPACITY, while saving from or alleviating the disadvantages of them both.

When digital signature is applied on low-power devices, like smart cards, wireless sensors and RFID tags, some specific properties, e.g., better offline storage, more modular and flexible deployment, are desired. To meet these needs, a new variant of the Fiat-Shamir transformation for digital signatures, referred to as Γ -transformation, is introduced and formalized in this work. Following this new transformation approach, some new signature schemes (referred to as Γ-signatures) are presented and discussed. In particular, it is shown that the Γ-signatures for discrete logarithm problem (DLP) developed in this work combine, in essence, the advantages of both Schnorr's signature and the digital signature standard (DSS), while saving from the disadvantages of them both.

In this paper we study (interpret) the precise composability guarantee of the generalised universal composability (GUC) feasibility with global setups that was proposed in the recent paper Canetti et al. (2007) from the point of view of full universal composability (FUC), that is, composability with arbitrary protocols, which was the original security goal and motivation for UC. By observing a counter-intuitive phenomenon, we note that the GUC feasibility implicitly assumes that the adversary has limited access to arbitrary external protocols. We then clarify a general principle for achieving FUC security, and propose some approaches for fixing the GUC feasibility under the general principle. Finally, we discuss the relationship between GUC and FUC from both technical and philosophical points of view. This should be helpful in gaining a precise understanding of the GUC feasibility, and for preventing potential misinterpretations and/or misuses in practice.

A central question in quantum information theory and computational complexity is how powerful nonlocal strategies are in cooperative games with imperfect information, such as multi-prover interactive proof systems. This paper develops a new method for proving limits of nonlocal strategies that make use of prior entanglement among players (or, provers, in the terminology of multi-prover interactive proofs). Instead of proving the limits for usual isolated provers who initially share entanglement, this paper proves the limits for "commuting-operator provers", who share private space, but can apply only such operators that are commutative with any operator applied by other provers. Obviously, these commuting-operator provers are at least as powerful as usual isolated but prior-entangled provers, and thus, limits in the model with commuting-operator provers immediately give limits in the usual model with prior-entangled provers. Using this method, we obtain an n-party generalization of the Tsirelson bound for the Clauser-Horne-Shimony-Holt inequality, for every n. Our bounds are tight in the sense that, in every n-party case, the equality is achievable by a usual nonlocal strategy with prior entanglement. We also apply our method to a three-prover one-round binary interactive proof system for NEXP. Combined with the technique developed by Kempe, Kobayashi, Matsumoto, Toner and Vidick to analyze the soundness of the proof system, it is proved to be NP-hard to distinguish whether the entangled value of a three-prover one-round binary-answer game is equal to one or at most 1-1/p(n) for some polynomial p, where n is the number of questions. This is in contrast to the two-prover one-round binary-answer case, where the corresponding problem is efficiently decidable. Alternatively, NEXP has a three-prover one-round binary interactive proof system with perfect completeness and soundness 1 middot 2-poly.

The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d ges 5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2is Omega(nfrac12 - delta), and that for the 3-dimensional grid [n]3is Omega(n1 - delta), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (2004) (based on Ambainis' adversary method (2003) for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemeridi (1965), Bose and Chowla (1962-63), and Halasz (1977) from combinatorial number theory, as well as less familiar probability tools like Esseen's inequality

Summary form only given,as follows. In past decades, the theory of computational complexity has fl ourished in terms of both the revelation of its internal structures and the unfolding of its numerous applications. In this talk we discuss several persistent and interwoven themes underlying many of these accomplishments. In particular we shall focus on the interplay between communication and computation which has a key role in these developments. We also speculate on promising future directions in the study of computational and communication complexity.

In decision tree models, considerable attention has been paid on the effect of symmetry on computational complexity. That is, for a permutation group /spl Gamma/, how low can the complexity be for any Boolean function invariant under /spl Gamma/? In this paper, we investigate this question for quantum decision trees for graph properties, directed graph properties, and circular functions. In particular, we prove that the n-vertex Scorpion graph property has quantum query complexity /spl Theta//sup /spl tilde// (n/sup 1/2/), which implies that the minimum quantum complexity for graph properties is strictly less than that for monotone graph properties (known to be /spl Omega/(n/sup 2/3/)). A directed graph property, SINK, is also shown to have the /spl Theta//sup /spl tilde//(n/sup 1/2/) quantum query complexity. Furthermore, we give an N-ary circular function which has the quantum query complexity /spl Theta/ /sup /spl tilde//(N/sup 1/4/). Finally, we show that for any permutation group /spl Gamma/, as long as /spl Gamma/ is transitive, the quantum query complexity of any function invariant to /spl Gamma/ is at least /spl Omega/(N/sup 1/4/), which implies that our examples are (almost) the best ones in the sense of pinning down the complexity for the corresponding permutation group.

Let P = (X, < P) be a partial order on a set of n elements X = x1, x2,..., xn. Define the quantum sorting problem QSORTP as: given n distinct numbers x1, x2,..., xn consistent with P, sort them by a quantum decision tree using comparisons of the form "xi: xj". Let Qε(P) be the minimum number of queries used by any quantum decision tree for solving QSORTP with error less than ε (where 0 < ε < 1/10 is fixed). It was proved by Hoyer, Neerbek and Shi (Algorithmica 34 (2002), 429--448) that, when P0 is the empty partial order, Qε(P0) ≥ Ω (n log n), i. e., the classical information lower bound holds for quantum decision trees when the input permutations are unrestricted.In this paper we show that the classical information lower bound holds, up to an additive linear term, for quantum decision trees for any partial order P. Precisely, we prove Qε(P) ≥ c log2 e(P)-c'n where c,c' > 0 are constants and e(P) is the number of linear orderings consistent with P. Our proof builds on an interesting connection between sorting and Korner's graph entropy that was first noted and developed by Kahn and Kim (JCSS 51(1995), 390--399).

In the simultaneous message model, two parties holding n-bit integers x,y send messages to a third party, the referee, enabling him to compute a boolean function f(x,y). Buhrman et al [3] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short "quantum fingerprints" sent by the two parties, i.e., there exists a quantum protocol using only O(log n) bits. This is in contrast to the well-known classical case for which Ω(n1/2) bits are provably necessary for the same problem even with randomization. In this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. Let R<??par line>,pub(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). We prove that, if R<??par line>,pub(f)=O(1), then there exists a quantum protocol for f using only O(log n) bits. As an application we show that O(log n) quantum bits suffice for the bounded Hamming distance function, defined by f(x,y)=1 if and only if x and y have a constant Hamming distance d or less.

Would physical laws permit the construction of computing machines that are capable of solving some problems much faster than the standard computational model? Recent evidence suggests that this might be the case in the quantum world. But the question is of great interest even in the realm of classical physics. In this article, we observe that there is fundamental tension between the Extended Church--Turing Thesis and the existence of numerous seemingly intractable computational problems arising from classical physics. Efforts to resolve this incompatibility could both advance our knowledge of the theory of computation, as well as serve the needs of scientific computing.

Given m copies of the same problem, does it take m times the amount of resources to solve these m problems? This is the direct sum problem, a fundamental question that has been studied in many computational models. We study this question in the simultaneous message (SM) model of communication introduced by A.C. Yao (1979). The equality problem for n-bit strings is well known to have SM complexity /spl Theta/(/spl radic/n). We prove that solving m copies of the problem has complexity /spl Omega/(m/spl radic/n); the best lower bound provable using previously known techniques is /spl Omega/(/spl radic/(mn)). We also prove similar lower bounds on certain Boolean combinations of multiple copies of the equality function. These results can be generalized to a broader class of functions. We introduce a new notion of informational complexity which is related to SM complexity and has nice direct sum properties. This notion is used as a tool to prove the above results; it appears to be quite powerful and may be of independent interest.

In past decades, the theory of computational complexity has flourished in terms of both the revelation of its internal structures and the unfolding of its numerous applications. In this paper we discuss several persistent and interwoven themes underlying many of these accomplishments. Chief among them are the interplay between communication and computation, the power of problem reduction, and the increasingly prominent role played by classical mathematics. We will also speculate on a few promising directions for future development of computational complexity.

Article Free Access Share on Quantum bit escrow Authors: Dorit Aharonov University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Amnon Ta-Shma University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Umesh V. Vazirani University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Andrew C. Yao Princeton University, Princeton, NJ Princeton University, Princeton, NJView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 705–714https://doi.org/10.1145/335305.335404Published:01 May 2000Publication History 46citation619DownloadsMetricsTotal Citations46Total Downloads619Last 12 Months56Last 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

Quantum key distribution, first proposed by C.H. Bennett and G. Brassard (1984), provides a possible key distribution scheme whose security depends only on the quantum laws of physics. So far the protocol has been proved secure even under channel noise and detector faults of the receiver but is vulnerable if the photon source used is imperfect. In this paper we propose and give a concrete design for a new concept, self-checking source, which requires the manufacturer of the photon source to provide certain tests; these tests are designed such that, if passed, the source is guaranteed to be adequate for the security of the quantum key distribution protocol, even though the testing devices may not be built to the original specification. The main mathematical result is a structural theorem which states that, for any state in a Hilbert space, if certain EPR-type equations are satisfied, the state must be essentially the orthogonal sum of EPR pairs.

This paper describes a randomized approach for finding invari-ants in a set of flexible ligands (drug molecules) that underlies an integrated software system called RAPID currently under development. An invariant is a collection of features embed-ded in <3 which is present in one or more of the possible low-energy conformations of each ligand. Such invariants of chemically distinct molecules are useful for computational chemists since they may represent candidate pharmacophores. A pharmacophore contains the parts of the ligand that are pri-marily responsible for its interaction and binding with a specific receptor. It is regarded as an inverse image of a receptor and is used as a template for building more effective pharmaceutical drugs. The identification of pharmacophores is crucial in drug design since the structure of the targeted receptor is frequently unknown, but a number of molecules that interact with the receptor have been discovered by experiments. It is expected that our techniques and the results produced by our system will prove useful in other applications such as molecular database screening and comparative molecular field analysis.

This paper describes a randomized approach for finding invariant in a set of flexible Iigands (drug molecules) that underlies an integrated software system called RAPID currently underdevelopment.An invariant is a collection of features embedded in 3?3 which is present in one or more of the possible low-energy conformations of each Iigand.Such invariants of chemically distinct molecules are useful for computational chemists since they may represent candidate pharmacophores.A pharmacophore contains the parts of the Iigand that are primarily responsible for its interaction and binding with a specific receptor.It is regarded as an inverse image of a receptor and is used as a template for building more effective pharmaceutical drugs.The identification of pharmacophores is crucial in drug design since the structure of the targeted receptor is frequently unknown, but a number of molecules that interact with the receptor have been discovered by experiments.It is expected that our techniques and the results produced by our system will prove useful in other applications such as molecular database screening and comparative molecular field analysis.

We investigate read-once branching programs for the following search problem: given a Boolean m n matrix with m>n, nd either an all-zero row, or two 1's in some column. Our primary motivation is that this models regular resolution proofs of the pigeonhole principle PHP m n, and that for m>n 2 no lower bounds are known for the length of such proofs. We prove exponential lower bounds (for arbitrarily large m!) if we further restrict this model by requiring the branching program either

The goal of quantum cryptography is to design cryptographic protocols whose security depends on quantum physics and little else. A serious obstacle to security proofs is the cheaters' ability to make coherent measurements on the joint properties of large composite states. With the exception of commit protocols, no cryptographic primitives have been proved secure when coherent measurements are allowed. In this paper we develop some mathematical techniques for analyzing probabilistic events in Hilbert spaces, and prove the security of a canonical quantum oblivious transfer protocol against coherent measurements. 1 Introduction Work on quantum cryptography was started by Wiesner [Wi70] twenty-five years ago. Much knowledge on how to exploit quantum physics for cryptographic purposes has been gained through the work of Bennet and Brassard ([BBBW83][BB84][BBBSS92]), and later Cr'epeau ([Cr90][BC91][BBCS92][Cr94]). Furthermore, prototypes for implementing some of these This research was...

Let $\rho$ be a set of algebraic expressions constructed with radicals and arithmetic operations, and which generate the splitting field F of some polynomial. Let $N_{\beta}(\rho)$ be the minimum total number of root-takings and exponentiations used in any straightline program for computing the functions in $\rho$ by taking roots, exponentials, logarithms, and performing arithmetic operations. In this paper it is proved that $N_{\beta}(\rho) = v(G)$, where $v(G)$ is the minimum length of any cyclic Jordan-Hölder tower for the Galois group G of F. This generalizes a result of Ja’Ja’ [Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, 1981, pp. 95–100], and shows that the inclusion of certain new primitives, such as taking exponentials and logarithms, does not improve the cost of computing such expressions as compared with programs that use only root-takings.

We show that any monotone circuit for computing graph connectivity must have a depth greater than /spl Omega/((log n)/sup 3/2// log log n). This proves that UCONN/sub n/ is not in monotone NC/sup 1/. The proof technique, which is an adaptation of Razborov's approximation method, is also used to derive lower bounds for a general class of graph problems.>

We show that any algebraic computation tree or any fixed-degree algebraic tree for solving the membership question of a compact set S ~R" must have height greater than Cl(log(@i(S))) -cn for each i, where pi(S) is the i-th Betti number.This generalizes a well-known result by Ben-Or [Be83] who proved this lower bound for the case i = O, and a recent result by Bjorner and Lovtisz [BL92] who proved this lower bound for all i for linear decision trees.

It was conjectured in Borodin et al. [J. Comput. System Sci., 22 (1981), pp. 351–364] that to solve the element distinctness problem requires $TS = \Omega (n^2 )$ on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since $TS = O((n\log n)^2 )$ is achievable. Recently, Borodin et al. [SIAM J. Comput.,16 (1987), pp. 97–99] showed that $TS = \Omega (n^{{3 / 2}} (\log n)^{{1 / 2}} )$. This paper presents a near-optimal tradeoff $TS = \Omega (n^{2 - \epsilon (n)} )$, where $ \epsilon (n) = O({1 / {(\log n)^{{1 / 2}} }})$.

We propose a complexity model of quantum circuits analogous to the standard (acyclic) Boolean circuit model. It is shown that any function computable in polynomial time by a quantum Turing machine has a polynomial-size quantum circuit. This result also enables us to construct a universal quantum computer which can simulate, with a polynomial factor slowdown, a broader class of quantum machines than that considered by E. Bernstein and U. Vazirani (1993), thus answering an open question raised by them. We also develop a theory of quantum communication complexity, and use it as a tool to prove that the majority function does not have a linear-size quantum formula.>

For any set S contained in R/sup n/, let chi (S) denote its Euler characteristic. The author shows that any algebraic computation tree or fixed-degree algebraic decision tree must have height Omega (log mod chi (S) mod )for deciding the membership question of a compact semi-algebraic set S. This extends a result by A. Bjorner, L. Lovasz and A. Yao where it was shown that any linear decision tree for deciding the membership question of a closed polyhedron S must have height greater than or equal to log/sub 3/ mod chi (S) mod .>

Article Free Access Share on Linear decision trees: volume estimates and topological bounds Authors: Anders Björner Royal Institute of Technology, Stockholm, Sweden S-100 44 Royal Institute of Technology, Stockholm, Sweden S-100 44View Profile , László Lovász Eötvös Loránd University, Budapest, Hungary H-1088, Princeton University, Princeton, NJ Eötvös Loránd University, Budapest, Hungary H-1088, Princeton University, Princeton, NJView Profile , Andrew C. C. Yao Princeton University, Princeton, NJ Princeton University, Princeton, NJView Profile Authors Info & Claims STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of ComputingJuly 1992 Pages 170–177https://doi.org/10.1145/129712.129730Published:01 July 1992Publication History 41citation642DownloadsMetricsTotal Citations41Total Downloads642Last 12 Months28Last 6 weeks4 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 $W \subseteq R^n $ be scale-invariant and rationally dispersed, i.e., $\tilde x \in W$ implies $\lambda \tilde x \in W$ for all real $\lambda > 0$; and the rationale are dense in both W and $R^n - W$. It is shown that, in the algebraic computation tree model, the problem of deciding whether an input $\tilde x \in R^n $ with integer coordinates is a member of W has complexity $\Omega (\log _2 \hat \beta (W) - 2n)$, where $\hat \beta (W)$ is the number of connected components of W that are not of measure 0. This theorem can be used to prove tight lower bounds for the integral-constrained form of many basic problems, such as Element Distinctness, Set Disjointness, Finding Convex Hull, etc. Through further transformations, it leads to lower bounds for problems such as Integer Max Gap and Closest Pair of a simple polygon. The proof involves a nontrivial extension of the Milnor–Thorn techniques for finding upper bounds on the Betti numbers of algebraic varieties.

It is proved that any language in ACC can be approximately computed by two-level circuits of size 2 raised to the (log n)/sup k/ power, with a symmetric-function gate at the top and only AND gates on the first level. This implies that any language in ACC can be recognized by depth-3 threshold circuits of that size. This result gives the first nontrivial upper bound on the computing power of ACC circuits.>

to program checking and other subjects.Unctions whose value at one point can be interpolated from values at other points have occupied a special place in cryptography.In this paper we will develop a general concept of "coherence" to capture this property and show its applications to several models of program checking.The concept and techniques also have applications in Hellman's timememory tradeoff for inverting random functions.

A proof is given of a general theorem showing that for certain sets W a certain topological lower bound is valid in the algebraic computation tree model, even if the inputs are restricted to be integers. The theorem can be used to prove tight lower bounds for the integral-constrained form of many basic problems, such as element distinctness, set disjointness, and finding the convex hull. Through further transformations it leads to lower bounds for problems such as the integer max gap and closest pair of a simple polygon. The proof involves a nontrivial extension of the Milnor-Thom techniques for finding upper bounds on the Betti numbers of algebraic varieties.>

It is well known that for the Byzantine Generals Problem, no deterministic protocol can exist for an n-processor system if the number t of faulty processors is allowed to be as large as n/3. In this paper we investigate the maximum achievable agreement probability Βn,t in a model in which the faulty processors can be as devious and powerful as possible. We also discuss a restricted model with Βn,t denoting the corresponding maximum achievable probability. We will prove that: (i) for n = 3, t = 1 (the first nontrivial case), Β3,1 = (√5 - 1)/2 (the reciprocal of the golden ratio); (ii) for all ε with 0 < ε < 1, if t/n > 1 - log (1 -ε)1/2/ log (1 - (1 -ε)1/2) then Βtn,t < ε

This paper contains two parts. In Part I, we show that polynomial-size monotone threshold circuits of depth k form a proper hierarchy in parameter k. This implies in particular that monotone TC0 is properly contained in NC1. In Part II, we introduce a new concept, called local function, which tries to characterize when a function can be efficiently computed using only localized processing elements. It serves as a unifying framework for viewing related and sometimes apparently unrelated results. In particular, it will be demonstrated that the recent results on lower bounds for monotone circuits by Razborov [Ra1] and Karchmer and Wigderson [KW], as well as a main theorem in Part I of this paper, can be regarded as proving certain functions to be nonlocal. We will also suggest an approach based on locality for attacking the conjecture that (nonmonotone) TC0 is properly contained in NC1.

Let $P = ( < _P ,Y)$ be a partial order on a set $Y = \{ y_1 ,y_2 , \cdots ,y_n \} $ of n elements. The problem of P-production is as follows: Given an input of n distinct numbers $Y = x_1 ,x_2 , \cdots ,x_n $, find a permutation $\sigma $ of $(1,2, \cdots ,n)$ such that $y_i < _P y_j $ implies $x_{\sigma (i)} < x_{\sigma (j)} $. Let $C(P),\bar C(P)$ be, respectively, the minimum number and the minimum average number of binary comparisons $x_i :x_j $ needed by any decision-tree algorithm to produce P. It is proved that $C(P) = \Theta (\bar C(P))$. As an intermediate result, it is shown that $C(P) = O(\log _2 ({{n!} / {\mu (P)}}) + n)$, where $\mu (P)$ is the number of permutations consistent with P, thus proving a conjecture of Saks.

It was conjectured by A. Borodin et al. that to solve the element distinctness problem requires TS= Omega (n/sup 2/) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS=O(n/sup 2/ log n) is achievable. They showed recently (1987) that TS= Omega (n/sup 3/2/(log n)/sup 1/2/). The author shows a near-optimal tradeoff TS= Omega (n/sup 2- epsilon (n)/), where epsilon (n)=O(1/(log n)/sup 1/2/).>

A Boolean function P from $\{ {0,1} \}^\prime $ into $\{ {0,1} \}$ is said to be evasive, if every decision-tree algorithm for evaluating P must examine all t arguments in the worst case. It was known that any nontrivial monotone bipartite graph property on vertex set $V \times W$ must be evasive, when $|V| \cdot |W|$ is a power of a prime number. In this paper, we prove that every nontrivial monotone bipartite graph property is evasive.

For any property P on n-vertex graphs, let C(P) be the minimum number of edges that need to be examined by any decision tree algorithm for determining P. In 1975 Rivest and Vuillemin settled the Aanderra-Rosenberg Conjecture, proving that C(P) = Ω(n2) for every nontrivial monotone graph property P. An intriguing open question is whether the theorem remains true when randomized algorithms are allowed. In this paper we report progress on this problem, showing that Ω(n(log n)1/12) edges must be examined by a randomized algorithm for determining any nontrivial monotone graph property.

In this paper we introduce a new tool for controlling the knowledge transfer process in cryptographic protocol design. It is applied to solve a general class of problems which include most of the two-party cryptographic problems in the literature. Specifically, we show how two parties A and B can interactively generate a random integer N = p·q such that its secret, i.e., the prime factors (p, q), is hidden from either party individually but is recoverable jointly if desired. This can be utilized to give a protocol for two parties with private values i and j to compute any polynomially computable functions f(i,j) and g(i,j) with minimal knowledge transfer and a strong fairness property. As a special case, A and B can exchange a pair of secrets sA, sB, e.g. the factorization of an integer and a Hamiltonian circuit in a graph, in such a way that sA becomes computable by B when and only when sB becomes computable by A. All these results are proved assuming only that the problem of factoring large intergers is computationally intractable.

We present exponential lower bounds on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct, i.e., ΣkP,A is properly contained in Σk+1P,A for all k.

It is shown that any bounded region in Ed can be divided into 2d subregions of equal volume in such a way that no hyperplane in Ed can intersect all 2d of the subregions. This theorem provides the basis of a data structure scheme for organizing n points in d dimensions. Under this scheme, a broad class of geometric queries in d dimensions, including many common problems in range search and optimization, can be solved in linear storage space and sublinear time.

It was conjectured by J. Ullman that uniform hashing is optimal in its expected retrieval cost among all open-address hashing schemes [4]. In this paper, we show that, for any open-address hashing scheme, the expected cost of retrieving a record from a large table that is α-fraction full is at least (1/α) log (1/(1 - α)) + o (1). This proves Ullman's conjecture to be true in the asymptotic sense.

We consider the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An $O(n)$ expected running time is proved for the execution of a random equivalence program in the Spanning Tree Model.

Let $F = \{ ({\bf r}_i ,s_i )|0 \leqq i < n\} $ be a file of n records, where ${\bf r}_i $ are d-dimensional vectors and $s_i $ are elements of a commutative semigroup S. We are interested in the partial sum problem, in which queries of the form “$\sum_{r_i \leqq {\bf a}} {s_i = ?} $” are to be answered. A space-time tradeoff $t = \Omega (\log n/\log (m\log n/ n)$ is established for storing a static two-dimensional file. It will also be shown that, for the one-dimensional problem, any dynamic algorithm must have a worst-case time $\Omega (n\log n/\log \log n)$ in processing a sequence $O(n)$ INSERT and QUERY instructions.

The study of constructing reliable systems from unreliable components goes back to the work of von Neumann, and of Moore and Shannon. The present paper studies the use of redundancy to enhance reliability for sorting and related networks built from unreliable comparators. Two models of fault-tolerant networks are discussed. The first model patterns after the concept of error-correcting codes in information theory, and the other follows the stochastic criterion used by von Neumann and Moore–Shannon. It is shown, for example, that an additional $k(2n - 3)$ comparators are sufficient to render a sorting network reliable, provided that no more than k of its comparators may be faulty.

The purpose of this paper is to resolve several open problems in the current literature on Boolean circuits, communication complexity, and hashing functions. These lower bound results share the common feature that their proofs utilize probabilistic arguments in an essential way. Specifically, we prove that, to compute the majority function of n Boolean variables, the size of any depth-3 monotone circuit must be greater than 2nε, and the size of any width-2 branching program must have super-polynomial growth. We also show that, for the problem of deciding whether i ≤ j for two n-bit integers i and j, the probabilistic ε-error one-way communication complexity is of order θ(n), while the two-way ε-error complexity is O((log n)2). We will also prove that, to compute i · j mod p for an n-bit prime p, the probabilistic ε-error two-way communication complexity is of order θ(n). Finally, we prove a conjecture of Ullman that uniform hashing is asymptotically optimal in its expected retrieval cost among open address hashing schemes.

The notion of digital signature based on trapdoor functions has been introduced by Diffie and Hellman[3]. Rivest, Shamir and Adleman[8] gave the first number theoretic implementation of a signature scheme based on a trapdoor function. If f is a trapdoor function and m a message, f−1(m) is the signature of m. The signature can be verified by computing f(f−1(m)) = m. This approach presents the following problems even when f is hard to invert: 1) there may be special message spaces (or subsets of them) that are easy to sign without knowing the trapdoor information 2) it is possible to forge the signature of random numbers; this violates the requirements of many protocols 3) given a polynomial number of signed messages, it may be possible to sign a new one without knowing the trapdoor information. We solve the above problems by exhibiting two signature schemes for which any strategy of an adversary, who has seen all previously signed messages, that has a moderate success in forging even a single additional signature, is transformable to a fast algorithm for factoring or inverting the RSA function. This provably holds for all message spaces with all possible Probability distributions. Thus, in particular, given the signature of m, forging the signature of m+1 or 2m or 2sm is as hard as factoring. The two signature schemes

Recently the use of public key encryption to provide secure network communication has received considerable attention. Such public key systems are usually effective against passive eavesdroppers, who merely tap the lines and try to decipher the message. It has been pointed out, however, that an improperly designed protocol could be vulnerable to an active saboteur, one who may impersonate another user or alter the message being transmitted. Several models are formulated in which the security of protocols can be discussed precisely. Algorithms and characterizations that can be used to determine protocol security in these models are given.

The purpose of this paper is to introduce a new information theory and explore its appplications. Using modern computational complexity, we study the notion of information that can be accessed through a feasible computation. In Part 1 of this paper, we lay the foundation of the theory and set up a framework for cryptography and pseudorandom number generation. In Part 2, we study the concept of trapdoor functions and examine applications of such functions in cryptography, pseudorandom number generation, and abstract complexity theory.

The author investigates the following problem: Suppose m people wish to compute the value of a function f(x1, x2, x3, ..., xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x's. Is it possible for them to compute the value of f, by communicating among themselves, without unduly giving away any information about the values of their own variables? The author gives a precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc.. He also discusses the complexity question "How many bits need to be exchanged for the computation," and describes methods to prevent participants from cheating. Finally, he studies the question "What cannot be accomplished with one-way functions."

In this paper, we raise and investigate the question of (storage) space- (retrieval) time tradeoff for a static database, in the general framework of Fredman's. As will be seen, such tradeoff results also lead to lower bounds on the complexity of processing a sequence of m INSERT and QUERY instructions. The latter results are incomparable to Fredman's, since the presence of DELETE instructions was crucial for his proof technique. We will present our results in detail in the next few sections. Here we will only mention three main conclusions. Firstly, circular query is shown to be intrinsically hard in the sense that, for some static database with n records, there is a space-time tradeoff TS > n1 + ε where ε>0; in contrast, orthogonal query can always be implemented with space S=0(n(log n)k) and time T=0((log n)k) for fixed k. Furthermore, any algorithm for processing 0(n) INSERT and QUERY instructions must use time Ω(n1+ε) in the worst case. Secondly, for the “interval” query, we have determined the space-time tradeoff quite precisely to be T @@@@ α(S,n), where α is the inverse to an Ackermann's function first defined by Tarjan [9]. This is a rare case where the function α arises outside the context of path compression, and is obtained through a totally independent derivation. Thirdly, we prove that, for the interval query, any algorithm to process a sequence of 0(n) INSERT and QUERY must take time Ω((n log n)/(log log n)) in the worst case. This means that one cannot hope to maintain the most efficient static data structure (with retrieval time α(S,n)) in the dynamic case.

The complexity of solwng the knapsack problem with n input real numbers on a parallel computer wRh real arithmeUc and branching operations is considered A trine-processor trade-off constraint ts derived; m particular, it ts shown that an exponential number of processors have to be used if the problem is to be solved m time t _< ~n/2.

Given a function f over a finite domain D and an arbitrary starting point x, the sequence $f^0 (x),f^1 (x),f^2 (x), \cdots $ is ultimately periodic. Such sequences are typically the output of random number generators. The cycle problem is to determine the first repeated element $f^n (x)$ in the sequence. Previous algorithms for this problem have required $3n + O(1)$ operations. In this paper we show that $n(1 + \Theta (1/\sqrt M ))$ steps are both necessary and sufficient, if M memory cells are available to store values of the function. We explicitly consider the performance of the algorithm as a function of the amount of memory available and the relative cost of evaluating f and comparing sequence elements for equality.

The problem of finding a minimum spanning tree connecting n points in a k-dimensional space is discussed under three common distance metrics: Euclidean, rectilinear, and $L_\infty $. By employing a subroutine that solves the post office problem, we show that, for fixed $k \geqq 3$, such a minimum spanning tree can be found in time $O(n^{2 - a(k)} (\log n)^{1 - a(k)} )$, where $a(k) = 2^{ - (k + 1)} $, The bound can be improved to $O((n\log n)^{1.8} )$ for points in 3-dimensional Euclidean space. We also obtain $o(n^2 )$ algorithms for finding a farthest pair in a set of n points and for other related problems.

Let $\bar V_k (n)$ be the minimum average number of pairwise comparisons needed to find the kth largest of n numbers $(k \geqq 2)$, assuming that all $n!$ orderings are equally likely. D. W. Matula proved that, for some absolute constant c, $\bar V_k (n) - n \leqq ck\ln \ln n$ as $n \to \infty $. In the present paper, we show that there exists an absolute constant $c' > 0$ such that $\bar V_k (n) - n \geqq c'k\ln \ln n$ as $n \to \infty $, proving a conjecture of Matula.

Recently the use of public key encryption to provide secure network communication has received considerable attention. Such public key systems are usually effective against passive eavesdroppers, who merely tap the lines and try to decipher the message. It has been pointed out, however, that an improperly designed protocol could be vulnerable to an active saboteur, one who may impersonate another user or alter the message being transmitted. Several models are formulated in which the security of protocols can be discussed precisely. Algorithms and characteri-zations that can be used to determine protocol security in these models are given.

We are interested in the complexity of solving the knapsack problem with n input real numbers on a parallel computer with real arithmetic and branching operations. A processor-time tradeoff constraint is derived; in particular, it is shown that an exponential number of processors have to be used if the problem is to be solved in time t ≤ @@@@n/2.

In this paper we will explore the limitations imposed by entropic constraints, both in generality and for specific problems. We list below the main questions that we will address.

Optmaahty questions are examined m the following information retrieval problem.Given a set S of n keys, store them so that queries of the form, "Is x E S?" can be answered quickly It is shown that m a rather general model including all the commonly used schemes, [lg(n + I)] probes to the table are needed m the worst case, prowded the key space is sufficiently large The effects of smaller key space and arbitrary encoding are also explored KEY WORDS AND PHRASES mformaUon retrieval, lower bound, optmaahty, query, Ramsey's theorem, search strategy, sorted table

Gwen a set S of n distinct points {(x,, y,)[O _< l < n }, the convex hull problem is to determine the vertices of the convex hull H(S).All the known algorithms for solving this problem have a worst case runmng time of cn log n or higher and employ only quadratic tests, that is, tests of the formf(x0, y0, xl, yl, ., xn-~, yn-0:0, where f is any polynomial of degree not exceeding 2 It is shown here that any algorithm In the quadratic deciswn-tree model must make cn log n tests for some input KEY WORDS AND PHRASES: complexity, convex hull, decision tree, lower bound, quadratic decision-tree model, quadratic test CR CATEGORIES" 5.25, 5.30We use O(g(n)) to denote any functlonf(n) with the property that clg(n) _< f(n) _< c2g(n) for some positive constants ci, c2 and all sufficiently large n.

Consider the implementation of two stacks by letting them grow towards each other in a table of size m. Suppose a random sequence of insertions and deletions is executed, with each instruction having a fixed probability $p(0 < p < \frac{1}{2})$ to be a deletion. Let $A_p (m)$ denote the expected value of $\max \{ x,y\} $, where x and y are the stack heights when the table first becomes full. We shall prove that, as $m \to \infty $, $A_p (m) = m/2 + \sqrt{m/(2\pi (1 - 2p))} + O((\log m)^2 /\sqrt m )$. This gives a solution to an open problem in Knuth [The Art of Computer Programming, Vol. 1, Exercise 2.2.2-13].

ASSTRACT. In the all-pair shortest distance problem, one computes the matrix D = (du), where dq is the minimum weighted length of any path from vertex i to vertexj in a directed complete graph with a weight on each edge. In all the known algorithms, a shortest path p, ~ achieving di./is also implicitly computed. In fact, logs(f (n)) is an information-theoretic lower bound, wheref(n) is the total number of distinct patterns (Po) for n-vertex graphs. As f(n) potentially can be as large as 2":', it would appear possible that a nontrivial lower bound can be derived this way in the decision tree model. The characterization and enumeration of realizable patterns is studied, and it is shown thatf(n) < C "~. Thus no lower bound greater than Cn 2 can be derived from this approach. It is proved as a corollary that the Triangular polyhedron T ~"~, defined in E ¢~' ~ by d,j> 0 and the triangle inequalities d~j + dik> d,k, has at most C" ' faces of all dimensions, thus resolving an open question in a similar information bound approach to the shortest distance problem.

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

In the bin-packing problem a list L of n numbers are to be packed into unit-capacity bins. For any algorithm S , let r ( S ) be the maximum ratio S ( L )/ L * for large L * , where S ( L ) denotes the number of bins used by S and L * denotes the minimum number needed. An on-line Ο ( n log n )-time algorithm RFF with r (RFF) = 5/3 and an off-line polynomial-time algorithm RFFD with r (RFFD) ≤ 11/9 - ε for some fixed ε > 0, are given. These are strictly better, respectively, than two prominent algorithms: the First-Fit (FF), which is on-line with r (FF) = 17/10, and the First-Fit-Decreasing (FFD) with r (FFD) = 11/9. Furthermore, it is shown that any on-line algorithm S must have r ( S ) ≥ 3/2. The question, “How well can an ο ( n log n )-time algorithm perform?” is also discussed. It is shown that in the generalized d -dimensional bin packing, any ο ( n log n )-time algorithm S must have r ( S ) ≥ d .

We investigate the complexity of network selection by measuring it in terms of $U(t,N)$, the minimum number of comparators needed, and $T(t,N)$, the minimum delay time possible, for networks selecting the smallest t elements from a set of N inputs. New bounds on $U(t,N)$ and $T(t,N)$ are presented. In particular, the asymptotic forms of $U(t,N)$ and $T(t,N)$ are determined for any fixed t.

Computational problems sometimes can be cast in the following form: Given a point ${\bf x}$ in $R^n $, determine if ${\bf x}$ lies in some fixed polyhedron. In this paper we give a general lower bound to the complexity of such problems, showing that $\frac{1}{2}\log _2 f_s $ linear comparisons are needed in the worst case, for any polyhedron with $f_s$s-dimensional faces. For polyhedra with abundant faces, this leads to lower bounds nonlinear in n, the number of variables.

Geometric closest potnt problems deal with the proxLmity relationships in k-dimensional point sets.Examples of closest point problems include building minimum spanning trees, nearest neighbor searching, and triangulation constructmn Shamos and Hoey [17] have shown how the Voronoi dtagram can be used to solve a number of planar closest point problems in optimal worst case tune.In this paper we extend thmr work by giving optimal expected.trinealgorithms for solving a number of closest point problems in k-space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimum spanning trees.In addition to establishing theoretical bounds, the algorithms in this paper can be implemented to solve practical problems very efficiently.

Let M = {0, 1, 2, ..., m—1} , N = {0, 1, 2,..., n—1} , and f:M × N → {0, 1} a Boolean-valued function. We will be interested in the following problem and its related questions. Let i ε M, j ε N be integers known only to two persons P1 and P2, respectively. For P1 and P2 to determine cooperatively the value f(i, j), they send information to each other alternately, one bit at a time, according to some algorithm. The quantity of interest, which measures the information exchange necessary for computing f, is the minimum number of bits exchanged in any algorithm. For example, if f(i, j) = (i + j) mod 2. then 1 bit of information (conveying whether i is odd) sent from P1 to P2 will enable P2 to determine f(i, j), and this is clearly the best possible.

We study the average-case complexity of finding all occurrences of a given pattern $\alpha $ in an input text string. Over an alphabet of q symbols, let $c(\alpha ,n)$ be the minimum average number of characters that need to be examined in a random text string of length n. We prove that, for large m, almost all patterns $\alpha $ of length m satisfy \[ c(\alpha ,n) = \theta \left( \left\lceil \log _q \left(\frac{{n - m}}{{\ln m}} + 2\right) \right\rceil \right)\quad \text{if }m \leqq n \leqq 2m, \] and \[ c(\alpha ,n) = \theta \left( \frac{{\lceil {\log _q m} \rceil }}{m}n \right)\quad{\text{if }} n > 2m. \] This in particular confirms a conjecture raised in a recent paper by Knuth, Morris, and Pratt (Fast pattern matching in strings, SIAM J. Comput., 6 (1977), pp. 323–350.

We examine optimality questions in the following information retrieval problem: Given a set S of n keys, store them so that queries of the form Is x $\in$ S? can be answered quickly. It is shown that, in a rather general model including al1 the commonly-used schemes, $\lceil$ lg(n+l) $\rceil$ probes to the table are needed in the worst case, provided the key space is sufficiently large. The effects of smaller key space and arbitrary encoding are also explored.

Let Vk (n) be the minimum average number of pairwise comparisons needed to find the k-th largest of n numbers (k≥2), assuming that all n! orderings are equally likely. D. W. Matula proved that, for some absolute constant c, Vk(n)- n ≤ ck log log n as n → ∞. In the present paper, we show that there exists an absolute constant c′ ≫ 0 such that Vk(n) - n ≥ c′k log log n as n → ∞, proving a conjecture by Matula.

AaSTRACr There are languages which can be recognized by a deterministic (k+l)-headed one-way finite automaton but which cannot be recognized by a k-headed one-way (deterministic or nondetermlnisuc) finite automaton Furthermore, there is a language accepted by a 2-headed nondetermlmstic fimte automaton which is accepted by no k-headed deterministic finite automaton.

The following graph addressing problem was studied by Graham and Pollak in devising a routing scheme for Pierce’s loop switching network. Let G be a graph with n vertices. It is desired to assign to each vertex $v_i $ an address in $\{ 0,1, * \} ^l $, such that the Hamming distance between the addresses of any two vertices agrees with their distance in G. Let $N(G)$ be the minimum length l for which an assignment is possible. It was shown by Graham and Pollak that $N(G) \leqq m_G (n - 1)$, where $m_G $ is the diameter of G. In the present paper, we shall prove that $N(G) \leqq 1.09(\lg m_G )n + 8n$ by an explicit construction. This shows in particular that any graph has an addressing scheme of length $O(n\log n)$.

Let P be a polyhedron with fs s-dimensional faces. We show that Ω(log fs) linear comparisons are needed to determine if a point lies in P. This is used to establish an Ω(n2 log n) lower bound to the all-pairs shortest path problem between n points.

There are languages which can be recognized by a deterministic (k + 1)-headed oneway finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, there is a language accepted by a 2-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton.

In this paper we study the expected running time of a variety of algorithms that perform set merging. The set merging problem (for example, see AHU [1]) is concerned with using suitable data structures to represent partition of a set S = { 1,2, .... ,n} so that a sequence of instructions of the form “x X y”, meaning“Find the subset containing x; Find the subset containing y; Merge the two subsets if they are different.”may be carried out efficiently. Several alternative data structures for solving this problem are known, and their worse-case complexity fairly well understood [3], [4], [5], [8]. In contrast, the average behavior of even the most basic of these schemes remains an open problem [6]. It is the purpose of the present paper to determine the average behavior for several of the set merging algorithms commonly known.

Let M ( m, n ) be the minimum number or comparators needed in an ( m, n )-merging network. It is shown that M ( m, n ) ≥ n (lg( m + 1))/2, which implies that Batcher's merging networks are optimal up to a factor of 2 + ε for almost all values of m and n . The limit r m = lim n→∞ M ( m, n )/ n is determined to within 1. It is also proved that M (2, n ) = [3 n /2].

It is shown that for any set of positive integers $\{ n_1 ,n_2 , \cdots ,n_p \} $, there exists a procedure which computes $\{ x^{n_1 } ,x^{n_2 } , \cdots ,x^{n_p } \} $ for any input x in less than $\lg N + c\sum_{i = 1}^P [\lg n_i /\lg \lg (n_i + 2)]$ multiplications for some constant c, where $N = \max _i \{ n_i \} $. This gives a partial solution to an open problem in Knuth [3, § 4.6.3, Ex. 32] and generalizes Brauer’s theorem on addition chains.

The following problem was recently raised by C. William Gear [1]: Let F(x1,x2,...,xn) = Σi≤j a'ijxixj + Σi bixi +c be a quadratic form in n variables. We wish to compute the point x→(0) = (x1(0),...,xn(0)), at which F achieves its minimum, by a series of adaptive functional evaluations. It is clear that, by evaluating F(x→) at 1/2(n+1)(n+2)+1 points, we can determine the coefficients a'ij,bi,c and thereby find the point x→(0). Gear's question is, “How many evaluations are necessary?” In this paper, we shall prove that O(n2) evaluations are necessary in the worst case for any such algorithm.