Jiri Matousek's recent publications and preprints

Preprints in electronic form

Some of these are compressed postscript files (use "gunzip " before sending to a postscript printer). With the U.S. paper format, people sometimes have problems printing some of the files. If this happens to you, please send me an e-mail, I'll reformat the relevant paper or send you a TeX file.

Higher-order Erdos-Szekeres theorems with Marek Elias (arXiv preprint).
Unit Distances in Three Dimensions with Haim Kaplan, Zuzana Safernova, Micha Sharir (arXiv preprint).
Computing all maps into a sphere with Martin Cadek, Marek Krcal, Francis Sergeraert, Lukas Vokrinek, and Uli Wagner (arXiv preprint).
The dawn of an algebraic era in discrete geometry? A survey or blog-like text written for proceedings of the conference EuroCG 2011.
A doubly exponentially crumbled cake with Tobias Christ, Andrea Francke, Heidi Gebauer, and Takeaki Uno (Eurocomb 2011). The result of this paper has been surpassed by Dumitrescu and Toth.
Simple proofs of classical theorems in discrete geometry via the Guth--Katz polynomial partitioning technique with Haim Kaplan and Micha Sharir
The determinant bound for discrepancy is almost tight
On Gromov's method of selecting heavily covered points with Uli Wagner
A geometric proof of the colored Tverberg theorem with Martin Tancer and Uli Wagner
The number of unit distances is almost linear for most norms
On the nonexistence of k-reptile tetrahedra with Zuzana Safernova (to appear in Discr. Comput. Geom.)
Minimum and maximum against k lies with Michael Hoffmann, Yoshio Okamoto, Philipp Zumstein.
Zone diagrams in Euclidean spaces and in other normed spaces with Akitoshi Kawamura and Takeshi Tokuyama (Math. Annalen, to appear).
Distance k-Sectors Exist with Keiko Imai, Akitoshi Kawamura, Daniel Reem, and Takeshi Tokuyama (arXiv preprint)
Vectors in a Box with Kevin Buchin, Robin A. Moser, and Domotor Palvolgyi (arXiv preprint; to appear in Math. Programming)
Lower bounds for weak epsilon-nets and stair-convexity with Boris Bukh and Gabriel Nivasch (arXiv preprint)
Blocking visibility for points in general position; (Discr. Comput. Geom.). As was pointed out by David Wood, the main construction in this paper is almost the same as in this earlier paper of Janos Pach. So there isn't much new in the paper but the problem remains fascinating. An unfortunate mistake, found by Peter Terlecky and present in the published version, is fixed in this copy (in the proof of Theorem 1, m should be the root of log n, not log n).
Inapproximability for metric embeddings into R^d with Anastasios Sidiropoulos (arXiv preprint; appeared in FOCS 2008)
Hardness of embedding simplicial complexes in R^d with Martin Tancer and Uli Wagner (arXiv preprint; appeared in SODA 2009)
Stabbing simplices by points and flats with Boris Bukh and Gabriel Nivasch (Discr. Comput. Geom.)
How many points can be reconstructed from k projections? with Ales Privetivy and Petr Skovron (SIAM J. Discr. Math.)
On the gap between representability and collapsibility with Martin Tancer (Discr. Comput. Geom.). The result has recently been imroved by Tancer in this paper; finite projective planes are 2-collapsible but not representable in any fixed dimension.
Computing D-convex hulls in the plane with Vojtech Franek (Comput. Geom. Theor. Appl.)
Removing degeneracy in LP-type problems revisited (Discr. Comput. Geom.)
Graph coloring with no large monochromatic components with Nati Linial, Or Sheffet, and Gabor Tardos (extended abstract Eurocomb 2007, also in Comb. Probab. Comput.)
Large monochromatic components in two-colored grids with Ales Privetivy (SIAM J. Discr. Math.)
Violator spaces: structure and algorithms with Bernd Gartner, Leo Rust and Petr Skovron (extended abstract in Proc. ESA 2006; Discr. Appl. Math.)
On variants of the Johnson-Lindenstrauss lemma (Random Struc. Algo.)
Packing cones and their negatives in space with Imre Barany
Zone Diagrams: Existence and Uniqueness with Tetsuo Asano and Takeshi Tokuyama (SODA 2007; SIAM J. Comput.)
The distance trisector curve with Tetsuo Asano and Takeshi Tokuyama (STOC 2006; Adv. Math)
Nonexistence of 2-reptile simplices; this paper (published in LNCS 3742, Springer 2005, pages 151-160) contains an error, noticed by Zuzana Safernova, which is corrected here.
Towards Asymptotic Optimality in Probabilistic Packet Marking with Micah Adler and Jeff Edmonds (extenden abstract, STOC 2005; full version doesn't exist)
Random edge can be exponential on abstract cubes with Tibor Szabo (Adv. in Math.; extended abstract: FOCS 2004)
On k-Sets in Four Dimensions with Micha Sharir, Shakhar Smorodinsky, and Uli Wagner (Discr. Comput. Geom.)
Expected length of the longest common subsequence for large alphabets with Marcos Kiwi and Martin Loebl (Advances in Math.); here is a 3-page extended abstract
Crossing number, pair-crossing number, and expansion with Petr Kolman (J. Combin. Theory Ser. B)
New Constructions of Weak Epsilon-Nets with Uli Wagner, Proc. 19th ACM Sympos. Comput. Geom. (2003), also in Discr. Comput. Geom.
The randomized integer convex hull with Imre Barany (Discr. Comput. Geom.)
Topological lower bounds for the chromatic number: A hierarchy with G"unter M. Ziegler (J. DMV)
No Helly theorem for stabbing translates by lines in R^3 with Andreas Holmsen (Discr. Comput. Geom.)
The number of unique-sink orientations of the hypercube Combinatorica
Discrepancy after adding a single set with Jeong-Han Kim and Van Ha Vu (Combinatorica)
Bounded VC-dimension implies a fractional Helly theorem, Dicr. Comput. Geom.
A lower bound on the size of Lipschitz subsets in dimension 3, Combin. Probab. Comput.
Transversal Numbers for Hypergraphs Arising in Geometry with Noga Alon, Gil Kalai, and Roy Meshulam (Adv. Appl. Math)
A combinatorial proof of Kneser's conjecture (Combinatorica)

Jiri Matousek's home page