Cover Image

On optimal distinguishers for Planted Clique

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nagda, Ansh, Raghavendra, Prasad
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On approximability of the Permanent of PSD matrices
by: Ebrahimnejad, Farzam, et al.
Published: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
by: Guruswami, Venkatesan, et al.
Published: (2024)

The communication complexity of distributed estimation
by: Gopalan, Parikshit, et al.
Published: (2025)

Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
by: Chen, Yu-Zhen Janice, et al.
Published: (2025)

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

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
by: Enright, Jessica, et al.
Published: (2020)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
by: Dell, Holger, et al.
Published: (2022)

Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
by: Dolev, Shlomi
Published: (2025)

Improved approximation algorithms for the EPR Hamiltonian
by: Ju, Nathan, et al.
Published: (2025)

The Planted Orthogonal Vectors Problem
by: Kühnemann, David, et al.
Published: (2025)

Universal Solvability for Robot Motion Planning on Graphs
by: Dhar, Anubhav, et al.
Published: (2025)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

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

On the instance optimality of detecting collisions and subgraphs
by: Ben-Eliezer, Omri, et al.
Published: (2023)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
by: Maalouly, Nicolas El, et al.
Published: (2025)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
by: Dhar, Anubhav, et al.
Published: (2025)

Scheduling Problems with Constrained Rejections
by: Davies, Sami, et al.
Published: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
by: Uhlmann, Jeffrey
Published: (2025)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

Geometric Interpretation of 3-SAT and Phase Transition
by: Gillet, Frederic
Published: (2025)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
by: Scheder, Dominik, et al.
Published: (2025)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
by: Curticapean, Radu, et al.
Published: (2025)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
by: Gaikwad, Ajinkya, et al.
Published: (2025)

Most Juntas Saturate the Hardcore Lemma
by: Kumar, Vinayak M.
Published: (2025)

FPT Parameterisations of Fractional and Generalised Hypertree Width
by: Lanzinger, Matthias, et al.
Published: (2025)

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

Novel Complexity Results for Temporal Separators with Deadlines
by: Dondi, Riccardo, et al.
Published: (2025)