Boolean Devices 2018
2018-09-10..2018-09-14
Berkeley, United States
| title | author | length |
|---|---|---|
| Circuit Lower Bounds (and More) via the Fusion Method | Avi Wigderson | 01h 05m |
Fusion method reframes lower bounds as a static cover problem: pick a subset Omega of functions and lower bound circuit size by the minimum number of abstract… | ||
| The KRW Conjecture: Results and Open Problems | Or Meir | 33m |
KRW conjecture claims depth(f ∘ g) is essentially depth(f) + depth(g); proven cases replace “essentially” with small losses only for specific inners: universal… | ||
| Pseudorandom Generators from Polarizing Random Walks | Kaave Hosseini | 34m |
Presents a concrete reduction: any fractional PRG whose per-coordinate second moment is bounded away from zero (parameter p) and whose test class is closed… | ||
| Oracle Separation of BQP and the Polynomial Hierarchy | Avishay Tal | 01h 03m |
Proves an oracle separating BQP from PH by building a boolean distribution D from a 2N‑dimensional multivariate Gaussian (identity and Hadamard blocks)… | ||
| Lower Bounds for Unrestricted Boolean Circuits: Open Problems | Sasha Kulikov | 31m |
Current best unconditional lower bound for unrestricted Boolean circuits uses the gate elimination method to get roughly 3n gates by plugging an affine… | ||
| Static Data Structure Lower Bounds Imply Rigidity | Sasha Golovnev | 26m |
Shows that linear static data-structure hardness translates to matrix rigidity: if an n-input linear problem resists S = n(1+ε) space and small probe time T… | ||
| Lifting Nullstellensatz Degree to Monotone Span Program Size | Robert Robere | 59m |
States a concrete equivalence: for any unsatisfiable CNF the Nullstellensatz degree of refutation lifts (via a constant-size gadget) to the monotone span… | ||
| Algorithmic Polynomials | Sasha Sherstov | 35m |
Constructive approximating polynomials replace quantum-derived ones: using Chebyshev polynomials, an extension theorem (extending approximations costs a… | ||
| Approximate Degree and Quantum Query Lower Bounds via Dual Polynomials | Mark Bun | 37m |
Develops concrete lower bounds for approximate degree and quantum query complexity using linear-program duality and symmetrization, proving block composition… | ||
| BPP Lifting and Its Applications | Toni Pitassi | 01h 02m |
Gives a constructive proof that randomized decision-tree complexity of any outer problem F lifts to randomized communication complexity of F composed with an… | ||
| Monotone Circuit Lower Bounds from Resolution (Now with Applications!) | Mika Göös | 29m |
Gives a lifting theorem that converts resolution refutation lower bounds into exponential monotone circuit lower bounds by composing hard CNF instances with a… | ||
| Locating Linear Decision Lists within TC^0 | Meena Mahajan | 35m |
Meena Mahajan (Institute of Mathematical Sciences)
https://simons.berkeley.edu/talks/tbd-18
Boolean Devices | ||
| An Overview of Quantified Derandomization | Roei Tell | 37m |
Quantified derandomization asks: given a circuit, decide whether it accepts all but B inputs or rejects all but B inputs. Unconditional algorithms exist for… | ||
| Clique Is Hard on Average for Regular Resolution | Susanna de Rezende | 46m |
Proves that for random G (edge probability just below the K-clique threshold) and K up to n^{1/4}, any regular-resolution refutation of the unary clique… | ||
| Fooling Polytopes | Li-Yang Tan | 46m |
Constructs an explicit pseudorandom generator / discrepancy set that fools all M‑facet 0/1 polytopes in n dimensions with size roughly n^{polylog M} (for… | ||
| A Survey on MCSP | Rahul Santhanam | 01h 08m |
Defines MCSP and variants (decision, search, optimization, approximate) and frames the core open: is MCSP NP‑hard or in P. Shows the explicit construction… | ||
| Hardness Magnification | Igor Carboni Oliveira | 35m |
Magnification claims that a barely superlinear lower bound — roughly n^{1+ε} — for very specific problems yields superpolynomial circuit or formula lower… | ||
| Natural Properties, MCSP, and Proving Circuit Lower Bounds | Valentine Kabanets | 36m |
Asserts concrete reductions: an average-case MCSP algorithm yields a worst-case gap-MCSP solver, and putting MCSP in randomized polytime or giving a… | ||
| A Review of Some Recent Lower Bounds Against Low-Depth Threshold Circuits | Ryan Williams | 33m |
Presents concrete lower bounds: an explicit Andreev-style function needs superlinear gates and roughly n^{1.5}/polylog n size against depth‑3 TC0, proven by a… | ||
| Recent Structure Lemmas for Depth-two Threshold Circuits | Lijie Chen | 28m |
Shows two explicit structure lemmas: any poly-size depth-2 threshold circuit is constructively written as a disjoint OR decomposition into majority-of-majority… | ||
| New Lower Bounds Through an Improved Easy Witness Lemma | Cody Murray | 27m |
Combines a strengthened easy witness lemma with the usual SAT-to-lower-bound framework to push from NEXP-style results down to NP: proving that a nontrivial… | ||
| Boolean Matrix Multiplication Lower Bounds | Michal Koucky | 30m |
Proves explicit lower bounds for restricted “combinatorial” Boolean matrix multiplication: the classic Angluin model (binary union circuits) needs Ω(n^2 / log… | ||
| The Pathset Approach to Formula Lower Bounds | Ben Rossman | 34m |
Defines the average-case k-cycle on layered graphs (edges present with probability ≈1/n) and builds a combinatorial model called path set formulas whose gates… | ||
| Distribution-Free Junta Testing | Rocco A. Servedio | 35m |
Shows nonadaptive distribution-free junta testing needs exponential queries and gives an efficient adaptive alternative: a 2^{Ω(k)} lower bound comes from a… | ||
| The Complexity of Distributions | Emanuele Viola | 55m |
Characterization: any AC0 sampler whose output has min-entropy k > ~sqrt(n) is a convex combination of bit-block sources, so samplable distributions reduce to… | ||
| Does Looking Inside a Circuit Help? | Antonina Kolokolova | 35m |
Asks whether a circuit description gives more power than oracle queries and proves a concrete reduction: if a property of Boolean functions is decidable in BPP… | ||
| The Coin Problem and AC^0[parity] | Srikanth Srinivasan | 31m |
Proves that the delta coin problem can be solved by explicit depth‑3 AC0[⊕] formulas using only poly(1/δ) samples (instead of exponentially many), yielding a… | ||
| A Short List of Equalities Has Large Sign Rank | Arkadev Chattopadhyay | 30m |
Constructs a concrete depth‑two threshold-of-threshold function — essentially odd-max-bit of equality — and proves it has unexpectedly large sign rank (about… | ||
| nothing matches | ||