Pulling a graph across a partition I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am just ignorant of, in which case I apologise, and would be grateful to be set right.

The property is as follows:

Take a graph $G=(V,E)$ on $n$ vertices, where $V$ is the vertex set and $E$ is the edge set. Let me define two families of subsets of vertices, $A_i$ and $B_i$, with the relationship that $B = V \setminus A$. I require that $A_0 = V$ and $A_n$ is the empty set. Each intermediate $A_i$ is obtained from $A_{I-1}$ by removing one vertex (according to some strategy). The property I care about is $\max_i |\{(a,b): a\in A_i, b\in B_i,(a,b) \in E\}|$, minimised over all strategies for choosing $A_1 \ldots A_{n-1}$ according to the rules above.

$A_i$ and $B_i$ can be thought of as the $i$th step in a process of moving vertices of the graph from one side of a partition (the $A$ side) to the other (the $B$ side). Thus the property I am concerned with has an operational interpretation as the maximum number of edges that need to cross the partition at any one point in time as we move the graph from one side to another, minimised over all strategies for moving vertices across the partition.

Aside from computing the value of this property, an algorithm for determining the optimal strategy would also be helpful.

What you are looking for is known as Cutwidth. The problem is NP complete and quite well studied. For example it has a $O((\log n)^{3/2})$- approximation algorithm and is fixed parameter tractable when parameterized by the objective function value.


Kleene Algebra for star-free regular expressions TLDR: Is there a notion of Kleene Algebra for star-free regular expressions?

Kleene Algebras are algebraic structures that are equivalent to regular expressions. A Kleene Algebra is an idempotent semiring (non-commutative multiplication) with an extra unary operation $*$ that satisfies that following equations:
\begin{align}
&1+x\cdot x^* = x^* \\ &1+x^*\cdot x = x^* \\ &z+xy\le y \implies x^*\cdot z\le y \\ &z+yx\le y \implies z\cdot x^*\le y
\end{align}
where $x\le y$ means there exists $z$ such that $x+z=y$. Equivalence with regular expressions formally means, given regular expressions $r_1$ and $r_2$, $\mathcal{L}(r_1)=\mathcal{L}(r_2)$ iff we can prove $r_1=r_2$ using the axioms of Kleene Algebra.

Star-free regular expressions are regular expressions without the Kleene star but with the ability to take complements i.e. $$r_1,r_2::= \emptyset\mid a,b,c\in A\mid r_1\cup r_2\mid r_1\cap r_2\mid r_1\cdot r_2\mid (r_1)^c$$ where $A$ is the set of alphabets. Observe that complementation restores some Kleene star powers but not all: $A^*=(\emptyset)^c$ while $(aa)^*$ has no star-free form.

I was wondering how to tweak Kleene Algebra so that we capture exactly star-free expressions. While coming up with equation templates for the complementation operation the challenge is to get an equation for $(r_1\cdot r_2)^c$ because the rest of the interleaving of operations is taken care of by De Morgan's laws. Also, since Kleene Algebras do not explicitly talk about the alphabet set, I guess $a^c$ should be considered a normal form.

You might be interested in bounded synchronization delay expressions.
See [1] for details on these expressions.
To sum up, they are equivalent to star-free expressions, but instead of using complement, they restrict the use of the Kleene star to certain languages: the prefix codes with bounded synchronization delay.

This way, you can have your characterization: $L(r_1)=L(r_2)$ iff we can prove $r_1=r_2$ using the axioms of Kleene Algebra, the only difference being that $r_1$ and $r_2$ are more constrained on the use of Kleene star, and only represent star-free languages.

On the other hand, axiomatization of regular expressions with complement has been done in [2], so after careful verification, you could possibly use this to axiomatize star-free expressions directly.

[1] Diekert, V.; Kufleitner, M., Bounded synchronization delay in omega-rational expressions, Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. 7th international computer science symposium in Russia, CSR 2012.

[2]
Salomaa, A.; Tixier, V., Two complete axiom systems for the extended language of regular expressions, IEEE Trans. Comput. 17, 700-701 (1968). ZBL0174.29001.


Funny TCS-related papers etc? What is the funniest TCS-related published work you know?

Please include only those that are intended to be funny.  Works which are explicitly crafted to be intelligently humorous (rather than, say, a published collection of short jokes regarding complexity theory) are preferred.  Works with humorous (actually humorous, not just cute) titles are also accepted.

Please only one work per answer so the "best" ones can bubble to the top.

Scott Aaronson's newspiece: Polynomial
hierarchy collapses: thousands feared tractable


Higher-order and black-box clustering As far as I understand a large number of clustering problems can be formulated as:

$\underset{\textbf{P}}{ \text{argmin}} \;  \sum_{i,j} f \left(x_i, x_j\right)$

where $\textbf{P}$ is a partitioning of $\mathbf{x}$. In other words, the goal is to find a partitioning that is optimal with respect to a sum of pairwise contributions of the variables within and/or across clusters. Problems such as K-means and correlation clustering can be written in the above form. For example, K-means minimizes the sum-of-squares which is known to be NP-hard.

I am wondering if there is any work on what I informally would call higher-order or clustering, where the functions $f$ measure the affinity of general cliques of variables

$\underset{\textbf{P}}{\text{argmax}}\; \sum_{c_i} f(\mathbf{x}_{c_i})$

for cliques $c_i$ in some set $C$.

Perhaps a more difficult problem is what I would informally call black-box clustering, i.e. problems of the above form where $f$ is unknown (i.e. we don't have access to an algebraic or analytical expression of $f$, but we can query it. I imagine using some sort of direct-search optimization method for solving such problems.

Does anybody know of if these problems have been addressed in the literature? Perhaps they are known by other names?

One example of what you might call non-linear clustering is kernel-based clustering, where the similarity function is described by a (non-linear) kernel function. This is a weak form of non-linearity, since there's a lifting map that makes everything linear (albeit in a Hilbert space)


Combination of Disjointness and Gap Hamming Distance communication complexity Consider the two player constant-round communication problems:

Gap Hamming Distance $\Delta(a,b)$ where Alice and Bob each has an $n$-length bit string $a$ and $b$ respectively.

YES case: $\Delta(a,b) \geq n/2+\sqrt{n}$.

NO case:  $\Delta(a,b) \leq n/2-\sqrt{n}$.

Known result: Distinguishing between YES and NO requires $\Omega(n)$ bits of communication

Consider $m$ instances of Gap Hamming Distance $a_i,b_i$ for $i=1,2,\ldots,m$. Alice has $a_i$ and Bob has $b_i$. We are promised such that either all $(a_i,b_i)$ are NO instance (Case 1). Or exactly one pair of $(a_i,b_i)$ is a YES instance (Case 2).

Is is true that the communication complexity to distinguish Case 1 and Case 2 of this new problem is $\Omega(mn)$?

Yes, because (1) KLLRX prove $\Omega(n)$ information lower bound for Gap Hamming (for distribution over both YES and NO inputs), and (2) Theorem 3 in GJPW shows any such information lower bound holds also wrt distribution over NO inputs, and (3) BJKS paper shows that composing any function with m-bit OR increases the information complexity over NO inputs m-fold.


PH and Optimization Problems If we have a machine which can solve any problem in the second level of PH,
can this machine solve optimization problems which is generalized version of NP-complete problems such as MAX-CLIQUE or MIN-COLORING ?

I think that the answer is yes and that the power of this machine is strictly powerful than the one for solving the optimization version.  However, I am not sure the differences between decision class and function class,i.e, PH is a class of decision problems but optimization problems are not.

Let machine M solves the $\Sigma_2^p$-complete problem. We can use  this  machine to solve
any "NP-Hard" optimization problem (which includes MAX-CLIQUE and MIN-COLORING)  in
additional time polynomial in size of input as follows:

The solution is described for MAX-CLIQUE but the same idea works for any NP-Hard optimization problem. Let G = (V, E) and

O = { $<G,k>$ : the size of largest clique in G is k }

D = { $<G,k>$ : there is a clique of size >= k in G  }

Observation 1: Problem of deciding language O can be solved by making $\log{|V|}$ calls
to  the machine that decides D [Using Binary search]

Reduce instance of O to instance of D by using observation 1
Reduce instance of D obtained to instance of $\sigma_2^p$ complete problem P
Solve P using M

The reductions are all polynomial time, so its easy to see that if M works in polynomial
time then we can compute MAX-CLIQUE using M with polynomial time overhead.

Using the above reduction we can also see that M is at least as powerful as the machine
that solves NP-hard optimization problems.


Polynomial-time algorithms with huge exponent/constant Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, where the proven upper bound on the running time is in such a way)?

Here are two screenshots from An Energy-Driven Approach to Linkage Unfolding by Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben,  James F. O’Brien, SOCG 2004:


What type system fits the subclass of λ-terms that can be reduced optimally? There is a subset of λ-calculus terms that can be reduced by Lamping's Abstract Algorithm without using the Oracle. That is an interesting subset, because only for those terms it is proven that Lamping's algorithm is optimal and superior to naive strategies.

In order to use this in practice, one can write programs on the untyped lambda calculus and experimentally test if Lamping's Algorithm works on them for some inputs. It it does, the term is probably on that subset. For example, my answer to this question is a Church-nat sorting algorithm that was developed this way. That is inconvenient for 2 obvious reasons:

You can't be 100% sure an algorithm will work for all inputs by experimenting it on some.
Programming on the untyped lambda calculus can lead to human type errors.

An immediate solution to problem #2 would be to instead write your programs in a type system on the Lambda Cube (such as System F), but that doesn't work quite well in practice because algorithms on the optimal subset often rely on Scott-encoded data structures (as depicted on my answer above), which are excluded from those type systems. And about problem #1, I'm aware of some type systems based on light logics, but I found them overly complicated and I'm not sure how they could be used in practice.

What type system better fits the subclass of λ-terms that can be reduced optimally, in a way that could be used as the type system of a practical programming language?

I think that the type system you want is elementary affine logic with fixpoints.

A distinctive feature (actually, the distinctive feature) of light logics, including elementary linear/affine logic, is that types do not ensure termination: unlike usual logical system, cut-elimination follows from a structural property of proofs (namely, stratification), the logical complexity of formulas does not play any role.  Types in EAL only give you well-formedness properties (like progress, i.e., normalization doesn't get stuck; or the fact that the normal form will have a certain shape).

The fact that cut-elimination holds regardless of types means that you can add arbitrary type fixpoints to EAL and you still get normalization with the same complexity bounds (elementary), because you still have stratification.  With type fixpoints, Scott numerals get the following type:

$$\mu \beta.\forall \alpha.(\beta\multimap\alpha)\multimap\alpha\multimap\alpha$$

A paper that uses EAL+type fixpoints explicitly is

Patrick Baillot. On the expressivity of elementary linear logic: Characterizing Ptime and an exponential time hierarchy.
Information and Computation 241: 3-31, 2015.

You will find formal definitions there.  However, I am afraid that no implementation exists.


Information Theory used to prove neat combinatorial statements? What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ?

Some examples I can think of are related to lower bounds for locally decodable codes, e.g., in this paper: suppose that for a bunch of binary strings $x_1,...,x_m$ of length $n$ it holds that for every $i$, for $k_i$ different pairs {$j_1,j_2$}, $$e_i = x_{j_1} \oplus x_{j_2}.$$ Then m is at least exponential in n, where the exponent depends linearly on the average ratio of $k_i/m$.

Another (related) example is some isoperimetric inequalities on the Boolean cube (feel free to elaborate on this in your answers).

Do you have more nice examples? Preferably, short and easy to explain.

Moser's proof of the constructive Lovasz Local Lemma.  He basically shows that, under the conditions of the local lemma, the second-simplest algorithm for SAT you can think of works.  (The first simplest might be to just try a random assignment until one works.  The second simplest is took pick a random assignment, find an unsatisfied clause, satisfy it, then see what other clauses you broke, recurse, and repeat until done.)  The proof that this runs in polynomial time is perhaps the most elegant use of information theory (or Kolmogorov complexity, whatever you want to call it in this case) I've ever seen.


Complexity of the edge-disjoint cycle covers I am interested in decompositions of a directed graph $G=(V,E)$ into non-intersecting Eulerian subgraphs $G_i=(V_i, E_i)$. I want to find the decomposition that covers the largest number of edges.

I believe that the best case is when a "Eulerian decomposition" exists, that is, the union of $E_i$ gives back $E$.

This problem is related to the minimum cycle cover of a graph but distinct. The minimum cycle cover wants to find cycles covering all edges with minimum overlap, whereas I want find cycles with no overlap covering as many edges as possible.

More specifically, I am interested in complexity results related to the following problems:

Given an integer $k$, is there an edge-disjoint cycle decomposition covering more than $k$ edges?
Is there an edge-disjoint cycle decomposition covering all edges?

Edit:

The second question has been answered in comments and appears to be polynomial.
The first question seems to be equivalent to "What is the smallest number of edges that can be removed from a graph so that each vertex has the same in-degree as its out-degree."

The problem is polynomial-time solvable.

Say that a vertex is balanced if its in-degree equals its out-degree.

Note that a directed graph is Eulerian iff every vertex is balanced and its underlying undirected graph is connected. Now, a directed graph is a vertex-disjoint union of Eulerian graphs iff every vertex is balanced. So, the problem amounts to deleting a smallest number of arcs so that each vertex becomes balanced. In Theorem 2 of the following paper, this problem is solved in polynomial time using network flows.

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1): 41-61 (2014).


Finding the shortest distance in a dynamic graph I have a non-weighted directed graph G with edges E and vertices G. Edges can be added or removed, and therefore vertices can be added.

For instance, if I have a graph with 4 nodes: 0, 1, 2, 3 and if I add the edge 3 -> 4, it means the node 4 will be added. Nodes cannot be removed.

I am studying the problem of determining the shortest distance (just distance, not path) in this dynamic graph. I am very newbie in this problem, but as I know it would be still an open problem.

What is the fastest algorithm for this problem so far?

Thank you very much

The search keywords are "dynamic all pairs shortest paths".

Demetrescu and Italiano have a good survey,
http://dl.acm.org/citation.cfm?id=1198519

Looks like $O(n^2 log^3 n)$ cost per update if you want to maintain fast lookups.


Efficient universal problem solver? Define a "problem" to be an algorithm $A$ accepting a natural number and returning 0 or 1 which returns $1$ on at least one $n \in \mathbb{N}$. Any such $n$ is called a "solution" to $A$

Define a "universal problem solver" to be an algorithm $U$ accepting a problem and returning one of its solutions. For example, $U$ can work by looping over all natural numbers and running its input on them until $1$ results (it only has to halt on valid input)

I'm interested in exploring performance bounds on universal problem solvers

Given $U$ a universal problem solver and $A$ a problem, denote $t(U, A)$ the time it takes $U$ to produce output upon accepting input $A$

A universal problem solver $U$ is called "efficient" when for any universal problem solver $V$, we have

$$t(U, A) < t(V, A) + t_V $$

Here $t_V$ depends on $V$ but doesn't depend on $A$

  Do efficient universal problem solvers exist?

EDIT: I realized it is possible to change the definitions of "problem" and "universal problem solver" into something slightly more elegant and essentially equivalent. A "problem" is an algorithm without input returning 0 or 1 (which halts). A "universal problem solver" is an algorithm accepting a problem and returning its result. It's more or less a universal Turing machine

Old definition can be reduced to new definition, since given $A$ a problem in the old sense, we can construct $B$ a problem in the new sense which just applies the trivial old-sense universal problem solver to $A$ (the solver described in the text above)

New definition can be reduced to old definition, since given $B$ a problem in the new sense, we can construct $A$ a problem in the old sense which just computes $B$ and compares the input to the result

The trivial example of a new-sense universal problem solver is an algorithm which simply runs its input

Levin's universal algorithm is an algorithm such that $t(U,A) < s_V t(V,A) + t_V$. By modifying the algorithm (see for example Hutter's The Fastest and Shortest Algorithm for All Well-Defined Problems), you can make $s_V$ a universal constant, though definitely not $1$ as you require. For related work, consult work by Hirsch, Itsykson and their students, for example this technical report.

Edit: As Squark comments, the runtime of Levin's algorithm also depends on the runtime of $A$, since it has to verify its answers. To get a constant $s_V$, all you need to do is to set the speeds of the various algorithms in geometric progression (rather than arithmetical progression, like in Levin's original algorithm).


Fast Finding Main Diagonal of Matrix Multiplication Suppose we have two matrices $A_{m\times n}$ and $B_{m\times m}$. Such that $B$ is a symmetric positive definite matrix. Is it possible to compute main diganoal of $A^TBA$ in $O(n\times m)$?

Not unless $\omega = 2$. Take $B = \operatorname{id}$, $A = \begin{bmatrix}X & Y\end{bmatrix}$. You can extract $XY$ from $A^TBA$.

UPDATE: I missed the main diagonal part of the question. Even computing the main diagonal is as hard as matrix multiplication: denote $f(A, B) = \operatorname{tr}(A^TBA) = \sum_{i,j,k} a_{ij} b_{ik} a_{kj}$. The derivatives $\frac{\partial f(A, B)}{\partial a_{ij}}$ form the matrix $BA + A^TB$, and we can apply the Baur-Strassen theorem.


Using partial functions to prove correctness I'm interested in proving that a program (which may or may not terminate) will give the correct answer if it terminates.  Given:

$P$ is a family of programs, parameterized by a function $f$. Write $P_f$ for a particular program from this family.
We know that $P_f$ is correct.
$g$ is partial function from the same domain to the same range as $f$.
Moreover, $g$ is a subset of $f$; that is, for all $x$ where $g(x)$ is defined, $g(x) = f(x)$.

I'd like to show that $P_g$, wherever it terminates, gives the correct answer.  This seems intuitively obvious.  However, I'm struggling to find the appropriate math for it.

Most importantly, if we use functions instead of programs the claim is not correct.  For example, if $Q$ is a multivariable function, $Q(f,n)$ does not in general equal $Q(g,n)$, even if they're both defined.  However, if we think of $Q$ not as a function but as a program, which gets to use $f$ and $g$ as oracles, then they are.  What is the proper way to show that mathematically? Or, even simpler: What is the correct mathematical term for $Q$? If it's not a function, what is it?

By program, I mean "algorithm which makes use of an other algorithm"; I'm not referring to any particular language or implementation.  Note that even in functional languages like Haskell, due to the Halting Problem, a program is not truly a function: a program isn't guaranteed to terminate, whereas the concept of terminating doesn't apply to functions.  A function of $f$ can depend on whether $f$ terminates, but no program which uses $f$ as a subroutine can.

Indeed, this is the essence of waht I'm struggling with: What is the appropriate mathematical formalism for a program which uses other programs as subroutines?

If I read you correctly, the intuition you have in mind goes like this:

Suppose we have a program $P$, which takes a function as an argument. Further suppose that we have two functions $f$ and $g$, such that $f$ terminates on a subset of the inputs $g$ terminates on, but agrees with $g$ whenever they both terminate.

Now, if $P\;g$ is partially correct, then you want to argue that $P\;f$ must also be partially correct. After all, the "only thing" that $P$ can do with its functional parameter is to apply it (what you call "use as an oracle"), and so $P\;f$ must compute the same values as $P\;g$, possibly terminating less often.

This is more or less exactly the intuition underlying domain theory. The idea is that we can interpret computations at a particular type as CPPOs, or chain-complete pointed partial orders.

That is, a CPPO is a triple $(X, \bot, \leq)$, with $X$ as the set of elements denoting computations, $\bot$ as the nonterminating computation, and $\leq$ as a partial order representing how close to fully defined a computation is. $\bot$ is the least element in this partial order, and the chain-completeness condition says that if you have a countable chain $x_0 \leq x_1 \leq \ldots$, then the chain has a least upper bound $\bigsqcup_{i \in \mathbb{N}} x_i$.

Programs are interpreted by continuous functions between CPPOs, with the idea that continuity is a stand-in for computability. That is, a function $f : X \to Y$ should be a monotone function which preserves lubs.

In particular, the set of continuous functions $X \to Y$ also forms a CPPO, with the least element given by $\lambda x.\;\bot_Y$, and the order given pointwise, so that

$$f \leq_{X \to Y} g \iff \forall x \in X.\; f\;x \leq_Y g\;x$$

Then the property you want follows more or less instantaneously. Suppose we have a continuous $P : (X \to Y) \to Z$. Then $f$ being "less defined" than $g$ amounts to saying that $f \leq g$. Then, by the continuity of $P$, it follows that $P\;f \leq P\;g$.

Samson Abramsky and Achim Jung have a chapter on domain theory in the Handbook on Logic in Computer Science, which is freely available online.


Is there an extension to the stable roommates problem with multiple roommates per room? The stable roommates problem presents a set of N two-person rooms and 2N would-be roommates with preferences over each other, and asks for a stable allocation of roommates to rooms (and, really, to each other). There is an efficient algorithm which finds a solution, if there is one.

Is there an extension of this problem to rooms which can take more than two people?

Such an extension does seem challenging, because so much of the definition of the problem rests on the fact that roommates are in pairs, which means that each roommate only shares with a single other. This makes comparisons between potential pairings trivial - does the roommate prefer this partner or that one? Asking whether a roommate prefers one set of partners or another is much harder. Still, i'm interested in any approaches which have been taken!

Switching from 2 to 3 "beds" makes the problem NP-complete :-)

See K. Iwama, S. Miyazaki, and K. Okamoto, "Stable roommates problem with triple rooms." Proc. 10th KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2007), pp. 105–112, 2007

(an electronic edition can be downloaded from ResearchGate).

Abstract: In the stable roommates problem, we are given 2N men and each person's preference list. We are asked to find a stable matching, namely, a set of N pairs satisfying the stability condition. This problem is known to be solved in polynomial time; more precisely, there is a polynomial-time algorithm to find a stable matching for a given instance, or to report that a given instance has no stable matching. In this paper, we extend this problem into three-dimension, i.e., a matching is defined to be a set of triples, and show that this problem is NP-complete. ...

See also this survey: Kazuo Iwama and Shuichi Miyazaki. 2008. A Survey of the Stable Marriage Problem and Its Variants. In Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008) (ICKS '08). IEEE Computer Society, Washington, DC, USA, 131-136.


Minimum chordless odd-cycle graph completion: is it NP-hard? The following interesting problem came up in my research recently:

INSTANCE: Graph $G(V, E)$.

SOLUTION: A chordless odd-cycle completion, defined as a superset $E'$ of the edge set $E$ so that the completed graph $G'(V, E')$ has the property that every edge in $G'$ is contained in a chordless odd cycle.

MEASURE: The size of the completion, i.e., $|E' - E|$.

So far, we were able to prove that a modified version of this problem is NP-complete, where instead of requiring that "every edge in $G'$ is contained in a chordless odd cycle" we require the stronger property that "every edge is contained in a triangle (cycle of length 3)". (Note that this is not equivalent with the MINIMUM CHORDAL GRAPH COMPLETION problem.)

The former is easily seen to be a generalization of the latter, but this far all my efforts to prove it failed. Could anyone come up with a pointer/reference/etc.?

We prove that the problem is NP-hard even in its decision form, i.e. ''Is the input graph $G$ already a chordless odd-cycle completion?'' by reduction from the following problem:

  Problem P: Given a graph $G$ and an edge $e\in E(G)$, is there an chordless odd cycle of length greater than 3 passing through $e$?

This problem is known to be NP-hard by reduction from ''detecting chordless even cycles passing through a given node'' in the reference given in one of your comments which is stated in the paragraph before section 3 by letting $p=0$ and $q=2$:

  As an aside, let $q>1$ and $p\ge 0$ be arbitrary fixed integers. The following problems are NP-complete: Does a graph $G$ contain an induced cycle through a prescribed vertex $u$, of length $p$ (mod $q$)? ...

(There may be a Karp reduction, but if we allow a Cook one, consider the following reduction: Replacing the given degree d node into a complete subgraph of size d with proper outgoing edges.  Then for each edges in the complete graph we can query the oracle that solves Problem P.  Note that a chordless even cycle passing through the given node corresponds to a chordless odd cycle of length greater than 3 passing through one of the edges in the complete graph.)

Now for the main reduction.  Given an instance of Problem P, first we detect if there are any triangles passing through $e$; if so, delete every node that forms a triangle with $e$.  Note that deleting nodes that forms a triangle with $e$ will not removing any chordless odd cycles passing through $e$ (by the chordless property).

Next, for each edge $f$ other than $e=(u,v)$ we add an auxiliary node $v_f$ and two edges $(v_f,u)$ and $(v_f,v)$.  Observe that the new graph $G'$ has the following property:

  $G$ has a chordless odd cycle of length greater than 3 passing through $e$ if and only if $G'$ is a chordless odd-cycle completion.

For the only if direction, it can be proved by considering different types of edges in $G'$.  Every edge other than $e$ (including those newly added edges) will be in at least one triangle (the one that contains the auxiliary node); and $e$ will be in a chordless odd cycle in $G′$ since there is a chordless odd cycle passing through $e$ in $G$, and the cycle is not removed during the node-deleting process.

For the if direction, since every edges other than $e$ must be in at least one triangle, we only have to worry about the edge $e$.  There is a chordless odd cycle passing through $e$ in $G'$ ($G'$ is a chordless odd cycle completion).  The cycle cannot have length 3 by construction of $G'$, and since the cycle cannot contain any auxiliary nodes (by chordless property), it will be in graph $G$ as well.  Therefore the proof is complete.


Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$ Let $H$ be a maximum induced interval subgraph of a graph $G=(V,E)$.  If $n=|V|$， then what is the smallest number of $V(H)$?

The number is at most $3n/4$： consider a set of disjoint $4$-holes.

Can it be smaller?

We can do $2\sqrt{n}-1$; consider the complete $\sqrt{n}$-partite graph, as long as there are two parties both with more than one node inside there is an induced $C_4$, so it cannot be inteval.  Therefore we have to remove at least $(\sqrt{n}-1)^2 = n - 2\sqrt{n} + 1$ nodes to destroy all the induced $C_4$.


Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry? Are there any problems that are NP-complete when using Euclidean geometry but are well-defined and solvable in polynomial time for some non-euclidean geometry?

Partial answer:

Maximum TSP is polynomial time solvable under polyhedral norms,
but NP-hard for Euclidean norms (optimization as well as decision
version). Whether the latter is also NP-easy is a different question.
(You might be able to define a somewhat artifical variant that is in NP,
since the instances created for the NP-hardness proof only require
bounded precision.)

A. Barvinok, S. P. Fekete, D. S. Johnson, A. Tamir,
G. J. Woeginger, and R. Wodroofe.
The geometric maximum Traveling Salesman problem.
Journal of the ACM, 50:641-664, 2003.


Data structure for radial orderings of points on the plane Assume points are always in general position.
For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$.

Consider shooting an upward vertical ray from $x$, and rotate the ray counterclockwise. The sequence of points in $S$ swept through by the ray is the radial ordering.

Given a set of $n$ points on the plane. Create a data structure, so it can answer the following query:

  Query($x$,$i$)

  Input: $x\in S$, $1\leq i\leq n-1$.

  Output: The $i$th element in the radial ordering with respect to $x\in S$.

Is there any study on such a data structure?
In my application, there will be around $\tilde{O}(n)$ queries.

This problem is the same as halfspace range counting up to polylog factors.

  Halfspace range counting in 2D

  Preprocess $n$ points $S$ on the plane. A query takes a halfspace $H$ (represented by the boundary), and return $|H\cap S|$.

For the case of $\tilde{O}(n)$ queries, one can use $\tilde{O}(n^{4/3})$ time to build a data structure that returns the answer in $\tilde{O}(n^{1/3})$ time. This is the best possible up to polylog factors [1].

Proof Sketch:

Upper bound:

The simplex partition tree data structure for halfspace range counting [1] can be used directly for this problem. A simple solution would be using a halfspace counting query as a proxy for binary search while navigating the partition tree. I believe polylog factors can be saved with more care.

Lower bound:

Consider we want to solve the halfspace range counting problem in 2D on $S$,
we first construct the radial orderings data structure.

For any halfspace $H$ as input, we shift the halfspace up until it touches an element in $S$. By duality, this operation can be modeled as a vertical ray shooting problem in a convex polygon defined by the intersection of halfspaces, which is known to be very fast [2].

We can use our data structure to do binary search. We find two adjacent points in the radial ordering so the slope of $H$ is in between. The index shows the number of points in $H\cap S$.

Matoušek, Jiří, Range searching with efficient hierarchical cuttings, Discrete Comput. Geom. 10, No. 2, 157-182 (1993). ZBL0774.68101.
Agarwal, Pankaj K.; Matoušek, Jiří, Ray shooting and parametric search, SIAM J. Comput. 22, No. 4, 794-806 (1993). ZBL0777.68042.


Gaussian Elimination in terms of Group Action Gaussian elimination makes determinant of a matrix polynomial-time computable.   The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence of alternate negative signs (lack of which makes computing permanent is $ \#P\mbox{-}hard$ ie. harder then $NP\mbox{-}C$ problems). This leads to some sort of symmetry in determinant, eg exchange of a pair of rows or columns just reverses the signs. I read somewhere, probably in connections with holographic algorithms introduced by Valiant, that Gaussian elimination could be explained in terms of group action and this in turns leads to generic techniques in complexity reduction.

Also, i feel that almost all source of complexity reduction for any computational problem is some sort of symmetry present. Is it true? Can we rigorously formalize this in terms of group theory?

Edit

I found the reference. (pg 2, last line of second paragraph). I did not understand the paper properly, If my question is based on wrong understanding of the paper, please correct me.

In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) and is characterized by that symmetry group (meaning any other homogeneous degree $n$ polynomial in $n^2$ variables with those symmetries must be a scalar multiple of the determinant). (And, as to @Tsuyoshi Ito's point that the symmetries of the permanent seem not to help compute it efficiently: although the permanent is also characterized by its symmetries, its symmetry group is much smaller than that of the determinant.)

You can find a write-up of this - where the symmetries of the determinant are used to do Gaussian elimination, along the way proving that the determinant is characterized by its symmetries - in Proposition 3.4.3 of my thesis (shameless self plug - but also, I've never seen it phrased quite this way before and written in full detail, as the OP was asking for, though I'm sure it's been done; I'd be happy if someone had other references).

As to the idea that symmetry always leads to complexity reduction (or not), in addition to things already in the comments, see this question and its answers.

An interesting point is that in Valiant's first papers on what is now known as Valiant's version of algebraic complexity theory, he was trying to make the point that one reason the determinant is important computationally is because roughly all the (then) known efficient algorithms could be reduced to linear algebra and thence to the computation of the determinant, e.g. the FKT algorithm for counting matchings in planar graphs. This is of course an exaggeration, but continues to be borne out by research into holographic algorithms, which often reduce to computing the Pfaffian (a close relative of the determinant). Surely Valiant knew this was an exaggeration, but here's the exact quote just to make sure I'm not misrepresenting (L. Valiant. Completeness classes in algebra. ACM STOC 1979):

  Our main conclusions can be summarized roughly as follows:

  (a) Linear algebra offers essentially the only fast technique for computing multivariate polynomials of moderate degree

  (b) ...


Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory I was reading the GCT IV paper (http://arxiv.org/pdf/cs/0703110v4.pdf) and while the representation theory is clear enough (by which I do not mean to say 'easy'!) the relation to complexity theory as stated in the introduction confuses me.

I quote:

  The flip suggests that separating the classes P and NP will require solving difficult positivity problems in algebraic geometry and representation theory. A central positivity problem arising here is the following
  fundamental problem in the representation theory of the symmetric group.

  Let $S_r$ denote the symmetric group on $r$ letters and let $M_\nu$ denote the $S_r$-irreducible corresponding to the partition $\nu$. Given three partitions λ, µ, ν of r, the Kronecker coefficient $g_{\lambda \mu \nu}$ is defined to be the multiplicity of $M_\nu$ in the tensor product $M_\lambda \otimes M_\mu$. (...)

  Problem 1.1 (Kronecker problem). Find a positive combinatorial formula for the Kronecker coefficients $g_{\lambda \mu \nu}$.

  There are two precise related problems in complexity theory that arise in the flip: (1) find a (positive) #P formula for Kronecker coefficients, and harder, (2) find a polynomial time algorithm to determine whether a Kronecker coefficient is zero.

My questions are:

A) When they say polynomial time in question (2), what is the input size here? I found it easy to find a $O(d^3)$ algorithm where $d$ is the product of the dimensions of the vector spaces $M_\lambda, M_\mu, M_\nu$, so apparently they are thinking of something smaller than that. But what? The number $r$? How do we know that the dimensions are not polynomial in $r$? (It seems to me they are polynomial in $r$ but with an exponent that depends on the number of elements in the partition, so maybe that doesn't count as truly polynomial?)

B) How can question (2) be harder than question (1) when, obviously, any solution to question (1) gives you a solution to question (2). (At least I find it hard to imagine a world where an algorithm to compute a number doesn't give you an algortithm to tell if that number is zero.) The $P$ in $\#P$ also means 'polynomial time', right?

It looks like I am missing something really obvious here but what?

A) The input here is the triple of partitions $(\lambda, \mu, \nu)$, represented as sequences of numbers in binary. The dimension of the irreducible representation $M_{\lambda}$ can actually be exponential in $r$, take for example the hook partition $n + 1, 1, 1, \dots, 1 \vdash 2n + 1$. Using the hook formula for the dimension we get $\frac {(2n)!}{(n !)^2}$.

B) The $P$ in $\# P$ means polynomial time, but the $\#$ in $\#P$ means "count computation paths of a nondeterministic machine". An example of $\#P$ problem is $\#SAT$ (count the number of satisfying assignments for a given formula), and the corresponding decision problem is $SAT$, which is probably not in $P$.


Tree decomposition for planar graphs First asked on math.SE with no replies.

Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition?
What is the optimal tree decomposition of a $d$-by-$d$ square grid? Not completely sure how to define "optimal", but it should distinguish between decomposition with one large bag and decomposition with many large bags.

For the first question, it is open whether finding a tree decomposition for planar graphs can be done in polynomial time. The best approximation algorithm may be the RatCatcher algorithm by Seymour and Thomas, which computes the branchwidth of the planar graph, so it has a 1.5 approximation ratio by the relation between branchwidth and treewidth.

For the second one, we have the following theorem about the treewidth of $k \times k$ grids:

  Theorem. A $k \times k$ grid has treewidth $k$.

And the bags can be taken with size $k+1$, with a total $k(k-1)$ bags. I'm not sure if this is what you want, so feel free to do it if you modify the definition of "optimal".


Is conversion of PRAM to parameter number of processors trivial In section 2 of chapter 4 of Kumar the idea of scaling down is discussed.
It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just "shifting" it from the  number of processors to time.

Two things are on my mind with respect to this question.

I'm sure it is interesting to come up with efficient schemes for such conversion for dedicated hardware solutions (say , given the architecture of CUDA , one can implement efficient algorithms based on the size of the different cache levels etc.)
Is it interesting from the theory point of view? Can I say something about it without relating to a particular hardware solution? (Say , general schemes for work efficient preserving conversions)
I'm starting to see some possible connections to parameterized complexity. Is there any known work on the area? So far , Iv'e seen two popular papers and that

Any leads?

here are my answers to your questions.

1) In general, you can not come up with efficient schemes for scaling down the number of processor from $n$ to $p < n$. Why ? Because, even without taking into account additional issues such as caches etc, the problem is strictly related to how you map tasks to processors, which is known to be an NP-complete problem. In particular, this is almost always application dependent, so you have to carefully evaluate this each time you want to scale down your parallel algorithm. The good news here is that, starting from a work-efficient algorithm you can obtain a scaled-down work-efficient algorithm, thus preserving its efficiency.

2) To the best of my knowledge there are no strong connections with parameterized complexity, at least I am not aware of any significant published paper discussing this relation. I may be wrong of course.


What is this variant of set cover problem known as? Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$.

An incremental covering sequence is a sequence of subsets in ${\cal F}$, say, ${\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\}$, that satisfies

1) $\forall E\in {\cal A}, E\in {\cal F}$,

2) every newcomer has new contribution, i.e., $\forall i>1$, $\bigcup_{j=1}^{i-1}E_i \subsetneq \bigcup_{j=1}^{i}E_i$;

The problem is to find an incremental covering sequence of maximum length (i.e., with maximum $|{\cal A}|$). Note that a maximum length sequence must eventually cover $U$, i.e., $\bigcup_{E\in {\cal A}}E=U$.

I have attempted to find an algorithm or an approximate algorithm to find the longest incremental covering sequence. I was just wondering what this variant of set cover problem known as. Thank you!

Here I show that the problem is NP-complete.

We convert a CNF to an instance of your problem as follows.
Suppose that the variables of the CNF are $n$ $x_i$'s and the clauses are $m$ $C_j$'s, where $n<m$.
Let $U=\cup_i (A_i\cup B_i\cup Z_i)$ where all sets in the union are completely disjoint.
In fact, $A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\}$ and $B_i=\{b_{i,j}\mid x_i\in C_j\}\cup\{b_{i,0}\}$, while $Z_i$ is any set of cardinality $k=2n+1$.
Also denote $Z=\cup_i Z_i$ and fix for every $Z_i$ an increasing family of length $k$ inside it, denoted by $Z_{i,l}$ for $l=1..k$.
For every variable $x_i$, we add $2k$ sets to $\mathcal F$, every set of the form $A_i \cup Z_{i,l}$ and $B_i \cup Z_{i,l}$.
For every clause $C_j$, we add one set to $\mathcal F$, which contains $Z$, and for every $x_i\in C_j$ element $\{a_{i,j}\}$ and for every $\bar x_i\in C_j$ element $\{b_{i,j}\}$.

Suppose that the formula is satisfiable and fix a satisfying assignment.
Then pick the $k$ sets of the form $A_i \cup Z_{i,l}$ or $B_i \cup Z_{i,l}$, depending on whether $x_i$ is true or not.
These are $nk$ incremental sets.
Now add the $m$ sets corresponding to the clauses.
These also keep increasing the size, as the clauses are satisfiable.
Finally, we can even add $k$ more sets (one for each variable) to make the sequence cover $U$.

Now suppose that $n(k+1)+m$ sets are put in an incremental sequence.
Notice that at most $k+1$ sets corresponding to $x_i$ can be selected for each $x_i$.
Thus, if there are no clause sets in the incremental sequence, at most $n(k+1)$ can be selected, which is too few.
Notice that as soon as a clause set is selected, we can pick at most two sets corresponding to each $x_i$, a total of at most $2n$ sets.
Therefore, we have to pick at least $n(k-1)$ variable sets before any clause set is picked.
But as we can pick at most $k+1$ for each $x_i$, this means that for each we have picked at least $1$, as $k=2n+1$.
This determines the "value" of the variable, thus we can pick only "true" clauses.

Update: Changed value of $k$ from $n$ to $2n+1$ as pointed out by Marzio.


Calculate Huffman code length having probability? Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will the longest encoded symbol have? How many encoded symbols will have same length?

I try to imagine a Huffman tree for it, but it does not appear to make much sense, as trees for Huffman encoding aren't always balanced (so I can't use tree's height to calculate this I guess). I know that at least two least-probable symbols will have longest codings, but how to relate element's probability with its Huffman code length? Or maybe there is some other way to calculate it?

The intended answer is probably that the length of the longest codeword is approximately $$-\log_2 10^{-6} = 20.$$ But this is wrong. The information given doesn't come close to specifying the length of the longest codeword. Even the entire probability distribution doesn't specify the length of the longest codeword.

One can see this by constructing a Huffman tree with a probability distribution with probabilities proportional to the Fibonacci numbers $$\{1,1,1,2,3,5,8,13, \ldots, F_n\}.$$ (The third 1 is deliberate.) When combining these into a Huffman tree, you are faced with lots of choices. One set of choices yields a tree of depth approximately $n$; another, approximately $n/2$.

For the probabilities $$\frac{1}{34}, \frac{1}{34}, \frac{1}{34}, \frac{2}{34}, \frac{3}{34}, \frac{5}{34}, \frac{8}{34}, \frac{13}{34},$$
we have the large-depth Huffman tree where the longest codeword has length 7:

and the small-depth Huffman tree where the longest codeword has length 4:

Both of these trees have $43/17$ for the expected length of a codeword, which is optimal.

It is possible to show that the length of the longest codeword is no more than a factor of $\log_\phi(2)\approx 1.44$ larger than $-\log_2 p$, where $\phi$ is the golden ratio; the worst case example is the large-depth one above, using Fibonacci numbers. So for your example the length is at most $28$. And because there are 1024 codewords, the length of the longest one has to be at least $\log_2 1024 = 10$.  So the correct answer is the length of the longest codeword is between $10$ and $28$. But unless the OP changed the wording of the question, these bounds don't seem to be what the problem was asking for.


Complexity classes for proofs of knowledge Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge.  Classes like SZK and NISZK are extremely natural from a complexity standpoint, even if we forgot entirely about zero knowledge and just defined them in terms of their complete promise problems.  By contrast, on googling 'proofs of knowledge,' I was surprised not to find any papers or lecture notes discussing this lovely concept in terms of complexity classes.

To give some examples: what can one say about the subclass of SZK∩MA∩coMA consisting of all languages L that admit statistical zero-knowledge proofs for x∈L or x∉L, that are also proofs of knowledge of a witness proving x∈L or x∉L?  Certainly this class contains things like discrete log, but we couldn't prove that it contains graph isomorphism without putting GI in coMA.  Does the class encompass all of SZK∩MA∩coMA?  One could also ask: if one-way functions exist, then does every language L∈MA∩coMA admit a computational zero-knowledge proof, that's also a proof of knowledge of a witness proving x∈L or x∉L?  (My apologies if one or both of these have trivial answers---I'm just trying to illustrate the sort of thing one could ask, once one decided to look at PoK in complexity-theoretic terms.)

This is not an actual answer; I'm just sharing some results (which do not fit in one comment).

Goldreich, Micali and Wigderson (J. ACM, 1991) proved that every language in NP has a zero-knowledge proof of language membership (assuming OWFs exist). To this end, their presented a ZK proof for graph 3-colorability. Later, Bellare and Goldreich (CRYPTO '92) proved that this ZK proof is also a ZK proof of knowledge (PoK). Using Levin reductions (see footnote 12 of the former paper), Every language in NP has a ZK PoK (assuming OWFs exist).
Itoh and Sakurai (ASIACRYPT '91) have a paper on complexity-theoretic results regarding relations having constant-round ZK PoK.
This is a seemingly unrelated result, though I can't help noticing some similarities. I somehow feel (not anything formal) that proof of membership vs. proof of knowledge is similar to decision vs. search. Perhaps in this sense, one can also cite the work of Bellare and Goldwasser (J. Computing, 1994), where they (conditionally) prove that not all languages in NP have a reduction from search to decision.

Some open problems (perhaps solved, but not that I know of) regarding complexity-theoretic aspects of PoKs:

Various efficiency measures for ZK PoKs of a specific relation with certain complexity (e.g., a relation in AM):

Communication complexity of the proof
Computational complexity of the parties
Knowledge tightness (i.e., the ratio between the (expected) running time of the simulator and the running time of the verifier in the real interaction)

Complexity of relations admitting ZK PoK with certain limitations, say limited round complexities (Itoh and Sakurai only consider constant-round ZK PoK). Another example is when the prover is polynomial time: He cannot use the reduction to 3-colorability, as he cannot solve NP-complete relations. All NP-complete problems have a Cook reduction from search to decision. Yet, by Bellare-Goldwasser result cited above, such reductions do not necessarily exist for all NP languages/relations.
Other interesting results regarding PoKs which are not necessarily ZK, but whose knowledge complexity is otherwise limited. See Goldreich and Petrank (Comput. complex., 1999).

Before concluding, allow me to mention that there are actually several definitions for PoKs, some of which are cited below:

1) Early attempts: Feige, Fiat and Shamir (J. Cryptology, 1988), Tompa and Woll (FOCS 1987), and Feige and Shamir (STOC 1990).

2) De facto standard: Bellare and Goldreich (CRYPTO '92). This paper surveys the early attempts at defining PoKs, observes their shortcomings, and suggests a new definition which can be considered as "the" definition of PoK. This definition has a black-box nature (the knowledge extractor has black-box access to the cheating prover).

3) Conservative PoKs: Defined by Halevi and Micali (ePrint Archive: Report 1998/015), this definition augments the previous definition to guarantee prover feasibility. It also gives a definition for the knowledge of a single prover, which is good when answering the question "what does it mean to say that P knows something?"

4) Arguments of Knowledge with Non Black-Box Extraction: As mentioned above, the standard definition of PoKs is black box, which makes it impossible to have resettable zero-knowledge proofs (or arguments) of knowledge for non-trivial languages. Barak et al. (FOCS 2001) provide a non-black-box definition, which is based on (but differs from) the definition of Feige and Shamir (STOC 1990) cited above.


What are the consequences of $L = \oplus L$? Shiva Kintali has just announced a (cool!) result that graph isomorphism for bounded treewidth graphs of width $\geq 4$ is $\oplus L$-hard.  Informally, my question is, "How hard is that?"

We know that nonuniformly $NL \subseteq \oplus L$, see the answers to this question.  We also know that it is unlikely that $\oplus L = P$, see the answers to this question.  How surprising would it be if $L=\oplus L$?  I have heard many people say that $L=NL$ would not be shocking the way $P=NP$ would.

  What are the consequences of $L=\oplus L$?

Definition: $\oplus L$ is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero number of acceptance paths), and which is further restricted to work in logarithmic space.

Wigderson proved that $NL/poly \subseteq \oplus L/poly$. By standard arguments, $L = \oplus L$ would imply $L/poly = NL/poly$. (Take a machine $M$ in $NL/poly$. It has an equivalent machine $M'$ in $\oplus L/poly$. Take the $\oplus L$ language of instance-advice pairs $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$. If this language is in $L$, then by hardcoding the appropriate advice $a$ we get an $L/poly$ machine equivalent to $M$.)

I think that would be surprising: nondeterministic branching programs would be equivalent to deterministic branching programs (up to polynomial factors).


Maximum-minimum satisfiability In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\in\{1,\ldots,n\}$ such that, for some assignment, some $k$ clauses $c_{i1},\ldots,c_{ik}$ are true.

In MAX-MIN-SAT, given two different formulas, we want to maximize the minimum number of satisfied clauses in both.
I.e., given $\phi_a = a_1 \cap \cdots \cap a_n$ and $\phi_b = b_1 \cap \cdots \cap b_n$,  where each $a_i$ and each $b_i$ is a disjunction, find the largest $k$ such that, for some assignment, some $k$ clauses $a_{i1},\ldots,a_{ik}$ and some $k$ clauses $b_{j1},\ldots,b_{jk}$ are true.

To illustrate the difference between the problems, suppose we have two assignments: one assignment satisfies 10 clauses in $\phi_a$ and 1 clause in $\phi_b$, while another assignment satisfies 5 clauses in $\phi_a$ and 4 clauses in $\phi_b$. Then, MAX-SAT (on $\phi_a \cap \phi_b$) would prefer the first assignment since it satisfies $11>9$ clauses overall, while MAX-MIN-SAT would prefer the second assignment since it satisfies at least $4>1$ clauses in both formulas.

This problem is obviously NP-hard, so I am looking for reasonable approximations.

As a first approximation, suppose each formula is a conjunction of $n$ clauses, and each clause is a disjunction of $l$ variables. Suppose we set each variable randomly. Then, each clause is unsatisfied with probability $2^{-l}$. So the expected number of unsatisfied clauses in each formula is $2^{-l}n$. So the expected number of unsatisfied clauses in both formulas is $2^{1-l}n$. So there exists an assignment in which the total number of unsatisfied clauses is at most $2^{1-l}n$. In that assignment, in each formula, at least  $(1-2^{1-l})n$ clauses are satisfied.
So we have a constant-factor $(1-2^{1-l})$ approximation to MAX MIN SAT.

Is there a better approximation?

Posted some weeks ago in cs.SE, with no replies

Some such problems are considered here
https://eccc.weizmann.ac.il/report/2014/098/
under the name "simultaneous approximation".

See Theorems 1.1 and 1.3.


Doubt in John Langford's "Tutorial on Practical Prediction Theory for Classiﬁcation" paper I am reading John Langford's paper on practical prediction theory (link), and I have the following doubt with definition of Binomial Tail inversion.

The paper says that binomial tail inversion is the largest true error such that the probability of having k or more errors is at least $\delta$.

But the expression used in the paper reads "largest true error such that probability of having k or less errors is at least $\delta$"

Can anyone help?

I think this is a typo.

In the Definition 2.1 and Definition 2.2, the estimation of $c_D$ is done by empirical summation of $\mathbf{1}(c(x_i) = y_i)$.

Later in the Definition 3.1 it used the following notation :
$$
... = \Pr_{...} \left( \sum_i Z_i < k \right) = ...
$$
In this notation $Z_i=1$ corresponds to correct decisions or $c(x_i) = y_i$, and $Z_i=0$ corresponds to the mistakes or $c(x_i) \neq y_i$. I suppose that in this binomial representation $Z_i = 1$ (correct decision) corresponds to heads" (And similarly $Z_i = 0$ (wrong decision) corresponds totail").

That said, the right sentence seems to be "... having k or less errors is at least $\delta$"


Prove proof irrelevance in Coq? Is there a way to prove the following theorem in Coq?

Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2.

EDIT: An attempt to give a brief explanation for "what proof irrelevance is" (correct me someone if I am wrong or inaccurate)

The basic idea is that in the proposition world (or the Prop sort in Coq), what you (and you should) really care about is the provability of a proposition, not the proofs of it, there may be many (or none). In case you have multiple proofs, from the provability point of view, they are equal in the sense that they prove the same proposition. So their distinction is just irrelevant. This differs from the computational point of view where you really care about the distinction of two terms, e.g., basically, you don't want the two inhabitants of the bool type (or Set in Coq's words), namely true and false to be equal. But if you put them in Prop, they are treated equal.

Proof irrelevance in general is not implied by the theory behind Coq. Even proof irrelevance for equality is not implied; it is equivalent to Streicher's axiom K. Both can be added as axioms.

There are developments where it's useful to reason about proof objects, and proof irrelevance makes this nigh-impossible. Arguably these developments should have all the objects whose structure matters recast in Set, but with the basic Coq theory the possibility is there.

There is an important subcase of proof irrelevance that always holds. Streicher's axiom K always holds on decidable domains, i.e. equality proofs on decidable sets are unique. The general proof is in the Eqdep_dec module in the Coq standard library. Here's your theorem as a corollary (my proof here is not necessarily the most elegant):

Require Bool.
Require Eqdep_dec.
Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2.
Proof.
  intros; apply Eqdep_dec.eq_proofs_unicity; intros.
  destruct (Bool.bool_dec x y); tauto.
Qed.

For this special case, here's a direct proof (inspired by the general proof in Eqdep_dec.v). First, define we define a canonical proof of true=b (as usual in Coq, it's easier to have the constant first). Then we show that any proof of true=b has to be refl_equal true.

Let nu b (p:true = b) : true = b :=
  match Bool.bool_dec true b with
    | left eqxy => eqxy
    | right neqxy => False_ind _ (neqxy p)
  end.
Lemma bool_pcanonical : forall (b : bool) (p : true = b), p = nu b p.
Proof.
  intros. case p. destruct b.
  unfold nu; simpl. reflexivity.
  discriminate p.
Qed.

If you add classical logic to Coq, you get proof irrelevance. Intuitively speaking, classical logic gives you a decision oracle for propositions, and that's good enough for axiom K. There is a proof in the Coq standard library module Classical_Prop.


Given the following set of LISP primitives, is it possible to extend the eval function to evaluate defmacro? In this paper McCarthy sets out the following primitives: QUOTE, CAR, CDR, CONS, EQUAL, ATOM, COND, LAMBDA and LABEL.

He then sets up the following abbreviations: T, NIL, DEFUN, NULL, CADR, LIST, AND, ALT, and SUBST.

He rounds it up with an incredible definition of the EVAL function used in the reader.

Given the above set of LISP primitives, is it possible to extend the EVAL function to evaluate defmacro?

Yes, in fact it's quite similar to evaluating DEFUN. Of course, in the paper EVAL has no rule for evaluating DEFUN, since it's treated as an abbreviation. From the definition of DEFMACRO in emacs LISP (link):

Special Form: defmacro name argument-list body-forms...
defmacro defines the symbol name as a macro that looks like this:
(macro lambda argument-list . body-forms)

It's easier if we ignore the name of the macro and treat that as an abbreviation. Then we have simply to create the list (macro lambda argument-list . body-forms) and set name to be shorthand for that list, the same way a (defun name (arguments) (body)) sets name as a shorthand for (lambda (arguments) (body)). As for evaluating a macro, that is also easy --- just pass the function inside the macro your arguments, but WITHOUT evaluating them first.


Do bounded-visit nondeterministic linear bounded automata recognize only regular languages? Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine where the input comes "padded" with endmarkers on both ends which can never be overwritten, and so that the head can never move out of the input region, "outside" the endmarkers.

The LBA is bounded-visit if there is a number $k$ such that all runs on all inputs terminate and visit every cell of the tape at most $k$ times.

Does such a machine recognize only regular languages? Hennie's result seems to say this only for deterministic machines, if I'm reading it right. Does the result hold for nondeterministic machines too? If yes, a reference would be appreciated.

A bit overkill, but:
this paper shows (among other nice things) that non-deterministic Hennie transducers realize exactly the class of non-deterministic MSO-definable transductions. The latter have regular domains.


Is state splitting the LR equivalent of LL nonterminal replication The grammar classes SLR and strong LL are similar in that they both use FOLLOW sets to resolve conflicts. For still unresolved conflicts, state splitting always works for SLR grammars, if the grammar is LR. Similarly, Aho/Ullman have shown that nonterminal replication can make any LL grammar strong. If the form of the LL grammar is EBNF, the replication is intrinsic if identical EBNF forms are implemented as different nonterminals at each occurrence in the grammar.

I wonder if the nonterminal replication provided by an EBNF formed SLR grammar would provide something equivalent to state splitting such that the grammar would have LR recognition power.

More specifically, for a fixed k, given any LR(k) grammar, if that grammar contains at most one occurrence of each nullable nonterminal on the right hand sides of all productions, must that grammar also be SLR(k)? What I am looking for is a counter example grammar.

It is indeed well-known that LR($k$) languages for $k>0$ coincide with SLR($1$) languages, see e.g. M. Dennis Mickunas, Ronald L. Lancaster, and Victor B. Schneider, Transforming LR($k$) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars, J. ACM 23(3):511--533, 1976, doi: 10.1145/321958.321972; it's not clear to me what EBNF syntax has to do with it: could you be more specific?

Edit: in answer to the more specific question regarding nullable nonterminals and LR($k$) vs. SLR($k$), the grammar with rules
$$S\to aAa\mid bAb\mid aBb\mid bBa, A\to a, B\to a$$
is LR(1) but neither SLR(1) nor LALR(1) and does not have any nullable nonterminal.

Another issue is that there is no "perfect" definition of LR($k$) for EBNF syntax---unless you convert to BNF in some specific way and ask the resulting grammar to be LR($k$); see Heilbrunner, Definition of ELR($k$) and ELL($k$) Grammars, Acta Inf. 11(2):169--176, 1979, doi: 10.1007/BF00264023.  The issue is with the reduction operation: how much of the stack should be reduced when reducing, say, $A\to a^\ast$?  Answering this question might require inspecting the stack contents, or adding special stack markers, or $\dots$, and is likely to restrict the class of accepted grammars below ELR($k$).

Finally, I do not know about SLR($k$) techniques for EBNF grammars; a survey on the subject of parsing for EBNF was recently written by Hemerik, Towards a Taxonomy for ECFG and RRPG Parsing, LATA'09, LNCS 5457:410--421, 2009, doi: 10.1007/978-3-642-00982-2_35.


Types which correspond to sets of cardinality of continuum Are types which correspond to sets with cardinality of continuum possible in MLTT (or in any other constructive theory)?

On the first sight, they aren't, since elements of types are terms and we have only countable number of terms.

Does it mean that sets with cardinality of a continuum really doesn't exist and just a nice abstraction which simplifies mathematics a lot?

You must be careful here. You are using set-theoretic concepts (cardinal, continuum) outside set theory. There is potential for confusion.

Your question can be understood in several ways.

Maybe you are asking whether there can be uncountably many terms of a given type. The answer is: obviously not since there are only countably many finite strings, and eact term is a string (or a finite tree if we think of abstract syntax). You might be asking this question because you claim that "the elements of types are terms". This, in my opinion, is a very damaging view of types. It is like saying that the elements of $\mathbb{R}$ are only certain expressions which denote real numbers.

Another possibility is that you are asking whether there is a model of type theory in which some of the types are interpreted as uncountable sets. The answer is yes, for example the set-theoretic type model in which types are sets. In this case $\mathtt{nat} \to \mathtt{bool}$ has the power of continuum because it is the sets of all infinite boolean sequences.

You could be asking whether inside type theory we can prove that there are types of the cardinality of continuum. In this case the question does not make sense because the notion "cardinality of continuum" is something that only make sense in set theory. You need to rephrase it so that it makes sense in type theory, but there are complications. Cardinality just does not behave the same way in type theory as it does in set theory. For example, you cannot show that cardinals (whatever you think they are) are linearly ordered. But we can still define special cases. Thus we can define the notion of an uncountable type:

Definition uncountable (A : Type) :=
   forall f : nat -> A, exists x : A, forall n : nat, ~ (f n = x).

In words, $A$ is uncountable if for every sequence $f : \mathbb{N} \to A$ there exists $x : A$ such that $x$ is not in the image of $f$. The Baire space $\mathbb{N}^\mathbb{N}$ is uncountable:

Theorem baire_uncountable : uncountable (nat -> nat).
Proof.
  intro f.
  exists (fun n => S (f n n)).
  intro n.
  intro E.
  absurd (f n n = S (f n n)).
  - auto.
  - pattern (f n) at 1.
    rewrite E.
    reflexivity.
Qed.

So, classically this would mean that the cardinality of the Baire space is larger than $\aleph_0$, but as I said, cardinalities inside type theory, and in constructive mathematics in general, behave a lot less nicely than in set theory.


Downward self-reducibility of factorization Is integer factorization downward self-reducible? Is anything known about this?

The state of the art here is: We can decide primality in polynomial time, but the fastest, general-purpose algorithm to $\underline{\rm find}$ the factors of an n-bit composite integer takes time $\approx 2^{n^{1/3}\log^{2/3}n}$.

More to your question, a primality test is the same thing as a compositeness test. Therefore, we can easily implement the 'primality decision oracle' required by any (supposed) Cook reduction from factoring to itself.

The reason, then, that factoring is commonly presented as an example of a problem that is "unlikely to be downward self-reducible" is because of the possibility that such a reduction identifies prime factors of the original integer. This can be phrased in many ways, but as Joshua points out in comments above, a good example is a reduction that takes $(n, k)$ (is there a factor of $n$ that is at most $k$?) to $(m, k')$ where $m|n$.

A reduction of this particular type would have the consequence of breaking the plethora of cryptosystems based on the hardness of factoring (without the need for a quantum computer), e.g. RSA.


Partitioning graphs while minimizing inter-partition edges I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been partitioned into 4 "clusters":

What I wanted originally was an algorithm that could create partitions of approximately k triangles (there could be some error as long it wasn't too large), and I managed to figure out a $O(k^2p^2(v+e))$ algorithm (where p is the total number of partitions) that could find such a partitioning. I then realized that having large numbers of inter-partition edges were detrimental for the application I needed this algorithm for.

Ideally, I'd like an algorithm that can keep each partition within some range of $k$, ideally have it be a constant factor like 2. Also, I'd like to be able to make the number of inter-edges have an upper bound that is "low".

Additionally, another problem I have is if I have a partition that has these properties, and I modify the graph by doing one of the following:

Adding a set of edges connecting to existing vertices
Adding a vertex and a set of edges connecting to the added vertex
Removing a set of edges
Removing a vertex and all edges that connect to this vertex

I want to be able to repartition the graph and still have each partition with size $k$ and number of cut edges minimized. (This is the solution I'm putting up a bounty for). This means that using this algorithm, we can construct any partition by starting with an empty graph and adding vertices and edges one by one and repartitioning.

Here's some additional constraints to the problem:

The graph is planar
Each "triangle" is a vertex that has undirected edges to triangles it shares an edge with
From the above statement, it is obvious that each vertex in this graph has degree at most 3
The graph is connected
Each subgraph from the partition is connected
Each subgraph has approximately k vertices
There are at most $\sqrt n$ inter-partition edges (edges that contain a vertices from different partitions). If you can find a similar bound for inter-partition edges like $2\sqrt n$ or $O(\log n)$ then that could work too. I'm not entirely sure the upper bound for inter-partition edges can be less than $O(n)$ so if you can prove that its impossible to do better, that is satisfying as well.

I'm at a point where I'm stuck, so any help with this problem would be lovely. If you can flat out solve this problem, you're the bees knees. Otherwise, if you know of any papers or textbooks or algorithms you could point me to, I'd appreciate it very much.

Let me know if I need to clarify anything!

EDIT: Here are some additional constraints if it makes the problem easier.

We are dealing with constrained delaunay triangulations
Constraints will NEVER be a single vertex
The graph created from the triangulation is constructed as follows: each triangle is represented as a vertex. Each edge in the graph corresponds to an unconstrained edge in the triangulation. This means that a constrained edge between two triangles will not show up in the graph representation of the triangulation.

Another thing I realized is that we may need to modify $k$ to grow as $n$ grows, otherwise there can be no sub $O(n)$ guarantees on the number of inter-partition edges.

Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem.

Satish Rao. Finding near optimal separators in planar graphs. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987.

Satish Rao. Faster algorithms for finding small edge cuts in planar graphs (extended abstract). In 24th ACM Symposium on Theory of Computing (STOC), pages 229-240, 1992.

Horst D. Simon and Shang-Hua Teng. How Good is Recursive Bisection?
In  SIAM Journal on Scientific Computing, Volume 18, Issue 5, pages 1436-1445, 1997.


What kind of reinforcement learning is MENACE? The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description:

  ...an interesting machine for playing tic-tac-toe. It was made
  entirely out of matchboxes, each one of which had a tic tac toe
  position on the top. Inside was a collection of colored beads. Each
  color specified a possible legal move for the position on top. The
  idea was that you’d play a game by drawing these beads from the
  appropriate box, and making the appropriate move. At the end of the
  game, you’d remove the bead from the last box that sent you along the
  losing path. Eventually, all the losing moves get removed, and the
  machine plays perfect tic-tac-toe. Gardner showed how this same idea
  could be used to create a matchbox computer to play hexapawn, a simple
  game played with six pawns on a 3×3 board.

My question is: what kind of algorithm is this, in modern parlance? Is it policy iteration? Q-learning? Or sooething else? I am a bit new to the subject and can't figure it out for sure.

I found this question because I was searching for an answer to it myself...so take my answer on this with a grain of salt...but I believe that it's similar to policy gradients. In policy gradients you increase the probability of taking actions when you see a large reward which followed those actions...that seems to be the idea behind MENACE as well.


Relationship between SPACE(n) and E Is it known whether SPACE(n) (the class of languages recognized by deterministic TMs with linear space) is a proper subset of E (the class of languages recognized by deterministic TMs in time 2^O(n))?

If in fact DSPACE(n) = E, then a padding argument would translate this to PSPACE=EXP.
Similarly, if DSPACE(n) $\neq$ E then a padding argument would translate this to L $\neq$ P.


Drawing graphs with few "sharp" vertices? For a planar embedding of a planar graph on a plane with straight edges, define a vertex as a sharp vertex if the maximum angle between two consecutive edges around it is more than 180. Or in other words, if there exists a line passing through that vertex in the embedding such that all the edges incident on that vertex lie on one side of the line, then the vertex is "sharp" otherwise it's not. Also, let us worry only about vertices with degree at least 3.

I want to draw planar graphs with few sharp vertices. Has anyone studied such drawings before?

In particular, I want to draw planar graphs with max degree 3 such that the number of sharp vertices of degree 3 in the embedding is $O(\log n)$ and the coordinates of the vertices can be written down with a polynomial number of bits.

Here's what I can find after spending some time on Google Scholar:

My measure of sharpness of a vertex is related to an already studied concept called the Angular Resolution. From Wikipedia:

  The angular resolution of a drawing of a graph refers to the sharpest angle formed by any two edges that meet at a common vertex of the drawing.

Thus a planar drawing with angular resolution $\pi/2$ around degree 3 vertices will be good for my purpose.

For a vertex with degree $d$ in the drawing, the angular resolution around it can be at most $2\pi/d$.

The question of whether this is tight has been studied in the past, but I can only find asymptotic results. For example, Malitz and Papakostas prove that any planar graph with maximum degree $d$ can be drawn with an angular resolution of $\alpha^d$. But this result doesn't give good bounds for the case when $d=3$.

It is possible to construct 3-regular planar graphs with $\Theta(n)$ biconnected components (see e.g. fig.16 of this paper), each of which must contain at least one sharp vertex.

On the other hand, if you require higher levels of connectivity, you can avoid having many sharp vertices. In particular, if you have a 3-connected planar graph, it can be drawn (e.g. by using Steinitz' theorem to find a polyhedral representation and then forming a perspective projection) in such a way that all faces are convex, which causes only the outer face to be sharp. But every 3-connected planar graph can be embedded in such a way that the outer face has at most five vertices (the worst case being a dodecahedron) so you can draw every 3-connected planar graph (3-regular or not) with at most five sharp vertices.


Is compiler for dependent type much harder than an intepreter? I have been learning something about implementing dependent types, like this tutorial, but most of them is implementing interpreters. My question is, it seems that implementing a compiler for dependent type is much harder than a compiler, because you can really evaluate the the dependent type arguments for type checking.

So

Is my naive impression right?
If it is right, any example / resources about implementing a statically checked language supporting dependent type?

This is an interesting question! As Anthony's answer suggests, one can use the usual approaches to compiling a non-dependent functional language, provided you already have an interpreter to evaluate terms for type-checking.

This is the approach taken by Edwin Brady. Now this is conceptually simpler, but it does lose the speed advantages of compilation when performing type checking. This has been addressed in several manners.

First, one can implement a virtual machine which compiles terms to byte-code on the fly to perform the conversion check. This is the idea behind vm_compute implemented in Coq by Benjamin Gregoire. Apparently there is also this thesis by Dirk Kleeblatt on this exact subject, but down actual machine code rather than a virtual machine.

Second, one may generate code in a more conventional language which, upon execution, checks all the conversions necessary to type-check a dependently typed program. This means we can use Haskell, say, to type-check an Agda module. The code can be compiled and run, and if it accepts, then the code in the dependently-type language can be assumed to be well-typed (barring implementation and compiler errors). I've first heard this approach suggested by Mathieu Boesflug.

Finally, one may require that the terms appearing in types and the terms intended to be run be part of two distinct languages. If the terms appearing at the type level do not themselves have dependent types, then one may compile in two stages: first, compile the "type-level" code and then you can execute this when checking the types of the "term-level" code. I'm not aware of any system that proceeds in this manner, but it is potentially possible for many systems, like Microsoft's F$^*$ language which has distinct type-level and program-level terms.


Finding a "lowest" path in a graph I have an undirected graph $G = (E,V)$, $|V|=n$,
where each node $v_i$ has a natural number weight.
Think of these weights as heights $h_i$.
Given two nodes $s$ and $t$, I'd like to find a lowest simple path between $s$ and $t$,
a path whose average height is minimal among all simple paths.
If $\rho = (s{=}v_1, v_2, \ldots, v_{k-1}, v_k{=}t)$ is a path,
its average height is $(h_1 + \cdots + h_k)/k$.
The path $\rho$ must be simple, i.e., no vertex repeated.

I am not seeing an efficient algorithm. If it helps, assume $G$ is planar.

This problem is NP-complete, by reduction from Hamiltonian cycle in a graph G=(V,E). Every edge in E receives weight 0. If a vertex is traversed, there is a gadget that allows you to use an edge of weight 1. Now in order to maximize the average, you need as many weight-1 edges as possible.

Here are some details for the construction:

Consider an instance $(V',E')$ of directed Hamilton path that asks for a Hamilton path from vertex $x\in V'$ to vertex $y\in V'$.
We create the following instance of the lowest path problem in an undirected graph $G=(V,E)$ from it:

Every vertex $v\in V'$ is replaced by three new vertices $v_1,v_2,v_3$, together with the two edges $\{v_1,v_2\}$ and $\{v_2,v_3\}$.
For every arc $(v,u)\in E'$, we introduce the undirected edge $\{v_3,u_1\}$ in graph $G$.
All edges $\{v_2,v_3\}$ in $G$ with $v\ne x$ and $v\ne y$ have weight 1, and all the remaining edges have weight 0.
The starting point of the desired lowest path is vertex $x_2$, and the endpoint is vertex $y_2$.

Consider a path $P$ in $G$ from $x_2$ to $y_2$, and let $k$ denote the number of weight $1$ edges on $P$.Then $P$ must also contain (at least) $3k+4$ edges of weight $0$, so that the average weight is at most $k/(4k+4)$. This expression is at most $|V'|/(4|V'|+4)$. A Hamilton cycle in $G'$ translates into a path with average weight $|V'|/(4|V'|+4)$ in $G$.


Is a quadratic nondeterminism speed-up of deterministic computation plausible? This is a follow up to
nondeterministic speed-up of deterministic computation.

Is it plausible that nondeterminism (or more generally alternation)
would allow a general quadratic speed-up of deterministic computation?
Or are there any known implausible consequences for something like
 $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$?

Note that even a result along the lines of $\mathsf{DTime}(\tilde{O}(n^2)) \subseteq \mathsf{NTime}(n^{2-\epsilon})$ would violate NSETH as univariate polynomial identity testing (as defined in section 3.2) can be solved in $\tilde{O}(n^2)$ time deterministically, but there doesn't seem to be an obvious way to use nondeterminism to help prove identity.


Graph building with weighted nodes I have a set of nodes which can be connected together through arcs. Every node has an associated value, reflecting the "fitness" that this particular node has in the graph. I have to find the best graph connecting the vertices, defining best as the maximum value achievable by summing node fitness. I already have an algorithm for that, I'm only asking if this is a well-known problem or a more efficient algorithm than NP-hard does exist.

I am not sure I understand the problem correctly, but let me try a definition:
Given a graph and an integer k.
Find the subset $S$ of $k+1$ vertices with max sum of weights such that $S$ induces a connected graph (i.e. there is a tree with k edges spanning $S$).

This sounds to me like the Steiner tree problem
http://en.wikipedia.org/wiki/Steiner_tree_problem

The steiner tree problem gives as input a graph, a set of terminals and asks for a set of edges from the graph (i.e. a tree) that connects all terminals.
The goal is to minimize the sum of the edge weights.

Gary and Johnson showed this NP-complete, I believe even for all edge weights 1.

Give the terminals a high weight such that any solution would need to take all terminals.
The rest of the vertices gets weight 1. Since a tree always has 1 edge less than number of nodes the question is find a set of nodes such that all terminals will be connected.

Hence your problem is NP-complete.
Much work has been done on approximation, there has been comparison of different implementations. I seem to remember there was a DIMACS challenge on the Steiner tree problem.


"right" uniformity condition for Nick's Class DLOGTIME is defined at http://en.wikipedia.org/wiki/DLOGTIME

$\operatorname{L}$ is defined at http://en.wikipedia.org/wiki/L_%28complexity%29

$\operatorname{NC}$ and $\operatorname{NC}^n$ are defined at http://en.wikipedia.org/wiki/NC_%28complexity%29

DLOGTIME seems to be the smallest that might work.

I've read in various places that $\, \operatorname{L} \subseteq \operatorname{NC}^2 \,$, $\,$ although every place I've

found that results which states a uniformity condition uses $\operatorname{L}$-uniformity.

Is there any deterministic class $X$ such that $\, \operatorname{L} \subseteq \operatorname{NC} \,$ is known with $X$-uniform $\operatorname{NC}$, and

1. $\;$ ... $\; X\subset \operatorname{L} \;$ is known to hold?

2. $\;$ ... $\; X\subseteq \operatorname{L} \;$ is known to hold and $\, X = \operatorname{L} \,$ is not known to hold?

(1, or to a much lesser extent 2, would seem to imply that $\operatorname{L}$-uniformity is the correct condition)

You can use $\mathsf{DLogTime}$ for uniformity of $\mathsf{NC}$ and $\mathsf{NC^2}$. There is no problem and the classes uniform $\mathsf{NC^k}$ remain the same and equal to $\mathsf{ATimeSpace}(O(\lg^k n),O(\lg n))$ (for $k\geq1$).

Generally, the only case that we need to be more careful is $\mathsf{NC^1}$ case where one should be careful about what needs to be in decidable in $\mathsf{DLogTime}$. If you use extended connection language description of circuits then everything works even in $\mathsf{NC^1}$ case.

For more on uniformity see:

Walter L. Ruzzo, "On Uniform Circuit Complexity", Journal of Computer and System Sciences, vol. 22 (1981), pp. 365–383.


Is "Experimental Complexity Theory" being used to solve open problems? Scott Aaronson proposed an interesting challange: can we use supercomputers today to help solve CS problems in the same way that physicists use large particle colliders?

  More concretely, my proposal is to
  devote some of the world’s computing
  power to an all-out attempt to answer
  questions like the following: does
  computing the permanent of a 4-by-4
  matrix require more arithmetic
  operations than computing its
  determinant?

He concludes that this would require ~$10^{123}$ floating point operations, which is beyond our current means.  The slides are available and are also worth reading.

Is there any precedence for solving open TCS problems through brute force experimentation?

In "Finding Efficient Circuits Using SAT-solvers", Kojevnikov, Kulikov, and Yaroslavtsev have used SAT solvers to find better circuits for computing $MOD_k$ function.

I have used computers to find proofs of time-space lower bounds, as described here. But that was only feasible because I was working with an extremely restrictive proof system.

Maverick Woo and I have been working for some time to find the "right" domain for proving circuit upper/lower bounds using computers. We had hoped that we may resolve $CC^0$ vs $ACC^0$ (or a very weak version of it) using SAT solvers, but this is looking more and more unlikely. (I hope Maverick doesn't mind me saying this...)

The first generic problem with using brute-force search to prove nontrivial lower bounds is that it just takes too damn long, even on a very fast computer. The alternative is to try to use SAT solvers, QBF solvers, or other sophisticated optimization tools, but they do not seem to be enough to offset the enormity of the search space. Circuit synthesis problems are among the hardest practical instances one can come by.

The second generic problem is that the "proof" of the resulting lower bound (obtained by running brute-force search and finding nothing) would be insanely long and apparently yield no insight (other than the fact that the lower bound holds). So a big challenge to "experimental complexity theory" is to find interesting lower bound questions for which the eventual "proof" of the lower bound is short enough to be verifiable, and interesting enough to lead to further insights.


Does the following type of hitting problem have a name? Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the cardinality of the union $B_1\cup B_2\cup\dots\cup B_m$ is minimized. In other words, I want to hit each of the families $\mathcal F_i$ using as few elements of the ground set as possible.

Edit (an example for a special case): A scheduling problem that can be interpreted in this way is where you want to schedule a set of jobs indexed by $i$ (given by earliest start time $r_i$, latest completion time $d_i$  and processing time $p_i$) on a single machine of infinite capacity, and the objective is to minimize the total busy time of the machine. In this setting, the family $\mathcal F_i$ would just be the set of intervals $\{[r_i,r_i+p_i-1],[r_i+1,r_i+p_i],\dots,[d_i-p_i+1,d_i]\}$, and the problem can be solved efficiently (Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir. “Real-time scheduling
to minimize machine busy times”. In: Journal of Scheduling 18.6 (2015), p. 561-573, doi:10.1007/s10951-014-0411-z)

I am looking for references where this problem (or something similar) has been considered with more general families $\mathcal F_i$.

I don't know of a name, but your problem generalizes the notoriously hard Min-Rep problem  (introduced in this paper by Kortsarz). Roughly, an input to Min-Rep consists of a bipartite graph $G=(A;B,E)$, with each of $A$ and $B$ sub-partitioned into a collection of equal-sized  so-called supervertices. A superedge between two supervertices $a,b$ is the set edges of the form $u,v$ where $u \in a$ and $v \in b$. For a vertex set $S \subseteq A \cup B$, we say $S$ covers superedge $\hat{e}$ if there exists some $(u,v) \in \hat{e}$ such that $\{u,v\} \subseteq S$. The problem is then to find the smallest subset of $S \subseteq A \cup B$ such that all nonempty superedges are covered by $S$. Phrased alternatively, we wish to distinguish (at least) one "witness" edge per nonempty superedge, and the objective function is to minimize the cardinality of the union of the various distinguished edges' endpoints.

Viewed in this light, the connection to your problem is now straightforward. The set of vertices $A \cup B$ will become your ground set $[n]$. The collection of nonempty superedges will become the subset families $\mathcal{F}_i$. If a superedge $e$ contains the edge $(u,v)$, then its corresponding subset family contains the set $\{i,j\}$, where $i$ and $j$ are the images of $u$ and $v$ in this reduction.

There is a clear bijection between solutions the Min-Rep instance and in your original problem, and this bijection preserves objective value. Thus, your problem is at least as hard as Min-Rep to approximate, and Min-Rep is known to be hard to something like $2^{\log^{1-\epsilon} n}$ under standard complexity theoretic conjectures.

Min-Rep is very intimately related to the famous graph label cover problem. My guess is that your problem is also related (or maybe even equivalent) to hypergraph label-cover (probably using a similar reduction), but I'm not familiar with the recent literature in the area, and someone else can probably elaborate on that connection.


Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)? I know that's impossible to decide $\beta$-equivalence for untyped lambda calculus. Quoting Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland, Amsterdam (1984).:

  If A and B are disjoint, nonempty sets of lambda terms which are closed under equality, then A and B are recursively inseparable. It follows that if A is a nontrivial set of lambda terms closed under equality, then A is not recursive. So, we cannot decide the problem "M=x?" for any particular M. Also, it follows that Lambda has no recursive models.

If we have a normalizing system, such as System F, then we can decide $\beta$-equivalence "from outside" by reducing the two given terms and comparing if their normal forms are the same or not. However, can we do it "from inside"? Is there a System-F combinator $E$ such that for two combinators $M$ and $N$ we have $E M N = \mbox{true}$ if $M$ and $N$ have the same normal form, and $E M N = \mbox{false}$ otherwise? Or can this be done at least for some $M$s? To construct a combinator $E_M$ such that $E_M N$ is true iff $N\equiv_\beta M$? If not, why?

No, it's not possible. Consider the following two inhabitants of the type $(A \to B) \to (A \to B)$.

$$
\begin{array}{l}
M = \lambda f.\;f \\
N = \lambda f.\;\lambda a.\; f\;a
\end{array}
$$

These are distinct $\beta$-normal forms, but cannot be distinguished by a lambda-term, since $N$ is an $\eta$-expansion of $M$, and $\eta$-expansion preserves observational equivalence in a pure typed lambda calculus.

Cody asked what happens if we mod out by $\eta$-equivalence, also. The answer is still negative, because of parametricity. Consider the following two terms at the type $(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$:

$$
\begin{array}{lcl}
M & = & \lambda f:(\forall \alpha.\;\alpha \to \alpha).\;\Lambda \alpha.\lambda x:\alpha.\;f \;[\forall \alpha.\;\alpha \to \alpha]\;(\Lambda \beta.\lambda y:\beta.\;y)\;[\alpha]\;x\\
N & = & \lambda f:(\forall \alpha.\;\alpha \to \alpha).\;\Lambda \alpha.\lambda x:\alpha.\;f\;[\alpha]\;x
\end{array}
$$

They are distinct $\beta$-normal, $\eta$-long form, but are observationally equivalent. In fact, all functions of this type are equivalent, since $\forall \alpha.\;\alpha \to \alpha$ is the encoding of the unit type, and so all functions of the type $(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$ must be extensionally equivalent.


Complexity class associated with exhaustive search What is the complexity class associated with exhaustive search algorithms? (if there is one)

Is it NP or PSPACE?

Are there restricted models of computation capturing the class of exhaustive search algorithms similar to models for greedy and dynamic programming?

It's a little vague, but I like the question. I wrote a paper about it a LONG time ago.
Maybe this will help the Anonymous questioner:

Brute Force Search and Oracle-Based Computation

Here's a summary. Informally, if you do not keep any scratch work from previous trials, and just try all possible solutions in lexicographical order until a desired solution is found, then brute force corresponds precisely to $P^{NP}$. If you keep around even $3$ bits of scratch work from one possible solution to the next, then you can do $PSPACE$, via Barrington's theorem. There are other possibilities, such as what happens when you don't run in lex order but according to some other efficiently computable list of all strings.

[WARNING WARNING WARNING: It's likely that I disagree with almost all opinions stated in this paper. It was written about 10 years ago, by someone with the same name but who is essentially a different person.]


Why is P vs. NP so hard? Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important?

Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem?

Why is it so hard?

All I'm looking for is the hindrances to solving $\mathsf{P}$ vs. $\mathsf{NP}$. Are there any theorems that help explain why $\mathsf{P}$ vs. $\mathsf{NP}$ is so hard?

I guess the best answer to your question is to point out that there have been several "barriers" to proving the P vs NP problem which have been identified and which rule out a number of approaches to a proof.

The three main barriers identified are relativization, natural proofs and algebrization. All of these are described on the P vs NP Wikipedia page under the heading "Results about the difficulty of proof", here.

A more detailed explanation can be found in the papers outlining these barriers referenced on the same Wikipedia page.


Verifying consistency of strict and non-strict partial orders constraints I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables representing elements of the set.  The laws that relate the two orderings are the same as $<$ and $\leq$ for integers.  I need to make sure that each constraint that I add does not make the set inconsistent (e.g. adding $x < y$ and then $y < x$ I'd get an error).

Now, if I had only the $<$ constraints I could get away with generating a graph and then doing a topological sort, or with disjoint-sets.  The problem is that I'm not sure how to handle the additional $\leq$ constraints.

One idea is to express $x \leq y$ as $\neg (x > y)$, and to keep two graphs:  one for the actual $<$ relations and one for the negated ones.  Then we'd need to check, at each new constraints, whether there are overlapping paths between the two graphs, in which case we'd have a problem.  However this seems rather costly since it seems to me that we'd need to analyze all the pairs each time.

Another idea would be to 'collapse' $\leq$ relations to equalities or $<$ when needed, but again I'm quite uncertain on the details.

Is this problem described somewhere?  As a bonus, I'd like the data structures involved to be purely functional.

You may find it helpful to think of your problem in terms of equalities and strict inequalities.

In the case of the constraints being equalities or disequalities there is a simple saturation procedure based on transitivity of equality.  Strict inequalities can be represented by directed edges in a graph. You can then compute strongly connected components to reason about dependencies between sets of variables. If you have uninterpreted functions, you can use congruence closure.

I would imagine that the first results date to the 50s or at least the 70s, but I do not have a good reference for you. Recent literature in which these ideas occur is the paper below.

  An Interpolating Decision Procedure for Transitive Relations with Uninterpreted Functions, Georg Weissenbacher.