All reports by Author Venkatesan Guruswami:

__
TR22-156
| 15th November 2022
__

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro#### Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms

Revisions: 1

__
TR22-102
| 15th July 2022
__

Venkatesan Guruswami, Xin Lyu, Xiuhan Wang#### Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness

__
TR22-101
| 15th July 2022
__

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar#### A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

Revisions: 1

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro

We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that ... more >>>

Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

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. Existing constructions of $2$-LDCs achieve $n = ... more >>>