Publications by Anastasios Sidiropoulos (chronological list)

1. Non-positive curvature, and the planar embedding conjecture.
   Anastasios Sidiropoulos.
   Submitted. [ArXiv]


2. A nearly-optimal approximation algorithm for asymmetric TSP on embedded graphs.
   Jeff Erickson, Anastasios Sidiropoulos.
   Submitted. [ArXiv]


3. Approximation algorithms for Euler genus, and related problems.
   Chandra Chekuri, Anastasios Sidiropoulos.
   Submitted. [ArXiv]


4. A pseudo-approximation for the genus of Hamiltonian graphs.
   Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos.
   Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013), to appear.


5. Euclidean spanners in high dimensions.
   Sariel Har-Peled, Piotr Indyk, Anastasios Sidiropoulos.
   ACM-SIAM Symposium on Discrete Algorithms (SODA 2013). [PDF]


6. Planarizing an unknown surface.
   Yury Makarychev, Anastasios Sidiropoulos.
   Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2012). [Arxiv]


7. How to walk your dog in the mountains with no magic leash.
   Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour, Anastasios Sidiropoulos.
   ACM Symposium on Computational Geometry (SoCG 2012). [PDF]


8. Near-optimal distortion bounds for embedding doubling spaces into L₁.
   James R. Lee, Anastasios Sidiropoulos.
   ACM Symposium on Theory of Computing (STOC 2011). [Extended abstract: PDF, Slides: PDF, Video of lecture]


9. On graph crossing number and edge planarization.
   Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos.
   ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). [Extended abstract: PDF, full version: PDF, slides: PDF]


10. Computationally limited randomness.
    Matei David, Phuong Nguyen, Periklis Papakonstantinou, Anastasios Sidiropoulos.
    Symposium on Innovations in Computer Science (ICS 2011). [PDF]


11. How strong is Nisan's pseudo-random generator?
    Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos.
    Information Processing Letters, 2011.


12. Optimal stochastic planarization.
    Anastasios Sidiropoulos.
    IEEE Symposium on Foundations of Computer Science (FOCS 2010). [Arxiv, slides: PDF, Video of lecture]


13. On-line embeddings.
    Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias.
    Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010). [PDF]


14. Genus and the geometry of the cut graph.
    James R. Lee, Anastasios Sidiropoulos.
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). [PDF, slides: PDF]


15. Inapproximability for planar embedding problems.
    Jeff Edmonds, Anastasios Sidiropoulos, Anastasios Zouzias.
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). [PDF]


16. Undecidability and intractability results concerning datalog programs and their persistency numbers.
    Stavros Cosmadakis, Eugenie Foustoucos, Anastasios Sidiropoulos.
    ACM Transactions on Computational Logic, 2010. [PDF]


17. Randomly removing g handles at once.
    Glencora Borradaile, James R. Lee, Anastasios Sidiropoulos.
    Journal version: Invited to Computational Geometry. [Link to article]
    Preliminary version: ACM Symposium on Computational Geometry (SoCG 2009). [PDF]


18. On the geometry of graphs with a forbidden minor.
    James R. Lee, Anastasios Sidiropoulos.
    Preliminary version: ACM Symposium on Theory of Computing (STOC 2009). [Extended abstract: PDF, slides: PDF]
    
• Journal version, part I:
  Pathwidth, trees, and random embeddings.
  James R. Lee, Anastasios Sidiropoulos.
  Combinatorica, to appear.


19. Streaming Embeddings with Slack.
    Christiane Lammersen, Anastasios Sidiropoulos, Christian Sohler.
    Algorithms and Data Structures Symposium (WADS 2009).


20. Inapproximability for metric embeddings into R^d.
    Jiri Matousek, Anastasios Sidiropoulos.
    Journal version: Transactions of the AMS, 2010.
    Preliminary version: IEEE Symposium on Foundations of Computer Science (FOCS 2008). [Extended abstract: PDF, full version: PDF, slides: PDF]


21. Ordinal embedding: Approximation algorithms and dimensionality reduction.
    Mihai Badoiu, Erik Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, Morteza Zadimoghaddam.
    Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008). [PS, PDF]


22. Fat polygonal partitions with applications to visualization and embeddings.
    Mark de Berg, Krzysztof Onak, Anastasios Sidiropoulos.
    Journal version: Submitted. [Arxiv]
    Preliminary version: Circular partitions with applications to visualization and embeddings.
    Krzysztof Onak, Anastasios Sidiropoulos.
    ACM Symposium on Computational Geometry (SoCG 2008). [PS, PDF, slides: PDF]


23. On distributing symmetric streaming computations.
    Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina.
    Journal version: Invited to ACM Transactions on Algorithms, 2010.
    Preliminary version: ACM-SIAM Symposium on Discrete Algorithms (SODA 2008). [PS, PDF, slides: PDF]


24. Probabilistic embeddings of bounded genus graphs into planar graphs.
    Piotr Indyk, Anastasios Sidiropoulos.
    ACM Symposium on Computational Geometry (SoCG 2007). [PS, PDF, slides: PDF]


25. Approximation algorithms for embedding general metrics into trees.
    Mihai Badoiu, Piotr Indyk, Anastasios Sidiropoulos.
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2007). [Extended abstract: PS, PDF, full version: PDF, slides: PDF]


26. Embedding ultrametrics into low-dimensional spaces.
    Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos.
    ACM Symposium on Computational Geometry (SoCG 2006). [PS, PDF, slides: PDF]


27. Convergence and approximation in potential games.
    George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos.
    Journal version: Theoretical Computer Science, to appear.
    Preliminary version: Symposium on Theoretical Aspects of Computer Science (STACS 2006). [PS, PDF]
    


28. Low-distortion embeddings of general metrics into the line.
    Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos.
    ACM Symposium on Theory of Computing (STOC 2005). [Extended abstract: PS, PDF, full version: PDF]


29. Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.
    Noga Alon, Mihai Badoiu, Erik Demaine, Martin Farach-Colton, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos.
    Journal version: ACM Transactions on Algorithms, 2008.
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2005). [PS, PDF, slides: PDF]


30. Approximation algorithms for low-distortion embeddings into low-dimensional spaces.
    Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Raecke, R. Ravi, Anastasios Sidiropoulos.
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2005). [PS, PDF]


31. Fractional and integral coloring of locally-symmetric sets of paths on binary trees.
    Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano, Anastasios Sidiropoulos.
    Workshop on Approximation and On-line Algorithms (WAOA 2003). [PS, PDF]

Thesis

• PhD Thesis.
  Computational metric embeddings.
  Dept. of Electrical Engineering and Computer Science, MIT, May 2008. [PS, PDF]


• MSc Thesis.
  Approximation algorithms for low-distortion embeddings into low-dimensional spaces.
  Dept. of Electrical Engineering and Computer Science, MIT, May 2005. [PS, PDF]