# Tag Info

### It is possible to implement a *greater than* function using only addition, substractions and multiplications?

Every function on a finite field $GF(q)$ can be represented unique as a polynomial of individual degree at most $q-1$. Indeed, as you mention, $1-x^{q-1} = [\![x=0]\!]$ is a polynomial that equals $1$...
Accepted

### Fastest way to solve a system of linear equations

A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices. Therefore, you can find a solution to a system of $n$ ...

### Inverting a band matrix

Since none of the comments gave the concrete answer, I'll write it explicitly here in case anyone needs it (like I did). Firstly, unfortunately, the inverse of a band-limited matrix is a full (non-...
Accepted

### Why is the probability of a false positive not 0 for Freivald's Algorithm?

Algorithms can't work over $\mathbb{R}^n$, as you can't represent real numbers in finite space. Also, you can't pick a number uniformly at random from $\mathbb{R}$. Instead, usually we work over a ...
Accepted

### Minimal basis for set of binary vectors using XOR

If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear ...
Accepted

### Solving systems of linear equations over semirings

I don't think there's any general algorithm that works for arbitrary semirings. The requirement to be a semiring doesn't give us a lot to work with. However, if you have a closed semiring, then there ...

### Automated optimization of 0-1 matrix vector multiplication

This is related to an open research question, which is known as the "Online Boolean Matrix-Vector Multiplication (OMv) problem". This problem reads as follows (see ): Given a binary $n \times n$ ...

### Suitable choice for moderate-size square matrix multiplication?

Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and ...
Accepted

### Unfeasible linear program becomes feasible if a variable is removed

There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l_i=u_i$ then the problem is to determine if there is a ...
Accepted

### Closed form solution for optimization problem

There is a closed-form solution to your problem, but first it helps to know two facts to derive the minimizer. The first fact is that we can re-write the Frobenius norm squared as a trace operation. ...

### Proving complexity of computing product of matrices

I'm afraid you can't. As I mentioned in my response to your previous question: The complexity of a problem is the running time of the fastest algorithm for that problem. There exist algorithms ...
Accepted

### Computing Von Neumann Entropy Efficiently

A paper Computing the Entropy of a Large Matrix by Thomas P. Wihler, Bänz Bessire, André Stefanov suggests approximating $x \lg x$ with a polynomial. Then you can use the trace of powers of the matrix ...
Accepted

### Automated optimization of 0-1 matrix vector multiplication

If it is possible try to exploit banded tridiagonal nature of matrix. Otherwise if the matrix contains only a constant number of distinct values (which surely is being binary), you should try Mailman ...
Accepted

### Positive Definiteness Constraint

A matrix $A$ is positive semidefinite if and only if there exists a matrix $V$ such that $$A = V^\top V.$$ So, you can use the entries of $V$ as your unknowns, and express each entry of $A$ as a ...

### How to find subset of vectors whose sum has certain characteristics

The question has changed. I'll answer the updated question. Here are three candidate algorithms; the first is faster than $O(m^n)$ time, and the second might be faster as well for some parameter ...

### Fastest way to solve a system of linear equations

There is what you want to achieve, and there is reality, and sometimes they are in conflict. First you check if your problem is a special case that can be solved quicker, for example a sparse matrix. ...
Accepted

Accepted

### Locality-sensitive hashing random projection

No. The statement you're reading is correct. Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens. The ...
Accepted

### Matrix chain multiplication and exponentiation

Disclaimer: The following method has not been rigorously proven to be optimal. An informal proof is provided. The problem reduces to finding the most efficient ordering when considering the square of ...
Accepted

### Time complexity of matrix multiplication in Big-Align

D.W. is absolutely right about the time complexity for $\bf X$. Meanwhile, I think the paper is vague on what they are saying and not exact on the complexity. The paper is about network alignment, ...
There are several possible techniques. Let $P^t$ denote the matrix $P$ raised to the $t$th power. Then $(P^t)_{i,j}$ (the $i,j$-th entry of that matrix) represents the probability that if you start ...