How to walk your dog in the mountains with no magic leash.
Sariel Har-Peled,
Amir Nayyeri,
Mohammad Salavatipour,
Anastasios Sidiropoulos.
[PDF]
How strong is Nisan's pseudo-random generator?
Matei David,
Periklis Papakonstantinou,
Anastasios Sidiropoulos.
Information Processing Letters, 2011.
Near-optimal distortion bounds for embedding doubling spaces into L1.
James R. Lee,
Anastasios Sidiropoulos.
ACM Symposium on Theory of Computing (STOC 2011).
[Extended abstract: PDF,
Slides: PDF,
Video of lecture]
Computationally limited randomness.
Matei David,
Phuong Nguyen,
Periklis Papakonstantinou,
Anastasios Sidiropoulos.
Symposium on Innovations in Computer Science (ICS 2011).
[PDF]
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]
Optimal stochastic planarization.
Anastasios Sidiropoulos.
IEEE Symposium on Foundations of Computer Science (FOCS 2010).
[Arxiv,
slides: PDF,
Video of lecture]
On-line embeddings.
Piotr Indyk,
Avner Magen,
Anastasios Sidiropoulos,
Anastasios Zouzias.
Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010).
[PDF]
Genus and the geometry of the cut graph.
James R. Lee,
Anastasios Sidiropoulos.
ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
[PDF,
slides: PDF]
Inapproximability for planar embedding problems.
Jeff Edmonds,
Anastasios Sidiropoulos,
Anastasios Zouzias.
ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
[PDF]
Undecidability and intractability results concerning datalog
programs and their persistency numbers.
Stavros Cosmadakis,
Eugenie Foustoucos,
Anastasios Sidiropoulos.
ACM Transactions on Computational Logic, 2010.
[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]
On the geometry of graphs with a forbidden minor.
James R. Lee,
Anastasios Sidiropoulos.
ACM Symposium on Theory of Computing (STOC 2009).
[Extended abstract: PDF,
slides: PDF]
Streaming Embeddings with Slack.
Christiane Lammersen,
Anastasios Sidiropoulos,
Christian Sohler.
Algorithms and Data Structures Symposium (WADS 2009).
Inapproximability for metric embeddings into Rd.
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]
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]
Fat polygonal partitions with applications to visualization and embeddings.
Mark de Berg,
Krzysztof Onak,
Anastasios Sidiropoulos.
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]
On distributing symmetric streaming computations.
Jon Feldman,
S. Muthukrishnan,
Anastasios Sidiropoulos,
Cliff Stein,
Zoya Svitkina.
ACM-SIAM Symposium on Discrete Algorithms (SODA 2008).
[PS,
PDF,
slides: 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]
Approximation algorithms for embedding general metrics into trees.
Mihai Badoiu,
Piotr Indyk,
Anastasios Sidiropoulos.
ACM-SIAM Symposium on Discrete Algorithms (SODA 2007).
[PS,
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]
Convergence and approximation in potential games.
George Christodoulou,
Vahab S. Mirrokni,
Anastasios Sidiropoulos.
Symposium on Theoretical Aspects of Computer Science (STACS 2006).
[PS,
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]
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]
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]