Jiri Matousek's recent publications and preprints
Preprints in electronic form
- Combinatorial Discrepancy for Boxes via the Ellipsoid-Infinity Norm with Aleksandar Nikolov
- Multilevel polynomial partitions and simplified range searching with Zuzana Safernova
- Three-monotone interpolation
with Josef Cibulka and Pavel Patak
- String graphs and separators
(expository paper, part of lecture notes)
-
Embeddability in the 3-sphere is decidable
with Eric Sedgwick, Martin Tancer, and Uli Wagner
-
Curves in R^d intersecting every hyperplane at most d+1 times
with Imre Barany and Attila Por
-
Lower bounds on geometric Ramsey functions
with Marek Elias, Edgardo Roldan-Pensado, Zuzana Safernova
-
Computing higher homotopy groups is W[1]-hard
- Near-optimal separators in string graphs
-
Untangling two systems of noncrossing curves
with Eric Sedgwick, Martin Tancer, and Uli Wagner
- Polynomial- time computation of homotopy groups and Postnikov systems in fixed dimension
with Martin Cadek, Marek Krcal, Lukas Vokrinek, and Uli Wagner
-
Extendability of continuous maps is undecidable
with Martin Cadek, Marek Krcal, Lukas Vokrinek, and Uli Wagner
- Extending continuous maps:
polynomiality and undecidability (a survey)
with Martin Cadek, Marek Krcal, Lukas Vokrinek, and Uli Wagner
- On Range Searching with Semialgebraic Sets II with Pankaj K. Agarwal and Micha Sharir
-
Simplifying inclusion-exclusion formulas
with Xavier Goaoc, Pavel Patak, Zuzana Safernova, Martin Tancer
-
Erdos-Szekeres-type statements: Ramsey function and decidability in dimension 1 with Boris Bukh
-
Polynomial-time homology for simplicial Eilenberg-MacLane spaces
with Marek Krcal and Francis Sergeraert (arXiv preprint).
- 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