LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE (Q5501765): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2105447726
@@ Property / OpenAlex ID: W2105447726 / rank @@
+Normal rank
@@ Property / cites work @@
+On approximate majority and probabilistic time
@@ Property / cites work: On approximate majority and probabilistic time / 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
@@ Property / cites work @@
+A Remark on Stirling's Formula
@@ Property / cites work: A Remark on Stirling's Formula / rank @@
+Normal rank
@@ Property / cites work @@
+A complexity gap for tree resolution
@@ Property / cites work: A complexity gap for tree resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Space complexity of random formulae in resolution
@@ Property / cites work: Space complexity of random formulae in resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+On uniformity within \(NC^ 1\)
@@ Property / cites work: On uniformity within \(NC^ 1\) / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
+Normal rank
@@ Property / cites work @@
+On sufficient conditions for unsatisfiability of random formulas
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+Special issue: Mathematical foundations of computer science. Selected papers from the 26th international symposium on mathematical foundations of computer science (MFCS 2001), Mariánské Lázně, Czech Republic, August 27-31, 2001
+Normal rank
@@ Property / cites work @@
+Q4275381
@@ Property / cites work: Q4275381 / rank @@
+Normal rank
@@ Property / cites work @@
+Theoretical computer science. Petri nets.
@@ Property / cites work: Theoretical computer science. Petri nets. / rank @@
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for the weak pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Proofs as Games
@@ Property / cites work: Proofs as Games / rank @@
+Normal rank
@@ Property / cites work @@
+A new proof of the weak pigeonhole principle
@@ Property / cites work: A new proof of the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Combinatorics of first order structures and propositional proof systems
+Normal rank
@@ Property / cites work @@
+On the weak pigeonhole principle
@@ Property / cites work: On the weak pigeonhole principle / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:5501765