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.
  • 4,721
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 ...
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 ...
  • 13.3k
6 votes

conversion to DAG

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
  • 1,432
6 votes
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 ...
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 ...
  • 3,160
4 votes
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
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 ...
  • 1,125
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 ...
3 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 ...
  • 10.5k
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....
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 ...
  • 13.6k
3 votes
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 ...
2 votes

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 ...
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 ...
  • 8,281
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)...
  • 1,197
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 ...
  • 1,633
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 ...
  • 814
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 ...
  • 10.5k
1 vote

What's a good advanced textbook/resource for studying the complexity of counting and combinatorics?

If I understood correctly, you're looking for a book (chapter) on counting complexity. In this case, I'd recommend the book of Sanjeev Arora and Boaz Barak, which has a chapter on counting complexity. ...
  • 161
1 vote
Accepted

An algorithm for counting to Graham’s Number

With only a polynomial amount of memory, a program that terminates can run for at most exponential time. This is because there are only exponentially many states (i.e. a combination of tape content (...
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$. ...
  • 852

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