:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Liu, Hui, Cao, Yi, Cai, Zehan, Mao, Hua, Chen, Jie
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2108.04000
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
by: Björklund, Andreas, et al.
Published: (2025)

Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
by: Arunachalam, Srinivasan, et al.
Published: (2021)

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

Learning complexity of gradient descent and conjugate gradient algorithms
by: Jiao, Xianqi, et al.
Published: (2024)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

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

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

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
by: Junchi, Ma, et al.
Published: (2024)

An Efficient Algorithm for Solving the 2-MAXSAT Problem
by: Chen, Yangjun
Published: (2023)

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

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

Approximation algorithms for noncommutative CSPs
by: Culf, Eric, et al.
Published: (2023)

A near-optimal Quadratic Goldreich-Levin algorithm
by: Briët, Jop, et al.
Published: (2025)

When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?
by: Chen, Yuansi, et al.
Published: (2023)

Singleton algorithms for the Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2025)

Efficient Matrix Product State Learning in Logarithmic Depth
by: Lin, Chia-Ying, et al.
Published: (2025)

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
by: Mao, Xinyu, et al.
Published: (2024)

A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
by: Kortsarz, Guy
Published: (2026)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
by: Liu, Zhenning, et al.
Published: (2024)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

Is a LOCAL algorithm computable?
by: Cruciani, Antonio, et al.
Published: (2026)

Bounded Dynamic Level Maintenance for Efficient Logic Optimization
by: Liu, Junfeng, et al.
Published: (2025)

Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Quantum algorithms for path and cycle containment problems
by: Cornelissen, Arjan, et al.
Published: (2026)

A slightly improved upper bound for quantum statistical zero-knowledge
by: Gall, François Le, et al.
Published: (2025)

How to fit large complexity classes into TFNP
by: Thapen, Neil
Published: (2024)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
by: Fan, Austen, et al.
Published: (2026)

On the Need for Large Quantum Depth
by: Chia, Nai-Hui, et al.
Published: (2019)

Complexity of some algorithmic problems in groups: a survey
by: Shpilrain, Vladimir
Published: (2024)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
by: Lou, Mengqi, et al.
Published: (2025)

Learning unitaries with quantum statistical queries
by: Angrisani, Armando
Published: (2023)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
by: Yi, Yongming
Published: (2026)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

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

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control
by: Krovi, Hari
Published: (2024)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
by: Bai, Tian, et al.
Published: (2026)

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

PSMC: Provable and Scalable Algorithms for Motif Conductance Based Graph Clustering
by: Lin, Longlong, et al.
Published: (2024)