Questions tagged [linear-equations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5
votes
0answers
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 ...
4
votes
1answer
188 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 ...
9
votes
2answers
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 ...
6
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
169 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 ...
6
votes
1answer
187 views

Solving Linear Equations over $Z_q$

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 $...
9
votes
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 ...
1
vote
0answers
179 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 $...
11
votes
0answers
1k views

Complexity of finding the leading eigenvector of a graph Laplacian

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 ...
22
votes
1answer
317 views

Belief propagation for approximate real 3LIN?

In a Science paper from 2002, Mezard, Parisi and Zecchina put forward the belief propagation heuristic for random 3SAT. Experiments indicate that the heuristic works well for ratios of constraints-per-...