Yair Bartal

According to our database1, Yair Bartal authored at least 78 papers between 1992 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2020
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Approximate nearest neighbor search for p-spaces (2 (DOI)
Theor. Comput. Sci., 2019

On notions of distortion and an almost minimum spanning tree with constant average distortion.
J. Comput. Syst. Sci., 2019

Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces.
CoRR, 2019

Dimensionality reduction: theoretical perspective on practical measures.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Covering Metric Spaces by Few Trees.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Approximate Nearest Neighbor Search for \ell _p -Spaces (2 via Embeddings.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2016
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme.
SIAM J. Comput., 2016

Dimension Reduction Techniques for ℓp (1 (DOI)
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp.
SIAM J. Discret. Math., 2015

Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion.
SIAM J. Comput., 2015

Approximate nearest neighbor search for ℓp-spaces (2 < p < ∞) via embeddings.
CoRR, 2015

Local Embeddings of Metric Spaces.
Algorithmica, 2015

2014
Volume in General Metric Spaces.
Discret. Comput. Geom., 2014

Dimension reduction techniques for ℓp, 1 ≤ p < ∞, with applications.
CoRR, 2014

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
Bandwidth and low dimensional embedding.
Theor. Comput. Sci., 2013

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp, p>2.
CoRR, 2013

A Linear Time Approximation Scheme for Euclidean TSP.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2011
Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Fast, precise and dynamic distance queries.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2009
Universal Immersion Spaces for Edge-Colored Graphs and Nearest-Neighbor Metrics.
SIAM J. Discret. Math., 2009

On low dimensional local embeddings.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Embedding metric spaces in their intrinsic dimension.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Nearly Tight Low Stretch Spanning Trees.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2006
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing.
SIAM J. Comput., 2006

Ramsey-type theorems for metric spaces with applications to online problems.
J. Comput. Syst. Sci., 2006

Advances in metric embedding theory.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

On the Value of Preemption in Scheduling.
Proceedings of the Approximation, 2006

2005
Randomized k-server algorithms for growth-rate bounded graphs.
J. Algorithms, 2005

Some Low Distortion Metric Ramsey Problems.
Discret. Comput. Geom., 2005

Metric Embeddings with Relaxed Guarantees.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Firmato: A novel firewall management toolkit.
ACM Trans. Comput. Syst., 2004

On the competitive ratio of the work function algorithm for the k-server problem.
Theor. Comput. Sci., 2004

On-line generalized Steiner problem.
Theor. Comput. Sci., 2004

Multiembedding of Metric Spaces.
SIAM J. Comput., 2004

Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control.
SIAM J. Comput., 2004

Low dimensional embeddings of ultrametrics.
Eur. J. Comb., 2004

Multi-Embedding of Metric Spaces
CoRR, 2004

Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.
Proceedings of the STACS 2004, 2004

Randomized k-server algorithms for growth-rate bounded graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Dimension reduction for ultrametrics.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Negotiation-range mechanisms: exploring the limits of truthful efficient markets.
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Graph Decomposition Lemmas and Their Role in Metric Embedding Methods.
Proceedings of the Algorithms, 2004

2003
Competitive distributed file allocation.
Inf. Comput., 2003

Incentive compatible multi unit combinatorial auctions.
Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2003), 2003

On metric ramsey-type phenomena.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Multi-embedding and path approximation of metric spaces.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

A Generic Scheme for Building Overlay Networks in Adversarial Scenarios.
Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 2003

2002
More on random walks, electrical networks, and the harmonic k-server algorithm.
Inf. Process. Lett., 2002

Fast, Fair and Frugal Bandwidth Allocation in ATM Networks.
Algorithmica, 2002

2001
On page migration and other relaxed task systems.
Theor. Comput. Sci., 2001

Approximating min-sum k-clustering in metric spaces.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Multiprocessor Scheduling with Rejection.
SIAM J. Discret. Math., 2000

The harmonic k-server algorithm is competitive.
J. ACM, 2000

A Randomized Algorithm for Two Servers on the Line.
Inf. Comput., 2000

Minimizing maximum response time in scheduling broadcasts.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
On-Line Routing in All-Optical Networks.
Theor. Comput. Sci., 1999

On Capital Investment.
Algorithmica, 1999

Firmato: A Novel Firewall Management Toolkit.
Proceedings of the 1999 IEEE Symposium on Security and Privacy, 1999

1998
Distributed Paging for General Networks.
J. Algorithms, 1998

On Approximating Arbitrary Metrices by Tree Metrics.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Feedback-free multicast prefix protocols.
Proceedings of the Third IEEE Symposium on Computers and Communications (ISCC 1998), June 30, 1998

A Randomized Algorithm for Two Servers on the Line (Extended Abstract).
Proceedings of the Algorithms, 1998

1997
The Distributed k-Server Problem - A Competitive Distributed Translator for k-Server Algorithms.
J. Algorithms, 1997

A polylog(n)-Competitive Algorithm for Metrical Task Systems.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

On Page Migration and Other Related Task Systems.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

A Modular Analysis of Network Transmission Protocols.
Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

Global Optimization Using Local Information with Applications to Flow Control.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Distributed Paging.
Proceedings of the Online Algorithms, 1996

1995
Competitive Algorithms for Distributed Data Management.
J. Comput. Syst. Sci., 1995

New Algorithms for an Ancient Scheduling Problem.
J. Comput. Syst. Sci., 1995

1994
A Better Lower Bound for On-Line Scheduling.
Inf. Process. Lett., 1994

Competitive Non-Preemptive Call Control.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
Heat & Dump: Competitive Distributed Paging
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Competitive Algorithms for Distributed Data Management (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992


  Loading...