Poke | Computer Science/Discrete Mathematics

Computer Science/Discrete Mathematics

449 videos • 4,896 views • by Institute for Advanced Study

Upper Bounds for Multicolour Ramsey Numbers - Marius Tiba

Institute for Advanced Study
Download

Why Extension-Based Proofs Fail - Faith Ellen

Institute for Advanced Study
Download

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem - Guy Blanc

Institute for Advanced Study
Download

Coboundary Expansion Inside Chevalley High-Dimensional Expanders - Ryan O'Donnell

Institute for Advanced Study
Download

Language Generation in the Limit - Jon Kleinberg

Institute for Advanced Study
Download

Cosystolic Expansion - Irit Dveer Dinur

Institute for Advanced Study
Download

Locally Testable Codes with the Multiplication Property from High-dimensional Expanders - Siqi Liu

Institute for Advanced Study
Download

Improved Private Information Retrieval Schemes from Matching Vectors and Deriva...- Swastik Kopparty

Institute for Advanced Study
Download

Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity - Avi Wigderson

Institute for Advanced Study
Download

Efficiency, Resilience, and Artificial Intelligence - Moshe Y. Vardi

Institute for Advanced Study
Download

Connections Between Matrix Spaces and Graphs - Youming Qiao

Institute for Advanced Study
Download

A Zero-Knowledge PCP Theorem - Nicholas Spooner

Institute for Advanced Study
Download

On the Complexity of Isomorphism Problems for Tensors, Groups, Polynomials, and...- Youming Qiao

Institute for Advanced Study
Download

Simulating Time With Square-Root Space - Ryan Williams

Institute for Advanced Study
Download

A Theory of Generalized Boosting - Nataly Brukhim

Institute for Advanced Study
Download

Improved Fault-Tolerant Non-Clifford Gates (or: How to Multiply Quantumly) - Louis Golowich

Institute for Advanced Study
Download

Independent Sets in Random Cayley Graphs - Huy Tuan Pham

Institute for Advanced Study
Download

Finding Regular Subgraphs - Richard Montgomery

Institute for Advanced Study
Download

“Sharp” Selector Processes - Huy Tuan Pham

Institute for Advanced Study
Download

Monochromatic Sums and Products over the Rationals - Maria-Romina Ivan

Institute for Advanced Study
Download

The Error Resilience of Binary Codes with Interaction - Gillat Kol

Institute for Advanced Study
Download

Lower Bounds for Local Codes from Induced Subgraphs of Cayley Graphs - Peter Manohar

Institute for Advanced Study
Download

Low-Depth Algebraic Circuit Lower Bounds Over Any Field - Michael A. Forbes

Institute for Advanced Study
Download

Spectral Algorithms from Induced Subgraphs of Cayley Graphs - Peter Manohar

Institute for Advanced Study
Download

On Approximability of Satisfiable Constraint Satisfaction Problems & Applications - Amey Bhangale

Institute for Advanced Study
Download

Explicit Codes Approaching the Generalized Singleton Bound Using Expanders - Shashank Srivastava

Institute for Advanced Study
Download

Random Matrices From GLn(q) Sampled by Words - Doron Puder

Institute for Advanced Study
Download

Structure and Randomness for Finite-field Polynomials are (almost) Equivalent - Guy Moshkovitz

Institute for Advanced Study
Download

Problems in Extremal Combinatorics and Connections with Multiparty Communication... - Zander Kelley

Institute for Advanced Study
Download

Grid-norm Regularity for Somewhat Dense Graphs, and Some Applications - Zander Kelley

Institute for Advanced Study
Download

Efficient Batch Verification: Recent Progress and Challenges - Ron Rothblum

Institute for Advanced Study
Download

A Review of the Notion of Graph Rigidity and Some Recent Developments - Orit Raz

Institute for Advanced Study
Download

QMA vs. QCMA and Pseudorandomness - Henry Yuen

Institute for Advanced Study
Download

Simple High Dimensional Expanders from Cayley Graphs - Yotam Dikstein

Institute for Advanced Study
Download

Dot-Product Proofs - Yuval Ishai

Institute for Advanced Study
Download

Quadratic Stability of the Brunn-Minkowski Inequality - Peter van Hintum

Institute for Advanced Study
Download

Induced Subgraphs and Pathwidth - Maria Chudnovsky

Institute for Advanced Study
Download

Linear Stability of the Brunn-Minkowski Inequality - Peter van Hintum

Institute for Advanced Study
Download

Quantum Locally Testable Codes and Codes with Transversal Gates - David (Ting-Chun) Lin

Institute for Advanced Study
Download

Fault Tolerant Routing Protocols on High-Dimensional Expanders - Mitali Bafna

Institute for Advanced Study
Download

Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders - Mitali Bafna

Institute for Advanced Study
Download

Sheaves on Graphs, the Hanna Neumann Conjecture, and My Debt to Number Theory and... - Joel Friedman

Institute for Advanced Study
Download

When and How are (promise) Constraint Satisfaction Problems Efficiently Sol...- Venkatesan Guruswami

Institute for Advanced Study
Download

Analytic Insights into the Zig-Zag Product and Its Friends: Part II - Gil Cohen

Institute for Advanced Study
Download

Subgroup Tests and the Aldous--Lyons Conjecture - Michael Chapman

Institute for Advanced Study
Download

Analytic Insights into the Zig-Zag Product and Its Friends: Part I - Gil Cohen

Institute for Advanced Study
Download

Subgroup Tests and Tailored Non-local Games - Michael Chapman

Institute for Advanced Study
Download

A New Approach to Strong Convergence - Ramon Van Handel

Institute for Advanced Study
Download

Sorting Using Partial Information - Robert Tarjan

Institute for Advanced Study
Download

Concentration on HDX: Derandomization Beyond Chernoff - Max Hopkins

Institute for Advanced Study
Download

An Improved Line-Point Low-Degree Test - Prahladh Harsha

Institute for Advanced Study
Download

Resolution of the Kohayakawa--Kreuter Conjecture - Raphael Steiner

Institute for Advanced Study
Download

Quantum Mechanics, Semidefinite Programming, and Graph Invariants - Matthew Hastings

Institute for Advanced Study
Download

Rounding Large Independent Sets on Expanders - Tim Hsieh

Institute for Advanced Study
Download

Incidence Bounds via Extremal Graph Theory - Istvan Tomon

Institute for Advanced Study
Download

Triangulated Surfaces in Moduli Space - Sahana Vasudevan

Institute for Advanced Study
Download

Lower Bounds for Set-Multilinear Branching Programs - Shubhangi Saraf

Institute for Advanced Study
Download

Random Cayley Graphs From a Combinatorial Perspective - Huy Tuan Pham

Institute for Advanced Study
Download

Additive Combinatorics Without Groups - Huy Tuan Pham

Institute for Advanced Study
Download

Parallel Repetition for 3-Player XOR Games - Yang Liu

Institute for Advanced Study
Download

Graphs, CSPs and Codes - Madhu Sudan

Institute for Advanced Study
Download

Avi Wigderson, 2023 Turing Award Laureate, Q&A with David Nirenberg | Institute for Advanced Study

Institute for Advanced Study
Download

The Method of Hypergraph Containers - Wojciech Samotij

Institute for Advanced Study
Download

Polynomial Capacity and its Applications: To TSP and Beyond - Jonathan Leake

Institute for Advanced Study
Download

New Derandomized Agreement Testers - Yotam Dikstein

Institute for Advanced Study
Download

Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries - Huacheng Yu

Institute for Advanced Study
Download

Sparsification of Gaussian Processes - Anindya De

Institute for Advanced Study
Download

Locally Consistent Decomposition of Strings with Applications to Edit Distance Ske...- Michal Koucký

Institute for Advanced Study
Download

Explicit SoS Lower Bounds from High Dimensional Expanders - Max Hopkins

Institute for Advanced Study
Download

Computing Greatest Common Divisors of Polynomials in Parallel - Robert Andrews

Institute for Advanced Study
Download

Stability and Learning in Strategic Games - Éva Tardos

Institute for Advanced Study
Download

Analyzing the Max Entropy Algorithm for TSP - Nathan Klein

Institute for Advanced Study
Download

Reconstruction on Trees and Hypertrees - Yuzhou Gu

Institute for Advanced Study
Download

Advances in Parallel and Private Stochastic Optimization from Ball Acceleration - Kevin Tian

Institute for Advanced Study
Download

An Exponential Lower bound on Three Query, Linear Locally Correctable Codes - Pravesh Kothari

Institute for Advanced Study
Download

Expanding the Reach of P not equal to NP: the Minimum Circuit Size Problem with a... - Rahul Ilango

Institute for Advanced Study
Download

Omniprediction and Multigroup Fairness - Parikshit Gopalan

Institute for Advanced Study
Download

The Tree Evaluation Problem: Context and Recent Results - Ian Mertz

Institute for Advanced Study
Download

Online Discrepancy Minimization - Victor Reis

Institute for Advanced Study
Download

Marton's Conjecture, aka the Polynomial Freiman--Ruzsa conjecture - Frederick Manners

Institute for Advanced Study
Download

Online Omniprediction - Sumegha Garg

Institute for Advanced Study
Download

Coboundary and Cosystolic Expansion - Siqi Liu

Institute for Advanced Study
Download

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition - Or Meir

Institute for Advanced Study
Download

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting- William Hoza

Institute for Advanced Study
Download

Recent Progress on Derandomizing Space-Bounded Computation - William Hoza

Institute for Advanced Study
Download

Sparsifying Sums of Functions - Yang Liu

Institute for Advanced Study
Download

Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications - Nitya Mani

Institute for Advanced Study
Download

The Iterative Win-Win Method, and Explicit Constructions (without) Using It - Hanlin Ren

Institute for Advanced Study
Download

A Definition of Spectral Gap for Nonreversible Markov Chains - Sourav Chatterjee

Institute for Advanced Study
Download

High Dimensional Expanders and Sparsifications of the Johnson Graph - Yotam Dikstein

Institute for Advanced Study
Download

A High Dimensional Goldreich-Levin Theorem - Silas Richelson

Institute for Advanced Study
Download

An Optimization Perspective on Log-concave Sampling - Sinho Chewi

Institute for Advanced Study
Download

A Proof of the RM Code Capacity Conjecture - Emmanuel Abbé

Institute for Advanced Study
Download

Extending Generalization Theory towards addressing modern challenges in Machine Learning- Shay Moran

Institute for Advanced Study
Download

A Combinatorial Characterization of Minimax in Win/Lose Games - Shay Moran

Institute for Advanced Study
Download

Shrinkage Under Random Restrictions - Robert Andrews

Institute for Advanced Study
Download

Private Optimization and Statistical Physics: Low-Rank Matrix Approximation - Nisheeth Vishnoi

Institute for Advanced Study
Download

Learning from Dynamics - Ankur Moitra

Institute for Advanced Study
Download

The Diffraction Limit and Extremal Functions - Ankur Moitra

Institute for Advanced Study
Download

Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?) - Avi Wigderson

Institute for Advanced Study
Download

Using Expanders for Fast Graph Algorithms - Thatchaphol Saranurak

Institute for Advanced Study
Download

Graph Vertex Expansion - Theo McKenzie

Institute for Advanced Study
Download

Fitting Various Metrics with Minimum Disagreements - Euiwoong Lee

Institute for Advanced Study
Download

A Constant Lower Bound for Frankl's Union-Closed Sets Conjecture - Justin Gilmer

Institute for Advanced Study
Download

A Unified Approach to Discrepancy Minimization - Nikhil Bansal

Institute for Advanced Study
Download

Approximating Iterated Multiplication of Stochastic Matrices in Small Space - Dean Doron

Institute for Advanced Study
Download

Existence of Subspace Designs - Ashwin Sah

Institute for Advanced Study
Download

Unit and Distinct Distances in Typical Norms - Noga Alon

Institute for Advanced Study
Download

Updates on the Lipschitz Extension Problem - Assaf Naor

Institute for Advanced Study
Download

Quantum Error Correction, Systolic Geometry, and Probabilistic Embeddings - Elia Portnoy

Institute for Advanced Study
Download

Hausdorff Dimension Analogues of the Elekes - Ronyai Theorem and Related Problems - Orit Raz

Institute for Advanced Study
Download

Common Linear Patterns Are Rare - Nina Kamčev

Institute for Advanced Study
Download

The Lens of Abelian Embeddings - Dor Minzer

Institute for Advanced Study
Download

Strong Bounds for 3-Progressions: In-Depth - Zander Kelley

Institute for Advanced Study
Download

Extremal Problems for Uniformly Dense Hypergraphs - Mathias Schacht

Institute for Advanced Study
Download

Strong Bounds for 3-Progressions - Raghu Meka

Institute for Advanced Study
Download

Why Can’t We Classically Describe Quantum Systems? - Chinmay Nirkhe

Institute for Advanced Study
Download

Recent Progress in Randomness Extraction - Eshan Chattopadhyay

Institute for Advanced Study
Download

Two (More) Algorithms for Set Cover - Anupam Gupta

Institute for Advanced Study
Download

From Robust Sublinear Expanders to Additive Number Theory via Rainbow Cycles - Matija Bucic

Institute for Advanced Study
Download

Rainbow Matchings in Hypergraphs - Cosmin Pohoata

Institute for Advanced Study
Download

Efficient Verification of Computation on Untrusted Platforms - Yael Kalai

Institute for Advanced Study
Download

Overview and Recent Results in Combinatorial Auctions - Matt Weinberg

Institute for Advanced Study
Download

Smooth Coverings of Space - Oded Regev

Institute for Advanced Study
Download

On Matrix Multiplication and Polynomial Identity Testing - Robert Andrews

Institute for Advanced Study
Download

Locally Decodable Codes - Zeev Dvir

Institute for Advanced Study
Download

Non-measurability of the inverse theorem for the Gowers norms - Terence Tao

Institute for Advanced Study
Download

A Characterization of Multiclass Learnability - Nataly Brukhim

Institute for Advanced Study
Download

Optimization-Friendly Generic Mechanisms Without Money - Mark Braverman

Institute for Advanced Study
Download

Online List Labeling: Breaking the log2 n Barrier - Nicole Wein

Institute for Advanced Study
Download

Optimal Weak to Strong Learning - Kasper Green Larsen

Institute for Advanced Study
Download

Superfast Derandomization of Interactive Proof Systems - Roei Tell

Institute for Advanced Study
Download

The Hypergraph Container Method, Partition Containers, and Algorithmic Applications - Or Zamir

Institute for Advanced Study
Download

Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model - Mark Sellke

Institute for Advanced Study
Download

The Polynomial Method in Communication Complexity - Pei Wu

Institute for Advanced Study
Download

Strong XOR Lemma for Communication with Bounded Rounds - Huacheng Yu

Institute for Advanced Study
Download

Additive combinatorics through the lens of communication complexity - Toniann Pitassi

Institute for Advanced Study
Download

Communication and Query Complexity of Bipartite Perfect Matching - Yuval Efron

Institute for Advanced Study
Download

Introduction to Natural Quasirandomness: Unique Colorability and Order-ability - Leonardo Coregliano

Institute for Advanced Study
Download

Smoothed Complexity of Local Max-Cut with Two Flips - Xi Chen

Institute for Advanced Study
Download

Average-Case Computational Complexity of Tensor Decomposition - Alex Wein

Institute for Advanced Study
Download

Almost Linear Time Algorithms for Max-flow and More - Sushant Sachdeva

Institute for Advanced Study
Download

The Optimal Error Resilience of Interactive Communication over the Binary Alphabet - Rachel Zhang

Institute for Advanced Study
Download

Is your distribution in shape? - Ronitt Rubinfeld

Institute for Advanced Study
Download

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Ampli... - Fernando Granha Jeronimo

Institute for Advanced Study
Download

Relative rank and regularity - Tamar Ziegler

Institute for Advanced Study
Download

Robust sublinear expanders, and an application towards the Erdos-Gallai conjecture - Matija Bucic

Institute for Advanced Study
Download

Making Proofs More Constructive, and Algorithms Less Random - Oliver Korten

Institute for Advanced Study
Download

Graphs as geometric objects - Nathan Linial

Institute for Advanced Study
Download

On Approximability of CSPs on Satisfiable Instances - Subhash Khot

Institute for Advanced Study
Download

Exact algorithms for graph coloring - Or Zamir

Institute for Advanced Study
Download

List decoding with double samplers - Inbal Livni-Navon

Institute for Advanced Study
Download

An Introduction to Binary Code Bounds - Fernando Granha Jeronimo

Institute for Advanced Study
Download

An Introduction to Lifted Expander Graphs - Fernando Granha Jeronimo

Institute for Advanced Study
Download

Norm Minimization, Invariant Theory, and the Jacobian conjecture - William Cole Franks

Institute for Advanced Study
Download

Reproducibility in Learning - Jessica Sorrell

Institute for Advanced Study
Download

Bias vs Low Rank of Polynomials with...Algebraic Geometry - Abhishek Bhowmick

Institute for Advanced Study
Download

Algorithmizing the Multiplicity Schwartz-Zippel Lemma - Prahladh Harsha

Institute for Advanced Study
Download

Random algebraic varieties and their applications to hardness of approximation - Bhargav Narayanan

Institute for Advanced Study
Download

Derandomization and its connections throughout complexity theory - Roei Tell

Institute for Advanced Study
Download

Derandomization and its connections throughout complexity theory - Liije Chen

Institute for Advanced Study
Download

Non-Black-Box Derandomization - Roei Tell

Institute for Advanced Study
Download

Refuting Smoothed k-SAT Formulas and a Proof of Feige's Conjecture - Pravesh Kothari

Institute for Advanced Study
Download

Association schemes and codes II: Completeness of the hierarchy of high-order...-Leonardo Coregliano

Institute for Advanced Study
Download

A Proof of the Kahn-Kalai Conjecture - Jinyoung Park

Institute for Advanced Study
Download

Association schemes and codes I: The Delsarte linear program - Leonardo Coregliano

Institute for Advanced Study
Download

Polynomial Bounds on Parallel Repetition For All 3-Player Games with Binary Inputs - Kunal Mittal

Institute for Advanced Study
Download

A Tutorial on Gaussian Elimination - John C Urschel

Institute for Advanced Study
Download

Set Chasing, with an application to online shortest path - Sébastien Bubeck

Institute for Advanced Study
Download

Multi-group fairness, loss minimization and indistinguishability - Parikshit Gopalan

Institute for Advanced Study
Download

A magnetic interpretation of the nodal count on graphs - Lior Alon

Institute for Advanced Study
Download

Many Nodal Domains in Random Regular Graphs - Nikhil Srivastava

Institute for Advanced Study
Download

The absorption method, and an application to an old Ramsey problem - Matija Bucic

Institute for Advanced Study
Download

Linear cover time is exponentially unlikely - Quentin Dubroff

Institute for Advanced Study
Download

Localization schemes: A framework for proving mixing bounds for Markov chains - Ronen Eldan

Institute for Advanced Study
Download

Online Bipartite Matching and Adwords - Vijay V. Vazirani

Institute for Advanced Study
Download

Localization schemes: A framework for proving mixing bounds for Markov chains - Ronen Eldan

Institute for Advanced Study
Download

Multi-group learning via Outcome Indistinguishability - Gal Yona

Institute for Advanced Study
Download

Hardness of Easy Problems and Fine-Grained Complexity - Or Zamir

Institute for Advanced Study
Download

The Minimum Formula Size Problem is (ETH) Hard - Rahul Ilango

Institute for Advanced Study
Download

Introduction to Continuous Combinatorics II: semantic limits - Leonardo Coregliano

Institute for Advanced Study
Download

The Kakeya Set conjecture over Z mod N for general N - Manik Dhar

Institute for Advanced Study
Download

Introduction to Continuous Combinatorics I: the semidefinite method of flag... - Leonardo Coregliano

Institute for Advanced Study
Download

Parallel Repetition for the GHZ Game: A Simpler Proof - Uma Girish

Institute for Advanced Study
Download

Locally testable codes with constant rate, distance, and locality, Part II - Irit Dinur

Institute for Advanced Study
Download

Locally testable codes with constant rate, distance, and locality, Part I - Irit Dinur

Institute for Advanced Study
Download

An Introduction to Determinantal Point Processes - John C Urschel

Institute for Advanced Study
Download

Sharp matrix concentration inequalities - Ramon van Handel

Institute for Advanced Study
Download

Recent progress in query complexity I & II Part 2 - Pei Wu

Institute for Advanced Study
Download

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS - Alexandros Hollender

Institute for Advanced Study
Download

Recent progress in query complexity I & II - Pei Wu

Institute for Advanced Study
Download

Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties - Guy Rothblum

Institute for Advanced Study
Download

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits II : A more... - Sébastien Tavenas

Institute for Advanced Study
Download

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits I... - Srikanth Srinivasan

Institute for Advanced Study
Download

Linear spaces of matrices - Avi Wigderson

Institute for Advanced Study
Download

Expander Random Walks: A Fourier-Analytic Approach - Gil Cohen

Institute for Advanced Study
Download

A Complexity-Theoretic Perspective on Fairness - Michael P. Kim

Institute for Advanced Study
Download

On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture... Part III - Ronen Eldan

Institute for Advanced Study
Download

On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourga... - Ronen Eldan

Institute for Advanced Study
Download

On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourga... - Ronen Eldan

Institute for Advanced Study
Download