Contact
CSE 668
206-543-5114
beamecs.washington.edu
Areas of interest:
Computational complexity, proof complexity and satisfiability
2024
Quantum Time-Space Tradeoffs for Matrix Problems
Proceedings of the Fifty-Sixth Annual ACM Symposium on Theory of Computing, 2024: 596–607.
, Quantum Time-Space Tradeoffs for Matrix Problems
CoRR abs/2401.05321, 2024.
, Arxiv: http://arxiv.org/abs/2401.05321v2 also Electronic Colloquium on Computational Complexity (ECCC) TR24-011: http://eccc.weizmann.acl.il/report/2024/011/#revision1
2023
On Disperser/Lifting Properties of the Index and Inner-Product Functions
14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10–13, 2023, Cambridge, MA, USA, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 251, 2023: 14:1-14:17.
, Towards a Complexity Theory of Parallel Computation
Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook, Association for Computing Machinery, 2023: 107–126.
, Cumulative Memory Lower Bounds for Randomized and Quantum Computation
Automata, Languages, and Programming: 50th International Colloquium (ICALP 2023), 2023: 17:1-17:20.
, Cumulative Memory Lower Bounds for Randomized and Quantum Computation
CoRR abs/2301.05680, 2023.
, Arxiv: http://arxiv.org/abs/2301.05680 also Electronic Colloquium on Computational Complexity (ECCC) TR23-005: http://eccc.weizmann.acl.il/report/2023/005/
2022
On Disperser/Lifting Properties of the Index and Inner-Product Functions
CoRR abs/2211.17211, 2022.
, http://arxiv.org/abs/2211.17211 Arxiv
http://eccc.weizmann.ac.il/report/2022/173/index.html ECCC Technical Report TR22-173
Adding Dual Variables to Algebraic Reasoning for Circuit Verification
Proceedings of 25th Design, Automation and Test in Europe (DATE), IEEE, 2022: 1435–1440.
, 2020
Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning
Proceedings of the 20th Conference on Formal Methods in Computer Aided Design – FMCAD 2020, TU Wein Academic Press, 2020: 194–204.
, Edge Estimation with Independent Set Oracles
ACM Transactions on Algorithms 16:4, 2020: 52:1-52:27.
, On the Bias of Reed-Muller Codes over Odd Prime Fields
SIAM Journal on Discrete Mathematics 34:2, 2020: 1232–1247.
, Technical perspective: Two for the price of one
Communications of the ACM 63:10, 2020: 96.
, 2019
Toward Verifying Nonlinear Integer Arithmetic
Journal of the ACM 66:3, 2019: 22:1-30.
, Smoothing Structured Decomposable Circuits
Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 2019: 11412–11422.
, Smoothing Structured Decomposable Circuits
CoRR abs/1906.00311, 2019.
, 2018
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials
Proceedings of the 31st Conference on Learning Theory, COLT 2018, 2018: 843–856.
, Edge Estimation with Independent Set Oracles
Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 94, 2018: 38:1–38:21.
, Stabbing Planes
Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 94, 2018: 10:1–10:20.
, On the Bias of Reed-Muller Codes over Odd Prime Fields
CoRR abs/1806.06973, 2018.
, Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials
Electronic Colloquium in Computational Complexity:TR18-114, 2018.
, 2017
Communication Steps for Parallel Query Processing
Journal of the ACM 64:6, 2017: 40:1-58. Preliminary material in Proceedings of 2013 and 2014 ACM Symposium on Principles of Database Systems.
, Towards Verifying Nonlinear Integer Arithmetic
Computer Aided Verification, 29th International Conference, CAV'17 Proceedings, Part II, 2017: 238–258.
, Towards Verifying Nonlinear Integer Arithmetic
CoRR abs/1705.04302, 2017.
, Exact Model Counting of Query Expressions: Limitations of Propositional Methods
ACM Transactions on Database Systems 42:1, 2017: 1:1–45. Invited paper from 2014 International Conference on Database Theory (ICDT) combined with preliminary version in Proceedings of the 2013 Conference on Uncertainty in Artificial Intelligence (UAI).
, Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
Proceedings of the Twenty-Eighth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2017: 289–306.
, Stabbing Planes
CoRR abs/1710.03219, 2017. Also Technical Report TR17-151 # eccc # available at http://eccc.uni-trier.de/eccc-reports/2017/151/index.html
, http://arxiv.org/abs/1710.03219 Arxiv
http://eccc.uni-trier.de/eccc-reports/2017/151/index.html ECCC Technical Report TR17-151
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
CoRR abs/1708.02640, 2017. Also July 2017 Technical Report TR17-120 # eccc # available at http://eccc.uni-trier.de/eccc-reports/2017/120/index.html
, http://arxiv.org/abs/1708.02640 Arxiv
http://eccc.uni-trier.de/eccc-reports/2017/120/index.html ECCC Technical Report TR17-120
2016
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
CoRR abs/1611.04999, 2016.
, Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
CoRR abs/1608.01932, 2016.
, Worst-Case Optimal Algorithms for Parallel Query Processing
Proceedings of 19th International Conference on Database Theory, 2016: 8:1–8:18.
, Nondeterminism and an Abstract Formulation of Nečiporuk's Lower Bound Method
ACM Transactions on Computation Theory 9:1, 2016: 5:1–5:34.
, Worst-Case Optimal Algorithms for Parallel Query Processing
CoRR abs/1604.01848, 2016.
, Communication Cost in Parallel Query Processing
CoRR abs/1602.06236, 2016.
, Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
SIAM Journal on Computing 45:4, 2016: 1612–1645.
, 2015
New Limits for Knowledge Compilation and Applications to Exact Model Counting
Proceedings 31st Conference on Uncertainty in Artificial Intelligence, 2015: 131–140.
, Symmetric Weighted First-Order Model Counting
Proceedings of the Thirty-Fourth Annual ACM Symposium on Principles of Database Systems, 2015: 313–328.
, Finding the Median (Obliviously) with Bounded Space
Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, 2015: 103–115.
, Finding the Median (Obliviously) with Bounded Space
CoRR abs/1505.00090, 2015.
, New Limits for Knowledge Compilation and Applications to Exact Model Counting
CoRR abs/1506.02639, 2015.
, 2014
Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution
Proceedings, AAAI-14: Twenty-Eighth National Conference on Artificial Intelligence, American Association for Artificial Intelligence, 2014: 2608–2615.
, Skew in Parallel Query Processing
Proceedings of the Thirty-Third Annual ACM Symposium on Principles of Database Systems, 2014: 212–223.
, Model Counting of Query Expressions: Limitations of Propositional Methods
Proceedings of 17th International Conference on Database Theory, 2014: 177–188.
, Skew in Parallel Query Processing
CoRR abs/1401.1872, 2014.
, Symmetric Weighted First-Order Model Counting
CoRR abs/1506.02639, 2014.
, 2013
Element Distinctness, Frequency Moments, and Sliding Windows
Proceedings 54th Annual Symposium on Foundations of Computer Science, IEEE, 2013: 290–299.
, Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
Proceedings 29th Conference on Uncertainty in Artificial Intelligence, 2013: 52–61.
, Communication Steps for Parallel Query Processing
Proceedings of the Thirty-Second Annual ACM Symposium on Principles of Database Systems, 2013: 273–284. Winner of 2023 ACM PODS Alberto O. Mendelzon Test-of-Time Award.
, Element Distinctness, Frequency Moments, and Sliding Windows
CoRR abs/1309.3690, 2013. Also Technical Report TR13-127, # eccc # available at http://eccc.hpi-web.de/report/2013/127
, http://arxiv.org/abs/1309.3690 Arxiv
http://eccc.hpi-web.de/report/2013/127 ECCC Technical Report TR13-127
Communication Steps for Parallel Query Processing
CoRR abs/1306.5972, 2013.
, Model Counting of Query Expressions: Limitations of Propositional Methods
CoRR abs/1312.4125, 2013.
, 2012
Approximating $AC^0$ Circuits by Small Height Decision Trees and a Deterministic Algorithm for $\#AC^0$-SAT
Proceedings Twenty-Seventh Annual IEEE Conference on Computational Complexity, 2012: 117–125.
, Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012: 212–232.
, Multiparty Communication Complexity and Threshold Circuit Size of $AC^0$
SIAM Journal on Computing 41:3, 2012: 484–518.
, The Quantum Query Complexity of $AC^0$
Quantum Information \& Computation 12:7–8, 2012: 670–676.
, Sliding Windows with Limited Storage
CoRR abs/1212.4372, 2012. Also Technical Report TR12-178, # eccc # available at http://eccc.uni-trier.de/eccc-reports/2012/TR12-178/index.html
, http://arxiv.org/abs/1212.4372 Arxiv
http://eccc.uni-trier.de/eccc-reports/2012/TR12-178/index.html ECCC Technical Report TR12-178
2011
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
Electronic Colloquium in Computational Complexity:TR11-149, 2011.
, Making Branching Programs Oblivious Requires Superlogarithmic Overhead
Proceedings Twenty-Sixth Annual IEEE Conference on Computational Complexity, 2011: 12–22.
, On the value of multiple read/write streams for approximating frequency moments
ACM Transactions on Computation Theory, 2011.
, On the Value of Multiple Read/Write Streams for Approximating Frequency Moments
ACM Transactions on Computation Theory 3:2, 2011: 6.1–6.22.
, 2010
Hardness Amplification in Proof Complexity
Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing, 2010: 87–96.
, Formula Caching in DPLL
ACM Transactions on Computation Theory 1:3, 2010: 9:1-33.
, Separating Deterministic from Randomized Multiparty Communication Complexity
Theory of Computing 6, 2010: 201–225.
, The Quantum Query Complexity of $AC^0$
arxiv/quant-phys:arXiv:1008.2422v1, 2010.
, 2009
Multiparty Communication Complexity and Threshold Circuit Size of $AC^0$
Proceedings 50th Annual Symposium on Foundations of Computer Science, IEEE, 2009: 53–62.
, Longest Common Subsequences in Sets of Permutations
arxiv/math.co:arXiv:0904.1615, 2009.
, Hardness Amplification in Proof Complexity
Electronic Colloquium in Computational Complexity:TR09-072, 2009.
, 2008
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments
Proceedings 49th Annual Symposium on Foundations of Computer Science, IEEE, 2008: 499–508.
, Multiparty Communication Complexity and Threshold Circuit Complexity of $AC^0$
Electronic Colloquium in Computational Complexity:TR08-082, 2008.
, On the Value of Multiple Read/Write Streams for Approximating Frequency Moments
Electronic Colloquium in Computational Complexity:TR08-024, 2008.
, 2007
Lower Bounds for Randomized Read/Write Stream Algorithms
Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007: 689–698.
, A dynamic approach for MPE and Weighted MAX-SAT
Proceedings of the 20th International Joint Conference in Artificial Intelligence (IJCAI), 2007: 173–179.
, The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs
Computational Complexity 16:3, 2007: 245–297.
, Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
SIAM Journal on Computing 37:3, 2007: 845–869.
, Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
Automata, Languages, and Programming: 34th International Colloquium (ICALP 2007), 2007: 134–145.
, 2006
Formula Caching in DPLL
Electronic Colloquium in Computational Complexity:TR06-140, 2006.
, A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Set Disjointness
Computational Complexity 15:4, 2006: 391–432. Invited submission for special issue on CCC 2005.
, 2005
Performing Bayesian Inference by Weighted Model Counting.
Proceedings, AAAI-05: Twentieth National Conference on Artificial Intelligence, American Association for Artificial Intelligence, 2005: 475-482.
, Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
Electronic Colloquium in Computational Complexity:TR05-053, 2005.
, The Resolution Complexity of Random Graph $k$-Colorability
Discrete Applied Mathematics 153, 2005: 25–47.
, Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
Automata, Languages, and Programming: 32nd International Colloquium (ICALP 2005), 2005: 1176–1188.
, Heuristics for fast exact model counting
SAT, Springer 3569, 2005: 226–240.
, A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
Proceedings Twentieth Annual IEEE Conference on Computational Complexity, 2005: 52–66.
, 2004
A sharp threshold in proof complexity yields lower bounds for satisfiability search
Journal of Computer and System Sciences 68:2, 2004: 238–268. Special issue of invited papers from STOC 2001 conference
, Exponential Bounds for DPLL Below the Satisfiability Threshold
Proceedings of the Fifteenth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 2004: 139–140.
, The Resolution Complexity of Random Graph $k$-Colorability
Electronic Colloquium in Computational Complexity:TR04-012, 2004.
, Towards understanding and harnessing the potential of clause learning
Journal of Artificial Intelligence Research 22, 2004: 319–351. Honorable mention (sole runner up) 2008 IJCAI-JAIR Best Paper Prize
, Proof Complexity
Computational Complexity Theory, American Mathematical Society 10, 2004: 199–246.
, Combining Component Caching and Clause Learning for Effective Model Counting
SAT 2004, Satisfiability Conference, 2004: 20–28.
, A sharp threshold in proof complexity yields lower bounds for satisfiability search
Journal of Computer and System Sciences 68:2, 2004: 238–268.
, Bounded-depth Frege lower bounds for weaker pigeonhole principles
SIAM Journal on Computing 34:2, 2004: 261–276.
, 2003
On the power of clause learning
Proceedings of the 18th International Joint Conference in Artificial Intelligence (IJCAI), 2003: 94–99.
, Memoization and DPLL: Formula Caching Proof Systems
Proceedings Eighteenth Annual IEEE Conference on Computational Complexity, 2003: 225–236.
, Time-Space Trade-Off Lower Bounds for Randomized Computation of Decision Problems
Journal of the ACM 50:2, 2003: 154–195.
, Using Problem Structure for Efficient Clause Learning
Proceedings of the Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT 2003), 2003: 159–166.
, 2002
Bounded-depth Frege lower bounds for weaker pigeonhole principles
Proceedings 43rd Annual Symposium on Foundations of Computer Science, IEEE, 2002: 583–592.
, Optimal Bounds for the Predecessor Problem and Related Problems
Journal of Computer and System Sciences 65:1, 2002: 38–72. Special issue of selected papers from 1999 STOC conference.
, Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems
Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 2002: 688-697.
, Optimal Bounds for the Predecessor Problem and Related Problems
Journal of Computer and System Sciences 65:1, 2002: 38–72.
, Bounded-depth Frege lower bounds for weaker pigeonhole principles
Electronic Colloquium in Computational Complexity:TR02-023, 2002.
, The efficiency of resolution and Davis-Putnam procedures
SIAM Journal on Computing 31:4, 2002: 1048–1075.
, 2001
Time-Space Tradeoffs for Branching Programs
Journal of Computer and System Sciences 63:4, 2001: 542–572. Special issue of selected papers from 1998 FOCS Conference
, A sharp threshold in proof complexity
Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, 2001: 337–346.
, The Resolution Complexity of the Independent Set Problem in Random Graphs
Proceedings Sixteenth Annual IEEE Conference on Computational Complexity, 2001: 52-68.
, Propositional Proof Complexity: Past, Present, and Future
Current Trends in Theoretical Computer Science: Entering the 21st Century, World Scientific Publishing, 2001: 42–70.
, Optimizing Symbolic Model-Checking for Statecharts
IEEE Transactions on Software Engineering 27:2, 2001: 170–190. Special section of invited papers from 21st International Conference on Software Engineering
, 2000
Super-linear Time-Space Tradeoff Lower Bounds for Randomized Computation
Proceedings 41st Annual Symposium on Foundations of Computer Science, IEEE, 2000: 169–179.
, Super-linear Time-Space Tradeoff Lower Bounds for Randomized Computation
Electronic Colloquium in Computational Complexity:TR00-025, 2000.
, 1999
Optimal Bounds for the Predecessor Problem
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999: 295–304.
, Decoupling Synchronization from Logic for Efficient Symbolic Model Checking of Statecharts
Proceedings of the 21st International Conference on Software Engineering, 1999: 142–151.
, A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
SIAM Journal on Computing 28:3, 1999: 1051–1072.
, Experiences with the Application of Symbolic Model Checking to the Analysis of Software Specifications
Proceedings of the Andrei Ershov Third International Conference on Perspectives of System Informatics, 1999: 355-361.
, 1998
Time-Space Tradeoffs for Branching Programs
Proceedings 39th Annual Symposium on Foundations of Computer Science, IEEE, 1998: 254-263.
, Decoupling Synchronization from Logic for Efficient Symbolic Model Checking of Statecharts
Department of Computer Science and Engineering, University of Washington:UW-CSE-98-09-02, 1998.
, Model Checking Large Software Specifications
IEEE Transactions on Software Engineering 24:7, 1998: 498–520. Special section of invited papers from 4th Foundations in Software Engineering Conference
, Propositional Proof Complexity: Past, Present, and Future
Bulletin of the European Association for Theoretical Computer Science 65, 1998. The Computational Complexity Column (ed. E. Allender).
, On the complexity of unsatisfiability of random $k$-CNF formulas
Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998: 561-571.
, Improving Efficiency of Symbolic Model Checking for State-Based System Requirements
ISSTA 98: Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis, 1998: 102–112. Published as \textitSoftware Engineering Notes, 23(2), March 1998
, Improving Efficiency of Symbolic Model Checking for State-Based System Requirements
Department of Computer Science and Engineering, University of Washington:UW-CSE-98-01-03, 1998.
, More on the Relative Strength of Counting Principles
Proof Complexity and Feasible Arithmetics, American Mathematical Society 39, 1998: 13-35.
, Time-Space Tradeoffs for Branching Programs
Electronic Colloquium in Computational Complexity:TR98-053, 1998.
, Improved Depth Bounds for Small Distance Connectivity
Computational Complexity 7:4, 1998: 325–345.
, Proof Complexity and Feasible Arithmetics
, Proof Complexity and Feasible Arithmetics, American Mathematical Society 39, 1998.
The Relative Complexity of NP Search Problems
Journal of Computer and System Sciences 57, 1998: 3–19. Special issue of invited papers from 1995 STOC conference.
, 1997
Separating the Power of EREW and CREW PRAMs with Small Communication Width
Information and Computation 138:1, 1997: 89-99.
, Combining Constraint Solving and Symbolic Model Checking for a Class of Systems with Non-Linear Constraints
Computer Aided Verification, 9th International Conference, CAV'97 Proceedings, Springer-Verlag 1254, 1997: 316–327.
, On Searching Sorted Lists: A Near-Optimal Lower Bound
Department of Computer Science and Engineering, University of Washington:UW-CSE-97-09-02, 1997.
, 1996
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata
Information and Computation 130:2, 1996: 101-129.
, Model Checking Large Software Specifications
Proceedings of the 4th ACM SIGSOFT Symposium on the Foundations of Software Engineering, 1996: 156–166. Also published as \textitSoftware Engineering Notes, 21(6), November 1996
, Simplified and Improved Resolution Lower Bounds
Proceedings 37th Annual Symposium on Foundations of Computer Science, IEEE, 1996: 274–282.
, Model Checking Large Software Specifications
Department of Computer Science and Engineering, University of Washington:TR-96-04-02, 1996.
, Parallel Algorithms for Arrangements
Algorithmica 15:2, 1996: 104-125. Special issue of invited papers from 1990 SPAA conference
, http://www.cs.washington.edu/homes/beame/papers/arrangejournal.pdf preprint
http://link.springer.com/article/10.1007%2FBF01941684 journal link
An Exponential Separation between the Parity Principle and the Pigeonhole Principle
Annals of Pure and Applied Logic 80, 1996: 197-222.
, Lower bounds on Hilbert's Nullstellensatz and propositional proofs
Proc. London Math. Soc. 73:3, 1996: 1–26.
, 1995
Improved Depth Bounds for Small Distance Connectivity
Proceedings 36th Annual Symposium on Foundations of Computer Science, IEEE, 1995: 692-701.
, The Relative Complexity of NP Search Problems
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995: 303–314.
, 1994
Lower bounds on Hilbert's Nullstellensatz and propositional proofs
Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994: 794-806.
, A Switching Lemma Primer
Department of Computer Science and Engineering, University of Washington:UW-CSE-95–07–01, 1994.
, Communication-Space Tradeoffs for Unrestricted Protocols
SIAM Journal on Computing 23:3, 1994: 652-661.
, Information Broadcasting by Exclusive Read PRAMs
Parallel Processing Letters 4:1&2, 1994: 159-169.
, http://www.cs.washington.edu/homes/beame/papers/broadcast.ps preprint
http://www.worldscientific.com/doi/abs/10.1142/S012962649400017X journal link
1993
An Exponential Separation between the Matching Principle and the Pigeonhole Principle
8th Annual IEEE Symposium on Logic in Computer Science, 1993: 308–319.
, An Exponential Separation between the Matching Principle and the Pigeonhole Principle
Department of Computer Science and Engineering, University of Washington:UW-CSE-93-04-07, 1993.
, Time-Space Tradeoffs for Undirected Graph Traversal
Department of Computer Science and Engineering, University of Washington:UW-CSE-93–02–01, 1993.
, Exponential Lower Bounds for the Pigeonhole Principle
Computational Complexity 3:2, 1993: 97–140.
, Separating the Power of EREW and CREW PRAMs with Small Communication Width
Proceedings of the 1993 Workshop on Algorithms and Data Structures, 1993: 163-174.
, http://www.cs.washington.edu/homes/beame/papers/crew.ps preprint
http://link.springer.com/chapter/10.1007%2F3-540-57155-8_245 conference proceedings
1992
Exponential Lower Bounds for the Pigeonhole Principle
Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, 1992: 200-220.
, Randomized versus Nondeterministic Communication Complexity
Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, 1992: 188-199.
, The Complexity of Computing Symmetric Functions using Threshold Circuits
Theoretical Computer Science 100, 1992: 253-265.
, 1991
Exponential Lower Bounds for the Pigeonhole Principle
University of Toronto, Department of Computer Science:TR257/91, 1991.
, A General Sequential Time-Space Tradeoff for Finding Unique Elements
SIAM Journal on Computing 20:2, 1991: 270-277.
, 1990
Communication-Space Tradeoffs for Unrestricted Protocols
Proceedings 31st Annual Symposium on Foundations of Computer Science, IEEE, 1990: 420-428.
, Time-Space Tradeoffs for Undirected Graph Traversal
Proceedings 31st Annual Symposium on Foundations of Computer Science, IEEE, 1990: 429-438.
, Parallel Algorithms for Arrangements
Proceedings of the 1990 ACM Symposium on Parallel Algorithms and Architectures, 1990: 298-306.
, Low Overhead Parallel Schedules for Task Graphs
Proceedings of the 1990 ACM Symposium on Parallel Algorithms and Architectures, 1990: 66-75.
, Low Overhead Parallel Schedules for Task Graphs
Department of Computer Science and Engineering, University of Washington:UW-CSE-90-04-03, 1990.
, The Complexity of Computing Symmetric Functions using Threshold Circuits
Department of Computer Science and Engineering, University of Washington:UW-CSE-90-01-01, 1990.
, Parallel Search for Maximal Independence Given Minimal Dependence
Proceedings of the First Annual {ACM-SIAM} Symposium on Discrete Algorithms, ACM, 1990: 212-218.
, Communication-Space Tradeoffs for Unrestricted Protocols
Department of Computer Science and Engineering, University of Washington:UW-CSE-90-01-12, 1990.
, Lower Bounds for Recognizing Small Cliques on CRCW PRAM's
Discrete Applied Mathematics 29:1, 1990: 3-20. Special issue on the applications of combinatorics to parallel computation
, 1989
Parallel Algorithms for Arrangements
Department of Computer Science and Engineering, University of Washington:UW-CSE-89-12-08, 1989.
, Optimal Bounds for Decision Problems on the CRCW PRAM
Journal of the ACM 36:3, 1989: 643-670.
, A General Sequential Time-Space Tradeoff for Finding Unique Elements
Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, 1989: 197-203.
, Distributed Computing on Transitive Networks: The Torus
{STACS} 89: 6th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag 349, 1989: 294-303.
, http://www.cs.washington.edu/homes/beame/papers/grid.ps preprint
http://link.springer.com/chapter/10.1007%2FBFb0028993 conference proceedings link
Parallel Search for Maximal Independence Given Minimal Dependence
International Computer Science Institute:TR-89-003, 1989.
, On Error Expressions for Reflected and Averaged Implicit Runge-Kutta Methods
BIT 29, 1989: 126-139.
, 1988
A General Sequential Time-Space Tradeoff for Finding Unique Elements
Department of Computer Science and Engineering, University of Washington:UW-CSE-88-10-04, 1988.
, Limits on the Power of Concurrent-Write Parallel Machines
Information and Computation 76:1, 1988: 13-28.
, Distributed Computing on Transitive Networks: The Torus
Department of Computer Science, University of Utrecht:RUU-CS-88-31, 1988.
, 1987
Optimal Bounds for Decision Problems on the CRCW PRAM
Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987: 83-93.
, Lower Bounds for Recognizing Small Cliques on CRCW PRAM's
Laboratory for Computer Science, M.I.T.:TM–336, 1987.
, 1986
Log Depth Circuits for Division and Related Problems
SIAM Journal on Computing 15:4, 1986: 994-1003.
, Limits on the Power of Concurrent-Write Parallel Machines
Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 1986: 169-176.
, Lower Bounds in Parallel Machine Computation
University of Toronto, 1986. Department of Computer Science Technical Report 198/87
, 1984
Log Depth Circuits for Division and Related Problems
25th Annual Symposium on Foundations of Computer Science, IEEE, 1984: 1-6.
, 1982
Random Routing in Constant Degree Networks
Department of Computer Science, 1982. Technical Report 161/82
,