Publications

Sort by: Date | Author | Title

Branzei, S., Caragiannis, I., Morgenstern, J. & Procaccia, A. (2013). How Bad is Selfish Voting? In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence AAAI Press. http://www.aaai.org/Library/AAAI/aaai13contents.php

Branzei, S., Michalak, T., Rahwan, T., Larson, K. & Jennings, N. (2013). Matchings with Externalities and Attitudes. In M. Gina & O. Shehory (Eds.), International Conference on Autonomous Agents and Multi-agent Systems, AAMAS '13 (pp. 295-302 ). Association for Computing Machinery. http://dl.acm.org/citation.cfm?id=2484969&CFID=340403434&CFTOKEN=84711969

Frederiksen, S. K. S. & Miltersen, P. B. (2013). Monomial strategies for concurrent reachability games and other stochastic games. In P. A. Abdulla & I. Potapov (Eds.), Reachability Problems: 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings (pp. 122-134 ). Springer VS. https://doi.org/10.1007/978-3-642-41036-9_12

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

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

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, 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

Gal, A., Hansen, K. A., Koucky, M., Pudlak, P. & Viola, E. (2013). Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. I E E E Transactions on Information Theory, 59(10), 6611-6627. https://doi.org/10.1109/TIT.2013.2270275

Filos-Ratsika, A. & Miltersen, P. B. (2013). Truthful approximations to range voting. (1307.1766v1 ed.) arxiv.org. http://arxiv.org/pdf/1307.1766v1.pdf

Hansen, T. D., Ibsen-Jensen, R. & Miltersen, P. B. (2012). A Faster Algorithm for Solving One-Clock Priced Timed Games. http://arxiv.org/abs/1201.3498

Eickmeyer, K., Hansen, K. A. & Verbin, E. (2012). Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques. Electronic Colloquium on Computational Complexity, (TR12-25). http://eccc.hpi-web.de/report/2012/025/

Eickmeyer, K., Hansen, K. A. & Verbin, E. (2012). Approximating the minmax value of Three-player games within a constant is as hard as detecting planted cliques. Lecture Notes in Computer Science, 7615, 96-107. https://doi.org/10.1007/978-3-642-33996-7_9

Andersson, K. O. D., Hansen, K. A., Miltersen, P. B. & Sørensen, T. B. (2012). Deterministic Graphical Games Revisited. Journal of Logic and Computation, 22(2), 165-178. https://doi.org/10.1093/logcom/exq001

Branzei, S., Forero, C., Larson, K. & Miltersen, P. B. (2012). Equilibria of Chinese Auctions. arxiv.org. http://arxiv.org/abs/1208.0296

Hansen, K. A., Koucky, M., Lauritzen, N., Miltersen, P. B. & Tsigaridas, E. (2012). Exact Algorithms for Solving Stochastic Games. http://arxiv.org/abs/1202.3898

Branzei, S., Michalak, T., Rahwan, T., Larson, K. & Jennings, N. R. (2012). Matching Games with Additive Externalities. http://arxiv.org/abs/1207.3682

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

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

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

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

Gál , A., Hansen, K. A., Koucký, M., Pudlák, P. & Viola, E. (2012). Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. In H. Karloff & T. Pitassi (Eds.), STOC '12 Proceedings of the 44th symposium on Theory of Computing (pp. 479-494). Association for Computing Machinery. https://doi.org/10.1145/2213977.2214023

Ackerman, M., Ben-David, S., Branzei, S. & Loker, D. (2012). Weighted Clustering. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (pp. 858-863). AAAI Press.

Frandsen, G. S. & Sankowski, P. (2011). Dynamic normal forms and dynamic characteristic polynomial. Theoretical Computer Science, 412(16), 1470-1483. https://doi.org/10.1016/j.tcs.2010.11.049

Hansen, K. A., Koucký, M., Lauritzen, N., Miltersen, P. B. & Tsigaridas, E. (2011). Exact algorithms for solving stochastic games. In STOC'11: proceedings of the 43rd annual ACM symposium on Theory of computing (pp. 205-214). Association for Computing Machinery. https://doi.org/10.1145/1993636.1993665

Chattopadhyay, A., Gavaldá, R., Hansen, K. A. & Thérien, D. (2011). Learning Read-constant Polynomials of Constant Degree modulo Composites. Lecture Notes in Computer Science, 6651, 29-42. https://doi.org/10.1007/978-3-642-20712-9_3

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.

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

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

Hansen, K. A., Miltersen, P. B. & Ibsen-Jensen, R. (2011). The complexity of solving reachability games using value and strategy iteration. Lecture Notes in Computer Science, 6651, 77-90. https://doi.org/10.1007/978-3-642-20712-9_7

Gál, A., Hansen, K. A., Koucký, M., Pudlák, P. & Viola, E. (2011). Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. Electronic Colloquium on Computational Complexity, 18(150). http://eccc.hpi-web.de/report/2011/150/

Hansen, K. A. & Koucký, M. (2010). A New Characterization of ACC⁰ and Probabilistic CC⁰. Computational Complexity, 19(2), 211-234. https://doi.org/10.1007/s00037-010-0287-z

Miltersen, P. B. & Sørensen, T. B. (2010). Computing a quasi-perfect equilibrium of a two-player game. Economic Theory, 42(1), 175-192. https://doi.org/10.1007/s00199-009-0440-6

Hansen, K. A. & Podolskii, V. V. (2010). Exact Threshold Circuits. In 2010 IEEE 25th Annual Conference on Computational Complexity (pp. 270-279) https://doi.org/10.1109/CCC.2010.33

Hansen, K. A., Miltersen, P. B. & Sørensen, T. B. (2010). The computational complexity of trembling hand perfection and other equilibrium refinements. Lecture Notes in Computer Science, 6386, 198-209. https://doi.org/10.1007/978-3-642-16170-4_18

Babai, L., Hansen, K. A., Podolskii, V. V. & Sun, X. (2010). Weights of Exact Threshold Functions. Lecture Notes in Computer Science, 6281, 66-77. https://doi.org/10.1007/978-3-642-15155-2_8

Hansen, K. A. & Koucký, M. (2009). A new characterization of ACC⁰ and probabilistic CC⁰. In 2009 24th Annual IEEE Conference on Computational Complexity (pp. 27-34). IEEE. https://doi.org/10.1109/CCC.2009.15

Hansen, K. A. (2009). Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. Lecture Notes in Computer Science, 5675, 117-128. https://doi.org/10.1007/978-3-642-03351-3_13

Frandsen, G. S. & Frandsen, P. F. (2009). Dynamic Matrix Rank. Theoretical Computer Science, 410(41), 4085-4093. https://doi.org/10.1016/j.tcs.2009.06.012

Escamocher, G., Miltersen, P. B. & Santillan, R. (2009). Existence and computation of equilibria of first-price auctions with integral valuations and bids. In K. S. Decker, J. S. Sichman, C. Sierra & C. Castelfranchi (Eds.), Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09): SESSION: Interactions (Vol. 2, pp. 1227-1228). International Foundation for Autonomous Agents and Multiagent Systems. http://delivery.acm.org/10.1145/1560000/1558225/p1227-escamocher.pdf?key1=1558225&key2=4204373621&coll=GUIDE&dl=GUIDE&CFID=73345521&CFTOKEN=52226755

Hansen, K. A., Lachish, O. & Miltersen, P. B. (2009). Hilbert's thirteenth problem and circuit complexity. Lecture Notes in Computer Science, 5878, 153-162. https://doi.org/10.1007/978-3-642-10631-6_17

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., 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

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

Andersson, D. & Miltersen, P. B. (2009). The complexity of solving stochastic games on graphs. Lecture Notes in Computer Science, 112-121. https://doi.org/10.1007/978-3-642-10631-6_13

Hansen, K. A., Koucký, M. & Miltersen, P. B. (2009). Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. Symposium on Logic in Computer Science, 332-341. https://doi.org/10.1109/LICS.2009.44

Hansen, K. A., Hansen, T. D., Miltersen, P. B. & Sørensen, T. B. (2008). Approximability and Parameterized Complexity of Minmax Values. Lecture Notes in Computer Science, 5385, 684-695. https://doi.org/10.1007/978-3-540-92185-1_74

Miltersen, P. B. (Ed.) (2008). Conference on Computational Complexity 2007: Guest Editor's Foreword. Computational Complexity, 17(2), 147-148. https://doi.org/10.1007/s00037-008-0247-z

Hansen, K. A. (2008). Constant Width Planar Branching Programs Characterize ACC⁰ in Quasipolynomial Size. In 2008 23rd Annual IEEE Conference on Computational Complexity (pp. 92-99). IEEE. https://doi.org/10.1109/CCC.2008.11

Andersson, D., Hansen, K. A., Miltersen, P. B. & Sørensen, T. B. (2008). Deterministic Graphical Games Revisited. Lecture Notes in Computer Science, 5028, 1-10. https://doi.org/10.1007/978-3-540-69407-6_1

Displaying results 101 to 150 out of 250

Sort by: Date | Author | Title

Revised 01.09.2025