1 citations · 1 across the 3 of their papers we have counts for
4 papers
Lower Bounds for CSP Hierarchies Through Ideal Reduction
Jonas Conneryd, Yassine Ghannane, Shuo Pang
We present a generic way to obtain level lower bounds for (promise) CSP hierarchies from degree lower bounds for algebraic proof systems. More specifically, we show that pseudo-red…
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström +2
We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erdős-Rényi…
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett +2
We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any circuit must have depth super-linear or even s…
Sum-of-squares lower bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang +1
Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Specifically, given i.i.d.\ samples from a distrib…