Publications by Anastasios Sidiropoulos (by subject)

Sparsest-cut, and multi-commodity flows

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


• 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]


• 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.

High-dimensional geometry

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


• 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]

Algorithms on planar graphs, and surfaces

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


• 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]


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


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


• 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]


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

Low-dimensional geometry

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


• 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]


• 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]


• 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]


• 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]


• 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]


• 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]

Database theory

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

Randomness in computation

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


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

Approximation algorithms

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


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


• 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.


• 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]


• 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]

Streaming, and on-line computation

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


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


• 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]

Visualization

• 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]

Game theory

• 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]
  

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]