Zobrazeno 1 - 10
of 632
pro vyhledávání: '"Kothari, A. K."'
We prove that for every odd $q\geq 3$, any $q$-query binary, possibly non-linear locally decodable code ($q$-LDC) $E:\{\pm1\}^k \rightarrow \{\pm1\}^n$ must satisfy $k \leq \tilde{O}(n^{1-2/q})$. For even $q$, this bound was established in a sequence
Externí odkaz:
http://arxiv.org/abs/2411.14361
Motivated by connections between algebraic complexity lower bounds and tensor decompositions, we investigate Koszul-Young flattenings, which are the main ingredient in recent lower bounds for matrix multiplication. Based on this tool we give a new al
Externí odkaz:
http://arxiv.org/abs/2411.14344
Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine, based on the sum-of-squares method, that finds a low-dimensional separation-preserving projection of the input da
Externí odkaz:
http://arxiv.org/abs/2411.12438
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 its 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