LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds

124 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Ryan Williams of the Institute for Advanced Study presents a result connecting circuit-analysis algorithms to nonuniform circuit lower bounds, delivered as part of the IAS Computer Science/Discrete Mathematics Seminar II. He argues that the nonexistence of nontrivial circuit-analysis algorithms can itself be used to derive lower bounds, producing win-win theorems and a possible route to refuting the Orthogonal Vectors Conjecture in the O(log n)-dimensional case, which would be enough to refute the Strong Exponential Time Hypothesis. Williams works through the technical cases in depth: read-once 2-DNFs against depth-two exact threshold circuits, the disjointness matrix from communication complexity, and the implications an algorithmic breakthrough would have for CNF-SAT running time and for ENP against Valiant series-parallel circuits. The talk is aimed at specialists in computational complexity and assumes familiarity with circuit complexity and fine-grained complexity theory, building its argument through formal claims and open problems rather than general exposition.

At a glance

Lecture facts

Runtime compared with the other 350 Mathematics lectures
Runtime2 h 4 m
Compared with MathematicsLonger than 98%
Source channelInstitute for Advanced Study (YouTube)
Link status✓ Working · checked today
QA · not live