| No. |
Title |
Author |
Year |
| 1 |
An Algorithmic Approach to Uniform Lower Bounds |
Santhanam, Rahul |
2023 |
| 2 |
A Relativization Perspective on Meta-Complexity |
Ren, Hanlin et al. |
2022 |
| 3 |
Errorless Versus Error-Prone Average-Case Complexity |
Hirahara, Shuichi et al. |
2022 |
| 4 |
Excluding PH Pessiland |
Hirahara, Shuichi et al. |
2022 |
| 5 |
Learning Algorithms Versus Automatability of Frege Systems |
Pich, Ján et al. |
2022 |
| 6 |
On Randomized Reductions to the Random Strings |
Saks, Michael et al. |
2022 |
| 7 |
Why MCSP Is a More Important Problem Than SAT (Invited Talk) |
Santhanam, Rahul |
2022 |
| 8 |
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121) |
Gál, Anna et al. |
2021 |
| 9 |
Hardness of KT Characterizes Parallel Cryptography |
Ren, Hanlin et al. |
2021 |
| 10 |
On the Pseudo-Deterministic Query Complexity of NP Search Problems |
Goldwasser, Shafi et al. |
2021 |
| 11 |
On the Structure of Learnability Beyond P/Poly |
Rajgopal, Ninad et al. |
2021 |
| 12 |
Beyond Natural Proofs: Hardness Magnification and Locality |
Chen, Lijie et al. |
2020 |
| 13 |
Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions |
Saks, Michael et al. |
2020 |
| 14 |
Pseudorandomness and the Minimum Circuit Size Problem |
Santhanam, Rahul |
2020 |
| 15 |
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121) |
Gál, Anna et al. |
2019 |
| 16 |
Hardness Magnification near State-Of-The-Art Lower Bounds |
Oliveira, Igor Carboni et al. |
2019 |
| 17 |
Parity Helps to Compute Majority |
Oliveira, Igor Carboni et al. |
2019 |
| 18 |
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds |
Rajgopal, Ninad et al. |
2018 |
| 19 |
Expander-Based Cryptography Meets Natural Proofs |
Carboni Oliveira, Igor et al. |
2018 |
| 20 |
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits |
Hirahara, Shuichi et al. |
2018 |
| 21 |
Proof Complexity (Dagstuhl Seminar 18051) |
Atserias, Albert et al. |
2018 |
| 22 |
Pseudo-Derandomizing Learning and Approximation |
Carboni Oliveira, Igor et al. |
2018 |
| 23 |
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness |
Oliveira, Igor C. Carboni et al. |
2017 |
| 24 |
On the Average-Case Complexity of MCSP and Its Variants |
Hirahara, Shuichi et al. |
2017 |
| 25 |
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits |
Chen, Ruiwen et al. |
2016 |
| 26 |
Exponential Time Paradigms Through the Polynomial Time Lens |
Drucker, Andrew et al. |
2016 |
| 27 |
New Non-Uniform Lower Bounds for Uniform Classes |
Fortnow, Lance et al. |
2016 |
| 28 |
Majority is Incompressible by AC^0[p] Circuits |
Oliveira, Igor Carboni et al. |
2015 |
| 29 |
Optimal algorithms and proofs (Dagstuhl Seminar 14421) |
Beyersdorff, Olaf et al. |
2015 |
| 30 |
Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes |
Jansen, Maurice et al. |
2012 |
| 31 |
Unconditional Lower Bounds against Advice |
Buhrman, Harry et al. |
2010 |
| 32 |
Fractional Pebbling and Thrifty Branching Programs |
Braverman, Mark et al. |
2009 |
