| 51 |
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
Venkatesan Guruswami, Jun-Ting Hsieh, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
6 |
2 years ago |
| 52 |
Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries
Dor Minzer, Kai Zheng
|
🔮
The Ethereal
|
cs.CC
|
5 |
2 years ago |
| 53 |
Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
Vijay Bhattiprolu, Venkatesan Guruswami, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
5 |
1 year ago |
| 54 |
The Quasi-Polynomial Low-Degree Conjecture is False
Rares-Darius Buhai, Jun-Ting Hsieh, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
5 |
10 months ago |
| 55 |
An Approximate Generalization of the Okamura-Seymour Theorem
Nikhil Kumar
|
🔮
The Ethereal
|
cs.DM
|
4 |
3 years ago |
| 56 |
An Improved Bound for the Beck-Fiala Conjecture
Nikhil Bansal, Haotian Jiang
|
🔮
The Ethereal
|
math.CO
|
4 |
7 months ago |
| 57 |
Fast Numerical Multivariate Multipoint Evaluation
Sumanta Ghosh, Prahladh Harsha, ... (+3 more)
|
🔮
The Ethereal
|
cs.DM
|
3 |
2 years ago |
| 58 |
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
Guy Blanc, Caleb Koch, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
3 |
2 years ago |
| 59 |
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
Guy Blanc, Alexandre Hayderi, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
3 |
1 year ago |
| 60 |
Cycle-factors of regular graphs via entropy
Micha Christoph, Nemanja Draganić, ... (+4 more)
|
🔮
The Ethereal
|
math.CO
|
2 |
8 months ago |
| 61 |
Obstructions to Erdős-Pósa Dualities for Minors
Christophe Paul, Evangelos Protopapas, ... (+2 more)
|
🔮
The Ethereal
|
math.CO
|
1 |
1 year ago |
| 62 |
Fast decision tree learning solves hard coding-theoretic problems
Caleb Koch, Carmen Strassle, Li-Yang Tan
|
🔮
The Ethereal
|
cs.CC
|
1 |
1 year ago |
| 63 |
Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
Jonathan Leake, Kasper Lindberg, Shayan Oveis Gharan
|
🔮
The Ethereal
|
math.CO
|
1 |
1 year ago |
| 64 |
Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
Alberto Larrauri
|
🔮
The Ethereal
|
cs.CC
|
1 |
11 months ago |
| 65 |
Deterministic factorization of constant-depth algebraic circuits in subexponential time
Somnath Bhattacharjee, Mrinal Kumar, ... (+3 more)
|
🔮
The Ethereal
|
cs.CC
|
1 |
11 months ago |
| 66 |
On optimal distinguishers for Planted Clique
Ansh Nagda, Prasad Raghavendra
|
🔮
The Ethereal
|
cs.CC
|
0 |
10 months ago |
| 67 |
Computational-Statistical Tradeoffs from NP-hardness
Guy Blanc, Caleb Koch, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
0 |
8 months ago |
| 68 |
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
|
🔮
The Ethereal
|
cs.CC
|
0 |
8 months ago |
| 69 |
Undirected Multicast Network Coding Gaps via Locally Decodable Codes
Mark Braverman, Zhongtian He
|
🔮
The Ethereal
|
cs.CC
|
0 |
5 months ago |
| 70 |
Efficiently Batching Unambiguous Interactive Proofs
Bonnie Berger, Rohan Goyal, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
0 |
5 months ago |