Source author record

Gabor Kun

Gabor Kun appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

3works
5topics
3close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

3 published item(s)

preprint2022arXiv

Perfect matchings in hyperfinite graphings

We characterize hyperfinite bipartite graphings that admit measurable perfect matchings. In particular, we prove that every regular hyperfinite bipartite graphing admits a measurable perfect matching if it is one-ended or the degree is odd. We give several applications of this result, answering various open questions in the field. For instance, we extend the Lyons--Nazarov theorem by characterizing bipartite Cayley graphs which admit a factor of iid perfect matching, answering the bipartite case of a well-known question of Lyons and Nazarov, popularized by Kechris and Marks. Moreover, we show how our results apply to measurable equidecompositions and, in particular, generalize the recent result of Grabowski, Máthé and Pikhurko on the measurable circle squaring. Our approach applies more generally to rounding measurable perfect fractional matchings.

preprint2013arXiv

Constraints, MMSNP and expander relational structures

We give a poly-time construction for a combinatorial classic known as Sparse Incomparability Lemma, studied by Erdos, Lovasz, Nesetril, Rodl and others: We show that every Constraint Satisfaction Problem is poly-time equivalent to its restriction to structures with large girth. This implies that the complexity classes CSP and Monotone Monadic Strict NP introduced by Feder and Vardi are computationally equivalent. The technical novelty of the paper is a concept of expander relations and a new type of product for relational structures: a generalization of the zig-zag product, the twisted product.

preprint2012arXiv

Lattice Sparsification and the Approximate Closest Vector Problem

We give a deterministic algorithm for solving the (1+eps)-approximate Closest Vector Problem (CVP) on any n dimensional lattice and any norm in 2^{O(n)}(1+1/eps)^n time and 2^n poly(n) space. Our algorithm builds on the lattice point enumeration techniques of Micciancio and Voulgaris (STOC 2010) and Dadush, Peikert and Vempala (FOCS 2011), and gives an elegant, deterministic alternative to the "AKS Sieve" based algorithms for (1+eps)-CVP (Ajtai, Kumar, and Sivakumar; STOC 2001 and CCC 2002). Furthermore, assuming the existence of a poly(n)-space and 2^{O(n)} time algorithm for exact CVP in the l_2 norm, the space complexity of our algorithm can be reduced to polynomial. Our main technical contribution is a method for "sparsifying" any input lattice while approximately maintaining its metric structure. To this end, we employ the idea of random sublattice restrictions, which was first employed by Khot (FOCS 2003) for the purpose of proving hardness for Shortest Vector Problem (SVP) under l_p norms.