All Questions
10
questions
1
vote
0
answers
68
views
Polynomial time algorithm to compute minimum distance of a linear code
For general (even binary I believe) linear codes, computing the minimum distance $\min_{d \in C} \Delta(d, 0)$ is NP-complete. However, there is a special case where a polytime algorithm is possible:
...
- 91
2
votes
0
answers
227
views
Counting permutation matrices
$J \in \{0,1\}^{n \times n}$ is a matrix with all elements being $1$. $S := \{P_1, P_2, ..., P_n\}$ is a set with $n$ permutation matrices $P_i \in \{0,1\}^{n \times n}$ such that $\sum\limits_{i=1}^n ...
- 1,008
1
vote
1
answer
247
views
parenthesis of expression in such a way value not changed
one example:
How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among ...
- 119
4
votes
0
answers
159
views
Minimizing floor space needed to store $N$ unit cubes, subject to two placement rules
There is a store room which has only three sides all touching each other perpendicularly, the sides can be defined as: two infinitely large walls and one infinitely large floor.
There are $N$ cubes ...
- 61
0
votes
1
answer
57
views
Find exactly k columns in binary matrix such that the sum of those columns is the 1-vector
Suppose I have an $M\times N$ binary matrix where $N$ can be large (say $N\approx10^6$). I want to find exactly $k$ columns ($k$ is relatively small, say $k<10$) such that the sum of those $k$ ...
- 312
1
vote
1
answer
102
views
How to maximize the total auction price for a set of bids subject to bidder constraints
I want to auction a set of ASSETS (A) and fetch the maximum total price. The bidding is simultaneous and works as follows.
Say I have a collection of BIDDERS (B) who, individually, bid to purchase a ...
- 141
9
votes
3
answers
535
views
What is the largest possible number of moves that can be taken to color the whole grid?
Consider a $10\times 10$ grid. On every move, we color $4$ unit squares that lie in the intersection of some two rows and two columns. A move is allowed if at least one of the $4$ squares is ...
- 90.7k
1
vote
1
answer
88
views
Proof for existence of exactly one solution for the number of marbles in each box
There are four boxes A, B, C and D containing marbles. Two boxes are randomly
selected and the number of marbles in each box is summarized. This procedure
is repeated five times with the following ...
- 13
2
votes
0
answers
651
views
Does a matrix represent a bijection
We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
- 404
12
votes
2
answers
13k
views
Efficient computation of the minimum distance of a binary linear code
I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix.
How can I find parameter $d$ efficiently?
I know the method that compute all the codewords and take ...
- 303