:: Library Catalog

Imagen de Portada

Guardado en:

Detalles Bibliográficos
Autores principales:	Arvind, V., Joglekar, Pushkar S.
Formato:	Preprint
Publicado:	2022
Materias:	Computational Complexity
Acceso en línea:	https://arxiv.org/abs/2202.09883
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
por: Arvind, Vikraman, et al.
Publicado: (2024)

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

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
por: Arvind, V., et al.
Publicado: (2023)

Some properties of Higman-Thompson monoids and digital circuits
por: Birget, J. C.
Publicado: (2024)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
por: Dutta, Pranjal, et al.
Publicado: (2024)

On Factorization of Sparse Polynomials of Bounded Individual Degree
por: Chuyoon, Aminadav, et al.
Publicado: (2026)

A Quadratic Lower Bound for Noncommutative Circuits
por: Shastri, Pratik
Publicado: (2026)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
por: S., Karthik C., et al.
Publicado: (2021)

Derandomizing Isolation In Catalytic Logspace
por: Arvind, V., et al.
Publicado: (2025)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
por: Mukhopadhyay, Partha, et al.
Publicado: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
por: Gibor, Daniel
Publicado: (2025)

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

On a Hierarchy of Spectral Invariants for Graphs
por: Arvind, V., et al.
Publicado: (2023)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
por: Wang, Cancan, et al.
Publicado: (2024)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
por: Tulsiani, Madhur, et al.
Publicado: (2024)

On Matrix Multiplication and Polynomial Identity Testing
por: Andrews, Robert
Publicado: (2022)

Lifting with Inner Functions of Polynomial Discrepancy
por: Manor, Yahel, et al.
Publicado: (2024)

Symmetric Algebraic Circuits and Homomorphism Polynomials
por: Dawar, Anuj, et al.
Publicado: (2025)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
por: Michno, Katzper
Publicado: (2025)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
por: Jiang, Cheng, et al.
Publicado: (2026)

Attacking the Polynomials in the Maze of Finite Fields problem
por: Barbero, Àngela, et al.
Publicado: (2026)

One-Way Functions and Polynomial Time Dimension
por: Nandakumar, Satyadev, et al.
Publicado: (2024)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
por: Orzel, Ian
Publicado: (2025)

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
por: Kahanamoku-Meyer, Gregory D., et al.
Publicado: (2024)

Extractors for Polynomial Sources over $\mathbb{F}_2$
por: Chattopadhyay, Eshan, et al.
Publicado: (2023)

Polynomial-Time PIT from (Almost) Necessary Assumptions
por: Andrews, Robert, et al.
Publicado: (2025)

Revisiting Tree Canonization using polynomials
por: Arvind, V., et al.
Publicado: (2024)

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings
por: Vu, Thi Xuan
Publicado: (2025)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
por: Chia, Nai-Hui, et al.
Publicado: (2024)

On the Characteristic Polynomial of Linearized Polynomials
por: Bastioni, Luca, et al.
Publicado: (2025)

An Efficient Quantum Factoring Algorithm
por: Regev, Oded
Publicado: (2023)

Low-Degree Polynomials Are Good Extractors
por: Alrabiah, Omar, et al.
Publicado: (2024)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
por: Komarath, Balagopal, et al.
Publicado: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
por: Cai, Jin-Yi, et al.
Publicado: (2024)

On the Expressibility of the Reconstructional Color Refinement
por: Arvind, V., et al.
Publicado: (2024)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
por: Bender, Matías, et al.
Publicado: (2025)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
por: Raz, Ran
Publicado: (2026)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
por: Amireddy, Prashanth, et al.
Publicado: (2025)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
por: Yao, Penghui, et al.
Publicado: (2025)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
por: Przybyłek, Michał R., et al.
Publicado: (2026)