Search the dblp DataBase
Richard Beigel :
[Publications ]
[Author Rank by year ]
[Co-authors ]
[Prefers ]
[Cites ]
[Cited by ]
Publications of Author
Sreerama K. Murthy , Simon Kasif , Steven Salzberg , Richard Beigel OC1: A Randomized Induction of Oblique Decision Trees. [Citation Graph (1, 0)][DBLP ] AAAI, 1993, pp:322-327 [Conf ] Richard Beigel On the Relativized Power of Additional Accepting Paths. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1989, pp:216-224 [Conf ] Richard Beigel Perceptrons, PP, and the Polynomial Hierarchy. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1992, pp:14-19 [Conf ] Richard Beigel The Polynomial Method in Circuit Complexity. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1993, pp:82-95 [Conf ] Richard Beigel Gaps in Bounded Query Hierarchies. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 1999, pp:124-141 [Conf ] Richard Beigel , Lance Fortnow Are Cook and Karp Ever the Same? [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 2003, pp:333-336 [Conf ] Richard Beigel , Bin Fu Circuits Over PP and PL. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 1997, pp:24-35 [Conf ] Richard Beigel , Bin Fu Solving Intractable Problems with DNA Computing. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 1998, pp:154-0 [Conf ] Richard Beigel , Judy Goldsmith Downward separation fails catastrophically for limited nondeterminism classes. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1994, pp:134-138 [Conf ] Richard Beigel , William I. Gasarch , Efim B. Kinber Frequency Computation and Bounded Queries. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1995, pp:125-132 [Conf ] Richard Beigel , Lane A. Hemachandra , Gerd Wechsung On the Power of Probabilistic Polynomial Time: PNP[log] subseteq PP. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1989, pp:225-227 [Conf ] Richard Beigel , Martin Kummer , Frank Stephan Approximable Sets. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1994, pp:12-23 [Conf ] Richard Beigel , Alexis Maciel Upper and Lower Bounds for Some Depth-3 Circuit Classes. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 1997, pp:149-157 [Conf ] Richard Beigel , Alexis Maciel Circuit Lower Bounds Collapse Relativized Complexity Classes. [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 1999, pp:222-226 [Conf ] Richard Beigel , Nick Reingold , Daniel A. Spielman The Perceptron Strikes Back. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1991, pp:286-291 [Conf ] Richard Beigel , Howard Straubing The Power of Local Self-Reductions. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1995, pp:277-285 [Conf ] Noga Alon , Richard Beigel Lower Bounds for Approximations by Low Degree Polynomials Over Zm . [Citation Graph (0, 0)][DBLP ] IEEE Conference on Computational Complexity, 2001, pp:184-187 [Conf ] Amihood Amir , Richard Beigel , William I. Gasarch Some Connections Between Bounded Query Classes and Non-Uniform Complexity. [Citation Graph (0, 0)][DBLP ] Structure in Complexity Theory Conference, 1990, pp:232-243 [Conf ] Noga Alon , Richard Beigel , Simon Kasif , Steven Rudich , Benny Sudakov Learning a Hidden Matching. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:197-0 [Conf ] Richard Beigel , Mihir Bellare , Joan Feigenbaum , Shafi Goldwasser Languages that Are Easier than their Proofs [Citation Graph (0, 0)][DBLP ] FOCS, 1991, pp:19-28 [Conf ] Richard Beigel , David Eppstein 3-Coloring in Time O(1.3446n ): A No-MIS Algorithm. [Citation Graph (0, 0)][DBLP ] FOCS, 1995, pp:444-452 [Conf ] Richard Beigel , William Hurwood , Nabil Kahale Fault Diagnosis in a Flash. [Citation Graph (0, 0)][DBLP ] FOCS, 1995, pp:571-580 [Conf ] Richard Beigel , Jun Tarui On ACC [Citation Graph (0, 0)][DBLP ] FOCS, 1991, pp:783-792 [Conf ] Manindra Agrawal , Richard Beigel , Thomas Thierauf Pinpointing Computation with Modular Queries in the Boolean Hierarchy. [Citation Graph (0, 0)][DBLP ] FSTTCS, 1996, pp:322-334 [Conf ] Richard Beigel , Bin Fu Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. [Citation Graph (0, 0)][DBLP ] ICALP, 1997, pp:816-826 [Conf ] Egemen Tanin , Richard Beigel , Ben Shneiderman Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. [Citation Graph (0, 0)][DBLP ] INFOVIS, 1997, pp:81-86 [Conf ] Richard Beigel , Lance Fortnow , Frank Stephan Infinitely-Often Autoreducible Sets. [Citation Graph (0, 0)][DBLP ] ISAAC, 2003, pp:98-107 [Conf ] Richard Beigel , Jun Tarui , Seinosuke Toda On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. [Citation Graph (0, 0)][DBLP ] ISAAC, 1992, pp:420-429 [Conf ] Bin Fu , Richard Beigel Diagnosis in the Presence of Intermittent Faults. [Citation Graph (0, 0)][DBLP ] ISAAC, 2004, pp:427-441 [Conf ] Richard Beigel Closure Properties of GapP and #P. [Citation Graph (0, 0)][DBLP ] ISTCS, 1997, pp:144-146 [Conf ] Richard Beigel , Richard Chang Commutative Queries. [Citation Graph (0, 0)][DBLP ] ISTCS, 1997, pp:159-165 [Conf ] Bin Fu , Richard Beigel A Comparison of Resource-Bounded Molecular Computation Models. [Citation Graph (0, 0)][DBLP ] ISTCS, 1997, pp:6-11 [Conf ] Richard Beigel , Egemen Tanin The Geometry of Browsing. [Citation Graph (0, 0)][DBLP ] LATIN, 1998, pp:331-340 [Conf ] Richard Beigel , Martin Kummer , Frank Stephan Quantifying the Amount of Verboseness. [Citation Graph (0, 0)][DBLP ] LFCS, 1992, pp:21-32 [Conf ] Richard Beigel , William I. Gasarch , James Glenn The Multiparty Communication Complexity of Exact-T : Improved Bounds and New Problems. [Citation Graph (0, 0)][DBLP ] MFCS, 2006, pp:146-156 [Conf ] Richard Beigel , William I. Gasarch , Martin Kummer , Timothy McNicholl , Frank Stephan On the Query Complexity of Sets. [Citation Graph (0, 0)][DBLP ] MFCS, 1996, pp:206-217 [Conf ] Richard Beigel , Noga Alon , Simon Kasif , Mehmet Serkan Apaydin , Lance Fortnow An optimal procedure for gap closing in whole genome shotgun sequencing. [Citation Graph (0, 0)][DBLP ] RECOMB, 2001, pp:22-30 [Conf ] Richard Beigel Finding Maximum Independent Sets in Sparse and General Graphs. [Citation Graph (0, 0)][DBLP ] SODA, 1999, pp:856-857 [Conf ] Ming Gu , Martin Farach , Richard Beigel An Efficient Algorithm for Dynamic Text Indexing. [Citation Graph (0, 0)][DBLP ] SODA, 1994, pp:697-704 [Conf ] Richard Beigel , S. Rao Kosaraju , Gregory F. Sullivan Locating Faults in a Constant Number of Parallel Testing Rounds. [Citation Graph (0, 0)][DBLP ] SPAA, 1989, pp:189-198 [Conf ] Richard Beigel , Grigorii Margulis , Daniel A. Spielman Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds. [Citation Graph (0, 0)][DBLP ] SPAA, 1993, pp:21-29 [Conf ] Richard Beigel , John Gill , Ulrich Hertrampf Counting Classes: Thresholds, Parity, Mods, and Fewness. [Citation Graph (0, 0)][DBLP ] STACS, 1990, pp:49-57 [Conf ] Vikraman Arvind , Richard Beigel , Antoni Lozano The Complexity of Modular Graph Automorphism. [Citation Graph (0, 0)][DBLP ] STACS, 1998, pp:172-182 [Conf ] Eric Allender , Richard Beigel , Ulrich Hertrampf , Steven Homer A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. [Citation Graph (0, 0)][DBLP ] STACS, 1990, pp:1-11 [Conf ] James Aspnes , Richard Beigel , Merrick L. Furst , Steven Rudich The Expressive Power of Voting Polynomials [Citation Graph (0, 0)][DBLP ] STOC, 1991, pp:402-409 [Conf ] David A. Mix Barrington , Richard Beigel , Steven Rudich Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) [Citation Graph (0, 0)][DBLP ] STOC, 1992, pp:455-461 [Conf ] Richard Beigel When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One [Citation Graph (0, 0)][DBLP ] STOC, 1992, pp:450-454 [Conf ] Richard Beigel , Harry Buhrman , Lance Fortnow NP Might Not Be As Easy As Detecting Unique Solutions. [Citation Graph (0, 0)][DBLP ] STOC, 1998, pp:203-208 [Conf ] Richard Beigel , Tirza Hirst One Help Bit Doesn't Help. [Citation Graph (0, 0)][DBLP ] STOC, 1998, pp:124-130 [Conf ] Richard Beigel , Nick Reingold , Daniel A. Spielman PP Is Closed Under Intersection (Extended Abstract) [Citation Graph (0, 0)][DBLP ] STOC, 1991, pp:1-9 [Conf ] Bin Fu , Richard Beigel A Comparison of Resource-Bounded Molecular Computation Models. [Citation Graph (0, 0)][DBLP ] Algorithmica, 1999, v:24, n:2, pp:87-95 [Journal ] Richard Beigel , Bin Fu Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. [Citation Graph (0, 0)][DBLP ] Algorithmica, 1999, v:25, n:2-3, pp:222-238 [Journal ] Richard Beigel , William I. Gasarch On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case. [Citation Graph (0, 0)][DBLP ] Ann. Pure Appl. Logic, 1989, v:45, n:1, pp:1-38 [Journal ] Richard Beigel , William I. Gasarch On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case. [Citation Graph (0, 0)][DBLP ] Ann. Pure Appl. Logic, 1989, v:45, n:3, pp:227-246 [Journal ] Richard Beigel , William I. Gasarch , James C. Owings Nondeterministic Bounded Query Reducibilities. [Citation Graph (0, 0)][DBLP ] Ann. Pure Appl. Logic, 1989, v:41, n:2, pp:107-118 [Journal ] David A. Mix Barrington , Richard Beigel , Steven Rudich Representing Boolean Functions as Polynomials Modulo Composite Numbers. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 1994, v:4, n:, pp:367-382 [Journal ] Richard Beigel When do Extra Majority Gates Help? Polylog(N ) Majority Gates Are Equivalent to One. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 1994, v:4, n:, pp:314-324 [Journal ] Richard Beigel Perceptrons, PP, and the Polynomial Hierarchy. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 1994, v:4, n:, pp:339-349 [Journal ] Richard Beigel , Joan Feigenbaum On Being Incoherent Without Being Very Hard. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 1992, v:2, n:, pp:1-17 [Journal ] Richard Beigel , Lance Fortnow , William I. Gasarch A tight lower bound for restricted pir protocols. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 2006, v:15, n:1, pp:82-91 [Journal ] Richard Beigel , Alexis Maciel Upper and Lower Bounds for Some Depth-3 Circuit Classes. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 1997, v:6, n:3, pp:235-255 [Journal ] Richard Beigel , Jun Tarui On ACC. [Citation Graph (0, 0)][DBLP ] Computational Complexity, 1994, v:4, n:, pp:350-366 [Journal ] James Aspnes , Richard Beigel , Merrick L. Furst , Steven Rudich The Expressive Power of Voting Polynomials. [Citation Graph (0, 0)][DBLP ] Combinatorica, 1994, v:14, n:2, pp:135-148 [Journal ] Richard Beigel , David Eppstein 3-Coloring in Time O(1.3289^n) [Citation Graph (0, 0)][DBLP ] CoRR, 2000, v:0, n:, pp:- [Journal ] Amihood Amir , Richard Beigel , William I. Gasarch Some Connections between Bounded Query Classes and Non-Uniform Complexity [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:24, pp:- [Journal ] Richard Beigel , Lance Fortnow , William I. Gasarch A Nearly Tight Bound for Private Information Retrieval Protocols [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 2003, v:, n:087, pp:- [Journal ] 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 [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:015, pp:- [Journal ] Richard Beigel , William Hurwood , Nabil Kahale Fault Diagnosis in a Flash [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 1994, v:1, n:11, pp:- [Journal ] Richard Beigel Closure Properties of GapP and #P [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:35, pp:- [Journal ] Richard Beigel , William I. GasarchEfim B. Kinber Frequency Computation and Bounded Queries [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:36, pp:- [Journal ] Richard Beigel , William I. Gasarch , Ming Li , Louxin Zhang Addition in log2 n + O(1) Steps on Average: A Simple Analysis [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 1996, v:3, n:51, pp:- [Journal ] Richard Beigel , Alexis Maciel Upper and Lower Bounds for Some Depth-3 Circuit Classes [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 1997, v:4, n:2, pp:- [Journal ] Richard Beigel Gaps in Bounded Query Hierarchies [Citation Graph (0, 0)][DBLP ] Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:26, pp:- [Journal ] Amihood Amir , Richard Beigel , William I. Gasarch Some connections between bounded query classes and non-uniform complexity. [Citation Graph (0, 0)][DBLP ] Inf. Comput., 2003, v:186, n:1, pp:104-139 [Journal ] Richard Beigel , Richard Chang Commutative Queries. [Citation Graph (0, 0)][DBLP ] Inf. Comput., 2001, v:166, n:1, pp:71-91 [Journal ] Richard Beigel , William I. Gasarch , John Gill , James C. Owings Terse, Superterse, and Verbose Sets [Citation Graph (0, 0)][DBLP ] Inf. Comput., 1993, v:103, n:1, pp:68-85 [Journal ] Richard Beigel , Lane A. Hemaspaandra , Harald Hempel , Jörg Vogel Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph. [Citation Graph (0, 0)][DBLP ] Inf. Comput., 2002, v:173, n:2, pp:123-131 [Journal ] Richard Beigel , Martin Kummer , Frank Stephan Quantifying the Amount of Verboseness [Citation Graph (0, 0)][DBLP ] Inf. Comput., 1995, v:118, n:1, pp:73-90 [Journal ] Richard Beigel , Martin Kummer , Frank Stephan Approximable Sets [Citation Graph (0, 0)][DBLP ] Inf. Comput., 1995, v:120, n:2, pp:304-314 [Journal ] Richard Beigel , Anna Bernasconi A Note on the Polynomial Representation of Boolean Functions over GF(2). [Citation Graph (0, 0)][DBLP ] Int. J. Found. Comput. Sci., 1999, v:10, n:4, pp:535-0 [Journal ] Richard Beigel , Lane A. Hemachandra , Gerd Wechsung Probabilistic Polynomial Time is Closed under Parity Reductions. [Citation Graph (0, 0)][DBLP ] Inf. Process. Lett., 1991, v:37, n:2, pp:91-94 [Journal ] Richard Beigel , David Eppstein 3-coloring in time O(1.3289n ). [Citation Graph (0, 0)][DBLP ] J. Algorithms, 2005, v:54, n:2, pp:168-204 [Journal ] Richard Beigel Relativized Counting Classes: Relations among Thresholds, Parity, and Mods. [Citation Graph (0, 0)][DBLP ] J. Comput. Syst. Sci., 1991, v:42, n:1, pp:76-96 [Journal ] Richard Beigel , Bin Fu Circuits over PP and PL. [Citation Graph (0, 0)][DBLP ] J. Comput. Syst. Sci., 2000, v:60, n:2, pp:422-441 [Journal ] Richard Beigel , Nick Reingold , Daniel A. Spielman PP Is Closed under Intersection. [Citation Graph (0, 0)][DBLP ] J. Comput. Syst. Sci., 1995, v:50, n:2, pp:191-202 [Journal ] Richard Beigel , William I. Gasarch , Martin Kummer , Georgia Martin , Timothy McNicholl , Frank Stephan The Comlexity of OddA n . [Citation Graph (0, 0)][DBLP ] J. Symb. Log., 2000, v:65, n:1, pp:1-18 [Journal ] Richard Beigel , Richard Chang , Mitsunori Ogiwara A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies. [Citation Graph (0, 0)][DBLP ] Mathematical Systems Theory, 1993, v:26, n:3, pp:293-310 [Journal ] Noga Alon , Richard Beigel , Simon Kasif , Steven Rudich , Benny Sudakov Learning a Hidden Matching. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 2004, v:33, n:2, pp:487-501 [Journal ] Vikraman Arvind , Richard Beigel , Antoni Lozano The Complexity of Modular Graph Automorphism. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 2000, v:30, n:4, pp:1299-1320 [Journal ] Richard Beigel Unbounded Searching Slgorithms. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 1990, v:19, n:3, pp:522-537 [Journal ] Richard Beigel , Judy Goldsmith Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 1998, v:27, n:5, pp:1420-1429 [Journal ] Richard Beigel , Lance Fortnow , Frank Stephan Infinitely-Often Autoreducible Sets. [Citation Graph (0, 0)][DBLP ] SIAM J. Comput., 2006, v:36, n:3, pp:595-608 [Journal ] Egemen Tanin , Richard Beigel , Ben Shneiderman Incremental data Structures and Algorithms for Dynamic Query Interfaces. [Citation Graph (0, 0)][DBLP ] SIGMOD Record, 1996, v:25, n:4, pp:21-24 [Journal ] Richard Beigel , John Gill Sorting n Objects with a K-Sorter. [Citation Graph (0, 0)][DBLP ] IEEE Trans. Computers, 1990, v:39, n:5, pp:714-716 [Journal ] Eric Allender , Richard Beigel , Ulrich Hertrampf , Steven Homer Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. [Citation Graph (0, 0)][DBLP ] Theor. Comput. Sci., 1993, v:115, n:2, pp:225-241 [Journal ] Richard Beigel Bi-Immunity Results for Cheatable Sets. [Citation Graph (0, 0)][DBLP ] Theor. Comput. Sci., 1990, v:73, n:3, pp:249-263 [Journal ] Richard Beigel Bounded Queries to SAT and the Boolean Hierarchy. [Citation Graph (0, 0)][DBLP ] Theor. Comput. Sci., 1991, v:84, n:2, pp:199-223 [Journal ] Richard Beigel , John Gill Counting Classes: Thresholds, Parity, Mods, and Fewness. [Citation Graph (0, 0)][DBLP ] Theor. Comput. Sci., 1992, v:103, n:1, pp:3-23 [Journal ] Richard Beigel , William I. Gasarch , Efim B. Kinber Frequency Computation and Bounded Queries. [Citation Graph (0, 0)][DBLP ] Theor. Comput. Sci., 1996, v:163, n:1&2, pp:177-192 [Journal ] Richard Beigel , William I. Gasarch , Ming Li , Louxin Zhang Addition in log2 n + O(1) Steps on Average: A Simple Analysis. [Citation Graph (0, 0)][DBLP ] Theor. Comput. Sci., 1998, v:191, n:1-2, pp:245-248 [Journal ] Vilhelm Dahllöf , Peter Jonsson , Richard Beigel Algorithms for four variants of the exact satisfiability problem. [Citation Graph (0, 0)][DBLP ] Theor. Comput. Sci., 2004, v:320, n:2-3, pp:373-394 [Journal ] A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing [Citation Graph (, )][DBLP ] The Mapmaker's dilemma. [Citation Graph (, )][DBLP ] Search in 0.008secs, Finished in 0.016secs