Tag Info

Status of Raghavendra's algorithm for solving linear systems in finite fields

This is a paper that seems to improve upon the result. https://arxiv.org/pdf/1209.3995.pdf
• 163
Accepted

Status of Raghavendra's algorithm for solving linear systems in finite fields

The paper by Raghavendra is now also published and available here under the title: Correlation Decay and Tractability of CSPs, appeared in the 43rd International Colloquium on Automata, Languages, ...
• 118
Accepted

Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?

The revised conjecture is true, even under relaxed constraints on $S$ and $t$—they may be arbitrary integer vectors (as long as the set $S$ is finite). Notice that if we arrange the vectors from $S$ ...
• 17.9k

Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

It's easy, and in fact I suspect your proof that the "degree-3 version is NP-hard" is flawed somewhere, since the degree-3 version is also easy. Here's the argument for degree-2: Suppose our ...
• 1,429
Accepted

Reference request for linear algebra over GF(2)

Strangely, linear algebra specific to finite fields is best studied in textbooks on the theory of error-correcting codes (for example, MacWilliams and Sloane). Pretty much all familiar notions in ...
• 4,031

Reference request: finite field computation over the Word-RAM model

Looks like Lemma 2.6 from https://arxiv.org/abs/2403.20326 answers my question. Constant time addition and multiplication are possible over $\mathbb{F}_q$ in the Word-RAM model, provided you first ...
• 686

• 12.2k
1 vote

Reference request for linear algebra over GF(2)

As you mention, standard Linear Algebra books demonstrate the notions using infinite fields (usually the reals and the complex numbers). Pretty much, though, all the definitions are general enough to ...
1 vote

complexity of deciding whether there's a small polynomial with a given root

Here is an algorithm that solves the problem in time $$\tilde O\Bigl(\min\Bigl\{(2r+1)^{\frac{d+1}2},p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)}\Bigr\}\sqrt r\Bigl)\subseteq\tilde O(p).$$ The tildes ...
• 17.9k

Only top scored, non community-wiki answers of a minimum length are eligible