On convex complexity measures

DOI10.1016/j.tcs.2010.02.004zbMath1192.68295OpenAlexW2137608191MaRDI QIDQ964405

Alexander S. Kulikov, Stasys P. Jukna, Pavel Hrubeš, 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

convexityrankmatrix normBoolean formulacomplexity measurecombinatorial rectangle

Mathematics Subject Classification ID

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

Related Items (4)

On the limits of gate elimination ⋮ On the nonnegative rank of distance matrices ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS

Cites Work

• Improvements on Khrapchenko's theorem
• A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
• The quantum adversary method and classical formula size power bounds
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• A New Rank Technique for Formula Size Lower Bounds
• The Shrinkage Exponent of de Morgan Formulas is 2
• Fractional Covers and Communication Complexity
• Lower bounds in communication complexity based on factorization norms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On convex complexity measures