31. On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
    2024/11/27 by Christoph Grüne, Lasse Wulf, Grüne, Christoph +1 · 1 voice · 2 citations
    Computer Science · Mathematics · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.CC #cs.DM #math.OC
32. QMA vs. QCMA and Pseudorandomness
    2024/11/21 by Jiahui Liu, Saachi Mutreja, Liu, Jiahui +3 · 1 voice · 1 citation
    Computer Science · Engineering · #Cellular Automata and Applications #Coding theory and cryptography #cs.CC #graph theory and CDMA systems #quant-ph
33. Uniformity testing when you have the source code
    2024/11/07 by Clément L. Canonne, Robin Kothari, Canonne, Clément L. +3 · 1 voice · 2 citations
    #quant-ph #cs.CC #cs.DS
34. Distributed Quantum Advantage for Local Problems
    2024/11/05 by Alkida Balliu, Balliu, Alkida, Sebastian Brandt +23 · 1 voice · 4 citations
    #cs.DC #cs.CC #quant-ph
35. Optimality of Frequency Moment Estimation
    2024/11/04 by Mark Braverman, Braverman, Mark, Or Zamir +1 · 1 voice · 1 citation
    Computer Science · Engineering · #Structural Health Monitoring Techniques #cs.CC #cs.DS #cs.IT
36. Gibbs state preparation for commuting Hamiltonian: Mapping to classical Gibbs sampling
    2024/10/07 by Yeongwoo Hwang, Jiaqing Jiang, Hwang, Yeongwoo +1 · 3 citations
    Mathematics · Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #Markov Chains and Monte Carlo Methods #Statistical Mechanics and Entropy #cs.CC #cs.DS #quant-ph
37. A polynomial-time classical algorithm for noisy quantum circuits
    2024/07/17 by Thomas Schuster, Chao Yin, Schuster, Thomas +5 · 2 voices · 18 citations
    Computer Science · #quant-ph #cs.CC #cs.IT #math-ph #physics.atom-ph
38. Geometric and computational hardness of bilevel programming
    2024/07/17 by Jérôme Bolte, Quoc-Tung Le, Bolte, Jérôme +5 · 1 voice · 2 citations
    #cs.CC #math.OC
39. Assembly Theory and its Relationship with Computational Complexity
    2024/06/18 by Christopher P. Kempes, Michael Lachmann, Kempes, Christopher P. +12 · 1 voice · 1 citation
    Engineering · #Manufacturing Process and Optimization #cs.CC
40. Models That Prove Their Own Correctness
    2024/05/24 by Noga Amit, Amit, Noga, Shafi Goldwasser +6 · 2 voices
    Computer Science · #cs.LG #cs.CC #cs.SE
41. Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
    2024/04/25 by Krishnamurthy Dvijotham, Dvijotham, Krishnamurthy, H. Brendan McMahan +7 · 1 voice · 2 citations
    Computer Science · Engineering · #Advanced MIMO Systems Optimization #Power Line Communications and Noise #Privacy-Preserving Technologies in Data #cs.CC #cs.CR #cs.DS #cs.LG
42. Online Locality Meets Distributed Quantum Computing
    2024/03/04 by Amirreza Akbari, Akbari, Amirreza, Xavier Coiteux-Roy +19 · 1 voice · 4 citations
    #cs.DC #cs.CC #math.PR #quant-ph
43. Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
    2024/02/20 by Zhiyuan Li, Hong Liu, Li, Zhiyuan +5 · 8 voices · 62 citations
    #cs.LG #cs.CC #stat.ML
44. Structure in Communication Complexity and Constant-Cost Complexity Classes
    2024/01/26 by Hamed Hatami, Pooya Hatami, Hatami, Hamed +1 · 1 citation
    Computer Science · Engineering · #Coding theory and cryptography #Quantum Computing Algorithms and Architecture #cs.CC #graph theory and CDMA systems
45. Envy-Free Cake-Cutting for Four Agents
    2023/11/03 by Alexandros Hollender, Hollender, Alexandros, Aviad Rubinstein +1 · 1 voice · 1 citation
    Computer Science · Engineering · #Logic, programming, and type systems #Optimization and Packing Problems #cs.CC #cs.GT #semigroups and automata theory
46. A one-query lower bound for unitary synthesis and breaking quantum cryptography
    2023/10/13 by Alex Lombardi, Fermi Ma, Lombardi, Alex +3 · 1 voice · 4 citations
    #quant-ph #cs.CC #cs.CR
47. Flat origami is Turing Complete
    2023/09/13 by Thomas C. Hull, Inna Zakharevich, Hull, Thomas C. +1 · 17 voices · 1 citation
    Biochemistry, Genetics and Molecular Biology · Engineering · #Advanced Materials and Mechanics #Cellular Mechanics and Interactions #Structural Analysis and Optimization #cs.CC #math.CO
48. Effect of non-unital noise on random circuit sampling
    2023/06/29 by Bill Fefferman, Soumik Ghosh, Fefferman, Bill +7 · 1 voice · 4 citations
    Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #cs.CC #quant-ph
49. Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective
    2023/05/24 by Guhao Feng, Feng, Guhao, Bohang Zhang +9 · 1 voice · 51 citations
    #cs.LG #cs.CC #cs.CL #stat.ML
50. An Efficient Algorithm for Solving the 2-MAXSAT Problem
    2023/04/25 by Yangjun Chen, Chen, Yangjun · 3 voices
    Computer Science · #Formal Methods in Verification #Logic, programming, and type systems #Natural Language Processing Techniques #cs.CC
51. SAT Requires Exhaustive Search
    2023/02/19 by Ke Xu, Xu, Ke, Guangyan Zhou +1 · 4 voices
    Computer Science · #cs.CC #cs.AI #cs.DM #cs.DS #math.CO
52. Unconditional Quantum Advantage for Sampling with Shallow Circuits
    2023/01/03 by Adam Bene Watts, Natalie Parham, Watts, Adam Bene +1 · 6 citations
    #quant-ph #cs.CC
53. The FBHHRBNRSSSHK-Algorithm for Multiplication in ℤ₂^5×5 is still not the end of the story
    2022/10/08 by Manuel Kauers, Kauers, Manuel, Jakob Moosbauer +1 · 2 voices
    Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Tensor decomposition and applications #cs.CC #cs.SC #graph theory and CDMA systems
54. Black holes and cryptocurrencies
    2022/05/25 by Alexey Milekhin, Milekhin, Alexey · 1 voice
    Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #General Relativity and Quantum Cosmology (gr-qc) #High Energy Physics - Theory (hep-th) #cs.CC #gr-qc #hep-th
55. Wordle is NP-hard
    2022/03/30 by Daniel Lokshtanov, Bernardo Subercaseaux, Lokshtanov, Daniel +1 · 5 voices
    #cs.CC
56. Making Life More Confusing for Firefighters
    2022/02/25 by Samuel Hand, Jessica Enright, Hand, Samuel +3 · 1 voice · 1 citation
    #cs.DS #cs.CC #cs.DM
57. Locally Testable Codes with constant rate, distance, and locality
    2021/11/08 by Irit Dinur, Shai Evra, Dinur, Irit +7 · 1 voice · 11 citations
    Computer Science · Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #Information Theory (cs.IT) #cs.CC #cs.IT #math.GR
58. MAJORITY-3SAT (and Related Problems) in Polynomial Time
    2021/07/06 by Shyan Akmal, Ryan Williams, Akmal, Shyan +1 · 1 voice
    #cs.CC #cs.AI #cs.DS
59. On Lev Gordeev's "On P Versus NP"
    2021/04/14 by David E. Narváez, David Narváez, Patrick Phillips +2 · 1 voice
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Low-power high-performance VLSI design #Numerical Methods and Algorithms #cs.CC
60. A Refined Laser Method and Faster Matrix Multiplication
    2020/10/12 by Josh Alman, Virginia Vassilevska Williams · 1 voice · 8 citations
    #cs.DS #cs.CC #math.CO

prev more