# Questions tagged [linear-equations]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
43 views

### Hard family for degree-$D$ MAX-3LIN

Max 3LIN is the problem where one is given a linear system of equations $C$ over $\mathbb{F}_2$ with $3$ variables per equation, and needs to determine the maximum number of equations that can be ...
192 views

### Cryptographic systems that don't leak linear combinations of encrypted bits

Various encryption schemes would be considered broken if an adversary could have a non-negligible edge in predicting the first (or any) bit of an encrypted message. I am looking for a slightly ...
2k views

### Complexity of solving linear equations

What is known about the complexity of solving a system of linear equations over some finite field? I know that there exists an $O(n^3)$ algorithm (Gauss) that computes a solution and that for sparse ...
1k views

### Applications of HHL's algorithm for solving linear equations

In HHL's algorithm for solving a system of linear equations (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge ...
92 views

### Known generalizations of Gauss pivot method?

The well-known Gauss pivot method can be used to solve a system of linear equations over a field. I'm aware of two extensions of this method: (i) the Büchberger algorithm for computation of Gröbner ...
172 views

### Piecewise Linear Circuit Identity Testing

A circuit is used to express a piecewise linear function of one variable $\ f:\mathbb{Q}\to\mathbb{Q}$ The component gates are: add the outputs of two other gates together scale the output of one ...
188 views

Suppose we are given a linear equation $Ax = b$, where $A \in Z_{q}^{m \times n}$ and $b \in Z_{q}^{m}$. Note that $q$ is NOT necessarily a prime here. I wonder whether the following can be done in $... 2answers 2k views ### How/Why are linear systems so crucial to computer science? I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ... 0answers 180 views ### Complexity of checking whether linear equations have a positve solution [closed] Consider a system of linear equations$Ax=0$, where$A$is a$n\times n$matrix with rational entries. Assume that the rank of$A$is$<n$. What is the complexiy to check whether it has a solution$...
Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$? Are there any families of Laplacians for which it takes ...