Arnold Filtser
Last update: 20 - Nov - 2025 (d-m-y).

About Me

I am a faculty member at the Computer Science Department at Bar-Ilan University. Prior to joining Bar Ilan, I was a postdoc at the Computer Science Department at Columbia University, hosted by Alex Andoni. The postdoc was part of the the Simons Collaboration on Algorithms and Geometry.
I did my PhD at the Computer Science Department at Ben Gurion University of the Negev. I was fortunate to be advised by Ofer Neiman and Robert Krauthgamer.

My research stands at the exciting intersection of algorithms, geometry, and graph theory. Broadly speaking, my work focuses on summarization of geometric data. That is, ways to organize data of geometric nature in more manageable forms that could be utilized for algorithmic design. Some key words: low-distortion metric embeddings, stochastic decompositions, spanners, approximation algorithms, streaming algorithms, online algorithms, and computational geometry.

I am recruiting excellent graduate students to our research group. If you are interested, don't hesitate to shoot me an email!

Check out our Bar-Ilan Theory seminar !

Check out our FOCS 2022 workshop “ Advances on Metric Embeddings ” I co-organized with Hung Le. There are video recordings of all the talks!

Contact information

Arnold Filtser
Email: arnold.filtser at biu dot ac dot il
Office: Bar-Ilan university, bldg 503, room 307

free hits
<> free hits
<>

Video

This page includes several talks regarding my research papers.

  1. How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
    [ Video , 65 min, Workshop on High-Dimensional and Complex Data Algorithms (Venice), May 2025]
  2. On Sparse partitions
    [ Video , 45 min, DIMACS Workshop on Efficient Algorithms for High Dimensional Metrics: New Tools, May 2024]
  3. Locality-Sensitive Orderings
    [ Video , 60 min, Bar-Ilan Theory Seminar, January 2023]
  4. Locality-Sensitive Orderings and Applications to Reliable Spanners
    [ Video , 24 min, STOC 2022 presentation]
    [ Video , 48 min, IDEAL Workshop on High-Dimensional Geometry and Analysis]
  5. Survey: Metric Embeddings into Trees and its Various Spin-offs
    [ Video , 83 min, Dagshtul 25212: Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs, May 2025]
  6. Metric Embedding into Trees
    [ Video , 85 min, BIU lecture for undergrands, July 2024] Prospective students, start here!
    [ Video , 64 min, BIU lecture for undergrands, May 2025] The most basic version of this lecture.
    [ Video , 53 min, FOCS workshop on metric embeddings, November 2022]
    [ Video , 83 min, HUJI theory seminar, March 2022]
  7. Hop-Constrained Metric Embeddings and their Applications
    [ Video , 20 min, FOCS 2021 presentation]
    The matirial is also covered by the Metric Embedding into Trees talk.
  8. Clan Embeddings into Trees, and Low Treewidth Graphs
    [ Video , 29 min, STOC 2021 presentation]
    [ Video , 67 min, Open University of Israel colloquium 2022, in Hebrew!]
    The matirial is also covered by the Metric Embedding into Trees talk.
  9. Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
    [ Video , 25 min, SODA 2021 presentation]
  10. Distributed Construction of Light Networks
    [ Video , 20 min, PODC 2020 presentation] [ Slides ]
  11. Scattering and Sparse Partitions, and their Applications
    [ Video 1 , 45 min, recorded during Simons algorithms and geometry collaboration Monthly meeting, January 2020] [ Simons slides ]
    [ Video 2, 60 min, recorded during Stony Brook (online) algorithms seminar, April 2020]
    [ ICALP presentation, 23 min, ICALP 2020 presentation] [ ICALP slides ]
  12. On Strong Diameter Padded Decompositions
    [ Video , 25 min] [ Slides ]
  13. On metric embeddings, shortest path decompositions and face cover of planar graphs
    [ Video , 45 min, recorded during a workshop on data science in low-dimensional spaces]
  14. Metric Embedding via Shortest Path Decompositions
    [ Video , 19 min, recorded during STOC 18]
  15. Steiner Point Removal with distortion O(logk), using the Noisy-Voronoi algorithm
    [ Video , 68 min] [ Slides ]
  16. Ramsey Spanning Trees and their Applications
    [ Video , 32 min] [ Slides ]
  17. The Greedy Spanner is Existentially Optimal
    [ Video , 35 min]
  18. On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
    [ Video , 28 min] [ Slides ]

Publications

  1. Stochastic Embedding of Digraphs into DAGs
    Arnold Filtser
    To appear in SODA 2026.
    [ Arxiv version ]
  2. The Squishy Grid Problem
    Zixi Cai, Kuowen Chen, Shengquan Du, Arnold Filtser, Seth Pettie, Daniel Skora
    [ Arxiv version ]
  3. How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
    Jonathan Conroy, Arnold Filtser
    In STOC 2025
    [ Conference version ] [ Arxiv version ] [ Video (STOC presentation by Jonathan Conroy)] [ Video (full lenght)]
  4. Faster Approximation Algorithms for k-Center via Data Reduction
    Arnold Filtser, Shaofeng H.-C. Jiang, Yi Li, Anurag Murty Naredla, Ioannis Psarros, Qiaoyuan Yang, Qin Zhang
    In ICML 2025
    [ Conference version ] [ Arxiv version ]
  5. Highway Dimension: a Metric View
    Andreas Emil Feldmann, Arnold Filtser
    In SODA 2025.
    [ Conference version ] [ Arxiv version ]
  6. FPT approximations for Capacitated Sum of Radii and Diameters
    Arnold Filtser, Ameet Gadekar
    [ Arxiv version ]
  7. Optimal Padded Decomposition For Bounded Treewidth Graphs
    Arnold Filtser, Tobias Friedrich, Davis Issac, Nikhil Kumar, Hung Le, Nadym Mallek, Ziena Zeif
    In TheoretiCS 2025.
    [ Journal version ] [ Arxiv version ]
  8. Near-Optimal Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs
    Arnold Filtser, Gramoz Goranci, Neel Patel, Maximilian Probst Gutenberg
    In FOCS 2024.
    [ Conference version ]
  9. On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
    Arnold Filtser
    In SOCG 2025
    [ Conference version ] [ Arxiv version ] [ Video (SOCG presentation)]
  10. Light, Reliable Spanners
    Arnold Filtser, Yuval Gitlitz, Ofer Neiman
    In SOCG 2024
    [ Conference version ] [ Arxiv version ]
  11. Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
    Sujoy Bhore, Arnold Filtser, Csaba D. Tóth
    In SODA 2024.
    [ Conference version ] [ Arxiv version ]
  12. One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
    Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D Ellis Hershkowitz, Rajmohan Rajaraman
    In FOCS 2023.
    [ Conference version ] [ Arxiv version ] [ Video (Talk by Ellis Hershkowitz)] [ Video (Talk on sparse partitions)]
  13. Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings
    Arnold Filtser
    In SOCG 2023.
    [ Conference version ] [ Arxiv version ] [ Video (SOCG presentation)]
  14. Streaming Facility Location in High Dimension via Geometric Hashing
    Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, Mingwei Yang
    [ Arxiv version ]
  15. Expander Decomposition in Dynamic Streams
    Arnold Filtser, Michael Kapralov, Mikhail Makarov
    In ITCS 2023.
    [ Conference version ] [ Arxiv version ] [ Video (ITCS presentation by Mikhail Makarov)]
  16. Communication Complexity of Inner Product in Symmetric Normed Spaces
    Alexandr Andoni, Jarosław Błasiok, Arnold Filtser
    In ITCS 2023.
    [ Conference version ] [ Arxiv version ]
  17. Low Treewidth Embeddings of Planar and Minor-Free Metrics
    Arnold Filtser, Hung Le
    In FOCS 2022.
    [ Conference version ] [ Arxiv version ] [ Video (FOCS presentation by Hung Le)]
  18. Online Spanners in Metric Spaces
    Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, Csaba D. Tóth
    In ESA 2022.
    In SIDMA 2024.
    [ Journal version ] [ Conference version ] [ Arxiv version ]
  19. Locality-Sensitive Orderings and Applications to Reliable Spanners
    Arnold Filtser, Hung Le
    In STOC 2022.
    [ Conference version ] [ Arxiv version ] [ Video (STOC presentation)] [ Video (IDEAL workshop)]
  20. Hop-Constrained Metric Embeddings and their Applications
    Arnold Filtser
    In FOCS 2021.
    [ Conference version ] [ Arxiv version ] [ Video (FOCS presentation)]
  21. Clan Embeddings into Trees, and Low Treewidth Graphs
    Arnold Filtser, Hung Le
    In STOC 2021.
    [ Conference version ] [ Arxiv version ] [ Video (STOC presentation)] [ Video (in Hebrew)]
  22. Condorcet Relaxation in Spatial Voting (or Plurality in Spatial Voting Games with Constant β)
    Arnold Filtser, Omrit Filtser
    In AAAI 2021.
    In DCG 2023.
    [ Journal version ] [ Conference version ] [ Arxiv version ]
  23. Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
    Arnold Filtser, Michael Kapralov, Navid Nouri
    In SODA 2021.
    [ Conference version ] [ Arxiv version ] [ Video (SODA presentation)]
  24. Static and Streaming Data Structures for Fréchet Distance Queries
    Arnold Filtser, Omrit Filtser
    In SODA 2021.
    In TALG 2023.
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Video (SODA presentation by Omrit Filtser)]
  25. On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs
    Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
    In FOCS 2020.
    [ Conference version ] [ Arxiv version ] [ Video (FOCS presentation by Hung Le)]
  26. Distributed Construction of Light Networks
    Michael Elkin, Arnold Filtser, Ofer Neiman
    In PODC 2020.
    [ Conference version ] [ Arxiv version ] [ Video (PODC presentation)]
  27. Scattering and Sparse Partitions, and their Applications
    Arnold Filtser
    In ICALP 2020.
    In TALG 2024.
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Video 1] [ Video 2] [ Video 3 (ICALP presentation)]
  28. Approximate Nearest Neighbor for Curves --- Simple, Efficient, and Deterministic
    Arnold Filtser, Omrit Filtser, Matthew J. Katz
    In ICALP 2020.
    In Algorithmica 2023.
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Video (ICALP presentation by Omrit Filtser)]
  29. Labelings vs. Embeddings: On Distributed Representations of Distances
    Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
    In SODA 2020.
    In DCG 2024.
    [ Journal version ] [ Conference version ] [ Arxiv version ]
  30. A Face Cover Perspective to ℓ1 Embeddings of Planar Graphs
    Arnold Filtser
    In SODA 2020.
    In TALG 2025.
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Video]
  31. On Strong Diameter Padded Decompositions
    Arnold Filtser
    In Approx 2019.
    [ Conference version ] [ Arxiv version ] [ Slides ] [ Video ]
  32. Constructing Light Spanners Deterministically in Near-Linear Time
    Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, Christian Wulff-Nilsen
    In ESA 2019.
    In TCS 2022 (Theoretical Computer Science).
    [ Journal version ] [ Conference version ] [ Arxiv version ]
  33. Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
    Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
    In SOSA 2019.
    [ Conference version ] [ Arxiv version ]
  34. Light Spanners for High Dimensional Norms via Stochastic Decompositions
    Arnold Filtser, Ofer Neiman
    In ESA 2018.
    In Algorithmica 2022
    [ Jurnal version ] [ Conference version ] [ Arxiv version ] [ Full version ]
  35. Metric Embedding via Shortest Path Decompositions
    Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman
    In STOC 2018.
    In SICOMP 2022. (SIAM Journal on Computing)
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Video 1 (STOC presentation)] [ Video 2]
  36. Steiner Point Removal with Distortion O(log k)
    Arnold Filtser
    In SODA 2018.
    [ Conference version ] [ Arxiv version ] [ Slides ]
    Steiner Point Removal with distortion O(logk), using the Relaxed-Voronoi algorithm
    This is the full version of the paper. The name was change in order to emphasis the different algorithm analysed in this paper.
    In SICOMP 2019. (SIAM Journal on Computing)
    [ Journal version ] [ Arxiv version ] [ Video ]
  37. Ramsey Spanning Trees and their Applications
    Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
    In SODA 2018.
    In TALG 2020 (Transactions on Algorithms).
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Video ] [ Slides ]
  38. Sparsification of Two-Variable Valued CSPs
    Arnold Filtser, Robert Krauthgamer
    In SIDMA 2017 (Siam journal on discrete mathematics).
    [ Journal version ] [ Arxiv version ]
  39. Distributed Monitoring of Election Winners
    Arnold Filtser, Nimrod Talmon
    In AAMAS 2017. Was nominated for best paper award. (what?!)
    In AIJ 2019 (Artificial Intelligence Journal).
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Full version ]
  40. The Greedy Spanner is Existentially Optimal
    Arnold Filtser, Shay Solomon
    In PODC 2016. Best student paper.
    In SICOMP 2020 (SIAM Journal on Computing).
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Full version ] [ Video ]
  41. On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
    Yair Bartal, Arnold Filtser, Ofer Neiman
    In SODA 2016.
    In JCSS 2019. (Journal of Computer and System Sciences)
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Video ] [ Slides ]
  42. Prioritized Metric Structures and Embedding
    Michael Elkin, Arnold Filtser, Ofer Neiman
    In STOC 2015.
    In SICOMP 2018. (SIAM Journal on Computing)
    [ Journal version ] [ Conference version ] [ Arxiv version ] [ Full version ]
  43. Terminal Embeddings
    Michael Elkin, Arnold Filtser, Ofer Neiman
    In Approx 2015.
    In TCS 2017 (Theoretical Computer Science).
    [ Journal version ] [ Conference version ] [ Arxiv version ]
  44. Efficient determination of the unique decodability of a string
    Arnold Filtser, Jiaxi Jin, Areyh Kontorovich, Ari Trachtenberg
    In ISIT 2013.
    [ Conference version ]
  • Master thesis: Terminal Embeddings.
    Supervisors: Michael Elkin and Ofer Neiman.
  • PhD thesis: On Refined Notions of Embeddings .
    Supervisors: Robert Krauthgamer and Ofer Neiman.


    • Honors

    Why not stroke your academic ego a little and list honors, awards and scholarships you have received?
    If you happen to be a more modest type, you can hide this tab by editing the #navbar section of the index.html. Below is a sample template for honors:

    • 2012 "Dance Your Ph.D" Contest winner
    • Member of the worlds largest multiple-player-single-guitar band
    • Generally awesome

    Best Relative Award

    The Best Relative Award is given annually by the Filtser family cooperation*, to a family member of the Filtser family, as recognition for great investment and donation to the family.


    Best Relative Award Laureates:

    • 2015 - Emi Filtser - for successful graduating from high school.
    • 2014 - Yosi Filtser - for successful discharging from the military (and staying alive).
    • 2013 - Naama Filtser - for being born.
    • 2012 - Omrit Filtser - for creating an infrastructure for the family to spread and multiply.





    *The head and sole member of the Filtser family cooperation is Arnold Filster.

    Personal

    I am married to Omrit Filtser (who is also in theory!), and father of Naama, Hadass, Ehud Emmanuel, and Boaz Lazer.