Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution (Q2255289): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.4007/annals.2015.181.2.1
+Normal rank
@@ Property / OpenAlex ID @@
+W2114400329
@@ Property / OpenAlex ID: W2114400329 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
+Normal rank
@@ Property / cites work @@
+Space Complexity in Propositional Calculus
@@ Property / cites work: Space Complexity in Propositional Calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom Generators in Propositional Proof Complexity
+Normal rank
@@ Property / cites work @@
+Q4681889
@@ Property / cites work: Q4681889 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3503433
@@ Property / cites work: Q3503433 / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum lower bounds by polynomials
@@ Property / cites work: Quantum lower bounds by polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Linear gaps between degrees for the polynomial calculus modulo distinct primes
+Normal rank
@@ Property / cites work @@
+Random CNF's are hard for the polynomial calculus
@@ Property / cites work: Random CNF's are hard for the polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+An exponential separation between the parity principle and the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Q4790380
@@ Property / cites work: Q4790380 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+On Interpolation and Automatization for Frege Systems
+Normal rank
@@ Property / cites work @@
+Q4228469
@@ Property / cites work: Q4228469 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness conductors and constant-degree lossless expanders
+Normal rank
@@ Property / cites work @@
+Q3729902
@@ Property / cites work: Q3729902 / rank @@
+Normal rank
@@ Property / cites work @@
+Candidate One-Way Functions Based on Expander Graphs
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Poisson approximation for large deviations
@@ Property / cites work: Poisson approximation for large deviations / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of cryptographical conjectures for \(S_2^1\) and EF
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Q4699287
@@ Property / cites work: Q4699287 / rank @@
+Normal rank
@@ Property / cites work @@
+On the weak pigeonhole principle
@@ Property / cites work: On the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Tautologies from Pseudo-Random Generators
@@ Property / cites work: Tautologies from Pseudo-Random Generators / rank @@
+Normal rank
@@ Property / cites work @@
+Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
+Normal rank
@@ Property / cites work @@
+CREW PRAM<scp>s</scp> and Decision Trees
@@ Property / cites work: CREW PRAM<scp>s</scp> and Decision Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Q4215637
@@ Property / cites work: Q4215637 / rank @@
+Normal rank
@@ Property / cites work @@
+Regular resolution lower bounds for the weak pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Q4850554
@@ Property / cites work: Q4850554 / rank @@
+Normal rank
@@ Property / cites work @@
+Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Q4818823
@@ Property / cites work: Q4818823 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for the polynomial calculus
@@ Property / cites work: Lower bounds for the polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Q4737899
@@ Property / cites work: Q4737899 / rank @@
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for perfect matching principles
+Normal rank
@@ Property / cites work @@
+Natural proofs
@@ Property / cites work: Natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution
+Normal rank
@@ Property / cites work @@
+The Complexity of Propositional                                                   Proofs
@@ Property / cites work: The Complexity of Propositional Proofs / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2255289