ITCS 2022 Session 1

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=WQC5_Hkg6CA


Duration: 1:15:40
915 views
0

Chair: Igor Oliveira

Small Circuits Imply Efficient Arthur-Merlin Protocols
Michael Ezra and Ron Rothblum (Technion)
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage
Bruno P. Cavalar and Zhenjian Lu (University of Warwick)
A variant of the VC-dimension with applications to depth-3 circuits
Peter Frankl (Rényi Institute); Svyatoslav Gryaznov and Navid Talebanfard (Institute of Mathematics of the Czech Academy of Sciences)
Smaller ACC0 Circuits for Symmetric Functions
Brynmor Chapman and Ryan Williams (MIT)
Almost-Orthogonal Bases for Inner Product Polynomials
Chris Jones and Aaron Potechin (University of Chicago)

13th Innovations in Theoretical Computer Science (ITCS) Conference



Other Videos By Simons Institute for the Theory of Computing


2022-02-01ITCS 2022 Graduating Bits
2022-02-01ITCS 2022 Session 7
2022-02-01Uniform brackets, containers, and combinatorial Macbeath regions
2022-02-01FPT Algorithms for Finding Near-Cliques in $c$-Closed Graphs
2022-02-01Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
2022-02-01ITCS 2022 Session 6
2022-02-01ITCS 2022 Session 5
2022-02-01ITCS 2022 Session 4
2022-02-01ITCS 2022 Session 3
2022-01-31ITCS 2022 Session 2
2022-01-31ITCS 2022 Session 1
2022-01-31Randomness Extraction from Somewhat Dependent Sources
2022-01-31Noisy Boolean Hidden Matching with Applications
2022-01-31Small Circuits Imply Efficient Arthur-Merlin Protocols
2022-01-29Multi-Agent Reinforcement Learning (Part II)
2022-01-29Multi-Agent Reinforcement Learning (Part I)
2022-01-29Reinforcement Learning (Part II)
2022-01-28Reinforcement Learning (Part I)
2022-01-28Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
2022-01-28Separating the NP-Hardness of the Grothendieck problem from the Little-Grothendieck problem
2022-01-28Adaptive Massively Parallel Constant-round Tree Contraction