Zobrazeno 1 - 10
of 92
pro vyhledávání: '"Golovnev, Alexander"'
In this note, we present examples showing that several natural ways of constructing lattices from error-correcting codes do not in general yield a correspondence between minimum-weight non-zero codewords and shortest non-zero lattice vectors. From th
Externí odkaz:
http://arxiv.org/abs/2410.16660
For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smalles
Externí odkaz:
http://arxiv.org/abs/2405.10277
We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three $n \times n$ matrices $A$, $B$, and $C$ as input, to decide whether $AB = C$. A classic randomized algorithm by Freivalds (MFCS, 1979) solves MMV in $\wideti
Externí odkaz:
http://arxiv.org/abs/2309.16176
Autor:
Chou, Chi-Ning1 chiningchou@g.harvard.edu, Golovnev, Alexander2 alexgolovnev@gmail.com, Sudan, Madhu1 madhu@cs.harvard.edu, Velusamy, Santhoshini3 santhoshini@ttic.edu
Publikováno v:
Journal of the ACM. Apr2024, Vol. 71 Issue 2, p1-74. 74p.
Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C\colon\{0,1\}^n\to\{0,1\}^m$, $m>n$, the task is to find a $y\in\{0,1\}^m$ outside the range of $C$. For an integer $k\geq 2$, $\mathrm{NC}^0_k$-AVOID is a special cas
Externí odkaz:
http://arxiv.org/abs/2303.05044
We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fr
Externí odkaz:
http://arxiv.org/abs/2212.03348
Autor:
Aggarwal, Divesh, Bennett, Huck, Brakerski, Zvika, Golovnev, Alexander, Kumar, Rajendra, Li, Zeyong, Peters, Spencer, Stephens-Davidowitz, Noah, Vaikuntanathan, Vinod
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-case to average-case reductions and two protocols. We also show a nove
Externí odkaz:
http://arxiv.org/abs/2211.11693
The Strong Exponential Time Hypothesis (SETH) asserts that for every $\varepsilon>0$ there exists $k$ such that $k$-SAT requires time $(2-\varepsilon)^n$. The field of fine-grained complexity has leveraged SETH to prove quite tight conditional lower
Externí odkaz:
http://arxiv.org/abs/2205.07709
Autor:
Chou, Chi-Ning, Golovnev, Alexander, Shahrasbi, Amirbehshad, Sudan, Madhu, Velusamy, Santhoshini
We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In~particular, we explore the approximability of monarchy-like functio
Externí odkaz:
http://arxiv.org/abs/2205.02345
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their i
Externí odkaz:
http://arxiv.org/abs/2202.08996