No photo of Yair Bartal

View Scopus Profile

Yair Bartal

 https://orcid.org/0000-0001-6252-6292
    Calculated based on number of publications stored in Pure and citations from Scopus
    1992 …2025

    Research activity per year

    Filter
    Conference contribution

    Search results

    • 2024

      Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications

      Banerjee, S., Bartal, Y., Gottlieb, L. A. & Hovav, A., 2024, Proceedings - 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024. IEEE Computer Society, p. 1724-1767 44 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      1 Scopus citations
    • 2022

      Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures

      Bartal, Y., Fandina, O. N. & Larsen, K. G., 1 Jun 2022, 38th International Symposium on Computational Geometry, SoCG 2022. Goaoc, X. & Kerber, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 13:1-13:16 16 p. 13. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 224).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2021

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

      Bartal, Y. & Gottlieb, L. A., 15 Jun 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 1028-1041 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      4 Scopus citations
    • 2020

      Online probabilistic metric embedding: A general framework for bypassing inherent bounds

      Bartal, Y., Fandina, N. & Umboh, S. W., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 1538-1557 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      7 Scopus citations
    • 2019

      Covering metric spaces by few trees

      Bartal, Y., Fandina, N. & Neiman, O., 1 Jul 2019, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Baier, C., Chatzigiannakis, I., Flocchini, P. & Leonardi, S. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 20. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 132).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      11 Scopus citations
    • 2018

      Approximate nearest neighbor search for lp-Spaces (2 < p < ∞) via Embeddings

      Bartal, Y. & Gottlieb, L. A., 2018, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. Mosteiro, M. A., Bender, M. A. & Farach-Colton, M. (eds.). Springer Verlag, p. 120-133 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10807 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      4 Scopus citations
    • 2016

      Dimension reduction techniques for ℓp (1 ≤ p ≤ 2), with applications

      Bartal, Y. & Gottlieb, L. A., 1 Jun 2016, 32nd International Symposium on Computational Geometry, SoCG 2016. Fekete, S. & Lubiw, A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 16.1-16.15 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 51).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      5 Scopus citations

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

      Bartal, Y., Filtsert, A. & Neiman, O., 2016, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Krauthgamer, R. (ed.). Association for Computing Machinery, p. 873-882 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      9 Scopus citations
    • 2014

      On the impossibility of dimension reduction for doubling subsets of ℓp

      Bartal, Y., Gottlieb, L. A. & Neiman, O., 2014, Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014. Association for Computing Machinery, p. 60-66 7 p. (Proceedings of the Annual Symposium on Computational Geometry).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      5 Scopus citations
    • 2013

      A linear time approximation scheme for Euclidean TSP

      Bartal, Y. & Gottlieb, L. A., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 698-706 9 p. 6686206. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      27 Scopus citations
    • 2012

      The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme

      Bartal, Y., Gottlieb, L. A. & Krauthgamer, R., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 663-672 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      31 Scopus citations
    • 2011

      Bandwidth and low dimensional embedding

      Bartal, Y., Carroll, D. E., Meyerson, A. & Neiman, O., 2011, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. p. 50-61 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound

      Bartal, Y., Recht, B. & Schulman, L. J., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, p. 868-887 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      35 Scopus citations

    • Fast, precise and dynamic distance queries

      Bartal, Y., Gottlieb, L. A., Kopelowitz, T., Lewenstein, M. & Roditty, L., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, p. 840-853 14 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      15 Scopus citations
    • 2010

      Volume in general metric spaces

      Abraham, I., Bartal, Y., Neiman, O. & Schulman, L. J., 2010, Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings. PART 2 ed. p. 87-99 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6347 LNCS, no. PART 2).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      2 Scopus citations
    • 2009

      On low dimensional local embeddings

      Abraham, I., Bartal, Y. & Neiman, O., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery (ACM), p. 875-884 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      8 Scopus citations
    • 2008

      Embedding metric spaces in their intrinsic dimension

      Abraham, I., Bartal, Y. & Neiman, O., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery (ACM), p. 363-372 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      30 Scopus citations

    • Nearly tight low stretch spanning trees

      Abraham, I., Bartal, Y. & Neiman, O., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 781-790 10 p. 4691010. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      78 Scopus citations
    • 2007

      Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion

      Abraham, I., Bartal, Y. & Neiman, O., 2007, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Association for Computing Machinery, p. 502-511 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 07-09-January-2007).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      28 Scopus citations

    • Local embeddings of metric spaces

      Abraham, I., Bartal, Y. & Neiman, O., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 631-640 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      16 Scopus citations
    • 2006

      Advances in metric embedding theory

      Abraham, I., Bartal, Y. & Neimant, O., 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 271-286 16 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      55 Scopus citations

    • On the value of preemption in scheduling

      Bartal, Y., Leonardi, S., Shallom, G. & Sitters, R., 2006, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a. Springer Verlag, p. 39-48 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4110 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      12 Scopus citations
    • 2005

      Metric embeddings with relaxed guarantees

      Abraham, I., Bartal, Y., Chan, T. H. H., Dhamdhere, K., Gupta, A., Kleinberg, J., Neiman, O. & Slivkins, A., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 83-100 18 p. 1530704. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      58 Scopus citations
    • 2003

      A generic scheme for building overlay networks in adversarial scenarios

      Abraham, I., Awerbuch, B., Azar, Y., Bartal, Y., Malkhi, D. & Pavlov, E., 2003, Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003. Institute of Electrical and Electronics Engineers Inc., 1213125. (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      57 Scopus citations

    • Incentive compatible multi unit combinatorial auctions

      Bartal, Y., Gonen, R. & Nisan, N., 20 Jun 2003, Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2003. Tennenholtz, M. (ed.). Association for Computing Machinery, Inc, p. 72-87 16 p. (Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2003).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      148 Scopus citations
    • 2000

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

      Bartal, Y. & Koutsoupias, E., 2000, STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings. Reichel, H. & Tison, S. (eds.). Springer Verlag, p. 605-613 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1770).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      6 Scopus citations
    • 1998

      A randomized algorithm for two servers on the line

      Bartal, Y., Chrobak, M. & Larmore, L. L., 1998, Algorithms, ESA 1998 - 6th Annual European Symposium, Proceedings. Springer Verlag, p. 247-258 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1461 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      10 Scopus citations

    • Distributed paging

      Bartal, Y., 1998, Online Algorithms - The State of the Art. Fiat, A. & Woeginger, G. J. (eds.). Springer Verlag, p. 97-117 21 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1442).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      6 Scopus citations

    • Feedback-free multicast prefix protocols

      Bartal, Y., Byers, J. W., Luby, M. & Raz, D., 1998, Proceedings - 3rd IEEE Symposium on Computers and Communications, ISCC 1998. Institute of Electrical and Electronics Engineers Inc., p. 135-141 7 p. 702473. (Proceedings - 3rd IEEE Symposium on Computers and Communications, ISCC 1998).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      13 Scopus citations
    • 1997

      On-line routing in all-optical networks

      Bartal, Y. & Leonardi, S., 1997, Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings. Degano, P., Gorrieri, R. & Marchetti-Spaccamela, A. (eds.). Springer Verlag, p. 516-526 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1256).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      28 Scopus citations
    • 1996

      Distributed paging for general networks

      Awerbuch, B., Bartal, Y. & Fiat, A., 28 Jan 1996, Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996. Association for Computing Machinery, p. 574-583 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. Part F129447).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      19 Scopus citations

    • Lower bounds for on-line graph problems with application to on-line circuit and optical routing

      Bartal, Y., Fiat, A. & Leonardi, S., 1 Jul 1996, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, p. 531-540 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129452).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      50 Scopus citations

    • Multiprocessor scheduling with rejection

      Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J. & Stougie, L., 28 Jan 1996, Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996. Association for Computing Machinery, p. 95-103 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. Part F129447).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      40 Scopus citations

    • On capital investment

      Azar, Y., Bartal, Y., Feuerstein, E., Fiat, A., Leonardi, S. & Rosén, A., 1996, Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings. Meyer auf der Heide, F. & Monien, B. (eds.). Springer Verlag, p. 430-441 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1099).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      2 Scopus citations

    • On-line generalized steiner problem

      Awerbuch, B., Azar, Y. & Bartal, Y., 28 Jan 1996, Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996. Association for Computing Machinery, p. 68-74 7 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. Part F129447).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      30 Scopus citations
    • 1994

      Competitive non-preemptive call control

      Awerbuch, B., Bartal, Y., Fiat, A. & Rosen, A., 1994, Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. Publ by ACM, p. 312-320 9 p. (Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      122 Scopus citations
    • 1993

      Competitive distributed file allocation

      Awerbuch, B., Bartal, Y. & Fiat, A., 1 Jun 1993, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, p. 164-173 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129585).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      88 Scopus citations

    • Heat & Dump: Competitive distributed paging

      Awerbuch, B., Bartal, Y. & Fiat, A., 1993, Annual Symposium on Foundatons of Computer Science (Proceedings). Anon (ed.). Publ by IEEE, p. 22-31 10 p. (Annual Symposium on Foundatons of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      19 Scopus citations
    • 1992

      Competitive algorithms for distributed data management

      Bartal, Y., Fiat, A. & Rabani, Y., 1 Jul 1992, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, p. 39-50 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129722).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      82 Scopus citations

    • New algorithms for an ancient scheduling problem

      Bartal, Y., Fiat, A., Karloff, H. & Vohra, R., 1 Jul 1992, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, p. 51-58 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129722).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      77 Scopus citations

    • The distributed k-server problem-a competitive distributed translator for k-server algorithms

      Bartal, Y. & Rosen, A., 1992, Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992. IEEE Computer Society, p. 344-353 10 p. 267756. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 1992-October).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      16 Scopus citations
    Your message has successfully been sent.
    Your message was not sent due to an error.