Zobrazeno 1 - 10
of 55
pro vyhledávání: '"Williams, R. Ryan"'
Autor:
Sacolick, Davidson A., Williams, R. Ryan, Wu, Samuel J., Kraeutler, Matthew J., McCulloch, Patrick C.
Publikováno v:
In Journal of Shoulder and Elbow Surgery December 2024 33(12):2766-2779
We consider low-space algorithms for the classic Element Distinctness problem: given an array of $n$ input integers with $O(\log n)$ bit-length, decide whether or not all elements are pairwise distinct. Beame, Clifford, and Machmouchi [FOCS 2013] gav
Externí odkaz:
http://arxiv.org/abs/2111.01759
A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the $\mathsf{SAT}$ problem and related problems within the polynomial-time hierarchy. For example, for the $\mathsf{SAT}$ problem, the state-of-the-a
Externí odkaz:
http://arxiv.org/abs/2012.00330
The best known size lower bounds against unrestricted circuits have remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds o
Externí odkaz:
http://arxiv.org/abs/1811.04828
Autor:
Williams, R. Ryan
We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over $\mathbb{R}$) of functions from some "simple" class ${\cal C}$. In particular, given ${\cal C}$ we are interested in finding low-complexity functi
Externí odkaz:
http://arxiv.org/abs/1802.09121
Given a set of numbers, the $k$-SUM problem asks for a subset of $k$ numbers that sums to zero. When the numbers are integers, the time and space complexity of $k$-SUM is generally studied in the word-RAM model; when the numbers are reals, the comple
Externí odkaz:
http://arxiv.org/abs/1605.07285
Autor:
Vyas, Nikhil1 (AUTHOR) vyasnikhil96@gmail.com, Williams, R. Ryan1 (AUTHOR)
Publikováno v:
Theory of Computing Systems. Feb2023, Vol. 67 Issue 1, p149-177. 29p.
Publikováno v:
Journal of the ACM. Sep2018, Vol. 65 Issue 5, p1-38. 38p.
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Chapman, Brynmor, Williams, R. Ryan
What is the power of constant-depth circuits with MOD_m gates, that can count modulo m? Can they efficiently compute MAJORITY and other symmetric functions? When m is a constant prime power, the answer is well understood. In this regime, Razborov and
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::357fe28622b132e2a23c078f2f599b01