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 26 entries
Showing up to 50 entries per page: fewer | more | all

Fri, 22 Nov 2024 (showing 7 of 7 entries )

[1] arXiv:2411.14431 [pdf, html, other]
Title: On Optimal Testing of Linearity
Vipul Arora, Esty Kelman, Uri Meir
Comments: To appear at SOSA 2025
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[2] arXiv:2411.14361 [pdf, html, other]
Title: Improved Lower Bounds for all Odd-Query Locally Decodable Codes
Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, Andrew D. Lin
Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
[3] arXiv:2411.14314 [pdf, html, other]
Title: Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
Jeff Xu
Subjects: Computational Complexity (cs.CC)
[4] arXiv:2411.14276 [pdf, html, other]
Title: A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
Oliver Janzer, Peter Manohar
Subjects: Computational Complexity (cs.CC); Information Theory (cs.IT)
[5] arXiv:2411.14268 [pdf, html, other]
Title: Supercritical Tradeoffs for Monotone Circuits
Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov
Subjects: Computational Complexity (cs.CC)
[6] arXiv:2411.14267 [pdf, other]
Title: Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang
Comments: 47 pages, 7 figures
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO)
[7] arXiv:2411.14416 (cross-list from quant-ph) [pdf, html, other]
Title: QMA vs. QCMA and Pseudorandomness
Jiahui Liu, Saachi Mutreja, Henry Yuen
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)

Thu, 21 Nov 2024 (showing 3 of 3 entries )

[8] arXiv:2411.13348 [pdf, html, other]
Title: Parameterized Complexity of Star Decomposition Problem
Sahab Hajebi, Ramin Javadi
Subjects: Computational Complexity (cs.CC)
[9] arXiv:2411.13141 [pdf, html, other]
Title: (Independent) Roman Domination Parameterized by Distance to Cluster
Pradeesha Ashok, Gautam K. Das, Arti Pandey, Kaustav Paul, Subhabrata Paul
Comments: arXiv admin note: text overlap with arXiv:2405.10556 by other authors
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[10] arXiv:2411.13015 [pdf, html, other]
Title: Strong XOR Lemma for Information Complexity
Pachara Sawettamalya, Huacheng Yu
Subjects: Computational Complexity (cs.CC); Information Theory (cs.IT)

Wed, 20 Nov 2024 (showing 3 of 3 entries )

[11] arXiv:2411.12512 [pdf, html, other]
Title: Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Kiril Bangachev, Guy Bresler, Stefan Tiegel, Vinod Vaikuntanathan
Comments: Abstract shortened to match arXiv requirements
Subjects: Computational Complexity (cs.CC); Cryptography and Security (cs.CR); Discrete Mathematics (cs.DM); Statistics Theory (math.ST)
[12] arXiv:2411.12730 (cross-list from quant-ph) [pdf, other]
Title: Testing classical properties from quantum data
Matthias C. Caro, Preksha Naik, Joseph Slote
Comments: 38 + 14 pages, 2 tables, 2 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[13] arXiv:2411.12131 (cross-list from quant-ph) [pdf, other]
Title: Empowering Large Scale Quantum Circuit Development: Effective Simulation of Sycamore Circuits
Venkateswaran Kasirajan, Torey Battelle, Bob Wold
Comments: 10 pages, 5 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Emerging Technologies (cs.ET)

Tue, 19 Nov 2024 (showing 11 of 11 entries )

[14] arXiv:2411.11611 [pdf, html, other]
Title: Improved PIR Schemes using Matching Vectors and Derivatives
Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
Comments: 16 pages
Subjects: Computational Complexity (cs.CC); Information Theory (cs.IT)
[15] arXiv:2411.10996 [pdf, html, other]
Title: Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
Xinyu Mao, Guangxu Yang, Jiapeng Zhang
Subjects: Computational Complexity (cs.CC)
[16] arXiv:2411.10870 [pdf, html, other]
Title: Near-Optimal Averaging Samplers and Matrix Samplers
Zhiyang Xun, David Zuckerman
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[17] arXiv:2411.10453 [pdf, other]
Title: Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
Gabriel Istrate
Comments: In Proceedings FROM 2024, arXiv:2410.23020. An extended version is under preparation and will also be posted on arXiv
Journal-ref: EPTCS 410, 2024, pp. 38-52
Subjects: Computational Complexity (cs.CC); Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM)
[18] arXiv:2411.11805 (cross-list from quant-ph) [pdf, html, other]
Title: On the hardness of cloning and connections to representation theory
Vojtěch Havlíček, Chinmay Nirkhe
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
[19] arXiv:2411.11722 (cross-list from math.OC) [pdf, html, other]
Title: Solving convex QPs with structured sparsity under indicator conditions
Daniel Bienstock, Tongtong Chen
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[20] arXiv:2411.11627 (cross-list from math.CO) [pdf, html, other]
Title: Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, Ryan O'Donnell, Rachel Yun Zhang
Comments: 28 pages
Subjects: Combinatorics (math.CO); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[21] arXiv:2411.10949 (cross-list from cs.DS) [pdf, html, other]
Title: Maximization of Approximately Submodular Functions
Thibaut Horel, Yaron Singer
Comments: 12 pages
Journal-ref: Advances in Neural Information Processing Systems 29, NeurIPS 2016, pp. 3045-3053
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[22] arXiv:2411.10860 (cross-list from math.LO) [pdf, html, other]
Title: Hereditary First-Order Model Checking
Manuel Bodirsky, Santiago Guzmán-Pro
Subjects: Logic (math.LO); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO)
[23] arXiv:2411.10719 (cross-list from cs.GT) [pdf, html, other]
Title: Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
Sota Kawase, Shuichi Miyazaki
Comments: 23 pages, 16 figures
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[24] arXiv:2411.10653 (cross-list from cs.DS) [pdf, html, other]
Title: Hardness Results on Characteristics for Elastic-Degenerated Strings
Dominik Köppl, Jannik Olbrich
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

Mon, 18 Nov 2024 (showing 2 of 2 entries )

[25] arXiv:2411.10107 [pdf, other]
Title: Monotone Contractions
Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani
Subjects: Computational Complexity (cs.CC)
[26] arXiv:2411.10093 [pdf, html, other]
Title: Bounded degree QBF and positional games
Nacim Oijid
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
Total of 26 entries
Showing up to 50 entries per page: fewer | more | all