Richard Beigel

	2012
110		Richard Beigel, Bin Fu: A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. FAW-AAIM 2012: 172-181
	2011
109		Richard Beigel, Bin Fu: A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. Electronic Colloquium on Computational Complexity (ECCC) 18: 28 (2011)
	2010
108		Richard Beigel, Bin Fu: A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing CoRR abs/1007.1260: (2010)
	2006
107		Richard Beigel, William I. Gasarch, James Glenn: The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. MFCS 2006: 146-156
106		Richard Beigel, Lance Fortnow, William I. Gasarch: A tight lower bound for restricted pir protocols. Computational Complexity 15(1): 82-91 (2006)
105		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)
104		Richard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006)
	2005
103		Richard Beigel, David Eppstein: 3-coloring in time O(1.3289n). J. Algorithms 54(2): 168-204 (2005)
	2004
102		Bin Fu, Richard Beigel: Diagnosis in the Presence of Intermittent Faults. ISAAC 2004: 427-441
101		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)
100		Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. SIAM J. Comput. 33(2): 487-501 (2004)
99		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)
	2003
98		Richard Beigel, Lance Fortnow: Are Cook and Karp Ever the Same? IEEE Conference on Computational Complexity 2003: 333-336
97		Richard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. ISAAC 2003: 98-107
96		Richard Beigel, Lance Fortnow, William I. Gasarch: A Nearly Tight Bound for Private Information Retrieval Protocols Electronic Colloquium on Computational Complexity (ECCC)(087): (2003)
95		Amihood Amir, Richard Beigel, William I. Gasarch: Some connections between bounded query classes and non-uniform complexity. Inf. Comput. 186(1): 104-139 (2003)
	2002
94		Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. FOCS 2002: 197-
93		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)
	2001
92		Noga Alon, Richard Beigel: Lower Bounds for Approximations by Low Degree Polynomials Over Zm. IEEE Conference on Computational Complexity 2001: 184-187
91		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
90		Richard Beigel, Richard Chang: Commutative Queries. Inf. Comput. 166(1): 71-91 (2001)
	2000
89		Richard Beigel, David Eppstein: 3-Coloring in Time O(1.3289^n) CoRR cs.DS/0006046: (2000)
88		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)
87		Richard Beigel, Bin Fu: Circuits over PP and PL. J. Comput. Syst. Sci. 60(2): 422-441 (2000)
86		Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl, Frank Stephan: The Comlexity of OddAn. J. Symb. Log. 65(1): 1-18 (2000)
85		Vikraman Arvind, Richard Beigel, Antoni Lozano: The Complexity of Modular Graph Automorphism. SIAM J. Comput. 30(4): 1299-1320 (2000)
	1999
84		Richard Beigel: Gaps in Bounded Query Hierarchies. IEEE Conference on Computational Complexity 1999: 124-141
83		Richard Beigel, Alexis Maciel: Circuit Lower Bounds Collapse Relativized Complexity Classes. IEEE Conference on Computational Complexity 1999: 222-226
82		Richard Beigel: Finding Maximum Independent Sets in Sparse and General Graphs. SODA 1999: 856-857
81		Bin Fu, Richard Beigel: A Comparison of Resource-Bounded Molecular Computation Models. Algorithmica 24(2): 87-95 (1999)
80		Richard Beigel, Bin Fu: Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. Algorithmica 25(2-3): 222-238 (1999)
79		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)
	1998
78		Richard Beigel, Bin Fu: Solving Intractable Problems with DNA Computing. IEEE Conference on Computational Complexity 1998: 154-
77		Richard Beigel, Egemen Tanin: The Geometry of Browsing. LATIN 1998: 331-340
76		Vikraman Arvind, Richard Beigel, Antoni Lozano: The Complexity of Modular Graph Automorphism. STACS 1998: 172-182
75		Richard Beigel, Tirza Hirst: One Help Bit Doesn't Help. STOC 1998: 124-130
74		Richard Beigel, Harry Buhrman, Lance Fortnow: NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208
73		Richard Beigel: Gaps in Bounded Query Hierarchies Electronic Colloquium on Computational Complexity (ECCC) 5(26): (1998)
72		Richard Beigel, Judy Goldsmith: Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. SIAM J. Comput. 27(5): 1420-1429 (1998)
71		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)
	1997
70		Richard Beigel, Bin Fu: Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. ICALP 1997: 816-826
69		Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. IEEE Conference on Computational Complexity 1997: 149-157
68		Richard Beigel, Bin Fu: Circuits Over PP and PL. IEEE Conference on Computational Complexity 1997: 24-35
67		Egemen Tanin, Richard Beigel, Ben Shneiderman: Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. INFOVIS 1997: 81-86
66		Richard Beigel: Closure Properties of GapP and #P. ISTCS 1997: 144-146
65		Richard Beigel, Richard Chang: Commutative Queries. ISTCS 1997: 159-165
64		Bin Fu, Richard Beigel: A Comparison of Resource-Bounded Molecular Computation Models. ISTCS 1997: 6-11
63		Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. Computational Complexity 6(3): 235-255 (1997)
62		Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes Electronic Colloquium on Computational Complexity (ECCC) 4(2): (1997)
	1996
61		Robert W. Floyd, Richard Beigel: Die Sprache der Maschinen. International Thomson 1996: I-XXVII, 1-652
60		Manindra Agrawal, Richard Beigel, Thomas Thierauf: Pinpointing Computation with Modular Queries in the Boolean Hierarchy. FSTTCS 1996: 322-334
59		Richard Beigel, William I. Gasarch, Martin Kummer, Timothy McNicholl, Frank Stephan: On the Query Complexity of Sets. MFCS 1996: 206-217
58		Manindra Agrawal, Richard Beigel, Thomas Thierauf: Modulo Information from Nonadaptive Queries to NP Electronic Colloquium on Computational Complexity (ECCC) 3(1): (1996)
57		Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang: Addition in log2n + O(1) Steps on Average: A Simple Analysis Electronic Colloquium on Computational Complexity (ECCC) 3(51): (1996)
56		Egemen Tanin, Richard Beigel, Ben Shneiderman: Incremental data Structures and Algorithms for Dynamic Query Interfaces. SIGMOD Record 25(4): 21-24 (1996)
55		Richard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries. Theor. Comput. Sci. 163(1&2): 177-192 (1996)
	1995
54		Richard Beigel, David Eppstein: 3-Coloring in Time O(1.3446n): A No-MIS Algorithm. FOCS 1995: 444-452
53		Richard Beigel, William Hurwood, Nabil Kahale: Fault Diagnosis in a Flash. FOCS 1995: 571-580
52		Richard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries. Structure in Complexity Theory Conference 1995: 125-132
51		Richard Beigel, Howard Straubing: The Power of Local Self-Reductions. Structure in Complexity Theory Conference 1995: 277-285
50		Richard Beigel, David Eppstein: 3-Coloring in time O(1.3446n): A no-MIS Algorithm Electronic Colloquium on Computational Complexity (ECCC) 2(33): (1995)
49		Richard Beigel: Closure Properties of GapP and #P Electronic Colloquium on Computational Complexity (ECCC) 2(35): (1995)
48		Richard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries Electronic Colloquium on Computational Complexity (ECCC) 2(36): (1995)
47		Richard Beigel, Howard Straubing: The Power of Local Self-Reductions Electronic Colloquium on Computational Complexity (ECCC) 2(37): (1995)
46		Richard Beigel, Martin Kummer, Frank Stephan: Quantifying the Amount of Verboseness Inf. Comput. 118(1): 73-90 (1995)
45		Richard Beigel, Martin Kummer, Frank Stephan: Approximable Sets Inf. Comput. 120(2): 304-314 (1995)
44		Richard Beigel, Nick Reingold, Daniel A. Spielman: PP Is Closed under Intersection. J. Comput. Syst. Sci. 50(2): 191-202 (1995)
	1994
43		Ming Gu, Martin Farach, Richard Beigel: An Efficient Algorithm for Dynamic Text Indexing. SODA 1994: 697-704
42		Richard Beigel, Martin Kummer, Frank Stephan: Approximable Sets. Structure in Complexity Theory Conference 1994: 12-23
41		Richard Beigel, Judy Goldsmith: Downward separation fails catastrophically for limited nondeterminism classes. Structure in Complexity Theory Conference 1994: 134-138
40		James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich: The Expressive Power of Voting Polynomials. Combinatorica 14(2): 135-148 (1994)
39		Richard Beigel: When do Extra Majority Gates Help? Polylog(N) Majority Gates Are Equivalent to One. Computational Complexity 4: 314-324 (1994)
38		Richard Beigel: Perceptrons, PP, and the Polynomial Hierarchy. Computational Complexity 4: 339-349 (1994)
37		Richard Beigel, Jun Tarui: On ACC. Computational Complexity 4: 350-366 (1994)
36		David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers. Computational Complexity 4: 367-382 (1994)
35		Richard Beigel, William Hurwood, Nabil Kahale: Fault Diagnosis in a Flash Electronic Colloquium on Computational Complexity (ECCC) 1(11): (1994)
	1993
34		Sreerama K. Murthy, Simon Kasif, Steven Salzberg, Richard Beigel: OC1: A Randomized Induction of Oblique Decision Trees. AAAI 1993: 322-327
33		Richard Beigel, Grigorii Margulis, Daniel A. Spielman: Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds. SPAA 1993: 21-29
32		Richard Beigel: The Polynomial Method in Circuit Complexity. Structure in Complexity Theory Conference 1993: 82-95
31		Richard Beigel, William I. Gasarch, John Gill, James C. Owings: Terse, Superterse, and Verbose Sets Inf. Comput. 103(1): 68-85 (1993)
30		Richard Beigel, Richard Chang, Mitsunori Ogiwara: A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies. Mathematical Systems Theory 26(3): 293-310 (1993)
29		Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. 115(2): 225-241 (1993)
	1992
28		Richard Beigel, Jun Tarui, Seinosuke Toda: On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. ISAAC 1992: 420-429
27		Richard Beigel, Martin Kummer, Frank Stephan: Quantifying the Amount of Verboseness. LFCS 1992: 21-32
26		Richard Beigel: When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One STOC 1992: 450-454
25		David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) STOC 1992: 455-461
24		Richard Beigel: Perceptrons, PP, and the Polynomial Hierarchy. Structure in Complexity Theory Conference 1992: 14-19
23		Richard Beigel, Joan Feigenbaum: On Being Incoherent Without Being Very Hard. Computational Complexity 2: 1-17 (1992)
22		Richard Beigel, John Gill: Counting Classes: Thresholds, Parity, Mods, and Fewness. Theor. Comput. Sci. 103(1): 3-23 (1992)
	1991
21		Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser: Languages that Are Easier than their Proofs FOCS 1991: 19-28
20		Richard Beigel, Jun Tarui: On ACC FOCS 1991: 783-792
19		Richard Beigel, Nick Reingold, Daniel A. Spielman: PP Is Closed Under Intersection (Extended Abstract) STOC 1991: 1-9
18		James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich: The Expressive Power of Voting Polynomials STOC 1991: 402-409
17		Richard Beigel, Nick Reingold, Daniel A. Spielman: The Perceptron Strikes Back. Structure in Complexity Theory Conference 1991: 286-291
16		Richard Beigel, William I. Gasarch: The Mapmaker's dilemma. Discrete Applied Mathematics 34(1-3): 37-48 (1991)
15		Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: Probabilistic Polynomial Time is Closed under Parity Reductions. Inf. Process. Lett. 37(2): 91-94 (1991)
14		Richard Beigel: Relativized Counting Classes: Relations among Thresholds, Parity, and Mods. J. Comput. Syst. Sci. 42(1): 76-96 (1991)
13		Richard Beigel: Bounded Queries to SAT and the Boolean Hierarchy. Theor. Comput. Sci. 84(2): 199-223 (1991)
	1990
12		Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer: A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS 1990: 1-11
11		Richard Beigel, John Gill, Ulrich Hertrampf: Counting Classes: Thresholds, Parity, Mods, and Fewness. STACS 1990: 49-57
10		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
9		Richard Beigel, John Gill: Sorting n Objects with a K-Sorter. IEEE Trans. Computers 39(5): 714-716 (1990)
8		Richard Beigel: Unbounded Searching Slgorithms. SIAM J. Comput. 19(3): 522-537 (1990)
7		Richard Beigel: Bi-Immunity Results for Cheatable Sets. Theor. Comput. Sci. 73(3): 249-263 (1990)
	1989
6		Richard Beigel, S. Rao Kosaraju, Gregory F. Sullivan: Locating Faults in a Constant Number of Parallel Testing Rounds. SPAA 1989: 189-198
5		Richard Beigel: On the Relativized Power of Additional Accepting Paths. Structure in Complexity Theory Conference 1989: 216-224
4		Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: On the Power of Probabilistic Polynomial Time: PNP[log] subseteq PP. Structure in Complexity Theory Conference 1989: 225-227
3		Richard Beigel, William I. Gasarch, James C. Owings: Nondeterministic Bounded Query Reducibilities. Ann. Pure Appl. Logic 41(2): 107-118 (1989)
2		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)
1		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)

Coauthor Index

1	Manindra Agrawal	[58] [60]
2	Eric Allender	[12] [29]
3	Noga Alon	[91] [92] [94] [100]
4	Amihood Amir	[10] [88] [95]
5	Mehmet Serkan Apaydin	[91]
6	Vikraman Arvind	[76] [85]
7	James Aspnes	[18] [40]
8	David A. Mix Barrington	[25] [36]
9	Mihir Bellare	[21]
10	Anna Bernasconi	[79]
11	Harry Buhrman	[74] [101] [105]
12	Richard Chang	[30] [65] [90]
13	Vilhelm Dahllöf	[99]
14	David Eppstein	[50] [54] [89] [103]
15	Martin Farach-Colton (Martin Farach)	[43]
16	Joan Feigenbaum	[21] [23]
17	Peter A. Fejer	[101] [105]
18	Robert W. Floyd	[61]
19	Lance Fortnow	[74] [91] [96] [97] [98] [101] [104] [105] [106]
20	Bin Fu	[64] [68] [70] [78] [80] [81] [87] [102] [108] [109] [110]
21	Merrick L. Furst	[18] [40]
22	William I. Gasarch	[1] [2] [3] [10] [16] [31] [48] [52] [55] [57] [59] [71] [86] [88] [95] [96] [106] [107]
23	John Gill	[9] [11] [22] [31]
24	James Glenn	[107]
25	Judy Goldsmith	[41] [72]
26	Shafi Goldwasser	[21]
27	Piotr Grabowski	[101] [105]
28	Ming Gu	[43]
29	Lane A. Hemaspaandra (Lane A. Hemachandra)	[4] [15] [93]
30	Harald Hempel	[93]
31	Ulrich Hertrampf	[11] [12] [29]
32	Tirza Hirst	[75]
33	Steven Homer	[12] [29]
34	William Hurwood	[35] [53]
35	Peter Jonsson	[99]
36	Nabil Kahale	[35] [53]
37	Simon Kasif	[34] [91] [94] [100]
38	Efim B. Kinber	[48] [52] [55]
39	S. Rao Kosaraju	[6]
40	Martin Kummer	[27] [42] [45] [46] [59] [86]
41	Ming Li	[57] [71]
42	Luc Longpré	[101] [105]
43	Antoni Lozano	[76] [85]
44	Alexis Maciel	[62] [63] [69] [83]
45	Grigorii Margulis	[33]
46	Georgia Martin	[86]
47	Timothy McNicholl	[59] [86]
48	Andrej Muchnik (Andrei A. Muchnik)	[101] [105]
49	Sreerama K. Murthy	[34]
50	Mitsunori Ogihara (Mitsunori Ogiwara)	[30]
51	James C. Owings	[3] [31]
52	Nick Reingold	[17] [19] [44]
53	Steven Rudich	[18] [25] [36] [40] [94] [100]
54	Steven Salzberg (Steven L. Salzberg)	[34]
55	Ben Shneiderman	[56] [67]
56	Daniel A. Spielman	[17] [19] [33] [44]
57	Frank Stephan	[27] [42] [45] [46] [59] [86] [97] [101] [104] [105]
58	Howard Straubing	[47] [51]
59	Benny Sudakov	[94] [100]
60	Gregory F. Sullivan	[6]
61	Egemen Tanin	[56] [67] [77]
62	Jun Tarui	[20] [28] [37]
63	Thomas Thierauf	[58] [60]
64	Seinosuke Toda	[28]
65	Leen Torenvliet	[101] [105]
66	Jörg Vogel	[93]
67	Gerd Wechsung	[4] [15]
68	Louxin Zhang	[57] [71]

Colors in the list of coauthors

Last update Sun May 27 04:04:01 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page