Natural proofs
From MaRDI portal
Publication:5890841
DOI10.1145/195058.195134zbMath1345.68165OpenAlexW2294221698WikidataQ56701135 ScholiaQ56701135MaRDI QIDQ5890841
Steven Rudich, Alexander A. Razborov
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195134
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (11)
The correlation between parity and quadratic polynomials mod \(3\) ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ On the limits of gate elimination ⋮ Optimal bounds for the approximation of Boolean functions and some applications ⋮ A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) ⋮ Unnamed Item ⋮ The hunting of the SNARK ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Binary pattern tile set synthesis is NP-hard ⋮ Pseudorandom Functions: Three Decades Later
This page was built for publication: Natural proofs
