Source author record

Roland Markó

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.CO math.PR math.OC math.ST Statistics Theory

Catalog footprint

Research overview

6works

6topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

A Poisson allocation of optimal tail

The allocation problem for a $d$ -dimensional Poisson point process is to find a way to partition the space to parts of equal size, and to assign the parts to the configuration points in a measurable, "deterministic" (equivariant) way. The goal is to make the diameter $R$ of the part assigned to a configuration point have fast decay. We present an algorithm for $d\geq3$ that achieves an $O(\operatorname {exp}(-cR^d))$ tail, which is optimal up to $c$ . This improves the best previously known allocation rule, the gravitational allocation, which has an $\operatorname {exp}(-R^{1+o(1)})$ tail. The construction is based on the Ajtai-Komlós-Tusnády algorithm and uses the Gale-Shapley-Hoffman-Holroyd-Peres stable marriage scheme (as applied to allocation problems).

preprint2016arXiv

Complexity of Nondeterministic Graph Parameter Testing

We study the sample complexity of nondeterministically testable graph parameters and improve existing bounds on it by several orders of magnitude. The technique used would be also of independent interest. We also discuss the special case of weak nondeterministic testing for uniform hypergraphs of arbitrary order.

preprint2016arXiv

Limits of CSP Problems and Efficient Parameter Testing

We present a unified framework on the limits of constraint satisfaction problems (CSPs) and efficient parameter testing which depends only on array exchangeability and the method of cut decomposition without recourse to the weakly regular partitions. In particular, we formulate and prove a representation theorem for compact colored $r$ -uniform directed hypergraph ( $r$ -graph) limits, and apply this to $r$ CSP limits. We investigate the sample complexity of testable $r$ -graph parameters, we discuss the generalized ground state energies and demonstrate that they are efficiently testable.

preprint2015arXiv

Explicit Bounds for Nondeterministically Testable Hypergraph Parameters

In this note we give a new effective proof method for the equivalence of the notions of testability and nondeterministic testability for uniform hypergraph parameters. We provide the first effective upper bound on the sample complexity of any nondeterministically testable $r$ -uniform hypergraph parameter as a function of the sample complexity of its witness parameter for arbitrary $r$ . The dependence is of the form of an exponential tower function with the height linear in $r$ . Our argument depends crucially on the new upper bounds for the $r$ -cut norm of sampled $r$ -uniform hypergraphs. We employ also our approach for some other restricted classes of hypergraph parameters, and present some applications.

preprint2015arXiv

On the Complexity of Nondeterministically Testable Hypergraph Parameters

The paper proves the equivalence of the notions of nondeterministic and deterministic parameter testing for uniform dense hypergraphs of arbitrary order. It generalizes the result previously known only for the case of simple graphs. By a similar method we establish also the equivalence between nondeterministic and deterministic hypergraph property testing, answering the open problem in the area. We introduce a new notion of a cut norm for hypergraphs of higher order, and employ regularity techniques combined with the ultralimit method.

preprint2014arXiv

Lower threshold ground state energy and testability of minimal balanced cut density

Lovász and his coauthors defined the notion of microcanonical ground state energy $\hat{\mathcal{E}}_\mathbb{a} (G,J)$ -- borrowed from the statistical physics -- for weighted graphs $G$ , where $\mathbb{a}$ is a probability distribution on $\{1,...,q\}$ and $J$ is a symmetric $q \times q$ matrix with real entries. We define a new version of the ground state energy, $\hat{\mathcal{E}}^c (G,J)=\inf_{\mathbb{a}\in A_c}\hat{\mathcal{E}}_\mathbb{a} (G,J)$ , called lower threshold ground state energy, where $A_c = \{\mathbb{a} :\, a_i\ge c,\,i=1,\dots, q \}$ . Both types of energies can be extended for graphons $W$ , the limit objects of convergent sequences of simple graphs. In the main result of the paper it is stated that if $0\leq c_1<c_2 \leq 1$ , then the convergence of the sequences $(\hat{\mathcal{E}}^{c_2/q} (G_n,J))$ for each $J$ implies convergence of the sequences $(\hat{\mathcal{E}}^{c_1/q} (G_n,J))$ for each $J$ . As a byproduct one can derive in a natural way the testability of minimum balanced multiway cut densities, that is one of the fundamental problems of cluster analysis.

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.

Roland Markó

Research overview

Is this your work?

6 publications

A Poisson allocation of optimal tail

Complexity of Nondeterministic Graph Parameter Testing

Limits of CSP Problems and Efficient Parameter Testing

Explicit Bounds for Nondeterministically Testable Hypergraph Parameters

On the Complexity of Nondeterministically Testable Hypergraph Parameters

Lower threshold ground state energy and testability of minimal balanced cut density

See the researcher in context

Building this map preview