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 |