Selected Publications of Research Area L

[L:GKa] S. Geschke and M. Kojman. Symmetrized induced Ramsey theorems. Graphs and Combinatorics. DOI:10.1007/s00373-010-1006-x, to appear.

[L:GKb] M. Gitik and P. Koepke. Violating the singular cardinals hypothesis without large cardinals. Israel Journal of Mathematics. to appear.

[L:IKRS] G. Ivanyos, M. Karpinski, L. Rónyai, and N. Saxena. Trading GRH for algebra: Algorithms for factoring polynomials and related structures. Mathematics of Computation. DOI:10.1090/S0025-5718-2011-02505-6, to appear.

[L:FG11] S. Frick and S. Geschke. Basis theorems for continuous n-colorings. Journal of Combinatorial Theory A, 118:1334–1349, 2011.

[L:SS11] N. Saxena and C. Seshadhri. An almost optimal rank bound for depth-3 identities. SIAM Journal on Computing, 40:200–224, 2011.

[L:CKKS10] M. Cramer, P. Koepke, D. Kühlwein, and B. Schröder. Premise selection in the Naproche system. In Proceedings of the 5th International Joint Conference on Automated Reasoning (IJCAR), pages 434–440. Springer, 2010.

[L:GJK10] L. A. Goldberg, M. Jerrum, and M. Karpinski. The mixing time of Glauber dynamics for coloring regular trees. Random Structures and Algorithms, 36:464–476, 2010.

[L:IKS10] G. Ivanyos, M. Karpinski, and N. Saxena. Deterministic polynomial time algorithms for matrix completion problems. SIAM Journal on Computing, 39:3736–3751, 2010.

[L:KRS10] M. Karpinski, A. Rucinski, and E. Szymanska. The complexity of perfect matching problems on dense hypergraphs. International Journal of Foundations of Computer Science, 21:905–924, 2010.

[L:KS10] M. Karpinski and W. Schudy. Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), pages 3–14. Springer, 2010.

[L:KAF+10] T. Kleinjung, K. Aoki, J. Franke, A. Lenstra, E. Thome, J. Bos, P. Gaudry, A. Kruppa, P. Montgomery, D. Osvik, H. te Riele, A. Timofeev, and P. Zimmermann. Factorization of a 768-bit RSA modulus. In Proceedings of the 30th Annual Cryptology Conference (CRYPTO), pages 333–350. Springer, 2010.

[L:IKS09] G. Ivanyos, M. Karpinski, and N. Saxena. Schemes for deterministic polynomial factoring. In Proceedings of the 34th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 191–198. Springer, 2009.

[L:KS09] M. Karpinski and W. Schudy. Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), pages 626–636, 2009.

[L:Koe09] P. Koepke. Ordinal computability. In Proceedings of the 5th Conference on Computability in Europe (CiE), pages 280–289. Springer, 2009.

[L:KS09] P. Koepke and B. Seyfferth. Ordinal machines and admissible recursion theory. Annals of Pure and Applied Logic, 160:310–318, 2009.

[L:BKS07] P. Berman, M. Karpinski, and A. Scott. Computational complexity of some restricted instances of 3SAT. Discrete Applied Mathematics, 155:649–653, 2007.