Top-Down Lower Bounds for Depth-Four Circuits
Explores new proof techniques for depth-4 boolean circuit complexity, applying robust sunflowers and block unpredictability to demonstrate exponential lower bounds for the parity function.
Nearly All K-SAT Functions Are Unate
Explore the prevalence of unate functions in k-SAT, resolving a 2003 conjecture and unveiling structural insights into Boolean satisfiability problems.
Tight Space Complexity of the Coin Problem
Explore the space complexity of the coin problem, focusing on distinguishing biased coins. Learn about tight thresholds and new combinatorial techniques for analyzing branching programs.
Some Remarks About Quantum and Classical Local Hamiltonian Optimization and SDP Rounding
Explore quantum and classical local Hamiltonian optimization and SDP rounding techniques, with insights from Ryan O'Donnell on advanced optimization strategies in quantum computing.
Randomized versus Deterministic Decision Tree Size
Explore the relationship between randomized and deterministic decision tree size complexity for Boolean functions, with implications for query complexity and rank equivalence.
Structures in Random Graphs - New Connections
Exploring structures in random graphs, including cliques and independence numbers in Cayley graphs, thresholds for monotone properties, and edge-colorings of bipartite graphs.
How to Do Fiat-Shamir in the Standard Model
Explore interactive protocols, Fiat-Shamir transformation, and delegation in cryptography. Learn about security assumptions, hash functions, and correlation intractability in probabilistic proof systems.
Efficient Zero Knowledge Proof from Interactive Proofs
Explore efficient zero-knowledge proofs derived from interactive proofs, focusing on new algorithms, performance improvements, and comparisons to existing systems.
Probabilistically Checkable Proofs - Part I
Explore probabilistically checkable proofs, focusing on proof verification, randomized verifiers, and proof rewriting techniques in this advanced theoretical computer science lecture.
Interactive Proofs - Part II
Explore advanced concepts in interactive proofs, including arithmetician protocols, sharpset, and general-purpose techniques. Learn about applications, limitations, and cutting-edge developments in this field.
Approximation Algorithms
Explore approximation algorithms for network design, including connectivity augmentation, Steiner trees, and spectral rounding techniques. Learn about linear programming and future research directions.
Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture
Explore semi-algebraic proofs, IPS lower bounds, and the τ-Conjecture in computational complexity theory, focusing on proof systems and algebraic circuits.
The Impossibility of Efficient Quantum Weak Coin Flipping
Explore quantum coin-flipping, its history, and recent developments in point games, profile functions, and communication rounds in quantum protocols.
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Explore circuit lower bounds and derandomization, focusing on AC circuits, algorithmic methods, and pseudorandom generators. Learn about recent developments in average-case circuit analysis.
Catalytic Approaches to the Tree Evaluation Problem
Explore catalytic approaches to the Tree Evaluation Problem, including pebbling games and catalytic space. Learn about multiplication lemmas and formulas for TEP.
Strong Self-Concordance and Sampling
Explore an algorithm for efficient polytope sampling, its connection to the KLS conjecture, and the properties of strong self-concordance in barrier functions.
Automating Cutting Planes is NP-Hard
Explore the complexity of automating cutting planes in computational geometry, covering historical context, algorithmic challenges, and proof systems.
On the Computability of Continuous Maximum Entropy Distributions with Applications
Explore computability of continuous maximum entropy distributions, their applications in quantum entropy and interior point methods, and implications for SDP rounding algorithms.
Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions
Explore unexpected findings on Kolmogorov complexity, including hardness results, limits, conjectures, and implications for pseudorandom generators and computational complexity.
A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Explore adaptive complexity in submodular maximization, covering nonmonotone approximation and hardness. Gain insights into this advanced computational topic through a concise presentation of key concepts and findings.
Are We Aging Well?
Explore the evolution and impact of Satisfiability (SAT) in computing theory over 50 years, including recent breakthroughs, algorithms, and its central role in computational complexity.