Buchumschlag

Exponential lower bound via exponential sums

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bhattacharjee, Somnath, Bläser, Markus, Dutta, Pranjal, Mukherjee, Saswata
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
von: Dutta, Pranjal, et al.
Veröffentlicht: (2024)

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
von: Agarwal, Sanyam, et al.
Veröffentlicht: (2026)

Probabilistic Generating Circuits -- Demystified
von: Agarwal, Sanyam, et al.
Veröffentlicht: (2024)

The Complexity of Order-Finding for ROABPs
von: Bhargava, Vishwas, et al.
Veröffentlicht: (2024)

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
von: Bläser, Markus, et al.
Veröffentlicht: (2025)

Simple general magnification of circuit lower bounds
von: Atserias, Albert, et al.
Veröffentlicht: (2025)

Depth lower bounds in Stabbing Planes for combinatorial principles
von: Dantchev, Stefan, et al.
Veröffentlicht: (2021)

Constant-depth circuits for polynomial GCD over any characteristic
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2025)

Closure under factorization from a result of Furstenberg
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2025)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
von: Gordeev, Lev, et al.
Veröffentlicht: (2026)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
von: Goubault-Larrecq, Aliénor, et al.
Veröffentlicht: (2025)

Exponential sums equations and the Exponential Closedness conjecture
von: Aslanyan, Vahagn, et al.
Veröffentlicht: (2024)

A note on quantum lower bounds for local search via congestion and expansion
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

Quantum circuit lower bounds in the magic hierarchy
von: Parham, Natalie
Veröffentlicht: (2025)

On the consistency of stronger lower bounds for NEXP
von: Thapen, Neil
Veröffentlicht: (2025)

The Existential Theory of the Reals with Summation Operators
von: Bläser, Markus, et al.
Veröffentlicht: (2024)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
von: Wu, Hao
Veröffentlicht: (2024)

From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
von: Dörfler, Julian, et al.
Veröffentlicht: (2024)

On the Complexity of Identification in Linear Structural Causal Models
von: Dörfler, Julian, et al.
Veröffentlicht: (2024)

The Limits of Tractable Marginalization
von: Broadrick, Oliver, et al.
Veröffentlicht: (2025)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2025)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2022)

Recent Advances in Debordering Methods
von: Dutta, Pranjal, et al.
Veröffentlicht: (2025)

On hardness of computing analytic Brouwer degree
von: Chakraborty, Somnath
Veröffentlicht: (2023)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
von: Hitchcock, John M.
Veröffentlicht: (2026)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2024)

Computational lower bounds for multi-frequency group synchronization
von: Kireeva, Anastasia, et al.
Veröffentlicht: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
von: Agarwal, Avantika, et al.
Veröffentlicht: (2024)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
von: Ron-Zewi, Noga, et al.
Veröffentlicht: (2024)

Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra
von: Dutta, Suman, et al.
Veröffentlicht: (2021)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
von: Geniet, Colin, et al.
Veröffentlicht: (2026)

A quasi-optimal lower bound for skew polynomial multiplication
von: Chen, Qiyuan, et al.
Veröffentlicht: (2024)

Probabilistic and Causal Satisfiability: Constraining the Model
von: Bläser, Markus, et al.
Veröffentlicht: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Clifford testing: algorithms and lower bounds
von: Hinsche, Marcel, et al.
Veröffentlicht: (2025)

Optimal lower bounds for quantum state tomography
von: Scharnhorst, Thilo, et al.
Veröffentlicht: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

Rice-like complexity lower bounds for Boolean and uniform automata networks
von: Goubault-Larrecq, Aliénor, et al.
Veröffentlicht: (2024)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
von: Chen, Zitan
Veröffentlicht: (2023)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
von: Bhattacharjee, Sutanay, et al.
Veröffentlicht: (2026)