Buchumschlag

Polynomial Identity Testing via Evaluation of Rational Functions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Hu, Ivan, van Melkebeek, Dieter, Morgan, Andrew
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Computational Complexity 68Q17, 68Q87, 68Q15
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Separation of $NP$ and $PSPACE$
von: Lin, Tianrong
Veröffentlicht: (2021)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
von: Lin, Tianrong
Veröffentlicht: (2023)

Unifying lower bounds for algebraic machines, semantically
von: Seiller, Thomas, et al.
Veröffentlicht: (2018)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
von: Edwards, Darren J.
Veröffentlicht: (2025)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
von: Lin, Tianrong
Veröffentlicht: (2021)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
von: Abdullah, Duaa, et al.
Veröffentlicht: (2025)

Beyond the Existential Theory of the Reals
von: Schaefer, Marcus, et al.
Veröffentlicht: (2022)

Completeness classes in algebraic complexity theory
von: Bürgisser, Peter
Veröffentlicht: (2024)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
von: Shalunov, Yakov
Veröffentlicht: (2023)

P not equal to NP
von: Delgado, Daniel Cardona
Veröffentlicht: (2023)

Resolution of The Linear-Bounded Automata Question
von: Lin, Tianrong
Veröffentlicht: (2021)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2025)

Undefinability of Approximation of 2-to-2 Games
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

Some derivations among Logarithmic Space Bounded Counting Classes
von: Janaki, V., et al.
Veröffentlicht: (2023)

Generalisations of Matrix Partitions : Complexity and Obstructions
von: Barsukov, Alexey, et al.
Veröffentlicht: (2021)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
von: Zhang, Weikun K., et al.
Veröffentlicht: (2026)

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

Shifted Partial Derivative Polynomial Rank and Codimension
von: Edwards, Darren J.
Veröffentlicht: (2025)

The Algorithmic Phase Transition in Correlated Spiked Models
von: Li, Zhangsong
Veröffentlicht: (2025)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
von: Meir, Or
Veröffentlicht: (2023)

Condensing and Extracting Against Online Adversaries
von: Chattopadhyay, Eshan, et al.
Veröffentlicht: (2024)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
von: Kumar, Mrinal, et al.
Veröffentlicht: (2018)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
von: Li, Zhangsong
Veröffentlicht: (2026)

On the Low Weight Polynomial Multiple Problem
von: Ţiplea, Ferucio Laurenţiu, et al.
Veröffentlicht: (2024)

Weighted Automata and Logics Meet Computational Complexity
von: Kostolányi, Peter
Veröffentlicht: (2023)

Fully Characterizing Lossy Catalytic Computation
von: Folkertsma, Marten, et al.
Veröffentlicht: (2024)

Quantum Lower Bounds by Sample-to-Query Lifting
von: Wang, Qisheng, et al.
Veröffentlicht: (2023)

Choiceless Polynomial Space
von: Ferrarotti, Flavio, et al.
Veröffentlicht: (2024)

A study of distributional complexity measures for Boolean functions
von: Köhler-Schindler, Laurin, et al.
Veröffentlicht: (2024)

The Complexity of Iterated Reversible Computation
von: Eppstein, David
Veröffentlicht: (2021)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
von: Marković, Petar, et al.
Veröffentlicht: (2026)

Teaching and Learning under Deductive Errors
von: Telle, Jan Arne, et al.
Veröffentlicht: (2026)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
von: Li, Zhangsong
Veröffentlicht: (2025)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
von: Ahn, Jungho, et al.
Veröffentlicht: (2022)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
von: Lela, Marko
Veröffentlicht: (2025)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
von: Saffidine, Abdallah, et al.
Veröffentlicht: (2025)

Algorithms for Minimum Membership Dominating Set Problem
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2024)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
von: Ye, Lixi
Veröffentlicht: (2026)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
von: Böhnlein, Toni, et al.
Veröffentlicht: (2024)

Computational Complexity of Determining the Assembly Index
von: Masierak, Piotr
Veröffentlicht: (2026)