No label defined (Q5028364)

From MaRDI portal

Jump to:navigation, search

scientific article; zbMATH DE number 7471588

Language	Label	Description	Also known as
English	No label defined	scientific article; zbMATH DE number 7471588

Statements

scholarly article

0 references

Igor C. Oliveira

0 references

0 references

Rahul Santhanam

0 references

Theory of Computing

0 references

publication date

9 February 2022

0 references

zbMATH Keywords

circuit complexity

0 references

minimum circuit size problem

0 references

Kolmogorov complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.4086/toc.2021.v017a011

0 references

$$P\mathop{ =}\limits^{?}NP$$

0 references

Pseudorandom Generators in Propositional Proof Complexity

0 references

Power from Random Strings

0 references

Amplifying lower bounds by means of self-reducibility

0 references

0 references

Oracles and queries that are sufficient for exact learning

0 references

\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)

0 references

Learning algorithms from natural proofs

0 references

Universal classes of hash functions

0 references

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity

0 references

Computational Complexity

0 references

The Shrinkage Exponent of de Morgan Formulas is 2

0 references

Non-commutative circuits and the sum-of-squares problem

0 references

0 references

Size--Depth Tradeoffs for Threshold Circuits

0 references

0 references

Boolean function complexity. Advances and frontiers.

0 references

Class of constructive asymptotically good algebraic codes

0 references

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

0 references

Circuit-size lower bounds and non-reducibility to sparse sets

0 references

Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound

0 references

On the weak pigeonhole principle

0 references

Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds

0 references

Randomness conservation inequalities; information and independence in mathematical theories

0 references

Amplifying circuit lower bounds against polynomial time, with applications

0 references

Simple strategies for large zero-sum games with applications to complexity theory

0 references

Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

0 references

Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs

0 references

Feasibly constructive proofs of succinct weak circuit lower bounds

0 references

Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma

0 references

Hardness magnification near state-of-the-art lower bounds

0 references

Circuit lower bounds in bounded arithmetics

0 references

Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

0 references

Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution

0 references

0 references

Circuit Lower Bounds for Merlin–Arthur Classes

0 references

0 references

Linear-time encodable and decodable error-correcting codes

0 references

On the approximability of clique and related maximization problems

0 references

0 references

Nonuniform ACC Circuit Lower Bounds

0 references

Identifiers

zbMATH Open document ID

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

10.4086/TOC.2021.V017A011

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5028364

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q5028364&oldid=39514457"