scientific article; zbMATH DE number 910895

MaRDI QIDQ4886070zbMATH OpenFDO

Authors Jeff Erickson

Publication date 28 July 1996

zbMATH Keywords

decision problems

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Real and complex fields (12D99)

Recommendations

• scientific article; zbMATH DE number 1351079
• Lower bounds for linear degeneracy testing
• Lower bounds for linear degeneracy testing
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Lower bounds for linear decision trees with bounded weights

Cited in

(17)

• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Lower bounds for some decision problems over \(C\)
• Lower bounds for linear degeneracy testing
• Finding submasses in weighted strings with fast Fourier transform
• Linear FPT reductions and computational lower bounds
• Results related to threshold phenomena research in satisfiability: Lower bounds
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Complexity Results for Linear XSAT-Problems
• \(k\)-SUM in the sparse regime: complexity and applications
• Arboral satisfaction: recognition and LP approximation
• Exact weight subgraphs and the \(k\)-sum conjecture
• Some lower bound results for set-multilinear arithmetic computations
• Improved subquadratic 3SUM
• Some geometric lower bounds
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• scientific article; zbMATH DE number 3988710 (Why is no real title available?)
• On 3SUM-hard problems in the decision tree model

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