Online Complexity Seminar

External homepage

computational complexity discrete mathematics logic in computer science combinatorics logic

University of Warwick

Audience: Researchers in the topic
Seminar series times: No fixed schedule
Organizer: Igor Oliveira*
*contact for this listing

Online Complexity Seminar - Please visit sites.google.com/view/igorcarbonioliveira/online-complexity-seminar for Zoom link and schedule

Upcoming talks
Past talks
Your timeSpeakerTitle
ThuDec 0713:00Mikito NanashimaLearning in Pessiland via Inductive Inference
ThuNov 3013:00Or MeirToward Better Depth Lower Bounds: A KRW-like Theorem for Strong Composition
ThuNov 2317:00Hanlin RenBounded Relativization
ThuNov 1617:00Susanna F. de RezendeAverage-case hardness in proof complexity
ThuOct 2616:00Lijie ChenDerandomization vs Refutation: A Unified Framework for Characterizing Derandomization
ThuOct 1916:00Noam MazorKolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement
ThuOct 1216:00Ian MertzThe Tree Evaluation Problem: Context and Recent Results
ThuSep 2112:00Moritz MüllerOn the Consistency of Circuit Lower Bounds for Non-Deterministic Time
ThuJun 2912:00Nobutaka ShimizuHardness Self-Amplification: Simplified, Optimized, and Unified
ThuJun 1516:00Iddo TzameretStretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
ThuJun 0116:00Ryan WilliamsSelf-Improvement for SAT
ThuNov 1717:00William HozaRecent Progress on Derandomizing Space-Bounded Computation
ThuOct 2716:00Robert AndrewsOn Matrix Multiplication and Polynomial Identity Testing
ThuOct 1316:00Zhengzhong JinIndistinguishability Obfuscation via Mathematical Proofs of Equivalence
ThuSep 1516:00Tom GurWorst-Case to Average-Case Reductions via Additive Combinatorics
ThuSep 0816:00Emanuele ViolaSurvey on Correlation Bounds Against Polynomials
ThuAug 2512:00Shuichi HiraharaNP-Hardness of Learning Programs and Partial MCSP
ThuAug 0416:00Hanlin RenOn the Range Avoidance Problem for Circuits
ThuNov 2517:00Noah FlemingExtremely Deep Proofs
ThuNov 1117:00Pranjal DuttaDemystifying the border of depth-3 algebraic circuits
ThuOct 2816:00Shyan AkmalMAJORITY-3SAT (and Related Problems) in Polynomial Time
ThuOct 0716:00Rahul IlangoThe Minimum Formula Size Problem is (ETH) Hard
ThuSep 2316:00Oliver KortenThe hardest explicit construction
ThuJul 1516:00Mika GöösUnambiguous DNFs and Alon-Saks-Seymour
FriJul 0915:00Nutan LimayeSuperpolynomial lower bounds against low-depth algebraic circuits
ThuJul 0116:00William HozaBetter pseudodistributions and derandomization for space-bounded computation
ThuJun 1716:00Lijie ChenHardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
ThuJun 1012:00Shuichi HiraharaAverage-case hardness of NP from exponential worst-case hardness assumptions
ThuMay 2016:00Amir YehudayoffSlicing the hypercube is not easy
ThuMay 0614:00Bruno LoffHardness of constant-round communication complexity
ThuApr 2212:00Hanlin RenHardness of KT characterizes parallel cryptography
ThuApr 0816:00Josh AlmanKronecker products, low-depth circuits, and matrix rigidity
FriMar 2617:00Avishay TalPseudorandom generators for read-once monotone branching programs
ThuMar 1115:00Yuval FilmusBounded indistinguishability for simple sources
ThuFeb 2517:00Robert RobereAmortized circuit complexity, formal complexity measures, and catalytic algorithms
FriFeb 1216:00Susanna F. de RezendeAutomating tree-like resolution in time n^o(log n) is ETH-hard
ThuJan 2817:00Alexandros HollenderThe complexity of gradient descent: CLS = PPAD ∩ PLS
ThuJan 1417:00Eric AllenderCryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity
ThuDec 0317:00Toniann PitassiLifting with Sunflowers
ThuNov 1217:00Roei TellSimple and fast derandomization from very hard functions - Eliminating randomness at almost no cost
ThuOct 2917:00Ryan WilliamsAlmost-everywhere circuit lower bounds from non-trivial derandomization
ThuOct 1516:00Christian IkenmeyerRecent progress on Geometric Complexity Theory
ThuOct 0116:00Rafael PassOn one-way functions and Kolmogorov complexity
ThuSep 1712:00Shuichi HiraharaMeta-complexity theoretic approach to complexity theory
ThuAug 2016:00Srikanth SrinivasanA robust version of Heged\H{u}s's lemma
ThuAug 0616:00Mrinal KumarOn the existence of algebraically natural proofs
ThuJul 2316:00Benjamin RossmanSize-depth tradeoff for multiplying k permutations
ThuJul 1616:00Lijie ChenSharp threshold results for computational complexity
ThuJul 0216:00Or MeirThe KRW Conjecture: Past, present, and future
ThuJun 1816:00Rahul IlangoA lifting-esque theorem for constant depth formulas with consequences for MCSP and lower bounds
Embed this schedule
Export series to