Publications

Sort by: Date | Author | Title

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

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.

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

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

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

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

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

Frandsen, G. S. & Sankowski, P. (2008). Dynamic Normal Forms and Dynamic Characteristic Polynomial. Lecture Notes in Computer Science, 434-446. https://doi.org/10.1007/978-3-540-70575-8_36

Hansen, K. A. (2007). Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates. In G. Lin (Ed.), Computing and Combinatorics: 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007. Proceedings (pp. 448-458). Springer. https://doi.org/10.1007/978-3-540-73545-8_44

Brodal, G. S., Georgiadis, L., Hansen, K. A. & Katriel, I. (2007). Dynamic Matchings in Convex Bipartite Graphs. In L. Kucera & A. Kucera (Eds.), Proc. 32nd International Symposium on Mathematical Foundations of Computer Science (pp. 406-417). Springer. https://doi.org/10.1007/978-3-540-74456-6_37

Hansen, K. A., Miltersen, P. B. & Sørensen, T. B. (2007). Finding Equilibria in Games of No Chance. In G. Lin (Ed.), Computing and Combinatorics: Proc. of 13th Annual International Computing and Combinatorics Conference (COCOON 2007) (pp. 274-284). Springer. https://doi.org/10.1007/978-3-540-73545-8_28

Agarwal, S. & Frandsen, G. S. (2006). A New GCD Algorithm for Quadratic Number Rings with Unique Factorization. In J. R. Correa, A. Hevia & M. A. Kiwi (Eds.), LATIN 2006: Theoretical Informatics, Proceedings of 7th Latin American Symposium (Valdivia, Chile, March 20-24, 2006) (pp. 30-42). Springer. https://doi.org/10.1007/11682462_8

Damgård, I. B. & Frandsen, G. S. (2006). An Extended Quadratic Frobenius Primality Test with Average- and Worst-Case Error Estimate. Journal of Cryptology, 19(4), 489-520. https://doi.org/10.1007/s00145-006-0332-x

Frandsen, G. S. & Schwartzbach, M. I. (2006). A singular choice for multiple choice. ACM SIGCSE Bulletin, 38(4), 34-38. https://doi.org/10.1145/1189136.1189164

Hansen, K. A., Miltersen, P. B. & Vinay, V. (2006). Circuits on Cylinders. Computational Complexity, 15(1), 62-81. https://doi.org/10.1007/s00037-006-0207-4

Hansen, K. A. (2006). Constant Width and Constant Depth Computation.

Hansen, K. A. (2006). Constant Width Planar Computation Characterizes ACC⁰. Theory of Computing Systems, 39(1), 79-92. https://doi.org/10.1007/s00224-005-1258-7

Frandsen, G. S. & Frandsen, P. F. (2006). Dynamic Matrix Rank. In M. Bugliesi, B. Preneel, V. Sassone & I. Wegener (Eds.), ICALP 2006: Automata, Languages and Programming: Proceedings (part I) of 33rd International Colloquium (Venice, Italy, July 10-14, 2006) (pp. 395-406) https://doi.org/10.1007/11786986_35

Hansen, K. A. (2006). Lower Bounds for Circuits with Few Modular Gates using Exponential Sums. Electronic Colloquium on Computational Complexity, 13(79). http://eccc.hpi-web.de/eccc-reports/2006/TR06-079/index.html

Hansen, K. A. (2006). On Modular Counting with Polynomials. In 21st Annual IEEE Conference on Computational Complexity (CCC'06) (pp. 202-212). IEEE Computer Society Press. https://doi.org/10.1109/CCC.2006.29

Damgård, I. B. & Frandsen, G. S. (2005). Efficient algorithms for gcd and cubic residuosity in the ring of Eisenstein integers. Journal of Symbolic Computation, 39(6), 643-652. https://doi.org/10.1016/j.jsc.2004.02.006

Hansen, K. A. & Chattopadhyay, A. (2005). Lower Bounds for Circuits with Few Modular and Symmetric Gates. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi & M. Yung (Eds.), Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings (pp. 994-1005). Springer. https://doi.org/10.1007/11523468_80

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

Agarwal, S. & Frandsen, G. S. (2004). Binary GCD like Algorithms for Some Complex Quadratic Rings. In D. Buell (Ed.), Algorithmic Number Theory: 6th International Symposium, ANTS-VI, Burlington, VT, USA, June 13-18, 2004, Proceedings (pp. 57-71). Springer. https://doi.org/10.1007/978-3-540-24847-7_4

Hansen, K. A. (2004). Constant Width Planar Computation Characterizes ACC⁰. In V. Diekert & M. Habib (Eds.), STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004. Proceedings (pp. 44-55). Springer. https://doi.org/10.1007/978-3-540-24749-4_5

Frandsen, G. S. & Shparlinski, I. E. (2004). On Reducing a System of Equations to a Single Equation. In 2004 International Symposium on Symbolic and Algebraic Computation (pp. 163-166). Association for Computing Machinery. https://doi.org/10.1145/1005285.1005310

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

Damgård, I. B. & Frandsen, G. S. (2003). An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates. In A. Lingas & B. J. Nilsson (Eds.), Fundamentals of Computation Theory (pp. 118-131). Springer. https://doi.org/10.1007/978-3-540-45077-1_12

Hansen, K. A., Miltersen, P. B. & Vinay, V. (2003). Circuits on Cylinders. In Fundamentals of Computation Theory (pp. 171-182). Springer. https://doi.org/10.1007/978-3-540-45077-1_17

Damgård, I. B. & Frandsen, G. S. (2003). Efficient Algorithms for gcd and Cubic Residuosity in the Ring of Eisenstein Integers. In A. Lingas & B. J. Nilsson (Eds.), Fundamentals of Computation Theory (pp. 109-117). Springer. https://doi.org/10.1007/978-3-540-45077-1_11

Displaying results 101 to 150 out of 172

Sort by: Date | Author | Title

Revised 01.09.2025