Hardness of graph-structured algebraic and symbolic problems

DOI10.1007/978-3-031-38906-1_16arXiv2109.12736OpenAlexW4385317379MaRDI QIDQ6179415

Yu Gao, Runze Wang, Jingbang Chen, Richard Peng, Yufan Huang

Publication date: 16 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.12736

zbMATH Keywords

graph Laplacianalgebraic computationfine-grained complexitycombinatorics and graph theory

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact solution of linear equations using p-adic expansions
• A probabilistic remark on algebraic program testing
• The shifted number system for fast linear algebra on integer matrices
• Progress on Polynomial Identity Testing-II
• Arithmetic Circuits: A survey of recent results and open questions
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Progress on Polynomial Identity Testing - II
• Generalized Nested Dissection
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Hardness Results for Structured Linear Systems
• Incomplete nested dissection
• Computing persistent homology
• Sparsified Cholesky and multigrid solvers for connection laplacians
• Approaching Optimality for Solving SDD Linear Systems
• Graph Connectivities, Network Coding, and Expander Graphs
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Nested Dissection of a Regular Finite Element Mesh
• The Factorization of Linear Graphs
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Matrix anti-concentration inequalities with applications

This page was built for publication: Hardness of graph-structured algebraic and symbolic problems