On convex complexity measures

DOI10.1016/J.TCS.2010.02.004MaRDI QIDQ964405zbMATH OpenOpenAlexFDO

Authors Pavel Hrubeš, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák

Publication date 15 April 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.02.004

zbMATH Keywords

Boolean formulacombinatorial rectanglecomplexity measureconvexitymatrix normrank

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• An extension of Khrapchenko's theorem
• The effect of random restrictions on formula size
• A measure in which Boolean negation is exponentially powerful
• A New Rank Technique for Formula Size Lower Bounds
• scientific article; zbMATH DE number 176870

Cites work

• A method for obtaining more than quadratic effective lower estimates of complexity of schemes
• A New Rank Technique for Formula Size Lower Bounds
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Fractional Covers and Communication Complexity
• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 4078803 (Why is no real title available?)
• scientific article; zbMATH DE number 176870 (Why is no real title available?)
• scientific article; zbMATH DE number 3089101 (Why is no real title available?)
• Improvements on Khrapchenko's theorem
• Lower bounds in communication complexity based on factorization norms
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• The quantum adversary method and classical formula size power bounds
• The Shrinkage Exponent of de Morgan Formulas is 2

Cited in

(12)

• On the complexity of sums of Dirichlet measures
• Complexity of convex optimization using geometry-based measures and a reference point
• On the limits of gate elimination
• A probabilistic analysis of a measure of combinatorial complexity for the central curve
• A refinement of Cauchy-Schwarz complexity
• Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model
• On the nonnegative rank of distance matrices
• On the Complexity of Computing Two Nonlinearity Measures
• Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
• Breaking the rectangle bound barrier against formula size lower bounds
• Title not available (Why is no real title available?)
• An extension of Khrapchenko's theorem

This page was built for publication: On convex complexity measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q964405)