# Questions tagged [finite-fields]

The tag has no usage guidance.

24 questions
Filter by
Sorted by
Tagged with
4 votes
0 answers
39 views

2 votes
0 answers
69 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 ...
0 votes
0 answers
35 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 ...
11 votes
1 answer
261 views

### 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}$?

I have a set of $n$ binary vectors $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ and a target vector $t = 1^k$ which is the all-ones vector. Conjecture: If $t$ can be written as ...
15 votes
2 answers
543 views

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

In 2012, Lipton wrote a blog entry about a new algorithm for solving linear systems over finite fields by Prasad Raghavendra. The link to Raghavendra's draft paper on the topic is now dead, and I can'...
2 votes
0 answers
67 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 ...
0 votes
0 answers
129 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}$ ...
2 votes
0 answers
93 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:...
2 votes
0 answers
86 views