Skip to main content
11 votes

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
user43170's user avatar
  • 163
8 votes
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, ...
LeoW.'s user avatar
  • 118
8 votes
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$ ...
Emil Jeřábek's user avatar
7 votes

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 ...
Andrew Morgan's user avatar
5 votes
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 ...
Mahdi Cheraghchi's user avatar
4 votes

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 ...
Naysh's user avatar
  • 686
4 votes

Constructing subfields of a finite field

This problem is in BPP. All finite fields of order $p^n$ are identical, and there is a generator element $g$ whose multiplicative order is $p^n-1$, so every non-zero field element is expressible as $...
Peter Shor 's user avatar
3 votes

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

It's not NP-hard, unless P=NP. There is a polynomial-time algorithm to determine whether a single quadratic polynomial $f(x_1,\dots,x_n)$ has any zeros over $\mathbb{F}_2$, and if it does, to output ...
D.W.'s user avatar
  • 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 ...
Pavlos M.'s user avatar
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 ...
Emil Jeřábek's user avatar

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