Beyond natural proofs: Hardness magnification and locality

Beyond natural proofs: Hardness magnification and locality

Hardness magnification reduces major complexity separations (such as EXP ⊈ NC^1) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [Igor Carboni Oliveira and Rahul Santhanam, 2018; Dylan M. McKay et al., 2019; Lijie Chen and Roei Tell, 2019; Igor Ca...

Full description

Bibliographic Details
Main Authors:	Chen, L, Hirahara, S, Oliveira, IC, Pich, J, Rajgopal, N, Santhanam, R
Format:	Conference item
Language:	English
Published:	Schloss Dagstuhl 2020

Similar Items

Beyond natural proofs: hardness magnification and locality
by: Chen, Lijie, et al.
Published: (2022)

Hardness magnification for natural problems
by: Santhanam, R, et al.
Published: (2018)

Hardness magnification near state-of-the-art lower bounds
by: Oliveira, IC, et al.
Published: (2021)

Hardness magnification near state-of-the-art lower bounds
by: Oliveira, I, et al.
Published: (2019)

Why are proof complexity lower bounds hard?
by: Pich, J, et al.
Published: (2020)

NP-hardness of minimum circuit size problem for OR-AND-MOD circuits
by: Hirahara, S, et al.
Published: (2018)

Reasons for hardness in QBF proof systems
by: Beyersdorff, O, et al.
Published: (2020)

Hardness Magnification for all Sparse NP Languages
by: Chen, Lijie, et al.
Published: (2021)

On the structure of learnability beyond P/poly
by: Rajgopal, N, et al.
Published: (2021)

Expander-based cryptography meets natural proofs
by: Oliveira, I, et al.
Published: (2018)

From proof complexity to circuit complexity via interactive protocols
by: Arteche, N, et al.
Published: (2024)

Physical magnification of objects
by: Boyden, Edward
Published: (2018)

Excluding PH Pessiland
by: Hirahara, S, et al.
Published: (2022)

Errorless versus error-prone average-case complexity
by: Hirahara, S, et al.
Published: (2022)

On the average-case complexity of MCSP and its variants
by: Hirahara, S, et al.
Published: (2017)

Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
by: Yang, Lisa L.
Published: (2022)

An average-case lower bound against ACC$^0$
by: Chen, R, et al.
Published: (2018)

Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
by: Rajgopal, N, et al.
Published: (2018)

Size magnification as a complement to cosmic shear
by: Casaponsa, B, et al.
Published: (2013)

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
by: Pich, J, et al.
Published: (2021)

Learning algorithms versus automatability of Frege systems
by: Pich, J, et al.
Published: (2022)

The augmented human - visual movement magnification
by: Siti Nazhura Muhamad Anuar
Published: (2022)

Learning-Based Video Motion Magnification
by: Oh, Tae-Hyun, et al.
Published: (2021)

The augmented human - visual movement magnification
by: Tan, Ryan Jinn-En
Published: (2023)

Relating Proof Complexity Measures and Practical Hardness of SAT
by: Järvisalo, M, et al.
Published: (2012)

Disentangling magnification in combined shear-clustering analyses
by: Thiele, L, et al.
Published: (2019)

A linear-optical proof that the permanent is #P-hard
by: Aaronson, Scott
Published: (2012)

Why effective proof tool support for Z is hard
by: Martin, A
Published: (1997)

High-magnification microgripper with low output displacement loss
by: Chen, Xiaodong, et al.
Published: (2023)

Computational hair quality categorization in lower magnifications
by: Heshmat Dehkordi, Barmak, et al.
Published: (2017)

Computational role of eccentricity dependent cortical magnification
by: Poggio, Tomaso, et al.
Published: (2015)

Quaternionic Representation of the Riesz Pyramid for Video Magnification
by: Wadhwa, Neal, et al.
Published: (2014)

Pseudodeterministic algorithms and the structure of probabilistic time
by: Lu, Z, et al.
Published: (2021)

Hardness of KT characterizes parallel cryptography
by: Ren, H, et al.
Published: (2021)

A simple proof that the (n2 − 1)-puzzle is hard
by: Demaine, Erik D, et al.
Published: (2021)

A simple proof that the (n2 − 1)-puzzle is hard
by: Demaine, Erik D, et al.
Published: (2022)

GGH15 Beyond Permutation Branching Programs: Proofs, Attacks, and Candidates
by: Chen, Yilei, et al.
Published: (2021)

DeepMag: Source Specific Change Magnification Using Gradient Ascent
by: Chen, Weixuan, et al.
Published: (2022)

Remote monitoring of health signs with Eulerian video magnification
by: Tan, Stanley Yi Rui
Published: (2023)

Deviation magnification: Revealing departures from ideal geometries
by: Wadhwa, Neal, et al.
Published: (2015)