Zobrazeno 1 - 10
of 323
pro vyhledávání: '"Gasarch, William"'
Autor:
Fortnow, Lance, Gasarch, William
Let G be a context-free grammar (CFG) in Chomsky normal form. We take the number of rules in G to be the size of G. We also assume all CFGs are in Chomsky normal form. We consider the question of, given a string w of length n, what is the smallest CF
Externí odkaz:
http://arxiv.org/abs/2405.20026
Autor:
Gasarch, William, Peng, Gary
We present an exposition of the proof of the induced bipartite Ramsey Theorem.
Externí odkaz:
http://arxiv.org/abs/2401.04922
Autor:
Canakci, Burcu, Christenson, Hannah, Fleischman, Robert, Gasarch, William, McNabb, Nicole, Smolyak, Daniel
We created and parallelized two SAT solvers to find new bounds on some Ramsey-type numbers. For $c > 0$, let $R_c(L)$ be the least $n$ such that for all $c$-colorings of the $[n]\times [n]$ lattice grid there will exist a monochromatic right isoscele
Externí odkaz:
http://arxiv.org/abs/2312.01159
Ramsey's theorem states that for all finite colorings of an infinite set, there exists an infinite homogeneous subset. What if we seek a homogeneous subset that is also order-equivalent to the original set? Let $S$ be a linearly ordered set and $a \i
Externí odkaz:
http://arxiv.org/abs/2305.07192
Autor:
Gasarch, William
Alpoge and Granville (separately) gave novel proofs that the primes are infinite that use Ramsey Theory. In particular, they use Van der Waerden's Theorem and some number theory. We prove the primes are infinite using an easier theorem from Ramsey Th
Externí odkaz:
http://arxiv.org/abs/2302.04755
With Moore's law coming to a close it is useful to look at other forms of computer hardware. In this paper we survey what is known about several modes of computation: Neuromorphic, Custom Logic, Quantum, Optical, Spintronics, Reversible, Many-Valued
Externí odkaz:
http://arxiv.org/abs/2111.08916
Autor:
Li, Zongxia, Gasarch, William
One of the most significant challenges on cryptography today is the problem of factoring large integers since there are no algorithms that can factor in polynomial time, and factoring large numbers more than some limits(200 digits) remain difficult.
Externí odkaz:
http://arxiv.org/abs/2111.02967
Autor:
Gasarch, William
Hilbert's 10th problem, stated in modern terms, is: Find an algorithm that will, given $p \in \mathbb{Z}[x_1,\ldots,x_n]$ determine if there exists $a_1, a_2, \ldots, a_n \in \mathbb{Z}$ such that $p(a_1,\ldots,a_n)=0$. Davis, Putnam, Robinson, and M
Externí odkaz:
http://arxiv.org/abs/2104.07220
Autor:
Chen, Douglas, Gasarch, William
Let A be a finite subset of the naturals and let n be a natural. Let NIM(A;n) be the two player game in which players alternate removing $a\in A$ stones from a pile with $n$ stones; the first player who cannot move loses. This game has been researche
Externí odkaz:
http://arxiv.org/abs/1911.00642
Autor:
Gasarch, William, Ulrich, Douglas
Erd\"{o}s proved that for every infinite $X \subseteq \mathbb{R}^d$ there is $Y \subseteq X$ with $|Y|=|X|$, such that all pairs of points from $Y$ have distinct distances, and he gave partial results for general $a$-ary volume. In this paper, we sea
Externí odkaz:
http://arxiv.org/abs/1807.06654