# Tag Info

Accepted

### Name for words without squared symbols

I would call them stutter-free words, since there is the notion of stutter-invariant language, which is already well-known.
• 4,841

### Binary rank of binary matrix

This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M_{i,j}$ is 1 if and only if ...
• 18.2k
Accepted

### Enumerating all simply typed lambda terms of a given type

This question has been considered several times in the academic community, from the practical: Yakushev & Jeuring, Enumerating Well-Typed Terms Generically Fetsher & al, Making Random ...
• 13.9k

### conversion to DAG

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
• 1,786

### Concrete version of KKL Theorem

See Exercise 9.30 of Ryan O'Donnell's Analysis of Boolean Functions book [1]: for any $f\colon\{-1,1\}^n\to \{-1,1\}$,  \mathbf{MaxInf}[f]\geq \frac{1}{2}\mathbf{Var}[f]\cdot \frac{\ln n}{n} (1-o(1))...
• 4,471

### Interesting real life problem similar to subsetsum /bin packing problem

Your problem is at least as hard as bin-packing. In particular, optimizing objective (a) basically is the bin-packing problem (in particular, bin packing is the special case where all drums have ...
• 12.2k

### Minimum amount of colors preventing an equilateral uniformly colored subtriangle

Using a SAT-based approach, I can confirm every instance is 3-colorable up to $n \leq 22$. A local search solver finds a solution for $n=22$ still rather quickly on a modern desktop. I tried the same ...
• 3,170
Accepted

### Binary rank of binary matrix

I had the following recent paper giving an fpt algorithm for binary rank. Our algorithm checks whether the given matrix has binary rank $k$ in $\mathcal{O}(2^{3k^2})poly(n+m)$ time, and if yes it also ...
• 368

### Results/concepts that also proved useful outside of their "home areas"

One thing that immediately comes to mind is that graph k-coloring is used in compilers for register allocation. An instance of register allocation for k registers is solved by reducing into an ...
• 1,185
Accepted

• 1,429
Accepted

### Intuition behind the Charikar's LP formulation for densest subgraph problem

Depending on how people interpret "research-level", this might need to be moved to cs.stackexchange.com. The intuition becomes more apparent if you first write down an alternate similar looking but ...
• 1,642
1 vote
Accepted

### weights in low density codes

Your question is somewhat ill-posed: given $n$ and $k$, it is easy to construct a Tanner graph with a 4-cycle and column weight at most 2. Instead, you can ask the question of what is the maximum ...
• 849
1 vote

### Reducing resource allocation problem to bipartite matching

Yes, there certainly is. There is a trivial solution. First, solve the resource allocation problem (which can be done in exponential time by enumerating all candidate solutions). Then, use the ...
• 12.2k
1 vote

### Difference Sets

"Beltway Reconstruction Problem” - arxiv.org/pdf/1212.2386.pdf may help. Note that you're asking for the function corresponding to $P$ whose autocorrelation is the given function corresponding to $A$. ...
• 1,125
1 vote
Accepted

### A non-trivial combinatorial optimization

This is NP-hard even for $d=1$ by reduction from the (strongly NP-hard) Product Partition problem. Lemma 1. The problem (with either objective function) is NP-hard, even for $d=1$. Proof sketch. Given ...
• 10.8k

Only top scored, non community-wiki answers of a minimum length are eligible