# 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,721

### 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 ...
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.3k

### conversion to DAG

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

### Greedy vs LP Approximation

Well, there are cases where LP gives you no useful information. Consider a graph $G$ with $n$ vertices, and the problem of finding a maximum independent set in $G$. The LP gives you a solution of ...
• 9,566

### 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,160
Accepted

### Complexity of generating a pseudo-Boolean function

There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely, f_z(x_1,\...
• 10.5k

### 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,125
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

### 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 ...
• 10.5k
Accepted

### Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

No, we get counterexamples by considering resource-bounded randomness. In fact the gap between c.e. and $\mathsf{CFL}$ is wide. Let $R$ be exponential-time random. Then $R$ is $\mathsf{NP}$-immune, i....
• 4,400
Accepted

### Directed graph with bounded in-deg can be partitioned in a balanced way

This is a special version of the Beck-Fiala theorem. Define a set system on the vertices whose sets are the out-neighborhoods of the vertices. The in-degree condition will give that every element is ...
• 13.6k
Accepted

### What is the standard name for the function which inflates a string by duplicating each of its characters?

As pointed out by Marcus Ritt, the correct name for this operation seems to be stutter. As far as I could determine, it has mostly been used in the field of concurrency theory, where I could trace ...

### Probability for an element to appear in at least one set

We can write an exact expression for the probability as a single sum using inclusion-exclusion. This sum has terms which can oscillate wildly in magnitude, so some care needs to be taken to evaluate ...
• 316

### Distributing a binary relation into bins such that each element is in a small number of bins

This is not an answer. It is just the somewhat trivial observation that WLOG you can relax the requirement that there be exactly $p$ edge subsets $\{E_i\}_i$ of exactly the same size, and instead ...
• 8,281