Envy, Multi Envy, and Revenue Maximization (2009)
We study the envy free pricing problem faced by a seller who wishes to maximize revenue by setting prices for bundles of items. If there is an unlimited supply of items and agents are single minded...
Envy-Free Makespan Approximation (2009)
Cohen, Edith, Feldman, Michal, Fiat, Amos, Kaplan, Haim, Olonetsky, Svetlana
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...
Strong Price of Anarchy for Machine Load Balancing (2008)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
Correlation Clustering in General Weighted Graphs (2008)
Erik D. Demaine, Dotan Emanuel, Amos Fiat, Nicole Immorlica
We consider the following general correlation-clustering problem [1]: given a graph with real nonnegative edge weights and a 〈+〉/〈− 〉 edge labeling, partition the vertices into clusters to...
Amos Fiat, Jared Saia, Thomas Hobbes, Rene Descartes, Francis Bacon, Benedict Spinoza, ...
We present a censorship resistant peer-to-peer Content Addressable Network for accessing n data items in a network of n nodes. Each search for a data item in the network takes O(log n) time and...
Abstract Matching nuts and bolts (Extended Abstract) (2008)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to find the corresponding pairs of bolts and nuts. The procedure uses our...
Efficient Contention Resolution Protocols for Selfish Agents (2008)
Amos Fiat, Yishay Mansour, Uri Nadav
“Alright people, listen up. The harder you push, the faster we will all get out of here.” Police Chief Wiggum to crowd in post office at tax filing deadline — The Simpsons We seek to understand...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
Abstract Online Conflict-Free Coloring for Intervals (2008)
Amos Fiat, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, ...
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...
Abstract Matching nuts and bolts (Extended Abstract) (2008)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan
We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to nd the corresponding pairs of bolts and nuts. The procedure uses our...
Efficient Sequences of Trials Edith Cohen \Lambda (2008)
An incompetent attorney can delay a trial for months or years. A competent attorney can delay one even longer.
Strong Price of Anarchy for Machine Load Balancing (2008)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load...
Competitive Queue Management for Latency Sensitive Packets (2008)
Fiat, Amos, Mansour, Yishay, Nadav, Uri
queue management. An online sequence of packets arrive, each of which has an associated intrinsic value. Packets can be accepted to a FIFO queue, or discarded. The profit gained by transmitting a...
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank Mcsherry. Web, In Moni Naor, Proceedings Of The
[2] Nasreen AbdulJaleel and Yan Qu. Domain term extraction and struc-turing via link analysis. In Dunja Mladenic, Natasha Milic-Frayling, and
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-topoint and multicast) where the goal is to minimize the required bandwidth. We concentrate on the...
Competitive Algorithms for On-line Set Cover or How to Beat Murphy's Law (2007)
Baruch Awerbuch, Yossi Azar, Amos Fiat
This paper considers an on-line optimization version of the set cover problem. We present a optimally competitive on-line randomized algorithm which is O(logn log m) competitive where n is the...
Competitive Distributed File Allocation (Extended Abstract) (2007)
Baruch Awerbuch, Yair Bartal, Amos Fiat
) Baruch Awerbuch Yair Bartal y Amos Fiat y Abstract This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a...
Abstract. We study impurity-based decision tree algorithms such as CART, C4.5, etc., so as to better understand their theoretical underpinnings. We consider such algorithms on special forms of...
Abstract Dynamically Fault-Tolerant Content Addressable Networks (2007)
Jared Saia, Amos Fiat, Steve Gribble, Anna R. Karlin, Stefan Saroiu
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an...
The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et al. introduced the access graph model for the paging problem, which attempts to...
Provable Unlinkability Against Tra#c Analysis (2007)
Ron Berman, Amos Fiat, Amnon Ta-shma
Chaum ([Cha79, Cha81]) suggested a simple and e#cient protocol aimed at providing anonymity in the presence of an adversary watching all communication links. Chaum's protocol is known to be...
Abstract. We study impurity-based decision tree algorithms such as CART, C4.5, etc., so as to better understand their theoretical underpinnings. We consider such algorithms on special forms of...
Competitive Queue Management for Latency Sensitive Packets (2007)
Amos Fiat, Yishay Mansour, Uri Nadav, Dante Alighieri
For who knows most, him loss of time most grieves
Efficient Contention Resolution Protocols for Selfish Agents (2007)
Amos Fiat, Yishay Mansour, Uri Nadav
“Alright people, listen up. The harder you push, the faster we will all get out of here.” Police Chief Wiggum to crowd in post office at tax filing deadline — The Simpsons We seek to understand...
Strong Price of Anarchy for Machine Load Balancing (2007)
Fiat, Amos, Levy, Meital, Kaplan, Haim, Olonetsky, Svetlana
As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load balancing on...
Truly Online Paging with Locality of Reference (2006)
The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model, which attempts to capture the locality...
Digital Signatures for Modifiable Collections (2006)
Abiteboul, Serge, Cautis, Bogdan, Fiat, Amos, Milo, Tova
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...
Censorship Resistant Peer-to-Peer Networks (2006)
Amos Fiat, Jared Saia, Thomas Hobbes, René Descartes, Francis Bacon, Benedict Spinoza, ...
Abstract: We present a censorship resistant peer-to-peer network for accessing n data items in a network of n nodes. Each search for a data item in the network takes O(logn) time and requires at most...
On the price of stability for designing undirected networks with fair cost allocations (2006)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. In this paper we address the open problem of bounding the price of stability for network design with fair cost allocation for undirected graphs posed in [1]. We consider the case where...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel
Abstract. 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...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
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...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
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...
Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan
We study the problem of designing seller optimal auctions. Prior to this work, the only previously known auctions that are approximately optimal in worst case employ randomization. Our main result is...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Ji Rí, Matou Sek, ...
Abstract. 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...
On the price of stability for designing undirected networks with fair cost allocations (2006)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo
Abstract. In this paper we address the open problem of bounding the price of stability for network design with fair cost allocation for undirected graphs posed in [1]. For the version of this problem...
Making chord robust to byzantine attacks (2005)
Amos Fiat, Jared Saia, Maxwell Young
Abstract. Chord is a distributed hash table (DHT) that requires only O(logn) links per node and performs searches with latency and message cost O(logn), where n is the number of peers in the network....
Provable Anonymity Against Traffic Analysis ∗ (2005)
Ron Berman, Amos Fiat, Amnon Ta-shma
With the advent of peer to peer networks, anonymity is grasped as a desired property of any well designed system for exchanging information between parties. Previous work dealing with anonymity and...
Making chord robust to byzantine attacks (2005)
Amos Fiat, Jared Saia, Maxwell Young
That which is not good for the swarm is not good for the bee either.
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
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...
Web content is under attack by state and corporate efforts to censor it, for political and... (2004)
Amos Fiat, Jared Saia, Thomas Hobbes, Rene Descartes, Francis Bacon, Benedict Spinoza, ...
Abstract: We present a censorship resistant peer-to-peer network for accessing n data items in a network of n nodes. Each search for a data item in the network takes O(logn) time and requires at most...
Provable Unlinkability against Traffic Analysis (2004)
Ron Berman, Amos Fiat, Amnon Ta-shma
Abstract. Chaum [1, 2] suggested a simple and efficient protocol aimed at providing anonymity in the presence of an adversary watching all communication links. Chaum’s protocol is known to be...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
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...
Optimal oblivious routing in polynomial time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately,...
Efficient Sequences of Trials (2003)
Edith Cohen, Amos Fiat, Haim Kaplan, Evelle J. Younger, La Times
We introduce a problem called sequential trial optimization, a generalization of the well studied set cover problem with a new objective function. We give a simple algorithm that achieves a constant...
Optimal Oblivious Routing in Polynomial Time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke's...
Online companion caching (2002)
Amos Fiat, Manor Mendel, Steven S. Seiden
Steve Seiden died in a tragic accident on June 11, 2002. The other authors would like to dedicate this paper to his memory. Abstract. This paper is concerned with online cachingalgorithms for the (n,...
Competitive Generalized Auctions (2002)
Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, A. Alfred Taubman
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...
the World Wide Web. comment, Science, 287:2115a, 2000. (2001)
Webgraph Papers, Daniel M. Abrams, Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank Mcsherry, ...
In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 171–180, 2000. [12] William Aiello, Fan R. K. Chung, and Linyuan Lu. Random evolution
Spectral analysis of data (2001)
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank Mcsherry, Jared Saia
Every action must be due to one or other of seven causes: chance, nature, compulsion, habit, reasoning, anger, or appetite.
Spectral Analysis of Data (2001)
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...
Web search via hub synthesis (2001)
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank Mcsherry
Small have continual plodders ever won save base authority from others books. — William Shakespeare, Loves Labours Lost. Act i. Sc. 1. They define themselves in terms of what they oppose. —...
Rigorous Time/Space Tradeoffs for Inverting Functions (2000)
We provide rigorous time-space tradeoffs for inverting any function. Given a function f , we give a time space tradeoff of TS 2 = N 3 q(f ), where q(f) is the probability that two random elements are...
Dynamic Traitor Tracing (1999)
Amos Fiat, Tamir Tassa, Communicated Jacques Stern
Abstract. Traitor tracing schemes were introduced to combat the typical piracy scenario whereby pirate decoders (or access control smartcards) are manufactured and sold by pirates to illegal...
Dynamic Traitor Tracing (1999)
. Traitor tracing schemes were introduced so as to combat the typical piracy scenario whereby pirate decoders (or access control smartcards) are manufactured and sold by pirates to illegal...
Refined Locality of Reference for Paging (1998)
In this paper we refine the locality of reference concept captured by the access graph model to allow temporal changes in the behavior of the underlying process. We formalize this by introducing the...
Competitive Algorithms For Layered Graph Traversal (1998)
Amos Fiat, Dean P. Foster, Howard Karloff, Yuval Rabani
.<F3.84e+05> A layered graph is a connected graph whose vertices are partitioned into sets<F3.379e+05> L<F2.724e+05> 0<F3.84e+05>...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
. 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...
Experimental Studies of Access Graph Based Heuristics: Beating the LRU standard? (1997)
In this paper we devise new paging heuristics motivated by the access graph model of paging [2]. Unlike the access graph model [2, 9, 4] and the related Markov paging model [11] our heuristics are...
Truly Online Paging with Locality of Reference (1997)
The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model for the paging problem, which attempts...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
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...
Experimental Studies of Access Graph Based Heuristics: Beating the LRU Standard? (1997)
In this paper we devise new paging heuristics motivated by the access graph model of paging [2]. Unlike the access graph model [2, 7, 4] and the related Markov paging model [8] our heuristics are...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
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 minimize the required bandwidth. We concentrate on the...
We present a variant of the RSA algorithm called Batch RSA with two important properties: • The cost per private operation is exponentially smaller than other number theoretic schemes ([9,...
On-line Competitive Algorithms for Call Admission in Optical Networks (1996)
Baruch Awerbuch, Yossi Azar, Amos Fiat, Stefano Leonardi, Adi Rosén
In the present work we study the on-line call admission problem in optical networks. We present a general technique to deal with the problem of call admission and wavelength selection by reducing...
Randomized Robot Navigation Algorithms (1996)
Piotr Berman, Avrim Blum, Amos Fiat, Howard Karloff, Adi Rosén, Michael Saks
We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot...
Packet Routing via Min-Cost Circuit Routing (1996)
Baruch Awerbuch, Yossi Azar, Amos Fiat
In this paper we initiate the study of competitive on-line packet routing algorithms. At any time, any network node may initiate sending a packet to another node. Our goal is to route these packets...
Distributed Paging for General Networks (1996)
Baruch Awerbuch, Yair Bartal, Amos Fiat
Distributed paging [BFR92, ABF93b, AK95] deals with the dynamic allocation of copies of files in a distributed network as to minimize the total communication cost over a sequence of read and write...
Yair Bartal, Amos Fiat, Stefano Leonardi
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...
Competitive Access Time via Dynamic Storage Rearrangement (1995)
Amos Fiat, Yishay Mansour, Adi Rosén, Orli Waarts
We deal with a natural generalization of one of the seminal problems in the study of on-line computation, list management [ST85a, IRSW91, Irani91]. We consider a doubly linked list with a pointer...
Competitive Access Time via Dynamic Storage Rearrangement (1995)
Amos Fiat, Yishay Mansour, Adi Rosen, 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...
Matching Nuts and Bolts (Extended Abstract) (1994)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon y Manuel Blum z Amos Fiat x Sampath Kannan -- Moni Naor k Rafail Ostrovsky Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of...
Competitive Concurrent Distributed Data Structures (1994)
Baruch Awerbuch, Yair Bartal, Amos Fiat, Rainer Gawlick
this paper are ffl definition of semantics and complexity measures for distributed data structure for concurrent asynchrnous distributed directory access.
Distributively-Competitive Online Paging for Arbitrary-Topology Networks (Extended Abstract) (1994)
Baruch Awerbuch, Yair Bartal, Amos Fiat
) Baruch Awerbuch Yair Bartal y Amos Fiat y May 3, 1994 Abstract This paper gives first competitive distributed paging algorithm for the general network topology. The competitive ratios in storage...
Matching Nuts and Bolts (1994)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon Manuel Blum y Amos Fiat z Sampath Kannan x Moni Naor -- Rafail Ostrovsky k Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of...
Implicit O(1) probe search (1993)
Given a set of n elements from the domain f1; : : : ; mg, 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. Yao...
Competitive Distributed File Allocation (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file...
Heat & Dump: Competitive Distributed Paging (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper gives a randomized competitive distributed paging algorithm called Heat & Dump. The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to...
Competitive Distributed File Allocation (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file...
Competitive Algorithms for Distributed Data Management (1992)
Yair Bartal, Amos Fiat, Yuval Rabani
We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([DF], [ML]), where copies of a file may be be stored in...
Competitive Algorithms for Distributed Data Management (1992)
Yair Bartal, Amos Fiat, Yuval Rabani
We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([DF], [ML]), where copies of a file may be be stored in...
Competitive Paging Algorithms (1991)
Amos Fiat, Richard M. Brp, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...
Competitive k-Server Algorithms (1990)
Amos Fiat, Yuval Rabani, Yiftach Ravid
In this paper we give deterministic competitive k-server algorithms for all k and all metric spaces. This settles the k-server conjecture [MMS] up to the competitive ratio. The best previous result...
Competitive k-Server Algorithms (1990)
Amos Fiat, Yuval Rabani, Yiftach Ravid
In this paper we give deterministic competitive k-server algorithms for all k and all metric spaces. This settles the k-server conjecture [MMS] up to the competitive ratio. The best previous result...
JOURNAL OF ALGORITHMS 12,685-699 (1991) Competitive Paging Algorithms (1988)
Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. Mcgeoch, Daniel D. Sleator, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...
How to prove yourself: Practical solutions to identification and signature problems (1987)
In this paper we describe simple identification and signature schemes which enable any user to prove his identity and the authenticity of his messages to any other user without shared or public keys....
Competitive Algorithms for Distributed Data Management
Yair Bartal, Amos Fiat, Yuval Rabani
We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([DF], [ML]), where copies of a file may be be stored in...