BZPEER

preprint2023arXiv

Online Learning of Smooth Functions

In this paper, we study the online learning of real-valued functions where the hidden function is known to have certain smoothness properties. Specifically, for $q \ge 1$ , let $\mathcal F_q$ be the class of absolutely continuous functions $f: [0,1] \to \mathbb R$ such that $\|f'\|_q \le 1$ . For $q \ge 1$ and $d \in \mathbb Z^+$ , let $\mathcal F_{q,d}$ be the class of functions $f: [0,1]^d \to \mathbb R$ such that any function $g: [0,1] \to \mathbb R$ formed by fixing all but one parameter of $f$ is in $\mathcal F_q$ . For any class of real-valued functions $\mathcal F$ and $p>0$ , let $\text{opt}_p(\mathcal F)$ be the best upper bound on the sum of $p^{\text{th}}$ powers of absolute prediction errors that a learner can guarantee in the worst case. In the single-variable setup, we find new bounds for $\text{opt}_p(\mathcal F_q)$ that are sharp up to a constant factor. We show for all $\varepsilon \in (0, 1)$ that $\text{opt}_{1+\varepsilon}(\mathcal{F}_{\infty}) = Θ(\varepsilon^{-\frac{1}{2}})$ and $\text{opt}_{1+\varepsilon}(\mathcal{F}_q) = Θ(\varepsilon^{-\frac{1}{2}})$ for all $q \ge 2$ . We also show for $\varepsilon \in (0,1)$ that $\text{opt}_2(\mathcal F_{1+\varepsilon})=Θ(\varepsilon^{-1})$ . In addition, we obtain new exact results by proving that $\text{opt}_p(\mathcal F_q)=1$ for $q \in (1,2)$ and $p \ge 2+\frac{1}{q-1}$ . In the multi-variable setup, we establish inequalities relating $\text{opt}_p(\mathcal F_{q,d})$ to $\text{opt}_p(\mathcal F_q)$ and show that $\text{opt}_p(\mathcal F_{\infty,d})$ is infinite when $p<d$ and finite when $p>d$ . We also obtain sharp bounds on learning $\mathcal F_{\infty,d}$ for $p < d$ when the number of trials is bounded.

preprint2021arXiv

A note on the price of bandit feedback for mistake-bounded online learning

The standard model and the bandit model are two generalizations of the mistake-bound model to online multiclass classification. In both models the learner guesses a classification in each round, but in the standard model the learner recieves the correct classification after each guess, while in the bandit model the learner is only told whether or not their guess is correct in each round. For any set $F$ of multiclass classifiers, define $opt_{std}(F)$ and $opt_{bandit}(F)$ to be the optimal worst-case number of prediction mistakes in the standard and bandit models respectively. Long (Theoretical Computer Science, 2020) claimed that for all $M > 2$ and infinitely many $k$ , there exists a set $F$ of functions from a set $X$ to a set $Y$ of size $k$ such that $opt_{std}(F) = M$ and $opt_{bandit}(F) \ge (1 - o(1))(|Y|\ln{|Y|})opt_{std}(F)$ . The proof of this result depended on the following lemma, which is false e.g. for all prime $p \ge 5$ , $s = \mathbf{1}$ (the all $1$ vector), $t = \mathbf{2}$ (the all $2$ vector), and all $z$ . Lemma: Fix $n \ge 2$ and prime $p$ , and let $u$ be chosen uniformly at random from $\left\{0, \dots, p-1\right\}^n$ . For any $s, t \in \left\{1, \dots, p-1\right\}^n$ with $s \neq t$ and for any $z \in \left\{0, \dots, p-1\right\}$ , we have $\Pr(t \cdot u = z \mod p \text{ } | \text{ } s \cdot u = z \mod p) = \frac{1}{p}$ . We show that this lemma is false precisely when $s$ and $t$ are multiples of each other mod $p$ . Then using a new lemma, we fix Long's proof.

preprint2020arXiv

A generalization of the Kővári-Sós-Turán theorem

We present a new proof of the Kővári-Sós-Turán theorem that $ex(n, K_{s,t}) = O(n^{2-1/t})$ for $s, t \geq 2$ . The new proof is elementary, avoiding the use of convexity. For any $d$ -uniform hypergraph $H$ , let $ex_d(n,H)$ be the maximum possible number of edges in an $H$ -free $d$ -uniform hypergraph on $n$ vertices. Let $K_{H, t}$ be the $(d+1)$ -uniform hypergraph obtained from $H$ by adding $t$ new vertices $v_1, \dots, v_t$ and replacing every edge $e$ in $E(H)$ with $t$ edges $e \cup \left\{v_1\right\},\dots, e \cup \left\{v_t\right\}$ in $E(K_{H, t})$ . If $H$ is the $1$ -uniform hypergraph on $s$ vertices with $s$ edges, then $K_{H, t} = K_{s, t}$ . We prove that $ex_{d+1}(n,K_{H,t}) = O(ex_d(n, H)^{1/t} n^{d+1-d/t} + t n^d)$ for any $d$ -uniform hypergraph $H$ with at least two edges such that $ex_d(n, H) = o(n^d)$ . Thus $ex_{d+1}(n,K_{H,t}) = O(n^{d+1-1/t})$ for any $d$ -uniform hypergraph $H$ with at least two edges such that $ex_d(n, H) = O(n^{d-1})$ , which implies the Kővári-Sós-Turán theorem in the $d = 1$ case. This also implies that $ex_{d+1}(n, K_{H,t}) = O(n^{d+1-1/t})$ when $H$ is a $d$ -uniform hypergraph with at least two edges in which all edges are pairwise disjoint, which generalizes an upper bound proved by Mubayi and Verstraëte (JCTA, 2004). We also obtain analogous bounds for 0-1 matrix Turán problems.

preprint2020arXiv

Broadcast Dimension of Graphs

In this paper we initiate the study of broadcast dimension, a variant of metric dimension. Let $G$ be a graph with vertex set $V(G)$ , and let $d(u,w)$ denote the length of a $u-w$ geodesic in $G$ . For $k \ge 1$ , let $d_k(x,y)=\min \{d(x,y), k+1\}$ . A function $f: V(G) \rightarrow \mathbb{Z}^+ \cup \{0\}$ is called a resolving broadcast of $G$ if, for any distinct $x,y \in V(G)$ , there exists a vertex $z \in V(G)$ such that $f(z)=i>0$ and $d_{i}(x,z) \neq d_{i}(y,z)$ . The broadcast dimension, $bdim(G)$ , of $G$ is the minimum of $c_f(G)=\sum_{v \in V(G)} f(v)$ over all resolving broadcasts of $G$ , where $c_f(G)$ can be viewed as the total cost of the transmitters (of various strength) used in resolving the entire network described by the graph $G$ . Note that $bdim(G)$ reduces to $adim(G)$ (the adjacency dimension of $G$ , introduced by Jannesari and Omoomi in 2012) if the codomain of resolving broadcasts is restricted to $\{0,1\}$ . We determine its value for cycles, paths, and other families of graphs. We prove that $bdim(G) = Ω(\log{n})$ for all graphs $G$ of order $n$ , and that the result is sharp up to a constant factor. We show that $\frac{adim(G)}{bdim(G)}$ and $\frac{bdim(G)}{dim(G)}$ can both be arbitrarily large, where $dim(G)$ denotes the metric dimension of $G$ . We also examine the effect of vertex deletion on the adjacency dimension and the broadcast dimension of graphs.

preprint2020arXiv

Constructing sparse Davenport-Schinzel sequences

For any sequence $u$ , the extremal function $Ex(u, j, n)$ is the maximum possible length of a $j$ -sparse sequence with $n$ distinct letters that avoids $u$ . We prove that if $u$ is an alternating sequence $a b a b \dots$ of length $s$ , then $Ex(u, j, n) = Θ(s n^{2})$ for all $j \geq 2$ and $s \geq n$ , answering a question of Wellman and Pettie [Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices, Disc. Math. 341 (2018), 1987--1993] and extending the result of Roselle and Stanton that $Ex(u, 2, n) = Θ(s n^2)$ for any alternation $u$ of length $s \geq n$ [Some properties of Davenport-Schinzel sequences, Acta Arithmetica 17 (1971), 355--362]. Wellman and Pettie also asked how large must $s(n)$ be for there to exist $n$ -block $DS(n, s(n))$ sequences of length $Ω(n^{2-o(1)})$ . We answer this question by showing that the maximum possible length of an $n$ -block $DS(n, s(n))$ sequence is $Ω(n^{2-o(1)})$ if and only if $s(n) = Ω(n^{1-o(1)})$ . We also show related results for extremal functions of forbidden 0-1 matrices with any constant number of rows and extremal functions of forbidden sequences with any constant number of distinct letters.

preprint2020arXiv

Extremal results for graphs of bounded metric dimension

Metric dimension is a graph parameter motivated by problems in robot navigation, drug design, and image processing. In this paper, we answer several open extremal problems on metric dimension and pattern avoidance in graphs from (Geneson, Metric dimension and pattern avoidance, Discrete Appl. Math. 284, 2020, 1-7). Specifically, we construct a new family of graphs that allows us to determine the maximum possible degree of a graph of metric dimension at most $k$ , the maximum possible degeneracy of a graph of metric dimension at most $k$ , the maximum possible chromatic number of a graph of metric dimension at most $k$ , and the maximum $n$ for which there exists a graph of metric dimension at most $k$ that contains $K_{n, n}$ . We also investigate a variant of metric dimension called edge metric dimension and solve another problem from the same paper for $n$ sufficiently large by showing that the edge metric dimension of $P_n^{d}$ is $d$ for $n \geq d^{d-1}$ . In addition, we use a probabilistic argument to make progress on another open problem from the same paper by showing that the maximum possible clique number of a graph of edge metric dimension at most $k$ is $2^{Θ(k)}$ . We also make progress on a problem from (N. Zubrilina, On the edge dimension of a graph, Discrete Math. 341, 2018, 2083-2088) by finding a family of new triples $(x, y, n)$ for which there exists a graph of metric dimension $x$ , edge metric dimension $y$ , and order $n$ . In particular, we show that for each integer $k > 0$ , there exist graphs $G$ with metric dimension $k$ , edge metric dimension $3^k(1-o(1))$ , and order $3^k(1+o(1))$ .

preprint2020arXiv

Metric dimension and pattern avoidance in graphs

In this paper, we prove a number of results about pattern avoidance in graphs with bounded metric dimension or edge metric dimension. We show that the maximum possible number of edges in a graph of diameter $D$ and edge metric dimension $k$ is at most $(\lfloor \frac{2D}{3}\rfloor +1)^{k}+k \sum_{i = 1}^{\lceil \frac{D}{3}\rceil } (2i)^{k-1}$ , sharpening the bound of $\binom{k}{2}+k D^{k-1}+D^{k}$ from Zubrilina (2018). We also show that the maximum value of $n$ for which some graph of metric dimension $\leq k$ contains the complete graph $K_{n}$ as a subgraph is $n = 2^{k}$ . We prove that the maximum value of $n$ for which some graph of metric dimension $\leq k$ contains the complete bipartite graph $K_{n,n}$ as a subgraph is $2^{Θ(k)}$ . Furthermore, we show that the maximum value of $n$ for which some graph of edge metric dimension $\leq k$ contains $K_{1,n}$ as a subgraph is $n = 2^{k}$ . We also show that the maximum value of $n$ for which some graph of metric dimension $\leq k$ contains $K_{1,n}$ as a subgraph is $3^{k}-O(k)$ . In addition, we prove that the $d$ -dimensional grids $\prod_{i = 1}^{d} P_{r_{i}}$ have edge metric dimension at most $d$ . This generalizes two results of Kelenc et al. (2016), that non-path grids have edge metric dimension $2$ and that $d$ -dimensional hypercubes have edge metric dimension at most $d$ . We also provide a characterization of $n$ -vertex graphs with edge metric dimension $n-2$ , answering a question of Zubrilina. As a result of this characterization, we prove that any connected $n$ -vertex graph $G$ such that $edim(G) = n-2$ has diameter at most $5$ . More generally, we prove that any connected $n$ -vertex graph with edge metric dimension $n-k$ has diameter at most $3k-1$ .

preprint2020arXiv

Reconfiguration graphs of zero forcing sets

This paper begins the study of reconfiguration of zero forcing sets, and more specifically, the zero forcing graph. Given a base graph $G$ , its zero forcing graph, $\mathscr{Z}(G)$ , is the graph whose vertices are the minimum zero forcing sets of $G$ with an edge between vertices $B$ and $B'$ of $\mathscr{Z}(G)$ if and only if $B$ can be obtained from $B'$ by changing a single vertex of $G$ . It is shown that the zero forcing graph of a forest is connected, but that many zero forcing graphs are disconnected. We characterize the base graphs whose zero forcing graphs are either a path or the complete graph, and show that the star cannot be a zero forcing graph. We show that computing $\mathscr{Z}(G)$ takes $2^{Θ(n)}$ operations in the worst case for a graph $G$ of order $n$ .

preprint2020arXiv

The damage throttling number of a graph

The cop throttling number of a graph, introduced in 2018 by Breen et al., optimizes the balance between the number of cops used and the number of rounds required to catch the robber in a game of Cops and Robbers. In 2019, Cox and Sanaei studied a variant of Cops and Robbers in which the robber tries to occupy (or damage) as many vertices as possible and the cop tries to minimize this damage. In their paper, they study the minimum number of vertices damaged by the robber over all games played on a given graph $G$ , called the damage number of $G$ . We introduce the natural parameter called the damage throttling number of a graph, denoted $\operatorname{th}_d(G)$ , which optimizes the balance between the number of cops used and the number of vertices damaged in the graph. To this end, we formalize the definition of $k$ -damage number, which extends the damage number to games played with $k$ cops. We show that damage throttling and cop throttling share many properties, yet they exhibit interesting differences. We prove that the damage throttling number is tightly bounded above by one less than the cop throttling number. Infinite families of examples and non-examples of tightness in this bound are given. We also find an infinite family of connected graphs $G$ of order $n$ for which $\operatorname{th}_d(G) = Ω(n^{2/3})$ .

preprint2016arXiv

Asymptotic bounds on renewal process stopping times

Suppose that i.i.d. random variables $X_{1}, X_{2}, \ldots$ are chosen uniformly from $[0,1]$ , and let $f: [0,1] \rightarrow [0,1]$ be an increasing bijection. Define $μ_{f}$ to be the expected value of $f(X_{i})$ for each $i$ . Define the random variable $K_{f}$ be to be minimal so that $\sum_{i = 1}^{K_{f}} f(X_{i}) > t$ and let $N_{f}(t)$ be the expected value of $K_{f}$ . We prove that if $c_{f} = \frac{\int_{0}^{1} \int_{f^{-1}(u)}^{1} (f(x)-u) dx du}{μ_{f}}$ , then $N_{f}(t) = \frac{t+c_{f}}{μ_{f}}+o(1)$ . This generalizes a result of Ćurgus and Jewett (2007) on the case $f(x) = x$ .

preprint2016arXiv

Bounding extremal functions of forbidden $0-1$ matrices using $(r,s)$ -formations

First, we prove tight bounds of $n 2^{\frac{1}{(t-2)!}α(n)^{t-2} \pm O(α(n)^{t-3})}$ on the extremal function of the forbidden pair of ordered sequences $(1 2 3 \ldots k)^t$ and $(k \ldots 3 2 1)^t$ using bounds on a class of sequences called $(r,s)$ -formations. Then, we show how an analogous method can be used to derive similar bounds on the extremal functions of forbidden pairs of $0-1$ matrices consisting of horizontal concatenations of identical identity matrices and their horizontal reflections.

preprint2016arXiv

Bounds for approximating lower envelopes with polynomials of degree at most $d$

Given a lower envelope in the form of an arbitrary sequence $u$ , let $LSP(u, d)$ denote the maximum length of any subsequence of $u$ that can be realized as the lower envelope of a set of polynomials of degree at most $d$ . Let $sp(m, d)$ denote the minimum value of $LSP(u, d)$ over all sequences $u$ of length $m$ . We derive bounds on $sp(m, d)$ using another extremal function for sequences. A sequence $u$ is called $v$ -free if no subsequence of $u$ is isomorphic to $v$ . Given sequences $u$ and v, let $LSS(u, v)$ denote the maximum length of a $v$ -free subsequence of $u$ . Let $ss(m, v)$ denote the minimum of $LSS(u, v)$ over all sequences $u$ of length $m$ . By bounding $ss(m, v)$ for alternating sequences $v$ , we prove quasilinear bounds in $m^{1/2}$ on $sp(m,d)$ for all $d > 0$ .

preprint2016arXiv

Distributed pursuit algorithms for probabilistic adversaries on connected graphs

A gambler moves between the vertices $1, \ldots, n$ of a graph using the probability distribution $p_{1}, \ldots, p_{n}$ . Multiple cops pursue the gambler on the graph, only being able to move between adjacent vertices. We investigate the expected capture time for the gambler against $k$ cops as a function of $n$ and $k$ for three versions of the game: (1) known gambler: the cops know the gambler's distribution (2) unknown gambler: the cops do not know the gambler's distribution (3) known changing gambler: the gambler's distribution can change every turn, but the cops know all of the gambler's distributions from the beginning. We show for $n > k$ that if the cops are allowed to choose their initial positions before the game starts and before they know the gambler's distribution(s), and if both the gambler and the cops play optimally, then the expected capture time is $Θ(n/k)$ for the known gambler, the unknown gambler, and the known changing gambler.

preprint2015arXiv

Improved lower bounds on extremal functions of multidimensional permutation matrices

A $d$ -dimensional zero-one matrix $A$ avoids another $d$ -dimensional zero-one matrix $P$ if no submatrix of $A$ can be transformed to $P$ by changing some ones to zeroes. Let $f(n,P,d)$ denote the maximum number of ones in a $d$ -dimensional $n \times \cdots \times n$ zero-one matrix that avoids $P$ . Fox proved for $n$ sufficiently large that $f(n, P, 2) = 2^{k^{Θ(1)}}n$ for almost all $k \times k$ permutation matrices $P$ . We extend this result by proving for $d \geq 2$ and $n$ sufficiently large that $f(n, P, d) = 2^{k^{Θ(1)}}n^{d-1}$ for almost all $d$ -dimensional permutation matrices $P$ of dimensions $k \times \cdots \times k$ .

preprint2015arXiv

Sequences of formation width $4$ and alternation length $5$

Sequence pattern avoidance is a central topic in combinatorics. A sequence $s$ contains a sequence $u$ if some subsequence of $s$ can be changed into $u$ by a one-to-one renaming of its letters. If $s$ does not contain $u$ , then $s$ avoids $u$ . A widely studied extremal function related to pattern avoidance is $Ex(u, n)$ , the maximum length of an $n$ -letter sequence that avoids $u$ and has every $r$ consecutive letters pairwise distinct, where $r$ is the number of distinct letters in $u$ . We bound $Ex(u, n)$ using the formation width function, $fw(u)$ , which is the minimum $s$ for which there exists $r$ such that any concatenation of $s$ permutations, each on the same $r$ letters, contains $u$ . In particular, we identify every sequence $u$ such that $fw(u)=4$ and $u$ contains $ababa$ . The significance of this result lies in its implication that, for every such sequence $u$ , we have $Ex(u, n) = Θ(n α(n))$ , where $α(n)$ denotes the incredibly slow-growing inverse Ackermann function. We have thus identified the extremal function of many infinite classes of previously unidentified sequences.

preprint2014arXiv

Improved bounds on maximum sets of letters in sequences with forbidden alternations

Let $A_{s,k}(m)$ be the maximum number of distinct letters in any sequence which can be partitioned into $m$ contiguous blocks of pairwise distinct letters, has at least $k$ occurrences of every letter, and has no subsequence forming an alternation of length $s$ . Nivasch (2010) proved that $A_{5, 2d+1}(m) = θ( m α_{d}(m))$ for all fixed $d \geq 2$ . We show that $A_{s+1, s}(m) = \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for all $s \geq 2$ , $A_{5, 6}(m) = θ(m \log \log m)$ , and $A_{5, 2d+2}(m) = θ(m α_{d}(m))$ for all fixed $d \geq 3$ .

preprint2014arXiv

Linear bounds on matrix extremal functions using visibility hypergraphs

The 0-1 matrix A contains a 0-1 matrix M if some submatrix of A can be transformed into M by changing some ones to zeroes. If A does not contain M, then A avoids M. Let ex(n,M) be the maximum number of ones in an n x n 0-1 matrix that avoids M, and let ex_k(m,M) be the maximum number of columns in a 0-1 matrix with m rows that avoids M and has at least k ones in every column. A method for bounding ex(n,M) by using bounds on the maximum number of edges in bar visibility graphs was introduced in (R. Fulek, Discrete Mathematics 309, 2009). By using a similar method with bar visibility hypergraphs, we obtain linear bounds on the extremal functions of other forbidden 0-1 matrices.

preprint2013arXiv

Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs

We examine semi-bar visibility graphs in the plane and on a cylinder in which sightlines can pass through k objects. We show every semi-bar k-visibility graph has a (k+2)-quasiplanar representation in the plane with vertices drawn as points in convex position and edges drawn as segments. We also show that the graphs having cylindrical semi-bar k-visibility representations with semi-bars of different lengths are the same as the (2k+2)-degenerate graphs having edge-maximal (k+2)-quasiplanar representations in the plane with vertices drawn as points in convex position and edges drawn as segments.

Jesse Geneson

Research overview

Is this your work?

18 publications

Online Learning of Smooth Functions

A note on the price of bandit feedback for mistake-bounded online learning

A generalization of the Kővári-Sós-Turán theorem

Broadcast Dimension of Graphs

Constructing sparse Davenport-Schinzel sequences

Extremal results for graphs of bounded metric dimension

Metric dimension and pattern avoidance in graphs

Reconfiguration graphs of zero forcing sets

The damage throttling number of a graph

Asymptotic bounds on renewal process stopping times

Bounding extremal functions of forbidden $0-1$ matrices using $(r,s)$ -formations

Bounds for approximating lower envelopes with polynomials of degree at most $d$

Distributed pursuit algorithms for probabilistic adversaries on connected graphs

Improved lower bounds on extremal functions of multidimensional permutation matrices

Sequences of formation width $4$ and alternation length $5$

Improved bounds on maximum sets of letters in sequences with forbidden alternations

Linear bounds on matrix extremal functions using visibility hypergraphs

Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs

See the researcher in context

Building this map preview

Jesse Geneson

Research overview

Is this your work?

18 publications

Online Learning of Smooth Functions

A note on the price of bandit feedback for mistake-bounded online learning

A generalization of the Kővári-Sós-Turán theorem

Broadcast Dimension of Graphs

Constructing sparse Davenport-Schinzel sequences

Extremal results for graphs of bounded metric dimension

Metric dimension and pattern avoidance in graphs

Reconfiguration graphs of zero forcing sets

The damage throttling number of a graph

Asymptotic bounds on renewal process stopping times

Bounding extremal functions of forbidden 0−10-10−1 matrices using (r,s)(r,s)(r,s)-formations

Bounds for approximating lower envelopes with polynomials of degree at most ddd

Distributed pursuit algorithms for probabilistic adversaries on connected graphs

Improved lower bounds on extremal functions of multidimensional permutation matrices

Sequences of formation width 444 and alternation length 555

Improved bounds on maximum sets of letters in sequences with forbidden alternations

Linear bounds on matrix extremal functions using visibility hypergraphs

Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs

See the researcher in context

Building this map preview

Bounding extremal functions of forbidden $0-1$ matrices using $(r,s)$ -formations

Bounds for approximating lower envelopes with polynomials of degree at most $d$

Sequences of formation width $4$ and alternation length $5$