Publications

Sort by: Date | Author | Title

Fich, F. & Miltersen, P. B. (1995). Tables should be sorted (on random access machines). In S. G. Akl, F. Dehne, J.-R. Sack & N. Santoro (Eds.), Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16-18, 1995 Proceedings (pp. 482-493). Springer. https://doi.org/10.1007/3-540-60220-8_87

Miltersen, P. B., Vinodchandran, N. V. & Watanabe, O. (1999). Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. In T. Asano, H. Imai, D. T. Lee, S. Nakano & T. Tokuyama (Eds.), Computing and Combinatorics: 5th Annual International Conference, COCOON'99 Tokyo, Japan, July 26-28, 1999 Proceedings (pp. 210-220). Springer. https://doi.org/10.1007/3-540-48686-0_21

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 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2021.24

Hansen, T. D., Miltersen, P. B. & Zwick, U. (2013). Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor. Journal of the ACM, 60(1), Article No. 1 . https://doi.org/10.1145/2432622.2432623

Hansen, T. D., Miltersen, P. B. & Zwick, U. (2011). Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. In Proceedings of the Second Symposium on Innovations in Computer Science (pp. 253-263). Tsinghua University Press, Beijing. http://conference.itcs.tsinghua.edu.cn/ICS2011/content/papers/7.html

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). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2017.55

Andersson, A., Miltersen, P. B., Riis, S. & Thorup, M. (1996). Static dictionaries on AC⁰ RAMs: query time (√log n/log log n) is necessary and sufficient. In 37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings. (pp. 441-450). IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1996.548503

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

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

Hansen, K. A. & Miltersen, P. B. (2004). Some Meet-in-the-middle Circuit Lower Bounds. In J. Fiala, V. Koubek & J. Kratochvil (Eds.), Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings (pp. 334-345). Springer. https://doi.org/10.1007/978-3-540-28629-5_24

Ibsen-Jensen, R. & Miltersen, P. B. (2012). Solving Simple Stochastic Games with Few Coin Toss Positions. Lecture Notes in Computer Science, 7501, 636-647. https://doi.org/10.1007/978-3-642-33090-2_55

Ibsen-Jensen, R. & Miltersen, P. B. (2011). Solving simple stochastic games with few coin toss positions. http://arxiv.org/abs/1112.5255

Bielikova, M., Nielsen, M., Kucera, A., Miltersen, P. B., Palamidessi, C., Tuma, P. & Valencia, F. (Eds.) (2009). SOFSEM 2009: Theory and Practice of Computer Science: 35th Conference on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn, Czech Republic, January 24-30, 2009. Proceedings. Springer. Lecture Notes in Computer Science Vol. 5404 https://doi.org/10.1007/978-3-540-95891-8

Balkanski, E., Branzei, S., Kurokawa, D. & Procaccia, A. D. (2014). Simultaneous Cake Cutting. In Proceedings of the 28th AAAI Conference on Artificial Intelligence AAAI Press. http://www.aaai.org/ocs/index.php/AAAI/AAAI14/schedConf/presentations

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., Koucky, M., Lauritzen, N. & Tsigaridas, E. (2011). Separation bounds for real roots of polynomial systems. Paper presented at MEGA 2011: Effective Methods in Algebraic Geometry, Stockholm, Sweden.

Miltersen, P. B. & Sheffet, O. (2012). Send mixed signals : earn more, work less. In B. Faltings, K. Leyton-Brown & P. Ipeirotis (Eds.), EC '12 Proceedings of the 13th ACM Conference on Electronic Commerce (pp. 234-247). Association for Computing Machinery. https://doi.org/10.1145/2229012.2229033

Miltersen, P. B. (2014). Semi-algebraic geometry in computational game theory - A consumer's perspective: Invited Talk. In E. W. Mayr & N. Portier (Eds.), 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) (pp. 11-12). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2014.11

Damgård, I. B., Kölker, J. & Miltersen, P. B. (2012). Secret Sharing and Secure Computing from Monotone Formulae. http://eprint.iacr.org/2012/536

Barrington, D. A. M., Lu, C.-J., Miltersen, P. B. & Skyum, S. (1998). Searching constant width mazes captures the AC⁰ hierarchy. In M. Morvan, C. Meinel & D. Krob (Eds.), STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25-27, 1998 Proceedings (pp. 73-83). Springer. https://doi.org/10.1007/BFb0028550

Frandsen, G. S. & Miltersen, P. B. (2005). Reviewing Bounds on the Circuit Size of the Hardest Functions. Information Processing Letters, 95(2), 354-357. https://doi.org/10.1016/j.ipl.2005.03.009

Ackerman, M. & Branzei, S. (2012). Research Quality, Fairness, and Authorship Order. http://arxiv.org/abs/1208.3391

Caragiannis, I. & Narang, S. (2023). Repeatedly Matching Items to Agents Fairly and Efficiently. In A. Deligkas & A. Filos-Ratsikas (Eds.), Algorithmic Game Theory: 16th International Symposium, SAGT 2023, Egham, UK, September 4–7, 2023, Proceedings (pp. 347-364). Springer. https://doi.org/10.1007/978-3-031-43254-5_20

Caragiannis, I. & Narang, S. (2023). Repeatedly Matching Items to Agents Fairly and Efficiently. In AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (pp. 2670-2672). Association for Computing Machinery.

Caragiannis, I. & Narang, S. (2024). Repeatedly matching items to agents fairly and efficiently. Theoretical Computer Science, 981, Article 114246. https://doi.org/10.1016/j.tcs.2023.114246

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

Kautz, S. M. & Miltersen, P. B. (1996). Relative to a Random Oracle, NP is not small. Journal of Computer and System Sciences, 235-250. https://doi.org/10.1006/jcss.1996.0065

Kautz, S. M. & Miltersen, P. B. (1994). Relative to a Random Oracle, NP is not small. In Proceedings of the Ninth Annual Structure in Complexity Theory Conference, 1994. (pp. 162-174). IEEE Computer Society Press.

Miltersen, P. B. (2013). Recent results on howard's algorithm. In A. Kučera (Ed.), Mathematical and Engineering Methods in Computer Science: 8th International Doctoral Workshop, MEMICS 2012, Znojmo, Czech Republic, October 25-28, 2012, Revised Selected Papers (pp. 53-56). Springer VS. https://doi.org/10.1007/978-3-642-36046-6_6

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). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2020.45

Caragiannis, I. & Kalantzis, G. (2024). Randomized learning-augmented auctions with revenue guarantees. In K. Larson (Ed.), Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI) (pp. 2687-2694). International Joint Conferences on Artificial Intelligence.

Miltersen, P. B., Nielsen, J. B. & Triandopoulos, N. (2009). Privacy-Enhancing Auctions Using Rational Cryptography. Lecture Notes in Computer Science, 5677, 541-558. https://doi.org/10.1007/978-3-642-03356-8_32

Filos-Ratsikas, A., Hansen, K. A., Høgh, K. & Hollender, A. (2024). PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization. In B. Mohar, I. Shinkar & R. O'Donnell (Eds.), STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 1204-1215). Association for Computing Machinery, Inc.. https://doi.org/10.1145/3618260.3649645

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

Hansen, K. A. & Podolskii, V. V. (2013). Polynomial threshold functions and Boolean threshold circuits. Electronic Colloquium on Computational Complexity, (TR13-021). http://eccc.hpi-web.de/report/2013/021/

Hansen, K. A. & Podolskii, V. V. (2013). Polynomial threshold functions and Boolean threshold circuits. In K. Chatterjee & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (pp. 516-527 ). Springer VS. https://doi.org/10.1007/978-3-642-40313-2_46

Hansen, K. A. & Podolskii, V. V. (2015). Polynomial threshold functions and Boolean threshold circuits. Information and Computation, 240, 56-73. https://doi.org/10.1016/j.ic.2014.09.008

Hansen, K. A., Ibsen-Jensen, R., Podolskii, V. V. & Tsigaridas, E. (2013). Patience of matrix games. Discrete Applied Mathematics, 161(16-17), 2440–2459. http://www.sciencedirect.com.ez.statsbiblioteket.dk:2048/science/article/pii/S0166218X13002357

Caragiannis, I. & Schwartzbach, N. I. (2023). Outsourcing Adjudication to Strategic Jurors. In E. Elkind (Ed.), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (pp. 2546-2553). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2023/283

Caragiannis, I. & Rathi, N. (2024). Optimizing Over Serial Dictatorships. Theory of Computing Systems, 68(5), 1180-1206. https://doi.org/10.1007/s00224-024-10196-6

Caragiannis, I. & Rathi, N. (2023). Optimizing over Serial Dictatorships. In A. Deligkas & A. Filos-Ratsikas (Eds.), Algorithmic Game Theory: 16th International Symposium, SAGT 2023, Egham, UK, September 4–7, 2023, Proceedings (pp. 329-346). Springer. https://doi.org/10.1007/978-3-031-43254-5_19

Miltersen, P. B. (2000). On the Shannon function for partially defined Boolean functions. In Proceedings of the Workshop on Boolean Functions and Applications

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

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

Caragiannis, I., Hansen, K. A. & Rathi, N. (2024). On the Complexity of Pareto-Optimal and Envy-Free Lotteries. In AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (pp. 244-252). Association for Computing Machinery. https://dl.acm.org/doi/10.5555/3

Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J. & Miltersen, P. B. (2005). On the Complexity of Numerical Analysis. Electronic Colloquium on Computational Complexity, (TR05-037), 1-12.

Miltersen, P. B., Kjeldgaard-Pedersen, J., Burgisser, P. & Allender, E. (2006). On the Complexity of Numerical Analysis. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity (pp. 331-339). IEEE Computer Society Press.

Miltersen, P. B., Allender, E., Burgisser, P. & Kjeldgaard-Pedersen, J. (2009). On the complexity of numerical analysis. S I A M Journal on Computing, 38(5), 1987-2006. https://doi.org/10.1137/070697926

Miltersen, P. B. (1995). On the cell probe complexity of polynomial evaluation. Theoretical Computer Science, 143(1), 167-174. https://doi.org/10.1016/0304-3975(95)80032-5

Arge, L. A. & Miltersen, P. B. (1999). On showing lower bounds for external-memory computational geometry problems. D I M A C S Series in Discrete Mathematics and Theoretical Computer Science, 50, 139-160.

Displaying results 51 to 100 out of 217

Sort by: Date | Author | Title

Revised 23.08.2023