Yair Bartal

Publication Activity (10 Years)

Years Active: 1992-2022
Publications (10 Years): 21

Top Venues

CoRR

SoCG

J. Comput. Syst. Sci.

SODA

Publications

Yair Bartal, Ora Nova Fandina, Ofer Neiman
Covering metric spaces by few trees. J. Comput. Syst. Sci. 130 (2022)
Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. SoCG (2022)
Yair Bartal
Advances in Metric Ramsey Theory and its Applications. CoRR (2021)
Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. CoRR (2021)
Yair Bartal, Lee-Ad Gottlieb
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. STOC (2021)
Yair Bartal, Nova Fandina, Seeun William Umboh
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds. SODA (2020)
Yair Bartal, Nova Fandina, Ofer Neiman
Dimensionality reduction: theoretical perspective on practical measures. NeurIPS (2019)
Yair Bartal, Arnold Filtser, Ofer Neiman
On notions of distortion and an almost minimum spanning tree with constant average distortion. J. Comput. Syst. Sci. 105 (2019)
Yair Bartal, Lee-Ad Gottlieb
-spaces (2<p<∞). Theor. Comput. Sci. 757 (2019)
Yair Bartal, Nova Fandina, Ofer Neiman
Covering Metric Spaces by Few Trees. ICALP (2019)
Yair Bartal, Nova Fandina, Ofer Neiman
Covering Metric Spaces by Few Trees. CoRR (2019)
Lee-Ad Gottlieb, Yair Bartal
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. CoRR (2019)
Yair Bartal, Lee-Ad Gottlieb
Approximate Nearest Neighbor Search for \ell _p -Spaces (2 via Embeddings. LATIN (2018)
Yair Bartal, Arnold Filtser, Ofer Neiman
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion. SODA (2016)
Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. SIAM J. Comput. 45 (4) (2016)
Yair Bartal, Arnold Filtser, Ofer Neiman
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion. CoRR (2016)
Yair Bartal, Lee-Ad Gottlieb
(1<p<2), with Applications. SoCG (2016)
Ittai Abraham, Yair Bartal, Ofer Neiman
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion. SIAM J. Comput. 44 (1) (2015)
Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman
. SIAM J. Discret. Math. 29 (3) (2015)
Ittai Abraham, Yair Bartal, Ofer Neiman
Local Embeddings of Metric Spaces. Algorithmica 72 (2) (2015)
Yair Bartal, Lee-Ad Gottlieb
-spaces (2 < p < ∞) via embeddings. CoRR (2015)
Yair Bartal, Lee-Ad Gottlieb
, 1 ≤ p < ∞, with applications. CoRR (2014)
Ittai Abraham, Yair Bartal, Ofer Neiman, Leonard J. Schulman
Volume in General Metric Spaces. Discret. Comput. Geom. 52 (2) (2014)
Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp. SoCG (2014)
Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman
Bandwidth and low dimensional embedding. Theor. Comput. Sci. 500 (2013)
Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman
, p>2. CoRR (2013)
Yair Bartal, Lee-Ad Gottlieb
A Linear Time Approximation Scheme for Euclidean TSP. FOCS (2013)
Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. STOC (2012)
Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman
Bandwidth and Low Dimensional Embedding. APPROX-RANDOM (2011)
Yair Bartal, Ben Recht, Leonard J. Schulman
Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound. SODA (2011)
Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty
Fast, precise and dynamic distance queries. SODA (2011)
Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme CoRR (2011)
Ittai Abraham, Yair Bartal, Ofer Neiman, Leonard J. Schulman
Volume in General Metric Spaces. ESA (2) (2010)
Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty
Fast, precise and dynamic distance queries CoRR (2010)
Yair Bartal, Leonard J. Schulman
Universal Immersion Spaces for Edge-Colored Graphs and Nearest-Neighbor Metrics. SIAM J. Discret. Math. 23 (2) (2009)
Ittai Abraham, Yair Bartal, Ofer Neiman
On low dimensional local embeddings. SODA (2009)
Ittai Abraham, Yair Bartal, Ofer Neiman
Nearly Tight Low Stretch Spanning Trees. FOCS (2008)
Ittai Abraham, Yair Bartal, Ofer Neiman
Embedding metric spaces in their intrinsic dimension. SODA (2008)
Ittai Abraham, Yair Bartal, Ofer Neiman
Nearly Tight Low Stretch Spanning Trees CoRR (2008)
Ittai Abraham, Yair Bartal, Ofer Neiman
Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. SODA (2007)
Ittai Abraham, Yair Bartal, Ofer Neiman
Local embeddings of metric spaces. STOC (2007)
Yair Bartal, Amos Fiat, Stefano Leonardi
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. SIAM J. Comput. 36 (2) (2006)
Ittai Abraham, Yair Bartal, Ofer Neiman
Advances in metric embedding theory. STOC (2006)
Yair Bartal, Béla Bollobás, Manor Mendel
Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst. Sci. 72 (5) (2006)
Yair Bartal, Stefano Leonardi, Gil Shallom, René Sitters
On the Value of Preemption in Scheduling. APPROX-RANDOM (2006)
Ittai Abraham, Yair Bartal, Ofer Neiman
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion CoRR (2006)
Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins
Metric Embeddings with Relaxed Guarantees. FOCS (2005)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Some Low Distortion Metric Ramsey Problems. Discret. Comput. Geom. 33 (1) (2005)
Yair Bartal, Manor Mendel
Randomized k-server algorithms for growth-rate bounded graphs. J. Algorithms 55 (2) (2005)
Yair Bartal, Manor Mendel
Multiembedding of Metric Spaces. SIAM J. Comput. 34 (1) (2004)
Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jirí Sgall, Tomás Tichý
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. STACS (2004)
Yair Bartal, Elias Koutsoupias
On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324 (2-3) (2004)
Yair Bartal, Manor Mendel
-server algorithms for growth-rate bounded graphs. SODA (2004)
Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool
: A novel firewall management toolkit. ACM Trans. Comput. Syst. 22 (4) (2004)
Baruch Awerbuch, Yossi Azar, Yair Bartal
On-line generalized Steiner problem. Theor. Comput. Sci. 324 (2-3) (2004)
Yair Bartal
Graph Decomposition Lemmas and Their Role in Metric Embedding Methods. ESA (2004)
Yair Bartal, John W. Byers, Danny Raz
Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control. SIAM J. Comput. 33 (6) (2004)
Yair Bartal, Béla Bollobás, Manor Mendel
Ramsey-type theorems for metric spaces with applications to online problems CoRR (2004)
Yair Bartal, Manor Mendel
Multi-Embedding of Metric Spaces CoRR (2004)
Yair Bartal, Rica Gonen, Pierfrancesco La Mura
Negotiation-range mechanisms: exploring the limits of truthful efficient markets. EC (2004)
Yair Bartal, Manor Mendel
Dimension reduction for ultrametrics. SODA (2004)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Low dimensional embeddings of ultrametrics. Eur. J. Comb. 25 (1) (2004)
Baruch Awerbuch, Yair Bartal, Amos Fiat
Competitive distributed file allocation. Inf. Comput. 185 (1) (2003)
Yair Bartal, Rica Gonen, Noam Nisan
Incentive compatible multi unit combinatorial auctions. TARK (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
On metric ramsey-type phenomena. STOC (2003)
Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, Elan Pavlov
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios. IPDPS (2003)
Yair Bartal, Manor Mendel
Multi-embedding and path approximation of metric spaces. SODA (2003)
Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang
Fast, Fair and Frugal Bandwidth Allocation in ATM Networks. Algorithmica 33 (3) (2002)
Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan
More on random walks, electrical networks, and the harmonic k-server algorithm. Inf. Process. Lett. 84 (5) (2002)
Yair Bartal, Moses Charikar, Piotr Indyk
On page migration and other relaxed task systems. Theor. Comput. Sci. 268 (1) (2001)
Yair Bartal, Béla Bollobás, Manor Mendel
A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems. FOCS (2001)
Yair Bartal, Moses Charikar, Danny Raz
-clustering in metric spaces. STOC (2001)
Yair Bartal, Elias Koutsoupias
On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem. STACS (2000)
Yair Bartal, S. Muthukrishnan
Minimizing maximum response time in scheduling broadcasts. SODA (2000)
Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jirí Sgall, Leen Stougie
Multiprocessor Scheduling with Rejection. SIAM J. Discret. Math. 13 (1) (2000)
Yair Bartal, Eddie Grove
-server algorithm is competitive. J. ACM 47 (1) (2000)
Yair Bartal, Marek Chrobak, Lawrence L. Larmore
A Randomized Algorithm for Two Servers on the Line. Inf. Comput. 158 (1) (2000)
Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang
Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks. SODA (1999)
Yair Bartal, Stefano Leonardi
On-Line Routing in All-Optical Networks. Theor. Comput. Sci. 221 (1-2) (1999)
Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén
On Capital Investment. Algorithmica 25 (1) (1999)
Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool
Firmato: A Novel Firewall Management Toolkit. IEEE Symposium on Security and Privacy (1999)
Yair Bartal, John W. Byers, Michael Luby, Danny Raz
Feedback-free multicast prefix protocols. ISCC (1998)
Yair Bartal
On Approximating Arbitrary Metrices by Tree Metrics. STOC (1998)
Baruch Awerbuch, Yair Bartal, Amos Fiat
Distributed Paging for General Networks. J. Algorithms 28 (1) (1998)
Yair Bartal, Marek Chrobak, Lawrence L. Larmore
A Randomized Algorithm for Two Servers on the Line (Extended Abstract). ESA (1998)
Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz
A Modular Analysis of Network Transmission Protocols. ISTCS (1997)
Yair Bartal, John W. Byers, Danny Raz
Global Optimization Using Local Information with Applications to Flow Control. FOCS (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
)-Competitive Algorithm for Metrical Task Systems. STOC (1997)
Yair Bartal, Adi Rosén
The Distributed k-Server Problem - A Competitive Distributed Translator for k-Server Algorithms. J. Algorithms 23 (2) (1997)
Yair Bartal, Moses Charikar, Piotr Indyk
On Page Migration and Other Related Task Systems. SODA (1997)
Yair Bartal, Stefano Leonardi
On-Line Routing in All-Optical Networks. ICALP (1997)
Baruch Awerbuch, Yossi Azar, Yair Bartal
On-line Generalized Steiner Problem. SODA (1996)
Yair Bartal, Amos Fiat, Stefano Leonardi
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. STOC (1996)
Yair Bartal
Distributed Paging. Online Algorithms (1996)
Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén
On Capital Investment. ICALP (1996)
Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jirí Sgall, Leen Stougie
Multiprocessor Scheduling with Rejection. SODA (1996)
Yair Bartal
Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. FOCS (1996)
Baruch Awerbuch, Yair Bartal, Amos Fiat
Distributed Paging for General Networks. SODA (1996)
Yair Bartal, Amos Fiat, Yuval Rabani
Competitive Algorithms for Distributed Data Management. J. Comput. Syst. Sci. 51 (3) (1995)
Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra
New Algorithms for an Ancient Scheduling Problem. J. Comput. Syst. Sci. 51 (3) (1995)

Yair Bartal.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Yair Bartal