Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u,p)-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u, p)-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding (u, p)-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for (u, p)-maxmin strategies.

Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special “leader” state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for n agents using O(log log n) states must take Ω(n/polylogn) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic convergence time can be achieved using O (log2 n) space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between O (log log n) and Θ(log2 n) state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.

We propose a simple method for improving the security of hashed passwords: the maintenance of additional ``honeywords'' (false passwords) associated with each user's account. An adversary who steals a file of hashed passwords and inverts the hash function cannot tell if he has found the password or a honeyword. The attempted use of a honeyword for login sets off an alarm. An auxiliary server (the ``honeychecker'') can distinguish the user password from honeywords for the login routine, and will set off an alarm if a honeyword is submitted.

We introduce Drifting Keys (DKs), a simple new approach to detecting device impersonation. DKs enable detection of complete compromise by an attacker of the device and its secret state, e.g., cryptographic keys. A DK evolves within a device randomly over time. Thus an attacker will create DKs that randomly diverge from those in the original, valid device over time, alerting a trusted verifier to the attack. DKs may be transmitted unidirectionally from a device, eliminating interaction between the device and verifier. Device emissions of DK values can be quite compact - even just a single bit - and DK evolution and emission require minimal computation. Thus DKs are well suited for highly constrained devices, such as sensors and hardware authentication tokens. We offer a formal adversarial model for DKs, and present a simple scheme that we prove essentially optimal (undominated) for a natural class of attack timelines. We explore application of this scheme to one-time passcode authentication tokens. Using the logs of a large enterprise, we experimentally study the effectiveness of DKs in detecting the compromise of such tokens.

We consider the following challenge: How can a cloud storage provider prove to a tenant that it's encrypting files at rest, when the provider itself holds the corresponding encryption keys? Such proofs demonstrate sound encryption policies and file confidentiality. (Cheating, cost-cutting, or misconfigured providers may bypass the computation/management burdens of encryption and store plaintext only.)

This paper presents a new challenge--verifying that a remote server is storing a file in a fault-tolerant manner, i.e., such that it can survive hard-drive failures. We describe an approach called the Remote Assessment of Fault Tolerance (RAFT). The key technique in a RAFT is to measure the time taken for a server to respond to a read request for a collection of file blocks. The larger the number of hard drives across which a file is distributed, the faster the read-request response. Erasure codes also play an important role in our solution. We describe a theoretical framework for RAFTs and offer experimental evidence that RAFTs can work in practice in several settings of interest.

A common trend in applications of block ciphers over the past decades has been to employ block ciphers as one piece of a “mode of operation”—possibly, a way to make a secure symmetric-key cryptosystem, but more generally, any cryptographic application. Most of the time, these modes of operation use a wide variety of techniques to achieve a subgoal necessary for their main goal: instantiation of “essentially different” instances of the block cipher. We formalize a cryptographic primitive, the “ tweakable block cipher .” Such a cipher has not only the usual inputs—message and cryptographic key—but also a third input, the “tweak.” The tweak serves much the same purpose that an initialization vector does for CBC mode or that a nonce does for OCB mode. Our abstraction brings this feature down to the primitive block-cipher level, instead of incorporating it only at the higher modes-of-operation levels. We suggest that (1) tweakable block ciphers are easy to design, (2) the extra cost of making a block cipher “tweakable” is small, and (3) it is easier to design and prove the security of applications of block ciphers that need this variability using tweakable block ciphers.

In the above titled paper (ibid., vol. 4, no. 4, pp. 611-627, Dec. 09), due to a production error, the affiliations of two of the authors were listed incorrectly. The correct affiliations are presented here. Also, the name of the last author in the affiliations footnote was printed incorrectly. The correct name is P. Y. A. Ryan.

Scantegrity II is an enhancement for existing paper ballot systems. It allows voters to verify election integrity - from their selections on the ballot all the way to the final tally - by noting codes and checking for them online. Voters mark Scantegrity II ballots just as with conventional optical scan, but using a special ballot marking pen. Marking a selection with this pen makes legible an otherwise invisible preprinted confirmation code. Confirmation codes are independent and random for each potential selection on each ballot. To verify that their individual votes are recorded correctly, voters can look up their ballot serial numbers online and verify that their confirmation codes are posted correctly. The confirmation codes do not allow voters to prove how they voted. However, the confirmation codes constitute convincing evidence of error or malfeasance in the event that incorrect codes are posted online. Correctness of the final tally with respect to the published codes is proven by election officials in a manner that can be verified by any interested party. Thus, compromise of either ballot chain of custody or the software systems cannot undetectably affect election integrity. Scantegrity II has been implemented and tested in small elections in which ballots were scanned either at the polling place or centrally. Preparations for its use in a public sector election have commenced.

The 13 papers in this special issue focus on electronic voting.

User authentication in computing systems traditionally depends on three factors: something you have (e.g., a hardware token), something you are (e.g., a fingerprint), and something you know (e.g., a password). In this paper, we explore a fourth factor, the social network of the user, that is, somebody you know.Human authentication through mutual acquaintance is an age-old practice. In the arena of computer security, it plays roles in privilege delegation, peer-level certification, help-desk assistance, and reputation networks. As a direct means of logical authentication, though, the reliance of human being on another has little supporting scientific literature or practice.In this paper, we explore the notion of vouching, that is, peer-level, human-intermediated authentication for access control. We explore its use in emergency authentication, when primary authenticators like passwords or hardware tokens become unavailable. We describe a practical, prototype vouching system based on SecurID, a popular hardware authentication token. We address traditional, cryptographic security requirements, but also consider questions of social engineering and user behavior.

Abstract Networks of the future will be characterized by a variety of computational devices that display a level of dynamism not seen in traditional wired networks. Because of the dynamic nature of these networks, resource discovery is one of the fundamental problems that must be solved. While resource discovery systems are not a novel concept, securing these systems in an efficient and scalable way is challenging. This paper describes the design and implementation of an architecture for access‐controlled resource discovery. This system achieves this goal by integrating access control with the Intentional Naming System (INS), a resource discovery and service location system. The integration is scalable, efficient, and fits well within a proxy‐based security framework designed for dynamic networks. We provide performance experiments that show how our solution outperforms existing schemes. The result is a system that provides secure, access‐controlled resource discovery that can scale to large numbers of resources and users. Copyright © 2004 John Wiley & Sons, Ltd.

We propose the use of selective blocking by as a way of protecting consumers from unwanted scanning of RFID tags attached to items they may be carrying or wearing.While an ordinary RFID tag is a simple, cheap (e.g. five-cent) passive device intended as an electronic bar-code for use in supply-chain management, a blocker tag is a cheap passive RFID device that can simulate many ordinary RFID tags simultaneously. When carried by a consumer, a blocker tag thus blocks RFID readers. It can do so universally by simulating all possible RFID tags. Or a blocker tag can block selectively by simulating only selected subsets of ID codes, such as those by a particular manufacturer, or those in a designated zone.We believe that this approach, when used with appropriate care, provides a very attractive alternative for addressing privacy concerns raised by the potential (and likely) widespread use of RFID tags in consumer products.We also discuss possible abuses arising from blocker tags, and means for detecting and dealing with them.

SPKI/SDSI is a novel public-key infrastructure emphasizing naming, groups, ease-of-use, and flexible authorization. To access a protected resource, a client must present to the server a proof that the client is authorized; this proof takes the form of a “certificate chain” proving that the client's public key is in one of the groups on the resource's ACL, or that the client's public key has been delegated authority (in one or more stages) from a key in one of the groups on the resource's ACL. While finding such a chain can be nontrivial, due to the flexible naming and delegation capabilities of SPKI/SDSI certificates, we present a practical and efficient algorithm for this problem of “certificate chain discovery”. We also present a tight worst-case bound on its running time, which is polynomial in the length of its input. We also present an extension of our algorithm that is capable of handling “threshold subjects”, where several principals are required to co-sign a request to access a protected resource.

We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every so often to its starting position (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that it has already explored. We present a surprisingly efficient algorithm for piecemeal learning an unknown undirected graph G=(V, E) in which the robot explores every vertex and edge in the graph by traversing at most O(E+V1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E+V2) edges. We also give an application of piecemeal learning to the problem of searching a graph for a “treasure.”

We examine the problem of deciphering a file that has been Huffman coded, but not otherwise encrypted. We find that a Huffman code can be surprisingly difficult to cryptanalyze. We present a detailed analysis of the situation for a three-symbol source alphabet and present some results for general finite alphabets.

) Baruch Awerbuch y Margrit Betke Ronald L. Rivest Mona Singh Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 Abstract We study the problem of learning a graph by piecemeal exploration, in which a mobile robot must return every so often to its starting point (for refueling, say). We assume that the robot can distinguish vertices and edges which it has already explored. We present an algorithm for piecemeal learning an unknown undirected graph G = (V; E) in which the robot explores every vertex and edge in G by traversing at most O(E + V 1+o(1) ) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E + V 2 ) edges. We also address the related problem of searching a graph for a particular distinguished location or treasure. If this location or treasure is known to be near the starting point, then the robot should search in a breadth-first manner from the starting point. We gi...

We explore the power of teaChillg by StUdyiIlg two uu-lille learuing models: teach er-clirecteci learninE and self-dlrectecl learning. In both models, the learner tries to identify an unkuowu concept based on examples of the concept presented one at, a time. The learner predirts wheth~r each example is positive or negative with immediate feedback, and the ol)ject,ive is to minimize the uurnl)er of predict,iou mistakes. ThP examples are selected by the teacher in teacher-dlrectecl learning and hy tlhe learner itself in self-directed learning. R,oughly, teacher-directed learning represents the scenario in which a teacher teaches a class of learners, and self-directed learning represents the scenario in which a smart learnerasks questious and learns by itself. For all previolmly studied concept classes, the rnirrimum numl)er of mistalws in teacller-ciirectf ecl learning is always larger than that, in self-directed learning. This raises an mtermting question [.)t ’ whrt, hrr teaching is helpful for all learners mrlu(ling the smart learner’. Assuming the existence of clue-way functioms, we construct com cept clahses for which the miuimum nurnher of mislakes is hnear in teacher-directed learning I,ut sllI>rrlJolyllorlllal m self-directed learning, cler~lc~llst,rt~tillg the power of a helpful teacher in a Iearmng process.

We present new procedures for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. Our procedures use a new representation for finite automata, based on the notion of equivalence betweentests. We call the number of such equivalence classes thediversityof the automaton; the diversity may be as small as the logarithm of the number of states of the automaton. For the special class ofpermutation automata, we describe an inference procedure that runs in time polynomial in the diversity and log(1/δ), where δ is a given upper bound on the probability that our procedure returns an incorrect result. (Since our procedure uses randomization to perform experiments, there is a certain controllable chance that it will return an erroneous result.) We also discuss techniques for handling more general automata. We present evidence for the practical efficiency of our approach. For example, our procedure is able to infer the structure of an automaton based on Rubik's Cube (which has approximately 1019states) in about 2 minutes on a DEC MicroVax. This automaton is many orders of magnitude larger than possible with previous techniques, which would require time proportional at least to the number of global states. (Note that in this example, only a small fraction (10-14) of the global states were even visited.) Finally, we present a new procedure for inferring automata of a special type in which the global state is composed of a vector of binary local state variables, all of which are observable (orvisible) to the experimenter. Our inference procedure runs provably in time polynomial in the size of this vector (which happens to be the diversity of the automaton), even though the global state space may be exponentially larger. The procedure plans and executes experiments on the unknown automaton; we show that the number of input symbols given to the automaton during this process is (to within a constant factor) the best possible.

We introduce a new learning problem: learning a graph by piecemeal search, in which the learner must return every so often to its starting point (for refueling, say).We present two linear-time piecemeal-search algorithms for learning city-block graphs: grid graphs with rectangular obstacles.

The problem of learning a binary relation between two sets of objects or between a set and itself is studied. This paper represents a binary relation between a set of size n and a set of size m as an $n \times m$ matrix of bits whose $(i,j)$ entry is 1 if and only if the relation holds between the corresponding elements of the two sets. Polynomial prediction algorithms are presented for learning binary relations in an extended on-line learning model, where the examples are drawn by the learner, by a helpful teacher, by an adversary, or according to a uniform probability distribution on the instance space. The first part of this paper presents results for the case in which the matrix of the relation has at most k row types. It presents upper and lower bounds on the number of prediction mistakes any prediction algorithm makes when learning such a matrix under the extended on-line learning model. Furthermore, it describes a technique that simplifies the proof of expected mistake bounds against a randomly chosen query sequence. In the second part of this paper the problem of learning a binary relation that is a total order on a set is considered. A general technique using a fully polynomial randomized approximation scheme (fpras) to implement a randomized version of the halving algorithm is described. This technique is applied to the problem of learning a total order, through the use of an fpras for counting the number of extensions of a partial order, to obtain a polynomial prediction algorithm that with high probability makes at most $n\lg n + (\lg e)\lg n$ mistakes when an adversary selects the query sequence. The case in which a teacher or the learner selects the query sequence is also considered

The MD4 message digest algorithm takes an input message of arbitrary length and produces an output 128-bit “fingerprint” or “message digest”, in such a way that it is (hopefully) computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest. The MD4 algorithm is thus ideal for digital signature applications: a large file can be securely “compressed” with MD4 before being signed with (say) the RSA public-key cryptosystem.The MD4 algorithm is designed to be quite fast on 32-bit machines. For example, on a SUN Sparc station, MD4 runs at 1,450,000 bytes/second (11.6 Mbit/sec). In addition, the MD4 algorithm does not require any large substitution tables; the algorithm can be coded quite compactly.The MD4 algorithm is being placed in the public domain for review and possible adoption as a standard.

Two parties, A and B, want to sign a contract C over a communication network. To do so, they must simultaneously exchange their commitments to C. Since simultaneous exchange is usually impossible in practice, protocols are needed to approximate simultaneity by exchanging partial commitments in piece-by-piece manner. During such a protocol, one party or another may have a slight advantage; a fair protocol keeps this advantage within acceptable limits. A new protocol is proposed. It is fair in the sense that, at any stage in its execution, the conditional probability that one party cannot commit both parties to the contract given that the other party can, is close to zero. This is true even if A and B have vastly different computing powers and is proved under very weak cryptographic assumptions.>

The problem of designing polynomial prediction algorithms for learning binary relations is studied for an online model in which the instances are drawn by the learner, by a helpful teacher, by an adversary, or according to a probability distribution on the instance space. The relation is represented as an n*m binary matrix, and results are presented when the matrix is restricted to have at most k distinct row types, and when it is constrained by requiring that the predicate form a total order.>

We present new algorithms for inferring an unknown finite-state automaton from its input/output behavior in the absence of a means of resetting the machine to a start state. A key technique used is inference of a homing sequence for the unknown automaton.

The problem of learning a concept from examples in a distribution-free model is considered. The notion of dynamic sampling, wherein the number of examples examined can increase with the complexity of the target concept, is introduced. This method is used to establish the learnability of various concept classes with an infinite Vapnik-Chervonenkis (VC) dimension. An important variation on the problem of learning from examples, called approximating from examples, is also discussed. The problem of computing the VC dimension of a finite concept set defined on a finite domain is considered.>

We present a digital signature scheme based on the computational difficulty of integer factorization. The scheme possesses the novel property of being robust against an adaptive chosen-message attack: an adversary who receives signatures for messages of his choice (where each message may be chosen in a way that depends on the signatures of previously chosen messages) cannot later forge the signature of even a single additional message. This may be somewhat surprising, since in the folklore the properties of having forgery being equivalent to factoring and being invulnerable to an adaptive chosen-message attack were considered to be contradictory. More generally, we show how to construct a signature scheme with such properties based on the existence of a “claw-free” pair of permutations—a potentially weaker assumption than the intractibility of integer factorization. The new scheme is potentially practical: signing and verifying signatures are reasonably fast, and signatures are compact.

A knapsack-type public key cryptosystem is introduced that is the system is based on a novel application of arithmetic in finite fields. By appropriately choosing the parameters, one can control the density of the resulting knapsack, which is the ratio between the number of elements in the knapsack and their size in bits. In particular, the density can be made high enough to foil so-called low-density attacks against the system. At the moment, no attacks capable of breaking the system in a reasonable amount of time are known.>

We present a new procedure for inferring the structure of a finitestate automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. Our procedure uses a new representation for FSA's, based on the notion of equivalence between testa. We call the number of such equivalence classes the diversity of the automaton; the diversity may be as small as the logarithm of the number of states of the automaton. The size of our representation of the FSA, and the running time of our procedure (in some case provably, in others conjecturally) is polynomial in the diversity and ln(1/ε), where ε is a given upper bound on the probability that our procedure returns an incorrect result. (Since our procedure uses randomization to perform experiments, there is a certain controllable chance that it will return an erroneous result.) We also present some evidence for the practical efficiency of our approach. For example, our procedure is able to infer the structure of an automaton based on Rubik's Cube (which has approximately 1019 states) in about 2 minutes on a DEC Micro Vax. This automaton is many orders of magnitude larger than possible with previous techniques, which would require time proportional at least to the number of global states. (Note that in this example, only a small fraction (10-14) of the global states were even visited.)

A transmission control strategy is described for slotted-ALOHA-type broadcast channels with ternary feedback. At each time slot, each station estimates the probability that n stations are ready to transmit a packet for eachn, using Bayes' rule and the observed history of collisions, successful transmissions, and holes (empty slots). A station transmits a packet in a probabilistic manner based on these estimates. This strategy is called Bayesian broadcast. An elegant and very practical strategy--pseudo-Bayesian broadcast--is then derived by approximating the probability estimates with a Poisson distribution with mean\nuand further simplifying. Each station keeps a copy of\nu, transmits a packet with probability1/\nu, and then updates\nuin two steps: For collisions, increment\nuby(e-2)^{-l}=1.39221 \cdots. For successes and holes, decrement\nuby1. Set\nuto\max (\nu + \hat{\lambda}, 1), where\hat{\lambda}is an estimate of the arrival rate\lambdaof new packets into the system. Simulation results are presented showing that pseudo-Bayesian broadcast performs well in practice, and methods that can be used to prove that certain versions of pseudo-Bayesian broadcast are stable for\lambda < e^{-1}are discussed.

A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ability to quickly move or copy small rectangles of pixels is essential. This paper proposes a novel organization of raster-graphics memory that permits all small rectangles to be moved efficiently. The memory organization is based on a doubly periodic assignment of pixels to M memory chips according to a “Fibonacci” lattice. The memory organization guarantees that, if a rectilinearly oriented rectangle contains fewer than M / @@@@5 pixels, then all pixels will reside in different memory chips and thus can be accessed simultaneously. Moreover, any M consecutive pixels, arranged either horizontally or vertically, can be accessed simultaneously. We also define a continuous analog of the problem, which can be posed as: “What is the maximum density of a set of points in the plane such that no two points are contained in the interior of a rectilinearly oriented rectangle of unit area?” We show the existence of such a set with density 1/ @@@@5, and prove this is optimal by giving a matching upper bound.

Let\{X_{i}\}_{i=1}^{\infty}be a sequence of independent Bernoulli random variables with probabilitypthatX_{i} = 1and probabilityq=1-pthatX_{i} = 0for alli \geq 1. Time-invariant finite-memory (i.e., finite-state) estimation procedures for the parameter p are considered which takeX_{1}, \cdotsas an input sequence. In particular, an n-state deterministic estimation procedure is described which can estimate p with mean-square errorO(\log n/n)and ann-state probabilistic estimation procedure which can estimatepwith mean-square errorO(1/n). It is proved that theO(1/n)bound is optimal to within a constant factor. In addition, it is shown that linear estimation procedures are just as powerful (up to the measure of mean-square error) as arbitrary estimation procedures. The proofs are based on an analog of the well-known matrix tree theorem that is called the Markov chain tree theorem.

We present a general signature scheme which uses any pair of trap-door permutations (f0, f1) for which it is infeasible to find any x, y with f0(x) = f1(y). The scheme possesses the novel property of being robust against an adaptive chosen message attack: no adversary who first asks for and then receives sgnatures for messages of his choice (which may depend on previous signatures seen) can later forge the signature of even a singl additional message.

We examine the problem of routing wires on a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case "channel-width" needed to route an n × n array, and develop provably good heuristics for the general case. An interesting "rounding algorithm" for obtaining integral approximations to solutions of linear equations is used to show the near-optimality of single-turn routings in the worst-case.

“PI” is an advanced LISP-based placement and interconnect system for custom NMOS or CMOS (single-layer metal) designs. When fully implemented, PI will handle placement of arbitrarily-sized rectangular modules, routing of power and ground, signal routing, and compaction. In this paper we briefly review the structure of PI, and present details on the signal-routing heuristics, focusing on the definition of “channels”, the global router, the “crossing placer”, and the channel routers. The signal router is fully operational; the rest of PI is currently being coded and will be more fully described in later papers and theses.

We present a new, “greedy”, channel-router that is quick, simple, and highly effective. It always succeeds, usually using no more than one track more than required by channel density. (It may be forced in rare cases to make a few connections “off the end” of the channel, in order to succeed.) It assumes that all pins and wiring lie on a common grid, and that vertical wires are on one layer, horizontal on another.

A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ability to quickly move or copy small rectangles of pixels is essential. This paper proposes a novel organization of raster-graphics memory that permits all small rectangles to be moved efficiently. The memory organization is based on a doubly periodic assignment of pixels to M memory chips according to a "Fibonacci" lattice. The memory organization guarantees that if a rectilinearly oriented rectangle contains fewer than M/√5 pixels, then all pixels will reside in different memory chips, and thus can be accessed simultaneously. We also define a continuous amdogue of the problem which can be posed as, "What is the maximum density of a set of points in the plane such that no two points are contained in the interior of a rectilinearly oriented rectangle of area N." We give a lower bound of 1/2N on the density of such a set, and show that 1/√5N can be achieved.

Storage media such as digital optical disks, PROMS, or paper tape consist of a number of “write-once” bit positions (wits); each wit initially contains a “0” that may later be irreversibly overwritten with a “I”. We demonstrate that such “write-once memories” (woms) can be “rewritten” to a surprising degree. For example, only 3 wits suffice to represent any 2-bit value in a way that can later be updated to represent any other 2-bit value. For large k, 1.29... k wits suffice to represent a k-bit value in a way that can be similarly updated. Most surprising, allowing t writes of a k-bit value requires only t + o(t) wits, for any fixed k. For fixed t, approximately k.t/log(t) wits are required as k → @@@@. An n-wit WOM is shown to have a “capacity” (i.e. k.t when writing a k-bit value t times) of up to n.log(n) bits.

We consider problems of packing an arbitrary collection of rectangular pieces into an open-ended, rectangular bin so as to minimize the height achieved by any piece. This problem has numerous applications in operations research and studies of computer operation. We devise efficient approximation algorithms, study their limitations, and derive worst-case bounds on the performance of the packings they produce.

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.

We investigate the problem of finding a homeomorphic image of a “pattern” graph H in a larger input graph G. We view this problem as finding specified sets of edge disjoint or node disjoint paths in G. Our main result is a linear time algorithm to determine if there exists a simple cycle containing three given nodes in G; here H is a triangle. No polynomial time algorithm for this problem was previously known. We also discuss a variety of reductions between related versions of this problem and a number of open problems.

We consider the problem of identifying an unknown value xε{1,2,...,n} using only comparisons of x to constants when as many as E of 'the comparisons may receive erroneous answers. For a continuous analogue of this problem we show that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log2n+E.log2log2n+O(E.log2E) comparisons in the worst case. This number is shown to be optimal even if arbitrary “Yes-No” questions are allowed.

When open addressing IS used to resolve collisions in a hash table, a given set of keys may be arranged in many ways, typically this depends on the order in which the keys are inserted It is shown that arrangements minimizing either the average or worst-case number of probes required to retrieve any key in the table can be found using an algorithm for the assignment problem.The worst-case retrieval time can be reduced to O(log2(M)) with probablhty 1 -e(M) when storing Mkeys In a table of size M, where ~(M)~ 0 as M ~ ~ We also examine insertion algorithms to see how to apply these ideas for a dynamically changing set of keys KEY WORDS AND PHRASES hashing, collision resolution, searching, assignment problem, optimal algorithms, database organization CR CATEGORIES 3 74, 5 41 "Spread the table and contention will cease "' Old English proverb [11, #¢272 6] General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyrlght notice is given and that reference is made to the pubhcatlon, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does repubhcation, or systematic or multiple reproduction This research was prepared with the support of the National Science Foundation

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.

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.

Any algorithm for finding a pattern of length k in a string of length n must examine at least $n - k + 1$ of the characters of the string in the worst case. By considering the pattern $00 \cdots 0$, we prove that this is the best possible result. Therefore there do not exist pattern matching algorithms whose worst-case behavior is “sublinear” in n (that is, linear with constant less than one), in contrast with the situation for average behavior (the Boyer-Moore algorithm is known to be sublinear on the average).

We present a specific n-input 2n-output positive unate Boolean function which can be realized with 2n two-input gates if feedback is used, but which requires 3n-2 gates if feedback is not used.

Consider n processes operating asynchronously in parallel, each of wich maintains a single "special" variable which can be read (but not written) by the other processes. All coordination between processes is to be accomplished by means of the execution of the primitive operations of a process (1) reading another process's special variable, and (2) setting its own special variable to some value. A process may "die" at any time, when its special variable is (automatically) set a special "dead" value. A dead process may revive. Reading a special variable which is being simultaneously written returns either the old or the new value. Each process may be in a certain "critical" state (which it leaves if it dies). We present a coordination scheme with the following properties. (1) At most one process is ever in its critical state at a time. (2) If a process wants to enter its critical state, it may do so before any other process enters its critical state more than once. (3) The special variables are bounded in value. (4) Some process wanting to enter its critical state can always make progress to that goal. By the definition of the problem, no process can prevent another from entering its critical state by repeatedly failing and restarting. In the case of two processes, what makes our solution of particular interest is its remarkable simplicity when compared with the extant solutions to this problem. Our n-process solution uses the two-process solution as a subroutine, and is not quite as elegant as the two-process solution.

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.

We examine the efficiency of hash-coding and tree-search algorithms for retrieving from a file of k-letter words all words which match a partially-specified input query word (for example, retrieving all six-letter English words of the form S**R*H where “*” is a “don’t care” character). We precisely characterize those balanced hash-coding algorithms with minimum average number of lists examined. Use of the first few letters of each word as a list index is shown to be one such optimal algorithm. A new class of combinatorial designs (called associative block designs) provides better hash functions with a greatly reduced worst-case number of lists examined, yet with optimal average behavior maintained. Another efficient variant involves storing each word in several lists. Tree-search algorithms are shown to be approximately as efficient as hash-coding algorithms, on the average. In general, these algorithms require time about $O(n^{(k - s)/k} )$ to respond to a query word with s letters specified, given a file of nk-letter words. Previous algorithms either required time $O(s \cdot n/k)$ or else used exorbitant amounts of storage.

We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P)=d whenever P(0d) @@@@ P(1d) and P is left invariant by a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) proves the generalized conjecture for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture by showing that at least v2/9 entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.

New upper and lower bounds are presented for the maximum number of comparisons, f(i,n), required to select the i-th largest of n numbers. An upper bound is found, by an analysis of a new selection algorithm, to be a linear function of n: