Zobrazeno 1 - 10
of 158
pro vyhledávání: '"BLAIS, ERIC"'
Autor:
Blais, Eric, Seth, Cameron
The graph and hypergraph container methods are powerful tools with a wide range of applications across combinatorics. Recently, Blais and Seth (FOCS 2023) showed that the graph container method is particularly well-suited for the analysis of the natu
Externí odkaz:
http://arxiv.org/abs/2403.18777
Autor:
Blais, Eric, Seth, Cameron
We establish nearly optimal sample complexity bounds for testing the $\rho$-clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs on $n$ vertices that have a $\rho n$-clique from graphs for which at
Externí odkaz:
http://arxiv.org/abs/2308.03289
We study the problems of testing and learning high-dimensional discrete convex sets. The simplest high-dimensional discrete domain where convexity is a non-trivial property is the ternary hypercube, $\{-1,0,1\}^n$. The goal of this work is to underst
Externí odkaz:
http://arxiv.org/abs/2305.03194
Autor:
BEN-DAVID, SHALEV1 shalev.b@uwaterloo.ca, BLAIS, ERIC1 eric.blais@uwaterloo.ca
Publikováno v:
Journal of the ACM. Dec2023, Vol. 70 Issue 6, p1-58. 58p.
We prove two results about randomised query complexity $\mathrm{R}(f)$. First, we introduce a "linearised" complexity measure $\mathrm{LR}$ and show that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g) \geq \Omega(\mathrm{R}(
Externí odkaz:
http://arxiv.org/abs/2208.12896
We consider the problem of determining which classes of functions can be tested more efficiently than they can be learned, in the distribution-free sample-based model that corresponds to the standard PAC learning setting. Our main result shows that w
Externí odkaz:
http://arxiv.org/abs/2012.03923
Autor:
Ben-David, Shalev, Blais, Eric
The celebrated minimax principle of Yao (1977) says that for any Boolean-valued function $f$ with finite domain, there is a distribution $\mu$ over the domain of $f$ such that computing $f$ to error $\epsilon$ against inputs from $\mu$ is just as har
Externí odkaz:
http://arxiv.org/abs/2002.10802
Autor:
Ben-David, Shalev, Blais, Eric
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $R(f\circ g)\ll R(f) R(g)$
Externí odkaz:
http://arxiv.org/abs/2002.10809
Recent beyond worst-case optimal join algorithms Minesweeper and its generalization Tetris have brought the theory of indexing and join processing together by developing a geometric framework for joins. These algorithms take as input an index $\mathc
Externí odkaz:
http://arxiv.org/abs/1909.12102
We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the non-adaptive convexity tester on the line. We re-prove the upper bound $
Externí odkaz:
http://arxiv.org/abs/1908.02525