Zobrazeno 1 - 10
of 83
pro vyhledávání: '"Zadik, Ilias"'
Over the last years, there has been a significant amount of work studying the power of specific classes of computationally efficient estimators for multiple statistical parametric estimation tasks, including the estimators classes of low-degree polyn
Externí odkaz:
http://arxiv.org/abs/2408.00746
We study the computational limits of the following general hypothesis testing problem. Let H=H_n be an \emph{arbitrary} undirected graph on n vertices. We study the detection task between a ``null'' Erd\H{o}s-R\'{e}nyi random graph G(n,p) and a ``pla
Externí odkaz:
http://arxiv.org/abs/2403.17766
We study the fundamental problem of transfer learning where a learning algorithm collects data from some source distribution $P$ but needs to perform well with respect to a different target distribution $Q$. A standard change of measure argument impl
Externí odkaz:
http://arxiv.org/abs/2403.11963
We show that sharp thresholds for Boolean functions directly imply average-case circuit lower bounds. More formally we show that any Boolean function exhibiting a sharp enough threshold at \emph{arbitrary} critical density cannot be computed by Boole
Externí odkaz:
http://arxiv.org/abs/2311.04204
A major question in the study of the Erd\H{o}s--R\'enyi random graph is to understand the probability that it contains a given subgraph. This study originated in classical work of Erd\H{o}s and R\'enyi (1960). More recent work studies this question b
Externí odkaz:
http://arxiv.org/abs/2302.14830
This note concerns a well-known result which we term the ``spread lemma,'' which establishes the existence (with high probability) of a desired structure in a random set. The spread lemma was central to two recent celebrated results: (a) the improved
Externí odkaz:
http://arxiv.org/abs/2209.11347
For any given graph $H$, we are interested in $p_\mathrm{crit}(H)$, the minimal $p$ such that the Erd\H{o}s-R\'enyi graph $G(n,p)$ contains a copy of $H$ with probability at least $1/2$. Kahn and Kalai (2007) conjectured that $p_\mathrm{crit}(H)$ is
Externí odkaz:
http://arxiv.org/abs/2209.03326
The last few years have seen a surge of work on high dimensional statistics under privacy constraints, mostly following two main lines of work: the ``worst case'' line, which does not make any distributional assumptions on the input data; and the ``s
Externí odkaz:
http://arxiv.org/abs/2208.07438
We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease within a population of size n, based on the outcomes of pooled tests which return positive whenever there is at least one infecte
Externí odkaz:
http://arxiv.org/abs/2206.07640
Autor:
Bandeira, Afonso S., Alaoui, Ahmed El, Hopkins, Samuel B., Schramm, Tselil, Wein, Alexander S., Zadik, Ilias
Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for such hardness, including lower bounds against restricted models of compu
Externí odkaz:
http://arxiv.org/abs/2205.09727