Richard Beigel

119 papers A* 15A 10B 9Misc 1Journal 63Unranked 19

Year	Rank	Type	Title / Venue / Authors
2016	J	`jnl`	On the sizes of DPDAs, PDAs, LBAs. Theor. Comput. Sci. Richard Beigel, William I. Gasarch
2015	J	`jnl`	On the Sizes of DPDAs, PDAs, LBAs. CoRR Richard Beigel, William I. Gasarch
2014	—	`conf`	On optimal scheduling of multiple mobile chargers in wireless sensor networks. MSCC@MobiHoc Richard Beigel, Jie Wu, Huanyang Zheng
2012	—	`conf`	A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. FAW-AAIM Richard Beigel, Bin Fu
2011	J	`jnl`	A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing. Electron. Colloquium Comput. Complex. Richard Beigel, Bin Fu
2010	J	`jnl`	A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing CoRR Richard Beigel, Bin Fu
2006	J	`jnl`	A tight lower bound for restricted pir protocols. Comput. Complex. Richard Beigel, Lance Fortnow, William I. Gasarch
2006	J	`jnl`	Enumerations of the Kolmogorov function. J. Symb. Log. Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet
2006	J	`jnl`	Infinitely-Often Autoreducible Sets. SIAM J. Comput. Richard Beigel, Lance Fortnow, Frank Stephan
2006	B	`conf`	The Multiparty Communication Complexity of Exact- MFCS Richard Beigel, William I. Gasarch, James Glenn
2005	J	`jnl`	3-coloring in time O(1.3289 J. Algorithms Richard Beigel, David Eppstein
2004	J	`jnl`	Algorithms for four variants of the exact satisfiability problem. Theor. Comput. Sci. Vilhelm Dahllöf, Peter Jonsson, Richard Beigel
2004	B	`conf`	Diagnosis in the Presence of Intermittent Faults. ISAAC Bin Fu, Richard Beigel
2004	J	`jnl`	Enumerations of the Kolmogorov Function Electron. Colloquium Comput. Complex. Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet
2004	J	`jnl`	Learning a Hidden Matching. SIAM J. Comput. Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
2003	J	`jnl`	A Nearly Tight Bound for Private Information Retrieval Protocols Electron. Colloquium Comput. Complex. Richard Beigel, Lance Fortnow, William I. Gasarch
2003	A	`conf`	Are Cook and Karp Ever the Same? CCC Richard Beigel, Lance Fortnow
2003	B	`conf`	Infinitely-Often Autoreducible Sets. ISAAC Richard Beigel, Lance Fortnow, Frank Stephan
2003	J	`jnl`	Some connections between bounded query classes and non-uniform complexity. Inf. Comput. Amihood Amir, Richard Beigel, William I. Gasarch
2002	A*	`conf`	Learning a Hidden Matching. FOCS Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
2002	J	`jnl`	Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph. Inf. Comput. Richard Beigel, Lane A. Hemaspaandra, Harald Hempel, Jörg Vogel
2001	B	`conf`	An optimal procedure for gap closing in whole genome shotgun sequencing. RECOMB Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow
2001	J	`jnl`	Commutative Queries. Inf. Comput. Richard Beigel, Richard Chang
2001	A	`conf`	Lower Bounds for Approximations by Low Degree Polynomials Over Z CCC Noga Alon, Richard Beigel
2000	J	`jnl`	3-Coloring in Time O(1.3289^n) CoRR Richard Beigel, David Eppstein
2000	J	`jnl`	Circuits over PP and PL. J. Comput. Syst. Sci. Richard Beigel, Bin Fu
2000	J	`jnl`	Some Connections between Bounded Query Classes and Non-Uniform Complexity Electron. Colloquium Comput. Complex. Amihood Amir, Richard Beigel, William I. Gasarch
2000	J	`jnl`	The Comlexity of Odd J. Symb. Log. Richard Beigel, William I. Gasarch, Martin Kummer, Georgia Martin, Timothy H. McNicholl, Frank Stephan
2000	J	`jnl`	The Complexity of Modular Graph Automorphism. SIAM J. Comput. Vikraman Arvind, Richard Beigel, Antoni Lozano
1999	J	`jnl`	A Comparison of Resource-Bounded Molecular Computation Models. Algorithmica Bin Fu, Richard Beigel
1999	J	`jnl`	A Note on the Polynomial Representation of Boolean Functions over GF(2). Int. J. Found. Comput. Sci. Richard Beigel, Anna Bernasconi
1999	A	`conf`	Circuit Lower Bounds Collapse Relativized Complexity Classes. CCC Richard Beigel, Alexis Maciel
1999	A*	`conf`	Finding Maximum Independent Sets in Sparse and General Graphs. SODA Richard Beigel
1999	A	`conf`	Gaps in Bounded Query Hierarchies. CCC Richard Beigel
1999	J	`jnl`	Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. Algorithmica Richard Beigel, Bin Fu
1998	J	`jnl`	Addition in log Theor. Comput. Sci. Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang
1998	J	`jnl`	Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. SIAM J. Comput. Richard Beigel, Judy Goldsmith
1998	J	`jnl`	Gaps in Bounded Query Hierarchies Electron. Colloquium Comput. Complex. Richard Beigel
1998	A*	`conf`	NP Might Not Be As Easy As Detecting Unique Solutions. STOC Richard Beigel, Harry Buhrman, Lance Fortnow
1998	A*	`conf`	One Help Bit Doesn't Help. STOC Richard Beigel, Tirza Hirst
1998	A	`conf`	Solving Intractable Problems with DNA Computing. CCC Richard Beigel, Bin Fu
1998	A	`conf`	The Complexity of Modular Graph Automorphism. STACS Vikraman Arvind, Richard Beigel, Antoni Lozano
1998	B	`conf`	The Geometry of Browsing. LATIN Richard Beigel, Egemen Tanin
1997	—	`conf`	A Comparison of Resource-Bounded Molecular Computation Models. ISTCS Bin Fu, Richard Beigel
1997	A	`conf`	Circuits Over PP and PL. CCC Richard Beigel, Bin Fu
1997	—	`conf`	Closure Properties of GapP and #P. ISTCS Richard Beigel
1997	—	`conf`	Commutative Queries. ISTCS Richard Beigel, Richard Chang
1997	—	`conf`	Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces. INFOVIS Egemen Tanin, Richard Beigel, Ben Shneiderman
1997	A*	`conf`	Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. ICALP Richard Beigel, Bin Fu
1997	—	`conf`	On molecular approximation algorithms for NP optimization problem. DNA Based Computers Bin Fu, Richard Beigel
1997	J	`jnl`	Upper and Lower Bounds for Some Depth-3 Circuit Classes Electron. Colloquium Comput. Complex. Richard Beigel, Alexis Maciel
1997	A	`conf`	Upper and Lower Bounds for Some Depth-3 Circuit Classes. CCC Richard Beigel, Alexis Maciel
1997	J	`jnl`	Upper and Lower Bounds for Some Depth-3 Circuit Classes. Comput. Complex. Richard Beigel, Alexis Maciel
1996	J	`jnl`	Addition in log Electron. Colloquium Comput. Complex. Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang
1996	—	`book`	Die Sprache der Maschinen. Robert W. Floyd, Richard Beigel
1996	J	`jnl`	Frequency Computation and Bounded Queries. Theor. Comput. Sci. Richard Beigel, William I. Gasarch, Efim B. Kinber
1996	J	`jnl`	Incremental data Structures and Algorithms for Dynamic Query Interfaces. SIGMOD Rec. Egemen Tanin, Richard Beigel, Ben Shneiderman
1996	J	`jnl`	Modulo Information from Nonadaptive Queries to NP Electron. Colloquium Comput. Complex. Manindra Agrawal, Richard Beigel, Thomas Thierauf
1996	B	`conf`	On the Query Complexity of Sets. MFCS Richard Beigel, William I. Gasarch, Martin Kummer, Timothy H. McNicholl, Frank Stephan
1996	—	`conf`	Pinpointing Computation with Modular Queries in the Boolean Hierarchy. FSTTCS Manindra Agrawal, Richard Beigel, Thomas Thierauf
1995	A*	`conf`	3-Coloring in Time O(1.3446 FOCS Richard Beigel, David Eppstein
1995	J	`jnl`	3-Coloring in time O(1.3446 Electron. Colloquium Comput. Complex. Richard Beigel, David Eppstein
1995	J	`jnl`	Approximable Sets Inf. Comput. Richard Beigel, Martin Kummer, Frank Stephan
1995	J	`jnl`	Closure Properties of GapP and #P Electron. Colloquium Comput. Complex. Richard Beigel
1995	A*	`conf`	Fault Diagnosis in a Flash. FOCS Richard Beigel, William Hurwood, Nabil Kahalé
1995	J	`jnl`	Frequency Computation and Bounded Queries Electron. Colloquium Comput. Complex. Richard Beigel, William I. Gasarch, Efim B. Kinber
1995	—	`conf`	Frequency Computation and Bounded Queries. SCT Richard Beigel, William I. Gasarch, Efim B. Kinber
1995	J	`jnl`	PP Is Closed under Intersection. J. Comput. Syst. Sci. Richard Beigel, Nick Reingold, Daniel A. Spielman
1995	J	`jnl`	Quantifying the Amount of Verboseness Inf. Comput. Richard Beigel, Martin Kummer, Frank Stephan
1995	J	`jnl`	The Power of Local Self-Reductions Electron. Colloquium Comput. Complex. Richard Beigel, Howard Straubing
1995	—	`conf`	The Power of Local Self-Reductions. SCT Richard Beigel, Howard Straubing
1994	A*	`conf`	An Efficient Algorithm for Dynamic Text Indexing. SODA Ming Gu, Martin Farach, Richard Beigel
1994	—	`conf`	Approximable Sets. SCT Richard Beigel, Martin Kummer, Frank Stephan
1994	—	`conf`	Downward separation fails catastrophically for limited nondeterminism classes. SCT Richard Beigel, Judy Goldsmith
1994	J	`jnl`	Fault Diagnosis in a Flash Electron. Colloquium Comput. Complex. Richard Beigel, William Hurwood, Nabil Kahalé
1994	J	`jnl`	On ACC. Comput. Complex. Richard Beigel, Jun Tarui
1994	J	`jnl`	Perceptrons, PP, and the Polynomial Hierarchy. Comput. Complex. Richard Beigel
1994	J	`jnl`	Representing Boolean Functions as Polynomials Modulo Composite Numbers. Comput. Complex. David A. Mix Barrington, Richard Beigel, Steven Rudich
1994	J	`jnl`	The Expressive Power of Voting Polynomials. Comb. James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich
1994	J	`jnl`	When do Extra Majority Gates Help? Polylog( Comput. Complex. Richard Beigel
1993	J	`jnl`	A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies. Math. Syst. Theory Richard Beigel, Richard Chang, Mitsunori Ogiwara
1993	J	`jnl`	Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theor. Comput. Sci. Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
1993	B	`conf`	Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds. SPAA Richard Beigel, Grigorii Margulis, Daniel A. Spielman
1993	A*	`conf`	OC1: A Randomized Induction of Oblique Decision Trees. AAAI Sreerama K. Murthy, Simon Kasif, Steven Salzberg, Richard Beigel
1993	J	`jnl`	Terse, Superterse, and Verbose Sets Inf. Comput. Richard Beigel, William I. Gasarch, John Gill, James C. Owings
1993	—	`conf`	The Polynomial Method in Circuit Complexity. SCT Richard Beigel
1992	J	`jnl`	Counting Classes: Thresholds, Parity, Mods, and Fewness. Theor. Comput. Sci. Richard Beigel, John Gill
1992	J	`jnl`	On Being Incoherent Without Being Very Hard. Comput. Complex. Richard Beigel, Joan Feigenbaum
1992	B	`conf`	On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. ISAAC Richard Beigel, Jun Tarui, Seinosuke Toda
1992	—	`conf`	Perceptrons, PP, and the Polynomial Hierarchy. SCT Richard Beigel
1992	Misc	`conf`	Quantifying the Amount of Verboseness. LFCS Richard Beigel, Martin Kummer, Frank Stephan
1992	A*	`conf`	Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) STOC David A. Mix Barrington, Richard Beigel, Steven Rudich
1992	A*	`conf`	When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One STOC Richard Beigel
1991	J	`jnl`	Bounded Queries to SAT and the Boolean Hierarchy. Theor. Comput. Sci. Richard Beigel
1991	A*	`conf`	Languages that Are Easier than their Proofs FOCS Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser
1991	A*	`conf`	On ACC FOCS Richard Beigel, Jun Tarui
1991	A*	`conf`	PP Is Closed Under Intersection (Extended Abstract) STOC Richard Beigel, Nick Reingold, Daniel A. Spielman
1991	J	`jnl`	Probabilistic Polynomial Time is Closed under Parity Reductions. Inf. Process. Lett. Richard Beigel, Lane A. Hemachandra, Gerd Wechsung
1991	J	`jnl`	Processor networks and interconnection networks without long wires (extended abstract). SIGARCH Comput. Archit. News Richard Beigel, Clyde P. Kruskal
1991	J	`jnl`	Relativized Counting Classes: Relations among Thresholds, Parity, and Mods. J. Comput. Syst. Sci. Richard Beigel
1991	A*	`conf`	The Expressive Power of Voting Polynomials STOC James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich
1991	J	`jnl`	The Mapmaker's dilemma. Discret. Appl. Math. Richard Beigel, William I. Gasarch
1991	—	`conf`	The Perceptron Strikes Back. SCT Richard Beigel, Nick Reingold, Daniel A. Spielman
1990	A	`conf`	A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. STACS Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
1990	J	`jnl`	Bi-Immunity Results for Cheatable Sets. Theor. Comput. Sci. Richard Beigel
1990	A	`conf`	Counting Classes: Thresholds, Parity, Mods, and Fewness. STACS Richard Beigel, John Gill, Ulrich Hertrampf
1990	—	`conf`	Some Connections Between Bounded Query Classes and Non-Uniform Complexity. SCT Amihood Amir, Richard Beigel, William I. Gasarch
1990	J	`jnl`	Sorting n Objects with a K-Sorter. IEEE Trans. Computers Richard Beigel, John Gill
1990	J	`jnl`	Unbounded Searching Slgorithms. SIAM J. Comput. Richard Beigel
1989	J	`jnl`	Bounded query classes and the difference hierarchy. Arch. Math. Log. Richard Beigel, William I. Gasarch, Louise Hay
1989	B	`conf`	Locating Faults in a Constant Number of Parallel Testing Rounds. SPAA Richard Beigel, S. Rao Kosaraju, Gregory F. Sullivan
1989	J	`jnl`	Nondeterministic Bounded Query Reducibilities. Ann. Pure Appl. Log. Richard Beigel, William I. Gasarch, James C. Owings
1989	J	`jnl`	On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case. Ann. Pure Appl. Log. Richard Beigel, William I. Gasarch
1989	J	`jnl`	On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case. Ann. Pure Appl. Log. Richard Beigel, William I. Gasarch
1989	—	`conf`	On the Power of Probabilistic Polynomial Time: P SCT Richard Beigel, Lane A. Hemachandra, Gerd Wechsung
1989	—	`conf`	On the Relativized Power of Additional Accepting Paths. SCT Richard Beigel
1989	J	`jnl`	Primitive recursion without implicit predecessor. SIGACT News Michael J. Fischer, Robert P. Fischer, Richard Beigel
1987	—	`conf`	A structural theorem that depends quantitatively on the complexity of SAT. SCT Richard Beigel
1987	—	`—`	Query-limited reducibilities. Richard Beigel