Exponential lower bounds via exponential sums

DOI10.4230/LIPICS.ICALP.2024.24MaRDI QIDQ6875185zbMATH OpenFDO

Authors Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, Saswata Mukherjee

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.24

zbMATH Keywords

algebraic complexitycounting hierarchyexponential sumsparameterized complexitytau conjecture

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Characterizing Valiant's algebraic complexity classes
• Complexity classes defined by counting quantifiers
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• scientific article; zbMATH DE number 5604125 (Why is no real title available?)
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 7650211 (Why is no real title available?)
• Interpolation in Valiant's theory
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On defining integers and proving arithmetic circuit lower bounds
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• On the optimality of Bellman-Ford-Moore shortest path algorithm
• Parametrized complexity theory.
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• The complexity of combinatorial problems with succinct input representation
• The permanent of a square matrix
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Valiant's model and the cost of computing integers

This page was built for publication: Exponential lower bounds via exponential sums

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