- Paul Beame, Raphaël
Clifford, and Widad Machmouchi.
Element
distinctness, frequency moments, and sliding windows.
In Proceedings 54th Annual Symposium on Foundations of Computer
Science, pages 290-299, Berkeley, CA, October 2013. IEEE.
- Paul Beame, Chris
Beck, and Russell Impagliazzo.
Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear
space.
In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of
Computing, pages 212-232, New York, NY, May 2012.
- Paul Beame and Widad
Machmouchi.
Making
branching programs oblivious requires superlogarithmic overhead.
In Proceedings Twenty-Sixth Annual IEEE Conference on Computational
Complexity, pages 12-22, San Jose, CA, June 2011.
- Paul Beame, Chris
Beck, and Russell Impagliazzo.
Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear
space.
Technical Report TR11-149, Electronic Colloquium in Computational Complexity,
November 2011.
- Paul Beame and
Widad Machmouchi.
Making branching programs
oblivious requires superlogarithmic overhead.
Technical Report TR10-104, Electronic Colloquium in Computational Complexity,
2010.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Time-space trade-off lower bounds for randomized computation of decision problems.
Journal of the ACM, 50(2):154-195, 2003.
- Paul Beame and Erik Vee.
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor
problems.
In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of
Computing, pages 688-697, Montreal, Quebec, Canada, May 2002.
- Paul Beame,
T. S. Jayram, and Michael Saks.
Time-space
tradeoffs for branching programs.
Journal of Computer and System Sciences, 63(4):542-572, December
2001.
Special issue of selected papers from 1998 FOCS Conference.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Super-linear time-space tradeoff lower bounds for randomized computation.
In Proceedings 41st Annual Symposium on Foundations of Computer
Science, pages 169-179, Redondo Beach, CA, November 2000. IEEE.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Super-linear time-space tradeoff lower bounds for randomized computation.
Technical Report TR00-025, Electronic Colloquium in Computational Complexity,
2000.
- Paul Beame, Allan Borodin,
Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
A time-space
tradeoff for undirected graph traversal by walking automata.
SIAM Journal on Computing, 28(3):1051-1072, 1999.
- Paul Beame, Michael
Saks, and Jayram S. Thathachar.
Time-space tradeoffs for branching programs.
In Proceedings 39th Annual Symposium on Foundations of Computer
Science, pages 254-263, Palo Alto, CA, November 1998. IEEE.
- Paul Beame,
Michael Saks, and Jayram S. Thathachar.
Time-space tradeoffs for branching programs.
Technical Report TR98-053, Electronic Colloquium in Computational Complexity,
1998.
- Paul Beame, Allan Borodin,
Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space
tradeoffs for undirected graph traversal by graph automata.
Information and Computation, 130(2):101-129, November 1996.
- Paul Beame, Martin
Tompa, and Peiyuan Yan.
Communication-space tradeoffs for unrestricted protocols.
SIAM Journal on Computing, 23(3):652-661, 1994.
- Paul Beame, Allan
Borodin, Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space
tradeoffs for undirected graph traversal.
Technical Report UW-CSE-93-02-01, Department of Computer Science and
Engineering, University of Washington, February 1993.
- Paul Beame.
A general
sequential time-space tradeoff for finding unique elements.
SIAM Journal on Computing, 20(2):270-277, 1991.
- Paul Beame, Allan
Borodin, Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space tradeoffs for undirected graph traversal.
In Proceedings 31st Annual Symposium on Foundations of Computer
Science, pages 429-438, St. Louis, MO, October 1990. IEEE.
- Paul Beame,
Martin Tompa, and Peiyuan Yan.
Communication-space tradeoffs for unrestricted protocols.
In Proceedings 31st Annual Symposium on Foundations of Computer
Science, pages 420-428, St. Louis, MO, October 1990. IEEE.
- Paul Beame.
A
general sequential time-space tradeoff for finding unique elements.
In Proceedings of the Twenty-First Annual ACM Symposium on Theory of
Computing, pages 197-203, Seattle, WA, May 1989.

- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Skew in parallel query processing.
In Proceedings of the Thirty-Third Annual ACM Symposium on Principles of
Database Systems, pages 212-223, Snowbird, UT, June 2014.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Skew in parallel query processing.
CoRR, abs/1401.1872, 2014.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Communication steps for parallel query processing.
In Proceedings of the Thirty-Second Annual ACM Symposium on Principles of
Database Systems, pages 273-284, New York, NY, June 2013.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Communication steps for parallel query
processing.
CoRR, abs/1306.5972, 2013.
- Paul Beame
and Trinh Huynh.
Multiparty communication complexity and threshold circuit size of AC
^{0}. SIAM Journal on Computing, 41(3):484-518, 2012. - Paul Beame and
Trinh Huynh.
On
the value of multiple read/write streams for approximating frequency
moments.
ACM Transactions on Computation Theory, 3(2):6.1-6.22, 2011.
- Paul Beame,
Matei David, Toniann Pitassi, and Philipp Woelfel.
Separating
deterministic from nondeterministic NOF multiparty communication
complexity.
Theory of Computing, 6:201-225, 2010.
- Paul Beame, Trinh Huynh,
and Toniann Pitassi.
Hardness amplification in proof complexity.
In Proceedings of the Forty-Second Annual ACM Symposium on Theory of
Computing, pages 87-96, Cambridge, MA, June 2010.
- Paul Beame
and Dang-Trinh Huynh-Ngoc.
Multiparty communication complexity and threshold circuit size of AC
^{0}. In Proceedings 50th Annual Symposium on Foundations of Computer Science, pages 53-62, Atlanta, GA, October 2009. IEEE. - Paul Beame, Trinh
Huynh, and Toniann Pitassi.
Hardness amplification in proof complexity.
Technical Report TR09-072, Electronic Colloquium in Computational Complexity,
2009.
- Paul Beame and
Dang-Trinh Huynh-Ngoc.
On the value
of multiple read/write streams for approximating frequency moments.
In Proceedings 49th Annual Symposium on Foundations of Computer
Science, pages 499-508, Philadelphia, PA, October 2008. IEEE.
- Paul Beame
and Dang-Trinh Huynh-Ngoc.
On the
value of multiple read/write streams for approximating frequency moments.
Technical Report TR08-024, Electronic Colloquium in Computational Complexity,
2008.
- Paul Beame, Matei David,
Toniann Pitassi, and Philipp Woelfel.
Separating deterministic from nondeterministic NOF multiparty communication
complexity.
In Automata, Languages, and Programming: 34th International
Colloquium, pages 134-145, 2007.
- Paul Beame, T. S.
Jayram, and Atri Rudra.
Lower
bounds for randomized read/write stream algorithms.
In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of
Computing, pages 689-698, San Diego, CA, June 2007.
- Paul Beame,
Toniann Pitassi, Nathan Segerlind, and Avi Wigderson.
A
strong direct product theorem for corruption and the multiparty communication
complexity of set disjointness.
Computational Complexity, 15(4):391-432, 2006.
Invited submission for special issue on CCC 2005.
- Paul Beame, Toniann
Pitassi, Nathan Segerlind, and Avi Wigderson.
A direct sum
theorem for corruption and the multiparty NOF communication complexity of
set disjointness.
In Proceedings Twentieth Annual IEEE Conference on Computational
Complexity, pages 52-66, 2005.
- Paul Beame and Joan Lawry.
Randomized versus nondeterministic communication complexity.
In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of
Computing, pages 188-199, Victoria, B.C., Canada, May 1992.

- Paul Beame and Ashish
Sabharwal.
Non-restarting SAT solvers with simple preprocessing can efficiently simulate
resolution.
In Proceedings, AAAI-14: Twenty-Eighth National Conference on Artificial
Intelligence, Quebec City, Canada, July 2014. American Association for
Artificial Intelligence.
To appear.
- Paul Beame, Chris
Beck, and Russell Impagliazzo.
Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear
space.
In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of
Computing, pages 212-232, New York, NY, May 2012.
- Paul Beame, Chris
Beck, and Russell Impagliazzo.
Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear
space.
Technical Report TR11-149, Electronic Colloquium in Computational Complexity,
November 2011.
- Paul Beame, Trinh Huynh,
and Toniann Pitassi.
Hardness amplification in proof complexity.
In Proceedings of the Forty-Second Annual ACM Symposium on Theory of
Computing, pages 87-96, Cambridge, MA, June 2010.
- Paul Beame,
Russell Impagliazzo, Toniann Pitassi, and Nathan Segerlind.
Formula caching in DPLL.
ACM Transactions on Computation Theory, 1(3):9:1-33, March
2010.
- Paul Beame, Trinh
Huynh, and Toniann Pitassi.
Hardness amplification in proof complexity.
Technical Report TR09-072, Electronic Colloquium in Computational Complexity,
2009.
- Paul Beame,
Russell Impagliazzo, and Ashish Sabharwal.
The
resolution complexity of independent sets and vertex covers in random
graphs.
Computational Complexity, 16(3):245-297, 2007.
- Paul Beame,
Toniann Pitassi, and Nathan Segerlind.
Lower bounds for Lovász-Schrijver systems and beyond follow from
multiparty communication complexity.
SIAM Journal on Computing, 37(3):845-869, 2007.
- Tian Sang, Paul Beame, and
Henry Kautz.
A dynamic approach for MPE and Weighted MAX-SAT.
In Proceedings of the 20th International Joint Conference in Artificial
Intelligence (IJCAI), pages 173-179, Hyderabad, India, January
2007.
- Paul Beame, Russell
Impagliazzo, Toniann Pitassi, and Nathan Segerlind.
Formula caching in DPLL.
Technical Report TR06-140, Electronic Colloquium in Computational Complexity,
2006.
- Paul Beame, Joe
Culberson, David Mitchell, and Cristopher Moore.
The
resolution complexity of random graph k-colorability.
Discrete Applied Mathematics, 153:25-47, 2005.
- Paul Beame, Toniann
Pitassi, and Nathan Segerlind.
Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty
communication complexity.
In Automata, Languages, and Programming: 32nd International
Colloquium, pages 1176-1188, 2005.
- Tian Sang, Paul Beame,
and Henry Kautz.
Heuristics for fast exact model counting.
In Fahiem Bacchus and Toby Walsh, editors, SAT, volume 3569 of
Lecture Notes in Computer Science, pages 226-240. Springer,
2005.
- Tian Sang, Paul Beame, and
Henry Kautz.
Performing Bayesian inference by weighted model counting.
In Proceedings, AAAI-05: Twentieth National Conference on Artificial
Intelligence, pages 475-482, Pittsburgh, PA, August 2005. American
Association for Artificial Intelligence.
- Dimitris
Achlioptas, Paul Beame, and Michael Molloy.
Exponential bounds for DPLL below the satisfiability threshold.
In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 139-140, New Orleans, LA, January 2004.
- Dimitris
Achlioptas, Paul Beame, and Michael Molloy.
A sharp
threshold in proof complexity yields lower bounds for satisfiability
search.
Journal of Computer and System Sciences, 68(2):238-268, March
2004.
Special issue of invited papers from STOC 2001 conference.
- Paul Beame.
Proof
complexity.
In Steven Rudich and Avi Wigderson, editors, Computational Complexity
Theory, volume 10 of IAS/Park City mathematics series,
pages 199-246. American Mathematical Society, 2004.
- Paul Beame, Henry
Kautz, and Ashish Sabharwal.
Towards understanding and harnessing the potential of clause learning.
Journal of Artificial Intelligence Research, 22:319-351, 2004.
Honorable mention (sole runner up) 2008 IJCAI-JAIR Best Paper Prize.
- Joshua
Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, and Ashish Sabharwal.
Bounded-depth Frege lower bounds for weaker pigeonhole principles.
SIAM Journal on Computing, 34(2):261-276, 2004.
- Tian Sang, Fahiem
Bacchus, Paul Beame, Henry Kautz, and Toniann Pitassi.
Combining
component caching and clause learning for effective model counting.
In SAT 2004, Satisfiability Conference, pages 20-28, 2004.
- Paul Beame, Russell
Impagliazzo, Toniann Pitassi, and Nathan Segerlind.
Memoization and DPLL: Formula caching proof systems.
In Proceedings Eighteenth Annual IEEE Conference on Computational
Complexity, pages 225-236, Aarhus, Denmark, July 2003.
- Paul Beame, Henry Kautz,
and Ashish Sabharwal.
On the
power of clause learning.
In Proceedings of the 18th International Joint Conference in Artificial
Intelligence (IJCAI), pages 94-99, Acapulco, Mexico, August 2003.
- Paul Beame,
Richard Karp, Toniann Pitassi, and Michael Saks.
The
efficiency of resolution and Davis-Putnam procedures.
SIAM Journal on Computing, 31(4):1048-1075, 2002.
- Joshua
Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, and Ashish Sabharwal.
Bounded-depth Frege lower bounds for weaker pigeonhole principles.
In Proceedings 43rd Annual Symposium on Foundations of Computer
Science, pages 583-592, Vancouver, B.C., Canada, November 2002.
IEEE.
- Dimitris Achlioptas,
Paul Beame, and Michael Molloy.
A
sharp threshold in proof complexity.
In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of
Computing, pages 337-346, Heraklion, Crete, Greece, July 2001.
- Paul Beame and
Toniann Pitassi.
Propositional Proof Complexity: Past, Present, and Future.
In G. Paun, G. Rozenberg, and A. Salomaa, editors, Current Trends in
Theoretical Computer Science: Entering the 21st Century, pages 42-70.
World Scientific Publishing, 2001.
- Paul Beame, Russell
Impagliazzo, and Ashish Sabharwal.
The
resolution complexity of the independent set problem in random graphs.
In Proceedings Sixteenth Annual IEEE Conference on Computational
Complexity, pages 52-68, Chicago, IL, June 2001.
- Paul Beame and
Samuel R. Buss, editors.
Proof Complexity and Feasible Arithmetics, volume 39 of
DIMACS Series in Discrete Mathematics and Theoretical Computer
Science.
American Mathematical Society, 1998.
- Paul Beame and
Toniann Pitassi.
Propositional Proof Complexity: Past, Present, and Future.
Bulletin of the European Association for Theoretical Computer
Science, 65, June 1998.
The Computational Complexity Column (ed. E. Allender).
- Paul Beame and Søren
Riis.
More on the
relative strength of counting principles.
In Paul W. Beame and Samuel R. Buss, editors, Proof Complexity and
Feasible Arithmetics, volume 39 of DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, pages 13-35. American
Mathematical Society, 1998.
- Paul Beame,
Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi.
The
relative complexity of NP search problems.
Journal of Computer and System Sciences, 57:3-19, 1998.
Special issue of invited papers from 1995 STOC conference.
- Paul Beame, Richard Karp,
Toniann Pitassi, and Michael Saks.
On the
complexity of unsatisfiability of random k-CNF formulas.
In Proceedings of the 30th Annual ACM Symposium on Theory of
Computing, pages 561-571, Dallas, TX, May 1998.
- Paul Beame and
Toniann Pitassi.
An
exponential separation between the parity principle and the pigeonhole
principle.
Annals of Pure and Applied Logic, 80:197-222, 1996.
- Paul Beame and
Toniann Pitassi.
Simplified and improved resolution lower bounds.
In Proceedings 37th Annual Symposium on Foundations of Computer
Science, pages 274-282, Burlington, VT, October 1996. IEEE.
- Paul Beame,
Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, and Pavel
Pudlák.
Lower
bounds on Hilbert's Nullstellensatz and propositional proofs.
Proc. London Math. Soc., 73(3):1-26, 1996.
- Paul Beame, Stephen A.
Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi.
The
relative complexity of NP search problems.
In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of
Computing, pages 303-314, Las Vegas, NV, May 1995.
- Paul Beame, Russell
Impagliazzo, Jan Krajícek, Toniann Pitassi, and Pavel Pudlák.
Lower
bounds on Hilbert's Nullstellensatz and propositional proofs.
In Proceedings 35th Annual Symposium on Foundations of Computer
Science, pages 794-806, Santa Fe, NM, November 1994. IEEE.
- Paul Beame and Toniann
Pitassi.
An
exponential separation between the matching principle and the pigeonhole
principle.
In 8th Annual IEEE Symposium on Logic in Computer Science, pages
308-319, Montreal, Quebec, June 1993.
- Toniann Pitassi, Paul Beame,
and Russell Impagliazzo.
Exponential
lower bounds for the pigeonhole principle.
Computational Complexity, 3(2):97-140, 1993.
- Paul Beame, Russell
Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, and
Alan Woods.
Exponential lower bounds for the pigeonhole principle.
In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of
Computing, pages 200-220, Victoria, B.C., Canada, May 1992.

- Paul Beame and
Faith Fich.
Optimal bounds for the predecessor problem and related problems.
Journal of Computer and System Sciences, 65(1):38-72, August
2002.
Special issue of selected papers from 1999 STOC conference.
- Paul Beame and Erik Vee.
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor
problems.
In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of
Computing, pages 688-697, Montreal, Quebec, Canada, May 2002.
- Paul Beame and Faith Fich.
Optimal
bounds for the predecessor problem.
In Proceedings of the Thirty-First Annual ACM Symposium on Theory of
Computing, pages 295-304, Atlanta, GA, May 1999.
- Paul Beame and Faith
Fich.
On searching sorted lists: A near-optimal lower bound.
Technical Report UW-CSE-97-09-02, Department of Computer Science and
Engineering, University of Washington, April 1997.

- Paul Beame, Russell
Impagliazzo, and Srikanth Srinivasan.
Approximating AC
^{0}circuits by small height decision trees and a deterministic algorithm for AC^{0}-SAT. In Proceedings Twenty-Seventh Annual IEEE Conference on Computational Complexity, pages 117-125, Porto, Portugal, June 2012. - Paul Beame and
Pierre McKenzie.
A note on
Neciporuk's method for nondeterministic branching programs.
Draft, 2011.
- Paul Beame
and Dang-Trinh Huynh-Ngoc.
Multiparty communication complexity and threshold circuit size of AC
^{0}. In Proceedings 50th Annual Symposium on Foundations of Computer Science, pages 53-62, Atlanta, GA, October 2009. IEEE. - Paul
Beame and Dang-Trinh Huynh-Ngoc.
Multiparty communication complexity and threshold circuit complexity of
AC
^{0}. Technical Report TR08-082, Electronic Colloquium in Computational Complexity, 2008. - Paul Beame,
Russell Impagliazzo, and Toniann Pitassi.
Improved depth bounds for small distance connectivity.
Computational Complexity, 7(4):325-345, 1998.
- Paul Beame, Faith E.
Fich, and Rakesh Sinha.
Separating the power of EREW and CREW PRAMs with small communication
width.
Information and Computation, 138(1):89-99, October 1997.
- Paul Beame, Russell
Impagliazzo, and Toniann Pitassi.
Improved
depth bounds for small distance connectivity.
In Proceedings 36th Annual Symposium on Foundations of Computer
Science, pages 692-701, Milwaukee, WI, October 1995. IEEE.
- Paul Beame.
A switching
lemma primer.
Technical Report UW-CSE-95-07-01, Department of Computer Science and
Engineering, University of Washington, November 1994.
- Paul Beame, Marcin Kik,
and Mirek Kutylowski.
Information broadcasting by exclusive read PRAMs.
Parallel Processing Letters, 4(1&2):159-169, 1994.
- Paul Beame, Faith E. Fich,
and Rakesh Sinha.
Separating
the power of EREW and CREW PRAMs with small communication width.
In Proceedings of the 1993 Workshop on Algorithms and Data
Structures, pages 163-174, 1993.
- Paul Beame.
Lower
bounds for recognizing small cliques on CRCW PRAM's.
Discrete Applied Mathematics, 29(1):3-20, 1990.
Special issue on the applications of combinatorics to parallel computation.
- Paul Beame and Johan
Håstad.
Optimal bounds for decision problems on the CRCW PRAM.
Journal of the ACM, 36(3):643-670, July 1989.
- Paul Beame.
Limits on
the power of concurrent-write parallel machines.
Information and Computation, 76(1):13-28, January 1988.
- Paul Beame and Johan
Håstad.
Optimal
bounds for decision problems on the CRCW PRAM.
In Proceedings of the Nineteenth Annual ACM Symposium on Theory of
Computing, pages 83-93, New York, NY, May 1987.
- Paul Beame.
Limits
on the power of concurrent-write parallel machines.
In Proceedings of the Eighteenth Annual ACM Symposium on Theory of
Computing, pages 169-176, Berkeley, CA, May 1986.
- Paul W. Beame.
Lower Bounds in Parallel Machine Computation.
PhD thesis, University of Toronto, 1986.
Department of Computer Science Technical Report 198/87.

- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Skew in parallel query processing.
In Proceedings of the Thirty-Third Annual ACM Symposium on Principles of
Database Systems, pages 212-223, Snowbird, UT, June 2014.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Skew in parallel query processing.
CoRR, abs/1401.1872, 2014.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Communication steps for parallel query processing.
In Proceedings of the Thirty-Second Annual ACM Symposium on Principles of
Database Systems, pages 273-284, New York, NY, June 2013.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Communication steps for parallel query
processing.
CoRR, abs/1306.5972, 2013.
- Richard J.
Anderson, Paul Beame, and Eric Brisson.
Parallel algorithms for arrangements.
Algorithmica, 15(2):104-125, 1996.
Special issue of invited papers from 1990 SPAA conference.
- Paul Beame, Eric Brisson, and
Richard E. Ladner.
The
complexity of computing symmetric functions using threshold circuits.
Theoretical Computer Science, 100:253-265, 1992.
- Richard J. Anderson,
Paul Beame, and Eric Brisson.
Parallel algorithms for arrangements.
In Proceedings of the 1990 ACM Symposium on Parallel Algorithms and
Architectures, pages 298-306, Crete, Greece, June 1990.
- Richard J. Anderson,
Paul Beame, and Walter L. Ruzzo.
Low overhead
parallel schedules for task graphs.
In Proceedings of the 1990 ACM Symposium on Parallel Algorithms and
Architectures, pages 66-75, Crete, Greece, June 1990.
- Paul Beame and Hans
Bodlaender.
Distributed
computing on transitive networks: The torus.
In STACS 89: 6th Annual Symposium on Theoretical Aspects of Computer
Science, volume 349 of Lecture Notes in Computer Science,
pages 294-303, Bordeaux, France, February 1989. Springer-Verlag.
- Paul W. Beame, Stephen A. Cook,
and H. James Hoover.
Log
depth circuits for division and related problems.
SIAM Journal on Computing, 15(4):994-1003, November 1986.
- Paul W. Beame, Stephen A. Cook,
and H. James Hoover.
Log
depth circuits for division and related problems.
In 25th Annual Symposium on Foundations of Computer Science, pages
1-6, Singer Island, FL, November 1984. IEEE.

- W. Chan, R. J.
Anderson, P. Beame, D. J. Jones, D. Notkin, and W. E Warner.
Optimizing
symbolic model-checking for statecharts.
IEEE Transactions on Software Engineering, 27(2):170-190, 2001.
Special section of invited papers from 21st International Conference on
Software Engineering.
- Richard J. Anderson,
William Chan, Paul Beame, and David Notkin.
Experiences with the application of symbolic model checking to the analysis of
software specifications.
In Proceedings of the Andrei Ershov Third International Conference on
Perspectives of System Informatics, pages 355-361, Novosibirsk,
Russia, 1999.
- W. Chan, R. J. Anderson,
P. Beame, D. J. Jones, D. Notkin, and W. E Warner.
Decoupling
synchronization from logic for efficient symbolic model checking of
statecharts.
In Proceedings of the 21st International Conference on Software
Engineering, pages 142-151, April 1999.
- W. Chan, R. J. Anderson,
P. Beame, S. Burns, F. Modugno, D. Notkin, and J. D. Reese.
Model checking large software specifications.
IEEE Transactions on Software Engineering, 24(7):498-520, July
1998.
Special section of invited papers from 4th Foundations in Software Engineering
Conference.
- W. Chan, R. J. Anderson,
P. Beame, and D. Notkin.
Improving
efficiency of symbolic model checking for state-based system
requirements.
In M. Young, editor, ISSTA 98: Proceedings of the ACM SIGSOFT
International Symposium on Software Testing and Analysis, pages
102-112, Clearwater Beach, FL, March 1998.
Published as
*Software Engineering Notes*, 23(2), March 1998. - W. Chan, R. J. Anderson,
P. Beame, and D. Notkin.
Combining
constraint solving and symbolic model checking for a class of systems with
non-linear constraints.
In O. Grumberg, editor, Computer Aided Verification, 9th International
Conference, CAV'97 Proceedings, volume 1254 of Lecture Notes in
Computer Science, pages 316-327, Haifa, Israel, June 1997.
Springer-Verlag.
- R. J. Anderson,
P. Beame, S. Burns, W. Chan, F. Modugno, D. Notkin, and J. D. Reese.
Model
checking large software specifications.
In D. Garlan, editor, Proceedings of the 4th ACM SIGSOFT Symposium on the
Foundations of Software Engineering, pages 156-166, San Francisco,
CA, October 1996.
Also published as
*Software Engineering Notes*, 21(6), November 1996.

- Paul Beame, Jerry Li,
Sudeepa Roy, and Dan Suciu.
Model counting of query expressions: Limitations of propositional methods.
In Proceedings of 17th International Conference on Database
Theory, pages 177-188, March 2014.
- Paul Beame, Jerry Li,
Sudeepa Roy, and Dan Suciu.
Lower
bounds for exact model counting and applications in probabilistic
databases.
In Proceedings 29th Conference on Uncertainty in Artificial
Intelligence, pages 52-61, Bellevue, WA, July 2013.
- Paul Beame and Widad
Machmouchi.
The
quantum query complexity of AC
^{0}. Quantum Information & Computation, 12(7-8):670-676, 2012. - Paul Beame and
Widad Machmouchi.
The quantum query complexity of
AC
^{0}. Technical Report arXiv:1008.2422v1, arxiv/quant-phys, 2010. - Paul Beame, Eric
Blais, and Dang-Trinh Huynh-Ngoc.
Longest common subsequences in sets of
permutations.
Technical Report arXiv:0904.1615, arxiv/math.co, 2009.
- Paul Beame and Paul Muir.
On error expressions for reflected and averaged implicit Runge-Kutta methods.
BIT, 29:126-139, 1989.
- Paul W. Beame.
Random routing in constant degree networks.
Master's thesis, Department of Computer Science, University of Toronto, 1982.
Technical Report 161/82.

- Paul Beame and Ashish
Sabharwal.
Non-restarting SAT solvers with simple preprocessing can efficiently simulate
resolution.
In Proceedings, AAAI-14: Twenty-Eighth National Conference on Artificial
Intelligence, Quebec City, Canada, July 2014. American Association for
Artificial Intelligence.
To appear.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Skew in parallel query processing.
In Proceedings of the Thirty-Third Annual ACM Symposium on Principles of
Database Systems, pages 212-223, Snowbird, UT, June 2014.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Skew in parallel query processing.
CoRR, abs/1401.1872, 2014.
- Paul Beame, Jerry Li,
Sudeepa Roy, and Dan Suciu.
Model counting of query expressions: Limitations of propositional methods.
In Proceedings of 17th International Conference on Database
Theory, pages 177-188, March 2014.
- Paul Beame, Raphaël
Clifford, and Widad Machmouchi.
Element
distinctness, frequency moments, and sliding windows.
In Proceedings 54th Annual Symposium on Foundations of Computer
Science, pages 290-299, Berkeley, CA, October 2013. IEEE.
- Paul Beame,
Raphaël Clifford, and Widad Machmouchi.
Element distinctness, frequency
moments, and sliding windows.
CoRR, abs/1309.3690, 2013.
Also Technical Report TR13-127, Electronic Colloquium in Computational
Complexity available at http://eccc.hpi-web.de/report/2013/127.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Communication steps for parallel query processing.
In Proceedings of the Thirty-Second Annual ACM Symposium on Principles of
Database Systems, pages 273-284, New York, NY, June 2013.
- Paul Beame, Paraschos
Koutris, and Dan Suciu.
Communication steps for parallel query
processing.
CoRR, abs/1306.5972, 2013.
- Paul Beame, Jerry Li,
Sudeepa Roy, and Dan Suciu.
Lower
bounds for exact model counting and applications in probabilistic
databases.
In Proceedings 29th Conference on Uncertainty in Artificial
Intelligence, pages 52-61, Bellevue, WA, July 2013.
- Paul Beame
and Trinh Huynh.
Multiparty communication complexity and threshold circuit size of AC
^{0}. SIAM Journal on Computing, 41(3):484-518, 2012. - Paul Beame and Widad
Machmouchi.
The
quantum query complexity of AC
^{0}. Quantum Information & Computation, 12(7-8):670-676, 2012. - Paul Beame, Chris
Beck, and Russell Impagliazzo.
Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear
space.
In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of
Computing, pages 212-232, New York, NY, May 2012.
- Paul Beame,
Raphaël Clifford, and Widad Machmouchi.
Sliding windows with limited
storage.
CoRR, abs/1212.4372, 2012.
Also Technical Report TR12-178, Electronic Colloquium in Computational
Complexity available at
http://eccc.uni-trier.de/eccc-reports/2012/TR12-178/index.html.
- Paul Beame, Russell
Impagliazzo, and Srikanth Srinivasan.
Approximating AC
^{0}circuits by small height decision trees and a deterministic algorithm for AC^{0}-SAT. In Proceedings Twenty-Seventh Annual IEEE Conference on Computational Complexity, pages 117-125, Porto, Portugal, June 2012. - Paul Beame and
Trinh Huynh.
On
the value of multiple read/write streams for approximating frequency
moments.
ACM Transactions on Computation Theory, 3(2):6.1-6.22, 2011.
- Paul Beame and Widad
Machmouchi.
Making
branching programs oblivious requires superlogarithmic overhead.
In Proceedings Twenty-Sixth Annual IEEE Conference on Computational
Complexity, pages 12-22, San Jose, CA, June 2011.
- Paul Beame and
Pierre McKenzie.
A note on
Neciporuk's method for nondeterministic branching programs.
Draft, 2011.
- Paul Beame, Chris
Beck, and Russell Impagliazzo.
Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear
space.
Technical Report TR11-149, Electronic Colloquium in Computational Complexity,
November 2011.
- Paul Beame and
Widad Machmouchi.
Making branching programs
oblivious requires superlogarithmic overhead.
Technical Report TR10-104, Electronic Colloquium in Computational Complexity,
2010.
- Paul Beame and
Widad Machmouchi.
The quantum query complexity of
AC
^{0}. Technical Report arXiv:1008.2422v1, arxiv/quant-phys, 2010. - Paul Beame,
Matei David, Toniann Pitassi, and Philipp Woelfel.
Separating
deterministic from nondeterministic NOF multiparty communication
complexity.
Theory of Computing, 6:201-225, 2010.
- Paul Beame, Trinh Huynh,
and Toniann Pitassi.
Hardness amplification in proof complexity.
In Proceedings of the Forty-Second Annual ACM Symposium on Theory of
Computing, pages 87-96, Cambridge, MA, June 2010.
- Paul Beame,
Russell Impagliazzo, Toniann Pitassi, and Nathan Segerlind.
Formula caching in DPLL.
ACM Transactions on Computation Theory, 1(3):9:1-33, March
2010.
- Paul Beame
and Dang-Trinh Huynh-Ngoc.
Multiparty communication complexity and threshold circuit size of AC
^{0}. In Proceedings 50th Annual Symposium on Foundations of Computer Science, pages 53-62, Atlanta, GA, October 2009. IEEE. - Paul Beame, Eric
Blais, and Dang-Trinh Huynh-Ngoc.
Longest common subsequences in sets of
permutations.
Technical Report arXiv:0904.1615, arxiv/math.co, 2009.
- Paul Beame, Trinh
Huynh, and Toniann Pitassi.
Hardness amplification in proof complexity.
Technical Report TR09-072, Electronic Colloquium in Computational Complexity,
2009.
- Paul
Beame and Dang-Trinh Huynh-Ngoc.
Multiparty communication complexity and threshold circuit complexity of
AC
^{0}. Technical Report TR08-082, Electronic Colloquium in Computational Complexity, 2008. - Paul Beame and
Dang-Trinh Huynh-Ngoc.
On the value
of multiple read/write streams for approximating frequency moments.
In Proceedings 49th Annual Symposium on Foundations of Computer
Science, pages 499-508, Philadelphia, PA, October 2008. IEEE.
- Paul Beame
and Dang-Trinh Huynh-Ngoc.
On the
value of multiple read/write streams for approximating frequency moments.
Technical Report TR08-024, Electronic Colloquium in Computational Complexity,
2008.
- Paul Beame, Matei David,
Toniann Pitassi, and Philipp Woelfel.
Separating deterministic from nondeterministic NOF multiparty communication
complexity.
In Automata, Languages, and Programming: 34th International
Colloquium, pages 134-145, 2007.
- Paul Beame,
Russell Impagliazzo, and Ashish Sabharwal.
The
resolution complexity of independent sets and vertex covers in random
graphs.
Computational Complexity, 16(3):245-297, 2007.
- Paul Beame, T. S.
Jayram, and Atri Rudra.
Lower
bounds for randomized read/write stream algorithms.
In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of
Computing, pages 689-698, San Diego, CA, June 2007.
- Paul Beame,
Toniann Pitassi, and Nathan Segerlind.
Lower bounds for Lovász-Schrijver systems and beyond follow from
multiparty communication complexity.
SIAM Journal on Computing, 37(3):845-869, 2007.
- Tian Sang, Paul Beame, and
Henry Kautz.
A dynamic approach for MPE and Weighted MAX-SAT.
In Proceedings of the 20th International Joint Conference in Artificial
Intelligence (IJCAI), pages 173-179, Hyderabad, India, January
2007.
- Paul Beame,
Russell Impagliazzo, Toniann Pitassi, and Nathan Segerlind.
Formula caching in DPLL.
Technical Report TR06-140, Electronic Colloquium in Computational Complexity,
2006.
- Paul Beame,
Toniann Pitassi, Nathan Segerlind, and Avi Wigderson.
A
strong direct product theorem for corruption and the multiparty communication
complexity of set disjointness.
Computational Complexity, 15(4):391-432, 2006.
Invited submission for special issue on CCC 2005.
- Paul Beame, Joe
Culberson, David Mitchell, and Cristopher Moore.
The
resolution complexity of random graph k-colorability.
Discrete Applied Mathematics, 153:25-47, 2005.
- Paul Beame, Toniann
Pitassi, and Nathan Segerlind.
Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty
communication complexity.
In Automata, Languages, and Programming: 32nd International
Colloquium, pages 1176-1188, 2005.
- Paul Beame, Toniann
Pitassi, Nathan Segerlind, and Avi Wigderson.
A direct sum
theorem for corruption and the multiparty NOF communication complexity of
set disjointness.
In Proceedings Twentieth Annual IEEE Conference on Computational
Complexity, pages 52-66, 2005.
- Tian Sang, Paul Beame,
and Henry Kautz.
Heuristics for fast exact model counting.
In Fahiem Bacchus and Toby Walsh, editors, SAT, volume 3569 of
Lecture Notes in Computer Science, pages 226-240. Springer,
2005.
- Tian Sang, Paul Beame, and
Henry Kautz.
Performing Bayesian inference by weighted model counting.
In Proceedings, AAAI-05: Twentieth National Conference on Artificial
Intelligence, pages 475-482, Pittsburgh, PA, August 2005. American
Association for Artificial Intelligence.
- Dimitris
Achlioptas, Paul Beame, and Michael Molloy.
Exponential bounds for DPLL below the satisfiability threshold.
In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 139-140, New Orleans, LA, January 2004.
- Dimitris
Achlioptas, Paul Beame, and Michael Molloy.
A sharp
threshold in proof complexity yields lower bounds for satisfiability
search.
Journal of Computer and System Sciences, 68(2):238-268, March
2004.
Special issue of invited papers from STOC 2001 conference.
- Paul Beame.
Proof
complexity.
In Steven Rudich and Avi Wigderson, editors, Computational Complexity
Theory, volume 10 of IAS/Park City mathematics series,
pages 199-246. American Mathematical Society, 2004.
- Paul Beame, Henry
Kautz, and Ashish Sabharwal.
Towards understanding and harnessing the potential of clause learning.
Journal of Artificial Intelligence Research, 22:319-351, 2004.
Honorable mention (sole runner up) 2008 IJCAI-JAIR Best Paper Prize.
- Joshua
Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, and Ashish Sabharwal.
Bounded-depth Frege lower bounds for weaker pigeonhole principles.
SIAM Journal on Computing, 34(2):261-276, 2004.
- Tian Sang, Fahiem
Bacchus, Paul Beame, Henry Kautz, and Toniann Pitassi.
Combining
component caching and clause learning for effective model counting.
In SAT 2004, Satisfiability Conference, pages 20-28, 2004.
- Paul Beame, Russell
Impagliazzo, Toniann Pitassi, and Nathan Segerlind.
Memoization and DPLL: Formula caching proof systems.
In Proceedings Eighteenth Annual IEEE Conference on Computational
Complexity, pages 225-236, Aarhus, Denmark, July 2003.
- Paul Beame, Henry Kautz,
and Ashish Sabharwal.
On the
power of clause learning.
In Proceedings of the 18th International Joint Conference in Artificial
Intelligence (IJCAI), pages 94-99, Acapulco, Mexico, August 2003.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Time-space trade-off lower bounds for randomized computation of decision problems.
Journal of the ACM, 50(2):154-195, 2003.
- Paul Beame and
Faith Fich.
Optimal bounds for the predecessor problem and related problems.
Journal of Computer and System Sciences, 65(1):38-72, August
2002.
Special issue of selected papers from 1999 STOC conference.
- Paul Beame and Erik Vee.
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor
problems.
In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of
Computing, pages 688-697, Montreal, Quebec, Canada, May 2002.
- Paul Beame,
Richard Karp, Toniann Pitassi, and Michael Saks.
The
efficiency of resolution and Davis-Putnam procedures.
SIAM Journal on Computing, 31(4):1048-1075, 2002.
- Joshua
Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, and Ashish Sabharwal.
Bounded-depth Frege lower bounds for weaker pigeonhole principles.
In Proceedings 43rd Annual Symposium on Foundations of Computer
Science, pages 583-592, Vancouver, B.C., Canada, November 2002.
IEEE.
- Dimitris Achlioptas,
Paul Beame, and Michael Molloy.
A
sharp threshold in proof complexity.
In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of
Computing, pages 337-346, Heraklion, Crete, Greece, July 2001.
- Paul Beame and
Toniann Pitassi.
Propositional Proof Complexity: Past, Present, and Future.
In G. Paun, G. Rozenberg, and A. Salomaa, editors, Current Trends in
Theoretical Computer Science: Entering the 21st Century, pages 42-70.
World Scientific Publishing, 2001.
- Paul Beame, Russell
Impagliazzo, and Ashish Sabharwal.
The
resolution complexity of the independent set problem in random graphs.
In Proceedings Sixteenth Annual IEEE Conference on Computational
Complexity, pages 52-68, Chicago, IL, June 2001.
- Paul Beame,
T. S. Jayram, and Michael Saks.
Time-space
tradeoffs for branching programs.
Journal of Computer and System Sciences, 63(4):542-572, December
2001.
Special issue of selected papers from 1998 FOCS Conference.
- W. Chan, R. J.
Anderson, P. Beame, D. J. Jones, D. Notkin, and W. E Warner.
Optimizing
symbolic model-checking for statecharts.
IEEE Transactions on Software Engineering, 27(2):170-190, 2001.
Special section of invited papers from 21st International Conference on
Software Engineering.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Super-linear time-space tradeoff lower bounds for randomized computation.
In Proceedings 41st Annual Symposium on Foundations of Computer
Science, pages 169-179, Redondo Beach, CA, November 2000. IEEE.
- Paul Beame,
Michael Saks, Xiaodong Sun, and Erik Vee.
Super-linear time-space tradeoff lower bounds for randomized computation.
Technical Report TR00-025, Electronic Colloquium in Computational Complexity,
2000.
- Richard J. Anderson,
William Chan, Paul Beame, and David Notkin.
Experiences with the application of symbolic model checking to the analysis of
software specifications.
In Proceedings of the Andrei Ershov Third International Conference on
Perspectives of System Informatics, pages 355-361, Novosibirsk,
Russia, 1999.
- Paul Beame and Faith Fich.
Optimal
bounds for the predecessor problem.
In Proceedings of the Thirty-First Annual ACM Symposium on Theory of
Computing, pages 295-304, Atlanta, GA, May 1999.
- Paul Beame, Allan Borodin,
Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
A time-space
tradeoff for undirected graph traversal by walking automata.
SIAM Journal on Computing, 28(3):1051-1072, 1999.
- W. Chan, R. J. Anderson,
P. Beame, D. J. Jones, D. Notkin, and W. E Warner.
Decoupling
synchronization from logic for efficient symbolic model checking of
statecharts.
In Proceedings of the 21st International Conference on Software
Engineering, pages 142-151, April 1999.
- Paul Beame and
Samuel R. Buss, editors.
Proof Complexity and Feasible Arithmetics, volume 39 of
DIMACS Series in Discrete Mathematics and Theoretical Computer
Science.
American Mathematical Society, 1998.
- Paul Beame and
Toniann Pitassi.
Propositional Proof Complexity: Past, Present, and Future.
Bulletin of the European Association for Theoretical Computer
Science, 65, June 1998.
The Computational Complexity Column (ed. E. Allender).
- Paul Beame and Søren
Riis.
More on the
relative strength of counting principles.
In Paul W. Beame and Samuel R. Buss, editors, Proof Complexity and
Feasible Arithmetics, volume 39 of DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, pages 13-35. American
Mathematical Society, 1998.
- Paul Beame,
Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi.
The
relative complexity of NP search problems.
Journal of Computer and System Sciences, 57:3-19, 1998.
Special issue of invited papers from 1995 STOC conference.
- Paul Beame,
Russell Impagliazzo, and Toniann Pitassi.
Improved depth bounds for small distance connectivity.
Computational Complexity, 7(4):325-345, 1998.
- Paul Beame, Richard Karp,
Toniann Pitassi, and Michael Saks.
On the
complexity of unsatisfiability of random k-CNF formulas.
In Proceedings of the 30th Annual ACM Symposium on Theory of
Computing, pages 561-571, Dallas, TX, May 1998.
- Paul Beame, Michael
Saks, and Jayram S. Thathachar.
Time-space tradeoffs for branching programs.
In Proceedings 39th Annual Symposium on Foundations of Computer
Science, pages 254-263, Palo Alto, CA, November 1998. IEEE.
- Paul Beame,
Michael Saks, and Jayram S. Thathachar.
Time-space tradeoffs for branching programs.
Technical Report TR98-053, Electronic Colloquium in Computational Complexity,
1998.
- W. Chan, R. J. Anderson,
P. Beame, S. Burns, F. Modugno, D. Notkin, and J. D. Reese.
Model checking large software specifications.
IEEE Transactions on Software Engineering, 24(7):498-520, July
1998.
Special section of invited papers from 4th Foundations in Software Engineering
Conference.
- W. Chan, R. J. Anderson,
P. Beame, and D. Notkin.
Improving
efficiency of symbolic model checking for state-based system
requirements.
In M. Young, editor, ISSTA 98: Proceedings of the ACM SIGSOFT
International Symposium on Software Testing and Analysis, pages
102-112, Clearwater Beach, FL, March 1998.
Published as
*Software Engineering Notes*, 23(2), March 1998. - Paul Beame and Faith
Fich.
On searching sorted lists: A near-optimal lower bound.
Technical Report UW-CSE-97-09-02, Department of Computer Science and
Engineering, University of Washington, April 1997.
- Paul Beame, Faith E.
Fich, and Rakesh Sinha.
Separating the power of EREW and CREW PRAMs with small communication
width.
Information and Computation, 138(1):89-99, October 1997.
- W. Chan, R. J. Anderson,
P. Beame, and D. Notkin.
Combining
constraint solving and symbolic model checking for a class of systems with
non-linear constraints.
In O. Grumberg, editor, Computer Aided Verification, 9th International
Conference, CAV'97 Proceedings, volume 1254 of Lecture Notes in
Computer Science, pages 316-327, Haifa, Israel, June 1997.
Springer-Verlag.
- R. J. Anderson,
P. Beame, S. Burns, W. Chan, F. Modugno, D. Notkin, and J. D. Reese.
Model
checking large software specifications.
In D. Garlan, editor, Proceedings of the 4th ACM SIGSOFT Symposium on the
Foundations of Software Engineering, pages 156-166, San Francisco,
CA, October 1996.
Also published as
*Software Engineering Notes*, 21(6), November 1996. - Richard J.
Anderson, Paul Beame, and Eric Brisson.
Parallel algorithms for arrangements.
Algorithmica, 15(2):104-125, 1996.
Special issue of invited papers from 1990 SPAA conference.
- Paul Beame and
Toniann Pitassi.
An
exponential separation between the parity principle and the pigeonhole
principle.
Annals of Pure and Applied Logic, 80:197-222, 1996.
- Paul Beame and
Toniann Pitassi.
Simplified and improved resolution lower bounds.
In Proceedings 37th Annual Symposium on Foundations of Computer
Science, pages 274-282, Burlington, VT, October 1996. IEEE.
- Paul Beame, Allan Borodin,
Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space
tradeoffs for undirected graph traversal by graph automata.
Information and Computation, 130(2):101-129, November 1996.
- Paul Beame,
Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, and Pavel
Pudlák.
Lower
bounds on Hilbert's Nullstellensatz and propositional proofs.
Proc. London Math. Soc., 73(3):1-26, 1996.
- Paul Beame, Stephen A.
Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi.
The
relative complexity of NP search problems.
In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of
Computing, pages 303-314, Las Vegas, NV, May 1995.
- Paul Beame, Russell
Impagliazzo, and Toniann Pitassi.
Improved
depth bounds for small distance connectivity.
In Proceedings 36th Annual Symposium on Foundations of Computer
Science, pages 692-701, Milwaukee, WI, October 1995. IEEE.
- Paul Beame.
A switching
lemma primer.
Technical Report UW-CSE-95-07-01, Department of Computer Science and
Engineering, University of Washington, November 1994.
- Paul Beame, Russell
Impagliazzo, Jan Krajícek, Toniann Pitassi, and Pavel Pudlák.
Lower
bounds on Hilbert's Nullstellensatz and propositional proofs.
In Proceedings 35th Annual Symposium on Foundations of Computer
Science, pages 794-806, Santa Fe, NM, November 1994. IEEE.
- Paul Beame, Marcin
Kik, and Mirek Kutylowski.
Information broadcasting by exclusive read PRAMs.
Parallel Processing Letters, 4(1&2):159-169, 1994.
- Paul Beame, Martin
Tompa, and Peiyuan Yan.
Communication-space tradeoffs for unrestricted protocols.
SIAM Journal on Computing, 23(3):652-661, 1994.
- Paul Beame and Toniann
Pitassi.
An
exponential separation between the matching principle and the pigeonhole
principle.
In 8th Annual IEEE Symposium on Logic in Computer Science, pages
308-319, Montreal, Quebec, June 1993.
- Paul Beame, Allan
Borodin, Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space
tradeoffs for undirected graph traversal.
Technical Report UW-CSE-93-02-01, Department of Computer Science and
Engineering, University of Washington, February 1993.
- Paul Beame, Faith E. Fich,
and Rakesh Sinha.
Separating
the power of EREW and CREW PRAMs with small communication width.
In Proceedings of the 1993 Workshop on Algorithms and Data
Structures, pages 163-174, 1993.
- Toniann Pitassi, Paul Beame,
and Russell Impagliazzo.
Exponential
lower bounds for the pigeonhole principle.
Computational Complexity, 3(2):97-140, 1993.
- Paul Beame and Joan Lawry.
Randomized versus nondeterministic communication complexity.
In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of
Computing, pages 188-199, Victoria, B.C., Canada, May 1992.
- Paul Beame, Eric Brisson, and
Richard E. Ladner.
The
complexity of computing symmetric functions using threshold circuits.
Theoretical Computer Science, 100:253-265, 1992.
- Paul Beame, Russell
Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, and
Alan Woods.
Exponential lower bounds for the pigeonhole principle.
In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of
Computing, pages 200-220, Victoria, B.C., Canada, May 1992.
- Paul Beame.
A general
sequential time-space tradeoff for finding unique elements.
SIAM Journal on Computing, 20(2):270-277, 1991.
- Richard J. Anderson,
Paul Beame, and Eric Brisson.
Parallel algorithms for arrangements.
In Proceedings of the 1990 ACM Symposium on Parallel Algorithms and
Architectures, pages 298-306, Crete, Greece, June 1990.
- Richard J. Anderson,
Paul Beame, and Walter L. Ruzzo.
Low overhead
parallel schedules for task graphs.
In Proceedings of the 1990 ACM Symposium on Parallel Algorithms and
Architectures, pages 66-75, Crete, Greece, June 1990.
- Paul Beame.
Lower
bounds for recognizing small cliques on CRCW PRAM's.
Discrete Applied Mathematics, 29(1):3-20, 1990.
Special issue on the applications of combinatorics to parallel computation.
- Paul Beame, Allan
Borodin, Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa.
Time-space tradeoffs for undirected graph traversal.
In Proceedings 31st Annual Symposium on Foundations of Computer
Science, pages 429-438, St. Louis, MO, October 1990. IEEE.
- Paul Beame,
Martin Tompa, and Peiyuan Yan.
Communication-space tradeoffs for unrestricted protocols.
In Proceedings 31st Annual Symposium on Foundations of Computer
Science, pages 420-428, St. Louis, MO, October 1990. IEEE.
- Paul Beame.
A
general sequential time-space tradeoff for finding unique elements.
In Proceedings of the Twenty-First Annual ACM Symposium on Theory of
Computing, pages 197-203, Seattle, WA, May 1989.
- Paul Beame and Hans
Bodlaender.
Distributed
computing on transitive networks: The torus.
In STACS 89: 6th Annual Symposium on Theoretical Aspects of Computer
Science, volume 349 of Lecture Notes in Computer Science,
pages 294-303, Bordeaux, France, February 1989. Springer-Verlag.
- Paul Beame and Johan
Håstad.
Optimal bounds for decision problems on the CRCW PRAM.
Journal of the ACM, 36(3):643-670, July 1989.
- Paul Beame and Paul Muir.
On error expressions for reflected and averaged implicit Runge-Kutta methods.
BIT, 29:126-139, 1989.
- Paul Beame.
Limits on
the power of concurrent-write parallel machines.
Information and Computation, 76(1):13-28, January 1988.
- Paul Beame and Johan
Håstad.
Optimal
bounds for decision problems on the CRCW PRAM.
In Proceedings of the Nineteenth Annual ACM Symposium on Theory of
Computing, pages 83-93, New York, NY, May 1987.
- Paul Beame.
Limits
on the power of concurrent-write parallel machines.
In Proceedings of the Eighteenth Annual ACM Symposium on Theory of
Computing, pages 169-176, Berkeley, CA, May 1986.
- Paul W. Beame.
Lower Bounds in Parallel Machine Computation.
PhD thesis, University of Toronto, 1986.
Department of Computer Science Technical Report 198/87.
- Paul W. Beame, Stephen A. Cook,
and H. James Hoover.
Log
depth circuits for division and related problems.
SIAM Journal on Computing, 15(4):994-1003, November 1986.
- Paul W. Beame, Stephen A. Cook,
and H. James Hoover.
Log
depth circuits for division and related problems.
In 25th Annual Symposium on Foundations of Computer Science, pages
1-6, Singer Island, FL, November 1984. IEEE.
- Paul W. Beame.
Random routing in constant degree networks.
Master's thesis, Department of Computer Science, University of Toronto, 1982.
Technical Report 161/82.