Aris Filos-Ratsikas

Lecturer || Laboratory for Foundations of Computer Science || School of Informatics, University of Edinburgh

• About me
• Publications
• Experience
• Teaching

Contact Information

School of Informatics, University of Edinburgh

Office: 507, Informatics Forum

10 Crichton St, Newington, Edinburgh EH8 9AB

E-mail: Aris.Filos-Ratsikased.ac.uk

About Me

I am an Lecturer (Assistant Professor) at the University of Edinburgh. My research lies in the intersection of theoretical computer science and artificial intelligence, with an emphasis on algorithms and computational complexity. In particular, I am interested in problems related to social choice theory, fair division, competitive markets, game theory and mechanism design.

I obtained my PhD degree from the Computer Science Department of Aarhus University, Denmark in 2015, under the supervision of Peter Bro Miltersen. In the past, I was a Lecturer at the University of Liverpool, a postdoctoral researcher at École polytechnique fédérale de Lausanne, and a postdoctoral research assistant at the University of Oxford. My MSc advisor was Ioannis Caragiannis.

When I am not working, I like to play the guitar and try to compose music. The results of my attempts can be summarized in four self-recorded and self-produced albums with my amateur band.

News

• 23/09/2023. Our paper Explainable and Efficient Randomized Voting Rules, with Soroush Ebadian, Mohamad Latifian, and Nisarg Shah, was accepted for publication at NeurIPS '23.
• 08/09/2023. The SAGT 2023 conference which I was co-organising just took place in Royal Holloway University of London. I hope everyone had a good time, I certainly did!
• 03/01/2022. 3 papers accepted to AAMAS '23 - check the "Publications" tab for details. Happy new year and see you in London!
• 20/12/2022. Our paper FIXP-membership via Convex Optimization: Games, Cakes, and Markets, with Kristoffer Arnsfelt Hansen, Kasper Høgh and Alexandros Hollender was accepted to the FOCS '21 special issue of the SIAM Journal on Computing.
• 14/09/2022. Our paper Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond, with Yorgos Amanatidis, Yorgos Birmpas and Alexandros Voudouris was accepted for publication at NeurIPS 2022.
• 01/09/2022. Moved to the University of Edinburgh, starting a new post as a Lecturer.
• 01/03/2022. Our paper A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching, with Yorgos Amanatidis, Yorgos Birmpas and Alexandros Voudouris was accepted for publication at the Journal of Artificial Intelligence Research.
• 17/01/2022. Our paper Putting Ridesharing to the Test: Efficient and Scalable Solutions and the Power of Dynamic Vehicle Relocation, with Panayiotis Danassis, Marija Sakota and Boi Faltings was accepted for publication at Artificial Intelligence Review.
• 01/12/2021. Our paper Heterogeneous Facility Location with Limited Resources, with Argyrios Deligkas and Alexandros Voudouris was accepted for publication at AAAI '22.
• 23/08/2021. Our paper FIXP-membership via Convex Optimization: Games, Cakes, and Markets, with Kristoffer Arnsfelt Hansen, Kasper Høgh and Alexandros Hollender was accepted for publication at FOCS '21. In this paper we develop a new technique for proving FIXP-membership results via convex optimization, and we manage to simplify and generalize several FIXP-membership results in games, markets and fair division. Interestingly, we also for the first time obtain the FIXP-completeness of exact envy-free cake cutting.
• 12/08/2021. It's been almost a year since I posted any news here. Too much has happened since then, so it's hard to list them all. Check the updated list of conference papers to see some of our newest work (including two interesting surveys that you should cite in all of your related papers). I am also improving my conference-to-journal conversion rate, so check the journal publications as well, to see where these conference papers ended up. Finally, make sure to check our recent workshop on fairness organized as part of EC '21.
• 02/10/2020. Our paper Stable Fractional Matchings, with Iannis Caragiannis, Panagiotis Kanellopoulos and Rohit Vaish was accepted for publication at Artificial Intellgence.
• 30/09/2020. It's been a while, but there are some great news to share. Our paper A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting, with Alexandros Hollender, Katerina Sotiraki and Manolis Zampetakis was accepted for publication at SODA '21.
• 05/05/2020. Our paper Consensus-Halving: Does it Ever Get Easier?, with Alexandros Hollender, Katerina Sotiraki and Manolis Zampetakis was accepted for publication at EC '20.
• 21/04/2020. Good news, three papers accepted to IJCAI 2020!
• 02/04/2020. It's been a while since I've posted updates here, so here's a list of papers to check out. Together with Alexandros Hollender, Katerina Sotiraki and Manolis Zampetakis, we have recently written two papers that you can find here and here. If you are interested in Consensus-Halving, Necklace Splitting and the complexity of topological theorems, the classes PPA or PPA-k or generally problems in TFNP, you should check them out! If you don't care about any of these things, you might be interested in fairness and EFX, and then you should check this paper, with Yorgos Amanatidis, Giorgos Birmpas, Alexandros Hollender and Alexandros Voudouris. Finally, if you are interested in ride-sharing and optimisation, how about checking out this paper, with Panayiotis Danassis, Marija Sakota and Boi Faltings?
• 11/11/2019. Our paper Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries (with Yorgos Amanatidis, Giorgos Birmpas and Alex Voudouris) was accepted for publication at AAAI 2020, which will take place in New York in February. If you can't wait until then, the poster will be part of the poster session at WINE 2019 (still in New York, December 10-12), so feel free to come by.
• 11/09/2019. Our paper The Pareto Frontier of Inefficiency in Mechanism Design (with Yiannis Giannakopoulos and Philip Lazos) was accepted for publication at WINE 2019.
• 30/07/2019. Moved to Liverpool, to start a new position as an Assistant Professor (Lecturer in the UK academic rank system).
• 18/07/2019. Check out our new paper (with Georgios Amanatidis, Georgios Birmpas and Alexandros A. Voudouris) on the distortion of mechanisms, when we enhance them with access to a limited number of cardinal queries. Spoiler alert: Only a few queries are enough to obtain really good improvements!
• 07/07/2019. Capping off a very busy month in terms of travelling, I will be attending ICALP at Patras, Greece, July 8-12. If you are around, please consider coming by our Workshop on Theoretical Aspects of Fairness which is held on the first day of the conference.
• 01/07/2019. Attending the Twenty Years of the Price of Anarchy workshop to be held at Chania, Greece, July 2-5, where I will be giving a talk on our recent work (with Yiannis Giannakopoulos and Philip Lazos), on the <>trade-offs between the Price of Anarchy and the Price of Stability in Mechanism Design.
• 01/07/2019. Our paper The Distortion of Distributed Voting (with Evi Micha and Alexandros Voudouris) was accepted for publication at SAGT 2019.
• 24/06/2019. Attending the FCRC Conference to present our paper The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches (with Paul Goldberg) at STOC 2019. Also, Rohit Vaish will be presenting our paper Stable Fractional Matchings (with Iannis Caragiannis, Panagiotis Kanellopoulos and Rohit Vaish) at EC 2019.
• 10/05/2019. Our paper Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior (with Panayiotis Danassis and Boi Faltings) was accepted for publication at IJCAI '19. By the way, if you are attending AAMAS next week, feel free to pass by the ALA Workshop, where Panayiotis will be giving a presentation of the paper.
• 28/04/2019. Finally broke the spell! Our paper Stable Fractional Matchings (with Iannis Caragiannis, Panagiotis Kanellopoulos and Rohit Vaish) was accepted for publication at EC '19.
• 07/04/2019. (My good friend) Alexios Balatsoukas-Stimming and I wrote a paper on the Complexity of the Blind Detection Problem of Binary Linear Codes, which was accepted for publication at ISIT '19. A bit different from what I usually do, but certainly a result that was missing from the literature. Plus, I don't think many people can claim to have written both papers and albums with their closest friends.
• 12/02/2019. Our paper The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches (with Paul Goldberg) was accepted for publication at STOC 2019.
• 26/01/2019. Attending AAAI' 19, in Honolulu, to present our paper (with Simina Branzei), Walrasian Dynamics in Multi-unit Markets.
• 11/12/2018. I will be attending WINE '18, at the University of Oxford. If you are interested in knowing more about our recent AAAI publication (with Simina Branzei), or our recent paper on combining mechanism design with and without money (with Iannis Caragiannis, Swaprava Nath and Alexandros Voudouris), come to the poster session!
• 02/11/2018. Our paper Walrasian Dynamics in Multi-unit Markets (with Simina Branzei) was accepted for publication at AAAI 2019.
• 12/09/2018. On October 6, I will be giving a lightning talk on "Natural" PPA-Complete problems at the Total Functions in Computation, Communication and Cryptography Workshop at FOCS '18, organized by Aviad Rubinstein and Manolis Zampetakis.
• 10/09/2018. We have uploaded our new paper (with Yiannis Giannakopoulos and Philip Lazos), on the trade-offs between the Price of Anarchy and the Price of Stability in Mechanism Design, on ArXiv, here. Make sure to check it out!
• 25/06/2018. Attending STOC '18, where I will be presenting my joint work with Paul Goldberg, Consensus Halving is PPA-complete.
• 14/06/2018. Our paper Hardness Results of Consensus-Halving (with Søren Frederiksen, Paul Goldberg and Jie Zhang) was accepted for publication at MFCS 2018.
• 11/06/2018. Paul Tylkin and I have prepared a tutorial on Auctions and Markets, which will be given by Paul at the 20th European Agents and Systems Summer School (EASSS '18). The summer school will take place on June 18-22, in Maastricht, The Netherlands. Check out the schedule here.
• 31/05/2018. In joint work with Paul Goldberg, we have extended our STOC 2018 result on Consensus-Halving to inverse-polynomial precision parameter, which implies that Necklace Splitting and Ham-Sandwich are PPA-Complete. We have uploaded the paper on ArXiv here.
• 24/04/2018. Attending the Web Conference (WWW 2018) at Lyon, were our paper Reinforcement Mechanism Design for e-Commerce (with Qingpeng Cai, Pingzhong Tang and Yiwei Zhang) will be presented.
• 01/04/2018. Joined the Artificial Intelligence Lab of EPFL as a post-doc.