Here’s an old trick that we found useful for proving some tight complexity lower bounds. You are given m coins, each of weight either a or b, and a modern scale that can tell you the total weight of any chosen subset of coins. How many weighings do you need to identify which coin is which? Checking each coin individually uses m weighings, but can you do less?
It turns out that this many is in fact enough, and this generalizes to various other settings with less restricted weights. This is the basis for two of our recent results: a tight complexity lower bound for Integer Linear Programming with few constraints and for multicoloring (a.k.a. b-fold coloring), assuming the Exponential Time Hypothesis. The trick allows us to use constraints that check the value of some number between 0 and m to indeed extract about log(m) bits of new information from each, in a way that is general enough to check m clauses of a 3-CNF-SAT instance using only O(m / log m) constraints.
In any weighing, we try some unknown number of weight-a coins between 0 and m, so this results in one of m + 1 possible values, giving us at most log(m + 1) bits of information. In total we need m bits of information to identify each coin, so clearly we will need at least Ω(m / log m) weighings.
Detecting matrices
One way to rephrase this coin-weighing problem is as follows: the unknown coin weights are described by a (column) vector x in {a,b}m. A subset of coins is described by a characteristic (row) vector v in {0,1}m and the resulting value of the weighing is the dot product v · x.
For a number of weighings k, the row vectors form a 0-1 matrix M with k rows and m columns, while the obtained values are simply the k-element vector M x. The condition that these values are enough to identify each entry of x is formalized as follows:
For all m, there is a 0-1 matrix M with k=O(m / log m) rows and
m columns such that for any x, y in {a,b}m, x ≠ y implies M x ≠ M y.
This is called a detecting matrix. In other words, instead of checking x = y entry by entry, it suffices to compare the k entries of M x and M y. (An equivalent definition is to require that the kernel of M is trivial on {-1,0,1}m, since we could instead compare (x - y)/(a - b) with zero). A generalization for x, y in {0, 1, …, d - 1}m was first proved by (Lindström 1965) (in fact he proves the constant hidden behind O is 2 log2(d) and cannot be improved, for any d), giving a deterministic, poly-time construction. (Bshouty 2009) gives a more direct and general construction using Fourier analysis. However, a random matrix can be shown to be detecting with fairly elementary methods.
Integer Linear Programming
In ILP we are given a matrix A with n columns and m rows, a vector b with m entries, and we ask for a vector x with n non-negative integer entries such that A x = b. So each of the m rows is a linear equality to be satisfied. What is the complexity for small m?
We start with an instance A x = b encoding a suitable 3-CNF-SAT instance of size O(m) in a straightforward way, using only {0,1,2,3} entries in A and b. Instead of checking each row individually, we use detecting matrices to check them in bunches, reducing our problem to an equivalent instance M A x = M b. The matrix M A of the new instance has only O(m / log m) rows (at the cost of having larger entries in M b). With some tinkering, this simple reduction shows that, assuming ETH, ILP with m constraints cannot be solved in time 2o(m log m), even when the matrix has only 0-1 entries and b has poly(m) entries. This matches a recent (surprisingly simple and clever!) 2O(m log m) algorithm by Eisenbrand and Weismantel (SODA 2018).
One caveat when applying detecting matrices is that we do not know any bound on one side, A x, except that it is a non-negative integer vector. Fortunately, (Grebinsky & Kucherov 2000) showed that a random 0-1 matrix satisfies the following:
For all d,m, there is a 0-1 matrix M with k=O(m log d / log m) rows and m columns
such that for any x, y in ℕm with ‖y‖1 ≤ d m, x ≠ y implies M x ≠ M y.
Here no upper bound on x is needed, because a single row in M full of ones is enough to guarantee that the sum of entries is the same: ‖x‖1 = ‖y‖1. However, it remains an open problem to find a deterministic construction (we work around this by giving a somewhat weaker construction). See the full paper (STACS 2019) for details (with Dušan Knop and Michał Pilipczuk). The reduction for multicoloring is quite different and more problem-specific, see the full paper (ESA 2017) for definitions (with Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk and Arkadiusz Socała).
Marcin Wrochna