Zobrazeno 1 - 10
of 189
pro vyhledávání: '"Tikhomirov, Konstantin"'
A seminal result of Lee asserts that the Ramsey number of any bipartite $d$-degenerate graph $H$ satisfies $\log r(H) = \log n + O(d)$. In particular, this bound applies to every bipartite graph of maximal degree $\Delta$. It remains a compelling cha
Externí odkaz:
http://arxiv.org/abs/2410.18223
A seminal open question of Pisier and Mendel--Naor asks whether every degree-regular graph which satisfies the classical discrete Poincar\'e inequality for scalar functions, also satisfies an analogous inequality for functions taking values in \texti
Externí odkaz:
http://arxiv.org/abs/2410.04394
We propose an algorithm of approximating the optimal objective value of a two-stage stochastic program under an assumption of {\it approximate rotational invariance} of the technology matrix, and compare the method with the L-shaped decomposition.
Externí odkaz:
http://arxiv.org/abs/2407.21215
We consider the problem of maximizing $\langle c,x \rangle$ subject to the constraints $Ax \leq \mathbf{1}$, where $x\in{\mathbb R}^n$, $A$ is an $m\times n$ matrix with mutually independent centered subgaussian entries of unit variance, and $c$ is a
Externí odkaz:
http://arxiv.org/abs/2401.17530
Determining the capacity $\alpha_c$ of the Binary Perceptron is a long-standing problem. Krauth and Mezard (1989) conjectured an explicit value of $\alpha_c$, approximately equal to .833, and a rigorous lower bound matching this prediction was recent
Externí odkaz:
http://arxiv.org/abs/2401.15092
Sharp conditions for the presence of spectral outliers are well understood for Wigner random matrices with iid entries. In the setting of inhomogeneous symmetric random matrices (i.e., matrices with a non-trivial variance profile), the corresponding
Externí odkaz:
http://arxiv.org/abs/2401.07852
Autor:
Tikhomirov, Konstantin
Let $A$ be an $n\times n$ matrix with mutually independent centered Gaussian entries. Define \begin{align*} \sigma^*:=\max\limits_{i,j\leq n}\sqrt{{\mathbb E}\,|A_{i,j}|^2}, \quad \sigma:=\max\bigg(\max\limits_{j\leq n}\sqrt{{\mathbb E}\,\|{\rm col}_
Externí odkaz:
http://arxiv.org/abs/2307.08211
Autor:
Tikhomirov, Konstantin
We show that for every $K\geq 1$ there is $c>0$ depending only on $K$ with the following property. Let $n>d\geq 1$, and let $X_1,\dots,X_n$ be independent random vectors with i.i.d components having a (possibly discrete) symmetric distribution of uni
Externí odkaz:
http://arxiv.org/abs/2304.13133
For reversible Markov chains on finite state spaces, we show that the modified log-Sobolev inequality (MLSI) can be upgraded to a log-Sobolev inequality (LSI) at the surprisingly low cost of degrading the associated constant by $\log (1/p)$, where $p
Externí odkaz:
http://arxiv.org/abs/2212.06028
Autor:
Tikhomirov, Konstantin
The size-Ramsey number $\hat r(G')$ of a graph $G'$ is defined as the smallest integer $m$ so that there exists a graph $G$ with $m$ edges such that every $2$-coloring of the edges of $G$ contains a monochromatic copy of $G'$. Answering a question of
Externí odkaz:
http://arxiv.org/abs/2210.05818