Paul Beame

@inproceedings{bkw:qmatrix,

title = {Quantum Time-Space Tradeoffs for Matrix Problems},

author = {Paul Beame and Niels Kornerup and Michael Whitmeyer},

url = {https://dl.acm.org/doi/pdf/10.1145/3618260.3649700"},

doi = {10.1145/3618260.3649700},

year  = {2024},

date = {2024-06-01},

booktitle = {Proceedings of the Fifty-Sixth Annual ACM Symposium on Theory of Computing},

pages = {596–607},

address = {Vancouver, B.C., Canada},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bk:cumulative,

title = {Cumulative Memory Lower Bounds for Randomized and Quantum Computation},

author = {Paul Beame and Niels Kornerup},

url = {https://drops.dagstuhl.de/opus/volltexte/2023/18069/pdf/LIPIcs-ICALP-2023-17.pdf},

doi = {https://doi.org/10.4230/LIPIcs.ICALP.2023.17},

year  = {2023},

date = {2023-01-01},

booktitle = {Automata, Languages, and Programming: 50th International Colloquium (ICALP 2023)},

pages = {17:1-17:20},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bogy:learn,

title = {Time-Space Tradeoffs for Learning Finite Functions from 

Random Evaluations, with Applications to Polynomials},

author = {Paul Beame and Shayan Oveis Gharan and Xin Yang},

url = {http://proceedings.mlr.press/v75/beame18a.pdf},

year  = {2018},

date = {2018-07-01},

booktitle = {Proceedings of the 31st Conference on Learning Theory, COLT 2018},

pages = {843–856},

address = {Stockholm, Sweden},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{blp:median,

title = {Finding the Median (Obliviously) with Bounded Space},

author = {Paul Beame and Vincent Liew and Mihai Patrascu},

url = {http://www.cs.washington.edu/homes/beame/papers/icmedian.pdf},

year  = {2015},

date = {2015-01-01},

urldate = {2015-01-01},

booktitle = {Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I},

pages = {103–115},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bcm:windowsED,

title = {Element Distinctness, Frequency Moments, and Sliding Windows},

author = {Paul Beame and Raphaël Clifford and Widad Machmouchi},

url = {http://www.cs.washington.edu/homes/beame/papers/windows.pdf},

year  = {2013},

date = {2013-10-01},

booktitle = {Proceedings 54th Annual Symposium on Foundations of Computer Science},

pages = {290–299},

address = {Berkeley, CA},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bbi:proofspace,

title = {Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for 

 Superlinear Space},

author = {Paul Beame and Chris Beck and Russell Impagliazzo},

url = {http://www.cs.washington.edu/homes/beame/papers/proofspace.pdf},

year  = {2012},

date = {2012-05-01},

booktitle = {Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing},

pages = {212–232},

address = {New York, NY},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bm:robp,

title = {Making Branching Programs Oblivious Requires Superlogarithmic 

 Overhead},

author = {Paul Beame and Widad Machmouchi},

url = {http://www.cs.washington.edu/homes/beame/papers/robp-ccc.pdf},

year  = {2011},

date = {2011-06-01},

booktitle = {Proceedings Twenty-Sixth Annual IEEE Conference on Computational Complexity},

pages = {12–22},

address = {San Jose, CA},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bv:multibp,

title = {Time-Space Tradeoffs, Multiparty Communication 

 Complexity, and Nearest-Neighbor Problems},

author = {Paul Beame and Erik Vee},

url = {http://www.cs.washington.edu/homes/beame/papers/multibp.pdf},

year  = {2002},

date = {2002-05-01},

urldate = {2002-05-01},

booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing},

pages = {688-697},

address = {Montreal, Quebec, Canada},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bssv:randomts-focs,

title = {Super-linear Time-Space Tradeoff Lower Bounds for Randomized Computation},

author = {Paul Beame and Michael Saks and Xiaodong Sun and Erik Vee},

url = {http://www.cs.washington.edu/homes/beame/papers/superlinear.pdf},

year  = {2000},

date = {2000-11-01},

booktitle = {Proceedings 41st Annual Symposium on Foundations of Computer Science},

pages = {169–179},

address = {Redondo Beach, CA},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bst:tradeoff,

title = {Time-Space Tradeoffs for Branching Programs},

author = {Paul Beame and Michael Saks and Jayram S. Thathachar},

url = {http://www.cs.washington.edu/homes/beame/papers/focsbranch.pdf},

year  = {1998},

date = {1998-11-01},

booktitle = {Proceedings 39th Annual Symposium on Foundations of Computer Science},

pages = {254-263},

address = {Palo Alto, CA},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bbrrt:jag-focs,

title = {Time-Space Tradeoffs for Undirected Graph Traversal},

author = {Paul Beame and Allan Borodin and Prabhakar Raghavan and Walter L. Ruzzo and Martin Tompa},

url = {http://www.cs.washington.edu/homes/beame/papers/focsbags.pdf},

year  = {1990},

date = {1990-10-01},

booktitle = {Proceedings 31st Annual Symposium on Foundations of Computer Science},

pages = {429-438},

address = {St. Louis, MO},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bty:communication-focs,

title = {Communication-Space Tradeoffs for Unrestricted Protocols},

author = {Paul Beame and Martin Tompa and Peiyuan Yan},

url = {http://www.cs.washington.edu/homes/beame/papers/focscommspace.pdf},

year  = {1990},

date = {1990-10-01},

booktitle = {Proceedings 31st Annual Symposium on Foundations of Computer Science},

pages = {420-428},

address = {St. Louis, MO},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bea89,

title = {A General Sequential Time-Space Tradeoff for Finding Unique Elements},

author = {Paul Beame},

url = {http://www.cs.washington.edu/homes/beame/papers/stocsorting.pdf},

year  = {1989},

date = {1989-05-01},

booktitle = {Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing},

pages = {197-203},

address = {Seattle, WA},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bk:lift-itcs,

title = {On Disperser/Lifting Properties of the Index and Inner-Product Functions},

author = {Paul Beame and Sajin Koroth},

doi = {https://doi.org/10.4230/LIPIcs.ITCS.2023.14},

year  = {2023},

date = {2023-01-01},

booktitle = {14th Innovations in Theoretical Computer Science Conference, ITCS 

 2023, January 10–13, 2023, Cambridge, MA, USA},

volume = {251},

pages = {14:1-14:17},

publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},

series = {LIPIcs},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{br:simjoin,

title = {Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube},

author = {Paul Beame and Cyrus Rashtchian},

url = {http://www.cs.washington.edu/homes/beame/papers/simjoin-soda.pdf},

year  = {2017},

date = {2017-01-01},

booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},

pages = {289–306},

address = {Barcelona, ES},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{kbs:worst,

title = {Worst-Case Optimal Algorithms for Parallel Query Processing},

author = {Paraschos Koutris and Paul Beame and Dan Suciu},

url = {http://dx.doi.org/10.4230/LIPIcs.ICDT.2016.8},

year  = {2016},

date = {2016-03-01},

booktitle = {Proceedings of 19th International Conference on Database Theory},

pages = {8:1–8:18},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bks:skew-pods,

title = {Skew in Parallel Query Processing},

author = {Paul Beame and Paraschos Koutris and Dan Suciu},

url = {https://dl.acm.org/doi/10.1145/2594538.2594558},

year  = {2014},

date = {2014-06-01},

booktitle = {Proceedings of the Thirty-Third Annual ACM Symposium on Principles of Database Systems},

pages = {212–223},

address = {Snowbird, UT},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bks:mpc-pods,

title = {Communication Steps for Parallel Query Processing},

author = {Paul Beame and Paraschos Koutris and Dan Suciu},

url = {http://www.cs.washington.edu/homes/beame/papers/mpcpods.pdf},

year  = {2013},

date = {2013-06-01},

booktitle = {Proceedings of the Thirty-Second Annual ACM Symposium on Principles of Database Systems},

pages = {273–284},

address = {New York, NY},

note = {Winner of 2023 ACM PODS Alberto O. Mendelzon Test-of-Time Award.},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bh-n:multiparty,

title = {Multiparty Communication Complexity and Threshold Circuit Size of $AC^0$},

author = {Paul Beame and Dang-Trinh Huynh-Ngoc},

url = {http://www.cs.washington.edu/homes/beame/papers/focsmultiac0.pdf},

year  = {2009},

date = {2009-10-01},

urldate = {2009-10-01},

booktitle = {Proceedings 50th Annual Symposium on Foundations of Computer Science},

pages = {53–62},

address = {Atlanta, GA},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bh-n:freq,

title = {On the Value of Multiple Read/Write Streams for Approximating Frequency Moments},

author = {Paul Beame and Dang-Trinh Huynh-Ngoc},

url = {http://www.cs.washington.edu/homes/beame/papers/freq.pdf},

year  = {2008},

date = {2008-10-01},

booktitle = {Proceedings 49th Annual Symposium on Foundations of Computer Science},

pages = {499–508},

address = {Philadelphia, PA},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bjr:reversal,

title = {Lower Bounds for Randomized Read/Write Stream Algorithms},

author = {Paul Beame and T. S. Jayram and Atri Rudra},

url = {http://www.cs.washington.edu/homes/beame/papers/stream.pdf},

year  = {2007},

date = {2007-06-01},

booktitle = {Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing},

pages = {689–698},

address = {San Diego, CA},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bdpw:kparty,

title = {Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity},

author = {Paul Beame and Matei David and Toniann Pitassi and Philipp Woelfel},

url = {http://www.cs.washington.edu/homes/beame/papers/icalpkparty.pdf},

year  = {2007},

date = {2007-01-01},

booktitle = {Automata, Languages, and Programming: 34th International Colloquium (ICALP 2007)},

pages = {134–145},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bpsw:directsum,

title = {A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness},

author = {Paul Beame and Toniann Pitassi and Nathan Segerlind and Avi Wigderson},

url = {http://www.cs.washington.edu/homes/beame/papers/dsum.pdf},

year  = {2005},

date = {2005-01-01},

booktitle = {Proceedings Twentieth Annual IEEE Conference on Computational Complexity},

pages = {52–66},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bps:kfoldtseitin,

title = {Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity},

author = {Paul Beame and Toniann Pitassi and Nathan Segerlind},

url = {http://www.cs.washington.edu/homes/beame/papers/kfoldtseitin.pdf},

year  = {2005},

date = {2005-01-01},

booktitle = {Automata, Languages, and Programming: 32nd International Colloquium (ICALP 2005)},

pages = {1176–1188},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bv:multibp,

title = {Time-Space Tradeoffs, Multiparty Communication 

 Complexity, and Nearest-Neighbor Problems},

author = {Paul Beame and Erik Vee},

url = {http://www.cs.washington.edu/homes/beame/papers/multibp.pdf},

year  = {2002},

date = {2002-05-01},

urldate = {2002-05-01},

booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing},

pages = {688-697},

address = {Montreal, Quebec, Canada},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bl92,

title = {Randomized versus Nondeterministic Communication Complexity},

author = {Paul Beame and Joan Lawry},

url = {http://www.cs.washington.edu/homes/beame/papers/randomvsnondet.pdf},

year  = {1992},

date = {1992-05-01},

booktitle = {Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing},

pages = {188-199},

address = {Victoria, B.C., Canada},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{lbden:multiply,

title = {Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning},

author = {Vincent Liew and Paul Beame and Jo Devriendt and Jan Elfers and Jakob Nordström},

url = {http://www.cs.washington.edu/homes/beame/papers/nonlinear-cutting-planes.pdf},

doi = {https://doi.org/10.34727/2020/isbn.978-3-85448-042-6},

year  = {2020},

date = {2020-09-01},

booktitle = {Proceedings of the 20th Conference on Formal Methods in Computer Aided Design – FMCAD 2020},

pages = {194–204},

publisher = {TU Wein Academic Press},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bl:multiply,

title = {Towards Verifying Nonlinear Integer Arithmetic},

author = {Paul Beame and Vincent Liew},

url = {http://www.cs.washington.edu/homes/beame/papers/multiply.pdf},

year  = {2017},

date = {2017-07-01},

booktitle = {Computer Aided Verification, 29th International Conference, CAV'17 Proceedings, Part II},

pages = {238–258},

address = {Heidelberg, Germany},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{cabjnw:icse99,

title = {Decoupling Synchronization from Logic for Efficient 

 Symbolic Model Checking of Statecharts},

author = {W. Chan and R. J. Anderson and P. Beame and D. J. Jones and D. Notkin and W. E Warner},

url = {http://www.cs.washington.edu/homes/beame/papers/icse99.pdf},

year  = {1999},

date = {1999-04-01},

booktitle = {Proceedings of the 21st International Conference on Software Engineering},

pages = {142–151},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{acbn:siberia,

title = {Experiences with the Application of Symbolic Model Checking to the 

 Analysis of Software Specifications},

author = {Richard J. Anderson and William Chan and Paul Beame and David Notkin},

year  = {1999},

date = {1999-01-01},

booktitle = {Proceedings of the 

 Andrei Ershov Third International Conference on 

 Perspectives of System Informatics},

pages = {355-361},

address = {Novosibirsk, Russia},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{cabn:issta98,

title = {Improving Efficiency of Symbolic Model Checking for 

 State-Based System Requirements},

author = {W. Chan and R. J. Anderson and P. Beame and D. Notkin},

editor = {M. Young},

url = {http://www.cs.washington.edu/homes/beame/papers/issta98.pdf},

year  = {1998},

date = {1998-03-01},

booktitle = {ISSTA 98: Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis},

pages = {102–112},

address = {Clearwater Beach, FL},

crossref = {issta98},

note = {Published as textitSoftware Engineering Notes, 23(2), March1998},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{cabn:cav97,

title = {Combining Constraint Solving and Symbolic Model Checking 

 for a Class of Systems with Non-Linear Constraints},

author = {W. Chan and R. J. Anderson and P. Beame and D. Notkin},

editor = {O. Grumberg},

url = {http://www.cs.washington.edu/homes/beame/papers/cav97.pdf},

year  = {1997},

date = {1997-06-01},

booktitle = {Computer Aided Verification, 9th International Conference, CAV'97 Proceedings},

volume = {1254},

pages = {316–327},

publisher = {Springer-Verlag},

address = {Haifa, Israel},

series = {Lecture Notes in Computer Science},

crossref = {cav97},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{abbcmnr:fse,

title = {Model Checking Large Software Specifications},

author = {R. J. Anderson and P. Beame and S. Burns and W. Chan and F. Modugno and D. Notkin and J. D. Reese},

editor = {D. Garlan},

url = {http://www.cs.washington.edu/homes/beame/papers/fse.pdf},

year  = {1996},

date = {1996-10-01},

urldate = {1996-10-01},

booktitle = {Proceedings of the 4th ACM SIGSOFT Symposium on the Foundations of Software Engineering},

pages = {156–166},

address = {San Francisco, CA},

crossref = {fse96},

note = {Also published as textitSoftware Engineering Notes, 21(6), November 1996},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bk:lift-itcs,

title = {On Disperser/Lifting Properties of the Index and Inner-Product Functions},

author = {Paul Beame and Sajin Koroth},

doi = {https://doi.org/10.4230/LIPIcs.ITCS.2023.14},

year  = {2023},

date = {2023-01-01},

booktitle = {14th Innovations in Theoretical Computer Science Conference, ITCS 

 2023, January 10–13, 2023, Cambridge, MA, USA},

volume = {251},

pages = {14:1-14:17},

publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},

series = {LIPIcs},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{kbbn:dual,

title = {Adding Dual Variables to Algebraic Reasoning for Circuit Verification},

author = {Daniela Kaufmann and Paul Beame and Armin Biere and Jakob Nordström},

url = {http://www.cs.washington.edu/homes/beame/papers/dual-verify.pdf},

year  = {2022},

date = {2022-01-01},

booktitle = {Proceedings of 25th Design, Automation and Test in Europe (DATE)},

pages = {1435–1440},

publisher = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{lbden:multiply,

title = {Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning},

author = {Vincent Liew and Paul Beame and Jo Devriendt and Jan Elfers and Jakob Nordström},

url = {http://www.cs.washington.edu/homes/beame/papers/nonlinear-cutting-planes.pdf},

doi = {https://doi.org/10.34727/2020/isbn.978-3-85448-042-6},

year  = {2020},

date = {2020-09-01},

booktitle = {Proceedings of the 20th Conference on Formal Methods in Computer Aided Design – FMCAD 2020},

pages = {194–204},

publisher = {TU Wein Academic Press},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{svba:smooth,

title = {Smoothing Structured Decomposable Circuits},

author = {Andy Shih and Guy Van den Broeck and Paul Beame and Antoine Amarilli},

url = {http://www.cs.washington.edu/homes/beame/papers/smoothing-decomposable-circuits.pdf},

year  = {2019},

date = {2019-01-01},

booktitle = {Advances in Neural Information Processing Systems 32: Annual Conference 

 on Neural Information Processing Systems 2019, NeurIPS 2019},

pages = {11412–11422},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bfikppr:stabbing,

title = {Stabbing Planes},

author = {Paul Beame and Noah Fleming and Russell Impagliazzo and Antonina Kolokolova and Denis Pankratov and Toniann Pitassi and Robert Robere},

url = {http://drops.dagstuhl.de/opus/volltexte/2018/8341},

year  = {2018},

date = {2018-01-01},

booktitle = {Proceedings of the 9th Innovations in Theoretical 

 Computer Science Conference (ITCS 2018)},

volume = {94},

pages = {10:1–10:20},

series = {Leibniz International Proceedings in Informatics (LIPIcs)},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bl:multiply,

title = {Towards Verifying Nonlinear Integer Arithmetic},

author = {Paul Beame and Vincent Liew},

url = {http://www.cs.washington.edu/homes/beame/papers/multiply.pdf},

year  = {2017},

date = {2017-07-01},

booktitle = {Computer Aided Verification, 29th International Conference, CAV'17 Proceedings, Part II},

pages = {238–258},

address = {Heidelberg, Germany},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bl:sdd,

title = {New Limits for Knowledge Compilation and Applications to Exact Model Counting},

author = {Paul Beame and Vincent Liew},

url = {http://www.cs.washington.edu/homes/beame/papers/sdd.pdf},

year  = {2015},

date = {2015-07-01},

booktitle = {Proceedings 31st  Conference on Uncertainty in Artificial Intelligence},

pages = {131–140},

address = {Amsterdam},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bbgs:symm-pods,

title = {Symmetric Weighted First-Order Model Counting},

author = {Paul Beame and Guy Van Broeck and Eric Gribkoff and Dan Suciu},

url = {http://www.cs.washington.edu/homes/beame/papers/symm-count-pods.pdf},

year  = {2015},

date = {2015-06-01},

booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Principles of Database Systems},

pages = {313–328},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bs:cdcl,

title = {Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution},

author = {Paul Beame and Ashish Sabharwal},

url = {http://www.cs.washington.edu/homes/beame/papers/cdcdres.pdf},

year  = {2014},

date = {2014-07-01},

urldate = {2014-01-01},

booktitle = {Proceedings, AAAI-14: Twenty-Eighth National Conference on Artificial Intelligence},

pages = {2608–2615},

address = {Quebec City, Canada},

organization = {American Association for Artificial Intelligence},

crossref = {aaai14},

key = {AAAI-14},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{blrs:dldd-icdt,

title = {Model Counting of Query Expressions: Limitations of Propositional Methods},

author = {Paul Beame and Jerry Li and Sudeepa Roy and Dan Suciu},

url = {http://dx.doi.org/10.5441/002/icdt.2014.20},

year  = {2014},

date = {2014-03-01},

booktitle = {Proceedings of 17th International Conference on Database Theory},

pages = {177–188},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{blrs:dnnf-uai,

title = {Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases},

author = {Paul Beame and Jerry Li and Sudeepa Roy and Dan Suciu},

url = {http://www.cs.washington.edu/homes/beame/papers/uai13.pdf},

year  = {2013},

date = {2013-07-01},

booktitle = {Proceedings 29th  Conference on Uncertainty in Artificial Intelligence},

pages = {52–61},

address = {Bellevue, WA},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bbi:proofspace,

title = {Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for 

 Superlinear Space},

author = {Paul Beame and Chris Beck and Russell Impagliazzo},

url = {http://www.cs.washington.edu/homes/beame/papers/proofspace.pdf},

year  = {2012},

date = {2012-05-01},

booktitle = {Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing},

pages = {212–232},

address = {New York, NY},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{sbk:mpe,

title = {A dynamic approach for MPE and Weighted MAX-SAT},

author = {Tian Sang and Paul Beame and Henry Kautz},

doi = {10.5555/1625275.1625302},

year  = {2007},

date = {2007-01-01},

urldate = {2007-01-01},

booktitle = {Proceedings of the 20th International Joint Conference in 

 Artificial Intelligence (IJCAI)},

pages = {173–179},

address = {Hyderabad, India},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{sbk:bayes,

title = {Performing Bayesian Inference by Weighted Model Counting.},

author = {Tian Sang and Paul Beame and Henry Kautz},

doi = {10.5555/1619332.1619409},

year  = {2005},

date = {2005-08-01},

urldate = {2005-08-01},

booktitle = {Proceedings, AAAI-05: Twentieth National Conference on Artificial Intelligence},

pages = {475-482},

address = {Pittsburgh, PA},

organization = {American Association for Artificial Intelligence},

crossref = {aaai05},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bps:kfoldtseitin,

title = {Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity},

author = {Paul Beame and Toniann Pitassi and Nathan Segerlind},

url = {http://www.cs.washington.edu/homes/beame/papers/kfoldtseitin.pdf},

year  = {2005},

date = {2005-01-01},

booktitle = {Automata, Languages, and Programming: 32nd International Colloquium (ICALP 2005)},

pages = {1176–1188},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{sbk:heuristics,

title = {Heuristics for fast exact model counting},

author = {Tian Sang and Paul Beame and Henry Kautz},

editor = {Fahiem Bacchus and Toby Walsh},

url = {http://www.cs.washington.edu/homes/beame/papers/cachet-heuristics.pdf},

year  = {2005},

date = {2005-01-01},

booktitle = {Theory and Applications of Satisfiability Testing, 8th International Conference, SAT 2005, St Andrews, UK, June 2005. Proceedings},

volume = {3569},

pages = {226–240},

crossref = {SAT05},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{abm:hardsat,

title = {Exponential Bounds for DPLL Below the Satisfiability Threshold},

author = {Dimitris Achlioptas and Paul Beame and Michael Molloy},

url = {http://www.cs.washington.edu/homes/beame/papers/soda04.pdf},

year  = {2004},

date = {2004-01-01},

booktitle = {Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms},

pages = {139–140},

address = {New Orleans, LA},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{sbbkp:numsat,

title = {Combining Component Caching and Clause Learning for Effective Model Counting},

author = {Tian Sang and Fahiem Bacchus and Paul Beame and Henry Kautz and Toniann Pitassi},

url = {http://www.cs.washington.edu/homes/beame/papers/cachet.pdf},

year  = {2004},

date = {2004-01-01},

booktitle = {SAT 2004, Satisfiability Conference},

pages = {20–28},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bks:learn,

title = {On the power of clause learning},

author = {Paul Beame and Henry Kautz and Ashish Sabharwal},

url = {http://www.cs.washington.edu/homes/beame/papers/ijcai03.pdf},

year  = {2003},

date = {2003-08-01},

booktitle = {Proceedings of the 18th International Joint Conference in 

 Artificial Intelligence (IJCAI)},

pages = {94–99},

address = {Acapulco, Mexico},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bips:caching,

title = {Memoization and DPLL: Formula Caching Proof Systems},

author = {Paul Beame and Russell Impagliazzo and Toniann Pitassi and Nathan Segerlind},

url = {http://www.cs.washington.edu/homes/beame/papers/caching.pdf},

year  = {2003},

date = {2003-07-01},

booktitle = {Proceedings Eighteenth Annual IEEE Conference on Computational Complexity},

pages = {225–236},

address = {Aarhus, Denmark},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{sbk:learnsat,

title = {Using Problem Structure for Efficient Clause Learning},

author = {Ashish Sabharwal and Paul Beame and Henry Kautz},

url = {http://www.cs.washington.edu/homes/beame/papers/learnSAT03.pdf},

year  = {2003},

date = {2003-01-01},

booktitle = {Proceedings of the Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT 2003)},

pages = {159–166},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bbprs:wphp,

title = {Bounded-depth Frege lower bounds for weaker pigeonhole principles},

author = {Joshua Buresh-Oppenheim and Paul Beame and Toniann Pitassi and Ran Raz and Ashish Sabharwal},

url = {http://www.cs.washington.edu/homes/beame/papers/focswphp.pdf},

year  = {2002},

date = {2002-11-01},

booktitle = {Proceedings 43rd Annual Symposium on Foundations of Computer Science},

pages = {583–592},

address = {Vancouver, B.C., Canada},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{abm:2+psat,

title = {A sharp threshold in proof complexity},

author = {Dimitris Achlioptas and Paul Beame and Michael Molloy},

url = {http://www.cs.washington.edu/homes/beame/papers/stoc2plusp.pdf},

year  = {2001},

date = {2001-07-01},

booktitle = {Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing},

pages = {337–346},

address = {Heraklion, Crete, Greece},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bis:independent,

title = {The Resolution Complexity of the Independent Set Problem in Random Graphs},

author = {Paul Beame and Russell Impagliazzo and Ashish Sabharwal},

url = {http://www.cs.washington.edu/homes/beame/papers/cccindep.pdf},

year  = {2001},

date = {2001-06-01},

booktitle = {Proceedings Sixteenth Annual IEEE Conference on Computational Complexity},

pages = {52-68},

address = {Chicago, IL},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bkps:kcnf,

title = {On the complexity of unsatisfiability of random $k$-CNF formulas},

author = {Paul Beame and Richard Karp and Toniann Pitassi and Michael Saks},

url = {http://www.cs.washington.edu/homes/beame/papers/stockcnf.pdf},

year  = {1998},

date = {1998-05-01},

booktitle = {Proceedings of the 30th Annual ACM Symposium on Theory of Computing},

pages = {561-571},

address = {Dallas, TX},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bp:resolve,

title = {Simplified and Improved Resolution Lower Bounds},

author = {Paul Beame and Toniann Pitassi},

url = {http://www.cs.washington.edu/homes/beame/papers/focsclause.pdf},

year  = {1996},

date = {1996-10-01},

booktitle = {Proceedings 37th Annual Symposium on Foundations of Computer Science},

pages = {274–282},

address = {Burlington, VT},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bceip:search,

title = {The Relative Complexity of NP Search Problems},

author = {Paul Beame and Stephen A. Cook and Jeff Edmonds and Russell Impagliazzo and Toniann Pitassi},

url = {http://www.cs.washington.edu/homes/beame/papers/stocsearch.pdf},

year  = {1995},

date = {1995-05-01},

booktitle = {Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing},

pages = {303–314},

address = {Las Vegas, NV},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bikpp:nsatz,

title = {Lower bounds on Hilbert's Nullstellensatz and propositional proofs},

author = {Paul Beame and Russell Impagliazzo and Jan Krajíček and Toniann Pitassi and Pavel Pudlák},

url = {http://www.cs.washington.edu/homes/beame/papers/focsstell.pdf},

year  = {1994},

date = {1994-11-01},

booktitle = {Proceedings 35th Annual Symposium on Foundations of Computer Science},

pages = {794-806},

address = {Santa Fe, NM},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bp93,

title = {An Exponential Separation between the Matching Principle and the 

 Pigeonhole Principle},

author = {Paul Beame and Toniann Pitassi},

url = {http://www.cs.washington.edu/homes/beame/papers/licsmatch.pdf},

year  = {1993},

date = {1993-06-01},

booktitle = {8th Annual IEEE Symposium on Logic in Computer Science},

pages = {308–319},

address = {Montreal, Quebec},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bikppw92,

title = {Exponential Lower Bounds for the Pigeonhole Principle},

author = {Paul Beame and Russell Impagliazzo and Jan Krajíček and Toniann Pitassi and Pavel Pudlák and Alan Woods},

url = {http://www.cs.washington.edu/homes/beame/papers/stocphp.pdf},

year  = {1992},

date = {1992-05-01},

booktitle = {Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing},

pages = {200-220},

address = {Victoria, B.C., Canada},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{br:simjoin,

title = {Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube},

author = {Paul Beame and Cyrus Rashtchian},

url = {http://www.cs.washington.edu/homes/beame/papers/simjoin-soda.pdf},

year  = {2017},

date = {2017-01-01},

booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},

pages = {289–306},

address = {Barcelona, ES},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{kbs:worst,

title = {Worst-Case Optimal Algorithms for Parallel Query Processing},

author = {Paraschos Koutris and Paul Beame and Dan Suciu},

url = {http://dx.doi.org/10.4230/LIPIcs.ICDT.2016.8},

year  = {2016},

date = {2016-03-01},

booktitle = {Proceedings of 19th International Conference on Database Theory},

pages = {8:1–8:18},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bks:skew-pods,

title = {Skew in Parallel Query Processing},

author = {Paul Beame and Paraschos Koutris and Dan Suciu},

url = {https://dl.acm.org/doi/10.1145/2594538.2594558},

year  = {2014},

date = {2014-06-01},

booktitle = {Proceedings of the Thirty-Third Annual ACM Symposium on Principles of Database Systems},

pages = {212–223},

address = {Snowbird, UT},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bks:mpc-pods,

title = {Communication Steps for Parallel Query Processing},

author = {Paul Beame and Paraschos Koutris and Dan Suciu},

url = {http://www.cs.washington.edu/homes/beame/papers/mpcpods.pdf},

year  = {2013},

date = {2013-06-01},

booktitle = {Proceedings of the Thirty-Second Annual ACM Symposium on Principles of Database Systems},

pages = {273–284},

address = {New York, NY},

note = {Winner of 2023 ACM PODS Alberto O. Mendelzon Test-of-Time Award.},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{abb:arrange,

title = {Parallel Algorithms for Arrangements},

author = {Richard J. Anderson and Paul Beame and Eric Brisson},

url = {http://www.cs.washington.edu/homes/beame/papers/spaaarrange.pdf},

year  = {1990},

date = {1990-06-01},

booktitle = {Proceedings of the 1990 ACM Symposium on Parallel Algorithms and Architectures},

pages = {298-306},

address = {Crete, Greece},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{abr:tasks,

title = {Low Overhead Parallel Schedules for Task Graphs},

author = {Richard J. Anderson and Paul Beame and Walter L. Ruzzo},

url = {https://arxiv.org/abs/1401.1872},

year  = {1990},

date = {1990-06-01},

booktitle = {Proceedings of the 1990 ACM Symposium on Parallel Algorithms and Architectures},

pages = {66-75},

address = {Crete, Greece},

abstract = {Introduces a task scheduling model which is useful in the design and analysis of algorithms for small parallel machines. The authors prove that under their model, the overhead experienced in scheduling an n*n grid graph is O(log log n) for p processors, p>or=2. They also prove a matching lower bound of Omega (log logn) for p processors, p>or=2. They give an extension of the model to cover the case where the processors can have varying speed or are subject to delay.},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bl:mish,

title = {Parallel Search for Maximal Independence Given Minimal Dependence},

author = {Paul Beame and Michael Luby},

url = {https://dl.acm.org/doi/10.5555/320176.320200},

year  = {1990},

date = {1990-01-01},

urldate = {1990-01-01},

booktitle = {Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms},

pages = {212-218},

address = {San Francisco, CA},

organization = {ACM},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bb:torus,

title = {Distributed Computing on Transitive Networks: The Torus},

author = {Paul Beame and Hans Bodlaender},

url = {http://www.cs.washington.edu/homes/beame/papers/grid.ps 

http://link.springer.com/chapter/10.1007%2FBFb0028993},

year  = {1989},

date = {1989-02-01},

urldate = {1989-01-01},

booktitle = {STACS 89: 6th Annual Symposium on Theoretical Aspects of Computer Science},

volume = {349},

pages = {294-303},

publisher = {Springer-Verlag},

address = {Bordeaux, France},

series = {Lecture Notes in Computer Science},

crossref = {stacs89},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bch84,

title = {Log Depth Circuits for Division and Related Problems},

author = {Paul W. Beame and Stephen A. Cook and H. James Hoover},

url = {http://www.cs.washington.edu/homes/beame/papers/focsdivision.pdf},

year  = {1984},

date = {1984-11-01},

booktitle = {25th Annual Symposium on Foundations of Computer Science},

pages = {1-6},

publisher = {IEEE},

address = {Singer Island, FL},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bv:multibp,

title = {Time-Space Tradeoffs, Multiparty Communication 

 Complexity, and Nearest-Neighbor Problems},

author = {Paul Beame and Erik Vee},

url = {http://www.cs.washington.edu/homes/beame/papers/multibp.pdf},

year  = {2002},

date = {2002-05-01},

urldate = {2002-05-01},

booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing},

pages = {688-697},

address = {Montreal, Quebec, Canada},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bf:pred,

title = {Optimal Bounds for the Predecessor Problem},

author = {Paul Beame and Faith Fich},

url = {http://www.cs.washington.edu/homes/beame/papers/stocpred.pdf},

year  = {1999},

date = {1999-05-01},

urldate = {1999-05-01},

booktitle = {Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing},

pages = {295–304},

address = {Atlanta, GA},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bis:parity,

title = {Approximating $AC^0$ Circuits by Small Height Decision Trees 

 and a Deterministic Algorithm for $#AC^0$-SAT},

author = {Paul Beame and Russell Impagliazzo and Srikanth Srinivasan},

url = {http://www.cs.washington.edu/homes/beame/papers/ac0approx.pdf},

year  = {2012},

date = {2012-06-01},

booktitle = {Proceedings Twenty-Seventh Annual IEEE Conference on Computational Complexity},

pages = {117–125},

address = {Porto, Portugal},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bh-n:multiparty,

title = {Multiparty Communication Complexity and Threshold Circuit Size of $AC^0$},

author = {Paul Beame and Dang-Trinh Huynh-Ngoc},

url = {http://www.cs.washington.edu/homes/beame/papers/focsmultiac0.pdf},

year  = {2009},

date = {2009-10-01},

urldate = {2009-10-01},

booktitle = {Proceedings 50th Annual Symposium on Foundations of Computer Science},

pages = {53–62},

address = {Atlanta, GA},

organization = {IEEE},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bip:smallconn,

title = {Improved Depth Bounds for Small Distance Connectivity},

author = {Paul Beame and Russell Impagliazzo and Toniann Pitassi},

url = {http://www.cs.washington.edu/homes/beame/papers/focsconn.pdf},

year  = {1995},

date = {1995-10-01},

booktitle = {Proceedings 36th Annual Symposium on Foundations of Computer Science},

pages = {692-701},

publisher = {IEEE},

address = {Milwaukee, WI},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bfs:erew,

title = {Separating the Power of EREW and CREW PRAMs with Small Communication Width},

author = {Paul Beame and Faith E. Fich and Rakesh Sinha},

url = {http://www.cs.washington.edu/homes/beame/papers/crew.ps 

http://link.springer.com/chapter/10.1007%2F3-540-57155-8_245},

year  = {1993},

date = {1993-01-01},

booktitle = {Proceedings of the 1993 Workshop on Algorithms and Data Structures},

pages = {163-174},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bh87,

title = {Optimal Bounds for Decision Problems on the CRCW PRAM},

author = {Paul Beame and Johan Håstad},

url = {http://www.cs.washington.edu/homes/beame/papers/stoccrcw.pdf},

year  = {1987},

date = {1987-05-01},

booktitle = {Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing},

pages = {83-93},

address = {New York, NY},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bea86,

title = {Limits on the Power of Concurrent-Write Parallel Machines},

author = {Paul Beame},

url = {http://www.cs.washington.edu/homes/beame/papers/stoclimits.pdf},

year  = {1986},

date = {1986-05-01},

booktitle = {Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing},

pages = {169-176},

address = {Berkeley, CA},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{bhpnrrs:is-oracle,

title = {Edge Estimation with Independent Set Oracles},

author = {Paul Beame and Sariel Har-Peled and Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian and Makrand Sinha},

url = {http://drops.dagstuhl.de/opus/volltexte/2018/8355},

year  = {2018},

date = {2018-01-01},

booktitle = {Proceedings of the 9th Innovations in Theoretical 

 Computer Science Conference (ITCS 2018)},

volume = {94},

pages = {38:1–38:21},

series = {Leibniz International Proceedings in Informatics (LIPIcs)},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}