Source author record

Richard Beigel

Richard Beigel appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Formal Languages and Automata Theory

Catalog footprint

What is connected

3works

3topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

On the Sizes of DPDAs, PDAs, LBAs

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 are languages A such that there is a Linear Bounded Automata (Linear Space Turing Machine, henceforth LBA) that recognizes A which is much smaller than ny PDA that recognizes A. There are languages A such that both A and compliment(A) are recognizable by a PDA, but the PDA for A is much smaller than the PDA for compliment(A). There are languages A1, A2 such that A1,A2,A1 INTERSECT A_2 are recognizable by a PDA, but the PDA for A1 and A2 are much smaller than the PDA for A1 INTERSECT A2. We investigate these phenomenon and show that, in all these cases, the size difference is captured by a function whose Turing degree is on the second level of the arithmetic hierarchy. Our theorems lead to infinitely-often results. For example: for infinitely many $n$ there exists a language An recognized by a DPDA such that there is a small PDA for An, but any DPDA for An is large. We look at cases where we can get almost-all results, though with much smaller size differences.

preprint2011arXiv

A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes $a_1,..., a_n$ in $(0,1]$. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized $O({n(\log n)(\log\log n)\over \sum_{i=1}^n a_i}+({1\over ε})^{O({1\overε})})$ time $(1+ε)$-approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs $Ω({n\over \sum_{i=1}^n a_i})$ time to give an $(1+ε)$-approximation. For each function $s(n): N\rightarrow N$, define $\sum(s(n))$ to be the set of all bin packing problems with the sum of item sizes equal to $s(n)$. For a constant $b\in (0,1)$, every problem in $\sum(n^{b})$ has an $O(n^{1-b}(\log n)(\log\log n)+({1\over ε})^{O({1\overε})})$ time $(1+ε)$-approximation for an arbitrary constant $ε$. On the other hand, there is no $o(n^{1-b})$ time $(1+ε)$-approximation scheme for the bin packing problems in $\sum(n^{b})$ for some constant $ε>0$.

preprint2000arXiv

3-Coloring in Time O(1.3289^n)

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 (CSP) formulation of these problems. 3-SAT is equivalent to (2,3)-CSP while the other problems above are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the time bounds for solving the other problems listed above. Our techniques involve a mixture of Davis-Putnam-style backtracking with more sophisticated matching and network flow based ideas.