scientific article; zbMATH DE number 7286919

DOI10.4086/toc.2020.v016a009zbMath1462.68071OpenAlexW3112656254MaRDI QIDQ5140843

Pavel Hrubeš

Publication date: 17 December 2020

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2020.v016a009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

quantifier eliminationlower boundscomplexity theoryformula complexityaverage caserandom Boolean function

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Quantifier elimination, model completeness, and related topics (03C10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

On the extension complexity of polytopes separating subsets of the Boolean cube

Cites Work

• Unnamed Item
• Unnamed Item
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• Definability and fast quantifier elimination in algebraically closed fields
• Real quantifier elimination is doubly exponential
• Expressing combinatorial optimization problems by linear programs
• Complexity of deciding Tarski algebra
• Superpolynomial lower bounds for monotone span programs
• Some \(0/1\) polytopes need exponential size extended formulations
• On the number of zero-patterns of a sequence of polynomials
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Arithmetic Circuits: A survey of recent results and open questions
• The Matching Polytope has Exponential Extension Complexity
• Representations of Monotone Boolean Functions by Linear Programs
• Lower Bounds for Approximation by Nonlinear Manifolds
• Definability and decision problems in arithmetic
• Algorithms in real algebraic geometry

This page was built for publication: