On the complexity of computing a random Boolean function over the reals

DOI10.4086/TOC.2020.V016A009MaRDI QIDQ5140843zbMATH OpenOpenAlexFDO

Authors Pavel Hrubeš

Publication date 17 December 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

average casecomplexity theoryformula complexitylower boundsquantifier eliminationrandom Boolean function

Mathematics Subject Classification ID

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

Recommendations

• Complexity and Probability of Some Boolean Formulas
• Complexity of implementation of Boolean functions by real-valued formulas
• The effect of random restrictions on formula size
• How Do Read-Once Formulae Shrink?
• Lower bounds on the formula complexity of a linear Boolean function

Cites work

• Algorithms in real algebraic geometry
• Arithmetic circuits: a survey of recent results and open questions
• Arithmetic complexity in ring extensions
• Complexity of deciding Tarski algebra
• Definability and decision problems in arithmetic
• Definability and fast quantifier elimination in algebraically closed fields
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• scientific article; zbMATH DE number 3744549 (Why is no real title available?)
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• On the number of zero-patterns of a sequence of polynomials
• Real quantifier elimination is doubly exponential
• Representations of monotone Boolean functions by linear programs
• Some \(0/1\) polytopes need exponential size extended formulations
• Superpolynomial lower bounds for monotone span programs

Cited in

(10)

• On the complexity of finite random functions
• Efficient probabilistic algorithm for estimating the algebraic properties of Boolean functions for large n
• Oblivious bounds on the probability of boolean functions
• On Reliable Computation by Noisy Random Boolean Formulas
• scientific article; zbMATH DE number 3916176 (Why is no real title available?)
• scientific article; zbMATH DE number 4025336 (Why is no real title available?)
• The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity
• On the extension complexity of polytopes separating subsets of the Boolean cube
• Hard submatrices for nonnegative rank and communication complexity
• Hard submatrices for non-negative rank and communication complexity

This page was built for publication: On the complexity of computing a random Boolean function over the reals

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