Zobrazeno 1 - 10
of 588
pro vyhledávání: '"Guruswami, Venkatesan"'
In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message $x$ into a codeword. The receiver (Bob) decodes it correctly whenever there is at most a small constant fraction of adversari
Externí odkaz:
http://arxiv.org/abs/2407.06446
Autor:
Guruswami, Venkatesan, Wang, Hsin-Po
To ensure differential privacy, one can reveal an integer fuzzily in two ways: (a) add some Laplace noise to the integer, or (b) encode the integer as a binary string and add iid BSC noise. The former is simple and natural while the latter is flexibl
Externí odkaz:
http://arxiv.org/abs/2406.17669
Autor:
Guruswami, Venkatesan, Jain, Rhea
The problem of efficiently coloring $3$-colorable graphs with few colors has received much attention on both the algorithmic and inapproximability fronts. We consider exponential time approximations, in which given a parameter $r$, we aim to develop
Externí odkaz:
http://arxiv.org/abs/2406.15563
Autor:
Wang, Hsin-Po, Guruswami, Venkatesan
Successive cancellation list (SCL) decoders of polar codes excel in practical performance but pose challenges for theoretical analysis. Existing works either limit their scope to erasure channels or address general channels without taking advantage o
Externí odkaz:
http://arxiv.org/abs/2405.16373
Autor:
Wang, Hsin-Po, Guruswami, Venkatesan
Group testing (GT) is the art of identifying binary signals and the marketplace for exchanging new ideas for related fields such as unique-element counting, compressed sensing, traitor tracing, and geno-typing. A GT scheme can be nonadaptive or adapt
Externí odkaz:
http://arxiv.org/abs/2405.16374
We modify Cheraghchi-Nakos [CN20] and Price-Scarlett's [PS20] fast binary splitting approach to nonadaptive group testing. We show that, to identify a uniformly random subset of $k$ infected persons among a population of $n$, it takes only $\ln(2 - 4
Externí odkaz:
http://arxiv.org/abs/2405.16370
Autor:
Wang, Hsin-Po, Guruswami, Venkatesan
Polar codes that approach capacity at a near-optimal speed, namely with scaling exponents close to $2$, have been shown possible for $q$-ary erasure channels (Pfister and Urbanke), the BEC (Fazeli, Hassani, Mondelli, and Vardy), all BMS channels (Gur
Externí odkaz:
http://arxiv.org/abs/2405.16360
We consider the task of certifying that a random $d$-dimensional subspace $X$ in $\mathbb{R}^n$ is well-spread - every vector $x \in X$ satisfies $c\sqrt{n} \|x\|_2 \leq \|x\|_1 \leq \sqrt{n}\|x\|_2$. In a seminal work, Barak et. al. showed a polynom
Externí odkaz:
http://arxiv.org/abs/2405.05373
The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant $\varepsilon> 0$ such that for any computable function $f:\mathbb{N}\to\mathbb{N}$, no $f(k)\cd
Externí odkaz:
http://arxiv.org/abs/2404.08870
Autor:
Alrabiah, Omar, Guruswami, Venkatesan
We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in vi
Externí odkaz:
http://arxiv.org/abs/2404.05864