Last update: 07 - NOV - 2019 (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 comming 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.


Curriculum Vitae (CV).

Contact information

Arnold Filtser
Email: arnoldf at cs dot columbia dot edu

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

Publications

  1. Labelings vs. Embeddings: On Distributed Representations of Distances
    Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
    To appear in SODA 2020.
    [ Arxiv version ]
  2. A Face Cover Perspective to ℓ1 Embeddings of Planar Graphs
    Arnold Filtser
    To appear in SODA 2020.
    [ Arxiv version ] [ Video]
  3. Distributed Construction of Light Networks
    Michael Elkin, Arnold Filtser, Ofer Neiman.
    [ Arxiv version ]
  4. Approximate Nearest Neighbor for Curves --- Simple, Efficient, and Deterministic
    Arnold Filtser, Omrit Filtser, Matthew J. Katz
    [ Arxiv version ]
  5. On Strong Diameter Padded Decompositions
    Arnold Filtser
    In Approx 2019.
    [ Conference version ] [ Arxiv version ] [ Slides ] [ Video ]
  6. 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 ]
  7. Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
    Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
    In SOSA 2019.
    [ Conference version ] [ Arxiv version ]
  8. Light Spanners for High Dimensional Norms via Stochastic Decompositions
    Arnold Filtser, Ofer Neiman
    In ESA 2018.
    [ Full version ] [ Conference version ] [ Arxiv version ]
  9. 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]
  10. 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 ]
  11. Ramsey Spanning Trees and their Applications
    Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman.
    In SODA 2018.
    To appear in TALG 2020 (Transactions on Algorithms).
    [ Conference version ] [ Arxiv version ] [ Video ] [ Slides ]
  12. Sparsification of Two-Variable Valued CSPs
    Arnold Filtser, Robert Krauthgamer.
    In SIDMA 2017 (Siam journal on discrete mathematics).
    [ Journal version ] [ Arxiv version ]
  13. Distributed Monitoring of Election Winners
    Arnold Filtser, Nimrod Talmon.
    In AAMAS 2017. Was nominated for best paper award. (what?!)
    To AIJ 2019 (Artificial Intelligence Journal).
    [ Full version ] [ Journal version ] [ Conference version ] [ Arxiv version ]
  14. The Greedy Spanner is Existentially Optimal
    Arnold Filtser, Shay Solomon.
    In PODC 2016. Best student paper.
    [ Full version ] [ Conference version ] [ Arxiv version ] [ Video ]
  15. 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 ]
  16. 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 ]
  17. Terminal Embeddings
    Michael Elkin, Arnold Filtser, Ofer Neiman.
    In Approx 2015.
    In TCS 2007 (Theoretical Computer Science).
    [ Journal version ] [ Conference version ] [ Arxiv version ]
  18. 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 (do visit her homepage!) and Hadass Filtser.

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