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 >>>

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

For a size parameter s\colon\mathbb{N}\to\mathbb{N}, the Minimum Circuit Size Problem (denoted by {\rm MCSP}[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f \colon \{0,1\}^n \to \{0,1\} (represented by a string of length N := 2^n) is at most a threshold s(n). A ... more >>>

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function f can be computed by a Boolean circuit of size at most \theta, for a given parameter \theta. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

Motivated by the structural analogies between point lattices and linear error-correcting codes, and by the mature theory on locally testable codes, we initiate a systematic study of local testing for membership in lattices. Testing membership in lattices is also motivated in practice, by applications to integer programming, error detection in ... more >>>

For every fixed constant \alpha > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform of an N-dimensional vector x \in \mathbb{R}^N in time k^{1+\alpha} (\log N)^{O(1)}. Specifically, the algorithm is given query access to x and computes a k-sparse \tilde{x} \in \mathbb{R}^N satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

\mathrm{AC}^{0} \circ \mathrm{MOD}_2 circuits are \mathrm{AC}^{0} circuits augmented with a layer of parity gates just above the input layer. We study the \mathrm{AC}^{0} \circ \mathrm{MOD}_2 circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... more >>>

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>>

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages s in a manner so that tampering the codeword causes the decoder to either output s or a message that is independent of s. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>>

Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the ... more >>>

We prove that a random linear code over \mathbb{F}_q, with probability arbitrarily close to 1, is list decodable at radius 1-1/q-\epsilon with list size L=O(1/\epsilon^2) and rate R=\Omega_q(\epsilon^2/(\log^3(1/\epsilon))). Up to the polylogarithmic factor in 1/\epsilon and constant factors depending on q, this matches the lower bound L=\Omega_q(1/\epsilon^2) for the list ... more >>>

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on \{-1,1\}^n (for any constant accuracy parameter \epsilon ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... more >>>

We study constraint satisfaction problems on the domain \{-1,1\}, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form \mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n) for some positive integer weights w_1, \dots, w_n. Despite their simplicity, current techniques fall short of providing a classification ... more >>>

The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower ... more >>>