scientific article; zbMATH DE number 4095383

MaRDI QIDQ3822097zbMATH OpenFDO

Authors Alexander Razborov

Publication date 1988

zbMATH Keywords

Boolean complexityBoolean functionsbounded depthcombinatorial problems for graphspolynomial size

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Generalized Ramsey theory (05C55)

Recommendations

• Improved boolean formulas for the Ramsey graphs
• Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables
• On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
• Upper bounds for the size and the depth of formulae for MOD-functions
• scientific article; zbMATH DE number 4085724

Cited in

(8)

• Almost \(k\)-wise independence and hard Boolean functions.
• The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes
• Combinatorial expressions and lower bounds
• scientific article; zbMATH DE number 4085724 (Why is no real title available?)
• Improved boolean formulas for the Ramsey graphs
• Formulas vs. circuits for small distance connectivity
• On bounded depth proofs for Tseitin formulas on the grid; revisited
• Random Boolean formulas representing any Boolean function with asymptotically equal probability

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 Q3822097)