10

Just an extended comment: You can take a look to the approach used by Steinbach and Posthoff to find the 4-coloring of a 18x18 (and 12x21) grid without monochromatic rectangles: Bernd Steinbach and Christian Posthoff, Solution of the Last Open Four-Colored Rectangle-free Grid an Extremely Complex Multiple-Valued Problem. In Proceedings of the 2013 IEEE ...


8

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 there is an edge $(i,j)$ in G (where $i$ is an element of the left partition, and $j$ an element of the right partition). Then $M$ has binary rank $r$ if and ...


8

Rephrasing as a set system, each row represents a subset $E_i$ of some set $X$, for $i=1,2,\dots,m$. You want a set $Y \subseteq X$ with at most $k$ elements, such that $E_i \cap Y \ne \emptyset$ for each $i$. In other words, you want a hitting set of size at most $k$; this problem is NP-complete.


7

Your problem seems a special case of the turnpike reconstruction problem (for which no polynomial time algorithm is known). See for example: Shiteng Chen, Zhiyi Huang, and Sampath Kannan, "Reconstructing Numbers from Pairwise Function Values". Abstract: The turnpike problem is one of the few natural problems that are neither known to be NP-complete nor ...


6

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


6

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 Judgments: Automatically Generating Well-Typed Terms from the Definition of a Type-System to the more theoretical Grygiel & Lescanne, Counting and generating ...


6

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 value at least $n/2$ (give every vertex a value of $1/2$). But the optimal independent set might be of size between $1$ and $n$. On the other hand, the greedy ...


4

An example of a locally monotone function is $g(x,y) = x \cdot (1-y)$. In this example $g$ is monotone increasing in $x$ and monotone decreasing in $y$. An example of a function that is not locally monotone is $h(x,y) = x \oplus y$. Let's see why it is not locally monotone. Look at the $x$ variable. (1) It is neither monotone increasing in $x$ since $h(0,1) ...


4

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 approach for $n=23$, but obtained no solution in about 96 hours. It is thus tempting to conjecture that $n=23$ is not 3-colorable anymore. (Let me also remark ...


4

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 instance of k-coloring. See, for example, section 8.8 of Aho, Lam, Sethi and Ullman (i.e. Dragon Book).


4

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,\dots,x_n) = (x_1-z_1)^2 + (x_2-z_2)^2 + \dots + (x_n-z_n)^2.$$ Based on this, we can easily construct a function $g : \{0,1\}^n \to \mathbb{R}$ that is zero at ...


3

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 equal length, so your problem is at least as hard as bin packing), which is known to be NP-complete. Consequently, your problem is NP-hard, too. All the usual ...


3

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.e., it has no infinite subset in $\mathsf{NP}$. In particular it has no infinite subset that is a context-free language.


3

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 in at most $n$ sets. The theorem states that in this case the elements can be colored with red and blue such that the difference of the red and blue elements in ...


3

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 it back at least to Lamport's 1983 seminal paper on temporal logic.


3

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 ouputs the corresponding decomposition. On the Parameterized Complexity of Biclique Cover and Partition. L. Sunil Chandran, Davis Issac, and Andreas ...


2

It is NP-hard, here is a reduction from SAT: You have variables $x_1,\dots,x_m$, and clauses $C_1,\dots,C_n$ on these variables. You build the following $(m+n)\times 2m$ matrix: For $i\in[1,m]$, the $i^{th}$ row contains only $0$ except two $1$'s in column $i$ (representing variable $x_i$) and column $m+i$ (representing $\neg x_i$). Then, the following $...


2

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 it if you don't use exact arithmetic. There are $M \choose j$ sets of size $j$. The probability that there are $j$ elements chosen is $M \choose j$ times the ...


2

For very crude bounds, you could use Chebyshev's inequality. Let $x$ denote one (fixed) value from the set of $M$ possibilities. The probability that $x$ appears at least once in the union of the sets is something like $$p = 1 - \left({{M-1 \choose N} \over {M \choose N}}\right)^k.$$ Now if we let the random variable $X$ denote the number of elements ...


2

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)^k \mu_\text{dnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$. In the literature, the quantity $\sum_{\nu \models \phi} (-1)^{|\nu|}$ is also ...


2

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 not necessarily linear mathematical program $$\begin{eqnarray} \textrm{maximize}\,\,&\tfrac{\sum_{(i,j) \in E} x_{ij}}{\sum_{i \in V} y_i}& \\ \textrm{...


1

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 column weight of a Tanner graph, given that is has no 4-cycle. Assuming uniform column weights, then the maximum column weight is $O(\sqrt{k})$. This is known as ...


1

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 solution to construct a bipartite graph whose maximum-weight matching corresponds to the solution in some way; this is straightforward. Finally, output that graph. ...


1

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 just look for any number of edge subsets of of size $O(\textsf{the desired size})$. Maybe this helps think about the problem. Fix any graph $G=(V,E)$ and integer ...


1

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. A draft of it can be found here. Concerning Extremal Combinatorics, Wiki suggests reading Extremal and Probabilistic Combinatorics by Noga Alon and Michael ...


1

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 (exponential), Turing machine state (constant) and position of the head over the tape (polynomial)). Thus any machine that runs for more than exponential time ...


1

"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$. I've often thought that there's some relation to factoring, at least to for the turnpike version. You can consider $A$ as an integer $Z=a_1x^1+a_2x^2+⋯a_Nx^...


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