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

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

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

(19)

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

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)