Paul Beame - Publications

Publications by date

Publications by topic:

Time-Space Tradeoffs

Proof Complexity and Satisfiability

Model Checking

Data Structures

Circuit and PRAM Lower Bounds

Parallel and Distributed Algorithms

Communication Complexity and other topics

Time-Space Tradeoff Lower Bounds

• 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 Computation 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 Computation 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.

Proof Complexity and Satisfiability

• 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, 2007. To appear.

• 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-149, Electronic Colloquium in Computation 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, Russell Impagliazzo, and Ashish Sabharwal. The resolution complexity of independent sets and vertex covers in random graphs. Computational Complexity, 2005. To appear.

• 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 on STOC 2001 conference.

• Paul Beame. Proof complexity. In Steven Rudich and Avi Wigdersom, 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.

• 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:66-89, 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.

Data Structures

• 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.

Software Model Checking

• 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.

Circuit and PRAM Lower Bounds

• 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.

Parallel and Distributed Algorithms

• Richard J. Anderson, Paul Beame, and Eric Brisson. Parallel algorithms for arrangements. Algorithmica, 15(2):104-125, 1996. Special issue 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.

Communication Complexity and other topics

• 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, 2007. To appear.

• 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, San Diego, CA, June 2007. To appear.

• 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, 2007. Invited submission for special issue on CCC 2005. To Appear.

• 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 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.

Publications by date

• 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, 2007. To appear.

• 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, San Diego, CA, June 2007. To appear.

• 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, 2007. To appear.

• 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, 2007. Invited submission for special issue on CCC 2005. To Appear.

• 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-149, Electronic Colloquium in Computation 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, Russell Impagliazzo, and Ashish Sabharwal. The resolution complexity of independent sets and vertex covers in random graphs. Computational Complexity, 2005. To appear.

• 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 on STOC 2001 conference.

• Paul Beame. Proof complexity. In Steven Rudich and Avi Wigdersom, 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.

• 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 Computation 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:66-89, 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 Computation 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 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.