Arrow Research search

Author name cluster

Richard Beigel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

26 papers
2 author rows

Possible papers

26

TCS Journal 2016 Journal Article

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 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 any PDA that recognizes A. There are languages A such that both A and A ‾ are recognizable by a PDA, but the PDA for A is much smaller than the PDA for A ‾. There are languages A 1, A 2 such that A 1, A 2, A 1 ∩ A 2 are recognizable by a PDA, but the PDA for A 1 and A 2 are much smaller than the PDA for A 1 ∩ A 2. We investigate these phenomena 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-many-n results. For example: for-infinitely-many-n there exists a language A n recognized by a DPDA such that there is a small PDA for A n, but any DPDA for A n is very large. We look at cases where we can get all-but-a-finite-number-of-n results, though with much smaller size differences.

Details DOI

MFCS Conference 2006 Conference Paper

The Multiparty Communication Complexity of Exact- T: Improved Bounds and New Problems

  • Richard Beigel
  • William I. Gasarch
  • James Glenn

Abstract Let x i, .. ., x k be n -bit numbers and T ∈ ℕ. Assume that P 1, .. ., P k are players such that P i knows all of the numbers exceptx i. They want to determine if \(\sum^{k}_{j=1}{\it x}_{j}\) = T by broadcasting as few bits as possible. In [7] an upper bound of \(O(\sqrt n )\) bits was obtained for the k =3 case, and a lower bound of ω (1) for k ≥3 when T =Θ(2 n ). We obtain (1) for k ≥3 an upper bound of \(k+O((n+\log k)^{1/(\lfloor{\rm lg(2k-2)}\rfloor)})\), (2) for k =3, T =Θ(2 n ), a lower bound of Ω(loglog n ), (3) a generalization of the protocol to abelian groups, (4) lower bounds on the multiparty communication complexity of some regular languages, and (5) empirical results for k = 3.

Details

TCS Journal 2004 Journal Article

Algorithms for four variants of the exact satisfiability problem

  • Vilhelm Dahllöf
  • Peter Jonsson
  • Richard Beigel

We present four polynomial space and exponential time algorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1. 1120 n ) (where n is the number of variables) time algorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1. 1907 n ) time algorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1. 1193 n ) and O(1. 2299 n ) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1. 1487 n ) time algorithm. We also present an O(1. 2190 n ) time algorithm for the general problem of counting the number of models for EXACT SATISFIABILITY; presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix.

Details DOI

I&C Journal 2003 Journal Article

Some connections between bounded query classes and non-uniform complexity

  • Amihood Amir
  • Richard Beigel
  • William Gasarch

Let A(x) be the characteristic function of A. Consider the function C A k (x 1, …, x k )=A(x 1)⋯A(x k ). We show that if C A k can be computed in polynomial time with fewer than k queries to some set X then A∈P/poly. A generalization of this result has applications to bounded query classes, circuits, and enumerability. In particular we obtain the following. (1) Assuming Σ3 p ≠Π3 p, there are functions computable using f(n)+1 queries to SAT that are not computable using f(n) queries to SAT, for f(n)=O(logn). (2) If C A k, restricted to length n inputs, can be computed by an unbounded fanin oracle circuit of size s(n) and depth d(n), with k−1 queries to some set X, then A can be computed with an unbounded fanin (non-oracle) circuit of size n O(k) s(n) and depth d(n)+O(1). (3) Assuming that PH≠Σ4 p ∩Π4 p, and ϵ<1, #SAT is not 2 n ϵ -enumerable.

Details DOI

FOCS Conference 2002 Conference Paper

Learning a Hidden Matching

  • Noga Alon
  • Richard Beigel
  • Simon Kasif
  • Steven Rudich
  • Benny Sudakov

We consider the problem of learning a matching (i. e. , a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a ( 1/2 +o(1))(n/2) upper bound and a nearly matching 0. 32(n/2) lower bound for the minimum possible number of queries. In contrast, if we allow randomness then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

Details

I&C Journal 2002 Journal Article

Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph

  • Richard Beigel
  • Lane A. Hemaspaandra
  • Harald Hempel
  • Jörg Vogel

Consider the problem of computing a function given only an oracle for its graph. For this problem, we present optimal trade-offs between serial and parallel queries. In particular, we give a function for which parallel access to its own graph is exponentially more expensive than sequential access.

Details DOI

I&C Journal 2001 Journal Article

Commutative Queries

  • Richard Beigel
  • Richard Chang

We consider polynomial-time Turing machines that have access to two oracles and investigate when the order of oracle queries is significant. The oracles used here are complete languages for the Polynomial Hierarchy (PH). We prove that, for solving decision problems, the order of oracle queries does not matter. This improves upon the previous result of E. Hemaspaandra, L. A. Hemaspaandra, and H. Hempel (1998, J. Universal Computer Sci. 4, 574–588), who showed that the order of the queries does not matter if the base machine asks only one query to each oracle. On the other hand, we prove that, for computing functions, the order of oracle queries does matter, unless PH collapses.

Details DOI

TCS Journal 1998 Journal Article

Addition in log2n + O(1) steps on average a simple analysis

  • Richard Beigel
  • Bill Gasarch
  • Ming Li
  • Louxin Zhang

We demonstrate the use of Kolmogorov complexity in average case analysis of algorithms through a classical example: adding two n-bit numbers in [log 2 n] + 2 steps on average. We simplify the analysis of Burks et al. (1961) and (in more complete forms) Briley (1973) and Schay (1995).

Details DOI

TCS Journal 1996 Journal Article

Frequency computation and bounded queries

  • Richard Beigel
  • William Gasarch
  • Efim Kinber

There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: F a A (x 1, …, x a ) = A(x 1)…A(x a ). We are interested in the complexity (in terms of the number of queries) of approximating F a A. Let b ⩽ a and let f be any function such that F a A (x 1, …, x a ) and f(x 1, …, x a ) agree on at least b bits. For a general set A we have matching upper and lower bounds on f that depend on coding theory. These are applied to get exact bounds for the case where A is semirecursive, A is superterse, and (assuming P ≠ NP) A = SAT. We obtain exact bounds when A is the halting problem using different methods.

Details DOI

MFCS Conference 1996 Conference Paper

On the Query Complexity of Sets

  • Richard Beigel
  • William I. Gasarch
  • Martin Kummer
  • Timothy H. McNicholl
  • Frank Stephan 0001

Abstract There has been much research over the last eleven years that considers the number of queries needed to compute a function as a measure of its complexity. We are interested in the complexity of certain sets in this context. We study the sets ODD A n ={(x 1, .. ., x n )∶¦ A ∩ { x 1, .. ., x n }¦ is odd} and WMOD( m ) A n ={( x 1, .. ., x n )∶¦ A ∩ { x 1, .. ., x n }¦≢0 (mod m )}. If A=K or A is semirecursive, we obtain tight bounds on the query complexity of ODD A n and WMOD( m ) A n. We obtain lower bounds for A r. e. The lower bounds for A r. e. are derived from the lower bounds for A semirecursive. We obtain that every tt-degree has a set A such that ODD A requires n n parallel queries to A, and a set B such that ODD B n can be decided with one query to B. Hence for bounded-query complexity, how information is packaged is more important than Turing degree. We investigate when extra queries add power. We show that, for several nonrecursive sets A, the more queries you can ask, the more sets you can decide; however, there are sets for which more queries do not help at all.

Details

FOCS Conference 1995 Conference Paper

3-Coloring in Time O(1. 3446 n ): A No-MIS Algorithm

  • Richard Beigel
  • David Eppstein

We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2, 3)-SSS while the other problems above are special cases of (3, 2)-SSS; there is also a natural duality transformation from (a, b)-SSS to (b, a)-SSS. We give a fast algorithm for (3, 2)-SSS and use it to improve the time bounds for solving the other problems listed above.

Details

FOCS Conference 1995 Conference Paper

Fault Diagnosis in a Flash

  • Richard Beigel
  • William Hurwood
  • Nabil Kahalé

Consider a set of n processors that can communicate with each other. Assume that each processor can be either "good" or "faulty". Also assume that the processors can test each other. We consider how to use parallel testing rounds to identify the faulty processors, given an upper bound t on their number. We prove that 4 rounds are necessary and sufficient when 2/spl radic/(2n)/spl les/0. 03n (for n sufficiently large). Furthermore, at least 5 rounds are necessary when t/spl ges/0. 49n (for n sufficiently large), and 10 rounds are sufficient when t<0. 5n (for all n). (It is well known that no general solution is possible when t/spl ges/0. 5n).

Details

TCS Journal 1992 Journal Article

Counting classes: thresholds, parity, mods, and fewness

  • Richard Beigel
  • John Gill

Counting classes consist of languages defined in terms of the number of accepting computations of nondeterministic polynomial-time Turing machines. Well-known examples of counting classes are NP, co-NP, ⊕ P, and PP. Every counting class is a subset of P#P[1], the class of languages computable in polynomial time using a single call to an oracle capable of determining the number of accepting paths of an NP machine. Using closure properties of #P, we systematically develop a complexity theory for counting classes defined in terms of thresholds and moduli. An unexpected result is that MOD ki P = MOD k P for prime k. Finally, we improve a result of Cai and Hemachandra (1990) by showing that recognizing languages in the class Few is as easy as distinguishing uniquely satisfiable formulas from unsatisfiable formulas (or detecting unique solutions, as in Valiant and Vazirani (1986)).

Details DOI

TCS Journal 1991 Journal Article

Bounded queries to SAT and the Boolean hierarchy

  • Richard Beigel

We study the complexity of decision problems that can be solved by a polynomial-time Turing machine that makes a bounded number of queries to an NP oracle. Depending on whether we allow some queries to depend on the results of other queries, we obtain two (probably) different hierarchies. We present several results relating the bounded NP query hierarchies to each other and to the Boolean hierarchy. We also consider the similarly defined hierarchies of functions that can be computed by a polynomial-time Turing machine that makes a bounded number of queries to an NP oracle. We present relations among these two hierarchies and the Boolean hierarchy. In particular we show for all k that there are functions computable with 2 k parallel queries to an NP set that are not computable in polynomial time with k serial queries to any oracle, unless P = NP. As a corollary k + 1 parallel queries to an NP set allow us to compute more functions than are computable with only k parallel queries to an NP set, unless P = NP; the same is true of serial queries. Similar results hold for all tt-self-reducible sets. Using a “mind-change” technique, we show that 2 k - 1 parallel queries to an NP set allow us to accept in polynomial time exactly the same sets as can be accepted in polynomial time with k serial queries to an NP set. (In fact, the same is true for any class in place of NP that is closed under polynomial-time positive-bounded-truth-table reductions.) This contrasts with the expected result for function computations with an NP oracle (Beigel, 1988). In addition we show that the Boolean hierarchy and the bounded query hierarchies (of languages) either stand or collapse together. Finally we show that if the Boolean hierarchy collapses to any level but the zeroth (deterministic polynomial time), then for all k there are functions computable in polynomial time with k parallel queries to an NP set that are not computable in polynomial time with k - 1 serial queries to any set (NP-complete sets are p-superterse).

Details DOI

FOCS Conference 1991 Conference Paper

Languages that Are Easier than their Proofs

  • Richard Beigel
  • Mihir Bellare
  • Joan Feigenbaum
  • Shafi Goldwasser

Languages in NP are presented for which it is harder to prove membership interactively than it is to decide this membership. Similarly, languages where checking is harder than computing membership are presented. Under assumptions about triple-exponential time, incoherent sets in NP are constructed. Without any assumptions, incoherent sets are constructed in DSPACE (n to the log n), yielding the first uncheckable and non-random-self-reducible sets in that space. >

Details

FOCS Conference 1991 Conference Paper

On ACC

  • Richard Beigel
  • Jun Tarui

It has been shown by A. Yao (1990) that every language in ACC is recognized by a sequence of depth-2 probabilistic circuits with a symmetric gate at the root and n/sup polylog/(n) AND gates of fan-in polylog (n) at the leaves. The authors simplify Yao's proof and strengthen his results: every language in ACC is recognized by a sequence of depth-2 deterministic circuits with a symmetric gate at the root and n/sup polylog/(n) AND gates of fan-in polylog(n) at the leaves. They also analyze and improve modulus-amplifying polynomials constructed by S. Toda (1989) and Yao: this yields smaller circuits in Yao's and the present results on ACC. >

Details

TCS Journal 1990 Journal Article

Bi-immunity results for cheatable sets

  • Richard Beigel

An oracle A is k-cheatable if there is a polynomial-time algorithm to determine the answers to 2k parallel queries to A from the answers to only k queries to some other oracle B. It is known that 1-cheatable sets cannot be bi-immune for P. In contrast, we construct 2-cheatable sets that are bi-immune for arbitrary time complexity classes. In addition, for each k, we construct a set that is (k + 1)-cheatable, but not k-cheatable; we show that this separation does not hold with bi-immunity. We show that if a recursive set A is bi-immune for P then there exists a nontrivial 1-cheatable set that is polynomial-time m-reducible to A. Consequently if NP contains a set that is bi-immune for P then NP contains a set that is not polynomial-time Turing-equivalent to a self-reducible set.

Details DOI
v2026.09.13