1
$\begingroup$

I have the following problem: I have a matrix $M$. Suppose the $n$ rows matrix consists of arbitrary binary values of a fixed length $m$. I can now store redundant information about my matrix. I give my matrix to an oracle. Then, I delete my matrix (but not my redundant information). The oracle changes one or more rows. The oracle replaces these rows with arbitrary binary values. Then the oracle sends me the adjusted matrix $M'$. How can I identify the "wrong" rows with my redundant data?

One solution is storing parity bits for each row by XORing all bits. But I want to find the "wrong" rows with 100% probability and not just 50%.

Another simple solution is storing M as my redundant information.

Is there a better solution for error detection (without correction)?

Edit: Specification of the question:

For simplicity, we assume that all bitstrings in $M$ ($n$ rows of length $m$) are sampled uniformly at random. The oracle takes $M$ as input. The oracle chooses an arbitrary number $k$ with $k\leq n$ of row indices $r_i$. For each $r_i$, the oracle samples a new uniformly random bitstring and replaces the row of $r_i$ in $M$ with the new bitstring. After the oracle changes all $k$ rows, it outputs the resulting matrix $M'$.

The goal is to detect all $k$ rows. To be more specific: The goal is minimizing the amount of redundant data while still being able to detect all $k$ row indices the oracles changed.

I am not sure, if there exist good solutions. Does this relaxation help?: We are allowed to detect false positives, but we want to minimize them. This means, if our goal is to output a set of row indices, the set should contain all rows in which $M$ and $M'$ differ, but could also contain indices in which both rows are the same. (We still need to identify all rows.)

Furthermore, I am a bit confused about the "limit of the oracle" mentioned in an answer, which leads to the question: If we fix an upper bound $k'$ for the faulty error, with faulty rows $k$ and $k \leq k' < n$, how do we solve the above problem and, more important, can we confidentially (always) detect, if $k' > k$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

There is no better solution, if there are no limits on the oracle. For instance, consider an oracle that replaces your original matrix with all-zeros; there's nothing better that can be done than to back up the original matrix in its entirety.

If there are limits on the oracle (e.g., it can only change $\le k$ entries, it can only change $\le k$ rows, etc.), then it is possible to do better, but the best method will depend on the exact limits placed on the oracle. In general this is the topic area addressed by error-correcting codes.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your reply. But most of the literature I have found deals with error correction. But I just want to identify the errors. I don't want to correct them. Does that change your answer? E.g. I could make a checksum for every row. The sum can be stored with fewer bits for a large enough row size. Then, if all entries are zero, the sum of zeroes does not match the checksum (assuming checksum > 0, otherwise there is no error). $\endgroup$ Commented Oct 24, 2024 at 7:15
  • 1
    $\begingroup$ @Titanlord, The best algorithm still depends on whether and in what way the oracle is limited. If the oracle is unlimited, it would be best to edit the question to say that. $\endgroup$ Commented Oct 24, 2024 at 8:00

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.