Source author record

Mónika Csikós

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

ResearcherUnclaimed source record

Computational Geometry Machine Learning math.CO Data Structures and Algorithms

Catalog footprint

Research overview

3works

4topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical

We study one of the key tools in data approximation and optimization: low-discrepancy colorings. Formally, given a finite set system $(X,\mathcal S)$ , the \emph{discrepancy} of a two-coloring $χ:X\to\{-1,1\}$ is defined as $\max_{S \in \mathcal S}|{χ(S)}|$ , where $χ(S)=\sum\limits_{x \in S}χ(x)$ . We propose a randomized algorithm which, for any $d>0$ and $(X,\mathcal S)$ with dual shatter function $π^*(k)=O(k^d)$ , returns a coloring with expected discrepancy $O\left({\sqrt{|X|^{1-1/d}\log|\mathcal S|}}\right)$ (this bound is tight) in time $\tilde O\left({|\mathcal S|\cdot|X|^{1/d}+|X|^{2+1/d}}\right)$ , improving upon the previous-best time of $O\left(|\mathcal S|\cdot|X|^3\right)$ by at least a factor of $|X|^{2-1/d}$ when $|\mathcal S|\geq|X|$ . This setup includes many geometric classes, families of bounded dual VC-dimension, and others. As an immediate consequence, we obtain an improved algorithm to construct $\varepsilon$ -approximations of sub-quadratic size. Our method uses primal-dual reweighing with an improved analysis of randomly updated weights and exploits the structural properties of the set system via matchings with low crossing number -- a fundamental structure in computational geometry. In particular, we get the same $|X|^{2-1/d}$ factor speed-up on the construction time of matchings with crossing number $O\left({|X|^{1-1/d}}\right)$ , which is the first improvement since the 1980s. The proposed algorithms are very simple, which makes it possible, for the first time, to compute colorings with near-optimal discrepancies and near-optimal sized approximations for abstract and geometric set systems in dimensions higher than $2$ .

preprint2022arXiv

Optimal Approximations Made Easy

The fundamental result of Li, Long, and Srinivasan on approximations of set systems has become a key tool across several communities such as learning theory, algorithms, computational geometry, combinatorics and data analysis. The goal of this paper is to give a modular, self-contained, intuitive proof of this result for finite set systems. The only ingredient we assume is the standard Chernoff's concentration bound. This makes the proof accessible to a wider audience, readers not familiar with techniques from statistical learning theory, and makes it possible to be covered in a single self-contained lecture in a geometry, algorithms or combinatorics course.

preprint2018arXiv

Induced Saturation of Graphs

A graph $G$ is $H$ -saturated for a graph $H$ , if $G$ does not contain a copy of $H$ but adding any new edge to $G$ results in such a copy. An $H$ -saturated graph on a given number of vertices always exists and the properties of such graphs, for example their highest density, have been studied intensively. A graph $G$ is $H$ -induced-saturated if $G$ does not have an induced subgraph isomorphic to $H$ , but adding an edge to $G$ from its complement or deleting an edge from $G$ results in an induced copy of $H$ . It is not immediate anymore that $H$ -induced-saturated graphs exist. In fact, Martin and Smith (2012) showed that there is no $P_4$ -induced-saturated graph. Behrens et.al. (2016) proved that if $H$ belongs to a few simple classes of graphs such as a class of odd cycles of length at least $5$ , stars of size at least $2$ , or matchings of size at least $2$ , then there is an $H$ -induced-saturated graph. This paper addresses the existence question for $H$ -induced-saturated graphs. It is shown that Cartesian products of cliques are $H$ -induced-saturated graphs for $H$ in several infinite families, including large families of trees. A complete characterization of all connected graphs $H$ for which a Cartesian product of two cliques is an $H$ -induced-saturated graph is given. Finally, several results on induced saturation for prime graphs and families of graphs are provided.

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.