Publications by Anastasios Sidiropoulos (by subject)

Poisoning

• Geometric Algorithms for k-NN Poisoning.
  Diego Ihara Centurion, Karine Chubarian, Bohan Fan, Francesco Sgherzi, Thiruvenkadam S. Radhakrishnan, Anastasios Sidiropoulos, Angelo Straight.
  Canadian Conference on Computational Geometry (CCCG 2023). [ArXiv]

Blockchains and permissionless systems

• Rational Economic Behaviours in the Bitcoin Lightning Network.
  Andrea Carotti, Cosimo Sguanci, Anastasios Sidiropoulos.
  IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2024). [ArXiv]


• Mass Exit Attacks on the Lightning Network.
  Cosimo Sguanci, Anastasios Sidiropoulos.
  IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2023). [ArXiv]

Algorithmic topological graph theory

• Polylogarithmic approximation for Euler genus on bounded degree graphs
  Ken-ichi Kawarabayashi, Anastasios Sidiropoulos.
  ACM Symposium on Theory of Computing (STOC 2019).


• Polylogarithmic approximation for minimum planarization (almost)
  Ken-ichi Kawarabayashi, Anastasios Sidiropoulos.
  IEEE Symposium on Foundations of Computer Science (FOCS 2017). [ArXiv]


• Beyond the Euler characteristic: Approximating the genus of general graphs.
  Ken-ichi Kawarabayashi, Anastasios Sidiropoulos.
  ACM Symposium on Theory of Computing (STOC 2015). [ArXiv]


• Approximation algorithms for Euler genus and related problems.
  Chandra Chekuri, Anastasios Sidiropoulos.
  Journal version: SIAM Journal on Computing (SICOMP), 2018. [Link to article]
  Conference version: IEEE Symposium on Foundations of Computer Science (FOCS 2013). [ArXiv]


• A pseudo-approximation for the genus of Hamiltonian graphs.
  Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos.
  Journal version: Theory of Computing, 2017. [Link to article]
  Conference version: Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013).
  


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

Deep learning

• NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs.
  Evan McCarty, Qi Zhao, Anastasios Sidiropoulos, Yusu Wang.
  Advances in Neural Information Processing Systems (NeurIPS 2021). [Conference paper]

Learning

• Learning Lines with Ordinal Constraints.
  Bohan Fan, Diego Ihara Centurion, Neshat Mohammadi, Francesco Sgherzi, Anastasios Sidiropoulos, Mina Valizadeh.
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2020). [ArXiv]


• Learning Mahalanobis Metric Spaces via Geometric Approximation Algorithms
  Diego Ihara Centurion, Neshat Mohammadi, Anastasios Sidiropoulos
  In preparation. [ArXiv]


• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families.
  Brian Axelrod, Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart, Gregory Valiant.
  Advances in Neural Information Processing Systems (NeurIPS 2019). [ArXiv]


• Algorithms for metric learning via contrastive embeddings
  Diego Ihara Centurion, Neshat Mohammadi, Anastasios Sidiropoulos
  ACM Symposium on Computational Geometry (SoCG 2019). [ArXiv]


• Near-optimal sample complexity bounds for maximum likelihood estimation of multivariate log-concave densities.
  Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart.
  Annual Conference on Learning Theory (COLT 2018). [ArXiv]


• Learning Wasserstein distance in spaces of low intrinsic dimension.
  Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos.
  Submitted.

Applied Machine Learning

• A Risk Assessment Tool for the Contamination of Aflatoxins on Dried Figs based on Machine Learning Algorithms.
  Klimentia, Kottaridi, Demopoulos Vasilis, Sidiropoulos Anastasios, Ihara Diego Centurion, Nikolaidis Vasileios, Antonopoulos Dimitrios.
  International Journal of Nutrition and Food Engineering, 2021. [Link to article]

Sparsest-cut and multi-commodity flows

• Embeddings of Planar Quasimetrics into Directed L₁ and Polylogarithmic Approximation for Directed Sparsest-Cut
  Ken-ichi Kawarabayashi, Anastasios Sidiropoulos.
  IEEE Symposium on Foundations of Computer Science (FOCS 2021). [ArXiv]


• Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion.
  Timothy Carpenter, Ario Salmasi, Anastasios Sidiropoulos.
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2019). [Link to article], [ArXiv]


• On constant multi-commodity flow-cut gaps for directed minor-free graphs.
  Ario Salmasi, Anastasios Sidiropoulos, Vijay Sridhar.
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2019). [ArXiv]


• Non-positive curvature and the planar embedding conjecture.
  Anastasios Sidiropoulos.
  IEEE Symposium on Foundations of Computer Science (FOCS 2013). [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.
  Conference 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.

Geometry

• Computing Bi-Lipschitz Outlier Embeddings into the Line.
  Karine Chubarian, Anastasios Sidiropoulos.
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2020). [ArXiv]


• Metric embeddings with outliers.
  Anastasios Sidiropoulos, Dingkang Wang, Yusu Wang.
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2017). [ArXiv]


• Constant-distortion embeddings of Hausdorff metrics into constant-dimensional L_p spaces.
  Arturs Backurs, Anastasios Sidiropoulos.
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016).


• Quasimetric embeddings and their applications.
  Facundo Memoli, Anastasios Sidiropoulos, Vijay Sridhar.
  Journal version: Algorithmica [Link to article].
  Conference version: International Colloquium on Automata, Languages, and Programming (ICALP 2016).


• Computing the Gromov-Hausdorff distance for metric trees.
  Pankaj K. Agarwal, Kyle J. Fox, Abhinandan Nath, Anastasios Sidiropoulos, Yusu Wang.
  Journal version: ACM Transactions on Algorithms, 2018. [Link to article]
  Conference version: 26th International Symposium on Algorithms and Computation (ISAAC 2015).


• The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems.
  Daniel Marx, Anastasios Sidiropoulos.
  ACM Symposium on Computational Geometry (SoCG 2014).


• 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.
  Conference version: IEEE Symposium on Foundations of Computer Science (FOCS 2008). [Extended abstract: PDF, full version: PDF, slides: PDF]

Clustering

• Sketching and Clustering Metric Measure Spaces.
  Facundo Memoli, Anastasios Sidiropoulos, Kritika Singhal.
  Submitted. [ArXiv]


• Temporal Hierarchical Clustering.
  Tamal K. Dey, Alfred Rossi, Anastasios Sidiropoulos.
  International Symposium on Algorithms and Computation (ISAAC 2017).


• Temporal Clustering.
  Tamal K. Dey, Alfred Rossi, Anastasios Sidiropoulos.
  European Symposium on Algorithms (ESA 2017). [ArXiv]


• Spectral concentration and greedy k-clustering.
  Tamal K. Dey, Pan Peng, Alfred Rossi, Anastasios Sidiropoulos.
  Computational Geometry: Theory and Applications, 2019. [ArXiv]


• Approximate greedy clustering and distance selection for graph metrics.
  David Eppstein, Sariel Har-Peled, Anastasios Sidiropoulos.
  Journal of Computational Geometry, 2020. [ArXiv]

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.
  Journal version: Discrete & Computational Geometry. [Link to article]
  Conference version: 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]
  Conference 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]

Expander graphs

• Layouts of expander graphs.
  Vida Dujmovic, Anastasios Sidiropoulos, David R. Wood.
  Chicago Journal of Theoretical Computer Science, 2016. [Link to article, ArXiv]

Fractal dimension

• Fractal dimension and lower bounds for geometric problems.
  Anastasios Sidiropoulos, Kritika Singhal, Vijay Sridhar.
  ACM Symposium on Computational Geometry (SoCG 2018). [ArXiv]


• Algorithmic interpretations of fractal dimension.
  Anastasios Sidiropoulos, Vijay Sridhar.
  ACM Symposium on Computational Geometry (SoCG 2017). [ArXiv]

Low-dimensional geometry

• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces.
  Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Anastasios Sidiropoulos.
  ACM Symposium on Computational Geometry (SoCG 2018). [ArXiv]


• Computing the Frechet distance between polygons with holes.
  Amir Nayyeri, Anastasios Sidiropoulos.
  International Colloquium on Automata, Languages, and Programming (ICALP 2015).


• 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, Piotr Indyk, Yuri Rabinovich, Harald Raecke, R. Ravi, Anastasios Sidiropoulos.
  Journal version: SIAM Journal on Discrete Mathematics [Link to article].
  Conference version: 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

• Approximating the I/O complexity of one-shot red-blue pebbling.
  Timothy Carpenter, Fabrice Rastello, P. Sadayappan, Anastasios Sidiropoulos.
  ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), brief announcement.


• Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs.
  Daniel Marx, Ario Salmasi, Anastasios Sidiropoulos.
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016). [ArXiv]


• Minimum d-dimensional arrangement with fixed points.
  Anupam Gupta, Anastasios Sidiropoulos.
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2014). [ArXiv]


• A nearly-optimal approximation algorithm for asymmetric TSP on embedded graphs.
  Jeff Erickson, Anastasios Sidiropoulos.
  ACM Symposium on Computational Geometry (SoCG 2014). [ArXiv]


• 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.
  Conference 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: Journal of Computational Geometry.
  Conference version: Circular partitions with applications to visualization and embeddings.
  Krzysztof Onak, Anastasios Sidiropoulos.
  ACM Symposium on Computational Geometry (SoCG 2008). [PS, PDF, slides: PDF]

Computational linguistics

• Grouping Words with Semantic Diversity.
  Karine Chubarian, Abdul Rafae Khan, Anastasios Sidiropoulos, Jia Xu.
  NAACL-HLT 2021.

Gerrymandering and fairness

• Maximizing coverage while ensuring fairness: a tale of conflicting objective.
  Abolfazl Asudeh, Tanya Berger-Wolf, Bhaskar DasGupta, Anastasios Sidiropoulos.
  Algorithmica, 2022. [ArXiv]


• On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering.
  Tanima Chatterjee, Bhaskar DasGupta, Laura Palmieri, Zainab Al-Qurashi Anastasios Sidiropoulos.
  Journal of Combinatorial Optimization, 2020. [ArXiv]

Game theory

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

Parallel algorithms and systems

• Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale
  Spyros Blanas, Paraschos Koutris, Anastasios Sidiropoulos.
  Conference on Innovative Data Systems Research (CIDR 2020).


• Chasing Similarity: Distribution-aware Aggregation Scheduling
  Feilong Liu, Ario Salmasi, Spyros Blanas, Anastasios Sidiropoulos.
  Proceedings of the VLDB Endowment (PVLDB), 2018. [ArXiv]

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]