Skip to main content
We gratefully acknowledge support from the Simons Foundation, member institutions, and all contributors. Donate
arXiv logo
Cornell University Logo

Computational Complexity

Authors and titles for recent submissions

See today's new changes

Total of 30 entries
Showing up to 50 entries per page: fewer | more | all

Mon, 1 Dec 2025 (showing 12 of 12 entries )

[1] arXiv:2511.23099 [pdf, html, other]
Title: On Computational Aspects of Cores of Ordered Graphs
Michal Čertík, Andreas Emil Feldmann, Jaroslav Nešetřil, Paweł Rzążewski
Comments: Submitted
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[2] arXiv:2511.23093 [pdf, html, other]
Title: On Computational Aspects of Ordered Matching Problems
Michal Čertík, Andreas Emil Feldmann, Jaroslav Nešetřil, Paweł Rzążewski
Comments: Accepted
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[3] arXiv:2511.23078 [pdf, html, other]
Title: Complexity Aspects of Homomorphisms of Ordered Graphs
Michal Čertík, Andreas Emil Feldmann, Jaroslav Nešetřil, Paweł Rzążewski
Comments: Accepted
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[4] arXiv:2511.22122 [pdf, html, other]
Title: Interactive Proofs For Distribution Testing With Conditional Oracles
Ari Biswas, Mark Bun, Clément Canonne, Satchit Sivakumar
Comments: To appear in ITCS 2026
Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
[5] arXiv:2511.21888 [pdf, other]
Title: Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
Kyle Burke, Caroline Cashman, Alfie Davies, Kanae Yoshiwatari, Francesca Yu
Comments: 21 pages, 23 figures
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[6] arXiv:2511.21738 [pdf, html, other]
Title: On the Incompressibility of Truth With Application to Circuit Complexity
Luke Tonon
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[7] arXiv:2511.23445 (cross-list from quant-ph) [pdf, html, other]
Title: Quantum Polymorphisms and Commutativity Gadgets
Lorenzo Ciardo, Gideo Joubert, Antoine Mottet
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Combinatorics (math.CO)
[8] arXiv:2511.22856 (cross-list from math.CO) [pdf, html, other]
Title: Algebraic Obstructions and the Collapse of Elementary Structure in the Kronecker Problem
Soong Kyum Lee
Comments: 25 pages, 3 tables, submitted to Advances in Mathematics
Subjects: Combinatorics (math.CO); Computational Complexity (cs.CC); Representation Theory (math.RT); Quantum Physics (quant-ph)
[9] arXiv:2511.22552 (cross-list from quant-ph) [pdf, html, other]
Title: Graphical Tests of Causality
Ämin Baumeler, Eleftherios-Ermis Tselentis, Stefan Wolf
Comments: 32 pages, 9 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
[10] arXiv:2511.22384 (cross-list from cs.GT) [pdf, other]
Title: Skating System Unveiled: Exploring Preference Aggregation in Ballroom Tournaments
Laryssa Horn (Heinrich-Heine-Universität Düsseldorf), Paul Nüsken (Heinrich-Heine-Universität Düsseldorf), Jörg Rothe (Heinrich-Heine-Universität Düsseldorf), Tessa Seeger (Heinrich-Heine-Universität Düsseldorf)
Comments: In Proceedings TARK 2025, arXiv:2511.20540
Journal-ref: EPTCS 437, 2025, pp. 271-285
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)
[11] arXiv:2511.22370 (cross-list from cs.GT) [pdf, other]
Title: Solving Four Open Problems about Core Stability in Altruistic Hedonic Games
Jörg Rothe, Ildikó Schlotter
Comments: In Proceedings TARK 2025, arXiv:2511.20540
Journal-ref: EPTCS 437, 2025, pp. 15-29
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)
[12] arXiv:2511.22117 (cross-list from cs.CR) [pdf, html, other]
Title: Privacy-preserving formal concept analysis: A homomorphic encryption-based concept construction
Qiangqiang Chen, Yunfeng Ke, Shen Li, Jinhai Li
Subjects: Cryptography and Security (cs.CR); Computational Complexity (cs.CC)

Thu, 27 Nov 2025 (showing 7 of 7 entries )

[13] arXiv:2511.21659 [pdf, html, other]
Title: Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
Guy Goldberg, Tom Gur, Sidhant Saraogi
Subjects: Computational Complexity (cs.CC); Information Theory (cs.IT); Combinatorics (math.CO)
[14] arXiv:2511.21450 [pdf, html, other]
Title: On the Usefulness of Promises
Per Austrin, Johan Håstad, Björn Martinsson
Subjects: Computational Complexity (cs.CC)
[15] arXiv:2511.21217 [pdf, html, other]
Title: Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
Chetan Gupta, Raghunath Tewari, Vimal Raj Sharma
Comments: Accepted in MFCS'2020
Subjects: Computational Complexity (cs.CC)
[16] arXiv:2511.21067 [pdf, html, other]
Title: Identifying Codes Kernelization Limitations
Aritra Banik, Praneet Kumar Patra, Adele Anna Rescigno, Abhishek Sahu
Subjects: Computational Complexity (cs.CC)
[17] arXiv:2511.21015 [pdf, html, other]
Title: The communication complexity of distributed estimation
Parikshit Gopalan, Raghu Meka, Prasad Raghavendra, Mihir Singhal, Avi Wigderson
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[18] arXiv:2511.21262 (cross-list from cs.GT) [pdf, other]
Title: Choosing What Game to Play without Selecting Equilibria: Inferring Safe (Pareto) Improvements in Binary Constraint Structures
Caspar Oesterheld (Carnegie Mellon University), Vincent Conitzer (Carnegie Mellon University)
Comments: In Proceedings TARK 2025, arXiv:2511.20540
Journal-ref: EPTCS 437, 2025, pp. 251-270
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); Multiagent Systems (cs.MA)
[19] arXiv:2511.20888 (cross-list from stat.ML) [pdf, html, other]
Title: Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
Arthur Jacot
Subjects: Machine Learning (stat.ML); Computational Complexity (cs.CC); Machine Learning (cs.LG)

Wed, 26 Nov 2025 (showing 2 of 2 entries )

[20] arXiv:2511.20023 [pdf, html, other]
Title: Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
Farzan Byramji, Russell Impagliazzo
Comments: An earlier version containing one of the results appeared as ECCC TR25-118
Subjects: Computational Complexity (cs.CC)
[21] arXiv:2511.20367 (cross-list from cs.DM) [pdf, html, other]
Title: Enumeration With Nice Roman Domination Properties
Kevin Mann
Comments: An extended abstract of this paper will be published in the proceedings of SOFSEM 2026
Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC)

Tue, 25 Nov 2025 (showing 4 of 4 entries )

[22] arXiv:2511.19212 [pdf, other]
Title: A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
Michał Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO)
[23] arXiv:2511.17821 (cross-list from quant-ph) [pdf, other]
Title: Quantum Algorithm for Estimating Gibbs Free Energy and Entropy via Energy Derivatives
Shangjie Guo, Corneliu Buda, Nathan Wiebe
Comments: 15 pages, 2 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
[24] arXiv:2511.17782 (cross-list from cs.LG) [pdf, html, other]
Title: Smoothed Agnostic Learning of Halfspaces over the Hypercube
Yiwen Kou, Raghu Meka
Subjects: Machine Learning (cs.LG); Computational Complexity (cs.CC); Machine Learning (stat.ML)
[25] arXiv:2511.17707 (cross-list from cs.DS) [pdf, html, other]
Title: Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
Elise Tate, Joshua A. Grochow
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

Mon, 24 Nov 2025 (showing 5 of 5 entries )

[26] arXiv:2511.17272 [pdf, html, other]
Title: Lower Bounds for CSP Hierarchies Through Ideal Reduction
Jonas Conneryd, Yassine Ghannane, Shuo Pang
Comments: 33 pages, to appear in SODA 2026
Subjects: Computational Complexity (cs.CC)
[27] arXiv:2511.17227 [pdf, html, other]
Title: A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
Xudong Wu, Guangxu Yang, Penghui Yao
Comments: 27 pages, 1 figure
Subjects: Computational Complexity (cs.CC); Quantum Physics (quant-ph)
[28] arXiv:2511.16903 [pdf, html, other]
Title: Simple Circuit Extensions for XOR in PTIME
Marco Carmosino, Ngu Dang, Tim Jackman
Subjects: Computational Complexity (cs.CC)
[29] arXiv:2511.17259 (cross-list from quant-ph) [pdf, other]
Title: Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
Chinonso Onah, Kristel Michielsen
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Computational Engineering, Finance, and Science (cs.CE); Discrete Mathematics (cs.DM); Mathematical Physics (math-ph)
[30] arXiv:2511.16918 (cross-list from cs.DS) [pdf, html, other]
Title: Low-Sensitivity Matching via Sampling from Gibbs Distributions
Yuichi Yoshida, Zihan Zhang
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
Total of 30 entries
Showing up to 50 entries per page: fewer | more | all