Dömötör Pálvölgyi

About me

I am a PhD student in math of the DCG group at EPFL. Here is my detailed CV:


I am mainly interested in Combinatorics, Combinatorial geometry and Complexity theory. Here is a detailed list of my results:

In preparation/To appear:

Bin Packing via Discrepancy of Permutations (with Friedrich Eisenbrand and Thomas Rothvoß), submitted. Almost optimal pairing strategy for Tic-Tac-Toe with numerous directions (with Padmini Mukkamala), submitted.
Unique-maximum and conflict-free colorings for hypergraphs and tree graphs. (with Panagiotis Cheilaris and Balázs Keszegh), submitted.
Permutations, hyperplanes and polynomials over finite fields (with András Gács, Tamás Héger and Zoltán Lóránt Nagy).
Finite Fields and Their Applications. (Earlier version: 22nd British Combinatorial Conference.)
On weakly intersecting pairs of sets (with Zoltán Király, Zoltán Lóránt Nagy and Mirkó Visontai). 7th International Conference on Lattice Path Combinatorics and Applications.
Indecomposable coverings with concave polygons. Discrete and Computational Geometry.



Finding the biggest and smallest element with one lie (with D. Gerbner, B. Patkós and G. Wiener). Discrete Applied Mathematics 158(9): 988-995 (2010). (Earlier version: International Conference on Interdisciplinary Mathematical and Statistical Techniques – IMST 2008 / FIM.)
Vectors in a Box (with Kevin Buchin, Jiri Matousek and Robin A. Moser). Coimbra Meeting on 0-1 Matrix Theory and Related Topics.
Consistent digital line segments (with Tobias Christ and Milos Stojakovic). SoCG 2010.
Testing additive integrality gaps (with Friedrich Eisenbrand, Nicolai Hähnle and Gennady Shmonin). SODA 2010.
Convex Polygons are Cover-Decomposable (with Géza Tóth). Discrete & Computational Geometry 43(3): 483-496 (2010).
Polychromatic Colorings of Arbitrary Rectangular Partitions (with D. Gerbner, B. Keszegh, N. Lemons, C. Palmer and B. Patkós). Discrete Math. 310, No. 1, 21-30 (2010). (Earlier version: 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications.)
Cubic Graphs Have Bounded Slope Parameter (with B. Keszegh, J. Pach, and G. Tóth). J. Graph Algorithms Appl. 14(1): 5-17 (2010). (Earlier version: Proceedings of Graph Drawing 2008, 50–60.)



2D-TUCKER is PPAD-complete. WINE 2009 Proceedings.
Combinatorial necklace splitting. Electron. J. Combin. 16 (2009), no. 1, Research Paper 79, 8 pp.
Deciding Soccer Scores and Partial Orientations of Graphs. Acta Univ. Sapientiae Math. 1 (2009), no. 1, 35–42. (Earlier version: EGRES Technical Reports 2008.)



Drawing cubic graphs with at most five slopes (with B. Keszegh, J. Pach, and G. Tóth). Comput. Geom. 40 (2008), no. 2, 138–147. (Earlier version: Graph drawing, 114–125, Lecture Notes in Comput. Sci., 4372, Springer, Berlin, 2007.)



Revisiting sequential search using question-sets with bounded intersections. J. Stat. Theory Pract. 1 (2007), no. 2, 199–204.



P2T is NP-complete. EGRES Quick-Proofs 2006.
Bounded-degree graphs can have arbitrarily large slope numbers (with János Pach). Electron. J. Combin. 13 (2006), no. 1, Note 1, 4 pp. (electronic).



Baljó S Árnyak (Left compressed shadows—a simple proof of the Kruskal-Katona theorem). Mat. Lapok (N.S.) 10 (2000/01), no. 2, 13–16 (2005).



Decomposition of Geometric Set Systems and Graphs. (PhD Thesis, 2010)
Communication Complexity. (Master’s Thesis, 2005)