Parameterized Bounded-Depth Frege Is Not Optimal (Q3012838): Difference between revisions

@@ Property / author @@
+Alexander A. Razborov
@@ Property / author: Alexander A. Razborov / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1572996061
@@ Property / OpenAlex ID: W1572996061 / rank @@
+Normal rank
@@ Property / cites work @@
+Resolution Is Not Automatizable Unless W[P] Is Tractable
+Normal rank
@@ Property / cites work @@
+The resolution complexity of independent sets and vertex covers in random graphs
+Normal rank
@@ Property / cites work @@
+The Efficiency of Resolution and Davis--Putnam Procedures
+Normal rank
@@ Property / cites work @@
+Parameterized Complexity of DPLL Search Procedures
+Normal rank
@@ Property / cites work @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+Polynomial size proofs of the propositional pigeonhole principle
+Normal rank
@@ Property / cites work @@
+The parameterized complexity of maximality and minimality problems
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Parameterized proof complexity
@@ Property / cites work: Parameterized proof complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Describing parameterized complexity classes
@@ Property / cites work: Describing parameterized complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / 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 @@
+Exponential lower bounds for the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
+Normal rank
@@ Property / cites work @@
+A complexity gap for tree resolution
@@ Property / cites work: A complexity gap for tree resolution / rank @@
+Normal rank