Richard Beigel

Richard Beigel, Bin Fu: A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. FAW-AAIM 2012: 172-181

Richard Beigel, Bin Fu: A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. Electronic Colloquium on Computational Complexity (ECCC) 18: 28 (2011)

Richard Beigel, Bin Fu: A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. CoRR abs/1007.1260 (2010)

Richard Beigel, Lance Fortnow, William I. Gasarch: A tight lower bound for restricted pir protocols. Computational Complexity 15(1): 82-91 (2006)

Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet: Enumerations of the Kolmogorov function. J. Symb. Log. 71(2): 501-528 (2006)

Richard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006)

Richard Beigel, William I. Gasarch, James Glenn: The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. MFCS 2006: 146-156

Richard Beigel, David Eppstein: 3-coloring in time O(1.3289ⁿ). J. Algorithms 54(2): 168-204 (2005)

Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. SIAM J. Comput. 33(2): 487-501 (2004)

Vilhelm Dahllöf, Peter Jonsson, Richard Beigel: Algorithms for four variants of the exact satisfiability problem. Theor. Comput. Sci. 320(2-3): 373-394 (2004)

Bin Fu, Richard Beigel: Diagnosis in the Presence of Intermittent Faults. ISAAC 2004: 427-441

Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet: Enumerations of the Kolmogorov Function. Electronic Colloquium on Computational Complexity (ECCC)(015) (2004)

Amihood Amir, Richard Beigel, William I. Gasarch: Some connections between bounded query classes and non-uniform complexity. Inf. Comput. 186(1): 104-139 (2003)

Richard Beigel, Lance Fortnow: Are Cook and Karp Ever the Same? IEEE Conference on Computational Complexity 2003: 333-336

Richard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. ISAAC 2003: 98-107

Richard Beigel, Lance Fortnow, William I. Gasarch: A Nearly Tight Bound for Private Information Retrieval Protocols. Electronic Colloquium on Computational Complexity (ECCC)(087) (2003)

Richard Beigel, Lane A. Hemaspaandra, Harald Hempel, Jörg Vogel: Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph. Inf. Comput. 173(2): 123-131 (2002)

Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. FOCS 2002: 197-

Richard Beigel, Richard Chang: Commutative Queries. Inf. Comput. 166(1): 71-91 (2001)

Noga Alon, Richard Beigel: Lower Bounds for Approximations by Low Degree Polynomials Over Z_m. IEEE Conference on Computational Complexity 2001: 184-187

Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow: An optimal procedure for gap closing in whole genome shotgun sequencing. RECOMB 2001: 22-30

Richard Beigel, Bin Fu: Circuits over PP and PL. J. Comput. Syst. Sci. 60(2): 422-441 (2000)

Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl, Frank Stephan: The Comlexity of Odd^A_n. J. Symb. Log. 65(1): 1-18 (2000)

Vikraman Arvind, Richard Beigel, Antoni Lozano: The Complexity of Modular Graph Automorphism. SIAM J. Comput. 30(4): 1299-1320 (2000)

Richard Beigel, David Eppstein: 3-Coloring in Time O(1.3289^n). CoRR cs.DS/0006046 (2000)

Amihood Amir, Richard Beigel, William I. Gasarch: Some Connections between Bounded Query Classes and Non-Uniform Complexity. Electronic Colloquium on Computational Complexity (ECCC) 7(24) (2000)

Bin Fu, Richard Beigel: A Comparison of Resource-Bounded Molecular Computation Models. Algorithmica 24(2): 87-95 (1999)

Richard Beigel, Bin Fu: Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. Algorithmica 25(2-3): 222-238 (1999)

Richard Beigel, Anna Bernasconi: A Note on the Polynomial Representation of Boolean Functions over GF(2). Int. J. Found. Comput. Sci. 10(4): 535- (1999)

Richard Beigel: Gaps in Bounded Query Hierarchies. IEEE Conference on Computational Complexity 1999: 124-141

Richard Beigel, Alexis Maciel: Circuit Lower Bounds Collapse Relativized Complexity Classes. IEEE Conference on Computational Complexity 1999: 222-226

Richard Beigel: Finding Maximum Independent Sets in Sparse and General Graphs. SODA 1999: 856-857

Richard Beigel, Judy Goldsmith: Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. SIAM J. Comput. 27(5): 1420-1429 (1998)

Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang: Addition in log₂n + O(1) Steps on Average: A Simple Analysis. Theor. Comput. Sci. 191(1-2): 245-248 (1998)

Richard Beigel, Bin Fu: Solving Intractable Problems with DNA Computing. IEEE Conference on Computational Complexity 1998: 154-

Richard Beigel, Egemen Tanin: The Geometry of Browsing. LATIN 1998: 331-340

Vikraman Arvind, Richard Beigel, Antoni Lozano: The Complexity of Modular Graph Automorphism. STACS 1998: 172-182

Richard Beigel, Tirza Hirst: One Help Bit Doesn't Help. STOC 1998: 124-130

Richard Beigel, Harry Buhrman, Lance Fortnow: NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208

Richard Beigel: Gaps in Bounded Query Hierarchies. Electronic Colloquium on Computational Complexity (ECCC) 5(26) (1998)

Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. Computational Complexity 6(3): 235-255 (1997)

Richard Beigel, Bin Fu: Circuits Over PP and PL. IEEE Conference on Computational Complexity 1997: 24-35

Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. IEEE Conference on Computational Complexity 1997: 149-157

Richard Beigel, Bin Fu: Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. ICALP 1997: 816-826

Egemen Tanin, Richard Beigel, Ben Shneiderman: Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. INFOVIS 1997: 81-86

Bin Fu, Richard Beigel: A Comparison of Resource-Bounded Molecular Computation Models. ISTCS 1997: 6-11

Richard Beigel: Closure Properties of GapP and #P. ISTCS 1997: 144-146

Richard Beigel, Richard Chang: Commutative Queries. ISTCS 1997: 159-165

Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. Electronic Colloquium on Computational Complexity (ECCC) 4(2) (1997)

Robert W. Floyd, Richard Beigel: Die Sprache der Maschinen. Informatik Lehrbuch-Reihe, International Thomson 1996, isbn 978-3-8266-0216-0, pp. I-XXVII, 1-652

Egemen Tanin, Richard Beigel, Ben Shneiderman: Incremental data Structures and Algorithms for Dynamic Query Interfaces. SIGMOD Record 25(4): 21-24 (1996)

Richard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries. Theor. Comput. Sci. 163(1&2): 177-192 (1996)

Manindra Agrawal, Richard Beigel, Thomas Thierauf: Pinpointing Computation with Modular Queries in the Boolean Hierarchy. FSTTCS 1996: 322-334

Richard Beigel, William I. Gasarch, Martin Kummer, Timothy McNicholl, Frank Stephan: On the Query Complexity of Sets. MFCS 1996: 206-217

Manindra Agrawal, Richard Beigel, Thomas Thierauf: Modulo Information from Nonadaptive Queries to NP. Electronic Colloquium on Computational Complexity (ECCC) 3(1) (1996)

Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang: Addition in log₂n + O(1) Steps on Average: A Simple Analysis. Electronic Colloquium on Computational Complexity (ECCC) 3(51) (1996)

Richard Beigel, Martin Kummer, Frank Stephan: Quantifying the Amount of Verboseness. Inf. Comput. 118(1): 73-90 (1995)

Richard Beigel, Martin Kummer, Frank Stephan: Approximable Sets. Inf. Comput. 120(2): 304-314 (1995)

Richard Beigel, Nick Reingold, Daniel A. Spielman: PP Is Closed under Intersection. J. Comput. Syst. Sci. 50(2): 191-202 (1995)

Richard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries. Structure in Complexity Theory Conference 1995: 125-132

Richard Beigel, Howard Straubing: The Power of Local Self-Reductions. Structure in Complexity Theory Conference 1995: 277-285

Richard Beigel, David Eppstein: 3-Coloring in Time O(1.3446ⁿ): A No-MIS Algorithm. FOCS 1995: 444-452

Richard Beigel, William Hurwood, Nabil Kahale: Fault Diagnosis in a Flash. FOCS 1995: 571-580

Richard Beigel, David Eppstein: 3-Coloring in time O(1.3446ⁿ): A no-MIS Algorithm. Electronic Colloquium on Computational Complexity (ECCC) 2(33) (1995)

Richard Beigel: Closure Properties of GapP and #P. Electronic Colloquium on Computational Complexity (ECCC) 2(35) (1995)

Richard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries. Electronic Colloquium on Computational Complexity (ECCC) 2(36) (1995)

Richard Beigel, Howard Straubing: The Power of Local Self-Reductions. Electronic Colloquium on Computational Complexity (ECCC) 2(37) (1995)

Richard Beigel: When do Extra Majority Gates Help? Polylog(N) Majority Gates Are Equivalent to One. Computational Complexity 4: 314-324 (1994)

Richard Beigel: Perceptrons, PP, and the Polynomial Hierarchy. Computational Complexity 4: 339-349 (1994)

Richard Beigel, Jun Tarui: On ACC. Computational Complexity 4: 350-366 (1994)

David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers. Computational Complexity 4: 367-382 (1994)

James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich: The Expressive Power of Voting Polynomials. Combinatorica 14(2): 135-148 (1994)

Richard Beigel, Martin Kummer, Frank Stephan: Approximable Sets. Structure in Complexity Theory Conference 1994: 12-23

Richard Beigel, Judy Goldsmith: Downward separation fails catastrophically for limited nondeterminism classes. Structure in Complexity Theory Conference 1994: 134-138

Ming Gu, Martin Farach, Richard Beigel: An Efficient Algorithm for Dynamic Text Indexing. SODA 1994: 697-704

Richard Beigel, William Hurwood, Nabil Kahale: Fault Diagnosis in a Flash. Electronic Colloquium on Computational Complexity (ECCC) 1(11) (1994)

Richard Beigel, William I. Gasarch, John Gill, James C. Owings: Terse, Superterse, and Verbose Sets. Inf. Comput. 103(1): 68-85 (1993)

Richard Beigel, Richard Chang, Mitsunori Ogiwara: A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies. Mathematical Systems Theory 26(3): 293-310 (1993)

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. 115(2): 225-241 (1993)

Sreerama K. Murthy, Simon Kasif, Steven Salzberg, Richard Beigel: OC1: A Randomized Induction of Oblique Decision Trees. AAAI 1993: 322-327

Richard Beigel: The Polynomial Method in Circuit Complexity. Structure in Complexity Theory Conference 1993: 82-95

Richard Beigel, Grigorii Margulis, Daniel A. Spielman: Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds. SPAA 1993: 21-29

Richard Beigel, Joan Feigenbaum: On Being Incoherent Without Being Very Hard. Computational Complexity 2: 1-17 (1992)

Richard Beigel, John Gill: Counting Classes: Thresholds, Parity, Mods, and Fewness. Theor. Comput. Sci. 103(1): 3-23 (1992)

Richard Beigel: Perceptrons, PP, and the Polynomial Hierarchy. Structure in Complexity Theory Conference 1992: 14-19

Richard Beigel, Jun Tarui, Seinosuke Toda: On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. ISAAC 1992: 420-429

Richard Beigel, Martin Kummer, Frank Stephan: Quantifying the Amount of Verboseness. LFCS 1992: 21-32

Richard Beigel: When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One. STOC 1992: 450-454

David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract). STOC 1992: 455-461

Richard Beigel, William I. Gasarch: The Mapmaker's dilemma. Discrete Applied Mathematics 34(1-3): 37-48 (1991)

Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: Probabilistic Polynomial Time is Closed under Parity Reductions. Inf. Process. Lett. 37(2): 91-94 (1991)

Richard Beigel: Relativized Counting Classes: Relations among Thresholds, Parity, and Mods. J. Comput. Syst. Sci. 42(1): 76-96 (1991)

Richard Beigel: Bounded Queries to SAT and the Boolean Hierarchy. Theor. Comput. Sci. 84(2): 199-223 (1991)

Richard Beigel, Nick Reingold, Daniel A. Spielman: The Perceptron Strikes Back. Structure in Complexity Theory Conference 1991: 286-291

Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser: Languages that Are Easier than their Proofs. FOCS 1991: 19-28

Richard Beigel, Jun Tarui: On ACC. FOCS 1991: 783-792

Richard Beigel, Nick Reingold, Daniel A. Spielman: PP Is Closed Under Intersection (Extended Abstract). STOC 1991: 1-9

James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich: The Expressive Power of Voting Polynomials. STOC 1991: 402-409

Richard Beigel: Unbounded Searching Slgorithms. SIAM J. Comput. 19(3): 522-537 (1990)

Richard Beigel, John Gill: Sorting n Objects with a K-Sorter. IEEE Trans. Computers 39(5): 714-716 (1990)

Richard Beigel: Bi-Immunity Results for Cheatable Sets. Theor. Comput. Sci. 73(3): 249-263 (1990)

Amihood Amir, Richard Beigel, William I. Gasarch: Some Connections Between Bounded Query Classes and Non-Uniform Complexity. Structure in Complexity Theory Conference 1990: 232-243

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS 1990: 1-11

Richard Beigel, John Gill, Ulrich Hertrampf: Counting Classes: Thresholds, Parity, Mods, and Fewness. STACS 1990: 49-57

Richard Beigel, William I. Gasarch, James C. Owings: Nondeterministic Bounded Query Reducibilities. Ann. Pure Appl. Logic 41(2): 107-118 (1989)

Richard Beigel, William I. Gasarch: On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case. Ann. Pure Appl. Logic 45(1): 1-38 (1989)

Richard Beigel, William I. Gasarch: On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case. Ann. Pure Appl. Logic 45(3): 227-246 (1989)

Richard Beigel: On the Relativized Power of Additional Accepting Paths. Structure in Complexity Theory Conference 1989: 216-224

Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: On the Power of Probabilistic Polynomial Time: P^NP[log] subseteq PP. Structure in Complexity Theory Conference 1989: 225-227

Richard Beigel, S. Rao Kosaraju, Gregory F. Sullivan: Locating Faults in a Constant Number of Parallel Testing Rounds. SPAA 1989: 189-198

Richard Beigel: A structural theorem that depends quantitatively on the complexity of SAT. Structure in Complexity Theory Conference 1987