Richard Beigel

	2006
105		Richard Beigel, William I. Gasarch, James Glenn: The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. MFCS 2006: 146-156
104		Richard Beigel, Lance Fortnow, William I. Gasarch: A tight lower bound for restricted pir protocols. Computational Complexity 15(1): 82-91 (2006)
103		Richard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006)
	2005
102		Richard Beigel, David Eppstein: 3-coloring in time O(1.3289n). J. Algorithms 54(2): 168-204 (2005)
	2004
101		Bin Fu, Richard Beigel: Diagnosis in the Presence of Intermittent Faults. ISAAC 2004: 427-441
100		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)
99		Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. SIAM J. Comput. 33(2): 487-501 (2004)
98		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
97		Richard Beigel, Lance Fortnow: Are Cook and Karp Ever the Same? IEEE Conference on Computational Complexity 2003: 333-336
96		Richard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. ISAAC 2003: 98-107
95		Richard Beigel, Lance Fortnow, William I. Gasarch: A Nearly Tight Bound for Private Information Retrieval Protocols Electronic Colloquium on Computational Complexity (ECCC)(087): (2003)
94		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
93		Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. FOCS 2002: 197-
92		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
91		Noga Alon, Richard Beigel: Lower Bounds for Approximations by Low Degree Polynomials Over Zm. IEEE Conference on Computational Complexity 2001: 184-187
90		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
89		Richard Beigel, Richard Chang: Commutative Queries. Inf. Comput. 166(1): 71-91 (2001)
	2000
88		Richard Beigel, David Eppstein: 3-Coloring in Time O(1.3289^n) CoRR cs.DS/0006046: (2000)
87		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)
86		Richard Beigel, Bin Fu: Circuits over PP and PL. J. Comput. Syst. Sci. 60(2): 422-441 (2000)
85		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)
84		Vikraman Arvind, Richard Beigel, Antoni Lozano: The Complexity of Modular Graph Automorphism. SIAM J. Comput. 30(4): 1299-1320 (2000)
	1999
83		Richard Beigel: Gaps in Bounded Query Hierarchies. IEEE Conference on Computational Complexity 1999: 124-141
82		Richard Beigel, Alexis Maciel: Circuit Lower Bounds Collapse Relativized Complexity Classes. IEEE Conference on Computational Complexity 1999: 222-226
81		Richard Beigel: Finding Maximum Independent Sets in Sparse and General Graphs. SODA 1999: 856-857
80		Bin Fu, Richard Beigel: A Comparison of Resource-Bounded Molecular Computation Models. Algorithmica 24(2): 87-95 (1999)
79		Richard Beigel, Bin Fu: Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. Algorithmica 25(2-3): 222-238 (1999)
78		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
77		Richard Beigel, Bin Fu: Solving Intractable Problems with DNA Computing. IEEE Conference on Computational Complexity 1998: 154-
76		Richard Beigel, Egemen Tanin: The Geometry of Browsing. LATIN 1998: 331-340
75		Vikraman Arvind, Richard Beigel, Antoni Lozano: The Complexity of Modular Graph Automorphism. STACS 1998: 172-182
74		Richard Beigel, Tirza Hirst: One Help Bit Doesn't Help. STOC 1998: 124-130
73		Richard Beigel, Harry Buhrman, Lance Fortnow: NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208
72		Richard Beigel: Gaps in Bounded Query Hierarchies Electronic Colloquium on Computational Complexity (ECCC) 5(26): (1998)
71		Richard Beigel, Judy Goldsmith: Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. SIAM J. Comput. 27(5): 1420-1429 (1998)
70		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
69		Richard Beigel, Bin Fu: Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. ICALP 1997: 816-826
68		Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. IEEE Conference on Computational Complexity 1997: 149-157
67		Richard Beigel, Bin Fu: Circuits Over PP and PL. IEEE Conference on Computational Complexity 1997: 24-35
66		Egemen Tanin, Richard Beigel, Ben Shneiderman: Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. INFOVIS 1997: 81-86
65		Richard Beigel: Closure Properties of GapP and #P. ISTCS 1997: 144-146
64		Richard Beigel, Richard Chang: Commutative Queries. ISTCS 1997: 159-165
63		Bin Fu, Richard Beigel: A Comparison of Resource-Bounded Molecular Computation Models. ISTCS 1997: 6-11
62		Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. Computational Complexity 6(3): 235-255 (1997)
61		Richard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes Electronic Colloquium on Computational Complexity (ECCC) 4(2): (1997)
	1996
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	[90] [91] [93] [99]
4	Amihood Amir	[10] [87] [94]
5	Mehmet Serkan Apaydin	[90]
6	Vikraman Arvind	[75] [84]
7	James Aspnes	[18] [40]
8	David A. Mix Barrington	[25] [36]
9	Mihir Bellare	[21]
10	Anna Bernasconi	[78]
11	Harry Buhrman	[73] [100]
12	Richard Chang	[30] [64] [89]
13	Vilhelm Dahllöf	[98]
14	David Eppstein	[50] [54] [88] [102]
15	Martin Farach-Colton (Martin Farach)	[43]
16	Joan Feigenbaum	[21] [23]
17	Peter A. Fejer	[100]
18	Lance Fortnow	[73] [90] [95] [96] [97] [100] [103] [104]
19	Bin Fu	[63] [67] [69] [77] [79] [80] [86] [101]
20	Merrick L. Furst	[18] [40]
21	William I. Gasarch	[1] [2] [3] [10] [16] [31] [48] [52] [55] [57] [59] [70] [85] [87] [94] [95] [104] [105]
22	John Gill	[9] [11] [22] [31]
23	James Glenn	[105]
24	Judy Goldsmith	[41] [71]
25	Shafi Goldwasser	[21]
26	Piotr Grabowski	[100]
27	Ming Gu	[43]
28	Lane A. Hemaspaandra (Lane A. Hemachandra)	[4] [15] [92]
29	Harald Hempel	[92]
30	Ulrich Hertrampf	[11] [12] [29]
31	Tirza Hirst	[74]
32	Steven Homer	[12] [29]
33	William Hurwood	[35] [53]
34	Peter Jonsson	[98]
35	Nabil Kahale	[35] [53]
36	Simon Kasif	[34] [90] [93] [99]
37	Efim B. Kinber	[48] [52] [55]
38	S. Rao Kosaraju	[6]
39	Martin Kummer	[27] [42] [45] [46] [59] [85]
40	Ming Li	[57] [70]
41	Luc Longpré	[100]
42	Antoni Lozano	[75] [84]
43	Alexis Maciel	[61] [62] [68] [82]
44	Grigorii Margulis	[33]
45	Georgia Martin	[85]
46	Timothy McNicholl	[59] [85]
47	Andrej Muchnik (Andrei A. Muchnik)	[100]
48	Sreerama K. Murthy	[34]
49	Mitsunori Ogihara (Mitsunori Ogiwara)	[30]
50	James C. Owings	[3] [31]
51	Nick Reingold	[17] [19] [44]
52	Steven Rudich	[18] [25] [36] [40] [93] [99]
53	Steven Salzberg (Steven L. Salzberg)	[34]
54	Ben Shneiderman	[56] [66]
55	Daniel A. Spielman	[17] [19] [33] [44]
56	Frank Stephan	[27] [42] [45] [46] [59] [85] [96] [100] [103]
57	Howard Straubing	[47] [51]
58	Benny Sudakov	[93] [99]
59	Gregory F. Sullivan	[6]
60	Egemen Tanin	[56] [66] [76]
61	Jun Tarui	[20] [28] [37]
62	Thomas Thierauf	[58] [60]
63	Seinosuke Toda	[28]
64	Leen Torenvliet	[100]
65	Jörg Vogel	[92]
66	Gerd Wechsung	[4] [15]
67	Louxin Zhang	[57] [70]

Colors in the list of coauthors