156 citations · 159 across the 4 of their papers we have counts for
4 papers
On the Sizes of DPDAs, PDAs, LBAs
Richard Beigel, William Gasarch
There are languages A such that there is a Pushdown Automata (PDA) that recognizes A which is much smaller than any Deterministic Pushdown Automata (DPDA) that recognizes A. There…
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing
Richard Beigel, Bin Fu
The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes in . Using uniform sampling, which selects a rand…
Square-Difference-Free Sets of Size Omega(n^{0.7334...})
Richard Beigel, William Gasarch
A set A is square-difference free (henceforth SDF) if there do not exist x,y\in A, x\ne y, such that |x-y| is a square. Let sdf(n) be the size of the largest SDF subset of {1,...,n…
3-Coloring in Time O(1.3289^n)
Richard Beigel, David Eppstein
We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a constraint satisfaction…