Copertina

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Arvind, V., Chatterjee, Abhranil, Mukhopadhyay, Partha
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Characterizing and Testing Principal Minor Equivalence of Matrices
di: Chatterjee, Abhranil, et al.
Pubblicazione: (2024)

Trading Determinism for Noncommutativity in Edmonds' Problem
di: Arvind, V., et al.
Pubblicazione: (2024)

Revisiting Tree Canonization using polynomials
di: Arvind, V., et al.
Pubblicazione: (2024)

Deterministic Independent Sets in the Semi-Streaming Model
di: Ye, Daniel
Pubblicazione: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
di: Grossman, Ofer, et al.
Pubblicazione: (2023)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
di: Bhattacharjee, Somnath, et al.
Pubblicazione: (2025)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
di: Kumar, Mrinal, et al.
Pubblicazione: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

On Optimal Testing of Linearity
di: Arora, Vipul, et al.
Pubblicazione: (2024)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
di: Gaspers, Serge, et al.
Pubblicazione: (2025)

The Trichotomy of Regular Property Testing
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

Improved Algorithm for Permutation Testing
di: Zhang, Xiaojin
Pubblicazione: (2020)

Testing Properties of Edge Distributions
di: Fei, Yumou
Pubblicazione: (2026)

Lower Bounds for Convexity Testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

Computational Complexity in Property Testing
di: Pinto Jr., Renato Ferreira, et al.
Pubblicazione: (2025)

Testing noisy low-degree polynomials for sparsity
di: Bao, Yiqiao, et al.
Pubblicazione: (2025)

Identity Testing for Circuits with Exponentiation Gates
di: Li, Jiatu, et al.
Pubblicazione: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
di: Li, Qian, et al.
Pubblicazione: (2025)

Privately Estimating Black-Box Statistics
di: Steinke, Günter F., et al.
Pubblicazione: (2025)

Sorting by Strip Swaps is NP-Hard
di: Roy, Swapnoneel, et al.
Pubblicazione: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
di: Sajith, Thejas Radhika
Pubblicazione: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
di: Chmel, Petr, et al.
Pubblicazione: (2026)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
di: Asadi, Vahid R., et al.
Pubblicazione: (2026)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
di: Grandjean, Étienne, et al.
Pubblicazione: (2025)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
di: Stoian, Mihail
Pubblicazione: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
di: Balzereit, Kaja, et al.
Pubblicazione: (2024)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
di: Rai, Shanthanu S
Pubblicazione: (2024)

Testing Sumsets is Hard
di: Chen, Xi, et al.
Pubblicazione: (2024)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
di: Chen, Shengminjie, et al.
Pubblicazione: (2026)

A General Framework for Low Soundness Homomorphism Testing
di: Mittal, Tushant, et al.
Pubblicazione: (2025)

Algorithms and Hardness for Estimating Statistical Similarity
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2025)

Computational Explorations of Total Variation Distance
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2024)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
di: Bai, Tian, et al.
Pubblicazione: (2026)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
di: Černý, Marek, et al.
Pubblicazione: (2025)

Complexity of Local Search for Euclidean Clustering Problems
di: Manthey, Bodo, et al.
Pubblicazione: (2023)