<>
<>

Video

1. On Sparse partitions
   [ Video , 45 min, DIMACS Workshop on Efficient Algorithms for High Dimensional Metrics: New Tools, May 2024]
   
2. Locality-Sensitive Orderings
   [ Video , 60 min, Bar-Ilan Theory Seminar, January 2023]
   
3. 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]
4. Metric Embedding into Trees
   [ Video , 85 min, BIU lecture for undergrands, July 2024] Prospective students, start here!
   [ Video , 53 min, FOCS workshop on metric embeddings, November 2022]
   [ Video , 83 min, HUJI theory seminar, March 2022]
5. 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.
6. 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.
7. Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
   [ Video , 25 min, SODA 2021 presentation]
8. Distributed Construction of Light Networks
   [ Video , 20 min, PODC 2020 presentation] [ Slides ]
9. 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 ]
   
10. On Strong Diameter Padded Decompositions
    [ Video , 25 min] [ Slides ]
11. 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]
12. Metric Embedding via Shortest Path Decompositions
    [ Video , 19 min, recorded during STOC 18]
13. Steiner Point Removal with distortion O(logk), using the Noisy-Voronoi algorithm
    [ Video , 68 min] [ Slides ]
14. Ramsey Spanning Trees and their Applications
    [ Video , 32 min] [ Slides ]
15. The Greedy Spanner is Existentially Optimal
    [ Video , 35 min]
16. On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
    [ Video , 28 min] [ Slides ]

Publications

1. Highway Dimension: a Metric View
   Andreas Emil Feldmann, Arnold Filtser
   To appear in SODA 2025.
   
2. FPT approximations for Capacitated Sum of Radii and Diameters
   Arnold Filtser, Ameet Gadekar
   [ Arxiv version ]
3. Optimal Padded Decomposition For Bounded Treewidth Graphs
   Arnold Filtser, Tobias Friedrich, Davis Issac, Nikhil Kumar, Hung Le, Nadym Mallek, Ziena Zeif
   [ Arxiv version ]
4. 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 ]
5. On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
   Arnold Filtser
   [ Arxiv version ]
6. Light, Reliable Spanners
   Arnold Filtser, Yuval Gitlitz, Ofer Neiman
   In SOCG 2024
   [ Conference version ] [ Arxiv version ]
7. 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 ]
8. 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)]
9. Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings
   Arnold Filtser
   In SOCG 2023.
   [ Conference version ] [ Arxiv version ] [ Video (SOCG presentation)]
10. 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 ]
11. Expander Decomposition in Dynamic Streams
    Arnold Filtser, Michael Kapralov, Mikhail Makarov
    In ITCS 2023.
    [ Conference version ] [ Arxiv version ] [ Video (ITCS presentation by Mikhail Makarov)]
12. Communication Complexity of Inner Product in Symmetric Normed Spaces
    Alexandr Andoni, Jarosław Błasiok, Arnold Filtser
    In ITCS 2023.
    [ Conference version ] [ Arxiv version ]
13. 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)]
14. Online Spanners in Metric Spaces
    Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, Csaba D. Tóth
    In ESA 2022.
    In SIDMA 2024.
    [ Conference version ] [ Arxiv version ] [ Journal version ]
15. 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)]
16. Hop-Constrained Metric Embeddings and their Applications
    Arnold Filtser
    In FOCS 2021.
    [ Conference version ] [ Arxiv version ] [ Video (FOCS presentation)]
17. 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)]
18. 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 ]
19. 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)]
20. Static and Streaming Data Structures for Fréchet Distance Queries
    Arnold Filtser, Omrit Filtser
    In SODA 2021.
    In TALG 2023.
    [ Conference version ] [ Arxiv version ] [ Journal version ] [ Video (SODA presentation by Omrit Filtser)]
21. 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)]
22. Distributed Construction of Light Networks
    Michael Elkin, Arnold Filtser, Ofer Neiman
    In PODC 2020.
    [ Conference version ] [ Arxiv version ] [ Video (PODC presentation)]
23. Scattering and Sparse Partitions, and their Applications
    Arnold Filtser
    In ICALP 2020.
    In TALG 2024.
    [ Conference version ] [ Arxiv version ] [ Journal version ] [ Video 1] [ Video 2] [ Video 3 (ICALP presentation)]
24. 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)]
25. 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 ]
26. A Face Cover Perspective to ℓ1 Embeddings of Planar Graphs
    Arnold Filtser
    In SODA 2020.
    To appear in TALG 2024.
    [ Conference version ] [ Arxiv version ] [ Video]
27. On Strong Diameter Padded Decompositions
    Arnold Filtser
    In Approx 2019.
    [ Conference version ] [ Arxiv version ] [ Slides ] [ Video ]
28. 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 ]
29. Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
    Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
    In SOSA 2019.
    [ Conference version ] [ Arxiv version ]
30. Light Spanners for High Dimensional Norms via Stochastic Decompositions
    Arnold Filtser, Ofer Neiman
    In ESA 2018.
    In Algorithmica 2022
    [ Full version ] [ Conference version ] [ Arxiv version ] [ Jurnal version ]
31. 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]
32. 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 ]
33. 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 ]
34. Sparsification of Two-Variable Valued CSPs
    Arnold Filtser, Robert Krauthgamer
    In SIDMA 2017 (Siam journal on discrete mathematics).
    [ Journal version ] [ Arxiv version ]
35. 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).
    [ Full version ] [ Journal version ] [ Conference version ] [ Arxiv version ]
36. The Greedy Spanner is Existentially Optimal
    Arnold Filtser, Shay Solomon
    In PODC 2016. Best student paper.
    In SICOMP 2020 (SIAM Journal on Computing).
    [ Full version ] [ Journal version ] [ Conference version ] [ Arxiv version ] [ Video ]
37. 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 ]
38. Prioritized Metric Structures and Embedding
    Michael Elkin, Arnold Filtser, Ofer Neiman
    In STOC 2015.
    In SICOMP 2018. (SIAM Journal on Computing)
    [ Full version ] [ Journal version ] [ Conference version ] [ Arxiv version ]
39. Terminal Embeddings
    Michael Elkin, Arnold Filtser, Ofer Neiman
    In Approx 2015.
    In TCS 2017 (Theoretical Computer Science).
    [ Journal version ] [ Conference version ] [ Arxiv version ]
40. Efficient determination of the unique decodability of a string
    Arnold Filtser, Jiaxi Jin, Areyh Kontorovich, Ari Trachtenberg
    In ISIT 2013.
    [ Conference version ]

Teaching:

• Spring 2019:
  • Discrete Structures and Combinatorics
    
• Spring 2018:
  • Discrete Structures and Combinatorics
    
• Spring 2017:
  • Discrete Structures and Combinatorics
    
• Spring 2016:
  • Discrete Structures and Combinatorics
    
• Spring 2015:
  • Discrete Structures and Combinatorics
    
• Fall 2015:
  • Automata and Formal Languages
    
• Spring 2014:
  • Discrete Structures and Combinatorics
    
• Fall 2014:
  • Automata and Formal Languages
    
• Spring 2013:
  • Discrete Structures and Combinatorics
    
• Fall 2013:
  • Automata and Formal Languages
    

Grading:

• Fall 2019:
  • Algorithms 2
    
• Fall 2018:
  • Complexity
    
• Fall 2017:
  • Complexity
    
• Fall 2016:
  • Algorithms 2
    
  • Spectral graph theory
    

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.