Yair Bartal

According to our database, Yair Bartal authored at least 81 papers between 1992 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications.

Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, Alon Hovav

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2022

Covering metric spaces by few trees.

Yair Bartal, Ora Nova Fandina, Ofer Neiman

J. Comput. Syst. Sci., 2022

Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures.

Yair Bartal, Ora Nova Fandina, Kasper Green Larsen

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Advances in Metric Ramsey Theory and its Applications.

Yair Bartal

CoRR, 2021

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

Yair Bartal, Lee-Ad Gottlieb

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds.

Yair Bartal, Nova Fandina, Seeun William Umboh

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Approximate nearest neighbor search for <i>ℓ</i>_<i>p</i>-spaces (2<p<∞).

Yair Bartal, Lee-Ad Gottlieb

Theor. Comput. Sci., 2019

On notions of distortion and an almost minimum spanning tree with constant average distortion.

Yair Bartal, Arnold Filtser, Ofer Neiman

J. Comput. Syst. Sci., 2019

Dimensionality reduction: theoretical perspective on practical measures.

Yair Bartal, Nova Fandina, Ofer Neiman

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Approximate Nearest Neighbor Search for \ell _p -Spaces (2 via Embeddings.

Yair Bartal, Lee-Ad Gottlieb

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2016

The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme.

Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer

SIAM J. Comput., 2016

Dimension Reduction Techniques for ℓ_p (1<p<2), with Applications.

Yair Bartal, Lee-Ad Gottlieb

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ_p.

Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman

SIAM J. Discret. Math., 2015

Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion.

Ittai Abraham, Yair Bartal, Ofer Neiman

SIAM J. Comput., 2015

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

Yair Bartal, Lee-Ad Gottlieb

CoRR, 2015

Local Embeddings of Metric Spaces.

Ittai Abraham, Yair Bartal, Ofer Neiman

Algorithmica, 2015

2014

Volume in General Metric Spaces.

Ittai Abraham, Yair Bartal, Ofer Neiman, Leonard J. Schulman

Discret. Comput. Geom., 2014

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

Yair Bartal, Lee-Ad Gottlieb

CoRR, 2014

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp.

Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

Bandwidth and low dimensional embedding.

Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman

Theor. Comput. Sci., 2013

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

Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman

CoRR, 2013

A Linear Time Approximation Scheme for Euclidean TSP.

Yair Bartal, Lee-Ad Gottlieb

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2011

Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound.

Yair Bartal, Ben Recht, Leonard J. Schulman

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Fast, precise and dynamic distance queries.

Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty

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.

Yair Bartal, Leonard J. Schulman

SIAM J. Discret. Math., 2009

On low dimensional local embeddings.

Ittai Abraham, Yair Bartal, Ofer Neiman

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Embedding metric spaces in their intrinsic dimension.

Ittai Abraham, Yair Bartal, Ofer Neiman

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Nearly Tight Low Stretch Spanning Trees.

Ittai Abraham, Yair Bartal, Ofer Neiman

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.

Yair Bartal, Amos Fiat, Stefano Leonardi

SIAM J. Comput., 2006

Ramsey-type theorems for metric spaces with applications to online problems.

Yair Bartal, Béla Bollobás, Manor Mendel

J. Comput. Syst. Sci., 2006

Advances in metric embedding theory.

Ittai Abraham, Yair Bartal, Ofer Neiman

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

On the Value of Preemption in Scheduling.

Yair Bartal, Stefano Leonardi, Gil Shallom, René Sitters

Proceedings of the Approximation, 2006

2005

Randomized k-server algorithms for growth-rate bounded graphs.

Yair Bartal, Manor Mendel

J. Algorithms, 2005

Some Low Distortion Metric Ramsey Problems.

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Discret. Comput. Geom., 2005

Metric Embeddings with Relaxed Guarantees.

Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

<i>Firmato</i>: A novel firewall management toolkit.

Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool

ACM Trans. Comput. Syst., 2004

On the competitive ratio of the work function algorithm for the k-server problem.

Yair Bartal, Elias Koutsoupias

Theor. Comput. Sci., 2004

On-line generalized Steiner problem.

Baruch Awerbuch, Yossi Azar, Yair Bartal

Theor. Comput. Sci., 2004

Multiembedding of Metric Spaces.

Yair Bartal, Manor Mendel

SIAM J. Comput., 2004

Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control.

Yair Bartal, John W. Byers, Danny Raz

SIAM J. Comput., 2004

Low dimensional embeddings of ultrametrics.

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Eur. J. Comb., 2004

Multi-Embedding of Metric Spaces

Yair Bartal, Manor Mendel

CoRR, 2004

Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.

Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jirí Sgall, Tomás Tichý

Proceedings of the STACS 2004, 2004

Randomized <i>k</i>-server algorithms for growth-rate bounded graphs.

Yair Bartal, Manor Mendel

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Dimension reduction for ultrametrics.

Yair Bartal, Manor Mendel

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Negotiation-range mechanisms: exploring the limits of truthful efficient markets.

Yair Bartal, Rica Gonen, Pierfrancesco La Mura

Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Graph Decomposition Lemmas and Their Role in Metric Embedding Methods.

Yair Bartal

Proceedings of the Algorithms, 2004

2003

Competitive distributed file allocation.

Baruch Awerbuch, Yair Bartal, Amos Fiat

Inf. Comput., 2003

Incentive compatible multi unit combinatorial auctions.

Yair Bartal, Rica Gonen, Noam Nisan

Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2003), 2003

On metric ramsey-type phenomena.

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Multi-embedding and path approximation of metric spaces.

Yair Bartal, Manor Mendel

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

A Generic Scheme for Building Overlay Networks in Adversarial Scenarios.

Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, Elan Pavlov

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.

Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan

Inf. Process. Lett., 2002

Fast, Fair and Frugal Bandwidth Allocation in ATM Networks.

Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang

Algorithmica, 2002

2001

On page migration and other relaxed task systems.

Yair Bartal, Moses Charikar, Piotr Indyk

Theor. Comput. Sci., 2001

Approximating min-sum <i>k</i>-clustering in metric spaces.

Yair Bartal, Moses Charikar, Danny Raz

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.

Yair Bartal, Béla Bollobás, Manor Mendel

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Multiprocessor Scheduling with Rejection.

Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jirí Sgall, Leen Stougie

SIAM J. Discret. Math., 2000

The harmonic <i>k</i>-server algorithm is competitive.

Yair Bartal, Eddie Grove

J. ACM, 2000

A Randomized Algorithm for Two Servers on the Line.

Yair Bartal, Marek Chrobak, Lawrence L. Larmore

Inf. Comput., 2000

Minimizing maximum response time in scheduling broadcasts.

Yair Bartal, S. Muthukrishnan

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

On-Line Routing in All-Optical Networks.

Yair Bartal, Stefano Leonardi

Theor. Comput. Sci., 1999

On Capital Investment.

Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén

Algorithmica, 1999

Firmato: A Novel Firewall Management Toolkit.

Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool

Proceedings of the 1999 IEEE Symposium on Security and Privacy, 1999

1998

Distributed Paging for General Networks.

Baruch Awerbuch, Yair Bartal, Amos Fiat

J. Algorithms, 1998

On Approximating Arbitrary Metrices by Tree Metrics.

Yair Bartal

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Feedback-free multicast prefix protocols.

Yair Bartal, John W. Byers, Michael Luby, Danny Raz

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

Yair Bartal, Marek Chrobak, Lawrence L. Larmore

Proceedings of the Algorithms, 1998

1997

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

Yair Bartal, Adi Rosén

J. Algorithms, 1997

A polylog(<i>n</i>)-Competitive Algorithm for Metrical Task Systems.

Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

A Modular Analysis of Network Transmission Protocols.

Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz

Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

Global Optimization Using Local Information with Applications to Flow Control.

Yair Bartal, John W. Byers, Danny Raz

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications.

Yair Bartal

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Distributed Paging.

Yair Bartal

Proceedings of the Online Algorithms, 1996

1995

Competitive Algorithms for Distributed Data Management.

Yair Bartal, Amos Fiat, Yuval Rabani

J. Comput. Syst. Sci., 1995

New Algorithms for an Ancient Scheduling Problem.

Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra

J. Comput. Syst. Sci., 1995

1994

Competitive analysis of distributed on-line problems - distributed paging

Yair Bartal

PhD thesis, 1994

A Better Lower Bound for On-Line Scheduling.

Yair Bartal, Howard J. Karloff, Yuval Rabani

Inf. Process. Lett., 1994

Competitive Non-Preemptive Call Control.

Baruch Awerbuch, Yair Bartal, Amos Fiat, Adi Rosén

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Heat & Dump: Competitive Distributed Paging

Baruch Awerbuch, Yair Bartal, Amos Fiat

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Competitive Algorithms for Distributed Data Management (Extended Abstract)

Yair Bartal, Amos Fiat, Yuval Rabani

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992