The Evolution of Evolvability Simons Institute 2014-03-27 | Lee Altenberg, Konrad Lorenz Institute for Evolution and Cognition ResearchComputational Theories of Evolutionhttp://simons.berkeley.edu/talks/lee-altenberg-2014-03-17
The Power of Randomness in Kolmogorov Complexity Simons Institute 2023-02-03 | Zhenjian Lu (Simon Fraser University)https://simons.berkeley.edu/talks/power-randomness-kolmogorov-complexityMeet the Fellows Welcome Event Spring 2023
Emulating Non-Local Games with Cryptography Simons Institute 2023-01-28 | Alex Lombardi (MIT)https://simons.berkeley.edu/talks/emulating-non-local-games-cryptographyMeet the Fellows Welcome Event Spring 2023
Is Cryptography Feasible if P=NP? Simons Institute 2023-01-28 | Marshall Ball (New York University)https://simons.berkeley.edu/talks/cryptography-feasible-if-pnpMeet the Fellows Welcome Event Spring 2023
Proof Complexity and TFNP Simons Institute 2023-01-28 | Robert Robere (McGill University)https://simons.berkeley.edu/talks/proof-complexity-tfnpMeet the Fellows Welcome Event Spring 2023
Learning versus Proofs of Complexity Lower Boundes Simons Institute 2023-01-28 | Marco Carmosino (UC San Diego)https://simons.berkeley.edu/talks/learning-versus-proofs-complexity-lower-boundesMeet the Fellows Welcome Event Spring 2023
Understanding the Role of Derandomization in TCS Simons Institute 2023-01-28 | Roei Tell (Weizmann Institute of Science)https://simons.berkeley.edu/talks/understanding-role-derandomization-tcsMeet the Fellows Welcome Event Spring 2023
New Forms of Hardness versus Randomness Simons Institute 2023-01-28 | Lijie Chen (UC Berkeley)https://simons.berkeley.edu/talks/new-forms-hardness-versus-randomnessMeet the Fellows Welcome Event Spring 2023
Quantum for Science Simons Institute 2023-01-28 | Jin-Peng Liu (UC Berkeley)https://simons.berkeley.edu/talks/quantum-scienceMeet the Fellows Welcome Event Spring 2023
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification Simons Institute 2023-01-28 | Yuval Dagan (MIT)https://simons.berkeley.edu/talks/adversarial-laws-large-numbers-optimal-regret-online-classificationMeet the Fellows Welcome Event Spring 2023
The Power of Randomness in Kolmogorov Complexity Simons Institute 2023-01-27 | Zhenjian Lu (Simon Fraser University)https://simons.berkeley.edu/talks/power-randomness-kolmogorov-complexityMeet the Fellows Welcome Event Spring 2023
Automatability: The Proof Search Problem Simons Institute 2023-01-21 | Susanna de Rezende (Lund University)https://simons.berkeley.edu/talks/automatability-proof-search-problemMeta-Complexity Boot Camp
Proofs, Circuits and Total Search Problems Simons Institute 2023-01-21 | Susanna de Rezende (Lund University)https://simons.berkeley.edu/talks/proofs-circuits-total-search-problems-0Meta-Complexity Boot Camp
Proof Complexity and Meta-Complexity Tutorial (2) Simons Institute 2023-01-21 | Toniann Pitassi (University of Toronto)https://simons.berkeley.edu/talks/tbd-37Meta-Complexity Boot Camp
Proof Complexity and Meta-Complexity Tutorial (1) Simons Institute 2023-01-21 | Toniann Pitassi (University of Toronto)https://simons.berkeley.edu/talks/tbd-37Meta-Complexity Boot Camp
Minimal Complexity Assumptions for Cryptography (Part II) Simons Institute 2023-01-20 | Tal Malkin (Columbia University)https://simons.berkeley.edu/talks/minimal-complexity-assumptions-cryptography-part-iiMeta-Complexity Boot Camp
Minimal Complexity Assumptions for Cryptography (Part I) Simons Institute 2023-01-20 | Tal Malkin (Columbia University)https://simons.berkeley.edu/talks/minimal-complexity-assumptions-cryptography-part-iMeta-Complexity Boot Camp
Cryptography and Kolmogorov Complexity (Part II) Simons Institute 2023-01-20 | Rafael Pass (Cornell University)https://simons.berkeley.edu/talks/cryptography-kolmogorov-complexity-part-iiMeta-Complexity Boot Camp
Cryptography and Kolmogorov Complexity (Part I) Simons Institute 2023-01-20 | Rafael Pass (Cornell University)https://simons.berkeley.edu/talks/cryptography-kolmogorov-complexity-part-iMeta-Complexity Boot Camp
The Quest for Hardness of Metacomplexity: Progress, Barriers, and Next Steps (Part II) Simons Institute 2023-01-19 | Rahul Ilango (MIT)https://simons.berkeley.edu/talks/quest-hardness-metacomplexity-progress-barriers-next-steps-part-iiMeta-Complexity Boot Camp
The Quest for Hardness of Metacomplexity: Progress, Barriers, and Next Steps (Part I) Simons Institute 2023-01-19 | Rahul Ilango (MIT)https://simons.berkeley.edu/talks/quest-hardness-metacomplexity-progress-barriers-next-steps-part-iMeta-Complexity Boot Camp
Probabilistic Kolmogorov Complexity Simons Institute 2023-01-19 | Igor Carboni Oliveira (University of Warwick)https://simons.berkeley.edu/talks/title-tba-0Meta-Complexity Boot Camp
Kolmogorov Complexity for Meta-Complexity for Theoreticians Simons Institute 2023-01-19 | Eric Allender (Rutgers University)https://simons.berkeley.edu/talks/title-tbaMeta-Complexity Boot Camp
The Power of Distinguishing Simple From Random (Part II) Simons Institute 2023-01-18 | Valentine Kabanets (Simon Fraser University)https://simons.berkeley.edu/talks/power-distinguishing-simple-random-part-iiMeta-Complexity Boot Camp
The Power of Distinguishing Simple From Random (Part I) Simons Institute 2023-01-18 | Valentine Kabanets (Simon Fraser University)https://simons.berkeley.edu/talks/power-distinguishing-simple-random-part-iMeta-Complexity Boot Camp
Intro to Meta-Complexity: Part 2 Simons Institute 2023-01-18 | Rahul Santhanam (University of Oxford)https://old.simons.berkeley.edu/talks/tbd-492Meta-Complexity Boot Camp
Intro to Meta-Complexity: Part 1 Simons Institute 2023-01-18 | Rahul Santhanam (University of Oxford)https://old.simons.berkeley.edu/talks/tbd-491Meta-Complexity Boot Camp
Constant-depth sorting networks Simons Institute 2023-01-15 | Authors: Natalia Dobrokhotova-Maikova (Yandex, Moscow, Russia); Alexander Kozachinskiy (Institute for Mathematical and Computational Engineering, Universidad Católica de Chile \ IMFD & CENIA Chile, Santiago, Chile); Vladimir Podolskii (Courant Institute of Mathematical Sciences, New York University, NY, USA)ITCS - Innovations in Theoretical Computer Science
Black-box Constructive Proofs are Unavoidable Simons Institute 2023-01-12 | Authors: Lijie Chen (UC Berkeley); Ryan Williams (MIT); Tianqi Yang (Tsinghua University)ITCS - Innovations in Theoretical Computer Science
On Oracles and Algorithmic Methods for Proving Lower Bounds Simons Institute 2023-01-11 | Authors: Nikhil Vyas, Ryan Williams (MIT)ITCS - Innovations in Theoretical Computer Science
On disperser/lifting properties of the Index and Inner-Product functions Simons Institute 2023-01-09 | Authors: Paul Beame (University of Washington); Sajin Koroth (University of Victoria)ITCS - Innovations in Theoretical Computer Science
Bit Complexity of Jordan Normal Form and Spectral Factorization Simons Institute 2023-01-09 | Authors: Nikhil Srivastava (UC Berkeley); Ravindran Kannan (Microsoft Reseach India); Nick Ryder (OpenAI); Papri Dey (Georgia Tech)ITCS - Innovations in Theoretical Computer Science
Certification with an NP Oracle Simons Institute 2023-01-08 | Authors: Guy Blanc, Caleb Koch (Stanford University); Jane Lange (MIT); Carmen Strassle, Li-Yang Tan (Stanford University)ITCS - Innovations in Theoretical Computer Science
Matrix multiplication via matrix groups Simons Institute 2023-01-08 | Authors: Jonah Blasiak (Department of Mathematics, Drexel University); Henry Cohn (Microsoft Research New England); Joshua A. Grochow (Departments of Computer Science and Mathematics, University of Colorado Boulder); Kevin Pratt (School of Computer Science, Carnegie Mellon University); Chris Umans (Department of Computing and Mathematical Sciences, California Institute of Technology)ITCS - Innovations in Theoretical Computer Science
TFNP Characterizations of Proof Systems and Monotone Circuits Simons Institute 2023-01-06 | Authors: Noah Fleming (Memorial University); Sam Buss, Russell Impagliazzo (University of California, San Diego)ITCS - Innovations in Theoretical Computer Science
Resilience of 3-Majority Dynamics to Non-Uniform Schedulers Simons Institute 2023-01-06 | Authors: Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov (Tel Aviv University)ITCS - Innovations in Theoretical Computer Science
Exponential separations using guarded extension variables Simons Institute 2023-01-05 | Authors: Emre Yolcu, Marijn Heule (Carnegie Mellon University)ITCS - Innovations in Theoretical Computer Science
Beyond Worst-Case Budget-Feasible Mechanism Design Simons Institute 2023-01-05 | Authors: Aviad Rubinstein, Junyao Zhao (Stanford University)ITCS - Innovations in Theoretical Computer Science
HappyMap: A Generalized Multicalibration Method Simons Institute 2023-01-05 | Authors: Zhun Deng, Cynthia Dwork (Harvard University); Linjun Zhang (Rutgers University)ITCS - Innovations in Theoretical Computer Science
Worst-Case to Expander-Case Reductions Simons Institute 2023-01-05 | Authors:amir Abboud, Nathan Wallheimer (Weizmann Institute)ITCS - Innovations in Theoretical Computer Science
Proofs of Quantumness from Trapdoor Permutations Simons Institute 2023-01-05 | Authors: Tomoyuki Morimae (Kyoto University); Takashi Yamakawa (NTT Social Informatics Laboratories)ITCS - Innovations in Theoretical Computer Science
On computing homological hitting sets Simons Institute 2023-01-05 | Authors: Ulrich Bauer (Technical University of Munich); Abhishek Rathod (Purdue University); Meirav Zehavi (Ben-Gurion University)ITCS - Innovations in Theoretical Computer Science
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems Simons Institute 2023-01-04 | Authors: Monika Henzinger (University of Vienna); Billy Jin (Cornell University); Richard Peng (Carnegie Mellon University and University of Waterloo); David Williamson (Cornell University)ITCS - Innovations in Theoretical Computer Science
Generalized Private Selection and Testing with High Confidence Simons Institute 2023-01-04 | Authors: Edith Cohen (Google Research and Tel Aviv University); Xin Lyu (UC Berkeley); Jelani Nelson (UC Berkeley & Google Research); Tamás Sarlós (Google Research); Uri Stemmer (Tel Aviv University and Google Research)ITCS - Innovations in Theoretical Computer Science
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method Simons Institute 2023-01-04 | Authors: Sepehr Assadi, Aaron Bernstein, Zachary Langley (Rutgers University)ITCS - Innovations in Theoretical Computer Science
Is it easier to count communities than find them? Simons Institute 2023-01-04 | Authors: Cynthia Rush (Columbia); Fiona Skerman (Uppsala University); Alexander S Wein (UC Davis); Dana Yang (Cornell)ITCS - Innovations in Theoretical Computer Science
Secure Distributed Network Optimization Against Eavesdroppers Simons Institute 2023-01-04 | Authors: Yael Hitron, Merav Parter (Weizmann Institute); Eylon Yogev (Bar-Ilan University)ITCS - Innovations in Theoretical Computer Science
Algorithms with More Granular Differential Privacy Guarantees Simons Institute 2023-01-04 | Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke (Google Research)ITCS - Innovations in Theoretical Computer Science
Graph Searching with Predictions Simons Institute 2023-01-04 | Authors: Siddhartha Banerjee (Cornell); Vincent Cohen-Addad (Google); Anupam Gupta (Carnegie Mellon); Zhouzi Li (Tsinghua University)ITCS - Innovations in Theoretical Computer Science
False Consensus, Information Theory, and Prediction Markets Simons Institute 2023-01-04 | Authors: Yuqing Kong (Peking University); Grant Schoenebeck (University of Michigan)ITCS - Innovations in Theoretical Computer Science
Symmetric Formulas for Products of Permutations Simons Institute 2023-01-04 | Authors: William He, Benjamin Rossman (Duke University)ITCS - Innovations in Theoretical Computer Science
