Zobrazeno 1 - 10
of 128
pro vyhledávání: '"Kothari, Pravesh"'
We prove that for every $D \in \N$, and large enough constant $d \in \N$, with high probability over the choice of $G \sim G(n,d/n)$, the \Erdos-\Renyi random graph distribution, the canonical degree $2D$ Sum-of-Squares relaxation fails to certify th
Externí odkaz:
http://arxiv.org/abs/2406.18429
Autor:
Bakshi, Ainesh, Kothari, Pravesh, Rajendran, Goutham, Tulsiani, Madhur, Vijayaraghavan, Aravindan
A set of high dimensional points $X=\{x_1, x_2,\ldots, x_n\} \subset R^d$ in isotropic position is said to be $\delta$-anti concentrated if for every direction $v$, the fraction of points in $X$ satisfying $|\langle x_i,v \rangle |\leq \delta$ is at
Externí odkaz:
http://arxiv.org/abs/2405.15084
We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has the second eigenvalue bounded away from 1. Consequently, we obtain a p
Externí odkaz:
http://arxiv.org/abs/2405.10238
We give a simple, greedy $O(n^{\omega+0.5})=O(n^{2.872})$-time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01]) that succeeds whenever the size of the planted clique is $k\geq O(\sqrt{n} \log^2 n
Externí odkaz:
http://arxiv.org/abs/2404.14159
Autor:
Kothari, Pravesh K., Manohar, Peter
We give improved lower bounds for binary $3$-query locally correctable codes (3-LCCs) $C \colon \{0,1\}^k \rightarrow \{0,1\}^n$. Specifically, we prove: (1) If $C$ is a linear design 3-LCC, then $n \geq 2^{(1 - o(1))\sqrt{k} }$. A design 3-LCC has t
Externí odkaz:
http://arxiv.org/abs/2404.06513
Autor:
Hsieh, Jun-Ting, Kothari, Pravesh K., Mohanty, Sidhanth, Correia, David Munhá, Sudakov, Benny
Given a $k$-uniform hypergraph $H$ on $n$ vertices, an even cover in $H$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalization of cycles in graphs and are equivalent to linearly dependent subse
Externí odkaz:
http://arxiv.org/abs/2401.11590
Autor:
Kothari, Pravesh K., Manohar, Peter
We prove that the blocklength $n$ of a linear $3$-query locally correctable code (LCC) $\mathcal{L} \colon {\mathbb F}^k \to {\mathbb F}^n$ with distance $\delta$ must be at least $n \geq 2^{\Omega\left(\left(\frac{\delta^2 k}{(|{\mathbb F}|-1)^2}\ri
Externí odkaz:
http://arxiv.org/abs/2311.00558
We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the $n$-dimensional hypercube. In both cases, the resulting algorithms yield a $O(\sqrt{n/k})$ multiplicative approximation in
Externí odkaz:
http://arxiv.org/abs/2310.00393
We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst-case and average-case input models, where the input is generated by (1) choos
Externí odkaz:
http://arxiv.org/abs/2309.16897
A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by randomly querying the encoding $x := C(b)$ on at most $q$ coordinates
Externí odkaz:
http://arxiv.org/abs/2308.15403