Skip to main content
8 votes
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.
J.-E. Pin's user avatar
  • 4,841
8 votes

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 ...
Sasho Nikolov's user avatar
6 votes
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 ...
cody's user avatar
  • 13.9k
6 votes

conversion to DAG

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
Laakeri's user avatar
  • 1,786
5 votes

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))...
Clement C.'s user avatar
  • 4,471
4 votes

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 ...
D.W.'s user avatar
  • 12.2k
4 votes

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 ...
Juho's user avatar
  • 3,170
4 votes
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 ...
Davis Issac's user avatar
4 votes

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 ...
xrq's user avatar
  • 1,185
3 votes
Accepted

Cover a graph with complete graphs

Here are asymptotic bounds for $k(n, m)$ that are tight up to a logarithmic factor. Note the threshold around $m = \Theta(n^{3/2})$: Theorem 1. $~~~~\frac{1}{21}\min(\lceil\sqrt n\rceil, \lceil m/(n\...
Neal Young's user avatar
  • 10.8k
3 votes
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....
Bjørn Kjos-Hanssen's user avatar
3 votes
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 ...
domotorp's user avatar
  • 14k
2 votes

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 ...
Neal Young's user avatar
  • 10.8k
2 votes
Accepted

Möbius values of CNF and DNF lattices of a monotone Boolean function

OK so, more than one year later, here is the answer to this. We'll see Boolean valuations $\nu$ as the set of variables that are mapped to $1$. We can show that $\mu_\text{cnf}(\hat{0},\hat{1}) = (-1)...
M.Monet's user avatar
  • 1,429
2 votes
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 ...
Yonatan N's user avatar
  • 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 ...
smapers's user avatar
  • 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 ...
D.W.'s user avatar
  • 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$. ...
Mark S's user avatar
  • 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 ...
Neal Young's user avatar
  • 10.8k

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