Questions tagged [finite-fields]
The finite-fields tag has no usage guidance.
13
questions with no upvoted or accepted answers
7
votes
0
answers
241
views
How is a "low-degree polynomial" precisely defined in Algebrization?
I'm going through papers which present algebrization as a barrier and I'm trying to understand how "low-degree" polynomials are precisely defined, i.e. are they low with respect to the ...
- 285
5
votes
0
answers
238
views
$\#$P hardness of computing weighted sum of degree $2$ polynomials
Consider polynomials $f: \{0, 1\}^{n} \rightarrow \{0, 1\}$ over $\mathbb{F}_2$ (addition and multiplication are taken modulo $2$.) Consider integers $x \in \{0,1\}^{n}$, written in binary. Let $\...
- 173
5
votes
0
answers
111
views
Algebraic dependence of roots of irreducibles over a finite field
I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math....
- 383
5
votes
0
answers
151
views
Applications of small Kakeya sets over finite fields
It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$.
For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...
- 190
2
votes
0
answers
68
views
Which invertible linear transformations can be computed reversibly without ancilla/garbage bits just as easily as they can be computed irreversibly?
Suppose that $L:F_{2}^{n}\rightarrow F_{2}^{n}$ is an invertible linear transformation. Then define $w(L)$ to be the gate count of the smallest reversible circuit on $n$ bits without ancilla/garbage ...
- 596
2
votes
0
answers
66
views
A random ensemble of sparse boundary operators
The following question arises from the study of quantum error correction, and high-dimensional expanders:
Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear ...
- 1,224
2
votes
0
answers
91
views
Is berklemap-massey works on extention field
According to the articles that i read (also wikipedia [1]), they refer that the above algorithm works on finite field $GF(q)$. But I cannot find an evidence that it still works on extension field, i.e:...
- 271
2
votes
0
answers
85
views
Module Independence Graphs
Given $n, k \in \mathbb{N}$, we create a set $S \subseteq \mathbb{Z}_m^k$ by treating it as an $n\times k$ grid and choosing each $S_{ij}$ by sampling from $\mathbb{Z}_m$, such that $P(S_{ij} = z) = ...
- 1,562
1
vote
0
answers
77
views
BCH codes and polynomials with many values in a subfield
For points $P=\{x_1, \ldots, x_n\} \subset {\mathbb F}_{2^m}$ define $$\mathcal{C}(P, t) =\{(f(x_1), \ldots, f(x_n)) \mid \mbox{$f\in {\mathbb F}_{2^m}[X]$ has degree $t$}\}$$ and $\mathcal{C}'(P, t) =...
- 1,242
1
vote
0
answers
67
views
The curve used in Parvaresh-Vardy decoding
Consider the Parvaresh-Vardy list decoder.
As I understand it, the idea is to decide on a curve over an extension field of the form $(f,f^h mod E, f^{h^2} mod E,\dots)$ and then evaluate each of ...
- 383
0
votes
0
answers
119
views
Solving Linear Equations over finite field $ Z_q $
Suppose we are given a linear equation $ Ax=b $, where $ A \in Z_q^{n \times m} $ and $ b \in Z_q^n $.
Note that $ q $ is a prime here, and $ Rank(A)= Rank(A;b)=n<m $.
I wonder whether the ...
- 1
0
votes
0
answers
34
views
Searchable finite field
Let $F$ be a large finite field, where the elements are strings of length $n$. We require, addition, multiplication, and division to be efficient (polynomial in $n$).
We say that $F$ is searchable if ...
- 471
0
votes
0
answers
124
views
On permanent mod $3^t$ computation
By $'$ I mean transpose. I gather the info here from rjlipton.wordpress.com/2014/12/21/modulating-the-permanent.
We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ ...
- 12.6k