Last update: 10 - SEP - 2020 (d-m-y).

About Me

I am a Postdoc at the Computer Science Department at Columbia University, hosted by Alex Andoni and Rocco Servedio. The postdoc is part of the the Simons Collaboration on Algorithms and Geometry.
Prior to coming to Columbia, 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 interest is theoretical computer science. More specifically: Metric Spaces, Low-Distortion Embeddings, Randomized Algorithms and Approximation.

Contact information

Arnold Filtser
Email: arnold273 at gmail dot com
Office: LOL

free hits
<> free hits
<>

Video

This page includes several talks regarding my research papers. As researches, we are often give talks in different venues. Once the slides and the talk are prepared, it is only a small additional effort to record. I encourage everyone to do so!

  1. Distributed Construction of Light Networks
    [ Video , 20 min, PODC 2020 presentation] [ Slides ]
  2. 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 ]
  3. On Strong Diameter Padded Decompositions
    [ Video , 25 min] [ Slides ]
  4. 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]
  5. Metric Embedding via Shortest Path Decompositions
    [ Video , 19 min, recorded during STOC 18]
  6. Steiner Point Removal with distortion O(logk), using the Noisy-Voronoi algorithm
    [ Video , 68 min] [ Slides ]
  7. Ramsey Spanning Trees and their Applications
    [ Video , 32 min] [ Slides ]
  8. The Greedy Spanner is Existentially Optimal
    [ Video , 35 min]
  9. On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
    [ Video , 28 min] [ Slides ]

Publications

  1. On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs
    Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
    To appear in FOCS 2020.
    [ Arxiv version ]
  2. Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
    Arnold Filtser, Michael Kapralov, Navid Nouri
    [ Arxiv version ]
  3. Static and Streaming Data Structures for Fréchet Distance Queries
    Arnold Filtser, Omrit Filtser
    [ Arxiv version ]
  4. Plurality in Spatial Voting Games with constant β
    Arnold Filtser, Omrit Filtser
    [ Arxiv version ]
  5. Distributed Construction of Light Networks
    Michael Elkin, Arnold Filtser, Ofer Neiman
    In PODC 2020.
    [ Conference version ] [ Arxiv version ] [ Video]
  6. Scattering and Sparse Partitions, and their Applications
    Arnold Filtser
    In ICALP 2020.
    [ Conference version ] [ Arxiv version ] [ Video 1] [ Video 2] [ Video 3 (ICALP 2020 presentation)]
  7. Approximate Nearest Neighbor for Curves --- Simple, Efficient, and Deterministic
    Arnold Filtser, Omrit Filtser, Matthew J. Katz
    In ICALP 2020.
    [ Conference version ] [ Arxiv version ] [ Video (ICALP presentation by Omrit Filtser)]
  8. Labelings vs. Embeddings: On Distributed Representations of Distances
    Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
    In SODA 2020.
    [ Conference version ] [ Arxiv version ]
  9. A Face Cover Perspective to ℓ1 Embeddings of Planar Graphs
    Arnold Filtser
    In SODA 2020.
    [ Conference version ] [ Arxiv version ] [ Video]
  10. On Strong Diameter Padded Decompositions
    Arnold Filtser
    In Approx 2019.
    [ Conference version ] [ Arxiv version ] [ Slides ] [ Video ]
  11. Constructing Light Spanners Deterministically in Near-Linear Time
    Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, Christian Wulff-Nilsen
    In ESA 2019.
    [ Conference version ] [ Arxiv version ]
  12. Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
    Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
    In SOSA 2019.
    [ Conference version ] [ Arxiv version ]
  13. Light Spanners for High Dimensional Norms via Stochastic Decompositions
    Arnold Filtser, Ofer Neiman
    In ESA 2018.
    [ Full version ] [ Conference version ] [ Arxiv version ]
  14. Metric Embedding via Shortest Path Decompositions
    Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman
    In STOC 2018.
    [ Conference version ] [ Arxiv version ] [ Video 1 (STOC)] [ Video 2]
  15. 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 ]
  16. 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 ]
  17. Sparsification of Two-Variable Valued CSPs
    Arnold Filtser, Robert Krauthgamer
    In SIDMA 2017 (Siam journal on discrete mathematics).
    [ Journal version ] [ Arxiv version ]
  18. 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 ]
  19. 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 ]
  20. 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 ]
  21. 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 ]
  22. Terminal Embeddings
    Michael Elkin, Arnold Filtser, Ofer Neiman
    In Approx 2015.
    In TCS 2017 (Theoretical Computer Science).
    [ Journal version ] [ Conference version ] [ Arxiv version ]
  23. 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.
    Committee: Eden Chlamtáč, and Amos Beimel.
  • PhD thesis: On Refined Notions of Embeddings .
    Supervisors: Robert Krauthgamer and Ofer Neiman.
    Committee: Yair Bartal, Eden Chlamtáč, and Michael Elkin.


  • 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 Filtser and Hadass Filtser.

    My hobbies are skiing, taekwondo, wines, hockey and role playing games.