Image de couverture de livre

Polynomial-Time PIT from (Almost) Necessary Assumptions

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Andrews, Robert, Kush, Deepanshu, Tell, Roei
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
par: Kush, Deepanshu
Publié: (2026)

Lower Bounds for Set-Multilinear Branching Programs
par: Chatterjee, Prerona, et autres
Publié: (2023)

On Matrix Multiplication and Polynomial Identity Testing
par: Andrews, Robert
Publié: (2022)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
par: S., Karthik C., et autres
Publié: (2021)

Deterministic Depth-4 PIT and Normalization
par: Guo, Zeyu, et autres
Publié: (2025)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
par: Asadi, Vahid R., et autres
Publié: (2026)

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
par: Bharadwaj, G V Sumukha, et autres
Publié: (2024)

Algebraic Pseudorandomness in $VNC^0$
par: Andrews, Robert
Publié: (2025)

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
par: Garg, Abhibhav, et autres
Publié: (2025)

A Polynomial Time Algorithm for 3SAT
par: Quigley, Robert
Publié: (2024)

Almost-catalytic Computation
par: Bisoyi, Sagar, et autres
Publié: (2024)

One-Way Functions and Polynomial Time Dimension
par: Nandakumar, Satyadev, et autres
Publié: (2024)

An Improved Construction of Variety-Evasive Subspace Families
par: Andrews, Robert, et autres
Publié: (2026)

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
par: Guruswami, Venkatesan, et autres
Publié: (2024)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
par: Andrews, Robert, et autres
Publié: (2024)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
par: Wang, Cancan, et autres
Publié: (2024)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
par: DeJesse, Nicholas, et autres
Publié: (2025)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
par: He, Yumeng, et autres
Publié: (2024)

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
par: Kosoy, Vanessa, et autres
Publié: (2016)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
par: Chia, Nai-Hui, et autres
Publié: (2024)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
par: Le, Tran Duy Anh, et autres
Publié: (2024)

Necessary President in Elections with Parties
par: Cechlárová, Katarína, et autres
Publié: (2026)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
par: Gibor, Daniel
Publié: (2025)

Modular composition & polynomial GCD in the border of small, shallow circuits
par: Andrews, Robert, et autres
Publié: (2025)

Hilbert's Nullstellensatz is in the Counting Hierarchy
par: Andrews, Robert, et autres
Publié: (2026)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
par: Hörsch, Florian, et autres
Publié: (2025)

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
par: Babichenko, Yakov, et autres
Publié: (2015)

Qubit Routing for (Almost) Free
par: de Griend, Arianne Meijer-van
Publié: (2026)

Testing Isomorphism of Graphs in Polynomial Time
par: Xue, Rui
Publié: (2023)

Symmetric Algebraic Circuits and Homomorphism Polynomials
par: Dawar, Anuj, et autres
Publié: (2025)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
par: Michno, Katzper
Publié: (2025)

Lifting with Inner Functions of Polynomial Discrepancy
par: Manor, Yahel, et autres
Publié: (2024)

MP-Aggregation MP(R,2-WO) is Polynomial-Time Solvable When the Output Should Be Dichotomous Weak Preference Order
par: Chen, Jiehua
Publié: (2025)

There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$
par: Kayibi, Koko-Kalambay Kalafan
Publié: (2018)

RoPE Attention Can Be Trained in Almost Linear Time
par: Cao, Yang, et autres
Publié: (2024)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
par: Orzel, Ian
Publié: (2025)

Attacking the Polynomials in the Maze of Finite Fields problem
par: Barbero, Àngela, et autres
Publié: (2026)

On Factorization of Sparse Polynomials of Bounded Individual Degree
par: Chuyoon, Aminadav, et autres
Publié: (2026)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
par: Rajakumar, Joel, et autres
Publié: (2024)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
par: Rohatgi, Dhruv, et autres
Publié: (2025)