Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with natural proofs:
TR08-038 | 4th April 2008
Eric Allender, Michal Koucky

Amplifying Lower Bounds by Means of Self-Reducibility

Revisions: 2

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

TR11-076 | 7th May 2011
Eric Miles, Emanuele Viola

The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we ... more >>>

TR16-008 | 26th January 2016
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Algorithms from Natural Lower Bounds

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>

TR17-009 | 19th January 2017
Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

Towards an algebraic natural proofs barrier via polynomial identity testing

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

TR17-091 | 17th May 2017
Andrej Bogdanov

Small bias requires large formulas

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas ... more >>>

TR17-144 | 27th September 2017
Moritz Müller, Ján Pich

Feasibly constructive proofs of succinct weak circuit lower bounds

We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length $n$. In 1995 Razborov showed that many can be proved in Cook’s theory $PV_1$, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small $n$ of ... more >>>

ISSN 1433-8092 | Imprint