arxiv cs.CC
@arxiv-cs-cc.bsky.social
Computer Science -- Computational Complexity (cs.CC)
source: https://export.arxiv.org/rss/cs.CC
maintainer: @tmaehara.bsky.social
source: https://export.arxiv.org/rss/cs.CC
maintainer: @tmaehara.bsky.social
Julio Aracena (UdeC), Florian Bridoux (AMU, CANA), Maximilien Gadouleau (I2M), Pierre Guillon (I2M), K\'evin Perrot (LIS), Adrien Richard (Laboratoire I3S - MDSC), Guillaume Theyssier (I2M)
On the Dynamics of Bounded-Degree Automata Networks
https://arxiv.org/abs/2511.11174
On the Dynamics of Bounded-Degree Automata Networks
https://arxiv.org/abs/2511.11174
November 17, 2025 at 5:25 AM
Julio Aracena (UdeC), Florian Bridoux (AMU, CANA), Maximilien Gadouleau (I2M), Pierre Guillon (I2M), K\'evin Perrot (LIS), Adrien Richard (Laboratoire I3S - MDSC), Guillaume Theyssier (I2M)
On the Dynamics of Bounded-Degree Automata Networks
https://arxiv.org/abs/2511.11174
On the Dynamics of Bounded-Degree Automata Networks
https://arxiv.org/abs/2511.11174
Thiago Marcilon, Murillo In\'acio da Costa Silva
Parameterized complexity of the f-Critical Set problem
https://arxiv.org/abs/2511.11546
Parameterized complexity of the f-Critical Set problem
https://arxiv.org/abs/2511.11546
November 17, 2025 at 5:24 AM
Thiago Marcilon, Murillo In\'acio da Costa Silva
Parameterized complexity of the f-Critical Set problem
https://arxiv.org/abs/2511.11546
Parameterized complexity of the f-Critical Set problem
https://arxiv.org/abs/2511.11546
Ryan O'Donnell, Noah G. Singer
Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
https://arxiv.org/abs/2511.10514
Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
https://arxiv.org/abs/2511.10514
November 14, 2025 at 5:43 AM
Ryan O'Donnell, Noah G. Singer
Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
https://arxiv.org/abs/2511.10514
Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
https://arxiv.org/abs/2511.10514
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
Random Permutations in Computational Complexity
https://arxiv.org/abs/2511.08786
Random Permutations in Computational Complexity
https://arxiv.org/abs/2511.08786
November 13, 2025 at 5:15 AM
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
Random Permutations in Computational Complexity
https://arxiv.org/abs/2511.08786
Random Permutations in Computational Complexity
https://arxiv.org/abs/2511.08786
Eric Goles (I2M), Pedro Montealegre (I2M), Mart\'in R\'ios-Wilson (I2M), Guillaume Theyssier (I2M)
On the complexity of freezing automata networks of bounded pathwidth
https://arxiv.org/abs/2511.09297
On the complexity of freezing automata networks of bounded pathwidth
https://arxiv.org/abs/2511.09297
November 13, 2025 at 5:14 AM
Eric Goles (I2M), Pedro Montealegre (I2M), Mart\'in R\'ios-Wilson (I2M), Guillaume Theyssier (I2M)
On the complexity of freezing automata networks of bounded pathwidth
https://arxiv.org/abs/2511.09297
On the complexity of freezing automata networks of bounded pathwidth
https://arxiv.org/abs/2511.09297
Benjamin Bordais, Daniel Neider
Learning DFAs from Positive Examples Only via Word Counting
https://arxiv.org/abs/2511.08431
Learning DFAs from Positive Examples Only via Word Counting
https://arxiv.org/abs/2511.08431
November 12, 2025 at 5:21 AM
Benjamin Bordais, Daniel Neider
Learning DFAs from Positive Examples Only via Word Counting
https://arxiv.org/abs/2511.08431
Learning DFAs from Positive Examples Only via Word Counting
https://arxiv.org/abs/2511.08431
Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
Halfspaces are hard to test with relative error
https://arxiv.org/abs/2511.06171
Halfspaces are hard to test with relative error
https://arxiv.org/abs/2511.06171
November 11, 2025 at 5:19 AM
Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
Halfspaces are hard to test with relative error
https://arxiv.org/abs/2511.06171
Halfspaces are hard to test with relative error
https://arxiv.org/abs/2511.06171
Mika G\"o\"os, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
Pseudodeterministic Communication Complexity
https://arxiv.org/abs/2511.04794
Pseudodeterministic Communication Complexity
https://arxiv.org/abs/2511.04794
November 10, 2025 at 5:28 AM
Mika G\"o\"os, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
Pseudodeterministic Communication Complexity
https://arxiv.org/abs/2511.04794
Pseudodeterministic Communication Complexity
https://arxiv.org/abs/2511.04794
Christian Ikenmeyer
On the gradient of the coefficient of the characteristic polynomial
https://arxiv.org/abs/2511.04954
On the gradient of the coefficient of the characteristic polynomial
https://arxiv.org/abs/2511.04954
November 10, 2025 at 5:27 AM
Christian Ikenmeyer
On the gradient of the coefficient of the characteristic polynomial
https://arxiv.org/abs/2511.04954
On the gradient of the coefficient of the characteristic polynomial
https://arxiv.org/abs/2511.04954
Robert Andrews, Mrinal Kumar, Shanthanu S. Rai
Modular composition & polynomial GCD in the border of small, shallow circuits
https://arxiv.org/abs/2511.05035
Modular composition & polynomial GCD in the border of small, shallow circuits
https://arxiv.org/abs/2511.05035
November 10, 2025 at 5:27 AM
Robert Andrews, Mrinal Kumar, Shanthanu S. Rai
Modular composition & polynomial GCD in the border of small, shallow circuits
https://arxiv.org/abs/2511.05035
Modular composition & polynomial GCD in the border of small, shallow circuits
https://arxiv.org/abs/2511.05035
Soham Chatterjee, Prahladh Harsha, Mrinal Kumar
Deterministic list decoding of Reed-Solomon codes
https://arxiv.org/abs/2511.05176
Deterministic list decoding of Reed-Solomon codes
https://arxiv.org/abs/2511.05176
November 10, 2025 at 5:26 AM
Soham Chatterjee, Prahladh Harsha, Mrinal Kumar
Deterministic list decoding of Reed-Solomon codes
https://arxiv.org/abs/2511.05176
Deterministic list decoding of Reed-Solomon codes
https://arxiv.org/abs/2511.05176
Isaac M. Hair, Amit Sahai
SVP$_p$ is NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
https://arxiv.org/abs/2511.04125
SVP$_p$ is NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
https://arxiv.org/abs/2511.04125
November 7, 2025 at 6:06 AM
Isaac M. Hair, Amit Sahai
SVP$_p$ is NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
https://arxiv.org/abs/2511.04125
SVP$_p$ is NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
https://arxiv.org/abs/2511.04125
Christoph Gr\"une, Femke Pfaue
A Compendium of Reductions: reductions.network
https://arxiv.org/abs/2511.04308
A Compendium of Reductions: reductions.network
https://arxiv.org/abs/2511.04308
November 7, 2025 at 6:06 AM
Christoph Gr\"une, Femke Pfaue
A Compendium of Reductions: reductions.network
https://arxiv.org/abs/2511.04308
A Compendium of Reductions: reductions.network
https://arxiv.org/abs/2511.04308
Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell
Boolean function monotonicity testing requires (almost) $n^(1/2)$ queries
https://arxiv.org/abs/2511.04558
Boolean function monotonicity testing requires (almost) $n^(1/2)$ queries
https://arxiv.org/abs/2511.04558
November 7, 2025 at 6:05 AM
Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell
Boolean function monotonicity testing requires (almost) $n^(1/2)$ queries
https://arxiv.org/abs/2511.04558
Boolean function monotonicity testing requires (almost) $n^(1/2)$ queries
https://arxiv.org/abs/2511.04558
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
https://arxiv.org/abs/2511.03083
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
https://arxiv.org/abs/2511.03083
November 6, 2025 at 5:22 AM
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
https://arxiv.org/abs/2511.03083
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
https://arxiv.org/abs/2511.03083
Balagopal Komarath (Indian Institute of Technology Gandhinagar), Rohit Narayanan (Indian Institute of Technology Gandhinagar)
Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
https://arxiv.org/abs/2511.03388
Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
https://arxiv.org/abs/2511.03388
November 6, 2025 at 5:21 AM
Balagopal Komarath (Indian Institute of Technology Gandhinagar), Rohit Narayanan (Indian Institute of Technology Gandhinagar)
Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
https://arxiv.org/abs/2511.03388
Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
https://arxiv.org/abs/2511.03388
Cynthia Dwork, Pranay Tankala
Efficient Testing Implies Structured Symmetry
https://arxiv.org/abs/2511.03653
Efficient Testing Implies Structured Symmetry
https://arxiv.org/abs/2511.03653
November 6, 2025 at 5:21 AM
Cynthia Dwork, Pranay Tankala
Efficient Testing Implies Structured Symmetry
https://arxiv.org/abs/2511.03653
Efficient Testing Implies Structured Symmetry
https://arxiv.org/abs/2511.03653
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
Ideals, Gr\"obner Bases, and PCPs
https://arxiv.org/abs/2511.03703
Ideals, Gr\"obner Bases, and PCPs
https://arxiv.org/abs/2511.03703
November 6, 2025 at 5:20 AM
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
Ideals, Gr\"obner Bases, and PCPs
https://arxiv.org/abs/2511.03703
Ideals, Gr\"obner Bases, and PCPs
https://arxiv.org/abs/2511.03703
Diptajit Roy, Nitin Saxena, Madhavan Venkatesh
Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces
https://arxiv.org/abs/2511.02262
Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces
https://arxiv.org/abs/2511.02262
November 5, 2025 at 6:33 AM
Diptajit Roy, Nitin Saxena, Madhavan Venkatesh
Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces
https://arxiv.org/abs/2511.02262
Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces
https://arxiv.org/abs/2511.02262
Nicholas Kocurek
Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
https://arxiv.org/abs/2511.02264
Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
https://arxiv.org/abs/2511.02264
November 5, 2025 at 6:32 AM
Nicholas Kocurek
Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
https://arxiv.org/abs/2511.02264
Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
https://arxiv.org/abs/2511.02264
Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, Geoffrey Mon
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
https://arxiv.org/abs/2511.02633
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
https://arxiv.org/abs/2511.02633
November 5, 2025 at 6:32 AM
Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, Geoffrey Mon
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
https://arxiv.org/abs/2511.02633
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
https://arxiv.org/abs/2511.02633
November 4, 2025 at 5:21 AM
Rares Folea, Emil-Ioan Slusanschi
A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
https://arxiv.org/abs/2511.00589
A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
https://arxiv.org/abs/2511.00589
November 4, 2025 at 5:20 AM
Rares Folea, Emil-Ioan Slusanschi
A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
https://arxiv.org/abs/2511.00589
A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
https://arxiv.org/abs/2511.00589
Yumou Fei
Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
https://arxiv.org/abs/2510.27012
Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
https://arxiv.org/abs/2510.27012
November 3, 2025 at 5:20 AM
Yumou Fei
Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
https://arxiv.org/abs/2510.27012
Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
https://arxiv.org/abs/2510.27012
Pascal Koiran, Rafael Oliveira
Tensor decomposition beyond uniqueness, with an application to the minrank problem
https://arxiv.org/abs/2510.26587
Tensor decomposition beyond uniqueness, with an application to the minrank problem
https://arxiv.org/abs/2510.26587
October 31, 2025 at 4:40 AM
Pascal Koiran, Rafael Oliveira
Tensor decomposition beyond uniqueness, with an application to the minrank problem
https://arxiv.org/abs/2510.26587
Tensor decomposition beyond uniqueness, with an application to the minrank problem
https://arxiv.org/abs/2510.26587