:: Library Catalog

Imatge de la portada

Guardat en:

Dades bibliogràfiques
Autors principals:	Cai, Jin-Yi, Maran, Ashwin
Format:	Preprint
Publicat:	2024
Matèries:	Computational Complexity
Accés en línia:	https://arxiv.org/abs/2412.17122
Etiquetes:	Afegir etiqueta Sense etiquetes, Sigues el primer a etiquetar aquest registre!

Ítems similars

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
per: Cai, Jin-Yi, et al.
Publicat: (2026)

The complexity of frugal digraph homomorphisms
per: Bard, Stefan, et al.
Publicat: (2026)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
per: Esmer, Barış Can, et al.
Publicat: (2022)

The complexity of testing all properties of planar graphs, and the role of isomorphism
per: Basu, Sabyasachi, et al.
Publicat: (2021)

Obstruction theory and the complexity of counting group homomorphisms
per: Samperton, Eric, et al.
Publicat: (2026)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
per: Carbonnel, Clément
Publicat: (2026)

Complexity classification of counting graph homomorphisms modulo a prime number
per: Bulatov, Andrei A., et al.
Publicat: (2021)

Between proper and square coloring of planar graphs, hardness and extremal graphs
per: Delépine, Thomas
Publicat: (2026)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
per: Khanna, Sanjeev, et al.
Publicat: (2025)

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

Holant* Dichotomy on Domain Size 3: A Geometric Perspective
per: Cai, Jin-Yi, et al.
Publicat: (2025)

On the complexity of embedding in graph products
per: Biedl, Therese, et al.
Publicat: (2023)

Lower bounds for planar Arithmetic Circuits
per: Ramya, C., et al.
Publicat: (2025)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
per: Colli, Giordano
Publicat: (2025)

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

Privacy-preserving formal concept analysis: A homomorphic encryption-based concept construction
per: Chen, Qiangqiang, et al.
Publicat: (2025)

Polynomial-like dynamics of analytic maps
per: Levin, Genadi
Publicat: (2025)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
per: Dumas, Maël, et al.
Publicat: (2022)

Average-case deterministic query complexity of boolean functions with fixed weight
per: Li, Yuan, et al.
Publicat: (2024)

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

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

On Matrix Multiplication and Polynomial Identity Testing
per: Andrews, Robert
Publicat: (2022)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
per: Michno, Katzper
Publicat: (2025)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
per: Rajakumar, Joel, et al.
Publicat: (2024)

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

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

Computing the Elementary Symmetric Polynomials in Positive Characteristics
per: Orzel, Ian
Publicat: (2025)

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

On the complexity of global Roman domination problem in graphs
per: Reddy, Sangam Balchandar, et al.
Publicat: (2026)

Fast simulation of planar Clifford circuits
per: Gosset, David, et al.
Publicat: (2020)

Random regular graph states are complex at almost any depth
per: Ghosh, Soumik, et al.
Publicat: (2024)

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

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

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

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

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

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
per: Arvind, V., et al.
Publicat: (2022)

Isometric path complexity of graphs
per: Chakraborty, Dibyayan, et al.
Publicat: (2022)

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

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