Lightnews — Scholar-powered news

LightNews

arXiv cs.CC Computational Complexity

@cscc-bot.bsky.social

20 followers 1 following 1.1K posts

Unofficial bot by @vele.bsky.social w/ http://github.com/so-okada/bXiv https://arxiv.org/list/cs.CC/new List https://bsky.app/profile/vele.bsky.social/lists/3lim7ccweqo2j ModList https://bsky.app/profile/vele.bsky.social/lists/3lim3qnexsw2g

Posts Media Videos Starter Packs

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Georgios Karaiskos, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert, Sevag Gharibian: How hard is it to verify a classical shadow? https://arxiv.org/abs/2510.08515 https://arxiv.org/pdf/2510.08515 https://arxiv.org/html/2510.08515

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Thomas Schuster, Dominik Kufel, Norman Y. Yao, Hsin-Yuan Huang: Hardness of recognizing phases of matter https://arxiv.org/abs/2510.08503 https://arxiv.org/pdf/2510.08503 https://arxiv.org/html/2510.08503

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Liang Mao, Laura Cui, Thomas Schuster, Hsin-Yuan Huang: Random unitaries that conserve energy https://arxiv.org/abs/2510.08448 https://arxiv.org/pdf/2510.08448 https://arxiv.org/html/2510.08448

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Laura Cui, Thomas Schuster, Liang Mao, Hsin-Yuan Huang, Fernando Brandao: Random unitaries from Hamiltonian dynamics https://arxiv.org/abs/2510.08434 https://arxiv.org/pdf/2510.08434 https://arxiv.org/html/2510.08434

Reposted by arXiv cs.CC Computational Complexity

arXiv cs.DM Discrete Mathematics @csdm-bot.bsky.social · 1d

Beisegel, Klost, Knorr, Ratajczak, Scheffler: A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers https://arxiv.org/abs/2510.08378 https://arxiv.org/pdf/2510.08378 https://arxiv.org/html/2510.08378

Reposted by arXiv cs.CC Computational Complexity

arXiv math.RT Representation Theory @mathrt-bot.bsky.social · 1d

van den Berg, Christandl, Lysikov, Nieuwboer, Walter, Zuiddam: Computing moment polytopes - with a focus on tensors, entanglement and matrix multiplication https://arxiv.org/abs/2510.08336 https://arxiv.org/pdf/2510.08336 https://arxiv.org/html/2510.08336

Reposted by arXiv cs.CC Computational Complexity

arXiv cs.DS Data Structures and Algorithms @csds-bot.bsky.social · 1d

Anton Herrmann, Christian Komusiewicz, Nils Morawietz, Frank Sommer: Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set https://arxiv.org/abs/2510.08124 https://arxiv.org/pdf/2510.08124 https://arxiv.org/html/2510.08124

Reposted by arXiv cs.CC Computational Complexity

arXiv cs.LO Logic in Computer Science @cslo-bot.bsky.social · 1d

Artem Chernobrovkin, Marco S\"alzer, Fran\c{c}ois Schwarzentruber, Nicolas Troquard: Verifying Graph Neural Networks with Readout is Intractable https://arxiv.org/abs/2510.08045 https://arxiv.org/pdf/2510.08045 https://arxiv.org/html/2510.08045

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Stephen Piddock: Quantum Max-Cut is NP hard to approximate https://arxiv.org/abs/2510.07995 https://arxiv.org/pdf/2510.07995 https://arxiv.org/html/2510.07995

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Chia-Ying Lin, Nai-Hui Chia, Shih-Han Hung: Efficient Closest Matrix Product State Learning in Logarithmic Depth https://arxiv.org/abs/2510.07798 https://arxiv.org/pdf/2510.07798 https://arxiv.org/html/2510.07798

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Thilo Scharnhorst, Jack Spilecki, John Wright: Optimal lower bounds for quantum state tomography https://arxiv.org/abs/2510.07699 https://arxiv.org/pdf/2510.07699 https://arxiv.org/html/2510.07699

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Ewin Tang, John Wright, Mark Zhandry: Conjugate queries can help https://arxiv.org/abs/2510.07622 https://arxiv.org/pdf/2510.07622 https://arxiv.org/html/2510.07622

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Robin Kothari, Ryan O'Donnell, Kewen Wu: No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore https://arxiv.org/abs/2510.07515 https://arxiv.org/pdf/2510.07515 https://arxiv.org/html/2510.07515

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 1d

Nai-Hui Chia, Yu-Ching Shen: 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH https://arxiv.org/abs/2510.07495 https://arxiv.org/pdf/2510.07495 https://arxiv.org/html/2510.07495

arXiv cs.CC Computational Complexity @cscc-bot.bsky.social · 1d

Michael Lampis: k-SUM Hardness Implies Treewidth-SETH https://arxiv.org/abs/2510.08185 https://arxiv.org/pdf/2510.08185 https://arxiv.org/html/2510.08185

arXiv cs.CC Computational Complexity @cscc-bot.bsky.social · 1d

Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, Kewen Wu: Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals https://arxiv.org/abs/2510.07808 https://arxiv.org/pdf/2510.07808 https://arxiv.org/html/2510.07808

arXiv cs.CC Computational Complexity @cscc-bot.bsky.social · 1d

[2025-10-10 Fri (UTC), 2 new articles found for csCC Computational Complexity]

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 2d

Varun Upreti, Ulysse Chabaud, Zo\"e Holmes, Armando Angrisani: When quantum resources backfire: Non-gaussianity and symplectic coherence in noisy bosonic circuits https://arxiv.org/abs/2510.07264 https://arxiv.org/pdf/2510.07264 https://arxiv.org/html/2510.07264

Reposted by arXiv cs.CC Computational Complexity

arXiv math.ST Statistics Theory @mathst-bot.bsky.social · 2d

Mengqi Lou, Guy Bresler, Ashwin Pananjady: Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs https://arxiv.org/abs/2510.07250 https://arxiv.org/pdf/2510.07250 https://arxiv.org/html/2510.07250

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 2d

Uma Girish, Alex May, Natalie Parham, Henry Yuen: Magic and communication complexity https://arxiv.org/abs/2510.07246 https://arxiv.org/pdf/2510.07246 https://arxiv.org/html/2510.07246

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 2d

Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert, Jop Bri\"et, Jonas Helsen: Clifford testing: algorithms and lower bounds https://arxiv.org/abs/2510.07164 https://arxiv.org/pdf/2510.07164 https://arxiv.org/html/2510.07164

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 2d

Junqiao Lin: MIPco=coRE https://arxiv.org/abs/2510.07162 https://arxiv.org/pdf/2510.07162 https://arxiv.org/html/2510.07162

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 2d

Ryu Hayakawa, Casper Gyurik, Mahtab Yaghubi Rad, Vedran Dunjko: Computational complexity of the homology problem with orientable filtration: MA-completeness https://arxiv.org/abs/2510.07014 https://arxiv.org/pdf/2510.07014 https://arxiv.org/html/2510.07014

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 2d

Jonathan Allcock, Joao F. Doriguello, G\'abor Ivanyos, Miklos Santha: Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more https://arxiv.org/abs/2510.06848 https://arxiv.org/pdf/2510.06848 https://arxiv.org/html/2510.06848

Reposted by arXiv cs.CC Computational Complexity

arXiv quant-ph Quantum Physics @quantph-bot.bsky.social · 2d

Sevag Gharibian, Jonas Kamminga: On the complexity of estimating ground state entanglement and free energy https://arxiv.org/abs/2510.06796 https://arxiv.org/pdf/2510.06796 https://arxiv.org/html/2510.06796