Arrow Research search

Author name cluster

Amos Fiat

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

59 papers
2 author rows

Possible papers

59

AIJ Journal 2024 Journal Article

An α-regret analysis of adversarial bilateral trade

  • Yossi Azar
  • Amos Fiat
  • Federico Fusco

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.

Details DOI

AAAI Conference 2022 Conference Paper

Almost Full EFX Exists for Four Agents

  • Ben Berger
  • Avi Cohen
  • Michal Feldman
  • Amos Fiat

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.

PDF Details

NeurIPS Conference 2022 Conference Paper

An $\alpha$-regret analysis of Adversarial Bilateral Trade

  • Yossi Azar
  • Amos Fiat
  • Federico Fusco

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.

PDF Details

AAMAS Conference 2019 Conference Paper

Efficient Allocation of Free Stuff

  • Yossi Azar
  • Allan Borodin
  • Michal Feldman
  • Amos Fiat
  • Kineret Segal

We study online matching settings with selfish agents when everything is free. Inconsiderate agents break ties arbitrarily amongst equal maximal value available choices, even if the maximal value is equal to zero. Even for the simplest case of zero/one valuations, where agents arrive online in an arbitrary order, and agents are restricted to taking at most one item, the resulting social welfare may be negligible for a deterministic algorithm. This may be surprising when contrasted with the 1/2 approximation of the greedy algorithm, analogous to this setting, except that agents are considerate (i. e. , they don’t take zero-valued items). We overcome this challenge by introducing a new class of algorithms, which we refer to as prioritization algorithms. We show that upgrading a random subset of the agents to “business class" already improves the approximation to a constant. For more general valuations, we achieve a constant approximation using logn priority classes, when the valuations are known in advance. We extend these results to settings where agents have additive valuations and are restricted to taking up to some q ≥ 1 items. Our results are tight up to a constant.

PDF

SODA Conference 2017 Conference Paper

(1 + ∊)-Approximate f -Sensitive Distance Oracles

  • Shiri Chechik
  • Sarel Cohen
  • Amos Fiat
  • Haim Kaplan

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 n 2+0(1) For comparison, the naive alternative requires m f n 2 space for sublinear query time.

Details

SODA Conference 2016 Conference Paper

Packing Small Vectors

  • Yossi Azar
  • Ilan Reuven Cohen
  • Amos Fiat
  • Alan Roytman

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.

Details

AAAI Conference 2016 Conference Paper

Variations on the Hotelling-Downs Model

  • Michal Feldman
  • Amos Fiat
  • Svetlana Obraztsova

In this paper we expand the standard Hotelling-Downs model (Hotelling 1929; Downs 1957) 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.

PDF Details

I&C Journal 2015 Journal Article

Minimal indices for predecessor search

  • Sarel Cohen
  • Amos Fiat
  • Moshik Hershcovitch
  • Haim Kaplan

We give a new predecessor data structure which improves upon the index size of the Pǎtraşcu–Thorup data structures, reducing the index size from O ( n w 4 / 5 ) bits to O ( n log ⁡ w ) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra O ( log ⁡ w ) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of O ( n log ⁡ w ) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree w / log ⁡ w (compared to w 1 / 5 of a fusion tree node). To construct these indices we device highly efficient bit selectors which, we believe, are of independent interest.

Details DOI

SODA Conference 2015 Conference Paper

Pricing Online Decisions: Beyond Auctions

  • Ilan Reuven Cohen
  • Alon Eden
  • Amos Fiat
  • Lukasz Jez

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.

Details

MFCS Conference 2013 Conference Paper

Minimal Indices for Successor Search - (Extended Abstract)

  • Sarel Cohen
  • Amos Fiat
  • Moshik Hershcovitch
  • Haim Kaplan

Abstract We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from O ( n w 4/5 ) bits to O ( n log w ) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z -fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra O (log w ) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of O ( n log w ) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree w /log w (compared to the w 1/5 out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.

Details

SODA Conference 2010 Conference Paper

Highway Dimension, Shortest Paths, and Provably Efficient Algorithms

  • Ittai Abraham
  • Amos Fiat
  • Andrew V. Goldberg
  • Renato F. Werneck

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.

Details

STOC Conference 2009 Conference Paper

Private coresets

  • Dan Feldman
  • Amos Fiat
  • Haim Kaplan
  • Kobbi Nissim

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 Re d , 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.

Details

TCS Journal 2006 Journal Article

An improved algorithm for online coloring of intervals with bandwidth

  • Yossi Azar
  • Amos Fiat
  • Meital Levy
  • N.S. Narayanaswamy

We present an improved online algorithm for coloring interval graphs with bandwidth. This problem has recently been studied by Adamy and Erlebach and a 195-competitive online strategy has been presented. We improve this by presenting a 10-competitive strategy. To achieve this result, we use variants of an optimal online coloring algorithm due to Kierstead and Trotter.

Details DOI

FOCS Conference 2006 Conference Paper

Coresets forWeighted Facilities and Their Applications

  • Dan Feldman
  • Amos Fiat
  • Micha Sharir

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 Ropf d, 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

Details

TCS Journal 2006 Journal Article

Correlation clustering in general weighted graphs

  • Erik D. Demaine
  • Dotan Emanuel
  • Amos Fiat
  • Nicole Immorlica

We consider the following general correlation-clustering problem [N. Bansal, A. Blum, S. Chawla, Correlation clustering, in: Proc. 43rd Annu. IEEE Symp. on Foundations of Computer Science, Vancouver, Canada, November 2002, pp. 238–250]: given a graph with real nonnegative edge weights and a 〈 + 〉 / 〈 - 〉 edge labelling, partition the vertices into clusters to minimize the total weight of cut 〈 + 〉 edges and uncut 〈 - 〉 edges. Thus, 〈 + 〉 edges with large weights (representing strong correlations between endpoints) encourage those endpoints to belong to a common cluster while 〈 - 〉 edges with large weights encourage the endpoints to belong to different clusters. In contrast to most clustering problems, correlation clustering specifies neither the desired number of clusters nor a distance threshold for clustering; both of these parameters are effectively chosen to be the best possible by the problem definition. Correlation clustering was introduced by Bansal et al. [Correlation clustering, in: Proc. 43rd Annu. IEEE Symp. on Foundations of Computer Science, Vancouver, Canada, November 2002, pp. 238–250], motivated by both document clustering and agnostic learning. They proved NP-hardness and gave constant-factor approximation algorithms for the special case in which the graph is complete (full information) and every edge has the same weight. We give an O ( log n ) -approximation algorithm for the general case based on a linear-programming rounding and the “region-growing’’ technique. We also prove that this linear program has a gap of Ω ( log n ), and therefore our approximation is tight under this approach. We also give an O ( r 3 ) -approximation algorithm for K r, r -minor-free graphs. On the other hand, we show that the problem is equivalent to minimum multicut, and therefore APX-hard and difficult to approximate better than Θ ( log n ).

Details DOI

STOC Conference 2005 Conference Paper

Derandomization of auctions

  • Gagan Aggarwal
  • Amos Fiat
  • Andrew V. Goldberg
  • Jason D. Hartline
  • Nicole Immorlica
  • Madhu Sudan 0001

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

Details

TCS Journal 2004 Journal Article

WITHDRAWN: Foreword

  • Sandy Irani
  • Amos Fiat

This article has been withdrawn at the request of the author(s) and/or editor. The Publisher apologizes for any inconvenience this may cause. The full Elsevier Policy on Article Withdrawal can be found at http: //www. elsevier. com/locate/withdrawalpolicy

Details DOI

I&C Journal 2003 Journal Article

Competitive distributed file allocation

  • Baruch Awerbuch
  • Yair Bartal
  • Amos Fiat

This paper deals with the file allocation problem [6] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file re-allocation strategy that adapts on-line to a sequence of read and write requests whose location and relative frequencies are completely unpredictable. This is achieved by replicating the file in response to read requests and migrating the file in response to write requests while paying the associated communications costs, so as to be closer to processors that access it frequently. We develop first explicit deterministic on-line strategy assuming existence of global information about the state of the network; previous (deterministic) solutions were complicated and more expensive. Our solution has (optimal) logarithmic competitive ratio. The paper also contains the first explicit deterministic data migration [7] algorithm achieving the best known competitive ratio for this problem. Using somewhat different technique, we also develop the first deterministic distributed file allocation algorithm (using only local information) with poly-logarithmic competitive ratio against a globally optimized optimal prescient strategy.

Details DOI

STOC Conference 2003 Conference Paper

Optimal oblivious routing in polynomial time

  • Yossi Azar
  • Edith Cohen
  • Amos Fiat
  • Haim Kaplan
  • Harald Räcke

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.

Details

STOC Conference 2002 Conference Paper

Competitive generalized auctions

  • Amos Fiat
  • Andrew V. Goldberg
  • Jason D. Hartline
  • Anna R. Karlin

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.

Details

MFCS Conference 2001 Invited Paper

Some Recent Results on Data Mining and Search

  • Amos Fiat

Abstract In this talk we review and survey some recent work and work in progress on data mining and web search. We discuss Latent Semantic Analysis and give conditions under which it is robust. We also consider the problem of collaborative filtering and show how spectral techniques can give a rigorous and robust justification for doing so. We consider the problems of web search and show how both Google and Klienberg’s algorithm are robust under a model of web generation, and how this model can be reasonably extended. We then give an algorithm that provably gives the correct result in this extended model. The results surveyed are joint work with Azar, Karlin, McSherry and Saia [ 2 ], and Achlioptas, Karlin and McSherry [ 1 ].

Details

STOC Conference 2001 Conference Paper

Spectral analysis of data

  • Yossi Azar
  • Amos Fiat
  • Anna R. Karlin
  • Frank McSherry
  • Jared Saia

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.

Details

FOCS Conference 2001 Conference Paper

Web Search via Hub Synthesis

  • Dimitris Achlioptas
  • Amos Fiat
  • Anna R. Karlin
  • Frank McSherry

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.

Details

FOCS Conference 1997 Conference Paper

Truly Online Paging with Locality of Reference

  • Amos Fiat
  • Manor Mendel

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.

Details

FOCS Conference 1995 Conference Paper

Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version)

  • Amos Fiat
  • Yishay Mansour
  • Adi Rosén
  • Orli Waarts

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.

Details

TCS Journal 1994 Journal Article

Competitive algorithms for the weighted server problem

  • Amos Fiat
  • Moty Ricklin

In this paper we deal with a generalization of the k-server problem (Manasse 1988), in which the servers are unequal. In the weighted server model each of the servers is assigned a positive weight. The cost associated with moving a server equals the product of the distance traversed and the server weight. A weighted k-server algorithm is called competitive if the competitive ratio depends only upon the number of servers (i. e. , the competitive ratio is independent of the weights associated with the servers and the number of points in the metric space). For the uniform metric space, we give super exponential 22O(k) -competitive algorithms for any set of weights. If the servers have one of two possible weights, we give deterministic exponential (k O(k)) competitive algorithms and randomized polynomial Õ(k 3) competitive algorithms. We use the MIN operator for both algorithms. This is the first true application of the randomized MIN operator (Fiat 1991). We show that for any metric space there exists some set of weights such that the deterministic competitive ratio must be exponential (k Ω(k)). If the servers are limited to be one of two possible weights then there exist two such weights such that the competitive ratio has a lower bound of 2Ω(k). With the randomized upper bound above, this shows a clear separation between deterministic and randomized algorithms for the problem of two weights. One can model the problem of storage management for RAM and E2PROM type memories as a weighted server problem with two weights on the uniform metric space.

Details DOI

FOCS Conference 1993 Conference Paper

Heat & Dump: Competitive Distributed Paging

  • Baruch Awerbuch
  • Yair Bartal
  • Amos Fiat

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

Details

FOCS Conference 1992 Conference Paper

Competitive Analysis of Financial Games

  • Ran El-Yaniv
  • Amos Fiat
  • Richard M. Karp
  • G. Turpin

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

Details

FOCS Conference 1991 Conference Paper

Competitive Algorithms for Layered Graph Traversal

  • Amos Fiat
  • Dean P. Foster
  • Howard J. Karloff
  • Yuval Rabani
  • Yiftach Ravid
  • Sundar Vishwanathan

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

Details

FOCS Conference 1990 Conference Paper

Competitive k-Server Algorithms (Extended Abstract)

  • Amos Fiat
  • Yuval Rabani
  • Yiftach Ravid

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

Details

STOC Conference 1989 Conference Paper

Implicit O(1) Probe Search

  • Amos Fiat
  • Moni Naor

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.

Details

FOCS Conference 1989 Conference Paper

Planning and Learning in Permutation Groups

  • Amos Fiat
  • Shahar Moses
  • Adi Shamir
  • Ilan Shimshoni
  • Gábor Tardos

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

Details

STOC Conference 1987 Conference Paper

Zero Knowledge Proofs of Identity

  • Uriel Feige
  • Amos Fiat
  • Adi Shamir

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.

Details

FOCS Conference 1984 Conference Paper

Polymorphic Arrays: A Novel VLSI Layout for Systolic Computers

  • Amos Fiat
  • Adi Shamir

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.

Details
v2026.09.13