Research
40. Triangle Evacuation of 2 Agents in the Wireless Model & the Power of Choosing a Starting Point
With Woojin Jang
Journal of Computer and System Sciences (2025)
Journal version (external link, opens in new window)
39. The Fagnano Triangle Patrolling Problem
With Somnath Kundu and Paweł Prałat
Discrete Mathematics & Theoretical Computer Science (2025)
Journal version (external link, opens in new window)
38. Weighted Group Search on the Disk & Improved Lower Bounds for Priority Evacuation
With Xin Wang
Journal of Computer and System Sciences (2025)
Journal version (external link, opens in new window)
37. Makespan Trade-offs for Visiting Triangle Edges
With Somnath Kundu and Paweł Prałat
Discrete Mathematics & Theoretical Computer Science (2024)
Journal version (external link, opens in new window)
36. Overcoming Probabilistic Faults in Disoriented Linear Search
With Nikos Giachoudis and Evangelos Kranakis
Theoretical Computer Science (2024)
Journal version (external link, opens in new window)
35. Improved Collision-Free Multi-Axis Tool-Path for Additive Manufacturing
With Rahnuma Islam Nishat, Yeganeh Bahoo, Robert Hedrick, R. Jill Urbanic
Computer-Aided Design and Applications (2024)
(PDF file) Journal version (external link, opens in new window)
34. Collision-Free Multi-Axis Tool-Path for Additive Manufacturing
With Rahnuma Islam Nishat, Yeganeh Bahoo, Robert Hedrick, R. Jill Urbanic
Computer-Aided Design and Applications (2023)
(PDF file) Journal version (external link, opens in new window)
33. Optimal Circle Search Despite the Presence of Faulty Robots
With Evangelos Kranakis, Nikos Leonardos, Aris Pagourtzis and Ioannis Papaioannou
Information Processing Letters (2023)
Journal version (external link, opens in new window)
32. Evacuating from ell-p Unit Disks in the Wireless Model
With Somnath Kundu, Sean Leizerovich and Jesse Lucier
Theoretical Computer Science (2022)
Journal version (external link, opens in new window)
31. Algorithms for p-faulty Search on a Half-Line
With Anthony Bonato, Calum MacCury and Paweł Prałat
Algorithmica (2022)
Journal version (external link, opens in new window)
30. Weighted Group Search on a Line & Implications to the Priority Evacuation Problem
With Jesse Lucier
Theoretical Computer Science (2022)
Journal version (external link, opens in new window)
29. The Unit Acquisition Number of Binomial Random Graphs
With Somnath Kundu and Paweł Prałat
Electronic Journal of Combinatorics (2021)
Journal version (external link, opens in new window) - Also on arXiv:2006.13294 (external link, opens in new window) (preprint, 2020)
28. Photon Beam Energy Dependent Single-Arc Volumetric Modulated Arc Optimization
With Shadab Momin, James L Gräfe and Rao F Khan
Physica Medica (2021)
Journal version (external link, opens in new window)
27. Search on a Line by Byzantine Robots
With Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jurek Opatrny and Sunil Shende
International Journal of Foundations of Computer Science (2021)
Journal version (external link, opens in new window)
26. Time-Energy Tradeoffs for Evacuation by Two Robots in the Wireless Model
With Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny and Sunil Shende
Theoretical Computer Science (2020)
Journal version (external link, opens in new window)
25. A Multi-Objective Optimization Problem on Evacuating 2 Robots from the Disk in the Face-to-Face Model; Trade-offs Between Worst-Case and Average-Case Analysis
With Huda Chuangpishit and Preeti Sharma
Information, Artificial Intelligence (2020), Special Issue: Distributed Systems and Mobile Computing
Journal version (external link, opens in new window)
24. Priority Evacuation from a Disk: The case of at Least 4 Robots
With Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny and Sunil Shende
Theoretical Computer Science (2020)
Journal version (external link)
23. Evacuating Robots from a Disk Using Face-to-Face Communication
With Jurek Czyzowicz, Evangelos Kranakis, Lata Narayanan, Jarda Opatrny and Birgit Vogtenhuber
Discrete Mathematics & Theoretical Computer Science (2020)
Journal version (external link, opens in new window)
22. Lift & Project Systems Performing on the Partial Vertex Cover Polytope
With Andy (Jia) Jiang, Edward Lee, Astrid A. Olave, Ian Seong and Twesh Upadhyaya
Theoretical Computer Science (2020)
Journal version (external link, opens in new window)
21. Priority Evacuation from a Disk: the case of n=1,2,3
With Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny and Sunil Shende
Theoretical Computer Science (2019)
Journal version (external link, opens in new window)
20. Symmetric Rendezvous With Advice: How to Rendezvous in a Disk
With Jay Griffiths and Yuval Yakubov
Journal of Parallel and Distributed Computing (2019)
Journal version (external link, opens in new window)
19. Simultaneous Optimization of Mixed Photon Energy Beams in Volumetric Modulated Arc Therapy
With Shadab Momin, James L Gräfe and Rao F Khan
Medical Physics (2019)
Journal version (external link, opens in new window)
18. Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models
With George Karakostas and Evangelos Kranakis
Discrete Mathematics & Theoretical Computer Science (2019)
Journal version (external link, opens in new window)
17. Treasure Evacuation with One Robot on a Disk
With George Karakostas and Evangelos Kranakis
Theoretical Computer Science (2020)
Journal version (external link, opens in new window)
16. Lift-and-Project Methods for Set Cover and Knapsack
With Eden Chlamtac and Zac Friggstad
Algorithmica (2018)
Journal version (external link, opens in new window)
15. Know When to Persist: Deriving Value from a Stream Buffer
With George Karakostas, Evangelos Kranakis and Danny Krizanc
Theoretical Computer Science (2017)
Journal version (external link, opens in new window)
14. Searching with Advice: Robot Fence-Jumping
With Evangelos Kranakis and Alexandra Steau
Journal of Information Processing (2017)
Journal version (external link, opens in new window)
13. Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
With Per Austrin and Siavosh Benabbas
ACM Transactions on Algorithms (TALG), (2016)
Journal version (external link, opens in new window)
12. Evacuating Two Robots from Multiple Unknown Exits in a Circle
With Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis and Fraser MacQuarrie
Theoretical Computer Science (2016)
Journal version (external link, opens in new window)
11. Stable Marriage with General Preferences
With Linda Farczadi and Jochen Könemann
Theory of Computing Systems (2016)
Journal version (external link, opens in new window)
10. On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
With Joseph Cheriyan, Zhihan Gao and Sahil Singla
Mathematical Programming Series A (2016)
Journal version (external link, opens in new window)
9. The Beachcombers' Problem: Walking and Searching with Mobile Robots
With Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis and Fraser MacQuarrie
Theoretical Computer Science (2015)
Journal version (external link, opens in new window)
8. Complexity of Barrier Coverage with Relocatable Sensors in the Plane
With S. Dobrev, S. Durocher, M. Eftekhari, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, S. Shende, J. Urrutia
Theoretical Computer Science (2015)
Journal version (external link, opens in new window)
7. Excuse Me! or The Courteous Theatregoers' Problem
With Evangelos Kranakis and Danny Krizanc
Theoretical Computer Science (2015)
Journal version (external link, opens in new window)
6. Black-Box Reductions for Cost-Sharing Mechanism Design
With Chaitanya Swamy
Games and Economic Behavior (2013)
Journal version (external link, opens in new window)
5. Social Exchange Networks With Distant Bargaining
With George Karakostas, Jochen Könemann and Zuzanna Stamirowska
Theoretical Computer Science (2013)
Journal version (external link, opens in new window)
4. SDP Gaps from Pairwise Independence
With Siavosh Benabbas, Avner Magen and Madhur Tulsiani
Theory of Computing (2012)
Journal version (external link, opens in new window)
3. Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lovasz-Schrijver Hierarchy
With Avner Magen, Toniann Pitassi and Iannis Tourlakis
SIAM Journal on Computing (2010)
Journal version (external link, opens in new window)
2. Random Maximal Independent Sets and the Unfriendly Theater Seating Arrangement Problem
With Evangelos Kranakis and Danny Krizanc
Discrete Mathematics (2009)
Journal version (external link, opens in new window)
1. Distributed Dynamic Storage in Wireless Networks
With Evangelos Kranakis, Ricardo Marcelin-Jimenez, Sergio Rajsbaum, Jorge Urrutia
International Journal of Distributed Sensor Networks (2005)
Journal version (external link, opens in new window)
53. Multi-Agent Disk Inspection
With James Conley
32nd International Colloquium On Structural Information and Communications Complexity (SIROCCO 2025)
Conference version (external link, opens in new window) - Also on arXiv:2411.15391 (external link, opens in new window) (preprint, 2024)
52. Multi-Agent Search-Type Problems on Polygons
With Caleb Jones and Jesse Lucier
50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2025)
Conference version (external link, opens in new window) - Also on arXiv:2406.19495 (external link, opens in new window) (preprint, 2024)
51. Weighted Group Search on the Disk & Improved Lower Bounds for Priority Evacuation
With Xin Wang
35th International Workshop on Combinatorial Algorithms (IWOCA 2024)
Conference version (external link, opens in new window) - Also on arXiv:2406.19490 (external link, opens in new window) (preprint - 2024)
50. The Fagnano Triangle Patrolling Problem
With Somnath Kundu and Paweł Prałat
25th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2023)
Track D: Dynamic, Mobile and Nature-Inspired Computing Mobile Agents
Conference version (external link, opens in new window) - Also on arXiv:2307.13153 (external link, opens in new window) (preprint, 2023)
49. Overcoming Probabilistic Faults in Disoriented Linear Search
With Nikos Giachoudis and Evangelos Kranakis
30th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2023)
Conference version (external link, opens in new window) - Also on arXiv:2303.15608 (external link, opens in new window) (preprint, 2023)
48. Improved Collision-Free Multi-Axis Tool-Path for Additive Manufacturing
With Rahnuma Islam Nishat, Yeganeh Bahoo, Robert Hedrick, R. Jill Urbanic.
20th Annual International Computer-Aided Design Conference (CAD 2023)
(PDF file) Conference version (external link, opens in new window)
47. Evacuation from a Disk for Robots with Asymmetric Communication
With Nikos Giachoudis and Evangelos Kranakis
33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Conference version (external link, opens in new window)
46. Triangle Evacuation of 2 Agents in the Wireless Model
With Woojin Jang
18th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2022)
Conference version (external link, opens in new window) - Also on arXiv:2209.08544 (external link, opens in new window) (preprint, 2022)
45. Collision-Free Multi-Axis Tool-Path for Additive Manufacturing
With Rahnuma Islam Nishat, Yeganeh Bahoo, Robert Hedrick, R. Jill Urbanic
19th Annual International Computer-Aided Design Conference (CAD 2022)
(PDF file) Conference version (external link, opens in new window)
44. Evacuating from ell-p Unit Disks in the Wireless Model
With Somnath Kundu, Sean Leizerovich, and Jesse Lucier
17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2021)
Conference version (external link, opens in new window) - Also on arXiv:2108.02367 (external link, opens in new window) (preprint 2021)
43. Makespan Trade-offs for Visiting Triangle Edges
With Somnath Kundu and Paweł Prałat
32nd International Workshop on Combinatorial Algorithms (IWOCA 2021)
Conference version (external link, opens in new window) - Also on arXiv:2105.01191 (external link, opens in new window) (preprint, 2021)
42. The Bike Sharing Problem
With Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny and Dennis Pankratov
15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021)
Conference version (external link, opens in new window) - Also on arXiv:2006.13241 (external link, opens in new window) (preprint, 2020)
41. Weighted Group Search on a Line
With Jesse Lucier
16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2020)
Conference version (external link, opens in new window)
40. Probabilistically Faulty Searching on a Half-Line
With Anthony Bonato, Calum MacCury and Paweł Prałat
14th Latin American Theoretical Informatics Symposium (LATIN 2020)
Conference version (external link, opens in new window) - Also on arXiv:2002.07797 (external link, opens in new window) (preprint, 2020)
39. Lower Bounds for Shoreline Searching with 2 or More Robots
With Sumi Acharjee, Somnath Kundu and Akshaya Srinivasan
23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Conference version (external link, opens in new window) - Also on arXiv:2001.04311 (external link, opens in new window) (preprint, 2020)
38. Optimal Circle Search Despite the Presence of Faulty Robots
With Evangelos Kranakis, Nikos Leonardos, Aris Pagourtzis and Ioannis Papaioannou
15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2019)
Conference version (external link, opens in new window)
37. Time-Energy Tradeoffs for Evacuation by Two Robots in the Wireless Model
With Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny and Sunil Shende
26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019)
Conference version (external link, opens in new window) - Also on arXiv:1905.06783 (external link, opens in new window) (preprint, 2019)
36. Energy Consumption of Group Search on a Line
With Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny and Sunil Shende
46th International Colloquium on Automata, Languages and Programming (ICALP 2019)
Conference version (external link, opens in new window) - Also on arXiv:1904.09714 (external link, opens in new window) (preprint, 2019)
35. Bargaining in Networks with Socially-Aware Agents
With Somnath Kundu
9th EAI International Conference on Game Theory for Networks (GameNets 2019)
Conference version (external link, opens in new window)
34. Average Case - Worst Case Tradeoffs for Evacuating 2 Robots from the Disk in the Face-to-Face Model
With Huda Chuangpishit and Preeti Sharma
14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2018)
Conference version (external link, opens in new window) - Also on arXiv:1807.08640 (external link, opens in new window) (preprint, 2018)
33. Symmetric Rendezvous With Advice: How to Rendezvous in a Disk
With Jay Griffiths and Yuval Yakubov
25th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2018)
Conference version (external link, opens in new window) - Also on arXiv:1805.03351 (external link, opens in new window) (preprint, 2018)
32. Priority Evacuation from a Disk Using Mobile Robots
With Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny and Sunil Shende
25th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2018)
Conference version (external link, opens in new window) - Also on arXiv:1805.03568 (external link, opens in new window) (preprint, 2018)
31. God Save the Queen
With Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny and Sunil Shende
9th International Conference on Fun With Algorithms (FUN 2018)
Conference version (external link, opens in new window) - Also on arXiv:1804.06011 (external link, opens in new window) (preprint, 2018)
30. Patrolling a Path-Connected Set of Points with Non-Uniform Visitation-Frequency Requirements
With Huda Chuangpishit, Jurek Czyzowicz, Leszek Gasieniec, Tomasz Jurdzinski and Evangelos Kranakis
44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018)
Conference version (external link, opens in new window) - Also on arXiv:1710.00466 (external link, opens in new window) (preprint, 2017)
29. Querying with Uncertainty
With Huda Chuangpishit and Evangelos Kranakis
13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS 2017)
Conference version (external link, opens in new window)
28. Evacuation from a Disc in the Presence of a Faulty Robot
With Jurek Czyzowicz, Maxime Godon, Evangelos Kranakis, Danny Krizanc, Wojciech Rytter and Michal Wlodarczyk
24th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2017)
Conference version (external link, opens in new window)
27. Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models
With George Karakostas and Evangelos Kranakis
6th International Conference on Operations Research and Enterprise Systems (ICORES 2017)
Conference version (external link, opens in new window) - Also on arXiv:1611.10208 (external link, opens in new window) (preprint, 2016)
26. Search on a Line by Byzantine Robots
With Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jurek Opatrny and Sunil Shende
27th International Symposium on Algorithms and Computation (ISAAC 2016)
Conference version (external link, opens in new window) - Also on arXiv:1611.08209 (external link, opens in new window) (preprint, 2016)
25. Search-and-Fetch with One Robot on a Disk
With George Karakostas and Evangelos Kranakis
12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2016)
Conference version (external link, opens in new window)
24. Searching with Advice: Robot Fence-Jumping
With Evangelos Kranakis, and Alexandra Steau
28th Canadian Conference on Computational Geometry (CCCG 2016)
(PDF file) Conference version (external link, opens in new window) - Also on arXiv:1606.08023 (external link, opens in new window) (preprint, 2016)
23. Know When to Persist: Deriving Value from a Stream Buffer
With George Karakostas, Evangelos Kranakis, and Danny Krizanc
11th International Conference on Algorithmic Aspects of Information and Management (AAIM 2016)
Conference version (external link, opens in new window) - Also on arXiv:1604.03009 (external link, opens in new window) (preprint, 2016)
22. Distributed Patrolling with Two-Speed Robots (and an Application to Transportation)
With Jurek Czyzowicz, Evangelos Kranakis, Fraser MacQuarrie, and Dominik Pajak
5th International Conference on Operations Research and Enterprise Systems (ICORES 2016)
Conference version (external link, opens in new window)
21. Evacuating Two Robots from Multiple Unknown Exits in a Circle
With Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis and Fraser MacQuarrie
17th International Conference on Distributed Computing and Networking - Distributed Computing Track (ICDCN 2016)
Conference version (external link, opens in new window)
20. Evacuating Robots from a Disk Using Face-to-Face Communication
With Jurek Czyzowicz, Evangelos Kranakis, Lata Narayanan, Jarda Opatrny and Birgit Vogtenhuber
8th International Conference on Algorithms and Complexity (CIAC 2015)
Conference version (external link, opens in new window) - Also on arXiv:1501.04985 (external link, opens in new window) (preprint, 2015)
19. Lift & Project Systems Performing on the Partial Vertex Cover Polytope
With Edward Lee
34th Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Conference version (external link, opens in new window) - Also on arXiv:1409.6365 (external link, opens in new window) (preprint, 2014)
18. The Multi-source Beachcombers' Problem
With Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis and Fraser MacQuarrie
10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2014)
Conference version (external link, opens in new window)
17. Stable Marriage with General Preferences
With Linda Farczadi and Jochen Könemann
7th International Symposium on Algorithmic Game Theory (SAGT 2014)
Conference version (external link, opens in new window) - Also on arXiv:1407.1853 (external link, opens in new window) (preprint, 2014)
16. The Beachcombers' Problem: Walking and Searching with Mobile Robots
With Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis and Fraser MacQuarrie
21st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014)
Conference version (external link, opens in new window) - Also on arXiv:1304.7693 (external link, opens in new window) (preprint, 2013)
15. Excuse Me! or The Courteous Theatregoers' Problem
With Evangelos Kranakis, Danny Krizanc
7th International Conference on Fun With Algorithms (FUN 2014)
Conference version (external link, opens in new window) - Also on arXiv:1403.1988 (external link, opens in new window) (preprint, 2014)
14. Network Bargaining with General Capacities
With Linda Farczadi and Jochen Könemann
21st European Symposium on Algorithms (ESA 2013)
Conference version (external link, opens in new window) - Also on arXiv:1306.4302 (external link, opens in new window) (preprint, 2013)
13. On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
With Joseph Cheriyan, Zhihan Gao and Sahil Singla
40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
Conference version (external link, opens in new window) - Also on arXiv:1405.0945 (external link, opens in new window) (preprint, 2014)
12. Lift-and-Project Methods for Set Cover and Knapsack
With Eden Chlamtac and Zac Friggstad
17th Workshop on Algorithms and Data Structures (WADS 2013)
Conference version (external link, opens in new window) - Also on arXiv:1204.5489 (external link, opens in new window) (preprint, 2012)
11. Social Exchange Networks With Distant Bargaining
With George Karakostas, Jochen Könemann and Zuzanna Stamirowska
19th Annual International Computing and Combinatorics Conference (COCOON 2013)
Conference version (external link, opens in new window)
10. Complexity of Barrier Coverage with Relocatable Sensors in the Plane
With S. Dobrev, S. Durocher, M. Eftekhari, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, S. Shende, J. Urrutia
8th International Conference on Algorithms and Complexity (CIAC 2013)
Conference version (external link, opens in new window)
9. Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
With Per Austrin and Siavosh Benabbas
24th Symposium on Discrete Algorithms (SODA 2013)
Conference version (external link) - Also on arXiv:1205.0458 (external link, opens in new window) (preprint, 2012)
8. Black-Box Reductions for Cost-Sharing Mechanism Design
With Chaitanya Swamy
23rd Symposium on Discrete Algorithms (SODA 2012)
Conference version (external link)
7. Tight Integrality gap for Sherali-Adams SDPs for Vertex Cover
With Siavosh Benabbas, Siuon Chan and Avner Magen
31st Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Conference version (external link) - Also in Electronic Colloquium on Computational Complexity (ECCC), TR10-169 (external link, opens in new window) (preprint, 2011)
6. On the Tightening of the Standard SDP for Vertex Cover with l1 Inequalities
With Avner Magen and Iannis Tourlakis
29th Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Coonference version (external link)
5. Optimal Sherali-Adams Gaps from Pairwise Independence
With Avner Magen and Madhur Tulsiani
12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009)
Conference version (external link) - Also in Electronic Colloquium on Computational Complexity (ECCC), TR096-061 (external link) (preprint, 2009)
4. Complexity and Algorithms for Well Structured k-SAT Instances
With Periklis Papakonstantinou
11th International Conference on Theory and Applications of Satisfiability Testing (SAT 2008)
Conference version (external link)
3. Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities
With Avner Magen and Iannis Tourlakis
13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008)
Conference version (external link)
2. Computability of Models for Sequence Assembly
With Paul Medvedev, Gene Myers and Michael Brudno
7th Workshop on Algorithms in Bioinformatics (7th Workshop on Algorithms in Bioinformatics (WABI 2007)
Conference version (external link)
1. Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lovasz-Schrijver Hierarchy
With Avner Magen, Toniann Pitassi and Iannis Tourlakis
48th IEEE Symposium on Foundations of Computer Science (FOCS 2007)
Conference version (external link, opens in new window) - Also in Electronic Colloquium on Computational Complexity (ECCC), TR06-152 (external link, opens in new window) (preprint, 2006)
2. Group Search and Evacuation
With Jurek Czyzowicz and Evangelos Kranakis
Chapter in book (external link, opens in new window) “Distributed Computing by Mobile Entities” (2019)
1. Patrolling with Mobile Agents
With Jurek Czyzowicz and Evangelos Kranakis
Chapter in book (external link, opens in new window) “Distributed Computing by Mobile Entities” (2019)
5. Optimal Average Disk-Inspection via Fermat's Principle
arXiv:2509.06334 (external link, opens in new window) (preprint, 2025)
4. Disk and Partial Disk Inspection: Worst- to Average-Case and Pareto Upper Bounds
With James Conley
arXiv:2411.15391 (external link, opens in new window) (preprint, 2025)
3. Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents
With Caleb Jones and Matthew Madej
arXiv:2508.10793 (external link, opens in new window) (preprint, 2025)
2. Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances
With Isaac Fung, Jochen Könemann and Malcolm Sharpe
arXiv:1202.5049 (external link, opens in new window) (preprint, 2011)
1. Expansion Fools the Sherali-Adams System: Compromising Local and Global Arguments
With Avner Magen.
(PDF file) Technical Report CSRG-587 (external link, opens in new window) ,University of Toronto (preprint, 2008)
2. Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations
PhD thesis (external link, opens in new window) , Department of Computer Science, University of Toronto
Supervisors: Avner Magen (external link, opens in new window) and Toniann Pitassi (external link, opens in new window) (2010)
1. Unfairness in Online Scheduling
MSc thesis, Department of Mathematics, University of Athens
Supervisor: Elias Koutsoupias (external link, opens in new window) (2004)