Research (Google Scholar, dblp)



Journal publications


 J10  Rapid mixing of the switch Markov chain for 2-class joint degree matrices
with P. Kleer
SIAM Journal on Discrete Mathematics, in press
[journal version] Partially supersedes the SODA 2019 paper below.
 J9  Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online
with P. Kleer and G. Schäfer
Mathematics of Operations Research, in press
[arxiv version] Supersedes the EC 2019 paper below.
 J8  Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results
with P. Fulla, E. Markakis, and K. Sornat
Theoretical Computer Science, Vol. 871, 62-78, June 2021
[arXiv version] Supersedes the MFCS 2016 paper below.
 J7  Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries
with G. Birmpas, A. Filos-Ratsikas, and A. Voudouris
Artificial Intelligence, Vol. 296, 103488, July 2021
[arxiv version] Supersedes the AAAI 2020 paper below.
 J6  Maximum Nash welfare and other stories about EFX
with G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris
Theoretical Computer Science, Vol. 863, 69-85, April 2021
[arXiv version] Supersedes the IJCAI 2020 paper below.
 J5  A Simple Deterministic Algorithm for Symmetric Submodular Maximization Subject to a Knapsack Constraint
with G. Birmpas and E. Markakis
Information Processing Letters, Vol. 163, 106010, November 2020
[journal version]
 J4  Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination
with E. Markakis and A. Ntokos
Theoretical Computer Science, Vol. 841, 94-109, November 2020
[arXiv version] Supersedes the AAAI 2020 paper below.
 J3  Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences
with P. Kleer
Random Structures & Algorithms, Vol. 57, 637-657, October 2020
[journal version] Partially supersedes the SODA 2019 paper below.
 J2  Connected Realizations of Joint-Degree Matrices
with B. Green and M. Mihail
Discrete Applied Mathematics, Vol. 250, 65-74, December 2018
[journal version] Partially supersedes the DIMACS Workshop poster below.
 J1  Approximation Algorithms for Computing Maximin Share Allocations
with E. Markakis, A. Nikzad, and A. Saberi
ACM Transactions on Algorithms, Vol. 13(4), 52:1-52:28, December 2017
[arXiv version] Supersedes the ICALP 2015 paper below.

Conference publications


C19 Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
with G. Birmpas, F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser
WINE 2021, 17th Conference on Web and Internet Economics, forthcoming
[arXiv version]
C18 Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
with F. Fusco, P. Lazos, S. Leonardi, A. Marchetti-Spaccamela, and R. Reiffenhäuser
ICML 2021, 38th International Conference on Machine Learning
[arXiv version]
C17 A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
with G. Birmpas, A. Filos-Ratsikas, and A. Voudouris
AAAI 2021, 35th AAAI Conference on Artificial Intelligence
[arXiv version]
C16 Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
with F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser
NeurIPS 2020, 34th Conference on Neural Information Processing Systems
[arXiv version] Appeared as a poster in HALG 2021.
C15 Maximum Nash Welfare and Other Stories About EFX
with G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris
IJCAI 2020, 29th International Joint Conference on Artificial Intelligence
[arXiv version] Superseded by the TCS paper above.
C14 Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries
with G. Birmpas, A. Filos-Ratsikas, and A. Voudouris
AAAI 2020, 34th AAAI Conference on Artificial Intelligence
[arxiv version] Superseded by the ARTINT paper above.
C13 Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination
with E. Markakis and A. Ntokos
AAAI 2020, 34th AAAI Conference on Artificial Intelligence
[arxiv version] Superseded by the TCS paper above.
C12 Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online
with P. Kleer and G. Schäfer
EC 2019, 20th ACM conference on Economics and Computation
[arxiv version] Superseded by the MOR paper above.
C11 Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices
with P. Kleer
SODA 2019, 30th Annual ACM-SIAM Symposium on Discrete Algorithms
[arxiv version] Superseded by the RSA paper and the SIDMA paper above.
C10 An Improved Envy-Free Cake Cutting Protocol for Four Agents
with G. Christodoulou, J. Fearnley, E. Markakis, C.-A. Psomas, and E. Vakaliou
SAGT 2018, 11th International Symposium on Algorithmic Game Theory
[arXiv version] Appeared as a poster in WINE 2017.
 C9  Comparing Approximate Relaxations of Envy-Freeness
with G. Birmpas and E. Markakis
IJCAI 2018, 27th International Joint Conference on Artificial Intelligence
[arXiv version] Also presented at the COMSOC 2018 workshop.
 C8  On Budget-Feasible Mechanism Design for Symmetric Submodular Objectives
with G. Birmpas and E. Markakis
WINE 2017, 13th Conference on Web and Internet Economics
[arXiv version]
 C7  Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness
with G. Birmpas, G. Christodoulou, and E. Markakis
EC 2017, 18th ACM conference on Economics and Computation
[arXiv version]
 C6  Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design
with G. Birmpas and E. Markakis
WINE 2016, 12th Conference on Web and Internet Economics
[arXiv version]
 C5  Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results
with E. Markakis and K. Sornat
MFCS 2016 , 41st International Symposium on Mathematical Foundations of Computer Science
[arXiv version] Also presented at the AGT@IJCAI 2016 workshop. Superseded by the TCS paper above.
 C4  On Truthful Mechanisms for Maximin Share Allocations
with G. Birmpas and E. Markakis
IJCAI 2016, 25th International Joint Conference on Artificial Intelligence
[arXiv version] Also presented at the COMSOC 2016 workshop, and appeared as a poster in WINE 2016.
 C3  Approximation Algorithms for Computing Maximin Share Allocations
with E. Markakis, A. Nikzad, and A. Saberi
ICALP 2015 (A) , 42nd International Colloquium on Automata, Languages, and Programming
[arXiv version] Also appeared as a poster in WINE 2015. Superseded by the TALG paper above.
 C2  Multiple Referenda and Multiwinner Elections Using Hamming Distances: Complexity and Manipulability
with N. Barrot, J. Lang, E. Markakis, and B. Ries
AAMAS 2015, 14th International Conference on Autonomous Agents and Multiagent Systems
[AAMAS version]
 C1  Provably-Secure Schemes for Basic Query Support in Outsourced Databases
with A. Boldyreva and A. O'Neill
DBSec 2007, 21st IFIP WG11.3 Working Conference on Data and Application Security
[DBSec version]

Theses


 T2  Algorithmic and Mechanism Design Aspects of Problems with Limited—or no—Payments
PhD Thesis, Athens University of Economics and Business, August 2017
Advisor: Asst. Prof. Vangelis Markakis
[thesis]
 T1  Probabilisticaly Checkable Proofs and Hardness of Approximation (in Greek)
Diploma Thesis, National Technical University of Athens, July 2004
Advisor: Prof. Stathis Zachos

Other


O3 Flexible Models for Complex Networks
with M. Mihail and S. Young
WebSci 2009, 1st Web Science Conference: Society On-Line
[WebSci version] Also appeared as a poster at the ARC2 GaTech workshop (October 2008).
O2 Graphic Realizations of Joint-Degree Matrices
with B. Green and M. Mihail
DIMACS Workshop on New Directions in Algorithms, Combinatorics and Optimization, 2008, Poster
[arXiv version] Partially superseded by the DAM paper above.
O1 Side-Channel Attacks
with S. Zachos and V. Zikas
Workshop on Internet-Education-Science, Pristina, Serbia, 2004