dblp.uni-trier.dewww.uni-trier.de

Richard Beigel

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2006
105EERichard Beigel, William I. Gasarch, James Glenn: The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. MFCS 2006: 146-156
104EERichard Beigel, Lance Fortnow, William I. Gasarch: A tight lower bound for restricted pir protocols. Computational Complexity 15(1): 82-91 (2006)
103EERichard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006)
2005
102EERichard Beigel, David Eppstein: 3-coloring in time O(1.3289n). J. Algorithms 54(2): 168-204 (2005)
2004
101EEBin Fu, Richard Beigel: Diagnosis in the Presence of Intermittent Faults. ISAAC 2004: 427-441
100EERichard 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)
99EENoga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. SIAM J. Comput. 33(2): 487-501 (2004)
98EEVilhelm 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
97EERichard Beigel, Lance Fortnow: Are Cook and Karp Ever the Same? IEEE Conference on Computational Complexity 2003: 333-336
96EERichard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. ISAAC 2003: 98-107
95EERichard Beigel, Lance Fortnow, William I. Gasarch: A Nearly Tight Bound for Private Information Retrieval Protocols Electronic Colloquium on Computational Complexity (ECCC)(087): (2003)
94EEAmihood Amir, Richard Beigel, William I. Gasarch: Some connections between bounded query classes and non-uniform complexity. Inf. Comput. 186(1): 104-139 (2003)
2002
93EENoga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov: Learning a Hidden Matching. FOCS 2002: 197-
92EERichard 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
91EENoga Alon, Richard Beigel: Lower Bounds for Approximations by Low Degree Polynomials Over Zm. IEEE Conference on Computational Complexity 2001: 184-187
90EERichard 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
88EERichard Beigel, David Eppstein: 3-Coloring in Time O(1.3289^n) CoRR cs.DS/0006046: (2000)
87EEAmihood 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)
84EEVikraman Arvind, Richard Beigel, Antoni Lozano: The Complexity of Modular Graph Automorphism. SIAM J. Comput. 30(4): 1299-1320 (2000)
1999
83EERichard Beigel: Gaps in Bounded Query Hierarchies. IEEE Conference on Computational Complexity 1999: 124-141
82EERichard Beigel, Alexis Maciel: Circuit Lower Bounds Collapse Relativized Complexity Classes. IEEE Conference on Computational Complexity 1999: 222-226
81EERichard Beigel: Finding Maximum Independent Sets in Sparse and General Graphs. SODA 1999: 856-857
80EEBin Fu, Richard Beigel: A Comparison of Resource-Bounded Molecular Computation Models. Algorithmica 24(2): 87-95 (1999)
79EERichard 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
77EERichard Beigel, Bin Fu: Solving Intractable Problems with DNA Computing. IEEE Conference on Computational Complexity 1998: 154-
76EERichard 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
74EERichard Beigel, Tirza Hirst: One Help Bit Doesn't Help. STOC 1998: 124-130
73EERichard Beigel, Harry Buhrman, Lance Fortnow: NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208
72EERichard Beigel: Gaps in Bounded Query Hierarchies Electronic Colloquium on Computational Complexity (ECCC) 5(26): (1998)
71EERichard Beigel, Judy Goldsmith: Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. SIAM J. Comput. 27(5): 1420-1429 (1998)
70EERichard 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
68EERichard Beigel, Alexis Maciel: Upper and Lower Bounds for Some Depth-3 Circuit Classes. IEEE Conference on Computational Complexity 1997: 149-157
67EERichard Beigel, Bin Fu: Circuits Over PP and PL. IEEE Conference on Computational Complexity 1997: 24-35
66EEEgemen Tanin, Richard Beigel, Ben Shneiderman: Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. INFOVIS 1997: 81-86
65EERichard Beigel: Closure Properties of GapP and #P. ISTCS 1997: 144-146
64EERichard Beigel, Richard Chang: Commutative Queries. ISTCS 1997: 159-165
63EEBin 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)
61EERichard 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
58EEManindra Agrawal, Richard Beigel, Thomas Thierauf: Modulo Information from Nonadaptive Queries to NP Electronic Colloquium on Computational Complexity (ECCC) 3(1): (1996)
57EERichard 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)
56EEEgemen Tanin, Richard Beigel, Ben Shneiderman: Incremental data Structures and Algorithms for Dynamic Query Interfaces. SIGMOD Record 25(4): 21-24 (1996)
55EERichard 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
50EERichard Beigel, David Eppstein: 3-Coloring in time O(1.3446n): A no-MIS Algorithm Electronic Colloquium on Computational Complexity (ECCC) 2(33): (1995)
49EERichard Beigel: Closure Properties of GapP and #P Electronic Colloquium on Computational Complexity (ECCC) 2(35): (1995)
48EERichard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries Electronic Colloquium on Computational Complexity (ECCC) 2(36): (1995)
47EERichard 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)
35EERichard 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
33EERichard 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
16EERichard 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
6EERichard 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

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

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)