A plank is the part of space between two parallel planes. The following open problem, posed 45 years ago, can be viewed as the converse of Tarski’s plank problem (Bang’s theorem): Is it true that if the total width of a collection of planks is sufficiently large, then the planks can be individually translated to cover a unit ball B? A translative covering of B by planks is said to be non-dissective if the planks can be added one by one, in some order, such that the uncovered part remains connected at each step and is empty at the end. Improving a classical result of Groemer, we show that every set of C/ε^{7/4} planks of width ε admits a non-dissective translative covering of a 3-dimensional ball B³, provided C is large enough. Our proof yields a low-complexity algorithm. We also show that c/ε^{4/3} planks are, in general, insufficient for a non-dissective covering of B³. This provides the first non-trivial lower bound for this problem.

For a given metric space \((P,\phi)\), a tree cover of stretch \(t\) is a collection of trees on \(P\) such that edges \((x,y)\) of trees receive length \(\phi(x,y)\), and such that for any pair of points \(u,v \in P\) there is a tree \(T\) in the collection such that the induced graph distance in \(T\) between \(u\) and \(v\) is at most \(t\phi(u,v)\). In this paper, we show that, for any set of points \(P\) on the Euclidean plane, there is a tree cover consisting of two trees and with stretch \(O(1)\). Although the problem in higher dimensions remains elusive, we manage to prove that for a slightly stronger variant of a tree cover problem we must have at least \((d+1)/2\) trees in any constant stretch tree cover in \(\mathbb{R}^d\).

We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant ε ∈ (0,1), one could construct a (2 + ε )-spanner with O (n log(n )) edges (SICOMP 2019), and there is a lower bound of Ω(n2) edges for any (2 — ε )-spanner (SoCG 2015). The main open question is whether a linear number of edges suffices and the stretch can be reduced to 2. We resolve this problem by showing that for stretch 2, one needs Ω(n log n ) edges, and for stretch 2 + ε for any fixed ε ∈ (0,1), O (n ) edges are sufficient. Our lower bound is the first super-linear lower bound for stretch 2.

Abstract. Let us consider a collection [Formula: see text] of codewords of length [Formula: see text] over an alphabet of size [Formula: see text]. Let [Formula: see text] be nonnegative integers. What is the maximum of [Formula: see text] subject to the condition that any two codewords should have at least [Formula: see text] positions where both have letter [Formula: see text] ([Formula: see text])? In the case [Formula: see text] it is a longstanding open question. Quite surprisingly we obtain an almost complete answer for [Formula: see text]. The main tool is a correlation inequality.

Abstract. We study vulnerability of a uniformly distributed random graph to an attack by an adversary who aims for a global change of the distribution while being able to make only a local change in the graph. We call a graph property [Formula: see text] antistochastic if the probability that a random graph [Formula: see text] satisfies [Formula: see text] is small but, with high probability, there is a small perturbation transforming [Formula: see text] into a graph satisfying [Formula: see text]. While for labeled graphs such properties are easy to obtain from binary covering codes, the existence of antistochastic properties for unlabeled graphs or, in other words, isomorphism-invariant antistochastic properties, is not so evident. If an admissible perturbation is either the addition or the deletion of one edge, we exhibit an isomorphism-invariant antistochastic property that is satisfied by a random graph of order [Formula: see text] with probability [Formula: see text], which is as small as possible. We also express another antistochastic property in terms of the degree sequence of a graph. This property has probability [Formula: see text], which is optimal up to a factor of 2.

Abstract We say that a set of points $$S\subset {{\mathbb {R}}}^d$$ S ⊂ R d is an $$\varepsilon $$ ε -nearly k-distance set if there exist $$1\le t_1\le \ldots \le t_k$$ 1 ≤ t 1 ≤ … ≤ t k , such that the distance between any two distinct points in S falls into $$[t_1,t_1+\varepsilon ]\cup \cdots \cup [t_k,t_k+\varepsilon ]$$ [ t 1 , t 1 + ε ] ∪ ⋯ ∪ [ t k , t k + ε ] . In this paper, we study the quantity $$\begin{aligned} M_k(d) = \lim _{\varepsilon \rightarrow 0}\max {\{|S|:S\,\text { is an}\, \varepsilon \text {-nearly}\, k\text {-distance set in}\,{{\mathbb {R}}}^d\}} \end{aligned}$$ M k ( d ) = lim ε → 0 max { | S | : S is an ε -nearly k -distance set in R d } and its relation to the classical quantity $$m_k(d)$$ m k ( d ) : the size of the largest k-distance set in $${{\mathbb {R}}}^d$$ R d . We obtain that $$M_k(d)=m_k(d)$$ M k ( d ) = m k ( d ) for $$k=2,3$$ k = 2 , 3 , as well as for any fixed k, provided that d is sufficiently large. The last result answers a question, proposed by Erdős, Makai, and Pach. We also address a closely related Turán-type problem, studied by Erdős, Makai, Pach, and Spencer in the 90s: given n points in $${{\mathbb {R}}}^d$$ R d , how many pairs of them form a distance that belongs to $$[t_1,t_1+1]\cup \cdots \cup [t_k,t_k+1]$$ [

We study the two-player communication problem of determining whether two vertices $x, y$ are nearby in a graph $G$, with the goal of determining the graph structures that allow the problem to be solved with a constant-cost randomized protocol. Equivalently, we consider the problem of assigning constant-size random labels (sketches) to the vertices of a graph, which allow adjacency, exact distance thresholds, or approximate distance thresholds to be computed with high probability from the labels. Our main results are that, for monotone classes of graphs: constant-size adjacency sketches exist if and only if the class has bounded arboricity; constant-size sketches for exact distance thresholds exist if and only if the class has bounded expansion; constant-size approximate distance threshold (ADT) sketches imply that the class has bounded expansion; any class of constant expansion (i.e. any proper minor closed class) has constant-size ADT sketches; and a class may have arbitrarily small expansion without admitting constant-size ADT sketches.

Suppose we are sending out k robots from 0 to search the real line at constant speed (with turns) to find a target at an unknown location; f of the robots are faulty, meaning that they fail to report the target although visiting its location (called crash type). The goal is to find the target in time at most $$\lambda |x|$$ , if the target is located at x, $$|x| \ge 1$$ , for $$\lambda $$ as small as possible. We show that this cannot be achieved for $$\begin{aligned}&\lambda < 2\frac{\rho ^\rho }{(\rho -1)^{\rho -1}}+1,~~ \rho := \frac{2(f+1)}{k}~, \end{aligned}$$ which is tight due to earlier work (see Czyzowitz et al. in Proc PODC’16, pp 405–414, 2016, where this problem was introduced). This also gives some better than previously known lower bounds for so-called Byzantine-type faulty robots that may actually wrongly report a target. In the second part of the paper we deal with the m-rays generalization of the problem, where the hidden target is to be detected on m rays all emanating at the same point. Using a generalization of our methods, along with a useful relaxation of the original problem, we establish a tight lower for this setting as well (as above, with $$\rho := \nicefrac {m(f+1)}{k}$$ ). When specialized to the case $$f=0$$ , this resolves the question on parallel search on m rays, posed by three groups of scientists some 15–30 years ago: by Baeza-Yates, Culberson, and Rawlins; by Kao, Ma, Sipser, and Yin; and by Bernstein, Finkelstein, and Zilberstein. The m-rays generalization is known to have connections to other, seemingly unrelated, problems, including hybrid algorithms for on-line problems, and so-called contract algorithms.

The VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: $k$-fold unions/intersections of half-spaces and the simplices set system. Among other implications, it settles an open question in machine learning that was first studied in the foundational paper of Blumer et al. (1989) as well as by Eisenstat and Angluin (2007) and Johnson (2008).

In this paper, we study zero-one laws for the Erdös--Rényi random graph model $G(n,p)$ in the case when $p = n^{-\alpha}$ for $\alpha>0$. For a given class $\mathcal{K}$ of logical sentences about graphs and a given function $p=p(n)$, we say that $G(n,p)$ obeys the zero-one law (w.r.t. the class $\mathcal{K}$) if each sentence $\varphi\in\mathcal{K}$ is either asymptotically almost surely (a.a.s.) true or a.a.s. false for $G(n,p)$. In this paper, we consider first order properties and monadic second order properties of bounded quantifier depth $k$, that is, the length of the longest chain of nested quantifiers in the formula expressing the property. We call zero-one laws for properties of quantifier depth $k$ the zero-one $k$-laws. The main results of this paper concern the zero-one $k$-laws for monadic second order (MSO) properties. We determine all values $\alpha>0$, for which the zero-one $3$-law for MSO properties does not hold. We also show that, in contrast to the case of the $3$-law, there are infinitely many values of $\alpha$ for which the zero-one $4$-law for MSO properties does not hold. To this end, we analyze the evolution of certain properties of $G(n,p)$ that may be of independent interest.

Following groundbreaking work by Haussler and Welzl (1987), the use of small epsilon-nets has become a standard technique for solving algorithmic and extremal problems in geometry and learning theory. Two significant recent developments are: (i) an upper bound on the size of the smallest epsilon-nets for set systems, as a function of their so-called shallow-cell complexity (Chan, Grant, Konemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in R^4 by a family of half-spaces such that the size of any epsilon-net for them is at least (1/(9*epsilon)) log (1/epsilon) (Pach and Tardos). The present paper completes both of these avenues of research. We (i) give a lower bound, matching the result of Chan et al., and (ii) generalize the construction of Pach and Tardos to half-spaces in R^d, for any d >= 4, to show that the general upper bound of Haussler and Welzl for the size of the smallest epsilon-nets is tight.

Retweet cascades play an essential role in information diffusion in Twitter. Popular tweets reflect the current trends in Twitter, while Twitter itself is one of the most important online media. Thus, understanding the reasons why a tweet becomes popular is of great interest for sociologists, marketers and social media researches. What is even more important is the possibility to make a prognosis of a tweet's future popularity. Besides the scientific significance of such possibility, this sort of prediction has lots of practical applications such as breaking news detection, viral marketing etc. In this paper we try to forecast how many retweets a given tweet will gain during a fixed time period. We train an algorithm that predicts the number of retweets during time T since the initial moment. In addition to a standard set of features we utilize several new ones. One of the most important features is the flow of the cascade. Another one is PageRank on the retweet graph, which can be considered as the measure of influence of users.