default search action
Yair Bartal
Person information
- affiliation: The Hebrew University of Jerusalem, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c60]Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, Alon Hovav:
Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications. FOCS 2024: 1724-1767 - [i15]Yair Bartal, Ora Nova Fandina, Seeun William Umboh:
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds. CoRR abs/2408.16298 (2024) - 2022
- [j34]Yair Bartal, Ora Nova Fandina
, Ofer Neiman
Covering metric spaces by few trees. J. Comput. Syst. Sci. 130: 26-42 (2022) - [c59]Yair Bartal, Ora Nova Fandina, Kasper Green Larsen:
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. SoCG 2022: 13:1-13:16 - 2021
- [c58]Yair Bartal, Lee-Ad Gottlieb:
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. STOC 2021: 1028-1041 - [i14]Yair Bartal:
Advances in Metric Ramsey Theory and its Applications. CoRR abs/2104.03484 (2021) - [i13]Yair Bartal, Ora Nova Fandina, Kasper Green Larsen:
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. CoRR abs/2107.06626 (2021) - 2020
- [c57]Yair Bartal, Nova Fandina, Seeun William Umboh
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds. SODA 2020: 1538-1557
2010 – 2019
- 2019
- [j33]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: 116-129 (2019) - [j32]Yair Bartal, Lee-Ad Gottlieb
Approximate nearest neighbor search for ℓp-spaces (2<p<∞). Theor. Comput. Sci. 757: 27-35 (2019) - [c56]Yair Bartal, Nova Fandina, Ofer Neiman:
Covering Metric Spaces by Few Trees. ICALP 2019: 20:1-20:16 - [c55]Yair Bartal, Nova Fandina, Ofer Neiman:
Dimensionality reduction: theoretical perspective on practical measures. NeurIPS 2019: 10576-10588 - [i12]Lee-Ad Gottlieb, Yair Bartal:
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. CoRR abs/1904.03611 (2019) - [i11]Yair Bartal, Nova Fandina, Ofer Neiman:
Covering Metric Spaces by Few Trees. CoRR abs/1905.07559 (2019) - 2018
- [c54]Yair Bartal, Lee-Ad Gottlieb
Approximate Nearest Neighbor Search for \ell _p -Spaces (2 via Embeddings. LATIN 2018: 120-133 - 2016
- [j31]Yair Bartal, Lee-Ad Gottlieb
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. SIAM J. Comput. 45(4): 1563-1581 (2016) - [c53]Yair Bartal, Lee-Ad Gottlieb
Dimension Reduction Techniques for ℓp (1<p<2), with Applications. SoCG 2016: 16:1-16:15 - [c52]Yair Bartal, Arnold Filtser, Ofer Neiman:
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion. SODA 2016: 873-882 - [i10]Yair Bartal, Arnold Filtser, Ofer Neiman:
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion. CoRR abs/1609.08801 (2016) - 2015
- [j30]Ittai Abraham, Yair Bartal, Ofer Neiman:
Local Embeddings of Metric Spaces. Algorithmica 72(2): 539-606 (2015) - [j29]Ittai Abraham, Yair Bartal, Ofer Neiman:
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion. SIAM J. Comput. 44(1): 160-192 (2015) - [j28]Yair Bartal, Lee-Ad Gottlieb
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp. SIAM J. Discret. Math. 29(3): 1207-1222 (2015) - [i9]Yair Bartal, Lee-Ad Gottlieb:
Approximate nearest neighbor search for ℓp-spaces (2 < p < ∞) via embeddings. CoRR abs/1512.01775 (2015) - 2014
- [j27]Ittai Abraham, Yair Bartal, Ofer Neiman, Leonard J. Schulman
Volume in General Metric Spaces. Discret. Comput. Geom. 52(2): 366-389 (2014) - [c51]Yair Bartal, Lee-Ad Gottlieb
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp. SoCG 2014: 60 - [i8]Yair Bartal, Lee-Ad Gottlieb:
Dimension reduction techniques for ℓp, 1 ≤ p < ∞, with applications. CoRR abs/1408.1789 (2014) - 2013
- [j26]Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman:
Bandwidth and low dimensional embedding. Theor. Comput. Sci. 500: 44-56 (2013) - [c50]Yair Bartal, Lee-Ad Gottlieb
A Linear Time Approximation Scheme for Euclidean TSP. FOCS 2013: 698-706 - [i7]Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman:
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp, p>2. CoRR abs/1308.4996 (2013) - 2012
- [c49]Yair Bartal, Lee-Ad Gottlieb
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. STOC 2012: 663-672 - 2011
- [c48]Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman:
Bandwidth and Low Dimensional Embedding. APPROX-RANDOM 2011: 50-61 - [c47]Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty:
Fast, precise and dynamic distance queries. SODA 2011: 840-853 - [c46]Yair Bartal, Ben Recht, Leonard J. Schulman
Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound. SODA 2011: 868-887 - [i6]Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer:
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. CoRR abs/1112.0699 (2011) - 2010
- [c45]Ittai Abraham, Yair Bartal, Ofer Neiman, Leonard J. Schulman:
Volume in General Metric Spaces. ESA (2) 2010: 87-99 - [i5]Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty:
Fast, precise and dynamic distance queries. CoRR abs/1008.1480 (2010)
2000 – 2009
- 2009
- [j25]Yair Bartal, Leonard J. Schulman
Universal Immersion Spaces for Edge-Colored Graphs and Nearest-Neighbor Metrics. SIAM J. Discret. Math. 23(2): 1110-1115 (2009) - [c44]Ittai Abraham, Yair Bartal, Ofer Neiman:
On low dimensional local embeddings. SODA 2009: 875-884 - 2008
- [c43]Ittai Abraham, Yair Bartal, Ofer Neiman:
Nearly Tight Low Stretch Spanning Trees. FOCS 2008: 781-790 - [c42]Ittai Abraham, Yair Bartal, Ofer Neiman:
Embedding metric spaces in their intrinsic dimension. SODA 2008: 363-372 - [i4]Ittai Abraham, Yair Bartal, Ofer Neiman:
Nearly Tight Low Stretch Spanning Trees. CoRR abs/0808.2017 (2008) - 2007
- [c41]Ittai Abraham, Yair Bartal, Ofer Neiman:
Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. SODA 2007: 502-511 - [c40]Ittai Abraham, Yair Bartal, Ofer Neiman:
Local embeddings of metric spaces. STOC 2007: 631-640 - 2006
- [j24]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): 890-921 (2006) - [j23]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): 354-393 (2006) - [c39]Yair Bartal, Stefano Leonardi, Gil Shallom, René Sitters:
On the Value of Preemption in Scheduling. APPROX-RANDOM 2006: 39-48 - [c38]Ittai Abraham, Yair Bartal, Ofer Neiman:
Advances in metric embedding theory. STOC 2006: 271-286 - [i3]Ittai Abraham, Yair Bartal, Ofer Neiman:
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion. CoRR abs/cs/0610003 (2006) - 2005
- [j22]Yair Bartal, Nathan Linial, Manor Mendel
Some Low Distortion Metric Ramsey Problems. Discret. Comput. Geom. 33(1): 27-41 (2005) - [j21]Yair Bartal, Manor Mendel:
Randomized k-server algorithms for growth-rate bounded graphs. J. Algorithms 55(2): 192-202 (2005) - [c37]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: 83-100 - 2004
- [j20]Yair Bartal, Nathan Linial, Manor Mendel
Low dimensional embeddings of ultrametrics. Eur. J. Comb. 25(1): 87-92 (2004) - [j19]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): 1261-1279 (2004) - [j18]Yair Bartal, Manor Mendel
Multiembedding of Metric Spaces. SIAM J. Comput. 34(1): 248-259 (2004) - [j17]Baruch Awerbuch, Yossi Azar
On-line generalized Steiner problem. Theor. Comput. Sci. 324(2-3): 313-324 (2004) - [j16]Yair Bartal, Elias Koutsoupias:
On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324(2-3): 337-345 (2004) - [j15]Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool
Firmato: A novel firewall management toolkit. ACM Trans. Comput. Syst. 22(4): 381-420 (2004) - [c36]Yair Bartal:
Graph Decomposition Lemmas and Their Role in Metric Embedding Methods. ESA 2004: 89-97 - [c35]Yair Bartal, Rica Gonen, Pierfrancesco La Mura
Negotiation-range mechanisms: exploring the limits of truthful efficient markets. EC 2004: 1-8 - [c34]Yair Bartal, Manor Mendel:
Dimension reduction for ultrametrics. SODA 2004: 664-665 - [c33]Yair Bartal, Manor Mendel:
Randomized k-server algorithms for growth-rate bounded graphs. SODA 2004: 666-671 - [c32]Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. STACS 2004: 187-198 - [i2]Yair Bartal, Béla Bollobás, Manor Mendel:
Ramsey-type theorems for metric spaces with applications to online problems. CoRR cs.DS/0406028 (2004) - [i1]Yair Bartal, Manor Mendel:
Multi-Embedding of Metric Spaces. CoRR cs.DS/0408003 (2004) - 2003
- [j14]Baruch Awerbuch, Yair Bartal, Amos Fiat:
Competitive distributed file allocation. Inf. Comput. 185(1): 1-40 (2003) - [c31]Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, Elan Pavlov:
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios. IPDPS 2003: 40 - [c30]Yair Bartal, Manor Mendel:
Multi-embedding and path approximation of metric spaces. SODA 2003: 424-433 - [c29]Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
On metric ramsey-type phenomena. STOC 2003: 463-472 - [c28]Yair Bartal, Rica Gonen, Noam Nisan
Incentive compatible multi unit combinatorial auctions. TARK 2003: 72-87 - 2002
- [j13]Yair Bartal, Martin Farach-Colton
Fast, Fair and Frugal Bandwidth Allocation in ATM Networks. Algorithmica 33(3): 272-286 (2002) - [j12]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): 271-276 (2002) - 2001
- [j11]Yair Bartal, Moses Charikar
On page migration and other relaxed task systems. Theor. Comput. Sci. 268(1): 43-66 (2001) - [c27]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: 396-405 - [c26]Yair Bartal, Moses Charikar
Approximating min-sum k-clustering in metric spaces. STOC 2001: 11-20 - 2000
- [j10]Yair Bartal, Marek Chrobak, Lawrence L. Larmore:
A Randomized Algorithm for Two Servers on the Line. Inf. Comput. 158(1): 53-69 (2000) - [j9]Yair Bartal, Eddie Grove:
The harmonic k-server algorithm is competitive. J. ACM 47(1): 1-15 (2000) - [j8]Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela
Multiprocessor Scheduling with Rejection. SIAM J. Discret. Math. 13(1): 64-78 (2000) - [c25]Yair Bartal, S. Muthukrishnan:
Minimizing maximum response time in scheduling broadcasts. SODA 2000: 558-559 - [c24]Yair Bartal, Elias Koutsoupias:
On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem. STACS 2000: 605-613
1990 – 1999
- 1999
- [j7]Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén:
On Capital Investment. Algorithmica 25(1): 22-36 (1999) - [j6]Yair Bartal, Stefano Leonardi:
On-Line Routing in All-Optical Networks. Theor. Comput. Sci. 221(1-2): 19-39 (1999) - [c23]Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang:
Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks. SODA 1999: 92-101 - [c22]Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool
Firmato: A Novel Firewall Management Toolkit. S&P 1999: 17-31 - 1998
- [j5]Baruch Awerbuch, Yair Bartal, Amos Fiat:
Distributed Paging for General Networks. J. Algorithms 28(1): 67-104 (1998) - [c21]Yair Bartal, Marek Chrobak, Lawrence L. Larmore:
A Randomized Algorithm for Two Servers on the Line (Extended Abstract). ESA 1998: 247-258 - [c20]Yair Bartal, John W. Byers, Michael Luby, Danny Raz:
Feedback-free multicast prefix protocols. ISCC 1998: 135-141 - [c19]Yair Bartal:
On Approximating Arbitrary Metrices by Tree Metrics. STOC 1998: 161-168 - 1997
- [j4]Yair Bartal, Adi Rosén:
The Distributed k-Server Problem - A Competitive Distributed Translator for k-Server Algorithms. J. Algorithms 23(2): 241-264 (1997) - [c18]Yair Bartal, John W. Byers, Danny Raz:
Global Optimization Using Local Information with Applications to Flow Control. FOCS 1997: 303-312 - [c17]Yair Bartal, Stefano Leonardi:
On-Line Routing in All-Optical Networks. ICALP 1997: 516-526 - [c16]Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz:
A Modular Analysis of Network Transmission Protocols. ISTCS 1997: 54-62 - [c15]Yair Bartal, Moses Charikar, Piotr Indyk:
On Page Migration and Other Relaxed Task Systems. SODA 1997: 43-52 - [c14]Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins:
A polylog(n)-Competitive Algorithm for Metrical Task Systems. STOC 1997: 711-719 - 1996
- [c13]Yair Bartal:
Distributed Paging. Online Algorithms 1996: 97-117 - [c12]Yair Bartal:
Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. FOCS 1996: 184-193 - [c11]Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén:
On Capital Investment. ICALP 1996: 429-441 - [c10]Baruch Awerbuch, Yossi Azar, Yair Bartal:
On-line Generalized Steiner Problem. SODA 1996: 68-74 - [c9]Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jirí Sgall, Leen Stougie:
Multiprocessor Scheduling with Rejection. SODA 1996: 95-103 - [c8]Baruch Awerbuch, Yair Bartal, Amos Fiat:
Distributed Paging for General Networks. SODA 1996: 574-583 - [c7]Yair Bartal, Amos Fiat, Stefano Leonardi:
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. STOC 1996: 531-540 - 1995
- [j3]Yair Bartal, Amos Fiat, Yuval Rabani
Competitive Algorithms for Distributed Data Management. J. Comput. Syst. Sci. 51(3): 341-358 (1995) - [j2]Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra:
New Algorithms for an Ancient Scheduling Problem. J. Comput. Syst. Sci. 51(3): 359-366 (1995) - 1994
- [b1]Yair Bartal:
Competitive analysis of distributed on-line problems - distributed paging. Tel Aviv University, Israel, 1994 - [j1]Yair Bartal, Howard J. Karloff, Yuval Rabani
A Better Lower Bound for On-Line Scheduling. Inf. Process. Lett. 50(3): 113-116 (1994) - [c6]Baruch Awerbuch, Yair Bartal, Amos Fiat, Adi Rosén:
Competitive Non-Preemptive Call Control. SODA 1994: 312-320 - 1993
- [c5]Baruch Awerbuch, Yair Bartal, Amos Fiat:
Heat & Dump: Competitive Distributed Paging. FOCS 1993: 22-31 - [c4]Baruch Awerbuch, Yair Bartal, Amos Fiat:
Competitive distributed file allocation. STOC 1993: 164-173 - 1992
- [c3]Yair Bartal, Adi Rosén:
The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms. FOCS 1992: 344-353 - [c2]Yair Bartal, Amos Fiat, Yuval Rabani
Competitive Algorithms for Distributed Data Management (Extended Abstract). STOC 1992: 39-50 - [c1]Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra:
New Algorithms for an Ancient Scheduling Problem. STOC 1992: 51-58
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-10 20:46 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: