No. Title Author Year
1 Beyond Natural Proofs: Hardness Magnification and Locality Chen, Lijie et al. 2020
2 Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions Saks, Michael et al. 2020
3 Pseudorandomness and the Minimum Circuit Size Problem Santhanam, Rahul 2020
4 Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121) Gál, Anna et al. 2019
5 Hardness Magnification near State-Of-The-Art Lower Bounds Oliveira, Igor Carboni et al. 2019
6 Parity Helps to Compute Majority Oliveira, Igor Carboni et al. 2019
7 Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds Rajgopal, Ninad et al. 2018
8 Expander-Based Cryptography Meets Natural Proofs Carboni Oliveira, Igor et al. 2018
9 NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits Hirahara, Shuichi et al. 2018
10 Proof Complexity (Dagstuhl Seminar 18051) Atserias, Albert et al. 2018
11 Pseudo-Derandomizing Learning and Approximation Carboni Oliveira, Igor et al. 2018
12 Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness Oliveira, Igor C. Carboni et al. 2017
13 On the Average-Case Complexity of MCSP and Its Variants Hirahara, Shuichi et al. 2017
14 Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits Chen, Ruiwen et al. 2016
15 Exponential Time Paradigms Through the Polynomial Time Lens Drucker, Andrew et al. 2016
16 New Non-Uniform Lower Bounds for Uniform Classes Fortnow, Lance et al. 2016
17 Majority is Incompressible by AC^0[p] Circuits Oliveira, Igor Carboni et al. 2015
18 Optimal algorithms and proofs (Dagstuhl Seminar 14421) Beyersdorff, Olaf et al. 2015
19 Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes Jansen, Maurice et al. 2012
20 Unconditional Lower Bounds against Advice Buhrman, Harry et al. 2010
21 Fractional Pebbling and Thrifty Branching Programs Braverman, Mark et al. 2009
Current Page :
Number of result pages: 1
Number of documents: 21

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI