Publications

Sort by: Date | Author | Title

Caragiannis, I. & Jiang, Z. (2023). Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming. In B. Saha & R. A. Servedio (Eds.), STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 710-722). Association for Computing Machinery, Inc. https://doi.org/10.1145/3564246.3585236

Barman, S., Khan, A., Shyam, S. & Sreenivas, K. V. N. (2023). Guaranteeing Envy-Freeness under Generalized Assignment Constraints. EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation, 242-269. https://doi.org/10.1145/3580507.3597698

Amireddy, P., Srinivasan, S. & Sudan, M. (2023). Low-Degree Testing over Grids. In N. Megow & A. Smith (Eds.), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, APPROX/RANDOM 2023 Article 41 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.41

Srinivasan, S. & Tripathi, U. (2023). Optimal Explicit Small-Depth Formulas for the Coin Problem. In B. Saha & R. A. Servedio (Eds.), STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 881-894). Association for Computing Machinery. https://doi.org/10.1145/3564246.3585238

Airiau, S., Aziz, H., Caragiannis, I., Kruger, J., Lang, J. & Peters, D. (2023). Portioning using ordinal preferences: Fairness and efficiency. Artificial Intelligence, 314, Article 103809. https://doi.org/10.1016/j.artint.2022.103809

Chaugule, P., Kumar, M., Limaye, N., Mohapatra, C. K., She, A. & Srinivasan, S. (2023). Schur Polynomials Do Not Have Small Formulas If the Determinant does not. Computational Complexity, 32(1), Article 3. https://doi.org/10.1007/s00037-023-00236-x

Bouras, C., Caragiannis, I., Gkamas, A., Protopapas, N., Sardelis, T. & Sgarbas, K. (2023). State of the Art Analysis of Resource Allocation Techniques in 5G MIMO Networks. In 37th International Conference on Information Networking, ICOIN 2023 (pp. 632-637). IEEE. https://doi.org/10.1109/ICOIN56518.2023.10049018

Fournier, H., Limaye, N., Malod, G., Srinivasan, S. & Tavenas, S. (2023). Towards Optimal Depth-Reductions for Algebraic Formulas. In A. Ta-Shma (Ed.), 38th Computational Complexity Conference, CCC 2023 Article 28 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2023.28

Brânzei, S., Filos-Ratsikas, A., Miltersen, P. B. & Zeng, Y. (2023). Walrasian pricing in multi-unit auctions. Artificial Intelligence, 322, Article 103961. https://doi.org/10.1016/j.artint.2023.103961

Caragiannis, I., Micha, E. & Shah, N. (2022). A Little Charity Guarantees Fair Connected Graph Partitioning. In AAAI-22 Technical Tracks 5 (Vol. 11, pp. 4908-4916). AAAI Press. https://doi.org/10.1609/aaai.v36i5.20420

Bilo, V., Caragiannis, I., Flammini, M., Igarashi, A., Monaco, G., Peters, D., Vinci, C. & Zwicker, W. (2022). Almost envy-free allocations with connected bundles. Games and Economic Behavior, 131, 197-221. https://doi.org/10.1016/j.geb.2021.11.006

Caragiannis, I., Gkatzelis, V., Psomas, A. & Schoepflin, D. (2022). Beyond Cake Cutting: Allocating Homogeneous Divisible Goods. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022) (pp. 208-216). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Caragiannis, I., Kanellopoulos, P. & Voudouris, A. A. (2022). Bounding the Inefficiency of Compromise in Opinion Formation. Algorithmica, 84(1), 234-271. https://doi.org/10.1007/s00453-021-00892-x

Caragiannis, I. & Ioannidis, S. D. (2022). Computing Envy-Freeable Allocations with Limited Subsidies. In M. Feldman, H. Fu & I. Talgam-Cohen (Eds.), Web and Internet Economics : 17th International Conference, WINE 2022 (pp. 522-539). Springer. https://doi.org/10.1007/978-3-030-94676-0_29

Caragiannis, I., Kaklamanis, C., Karanikolas, N. & Krimpas, G. (2022). Evaluating approval-based multiwinner voting in terms of robustness to noise. Autonomous Agents and Multi-Agent Systems, 36(1), Article 1. https://doi.org/10.1007/s10458-021-09530-w

Aziz, H., Caragiannis, I., Igarashi, A. & Walsh, T. (2022). Fair allocation of indivisible goods and chores. Autonomous Agents and Multi-Agent Systems, 36(1), Article 3. https://doi.org/10.1007/s10458-021-09532-8

Filos-Ratsikas, A., Hansen, K. A., Hogh, K. & Hollender, A. (2022). FIXP-membership via Convex Optimization: Games, Cakes, and Markets. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (pp. 827-838). IEEE. https://doi.org/10.1109/FOCS52979.2021.00085

Caragiannis, I., Christodoulou, G. & Protopapas, N. (2022). Impartial Selection with Additive Approximation Guarantees. Theory of Computing Systems, 66(3), 721-742. https://doi.org/10.1007/s00224-022-10081-0

Berthelsen, M. L. T. & Hansen, K. A. (2022). On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. Theory of Computing Systems, 66(3), 519-545. https://doi.org/10.1007/s00224-022-10080-1

Limaye, N., Srinivasan, S. & Tavenas, S. (2022). On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In S. Lovett (Ed.), 37th Computational Complexity Conference, CCC 2022 Article 32 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2022.32

Curticapean, R., Limaye, N. & Srinivasan, S. (2022). On the VNP-Hardness of Some Monomial Symmetric Polynomials. In A. Dawar & V. Guruswami (Eds.), 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 Article 16 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FSTTCS.2022.16

Caragiannis, I., Gravin, N., Lu, P. & Wang, Z. (2022). Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching. In M. Feldman, H. Fu & I. Talgam-Cohen (Eds.), Web and Internet Economics : 17th International Conference, WINE 2021 (pp. 131-148). Springer. https://doi.org/10.1007/978-3-030-94676-0_8

Tavenas, S., Limaye, N. & Srinivasan, S. (2022). Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. In S. Leonardi & A. Gupta (Eds.), STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 416-425). Association for Computing Machinery. https://doi.org/10.1145/3519935.3520044

Limaye, N., Srinivasan, S. & Tavenas, S. (2022). Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. In Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021 (pp. 804-814). IEEE Computer Society. https://doi.org/10.1109/FOCS52979.2021.00083

Caragiannis, I. & Fehrs, K. (2022). The Complexity of Learning Approval-Based Multiwinner Voting Rules. In AAAI-22 Technical Tracks 5 (Vol. 11, pp. 4925-4932). AAAI Press. https://doi.org/10.1609/aaai.v36i5.20422

Caragiannis, I., Shah, N. & Voudouris, A. A. (2022). The metric distortion of multiwinner voting. Artificial Intelligence, 313, Article 103802. https://doi.org/10.1016/j.artint.2022.103802

Caragiannis, I., Shah, N. & Voudouris, A. A. (2022). The Metric Distortion of Multiwinner Voting. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (Vol. 11, pp. 4900-4907). AAAI Press. https://doi.org/10.1609/aaai.v36i5.20419

Caragiannis, I., Christodoulou, G. & Protopapas, N. (2022). Truthful Aggregation of Budget Proposals with Proportionality Guarantees. In AAAI-22 Technical Tracks 5 (Vol. 11, pp. 4917-4924). AAAI Press. https://doi.org/10.1609/aaai.v36i5.20421

Bhandari, S., Harsha, P., Saptharishi, R. & Srinivasan, S. (2022). Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes. In S. Lovett (Ed.), 37th Computational Complexity Conference, CCC 2022 Article 31 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2022.31

Hansen, K. A., Liu, T. X. & Malekian, A. (Eds.) (2022). Web and Internet Economics: 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings. Springer. Lecture Notes in Computer Science Vol. 13778 https://doi.org/10.1007/978-3-031-22832-2

Hansen, K. A., Ibsen-Jensen, R. & Neyman, A. (2021). Absorbing games with a clock and two bits of memory. Games and Economic Behavior, 128, 213-230. https://doi.org/10.1016/j.geb.2021.04.008

Caragiannis, I. & Hansen, K. A. (Eds.) (2021). Algorithmic Game Theory: 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21-24, 2021, Proceedings. Springer. Lecture Notes in Computer Science https://doi.org/10.1007/978-3-030-85947-3

Hansen, K. A. & Lund, T. B. (2021). Computational Complexity of Computing a Quasi-Proper Equilibrium. In E. Bampis & A. Pagourtzis (Eds.), Fundamentals of Computation Theory - 23rd International Symposium, FCT 2021, Proceedings: 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings (pp. 259-271). Springer. https://doi.org/10.1007/978-3-030-86593-1_18

Blanc, M. & Hansen, K. A. (2021). Computational Complexity of Multi-player Evolutionarily Stable Strategies. In R. Santhanam & D. Musatov (Eds.), Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings (pp. 1-17). Springer. https://doi.org/10.1007/978-3-030-79416-31

Caragiannis, I. & Fanelli, A. (2021). On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Journal of Computer and System Sciences, 117, 40-48. https://doi.org/10.1016/j.jcss.2020.10.007

Caragiannis, I., Kanellopoulos, P. & Kyropoulou, M. (2021). On Interim Envy-Free Allocation Lotteries. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC 2021) (pp. 264-284). Association for Computing Machinery. https://doi.org/10.1145/3465456.3467648

Srinivasan, S. & Venkitesh, S. (2021). On the probabilistic degree of an n-variate boolean function. In M. Wootters & L. Sanita (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021 Article 42 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs-APPROX/RANDOM.2021.42

Caragiannis, I., Filos-Ratsikas, A., Kanellopoulos, P. & Vaish, R. (2021). Stable Fractional Matchings. Artificial Intelligence, 295, Article 103416. https://doi.org/10.1016/j.artint.2020.103416

Batziou, E., Hansen, K. A. & Høgh, K. (2021). Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem. In N. Bansal, E. Merelli & J. Worrell (Eds.), 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (Vol. 198, pp. 24:1-24:20). Article 24 Schloss Dagstuhl--Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2021.24

Caragiannis, I. & Voudouris, A. (2021). The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users. Mathematics of Operations Research, 46(2), 503-523. https://doi.org/10.1287/moor.2020.1070

Babai, L., Hansen, K. A., Podolskii, V. V. & Sun, X. (2021). Weights of exact threshold functions. Izvestiya: Mathematics, 85(6), 1039-1059. https://doi.org/10.1070/IM9113

Hansen, K. A. & Sølvsten, S. C. (2020). ∃R-completeness of stationary nash equilibria in perfect information stochastic games. In J. Esparza & D. Král (Eds.), 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 (pp. 45:1-45:15). Schloss Dagstuhl--Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2020.45

Hansen, K. A. & Raskin, M. (2019). A Stay-in-a-Set Game without a Stationary Equilibrium. In J. Leroux & J-F. Raskin (Eds.), Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification (Vol. 305, pp. 83-90). Electronic Proceedings in Theoretical Computer Science. https://doi.org/10.4204/EPTCS.305.6

Berthelsen, M. L. T. & Hansen, K. A. (2019). On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. In D. Fotakis & E. Markakis (Eds.), Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings (pp. 153-167). Springer VS. https://doi.org/10.1007/978-3-030-30473-7_11

Branzei, S., Orlandi, C. & Yang, G. (2019). Sharing Information with Competitors. In D. Fotakis & E. Markakis (Eds.), Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings: SAGT 2019 (pp. 34-48). Springer. https://doi.org/10.1007/978-3-030-30473-7

Hansen, K. A. (2019). The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. Theory of Computing Systems, 63(7), 1554-1571. https://doi.org/10.1007/s00224-018-9887-9

Dan, C., Hansen, K. A., Jiang, H., Wang, L. & Zhou, Y. (2018). Low rank approximation of binary matrices: Column subset selection and generalizations. In I. Potapov, J. Worrell & P. Spirakis (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 (Vol. 117, pp. 41:1-41:16). Article 41 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2018.41

Bosanský, B., Brânzei, S., Hansen, K. A., Lund, T. B. & Miltersen, P. B. (2017). Computation of Stackelberg Equilibria of Finite Sequential Games. A C M Transactions on Economics and Computation, 5(4), 23:1-23:24. Article 23. https://doi.org/10.1145/3133242

Chatterjee, K., Hansen, K. A. & Ibsen-Jensen, R. (2017). Strategy Complexity of Concurrent Safety Games. In K. G. Larsen, H. L. Bodlaender & J-F. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) (Vol. 83, pp. 55:1-55:13). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. https://doi.org/10.4230/LIPIcs.MFCS.2017.55

Hansen, K. A. (2017). The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. In V. Bilò & M. Flammini (Eds.), Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017 (pp. 119-130). Springer VS. https://doi.org/10.1007/978-3-319-66700-3_10

Displaying results 1 to 50 out of 204

Sort by: Date | Author | Title

Revised 23.08.2023