most citedLower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance

1 citations · 1 across the 3 of their papers we have counts for

collaborators
Showing cs.FLShow all

1 paper · 1 filter

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…