Publications

Sort by: Date | Author | Title

Kristensen, J. T. & Miltersen, P. B. (2006). Finding small OBDDs for incompletely specified truth tables is hard. Electronic Colloquium on Computational Complexity, (TR06-004), 1-6. http://eccc.hpi-web.de/eccc-reports/2006/TR06-004/index.html

Miltersen, P. B. & Kristensen, J. T. (2006). Finding small OBDDs for incompletely specified truth tables is hard. In D. Z. Chen & D. T. Lee (Eds.), Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006. Proceedings (pp. 489-496). Springer. https://doi.org/10.1007/11809678_51

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

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. & Vinodchandran, N. V. (2005). Derandomizing Arthur-Merlin Games using Hitting Sets. I E E E Conference on Computational Complexity. Proceedings, 14(3), 256-279. https://doi.org/10.1007/s00037-005-0197-7

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

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., Radhakrishnan, J. & Wegener, I. (2005). On converting CNF to DNF. Theoretical Computer Science, 347, 325-335.

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.

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

Miltersen, P. B. (2005). The Computational Complexity of One-Dimensional Sandpiles. In S. B. Cooper, B. Löwe & L. Torenvliet (Eds.), New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings (pp. 342-350). Springer. https://doi.org/10.1007/11494645_42

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

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

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

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. https://doi.org/10.1007/978-3-540-45138-9_55

Gal, A. & Miltersen, P. B. (2003). The Cell Probe Complexity of Succinct Data Structures. In J. C. M. Baeten, J. K. Lenstra, J. Parrow & G. J. Wöeginger (Eds.), Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings (pp. 442-453). Springer. https://doi.org/10.1007/3-540-45061-0_28

Buhrman, H., Miltersen, P. B., Radhakrishnan, J. & Venkatesh, S. (2002). Are Bitvectors Optimal? S I A M Journal on Computing, 31(6), 1723-1744. https://doi.org/10.1137/S0097539702405292

Hansen, K. A., Miltersen, P. B. & Vinay, V. (2002). Circuits on Cylinders. Electronic Colloquium on Computational Complexity, (TR02-066).

Miltersen, P. B., Rajasekaran, S. (Ed.), Pardalos, P. M. (Ed.), Reif, J. H. (Ed.) & Rolim, J. D. P. (Ed.) (2001). Derandomizing complexity classes. In Handbook on Randomized Computing: Combinatorial Optimization, Vol. 9 (chapter 19 ed., Vol. II, chapter 19, pp. 843-935). Kluwer Academic Publishers (Springer).

Hagerup, T., Miltersen, P. B. & Pagh, R. (2001). Deterministic Dictionaries. Journal of Algorithms, 41, 69-85.

Hagerup, T., Miltersen, P. B. & Pagh, R. (2001). Deterministic Dictionaries. J. Algorithms, 41(1), 69-85.

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

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.

Buhrman, H., Miltersen, P. B., Radhakrishnan, J. & Venkatesh, S. (2000). Are bitvectors optimal? In Proceedings of the thirty-second annual ACM symposium on Theory of computing (pp. 449-458). Association for Computing Machinery. https://doi.org/10.1145/335305.335357

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

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

Miltersen, P. B. & Vinodchandran, N. V. (1999). Derandomizing Arthur-Merlin games using hitting sets. In Proceedings of the 40th annual Foundations of Computer Science (pp. 71-80). IEEE Computer Society Press. https://doi.org/10.1109/SFFCS.1999.814579

Andersson, A., Miltersen, P. B. & Thorup, M. (1999). Fusion trees can be implemented with AC⁰ instructions only . Theoretical Computer Science, 215, 337-344. https://doi.org/10.1016/S0304-3975(98)00172-8

Alon, N., Dietzfelbinger, M., Miltersen, P. B., Petrank, E. & Tardos, G. (1999). Linear hash functions. Association for Computing Machinery. Journal, 46(5), 667-683. https://doi.org/10.1145/324133.324179

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

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

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.

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

Skyum, S., Frandsen, G. S., Miltersen, P. B. & Binderup, P. G. (1999). The Complexity of Identifying Large Equivalence Classes. Fundamenta Informaticae, 38(1-2), 25-37. https://doi.org/10.3233/FI-1999-381203

Miltersen, P. B. (1998). Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries. In Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms (pp. 556-563). Association for Computing Machinery.

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

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. & Skyum, S. (1997). Dynamic word problems. Association for Computing Machinery. Journal, 44(2), 257-271. https://doi.org/10.1145/256303.256309

Alon, N., Dietzfelbinger, M., Miltersen, P. B., Petrank, E. & Tardos, G. (1997). Is linear hashing good? In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (pp. 465-474). Association for Computing Machinery. https://doi.org/10.1145/258533.258639

Brodnik, A., Miltersen, P. B. & Munro, J. I. (1997). Trans-dichotomous algorithms without multiplication - some upper and lower bounds. In F. Dehne, A. Rau-Chaplin, J.-R. Sack & R. Tamassia (Eds.), Algorithms and Data Structures: 5th International Workshop, WADS'97 Halifax, Nova Scotia, Canada August 6-8, 1997 Proceedings (pp. 426-436). Springer. https://doi.org/10.1007/3-540-63307-3_80

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. https://doi.org/10.1007/3-540-61440-0_149

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

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

Miltersen, P. B., Paterson, M. & Tarui, J. (1996). The asymptotic complexity of merging networks. Association for Computing Machinery. Journal, 43(1), 147-165. https://doi.org/10.1145/227595.227693

Frandsen, G. S., Husfeldt, T., Miltersen, P. B., Rauhe, T. & Skyum, S. (1995). Dynamic algorithms for the Dyck languages. 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. 98-108). Springer. https://doi.org/10.1007/3-540-60220-8_54

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

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., Subramanian, S., Vitter, J. S. & Tamassia, R. (1994). Complexity models for incremental computation. Theoretical Computer Science, 130(1), 203-236. https://doi.org/10.1016/0304-3975(94)90159-7

Displaying results 151 to 200 out of 209

Sort by: Date | Author | Title

Revised 23.08.2023