The prophet inequality is a fundamental problem in optimal stopping theory. Given n independent variables drawn from known distributions, a player observes values sequentially and must decide irrevocably whether to stop and accept the current value or continue. The goal is to select a single element while maximizing the ratio between the value chosen and that of the maximum value in the sequence. In this paper, we study the minimization counterpart, often termed the min prophet or cost prophet inequality. Unlike the maximization setting, where simple threshold algorithms achieve half of the prophet’s value, the minimization setting is significantly harder, with an exponential lower bound even for i.i.d. variables. We study a multi-choice relaxation in which the algorithm may select multiple variables and gets to choose the best amongst them (the minimum amongst those selected). Our goal is to minimize the expected number of selections while achieving a constant competitive ratio. For adversarial order, we show that a constant competitive ratio requires a nearly linear number of choices in expectation, ergo, Ω(n/ln n). In contrast, we show that for the prophet secretary model (random order) one can attain constant competitiveness while requiring only an exponentially smaller expected number of choices i.e. O(ln n). We give a refined analysis and define M to be the ratio of the minimum expected value of any single variable to the expected minimum value of all variables (the prophet’s value) and present an algorithm that achieves a constant competitive ratio with O(min{ln ln M, ln n}) choices in expectation for the prophet secretary. We show that this is tight up to low order log factors even for the special case of the i.i.d. model. Specifically, the lower bound on the expected number of choices for any constant competitive algorithm is Ω(min{ln ln M/ln ln ln M, ln n/ln ln n}). We also show that if we insist on a deterministic bound on the number of choices then every constant competitive algorithm requires n choices. This holds even in the i.i.d. setting and shows that to achieve a constant competitive algorithm there is an exponential gap between the lower bound on the deterministic number of choices and the upper bound on the expected number of choices. Finally, we consider a variant where both the algorithm and the adversary choose r values and pay their sum, this is the minimization multi unit version. We extend our techniques to the multi-unit variant for i.i.d. variables, achieving a constant competitive ratio with a small expected number of choices.

A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that the mechanism designer might prefer not to disclose, such as her target function or private costs. Avoiding this may be possible via a trusted mediator; however, the availability of a trustworthy mediator, especially if mechanism secrecy must be maintained for years, might be unrealistic. We propose a new approach to commitment, and show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome—all without the need for any mediators. Our framework is based on zero-knowledge proofs—a cornerstone of modern cryptographic theory. Applications include both private-type settings such as auctions and private-action settings such as contracts, as well as non-mediated bargaining with hidden yet binding offers.

We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary ( i.e. , determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade, which is harder to approximate than social welfare. We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear α -regret for any α < 2 , (b) but with full feedback sublinear 2-regret is achievable; (c) with a single price and partial feedback one cannot get sublinear α regret for any constant α (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear 2-regret, and (e) there is a provable separation in the 2-regret bounds between full and partial feedback.

We study envy freeness up to any good (EFX) in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore that it is NP-complete to decide whether an EFX orientation exists. Our main result is that (EFX) allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than 3 agents.

The existence of EFX allocations of goods is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and yet, existence results are known only for very restricted settings, such as: (i) agents with identical valuations, (ii) 2 agents, and (iii) 3 agents with additive valuations. It is also known that EFX exists if one can leave n-1 items unallocated, where n is the number of agents. We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and (arguably) to simplify proofs of earlier results. Our main result is that every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated. Beyond our main result, we introduce a new class of valuations, termed nice cancelable, which includes additive, unit-demand, budget-additive and multiplicative valuations, among others. Using our new techniques, we show that both our results and previous results for additive valuations extend to nice cancelable valuations.

We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary ({\sl i.e.}, determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare.We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear $\alpha$-regret for any $\alpha<2$, (b) but with full feedback sublinear $2$-regret is achievable (c) with a single price and partial feedback one cannot get sublinear $\alpha$ regret for any constant $\alpha$ (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear $2$-regret, and (e) there is a provable separation in the $2$-regret bounds between full and partial feedback.

In this paper we consider the k-server problem where events are generated by selfish agents, known as the selfish k-server problem. In this setting, there is a set of k servers located in some metric space. Selfish agents arrive in an online fashion, each has a request located on some point in the metric space, and seeks to serve his request with the server of minimum distance to the request. If agents choose to serve their request with the nearest server, this mimics the greedy algorithm which has an unbounded competitive ratio. We propose an algorithm that associates a surcharge with each server independently of the agent to arrive (and therefore, yields a truthful online mechanism). An agent chooses to serve his request with the server that minimizes the distance to the request plus the associated surcharge to the server. This paper extends [Ilan Reuven Cohen et al., 2015], which gave an optimal k-competitive dynamic pricing scheme for the selfish k-server problem on the line. We give a k-competitive dynamic pricing algorithm for the selfish k-server problem on tree metric spaces, which matches the optimal online (non truthful) algorithm. We show that an alpha-competitive dynamic pricing scheme exists on the tree if and only if there exists alpha-competitive online algorithm on the tree that is lazy and monotone. Given this characterization, the main technical difficulty is coming up with such an online algorithm.

We give a prompt online mechanism for minimizing the sum of [weighted] completion times. This is the first prompt online algorithm for the problem. When such jobs are strategic agents, delaying scheduling decisions makes little sense. Moreover, the mechanism has a particularly simple form of an anonymous menu of options.

We consider a setting where an auctioneer sells a single item to n potential agents with interdependent values. That is, each agent has her own private signal, and the valuation of each agent is a known function of all n private signals. This captures settings such as valuations for oil drilling rights, broadcast rights, pieces of art, and many more.

We consider job scheduling settings, with multiple machines, where jobs arrive online and choose a machine selfishly so as to minimize their cost. Our objective is the classic makespan minimization objective, which corresponds to the completion time of the last job to complete. The incentives of the selfish jobs may lead to poor performance. To reconcile the differing objectives, we introduce posted machine prices. The selfish job seeks to minimize the sum of its completion time on the machine and the posted price for the machine. Prices may be static (i.e., set once and for all before any arrival) or dynamic (i.e., change over time), but they are determined only by the past, assuming nothing about upcoming events. Obviously, such schemes are inherently truthful.

An f-Sensitive Distance Oracle with stretch a preprocesses a graph G(V, E) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set F ⊂ E of at most f edges, and vertices s and t. The oracle answers a query (F,s.,t) by returning a value d which is equal to the length of some path between s and t in the graph G\F (the graph obtained from G by discarding all edges in F). Moreover, d is at most a times the length of the shortest path between s and t in G \ F. The oracle can also construct a path between s and t in G\F of length d. To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any and a fixed ∊ > 0 our oracle answers queries (F,s,t) in time O(l) with (1 + ∊) stretch using a data structure of size n2+0(1) For comparison, the naive alternative requires mfn2 space for sublinear query time.

In this paper we expand the standard Hotelling-Downs model of spatial competition to a setting where clients do not necessarily choose their closest candidate (retail product or political). Specifically, we consider a setting where clients may disavow all candidates if there is no candidate that is sufficiently close to the client preferences. Moreover, if there are multiple candidates that are sufficiently close, the client may choose amongst them at random. We show the existence of Nash Equilibria for some such models, and study the price of anarchy and stability in such scenarios.

We consider the online carpool fairness problem of [Fagin and Williams, 1983] in which an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. The online algorithm must select one driver from each pair, with the objective of partitioning the driving burden as fairly as possible for all drivers. The unfairness of an online algorithm is a measure of the worst-case deviation between the number of times a person has driven and the number of times they would have driven if life was completely fair. We introduce a version of the problem in which drivers only carpool with their neighbors in a given social network graph; this is a generalization of the original problem, which corresponds to the social network of the complete graph. We show that for graphs of degree d, the unfairness of deterministic algorithms against adversarial sequences is exactly d/2. For random sequences of edges from planar graph social networks we give a [deterministic] algorithm with logarithmic unfairness (holds more generally for any bounded-genus graph). This does not follow from previous random sequence results in the original model, as we show that restricting the random sequences to sparse social network graphs may increase the unfairness. A very natural class of randomized online algorithms are so-called static algorithms that preserve the same state distribution over time. Surprisingly, we show that any such algorithm has unfairness ~Theta(sqrt(d)) against oblivious adversaries. This shows that the local random greedy algorithm of [Ajtai et al, 1996] is close to optimal amongst the class of static algorithms. A natural (non-static) algorithm is global random greedy (which acts greedily and breaks ties at random). We improve the lower bound on the competitive ratio from Omega(log^{1/3}(d)) to Omega(log(d)). We also show that the competitive ratio of global random greedy against adaptive adversaries is Omega(d).

Walrasian prices, if they exist, have the property that one can assign every buyer some bundle in her demand set, such that the resulting assignment will maximize social welfare. Unfortunately, this assumes carefully breaking ties amongst different bundles in the buyer demand set. Presumably, the shopkeeper cleverly convinces the buyer to break ties in a manner consistent with maximizing social welfare. Lacking such a shopkeeper, if buyers arrive sequentially and simply choose some arbitrary bundle in their demand set, the social welfare may be arbitrarily bad. In the context of matching markets, we show how to compute dynamic prices, based upon the current inventory, that guarantee that social welfare is maximized. Such prices are set without knowing the identity of the next buyer to arrive. We also show that this is impossible in general (e.g., for coverage valuations), but consider other scenarios where this can be done. We further extend our results to Bayesian and bounded rationality models.

We extend the notion of Combinatorial Walrasian Equilibrium, as defined by \citet{FGL13}, to settings with budgets. When agents have budgets, the maximum social welfare as traditionally defined is not a suitable benchmark since it is overly optimistic. This motivated the liquid welfare of \cite{DP14} as an alternative. Observing that no combinatorial Walrasian equilibrium guarantees a non-zero fraction of the maximum liquid welfare in the absence of randomization, we instead work with randomized allocations and extend the notions of liquid welfare and Combinatorial Walrasian Equilibrium accordingly. Our generalization of the Combinatorial Walrasian Equilibrium prices lotteries over bundles of items rather than bundles, and we term it a lottery pricing equilibrium.

We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The social cost of a candidate is the sum of its distances to each voter. Some of our work assumes that these points can be modeled on the real line, but other results of ours are more general.

Consider the pricing problem faced by FedEx. Each customer has a package to ship, a deadline $d$ by which he needs his package to arrive, and a value $v$ for a guarantee that the package will arrive by his deadline. FedEx can (and does) offer a number of different shipping options in order to extract more revenue from their customers. In this paper, we solve the optimal (revenue-maximizing) auction problem for the single-agent version of this problem. Our paper adds to the relatively short list of multi-parameter settings for which a closed-form solution is known.

Online d-dimensional vector packing models many settings such as minimizing resources in data centers where jobs have multiple resource requirements (CPU, Memory, etc.). However, no online d-dimensional vector packing algorithm can achieve a competitive ratio better than d. Fortunately, in many natural applications, vectors are relatively small, and thus the lower bound does not hold. For sufficiently small vectors, an O(log d)-competitive algorithm was known. We improve this to a constant competitive ratio, arbitrarily close to e ≈ 2.718, given that vectors are sufficiently small. We give improved results for the two dimensional case. For arbitrarily small vectors, the First Fit algorithm for two dimensional vector packing is no better than 2-competitive. We present a natural family of First Fit variants, and for optimized parameters get a competitive ratio ≈ 1.48 for sufficiently small vectors. We improve upon the 1.48 competitive ratio – not via a First Fit variant – and give a competitive ratio arbitrarily close to 4/3 for packing small, two dimensional vectors. We show that no algorithm can achieve better than a 4/3 competitive ratio for two dimensional vectors, even if one allows the algorithm to split vectors among arbitrarily many bins.

Computing driving directions has motivated many shortest path algorithms based on preprocessing. Given a graph, the preprocessing stage computes a modest amount of auxiliary data, which is then used to speed up online queries. In practice, the best algorithms have storage overhead comparable to the graph size and answer queries very fast, while examining a small fraction of the graph. In this article, we complement the experimental evidence with the first rigorous proofs of efficiency for some of the speedup techniques developed over the past decade or variations thereof. We define highway dimension, which strengthens the notion of doubling dimension. Under the assumption that the highway dimension is low (at most polylogarithmic in the graph size), we show that, for some algorithms or their variants, preprocessing can be implemented in polynomial time, the resulting auxiliary data increases the storage requirements by a polylogarithmic factor, and queries run in polylogarithmic time. This gives a unified explanation for the performance of several seemingly different approaches. Our best bounds are based on a result that may be of independent interest: we show that unique shortest paths induce set systems of low VC-dimension, which makes them combinatorially simple.

We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of maximizing social welfare or revenue in an auction settings. This paper deals with quite general settings and minimizing social costs. We show that appropriately computed posted prices allow one to achieve essentially the same performance as the best online algorithm. This holds in a wide variety of settings. Unlike online algorithms that learn about the event, and then make enforcable decisions, prices are posted without knowing the future events or even the current event, and are thus inherently dominant strategy incentive compatible. In particular we show that one can give efficient posted price mechanisms for metrical task systems, some instances of the k-server problem, and metrical matching problems. We give both deterministic and randomized algorithms. Such posted price mechanisms decrease the social cost dramatically over selfish behavior where no decision incurs a charge. One alluring application of this is reducing the social cost of free parking exponentially.

We introduce and study strongly truthful mechanisms and their applications. We use strongly truthful mechanisms as a tool for implementation in undominated strategies for several problems, including the design of externality resistant auctions and a variant of multi-dimensional scheduling.

This paper introduces HLDB, the first practical system that can answer exact spatial queries on continental road networks entirely within a database. HLDB is based on hub labels (HL), the fastest point-to-point algorithm for road networks, and its queries are implemented (quite naturally) in standard SQL. Within the database, HLDB answers exact distance queries and retrieves full shortest-path descriptions in real time, even on networks with tens of millions of vertices. The basic algorithm can be extended in a natural way (still in SQL) to answer much more sophisticated queries, such as finding the ten closest fast-food restaurants. We also introduce efficient new HL-based algorithms for even harder problems, such as best via point, ride sharing, and point of interest prediction. The HLDB framework makes it easy to implement these algorithms in SQL, enabling interactive applications on continental road networks.

We study envy-free (EF) mechanisms for multi-unit auctions with budgeted agents that approximately maximize revenue. In an EF auction, prices are set so that every bidder receives a bundle that maximizes her utility amongst all bundles; We show that the problem of revenue-maximizing EF auctions is NP-hard, even for the case of identical items and additive valuations (up to the budget). The main result of our paper is a novel EF auction that runs in polynomial time and provides a approximation of 1/2 with respect to the revenue-maximizing EF auction. A slight variant of our mechanism will produce an allocation and pricing that is more restrictive (so called item pricing) and gives a 1/2 approximation to the optimal revenue within this more restrictive class.

A Nash Equilibrium is a joint strategy profile at which each agent myopically plays a best response to the other agents' strategies, ignoring the possibility that deviating from the equilibrium could lead to an avalanche of successive changes by other agents. However, such changes could potentially be beneficial to the agent, creating incentive to act non-myopically, so as to take advantage of others' responses. To study this phenomenon, we consider a non-myopic Cournot competition, where each firm selects whether it wants to maximize profit (as in the classical Cournot competition) or to maximize revenue (by masquerading as a firm with zero production costs). The key observation is that profit may actually be higher when acting to maximize revenue, (1) which will depress market prices, (2) which will reduce the production of other firms, (3) which will gain market share for the revenue maximizing firm, (4) which will, overall, increase profits for the revenue maximizing firm. Implicit in this line of thought is that one might take other firms’ responses into account when choosing a market strategy. The Nash Equilibria of the non-myopic Cournot competition capture this action/response issue appropriately, and this work is a step towards understanding the impact of such strategic manipulative play in markets. We study the properties of Nash Equilibria of non-myopic Cournot competition with linear demand functions and show existence of pure Nash Equilibria, that simple best response dynamics will produce such an equilibrium, and that for some natural dynamics this convergence is within linear time. This is in contrast to the well known fact that best response dynamics need not converge in the standard myopic Cournot competition. Furthermore, we compare the outcome of the non-myopic Cournot competition with that of the standard myopic Cournot competition. Not surprisingly, perhaps, prices in the non-myopic game are lower and the firms, in total, produce more and have a lower aggregate utility.

We study envy-free mechanisms for assigning tasks to agents, where every task may take a different amount of time to perform by each agent, and the goal is to get all the tasks done as soon as possible (i.e., minimize the makespan). For indivisible tasks, we put forward an envy-free polynomial mechanism that approximates the minimal makespan to within a factor of $O(\log m)$, where m is the number of machines. This bound is almost tight, as we also show that no envy-free mechanism can achieve a better bound than $\Omega(\log m / \log\log m)$. This improves the recent result of Mu'alem [On multi-dimensional envy-free mechanisms, in Proceedings of the First International Conference on Algorithmic Decision Theory, F. Rossi and A. Tsoukias, eds., Lecture Notes in Comput. Sci. 5783, Springer, Berlin, 2009, pp. 120–131] who introduced the model and gave an upper bound of $(m+1)/2$ and a lower bound of $2-1/m$. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan. Finally, we demonstrate how our mechanism for envy-free makespan minimization can be interpreted as a market clearing problem.

We consider budget constrained combinatorial auctions where each bidder has a private value for each of the items in some subset of the items and an overall budget constraint. Such auctions capture adword auctions, where advertisers offer a bid for those adwords that (hopefully) target their intended audience, and advertisers also have budgets. It is known that even if all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality. The auction is incentive compatible with respect to the private valuations whereas the budgets and the sets of interest are assumed to be public knowledge. This extends the result of Dobzinski, Lavi and Nisan (FOCS 2008) for auctions of multiple identical items with bugets to single-valued combinatorial auctions and address one of the basic challenges on auctioning web ads (see Nisan et al, 2009, Google auctions for tv ads).

We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that approximates the minimal makespan to within a factor of O(log m), where m is the number of machines. We also show a lower bound of γ(log m / log log m). This improves the recent result of Mu'alem [22] who give an upper bound of (m+1)/2, and a lower bound of 2-1/m. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan. Finally, we demonstrate how our mechanism for envy free makespan minimization can be interpreted as a market clearing problem.

Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the experimental evidence with the first rigorous proofs of efficiency for many of the heuristics suggested over the past decade. We introduce the notion of highway dimension and show how low highway dimension gives a unified explanation for several seemingly different algorithms.

A coreset of a point set P is a small weighted set of points that captures some geometric properties of $P$. Coresets have found use in a vast host of geometric settings. We forge a link between coresets, and differentially private sanitizations that can answer any number of queries without compromising privacy. We define the notion of private coresets, which are simultaneously both coresets and differentially private, and show how they may be constructed. We first show that the existence of a small coreset with low generalized sensitivity (i.e., replacing a single point in the original point set slightly affects the quality of the coreset) implies (in an inefficient manner) the existence of a private coreset for the same queries. This greatly extends the works of Blum, Ligett, and Roth [STOC 2008] and McSherry and Talwar [FOCS 2007]. We also give an efficient algorithm to compute private coresets for k-median and k-mean queries in Red, immediately implying efficient differentially private sanitizations for such queries. Following McSherry and Talwar, this construction also gives efficient coalition proof (approximately dominant strategy) mechanisms for location problems. Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have an additive error. We present a new technique for showing lower bounds on this error.

We consider the problem of approximating a set P of n points in Rd by a collection of j-dimensional flats, andextensions thereof, under the standard median / mean / centermeasures, in which we wish to minimize, respectively, the sum of thedistances from each point of P to its nearest flat, the sum of thesquares of these distances, or the maximal such distance.Such problems cannot be approximated unless P=NP but do allowbi-criteria approximations where one allows some leeway in both the numberof flats and the quality of the objective function.We give a very simple bi-criteria approximation algorithm, which producesat most α(k,j,n) = (k j log n)O(j) flats, which exceeds the optimalobjective value for any k j-dimensional flats by a factor of nomore than β(j)= 2O(j). Given this bi-criteria approximation, wecan use it to reduce the approximation factor arbitrarily, at the costof increasing the number of flats. Our algorithm hasmany advantages over previous work, in that it is muchmore widely applicable (wider set of objective functions and classes ofclusters) and much more efficient -- reducing the running time bound from O(n Poly(k,j)) to nd · (jk)O(j).Our algorithm is randomized and successful with probability 1/2(easily boosted to probabilities arbitrary close to 1).

We consider an online version of the conflict‐free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict‐free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.

The common assumption about digital signatures is that they disallow any kind of modification on signed data. However, a more flexible approach is often needed and has been advocated lately, one in which some restricted modifications may still occur, without invalidating the data. This is made possible by offering signatures which are homomorphic with respect to some operation on the message domain. Starting from the signature(s) of some data instance(s), computed by the data owner, anybody else can derive the signature corresponding to a new data instance, if obtained only via some accepted operation from the previous one(s). More, updated signatures should be indistinguishable from the ones computed by the data owner and this updating step should be applicable as many times as needed. This paper deals with the signing of insert-only collections, in which element insertions are accepted but no removals should occur. Newly inserted elements do not have to be signed or known by the initial signer. We propose two techniques: one which transposes the insert-only problem into a delete-only one (which is already solved), and another technique based on zero-knowledge proofs. We also give performance measures and discuss applications.

We develop efficient (1 + epsiv)-approximation algorithms for generalized facility location problems. Such facilities are not restricted to being points in Ropf, and can represent more complex structures such as linear facilities (lines in Ropfd, j-dimensional flats), etc. We introduce coresets for weighted (point) facilities. These prove to be useful for such generalized facility location problems, and provide efficient algorithms for their construction. Applications include: k-mean and k-median generalizations, i.e., find k lines that minimize the sum (or sum of squares) of the distances from each input point to its nearest line. Other applications are generalizations of linear regression problems to multiple regression lines, new SVD/PCA generalizations, and many more. The results significantly improve on previous work, which deals efficiently only with special cases. Open source code for the algorithms in this paper is also available

We present lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems, and we apply such results to on-line virtual circuit and optical routing problems. Lund and Yannakakis [The approximation of maximum subgraph problems, in Proceedings of the 20th International Colloquium on Automata, Languages and Programming, 1993, pp. 40-51] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any nontrivial, hereditary property pi--e.g., independent set, planar, acyclic, bipartite. We consider the on-line version of this family of problems, where some graph G is fixed and some subgraph H of G is presented on-line, vertex by vertex. The on-line algorithm must choose a subset of the vertices of H, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property pi. Furthermore, we study the on-line version of graph coloring whose off-line version has also been shown to be inapproximable [C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, in Proceedings of the 25th ACM Symposium on Theory of Computing, 1993], on-line max edge-disjoint paths, and on-line path coloring problems. Irrespective of the time complexity, we show an Omega(n epsilon ) lower bound on the competitive ratio of randomized on-line algorithms for any of these problems. As a consequence, we obtain an Omega(n epsilon ) lower bound on the competitive ratio of randomized on-line algorithms for virtual circuit routing on general networks, in contrast to the known results for some specific networks. Similar lower bounds are obtained for on-line optical routing as well.

We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the worst case employed randomization. Our main result is the existence of deterministic auctions that approximately match the performance guarantees of these randomized auctions. We give a fairly general derandomization technique for turning any randomized mechanism into an asymmetric deterministic one with approximately the same revenue. In doing so, we bypass the impossibility result for symmetric deterministic auctions and show that asymmetry is nearly as powerful as randomization for solving optimal mechanism design problems. Our general construction involves solving an exponential-sized flow problem and thus is not polynomial-time computable. To complete the picture, we give an explicit polynomial-time construction for derandomizing a specific auction with good worst-case revenue. Our results are based on toy problems that have a flavor similar to the hat problem from [3].

The success of a P2P file-sharing network highly depends on the scalability and versatility of its search mechanism. Two particularly desirable search features are scope (ability to find infrequent items) and support for partial-match queries (queries that contain typos or include a subset of keywords). While centralized-index architectures (such as Napster) can support both these features, existing decentralized architectures seem to support at most one: prevailing unstructured P2P protocols (such as Gnutella and FastTrack) deploy a "blind" search mechanism where the set of peers probed is unrelated to the query; thus they support partial-match queries but have limited scope. On the other extreme, the recently-proposed distributed hash tables (DHTs) such as CAN and CHORD, couple index location with the item's hash value, and thus have good scope but can not effectively support partial-match queries. Another hurdle to DHTs deployment is their tight control of the overlay structure and the information (part of the index) each peer maintains, which makes them more sensitive to failures and frequent joins and disconnects. We develop a new class of decentralized P2P architectures. Our design is based on unstructured architectures such as gnutella and FastTrack, and retains many of their appealing properties including support for partial match queries, and relative resilience to peer failures. Yet, we obtain orders of magnitude improvement in the efficiency of locating rare items. Our approach exploits associations inherent in human selections to steer the search process to peers that are more likely to have an answer to the query. We demonstrate the potential of associative search using models, analysis, and simulations.

A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is not polynomial time. We give a polynomial time construction that guarantee's Racke's bounds, and more generally gives the true optimal ratio for any network.

Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online algorithms for metrical task systems on arbitrary metric spaces.

We describe mechanisms for auctions that are simultaneously truthful (alternately known as strategy-proof or incentive compatible) and guarantee high "net" profit. We make use of appropriate variants of competitive analysis of algorithms in designing and analyzing our mechanisms. Thus, we do not require any probabilistic assumptions on bids.We present two new concepts regarding auctions, that of a cancellable auction and that of a generalized auction. We use cancellable auctions in the design of generalized auctions, but they are of independent interest as well. Cancellable auctions have the property that if the revenue collected does not meet certain predetermined criteria, then the auction can be cancelled and the resulting auction is still truthful. The trivial approach (run a truthful auction and cancel if needed) yields an auction that is not necessarily truthfu.Generalized auctions can be used to model many problems previously considered in the literature, as well as numerous new problems. In particular, we give the first truthful profit-maximizing auctions for problems such as conditional financing and multicast.

We present a model for web search that captures in a unified manner three critical components of the problem: how the link structure of the web is generated, how the content of a web document is generated, and how a human searcher generates a query. The key to this unification lies in capturing the correlations between these components in terms of proximity in a shared latent semantic space. Given such a combined model, the correct answer to a search query is well defined, and thus it becomes possible to evaluate web search algorithms rigorously. We present a new web search algorithm, based on spectral techniques, and prove that it is guaranteed to produce an approximately correct answer in our model. The algorithm assumes no knowledge of the model, and is well-defined regardless of the model's accuracy.

Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster documents into areas of interest, (ii) collaborative filtering --- the reconstruction of missing data items, and (iii) determining the relative importance of documents based on citation/link structure. Intuitive arguments can explain some of the phenomena that has been observed but little theoretical study has been done. In this paper we present a model for framing data mining tasks and a unified approach to solving the resulting data mining problems using spectral analysis. These results give strong justification to the use of spectral techniques for latent semantic indexing, collaborative filtering, and web site ranking.

Unfair metrical task systems are a generalization of online metrical task systems.In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain the following results:1. Better randomized algorithms for unfair metrical task systems on the uniform metric space.2. Better randomized algorithms for metrical task systems on general metric spaces, O(log z n(log log n) 2) competitive, improving on the best previous result of O(log s n log log n).3. A tight randomized competitive ratio for the k-weighted caching problem on k+l points, O(log k), improving on the best previous result of O(log 2 k).

We give cryptographic schemes that help trace the source of leaks when sensitive or proprietary data is made available to a large set of parties. A very relevant application is in the context of pay television, where only paying customers should be able to view certain programs. In this application, the programs are normally encrypted, and then the sensitive data is the decryption keys that are given to paying customers. If a pirate decoder is found, it is desirable to reveal the source of its decryption keys. We describe fully resilient schemes which can be used against any decoder which decrypts with nonnegligible probability. Since there is typically little demand for decoders which decrypt only a small fraction of the transmissions (even if it is nonnegligible), we further introduce threshold tracing schemes which can only be used against decoders which succeed in decryption with probability greater than some threshold. Threshold schemes are considerably more efficient than fully resilient schemes.

We provide rigorous time/space trade-offs for inverting any function. Given a function f, we give a time/space trade-off of T S 2 = N 3 q (f), where q(f) is the probability that two random elements (taken with replacement) are mapped to the same image under f. We also give a more general trade-off, T S 3 = N 3 , that can invert any function at any point.

A layered graph is a connected graph whose vertices are partitioned into sets L 0 =s, L 1 , L 2 ,..., and whose edges, which have nonnegative integral weights, run between consecutive layers. Its width is $\max\{|L_i|\}$. In the on-line layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. We give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. We give a deterministic on-line algorithm which is O(9 w )-competitive on width-w graphs and prove that for no w can a deterministic on-line algorithm have a competitive ratio better than 2 w-2 on width-w graphs. We prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized on-line layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, we give a randomized on-line algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.

The access graph model for paging, defined by (Borodin et al., 1991) and studied in (Irani et al., 1992) has a number of troubling aspects. The access graph has to be known in advance to the paging algorithm and the memory required to represent the access graph itself may be very large. We present a truly online strongly competitive paging algorithm in the access graph model that does not have any prior information on the access sequence. We give both strongly competitive deterministic and strongly competitive randomized algorithms. Our algorithms need only O(k log n) bits of memory, where k is the number of page slots available and n is the size of the virtual address space, i.e., no more memory than needed to store the virtual translation tables for pages in memory. In fact, we can reduce this to O(k log k) bits using appropriate probabilistic data structures. We also extend the locality of reference concept captured by the access graph model to allow changes in the behavior of the underlying process. We formalize this by introducing the concept of an "extended access graph". We consider a graph parameter /spl Delta/ that captures the degree of change allowed. We study this new model and give algorithms that are strongly competitive for the (unknown) extended access graph. We can do so for almost all values of /spl Delta/ for which it is possible.

In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast ) where the goal is to route all requests while minimizing the required bandwidth. We concentrate on the case of Permanent virtual circuits (i.e., once a circuit is established it exists forever), and describe an algorithm that achieves on O (log n ) competitive ratio with respect to maximum congestin, where n is the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O (log n ) factor. We also show that this result is tight, that is, for any on-line algorithm there exists a scenario in which Ω(log n ) increase in bandwidth is necessary in directed networks. We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival. Assigning a job to a machine increases the machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load. For the related machines case, we describe the first algorithm that achieves constant competitive ratio. for the unrelated case (with n machines), we describe a new method that yields O (log n )-competitive algorithm. This stands in contrast to the natural greed approach, whose competitive ratio is exactly n .

Article Free Access Share on Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract) Authors: Baruch Awerbuch Johns Hopkins University and Lab. for Computer Science, MIT Johns Hopkins University and Lab. for Computer Science, MITView Profile , Yossi Azar Department of Computer Science, Tel-Aviv University, Israel Department of Computer Science, Tel-Aviv University, IsraelView Profile , Amos Fiat Department of Computer Science, Tel-Aviv University, Israel Department of Computer Science, Tel-Aviv University, IsraelView Profile , Tom Leighton Mathematics Department and Lab for Computer Science, MIT Mathematics Department and Lab for Computer Science, MITView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 519–530https://doi.org/10.1145/237814.238000Published:01 July 1996Publication History 54citation583DownloadsMetricsTotal Citations54Total Downloads583Last 12 Months24Last 6 weeks3 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

We present lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems and we apply such results to online virtual circuit and optical routing problems.Lund and Yannakakis [LY93a] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any non-trivial, hereditary, property r.E.g., independent set, planar, acyclic, bipartite, etc.We consider the on-line version of this family of problems, where some graph G is fixed and some subgraph H is presented on-line, vertex by vertex.The on-line algorithm must choose a subset of the vertices of i7, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property m.Furthermore, we study the on-line version line algorithms for any of these problems.As a consequence, we obtain an fl(n') lower bound on the competitive ratio of randomized on-line algorithms for virtual circuit routing on general networks, in contrast to the known results for some specific networks.Moreover, this lower bound holds even if the use of preemption is allowed.Similar lower bounds are obtained for on-line optical routing as well,

We model the problem of storing items in some warehouse (modeled as an undirected graph) where a server has to visit items over time, with the goal of minimizing the total distance traversed by the server. Special cases of this problem include the management of a real industrial stacker crane warehouse, automatic robot run warehouses, disk track optimization to minimize access time, managing two dimensional memory (bubble memory and mass storage systems), doubly linked list management, and the process migration problem. The static version of this problem assumes some known probability distribution on the access patterns. We initiate the study of the dynamic version of the problem, where the robot may rearrange the warehouse to deal efficiently with future events. We require no statistical assumptions on the access pattern, and give competitive algorithms that rearrange the warehouse over time to deal efficiently with the true access patterns. We give non-trivial upper bounds for the general problem, along with some interesting lower bounds. In addition, we model realistic data access patterns on disk storage by considering two practically significant scenarios: access to some database via dynamically changing alternative indices and access patterns derived from root to leaf traversals of some (unknown) tree structure. In both cases we give greatly improved competitive ratios.

This paper gives a randomized competitive distributed paging algorithm called Heat and Dump, The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to within a constant factor. This is in contrast to the linear optimal deterministic competitive ratio.>

In this paper we study an idealized problem of on-line allocation of routes to virtual circuits where the goal is to minimize the required bandwidth.For the case where virtual circuits continue to exist forever, we describe an algorithm that achieves an O (log n) competitive ratio, where n is the number of nodes in the network.Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O(log n) factor.We also show that this result is tight, i.e. for any on-line algorithm there exists a scenario in which O(log n) increase in bandwidth is necessary.We view virtual circuit routing as a generalization of an on-line scheduling problem, and hence a major part of the paper focuses on development of algorithms for non-preemptive on-line scheduling for related and unrelated machines.Specialization of routing to scheduling leads us to concentrate on scheduling in the case where jobs must be assigned immediately upon arrival; assigning a job to a machine increases this machine's load by an amount that depends both on the job and on the machine.The goal is to minimize the maximum load.For the related machines case, we describe the first algorithm that achieves constant competitive ratio.For the unrekzted case (with n machines), we describe a new method that yields O(log n)-competitive algorithm.This stands in contrast to the natural greedy approach, which we show has only a ~(n) competitive ratio.The virtual circuit routing result follows as a generalization of the unrelated machines case.

Article Competitive distributed file allocation Share on Authors: Baruch Awerbuch View Profile , Yair Bartal View Profile , Amos Fiat View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 164–173https://doi.org/10.1145/167088.167142Online:01 June 1993Publication History 82citation483DownloadsMetricsTotal Citations82Total Downloads483Last 12 Months10Last 6 weeks2 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 SiteGet Access

Given a set of n elements from the domain $\{ {1, \cdots ,m} \}$, this paper investigates how to arrange them in a table of size n, so that searching for an element in the table can be done in constant time. Yao [J. Assoc. Comput. Mach., 28(1981), pp. 615–628] has shown that this cannot be done when the domain is sufficiently large as a function of n. This paper gives a constructive solution when the domain m is polynomial in n, the number of elements, as well as a nonconstructive proof for m no larger than exponential in ${\operatorname{poly}}(n)$. The authors improve upon a result of Yao and give better bounds on the maximum m for which implicit $O(1)$ probe search can be done. The results are achieved by showing the tight relationship between hashing and certain encoding problems called rainbows.

In the unidirectional conversion problem an on-line player is given the task of converting dollars to yen over some period of time. Each day, a new exchange rate is announced and the player must decide how many dollars to convert. His goal is to minimize the competitive ratio. defined as sup/sub E/ (P/sub OPT/(E)/P/sub X/E) where E ranges over exchange rate sequences. P/sub OPT/(E) is the number of yen obtained by an optimal off-line algorithm, and Px(E) is the number of yen obtained by the on-line algorithm X. The authors also consider a continuous version of the problem. in which the exchange rate varies over a continuous time interval. The on-line line players a priori information about the fluctuation of exchange rates distinguishes different variants of the problem. For three variants they show that a simple threat-based strategy is optimal for the on-line player and determine its competitive ratio. They also derive and analyze an optimal policy for the on-line player when he knows the probability distribution of the maximum value that the exchange rate will reach. Finally, they consider a bidirectional conversion problem, which the player may trade dollars for yen or yen for dollars.>

We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the make span, the completion time of the last job. In the on-line version, as soon as job j arrives, it must be assigned immediately to one of the m machines.

We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([C], [DF], [ML]), where copies of a file may be stored in the local storage of some subset of processors, copies may be replicated and discarded over time so as to optimize communication costs, but multiple copies must be kept consistent and at least one copy must be stored somewhere in the network at all times. We deal with competitive algorithms for minimizing communication costs, over arbitrary sequences of reads and writes, and arbitrary network topologies. We define the constrained file allocation problem to be the solution of many individual file allocation problems simultaneously, subject to the constraints of local memory size. We give competitive algorithms for this prblem on uniform networks. We then introduce distributed competitive algorithms for on-line data tracking (a generalization of mobile user tracking [AP1, AP3] to transform our competitive distributed data management algorithms into distributed algorithms themselves.

Nonoblivious hashing, where information gathered from unsuccessful probes is used to modify subsequent probe strategy, is introduced and used to obtain the following results for static lookup on full tables: (1) An O (1)-time worst-case scheme that uses only logarithmic additional memory, (and no memory when the domain size is linear in the table size), which improves upon previously linear space requirements. (2) An almost sure O (1)-time probabilistic worst-case scheme, which uses no additional memory and which improves upon previously logarithmic time requirements. (3) Enhancements to hashing: (1) and (2) are solved for multikey recors, where search can be performed under any key in time O (1); these schemes also permit properties, such as nearest neighbor and rank, to be determined in logarithmic time.

A layered graph is a connected, weighted graph whose vertices are partitioned into sets L/sub 0/=(s), L/sub 1/, L/sub 2/, . . ., and whose edges run between consecutive layers. Its width is max( mod L/sub i/ mod ). In the online layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. The authors give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. They give a deterministic online algorithm that is O(9w)-competitive on width-w graphs and prove that for no w can a deterministic online algorithm have a competitive ratio better than 2w/sup -2/ on width-w graphs. They prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized online layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, they give a randomized online algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.>

Article Free Access Share on Rigorous time/space tradeoffs for inverting functions Authors: Amos Fiat Tel-Aviv Univ., Tel-Aviv Univ., Israel Tel-Aviv Univ., Tel-Aviv Univ., IsraelView Profile , Moni Naor IBM, Almaden Research Center IBM, Almaden Research CenterView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 534–541https://doi.org/10.1145/103418.103473Published:03 January 1991Publication History 25citation443DownloadsMetricsTotal Citations25Total Downloads443Last 12 Months78Last 6 weeks14 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

Deterministic competitive k-server algorithms are given for all k and all metric spaces. This settles the k-server conjecture of M.S. Manasse et al. (1988) up to the competitive ratio. The best previous result for general metric spaces was a three-server randomized competitive algorithm and a nonconstructive proof that a deterministic three-server competitive algorithm exists. The competitive ratio the present authors can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open. The methods set forth here also give competitive algorithms for a natural generalization of the k-server problem, called the k-taxicab problem.>

Planning is defined as the problem of synthesizing a desired behavior from given basic operations, and learning is defined as the dual problem of analyzing a given behavior to determine the unknown basic operations. Algorithms for solving these problems in the context of invertible operations on finite-state environments are developed. In addition to their obvious artificial intelligence applications, the algorithms can efficiently find the shortest way to solve Rubik's cube, test ping-pong protocols, and solve systems of equations over permutation groups.>

Given a set of n elements from the domain 1, …, m, we investigate how to arrange them in a table of size n, so that searching for an element in the table can be done in constant time.

Abstract Consider a “sea” of M squares which contains (at some unknown location) a “battleship” of K squares. Both the sea and the battleship can assume any rectangular shape. Our goal is to find the battleship by probing at least one of its squares. In this paper we describe a deterministic strategy for this problem which is guaranteed to locate the battleship in at most c1 M/K probes, where c1 ≈︁ 3.065.

Non-oblivious hashing, where the information gathered by performing “unsuccessful” probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables:

We describe an implicit data structure for n multikey records that supports searching for a record, under any key, in the asymptotically optimal search time Ο(log n). This improves on [Mun87] in which Munro describes an implicit data structure for the problem of storing n k-key records so that search on any key can be performed in Ο(logk n(log log n)k-1) comparisons. The theoretical tools we develop also yield practical schemes that either halve the number of memory references over obvious solutions to the non-implicit version of the problem, or alternatively reduce the number of pointers involved significantly.

In this paper we extend the notion of zero knowledge proofs of membership (which reveal one bit of information) to zero knowledge proofs of knowledge (which reveal no information whatsoever). After formally defining this notion, we show its relevance to identification schemes, in which parties prove their identity by demonstrating their knowledge rather than by proving the validity of assertions. We describe a novel scheme which is provably secure if factoring is difficult and whose practical implementations are about two orders of magnitude faster than RSA-based identification schemes. In the last part of the paper we consider the question of sequential versus parallel executions of zero knowledge protocols, define a new notion of “transferable information”, and prove that the parallel version of our identification scheme (which is not known to be zero knowledge) is secure since it reveals no transferable information.

This paper proposes a novel architecture for massively parallel systolic computers, which is based on results from lattice theory. In the proposed architecture, each processor is connected to four other processors via constant-lenght wires in an regular borderless pattern. The mapping of processes to processors is continuous, and the architecture guarantees exceptional load uniformity for rectangular process arrays of arbitrary sizes. In addition, no timesharing is ever required when the ration of processes to processors is smaller than 1//spl radic/5.

Storage media such as digital optical discs, PROM's, or punched cards consist of a number of write-once bit positions (WIT's); each WIT initially contains a "0" that may later be irreversibly overwritten with a "r'. Rivest and Shamir have shown that such write-once memories (WOM's) can be reused very efficiently. Generalized WOM's are considered, in which the basic storage element has more than two possible states and the legal state transitions are described by an arbitrary directed acyclic graph. The capabilities of such memories depend on the depth of the graphs rather than on their size, and the decision problem associated with the generalized WOM's in NP-hard even for3-ary symbols rewritten several times or multiple values rewritten once.