Publications

Sort by: Date | Author | Title

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

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

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: SAGT 2019 (pp. 34-48). Springer. Lecture Notes in Computer Science Vol. 11801 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). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics Vol. 25 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. Lecture Notes in Computer Science Vol. 1373 https://doi.org/10.1007/BFb0028550

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

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

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. Lecture Notes in Computer Science Vol. 7721 https://doi.org/10.1007/978-3-642-36046-6_6

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

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. Lecture Notes in Computer Science Vol. 8087 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

Frandsen, G. S. (1991). Parallel Construction of Irreducible Polynomials. Department of Computer Science, Aarhus University.

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

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

Frandsen, G. S. (2000). On the Density of Normal Bases in Finite Fields. Finite Fields and Their Applications, 6(1), 23-38. https://doi.org/10.1006/ffta.1999.0263

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. Lecture Notes in Computer Science Vol. 11801 https://doi.org/10.1007/978-3-030-30473-7_11

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.

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.

Cryan, M. & Miltersen, P. B. (2001). On pseudorandom generators in NC⁰. In J. Sgall, A. Pultr & P. Kolman (Eds.), Mathematical Foundations of Computer Science 2001: Lecture Notes in Computer Science (Lecture Notes in Computer Science 2136 ed., Vol. 2136/2001, pp. 272-284). Springer.

Barrington, D. A. M., Lu, C-J., Miltersen, P. B. & Skyum, S. (1999). On monotone planar circuits. In Fourteenth Annual IEEE Conference on Computational Complexity, 1999. Proceedings. (pp. 24-31). IEEE Computer Society Press. https://doi.org/10.1109/CCC.1999.766259

Miltersen, P. B., Nisan, N., Safra, S. & Wigderson, A. (1995). On data structures and asymmetric communication complexity. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing (pp. 103-111). Association for Computing Machinery. https://doi.org/10.1145/225058.225093

Miltersen, P. B., Nisan, N., Safra, S. & Wigderson, A. (1998). On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57(1), 37-49. https://doi.org/10.1006/jcss.1998.1577

Miltersen, P. B., Radhakrishnan, J. & Wegener, I. (2003). On converting CNF to DNF. In B. Rovan & P. Vojtás (Eds.), Mathematical Foundations of Computer Science 2003: 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings (pp. 612-621). Springer. Lecture Notes in Computer Science Vol. 2747 https://doi.org/10.1007/978-3-540-45138-9_55

Miltersen, P. B., Radhakrishnan, J. & Wegener, I. (2005). On converting CNF to DNF. Theoretical Computer Science, 347, 325-335.

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, T. D., Miltersen, P. B. & Sørensen, T. B. (2008). On Range of Skill. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence: Constraints, Satisfiability, and Search (pp. 277-282). AAAI Press.

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

Buhrman, H., Miltersen, P. B. & Laplante, S. (2000). New bounds for the language compression problem. In 15th Annual IEEE Conference on Computational Complexity, 2000. Proceedings. (pp. 126-130). IEEE Computer Society Press. https://doi.org/10.1109/CCC.2000.856742

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. Lecture Notes in Computer Science Vol. 8169 https://doi.org/10.1007/978-3-642-41036-9_12

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

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

Miltersen, P. B. (2005). Lower bounds on the size of rank and selection indexes. In Proceedings of the Symposium on Discrete Algorithms (pp. 11-12). Society for Industrial and Applied Mathematics.

Miltersen, P. B. (1994). Lower bounds for union-split-find related problems on random access machines. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (pp. 625-634). Association for Computing Machinery. https://doi.org/10.1145/195058.195415

Miltersen, P. B. (1996). Lower bounds for static dictionaries on RAMs with bit operations but no multiplication. In Automata, Languages and Programming: 23rd International Colloquium, ICALP '96 Paderborn, Germany, July 8-12, 1996 Proceedings (pp. 442-453). Springer. Lecture Notes in Computer Science Vol. 1099 https://doi.org/10.1007/3-540-61440-0_149

Frandsen, G. S., Hansen, J. P. & Miltersen, P. B. (1999). Lower bounds for dynamic algebraic problems. Lecture Notes in Computer Science, 362-372. https://doi.org/10.1007/3-540-49116-3

Frandsen, G. S., Hansen, J. P. & Miltersen, P. B. (2001). Lower Bounds for Dynamic Algebraic Problems. Information and Computation, 171(2), 333-349. https://doi.org/10.1006/inco.2001.3046

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. Lecture Notes in Computer Science Vol. 3580 https://doi.org/10.1007/11523468_80

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

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). [41] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics No. 117 https://doi.org/10.4230/LIPIcs.MFCS.2018.41

Displaying results 51 to 100 out of 193

Page 1

Page 2

Page 3

Page 4

Sort by: Date | Author | Title

Revised 16.11.2021 -