Cover Image

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kunisky, Dmitriy, Yu, Xifan
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms Computational Complexity Number Theory Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Statistical inference of a ranked community in a directed graph
by: Kunisky, Dmitriy, et al.
Published: (2024)

Inference of rankings planted in random tournaments
by: Kunisky, Dmitriy, et al.
Published: (2024)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
by: Umans, Chris, et al.
Published: (2025)

A Control-Theoretic Perspective on Optimal High-Order Optimization
by: Lin, Tianyi, et al.
Published: (2019)

A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
by: Lin, Tianyi, et al.
Published: (2022)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
by: Prunet, Thibault, et al.
Published: (2023)

Stable Algorithms Lower Bounds for Estimation
by: Yu, Xifan, et al.
Published: (2026)

Solving convex QPs with structured sparsity under indicator conditions
by: Bienstock, Daniel, et al.
Published: (2024)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
by: Kurpisz, Adam, et al.
Published: (2026)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
by: Chen, Shengminjie, et al.
Published: (2026)

Tensor cumulants for statistical inference on invariant distributions
by: Kunisky, Dmitriy, et al.
Published: (2024)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
by: Yu, Xifan, et al.
Published: (2024)

Efficient approximation schemes for scheduling on a stochastic number of machines
by: Epstein, Leah, et al.
Published: (2024)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
by: Rai, Shanthanu S
Published: (2024)

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
by: Gribanov, Dmitry, et al.
Published: (2026)

Unifying Formal Explanations: A Complexity-Theoretic Perspective
by: Bassan, Shahaf, et al.
Published: (2026)

Efficient Convex Optimization Requires Superlinear Memory
by: Marsden, Annie, et al.
Published: (2022)

Simultaneous Network Design with Restricted Link Usage
by: Kakimura, Naonori, et al.
Published: (2025)

Semidefinite programming and linear equations vs. homomorphism problems
by: Ciardo, Lorenzo, et al.
Published: (2023)

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
by: Cherniavskii, M., et al.
Published: (2024)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
by: Blanchard, Moise
Published: (2024)

Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise
by: De, Debsurya, et al.
Published: (2025)

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
by: Kunisky, Dmitriy
Published: (2024)

Min-Max Optimization Requires Exponentially Many Queries
by: Bernasconi, Martino, et al.
Published: (2026)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
by: Diaby, Moustapha
Published: (2016)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

Constructing self-referential instances for the clique problem
by: Li, Jiaqi, et al.
Published: (2026)

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
by: Kunisky, Dmitriy
Published: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Low-degree phase transitions for detecting a planted clique in sublinear time
by: Mardia, Jay, et al.
Published: (2024)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

Optimal lower bounds for quantum state tomography
by: Scharnhorst, Thilo, et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)