Prasad Raghavendra

collaborators

2 papers

cs.DS2026

Improved Certificates for Independence Number in Semirandom Hypergraphs

Pravesh Kothari, Anand Louis, Rameesh Paul +1

We study the problem of efficiently certifying upper bounds on independence number of $ℓ$ -uniform hypergraphs in semirandom models. This is a notoriously hard problem, with effi…

cs.DS2024

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $n$ Dimension Threshold

Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra

We consider the task of certifying that a random $d$ -dimensional subspace $X$ in $R^{n}$ is well-spread - every vector $x \in X$ satisfies $c\sqrt{n} \|x\|_2 \leq \|x\|_1 \l…

Improved Certificates for Independence Number in Semirandom Hypergraphs

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the n​ Dimension Threshold

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $n$ Dimension Threshold