1 citations · 1 across the 3 of their papers we have counts for
3 papers
cs.FL2024
The CFG Complexity of Singleton Sets
Lance Fortnow, William Gasarch
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…
math.CO2024
The Induced Bipartite Ramsey Theorem: An Exposition
William Gasarch, Gary Peng
We present an exposition of the proof of the induced bipartite Ramsey Theorem.
cs.CC2004★ 1 cited
Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
Andris Ambainis, William Gasarch, Aravind Srinavasan +1
Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic prot…