default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRichard Beigel
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – 2019
- 2016
[j47]Richard Beigel, William I. Gasarch:
On the sizes of DPDAs, PDAs, LBAs. Theor. Comput. Sci. 638: 63-75 (2016)- 2015
- [i16]Richard Beigel, William I. Gasarch:
On the Sizes of DPDAs, PDAs, LBAs. CoRR abs/1503.08847 (2015) - 2014
- [c54]Richard Beigel, Jie Wu, Huanyang Zheng:
On optimal scheduling of multiple mobile chargers in wireless sensor networks. MSCC@MobiHoc 2014: 1-6 - 2012
- [c53]Richard Beigel, Bin Fu:
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. FAW-AAIM 2012: 172-181 - 2011
- [i15]Richard Beigel, Bin Fu:
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i14]Richard Beigel, Bin Fu:
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. CoRR abs/1007.1260 (2010)
2000 – 2009
- 2006
- [j46]Richard Beigel, Lance Fortnow, William I. Gasarch:
A tight lower bound for restricted pir protocols. Comput. Complex. 15(1): 82-91 (2006) - [j45]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) - [j44]Richard Beigel, Lance Fortnow, Frank Stephan:
Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006) - [c52]Richard Beigel, William I. Gasarch, James Glenn:
The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. MFCS 2006: 146-156 - 2005
- [j43]Richard Beigel, David Eppstein:
3-coloring in time O(1.3289n). J. Algorithms 54(2): 168-204 (2005) - 2004
- [j42]Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov:
Learning a Hidden Matching. SIAM J. Comput. 33(2): 487-501 (2004) - [j41]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) - [c51]Bin Fu, Richard Beigel:
Diagnosis in the Presence of Intermittent Faults. ISAAC 2004: 427-441 - [i13]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. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j40]Amihood Amir, Richard Beigel, William I. Gasarch:
Some connections between bounded query classes and non-uniform complexity. Inf. Comput. 186(1): 104-139 (2003) - [c50]Richard Beigel, Lance Fortnow:
Are Cook and Karp Ever the Same? CCC 2003: 333-336 - [c49]Richard Beigel, Lance Fortnow, Frank Stephan:
Infinitely-Often Autoreducible Sets. ISAAC 2003: 98-107 - [i12]Richard Beigel, Lance Fortnow, William I. Gasarch:
A Nearly Tight Bound for Private Information Retrieval Protocols. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j39]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) - [c48]Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov:
Learning a Hidden Matching. FOCS 2002: 197- - 2001
- [j38]Richard Beigel, Richard Chang:
Commutative Queries. Inf. Comput. 166(1): 71-91 (2001) - [c47]Noga Alon, Richard Beigel:
Lower Bounds for Approximations by Low Degree Polynomials Over Zm. CCC 2001: 184-187 - [c46]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 - 2000
- [j37]Richard Beigel, Bin Fu:
Circuits over PP and PL. J. Comput. Syst. Sci. 60(2): 422-441 (2000) - [j36]Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy H. McNicholl, Frank Stephan:
The Comlexity of OddAn. J. Symb. Log. 65(1): 1-18 (2000) - [j35]Vikraman Arvind, Richard Beigel, Antoni Lozano:
The Complexity of Modular Graph Automorphism. SIAM J. Comput. 30(4): 1299-1320 (2000) - [i11]Richard Beigel, David Eppstein:
3-Coloring in Time O(1.3289^n). CoRR cs.DS/0006046 (2000) - [i10]Amihood Amir, Richard Beigel, William I. Gasarch:
Some Connections between Bounded Query Classes and Non-Uniform Complexity. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j34]Bin Fu, Richard Beigel:
A Comparison of Resource-Bounded Molecular Computation Models. Algorithmica 24(2): 87-95 (1999) - [j33]Richard Beigel, Bin Fu:
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. Algorithmica 25(2-3): 222-238 (1999) - [j32]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) - [c45]Richard Beigel:
Gaps in Bounded Query Hierarchies. CCC 1999: 124-141 - [c44]Richard Beigel, Alexis Maciel:
Circuit Lower Bounds Collapse Relativized Complexity Classes. CCC 1999: 222-226 - [c43]Richard Beigel:
Finding Maximum Independent Sets in Sparse and General Graphs. SODA 1999: 856-857 - 1998
- [j31]Richard Beigel, Judy Goldsmith:
Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. SIAM J. Comput. 27(5): 1420-1429 (1998) - [j30]Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang:
Addition in log2n + O(1) Steps on Average: A Simple Analysis. Theor. Comput. Sci. 191(1-2): 245-248 (1998) - [c42]Richard Beigel, Bin Fu:
Solving Intractable Problems with DNA Computing. CCC 1998: 154- - [c41]Richard Beigel, Egemen Tanin:
The Geometry of Browsing. LATIN 1998: 331-340 - [c40]Vikraman Arvind, Richard Beigel, Antoni Lozano:
The Complexity of Modular Graph Automorphism. STACS 1998: 172-182 - [c39]Richard Beigel, Tirza Hirst:
One Help Bit Doesn't Help. STOC 1998: 124-130 - [c38]Richard Beigel, Harry Buhrman, Lance Fortnow:
NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208 - [i9]Richard Beigel:
Gaps in Bounded Query Hierarchies. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j29]Richard Beigel, Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes. Comput. Complex. 6(3): 235-255 (1997) - [c37]Richard Beigel, Bin Fu:
Circuits Over PP and PL. CCC 1997: 24-35 - [c36]Richard Beigel, Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes. CCC 1997: 149-157 - [c35]Bin Fu, Richard Beigel:
On molecular approximation algorithms for NP optimization problem. DNA Based Computers 1997: 207-216 - [c34]Richard Beigel, Bin Fu:
Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. ICALP 1997: 816-826 - [c33]Egemen Tanin, Richard Beigel, Ben Shneiderman:
Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. INFOVIS 1997: 81-86 - [c32]Bin Fu, Richard Beigel:
A Comparison of Resource-Bounded Molecular Computation Models. ISTCS 1997: 6-11 - [c31]Richard Beigel:
Closure Properties of GapP and #P. ISTCS 1997: 144-146 - [c30]Richard Beigel, Richard Chang:
Commutative Queries. ISTCS 1997: 159-165 - [i8]Richard Beigel, Alexis Maciel:
Upper and Lower Bounds for Some Depth-3 Circuit Classes. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [b2]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 - [j28]Egemen Tanin, Richard Beigel, Ben Shneiderman:
Incremental data Structures and Algorithms for Dynamic Query Interfaces. SIGMOD Rec. 25(4): 21-24 (1996) - [j27]Richard Beigel, William I. Gasarch, Efim B. Kinber:
Frequency Computation and Bounded Queries. Theor. Comput. Sci. 163(1&2): 177-192 (1996) - [c29]Manindra Agrawal, Richard Beigel, Thomas Thierauf:
Pinpointing Computation with Modular Queries in the Boolean Hierarchy. FSTTCS 1996: 322-334 - [c28]Richard Beigel, William I. Gasarch, Martin Kummer, Timothy H. McNicholl, Frank Stephan:
On the Query Complexity of Sets. MFCS 1996: 206-217 - [i7]Manindra Agrawal, Richard Beigel, Thomas Thierauf:
Modulo Information from Nonadaptive Queries to NP. Electron. Colloquium Comput. Complex. TR96 (1996) - [i6]Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang:
Addition in log2n + O(1) Steps on Average: A Simple Analysis. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [j26]Richard Beigel, Martin Kummer, Frank Stephan:
Quantifying the Amount of Verboseness. Inf. Comput. 118(1): 73-90 (1995) - [j25]Richard Beigel, Martin Kummer, Frank Stephan:
Approximable Sets. Inf. Comput. 120(2): 304-314 (1995) - [j24]Richard Beigel, Nick Reingold, Daniel A. Spielman:
PP Is Closed under Intersection. J. Comput. Syst. Sci. 50(2): 191-202 (1995) - [c27]Richard Beigel, William I. Gasarch, Efim B. Kinber:
Frequency Computation and Bounded Queries. SCT 1995: 125-132 - [c26]Richard Beigel, Howard Straubing:
The Power of Local Self-Reductions. SCT 1995: 277-285 - [c25]Richard Beigel, David Eppstein:
3-Coloring in Time O(1.3446n): A No-MIS Algorithm. FOCS 1995: 444-452 - [c24]Richard Beigel, William Hurwood, Nabil Kahalé:
Fault Diagnosis in a Flash. FOCS 1995: 571-580 - [i5]Richard Beigel, David Eppstein:
3-Coloring in time O(1.3446n): A no-MIS Algorithm. Electron. Colloquium Comput. Complex. TR95 (1995) - [i4]Richard Beigel:
Closure Properties of GapP and #P. Electron. Colloquium Comput. Complex. TR95 (1995) - [i3]Richard Beigel, William I. Gasarch, Efim B. Kinber:
Frequency Computation and Bounded Queries. Electron. Colloquium Comput. Complex. TR95 (1995) - [i2]Richard Beigel, Howard Straubing:
The Power of Local Self-Reductions. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [j23]Richard Beigel:
When do Extra Majority Gates Help? Polylog(N) Majority Gates Are Equivalent to One. Comput. Complex. 4: 314-324 (1994) - [j22]Richard Beigel:
Perceptrons, PP, and the Polynomial Hierarchy. Comput. Complex. 4: 339-349 (1994) - [j21]Richard Beigel, Jun Tarui:
On ACC. Comput. Complex. 4: 350-366 (1994) - [j20]David A. Mix Barrington, Richard Beigel, Steven Rudich:
Representing Boolean Functions as Polynomials Modulo Composite Numbers. Comput. Complex. 4: 367-382 (1994) - [j19]James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich:
The Expressive Power of Voting Polynomials. Comb. 14(2): 135-148 (1994) - [c23]Richard Beigel, Martin Kummer, Frank Stephan:
Approximable Sets. SCT 1994: 12-23 - [c22]Richard Beigel, Judy Goldsmith:
Downward separation fails catastrophically for limited nondeterminism classes. SCT 1994: 134-138 - [c21]Ming Gu, Martin Farach, Richard Beigel:
An Efficient Algorithm for Dynamic Text Indexing. SODA 1994: 697-704 - [i1]Richard Beigel, William Hurwood, Nabil Kahalé:
Fault Diagnosis in a Flash. Electron. Colloquium Comput. Complex. TR94 (1994) - 1993
- [j18]Richard Beigel, William I. Gasarch, John Gill, James C. Owings:
Terse, Superterse, and Verbose Sets. Inf. Comput. 103(1): 68-85 (1993) - [j17]Richard Beigel, Richard Chang, Mitsunori Ogiwara:
A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies. Math. Syst. Theory 26(3): 293-310 (1993) - [j16]Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer:
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. 115(2): 225-241 (1993) - [c20]Sreerama K. Murthy, Simon Kasif, Steven Salzberg, Richard Beigel:
OC1: A Randomized Induction of Oblique Decision Trees. AAAI 1993: 322-327 - [c19]Richard Beigel:
The Polynomial Method in Circuit Complexity. SCT 1993: 82-95 - [c18]Richard Beigel, Grigorii Margulis, Daniel A. Spielman:
Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds. SPAA 1993: 21-29 - 1992
- [j15]Richard Beigel, Joan Feigenbaum:
On Being Incoherent Without Being Very Hard. Comput. Complex. 2: 1-17 (1992) - [j14]Richard Beigel, John Gill:
Counting Classes: Thresholds, Parity, Mods, and Fewness. Theor. Comput. Sci. 103(1): 3-23 (1992) - [c17]Richard Beigel:
Perceptrons, PP, and the Polynomial Hierarchy. SCT 1992: 14-19 - [c16]Richard Beigel, Jun Tarui, Seinosuke Toda:
On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. ISAAC 1992: 420-429 - [c15]Richard Beigel, Martin Kummer, Frank Stephan:
Quantifying the Amount of Verboseness. LFCS 1992: 21-32 - [c14]Richard Beigel:
When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One. STOC 1992: 450-454 - [c13]David A. Mix Barrington, Richard Beigel, Steven Rudich:
Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract). STOC 1992: 455-461 - 1991
- [j13]Richard Beigel, William I. Gasarch:
The Mapmaker's dilemma. Discret. Appl. Math. 34(1-3): 37-48 (1991) - [j12]Richard Beigel, Lane A. Hemachandra, Gerd Wechsung:
Probabilistic Polynomial Time is Closed under Parity Reductions. Inf. Process. Lett. 37(2): 91-94 (1991) - [j11]Richard Beigel:
Relativized Counting Classes: Relations among Thresholds, Parity, and Mods. J. Comput. Syst. Sci. 42(1): 76-96 (1991) - [j10]Richard Beigel, Clyde P. Kruskal:
Processor networks and interconnection networks without long wires (extended abstract). SIGARCH Comput. Archit. News 19(1): 15-24 (1991) - [j9]Richard Beigel:
Bounded Queries to SAT and the Boolean Hierarchy. Theor. Comput. Sci. 84(2): 199-223 (1991) - [c12]Richard Beigel, Nick Reingold, Daniel A. Spielman:
The Perceptron Strikes Back. SCT 1991: 286-291 - [c11]Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser:
Languages that Are Easier than their Proofs. FOCS 1991: 19-28 - [c10]Richard Beigel, Jun Tarui:
On ACC. FOCS 1991: 783-792 - [c9]Richard Beigel, Nick Reingold, Daniel A. Spielman:
PP Is Closed Under Intersection (Extended Abstract). STOC 1991: 1-9 - [c8]James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich:
The Expressive Power of Voting Polynomials. STOC 1991: 402-409 - 1990
- [j8]Richard Beigel:
Unbounded Searching Slgorithms. SIAM J. Comput. 19(3): 522-537 (1990) - [j7]Richard Beigel, John Gill:
Sorting n Objects with a K-Sorter. IEEE Trans. Computers 39(5): 714-716 (1990) - [j6]Richard Beigel:
Bi-Immunity Results for Cheatable Sets. Theor. Comput. Sci. 73(3): 249-263 (1990) - [c7]Amihood Amir, Richard Beigel, William I. Gasarch:
Some Connections Between Bounded Query Classes and Non-Uniform Complexity. SCT 1990: 232-243 - [c6]Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer:
A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS 1990: 1-11 - [c5]Richard Beigel, John Gill, Ulrich Hertrampf:
Counting Classes: Thresholds, Parity, Mods, and Fewness. STACS 1990: 49-57
1980 – 1989
- 1989
- [j5]Richard Beigel, William I. Gasarch, Louise Hay:
Bounded query classes and the difference hierarchy. Arch. Math. Log. 29(2): 69-84 (1989) - [j4]Richard Beigel, William I. Gasarch, James C. Owings:
Nondeterministic Bounded Query Reducibilities. Ann. Pure Appl. Log. 41(2): 107-118 (1989) - [j3]Richard Beigel, William I. Gasarch:
On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case. Ann. Pure Appl. Log. 45(1): 1-38 (1989) - [j2]Richard Beigel, William I. Gasarch:
On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case. Ann. Pure Appl. Log. 45(3): 227-246 (1989) - [j1]Michael J. Fischer, Robert P. Fischer, Richard Beigel:
Primitive recursion without implicit predecessor. SIGACT News 20(4): 87-91 (1989) - [c4]Richard Beigel:
On the Relativized Power of Additional Accepting Paths. SCT 1989: 216-224 - [c3]Richard Beigel, Lane A. Hemachandra, Gerd Wechsung:
On the Power of Probabilistic Polynomial Time: PNP[log] subseteq PP. SCT 1989: 225-227 - [c2]Richard Beigel, S. Rao Kosaraju, Gregory F. Sullivan:
Locating Faults in a Constant Number of Parallel Testing Rounds. SPAA 1989: 189-198 - 1987
- [b1]Richard Beigel:
Query-limited reducibilities. Stanford University, USA, 1987 - [c1]Richard Beigel:
A structural theorem that depends quantitatively on the complexity of SAT. SCT 1987: 28-32
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-24 23:07 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
