Average-case rigidity lower bounds
type: Item
instance of: scholarly article
title: Average-case rigidity lower bounds
DOI: 10.1007/978-3-030-79416-3_11
author: Xuangui Huang
author: Emanuele Viola
publication date: 2022-03-21T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7493531
zbMATH Keywords: average-case lower bounds
zbMATH Keywords: matrix rigidity
zbMATH Keywords: correlation bounds
MaRDI profile type: Publication
full work available at URL: 978-3-030-79416-3 11
OpenAlex ID: W3177031611
cites work: Short PCPs with Projection Queries
cites work: Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
cites work: Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
cites work: Strong average-case lower bounds from non-trivial derandomization
cites work: Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
cites work: An average-case lower bound against \(\mathsf{ACC}^0\)
cites work: A hierarchy for nondeterministic time complexity
cites work: On Yao’s XOR-Lemma
cites work: Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
cites work: Q5875692
cites work: Q5005182
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Separating Nondeterministic Time Complexity Classes
cites work: Q4164821
cites work: Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
cites work: Improving exhaustive search implies superpolynomial lower bounds
cites work: Natural proofs versus derandomization
cites work: New algorithms and lower bounds for circuits with linear threshold gates
cites work: Nonuniform ACC Circuit Lower Bounds
cites work: A Turing machine time hierarchy
description: scientific article; zbMATH DE number 7493531