- The Complexity of Kemeny Aggregation with Three Rankings
2026/07/30 by Péter Madarasi · 1 voice
Computer Science · Mathematics · #cs.CC #cs.DM #cs.GT #math.CO #math.OC
- The Polynomial-Time Low-Degree Conjecture is False
2026/07/22 by Songtao Mao · 1 voice
#cs.CC #cs.DS
- Completeness of Canonical Closure Representations Is coNP-Complete
2026/07/20 by Mikhail Babin · 1 voice
#cs.DM #cs.CC #cs.LO
- Semi-Streaming Matching in a Single Pass II: Greedy is Optimal
2026/07/16 by Sepehr Assadi, Max Jiang, Mars Xiang · 5 voices
#cs.DS #cs.CC
- Completely Reachable Road Coloring
2026/07/13 by Mikhail V. Volkov, Yinfeng Zhu · 1 voice
#cs.FL #cs.CC
- Spectral gap of Lee-Yang Hamiltonians
2026/07/12 by Chaithanya Rayudu, Jun Takahashi · 2 voices
#quant-ph #cond-mat.stat-mech #cs.CC #math-ph
- Has quantum advantage been achieved?
2026/03/10 by Dominik Hangleiter · 2 voices
#quant-ph #cs.CC #physics.hist-ph
- Tetris is Hard with Just One Piece Type
2026/03/10 by MIT Hardness Group, Josh Brunner, Erik D. Demaine +2 · 1 voice
Computer Science · #cs.CC
- Reinforced Generation of Combinatorial Structures: Ramsey Numbers
2026/03/10 by Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta · 3 voices
#math.CO #cs.AI #cs.CC
- Flip Distance Between Triangulations of Convex Polygons is NP-Complete
2026/02/26 by Joseph Dorfer · 5 voices
#cs.CG #cs.CC #cs.DM #cs.DS #math.CO
- Markets are competitive if and only if P != NP
2026/02/23 by Philip Z. Maymin · 22 voices
#cs.GT #cs.CC #econ.TH #q-fin.CP
- Reducing the Complexity of Matrix Multiplication to O(N2log2N) by an Asymptotically Optimal Quantum Algorithm
2026/02/05 by Jiaqi Yao, Ding Liu · 1 voice
#quant-ph #cs.CC #cs.LG
- A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
2025/12/01 by Kean Chen, Qisheng Wang, Chen, Kean +3 · 1 voice · 2 citations
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Physics (quant-ph) #cs.CC #cs.IT #quant-ph
- Separating QMA from QCMA with a classical oracle
2025/11/12 by John Bostanci, Jonas Haferkamp, Bostanci, John +5 · 1 voice · 1 citation
#quant-ph #cs.CC
- Man, these New York Times games are hard! A computational perspective
2025/09/13 by Alessandro Giovanni Alberti, Flavio Chierichetti, Alberti, Alessandro Giovanni +9 · 8 voices
#cs.CC
- Random Unitaries in Constant (Quantum) Time
2025/08/15 by Ben Foxman, Natalie Parham, Foxman, Ben +5 · 1 voice · 10 citations
#quant-ph #cs.CC
- The vast world of quantum advantage
2025/08/07 by Hsin-Yuan Huang, Huang, Hsin-Yuan, Soonwon Choi +5 · 4 voices · 26 citations
#quant-ph #cs.CC #cs.IT
- The hidden subgroup problem for infinite groups
2025/07/24 by Greg Kuperberg, Kuperberg, Greg · 1 voice · 4 citations
#quant-ph #cs.CC #math.GR
- The Serial Scaling Hypothesis
2025/07/16 by Yuxi Liu, Konpat Preechakul, Liu, Yuxi +5 · 1 voice · 5 citations
#cs.LG #cs.CC #stat.ML
- Unitary designs in nearly optimal depth
2025/07/08 by Laura Cui, Thomas Schuster, Cui, Laura +5 · 1 voice · 14 citations
#quant-ph #cs.CC #cs.IT #math-ph
- Avoiding Obfuscation with Prover-Estimator Debate
2025/06/16 by Jonah Brown-Cohen, Geoffrey Irving, Brown-Cohen, Jonah +6 · 1 voice · 4 citations
#cs.AI #cs.CC #cs.DS
- New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
2025/06/09 by Alkida Balliu, Corinna Coupette, Balliu, Alkida +15 · 1 voice · 1 citation
#cs.DC #cs.CC
- Quantum circuit lower bounds in the magic hierarchy
2025/04/28 by Natalie Parham, Parham, Natalie · 1 voice · 6 citations
#quant-ph #cs.CC
- Learning to erase quantum states: thermodynamic implications of quantum learning theory
2025/04/09 by Haimeng Zhao, Yuzhen Zhang, Zhao, Haimeng +3 · 1 voice · 1 citation
#quant-ph #cond-mat.stat-mech #cs.CC #cs.IT #cs.LG
- Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition
2025/04/04 by Rishi Hazra, Hazra, Rishi, Gabriele Venturato +5 · 2 voices · 4 citations
Computer Science · Social Sciences · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Computational and Text Analysis Methods #FOS: Computer and information sciences #Machine Learning (cs.LG) #Natural Language Processing Techniques #Topic Modeling #cs.AI #cs.CC #cs.LG
- An exposition of recent list-size bounds of FRS Codes
2025/02/20 by Abhibhav Garg, Prahladh Harsha, Garg, Abhibhav +7 · 1 voice · 1 citation
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Coding theory and cryptography #cs.CC #cs.IT #graph theory and CDMA systems #math.CO
- Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
2025/02/12 by Dhruv Rohatgi, Dylan J. Foster, Rohatgi, Dhruv +1 · 1 voice · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Evolutionary Algorithms and Applications #cs.CC #cs.LG
- Intrinsic Barriers and Practical Pathways for Human-AI Alignment: An Agreement-Based Complexity Analysis
2025/02/09 by Aran Nayebi, Nayebi, Aran · 2 voices · 1 citation
Decision Sciences · #Innovation Diffusion and Forecasting #cs.AI #cs.CC #cs.GT #cs.LG #cs.MA
- Computing Game Symmetries and Equilibria That Respect Them
2025/01/15 by Emanuel Tewolde, Brian Hu Zhang, Tewolde, Emanuel +8 · 1 voice · 1 citation
Decision Sciences · #Game Theory and Applications #cs.AI #cs.CC #cs.GT #cs.MA
- Matrix Chaos Inequalities and Chaos of Combinatorial Type
2024/12/24 by Afonso S. Bandeira, Kevin Lucca, Bandeira, Afonso S. +5 · 1 voice · 4 citations
#math.PR #cs.CC #math.FA
more