scientific article; zbMATH DE number 2087215
From MaRDI portal
Publication:4737899
zbMATH Open1073.03540MaRDI QIDQ4737899FDOQ4737899
Authors: Alexander Razborov 
Publication date: 11 August 2004
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2295/22950100.htm
Title of this publication is not available (Why is that?)
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Cited In (18)
- Phase transitions related to the pigeonhole principle
- Perfect matching in random graphs is as hard as Tseitin
- Resolution and the binary encoding of combinatorial principles
- Title not available (Why is that?)
- Large clique is hard on average for resolution
- Title not available (Why is that?)
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
- Partially definable forcing and bounded arithmetic
- The treewidth of proofs
- On the proof complexity of Paris-Harrington and off-diagonal Ramsey tautologies
- Propositional proof complexity
- Short proofs of the pigeonhole formulas based on the connection method
- Exploiting symmetry in SMT problems
- Expander construction in \(\mathrm{VNC}^1\)
- Resolution over linear equations and multilinear proofs
- Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Rank bounds for a hierarchy of Lovász and Schrijver
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4737899)
