Characterizing the set of problems solvable via network flow What are some ways to prove that a certain problem cannot be solved using Network Flow (NF)?

One way is to prove the problem is NP-hard.
But NF has substantial structure -- is there some symmetry or invariant that all solutions must satisfy in order to be solvable with NF?

I'm interested in any necessary or sufficient conditions that a problem should satisfy in order to be solvable using NF.

It depends on how you define "solvable via network flows". If you allow the preprocessing step to take arbitrarily long, then anything is solvable using network flows by simply solving it an then outputting a trivial network flow that has the desired answer.

Under log-space reductions, network flow is $P$-complete so any problem in $P$ can be solved "efficiently" using a network flow.

Another interesting aspect of flows is that if you start with integer capacities, then the solution will be integer as well. Network Flows (when viewed as Linear Programs) are actually part of a larger class of problems called totally unimodular. The optimal solutions to these programs are always integer.


Finding the perfomance ratio in a multicommodity-flow I am reading the following paper about multicommodity-flows. I have not a very strong background in graph theory and hence most of my question regarding the paper are fundamental. My questions are about lemma 2 and its proof, which is needed to find an approximation algorithm for the maximum 2-splittable flow problem.

My first question is about the problem definition on page 102. A flow in a network has different values along the arcs. They define a k-splittable $s$-$t$ flow $F$ as $k$ pairs $(P_1,f_1),\dots,(P_k,f_k)$, where $P_i$ is a simple $s$-$t$ path. Does the value of such an $f_i$ change along $P_i$? Since they say $(P_i,f_i)\in \mathcal{P}_{s,t}\times\mathbb{R}_{\ge 0}$ this would imply it does not change along $P_i$. However since natural flows do change along the arcs, I want to be sure, if my interpretation is correct.
This question is about lemma $2$ on page 105. I have never heard the definition of a thickest $s$-$t$ path. Also a web search was not successful. What does thickest $s$-$t$ path mean in this context and how can we conclude in the proof that the bottleneck edge $e$ has strictly positive residual capacity using the value of a maximum $s$-$t$ flow in $G'$?
If this bottleneck edge $e$ is a forward edge of $P_1$, why do both $P^*_1$ and $P^*_2$ contain this edge?
What is meant by a $D/k$ integral $s$-$t$ flow?
the last question is about approximation algorithms. So far I have never been in touch with approximation algorithms. I know that a $\rho$ approximation algorithm yields a feasible solution whose value is at most a factor of $\rho$ away from the optimum. So how exactly does lemma 2 imply that using the maximum capacity augmenting path algorithm yields a $\frac{2}{3}$-approximation algorithm?

Thank you for your help

$f_i$ are constant real numbers. They stay the same over the entire path. But note that the paths are not necessarily edge-disjoint. So an edge could be present in multiple paths and hence the actual flow in that edge will be sum of all the corresponding path flows.
For a path $P$, let $cap(P)$ denote the smallest edge capacity in the path. A thickest path is a path $P$ with largest $cap(P)$ (imagine the edges as pipes and capacity defining the thickness of pipe). A bottleneck edge of path $P$ would be an edge with capacity $cap(P)$. After sending a flow $f_1$ on $P_1$, in the corresponding residual graph, let $P_3$ be a thickest path. If the residual capacity of the bottleneck edge is $0$ (i.e., maximum $cap(P)$ value is $0$ over all paths), then no more flow can be sent from $s$ to $t$. But this implies $f_1 \geq f_1^* + f_2^*$ contradicting the assumption that $f_1 \lt f_1^* + f_2^*$.
While constructing this new graph $G^\prime$, edge capacities were reduced to smallest values that allowed the flow $f_1$ to be feasible and the flows $f_1^*$, $f_2^*$ to be feasible. Suppose $e$ is not present in one of the two paths (say $P_1^*$). Then the capacity on edge $e$ must have been reduced to $f_1$ (as $f_1 \geq f_2^*$), resulting in zero residual capacity. So $e$ must be present in both the paths $P_1^*$ and $P_2^*$.
When we say something is $(1/r)$-integral, it means the values involved are integral multiples of $1/r$ (so standard integral solution will be $1$-integral). Here, $D/k$ integral flow means that each edge has a flow which is an integral multiple of $D/k$.
Using lemma $1$, if we have a flow $f_1+f_2$ obtained through two augmenting path iterations, then this flow can be written as sum of $3$ paths with flows $f_1^ \prime ,f_2^ \prime ,f_3^ \prime $. So we have $f_1^ \prime +f_2^ \prime +f_3^ \prime = f_1 + f_2 \geq f_1^* + f_2^*$, where $f_1^* + f_2^*$ is a maximum 2-splittable flow (from lemma 2). Suppose $f_3 ^\prime$ is smallest among $f_1^ \prime ,f_2^ \prime ,f_3^ \prime $. Then $f_3^\prime \leq (1/3) (f_1^ \prime +f_2^ \prime +f_3^ \prime )$. So taking the two paths corresponding to $f_1^\prime$ and $f_2^\prime$, the net flow is $f_1^ \prime +f_2^ \prime \geq (2/3)(f_1^ \prime +f_2^ \prime +f_3^ \prime ) \geq (2/3)(f_1^* + f_2^*)$. So this gives a $\frac{2}{3}$-approximation.

I am not able to see why lemma $1$ is true. Do you have any simple proof for that?


Compute Nash Equilibrium for 2-player games I want to compute a mixed strategy that will be the Nash Equilibrium of the game.
I have used my knowledge in order to create the system for the mixed strategy.
I concluded on a system with 3 variables and 5 constrains.I am not able to solve this system using the common Gaussian Elimination method.This system is a linear program from what I can imagine.I have searched google for similar examples but all the examples was on 2-player games with only 2 strategies per player.In those games was quite easy to compute the mixed strategy.I am thinking of using the simplex method for finding the NE but I am thinking that this is weird for such a small game...
Are there simpler method that can be used in computing a NE profile?
Thank you.

We have developed a user-friendly browser-based system to input and solve 2-player strategic-form and extensive-form games:

http://www.gametheoryexplorer.org/ (GTE)

Currently, we support:

finding all equilibria via polyhedral vertex enumeration (which works on the strategic-form representation, which is converted to in the case of extensive-form games; this uses David Avis' lrs http://cgm.cs.mcgill.ca/~avis/C/lrs.htmlW); and
finding one equilibrium using Lemke's algorithm (which works on the strategic-form representation or on the sequence-form representation for extensive-form games).

You can use lrs separately offline to solve larger bimatrix games.

The GTE project is under active development (supported by the Google Summer of Code in 2011, 2012, and 2014), so please provide feedback and/or let us know if you would like to contribute) at

gte@nash.lse.ac.uk

For a paper that covers the basic theory and a number of methods for enumeration of equilibria, see

D. Avis, G. Rosenberg, R. Savani , and B. von Stengel (2010).
Enumeration of Nash Equilibria for Two-Player Games.
Economic Theory 42, 9-37.

For a paper that describes GTE and what it can do, see

R. Savani and B. von Stengel (2014).
Game Theory Explorer - Software for the Applied Game Theorist.
Computational Management Science, 29 pages, to appear. arXiv version

Zouzias' answer gives a good description of how to use support enumeration, which works fine for small examples. The methods in the paper above and used in GTE will in general be much quicker than support enumeration for finding extreme equilibria. In addition, GTE will find the complete set of equilibria (which can include convex combinations of extreme equilibria) by finding maximal cliques in a bipartite graph.


If BQP contains NP, does this mean that P=NP? There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that if P=NP then PH collapses to the 0th level.

Based on the above two statements, I would like to ask if BQP contains NP, does this imply that P=NP?

[1] http://www.scottaaronson.com/papers/bqpph.pdf

No, $\mathrm{NP}\subseteq\mathrm{BQP}$ is not known to imply $\mathrm P=\mathrm{NP}$. Even the stronger assumption $\mathrm{NP}\subseteq\mathrm{BPP}$ is not known to yield a deeper collapse than $\mathrm{NP}=\mathrm{RP}$ and $\mathrm{PH}=\mathrm{ZPP^{RP}}=\mathrm{BPP}$; in particular, it is not even known to imply $\mathrm{NP}=\mathrm{coNP}$. (However, all these implications are likely true by virtue of their premises being false.)


Is there an analogy of a vertex separator for hypergraphs? Numerous parameters are defined and considered in the graph theory. I am interested in analogy of these parameters in theory of hypergraphs.

Is there some survey or book or lecture notes about various hypergraph parameters such as independent set, matching, separator, cut, and so on?

In particular, I am interested in an analogy of separator. For a graph $G=(V,E)$, a separator $S$ is a subset of vertices such that removing all elements in $S$ we can obtain two or more separated components $G_{1},G_{2},...$. I am interested in minimum size of separator for hypergraphs.

heres an example

PARTITIONING HYPERGRAPHS IN SCIENTIFIC COMPUTING
APPLICATIONS THROUGH VERTEX SEPARATORS ON GRAPHS KAYAASLAN et al

(there is also some research on hypergraph edge separators used in SAT solvers & other edge separators but not incl it because you asked for vertex separators although there is possibly/presumably some connection.)


resolution based theorem prover for temporal logic I am looking at implementing a a resolution-based theorem prover for propositional linear temporal logic (PLTL) (as opposed to a model checker). The ones out there (by Fisher et. al. and others) are complex on account have having to deal directly with temporal resolution. So looking for something quick and good enough for now (I'm not too concerned with retaining decidability or its efficiency at this point), I am considering the translation of PLTL into first order logic (FOL). The propositions are turned into unary predicates over numbers. This translation is well known and described in several places (eg Fisher)

p → p(i)

$\circ$p → p(i + 1)

$\diamond$p → ∃j. (j ≥ i) ∧ p(j)

$\Box$p → ∀j. (j ≥ i) ⇒ p(j)

The problem is that these first order formulas have distinguished symbols > and succ (as well as equality) - alternatively the FOL formulas are meant to be interpreted w.r.t. a natural number line which corresponds to the timeline of PLTL. Is there a good way to implement a resolution prover that can take into account or provide these symbols with their required interpretation? More specifically:

For example, would it work to add the theory of the successor function to the translation and go from there?
How would I handle equality? (paramodulation?)
I'd like to be able to implement this in Prolog but you can't encode equational theories like subsets of arithmetic in Prolog, but would Prolog's built-in arithmetic operators perhaps suffice?

Thanks!

Your translation goes into Presburger arithmetic, which is decidable.

You could take your translated formula, do quantifier elimination on it, and then hand it over to a proof-producing SMT solver. Since pretty much all SMT solvers are (fancy extensions of) DPLL, I would guess you can turn those proofs into resolution proofs without too much difficulty.

I'm pretty sure that CVC4 can directly give you the resolution proofs, and would be surprised if Z3 couldn't.


Categorical semantics for non-monotonic logics? Are there any categorical semantics for non-monotonic logics?

It appears that the simple answer to this is "No" since the obvious notion of composition fails for any model of a non-monotonic logic. But is there a model that actually works with an appropriately defined notion of composition?

Non-monotonic logic is kind of a wide area -- do you have any particular logics in mind? Anyway, defeasibly assuming :) that

you are interested in any logic in which the principle of monotony fails, and
you want a categorical semantics in the sense of categorical proof theory (rather than, say, a hyperdoctrine semantics), then

one answer is that you can give a reasonable categorical semantics to any logic for which a sequent calculus with cut-elimination is known. Basically, the types are objects, normal forms of the sequent calculus are morphisms, and cut-elimination tells you how to implement composition. This gives you the initial category in whatever category of models you end up using to prove soundness and completeness.

This recipe is independent of monotonicity, and so it can work well even for non-monotonic logics. For example, one of the more important successes in categorical logic is its treatment of linear logic. This is a logic where, intuitively, propositions refer to resources, so that the linear implication $A \multimap B$ can be read as "$A$ can be consumed to produce $B$". The consequence relation of linear logic is non-monotonic (since the fact that $A$ can be consumed to produce $B$ does not mean that $A$ and $X$ can both be consumed to produce $B$). However, it has an excellent proof theory, and its categorical models are closely tied to the theory of monoidal categories.


Communication lower bounds for partial boolean functions There are well known techniques for proving lower bounds on the communication complexity of boolean functions, like fooling sets, the rank of the communication matrix, and discepancy.

1) How do we use these techniques for lower bounding partial boolean functions? More specifically, how do you count the rectangles in the communication matrix? Do you also count the "undefined part" of the function? Or do you leave it out?

Another thing, what are the known relations between the communication complexity of total and partial functions? For example, is there a function $f$ with a promise version of it, call it $f'$, such that $C(f)\neq C(f')$? (here $C$ could be any communication complexity measure like deterministic, probabilistic with all its flavors, quantum). A concrete example is the equality function EQ, and its promise version defined in this paper denoted as EQ'. It is known that $C(EQ)=n$ and $C(EQ')=\Omega(n)$ where $C$ is the bounded error communication complexity (see the paper). There is no matching upper bound here, but they are asymptotically the same.

2) Is there a function defined in the same spirit of EQ and EQ', but with a different complexity?

(1) The way I like to think about partial functions is by defining a total function with three outputs e.g, $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1, *\}$.  The $*$ values are where your partial function is undefined.

(2)  You can still define a "monochromatic" rectangle in this case.  But here, you allow $*$'s to be in the rectangle.

A rectangle $R$ is monochromatic if $f(R) \subseteq \{0,*\}$ or $f(R) \subseteq \{1,*\}$.

From this, you can still use many of the standard lower bounds techniques such as fooling sets.

(3) As Marc mentions, you can always define trivial partial functions where the communication complexity is much less than the original.  For example, say the partial function TEQ is the EQ function, restricted to $(x,y)$ pairs such that $x \neq y$.

A partial function that people might care about is the Gap-Hamming-Distance function.
$GHD_{n,g}$ is takes two $n$ bit strings $x,y$ and returns $1$ if their Hamming distance is more than $n/2 + g$ and returns $0$ if their Hamming distance is less than $n/2 - g$.  (The Hamming distance $\Delta(x,y)$ is the number of $i$ where $x_i \neq y_i$.)

People are really particularly interested in the randomized communication complexity of $GHD$.  It's not hard to show that the gapless version (Alice/Bob want to tell if $\Delta(x,y)$ is greater than $n/2$ or not) requires $\Omega(n)$ bits of communication.

It turns out that when $g = O(\sqrt{n})$, you still need a linear amount of communication.  However, when $g = \omega(\sqrt{n})$, you can get away with only $O((n/g)^2)$ bits.  When $g = \Omega(n)$, you get a partial function with $O(1)$ communication complexity.

The $g = \Theta(\sqrt{n})$ case seems to be the "important case".  Indyk and Woodruff introduced this problem, gave a lower bound for one-way randomized protocols, and used it to get lower bounds for streaming algorithms that estimate frequency moments.  The state of the art lower bound is $\Omega(n)$ bits for any randomized protocol and is due to Chakrabarti and Regev.

Piotr Indyk and David Woodruff.  Tight Lower Bounds for the Distinct Elements Problem. FOCS 2003.

Amit Chakrabarti and Oded Regev.  An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. http://arxiv.org/pdf/1009.3460.


Maximum matching M with the condition G[M] is 2K_2-free Is there anything in the literature close to the following problem:

Given a bipartite graph $G(V,E)$ with balanced bipartition $ \{U,W\}$ , does there exist a perfect matching $ M $ in $ G $ such that for every 2 edges $u_1w_1, u_2w_2\in M $, there is an edge $u_1w_2$ or edge $u_2w_1$ (or both) in $ G $?

In other words, is there a perfect matching $M$ such that the induced subgraph $G[M]$ is $ 2K_2 $-free.
(With balanced bipartition, I meant $|U|=|W|$.)

The extra condition is something like an opposite extreme of that used in induced matching problem. Another possibly related one is the problem of finding maximum size matching $M$ in bipartite graph $G$ such that contraction of edges in $M$ minimizes the number of edges left in the graph.

I checked the list of matching related problems given by Plummer in Matching and vertex packing: how "hard" are they? without success.

PS: This problem is a special case of this decision problem :- For a given $k\in\mathbb{N}$, is there a maximum matching $M$ of a bipartite graph $G$ such that $G[M]$ is $2K_2$-free and $|M|>k$. If the input graph is balanced bipartite and $k=|U|$, we get the above problem.

Thank you.

Surprise! (for me).
This type of matchings are already studied in the literature. They are called connected matchings.

They were introduced by Plummer, Stiebitz and Toft in their study on Hadwiger conjecture. See the chapter "Connected Matchings" by Cameron in the book "Combinatorial Optimization – Eureka, You Shrink!"

The status of connected matchings in bipartite graphs (not necessary balanced) is open to the best of my knowledge (i shall update). The weighted version of the problem is NP-complete for bipartite graphs. The problem is polynomial time solvable for chordal bipartite graphs.

Update: the problem is NP-complete for balanced bipartite graphs (i.e., the exact problem asked in the question). This is proved in the paper "Multitasking Capacity: Hardness Results and Improved Constructions" by Alon et al.  They also report that finding the size of a largest connected matching is hard to approximate within a factor of $n^{1-\epsilon}$ unless NP = co-RP.

Notes added earlier (kept for interested people):
"Connected matchings in chordal bipartite graphs" by Jobson et al. (doi:https://doi.org/10.1016/j.disopt.2014.06.003) and "Connected matchings in special families of graphs" by Caragianis (thesis) are two notable references.


The number of states of local automata A deterministic automaton $\mathcal A = (X, Q, q_0, F, \delta)$ is called $k$-local  for $k > 0$ if for every $w \in X^k$ the set $\{ \delta(q,w) : q \in Q \}$ contains at most one element. Intuitively that means if a word $w$ of length $k$ leads to a state, then this state is unique, or said differently from an arbitrary word of length $> k$ the last $k$ symbols determine the state it leads to.

Now if an automaton is $k$-local, then it need not be $k'$-local for some $k' < k$, but it has to be $k'$-local for $k' > k$ cause the last symbols of some word $|w| > k$ determine the state, if any, uniquely.

Now I try to connect the number of states and the $k$-localness of an automaton. I conjecture:

  Lemma: Let $\mathcal A = (X,Q,q_0,F,\delta)$ be $k$-local, if $|Q| < k$ then the automaton is also $|Q|$-local.

But I failed to proof, any suggestions or ideas?

I hope by this Lemma to derive something about the number of states of an automaton which is not $k$-local for all $k \le N$ given a fixed $N > 0$, but $k$-local for some $k > N$.

A late answer, but the bound on synchronization delay has been studied for several classes of automata: see for instance Unambiguous Automata; Béal et al. MCS'08.

In particular; there is a family of deterministic automata that have delay $\Omega(|Q|^2)$ as showed in On the Bound of the Synchronization Delay of a Local Automaton; Béal et al. TCS'98, which matches a corresponding $O(|Q|^2)$ upper bound.

P.S. the synchronization delay defined in the paper is the minimal $k$ for which the deterministic local automaton is $k$-local.


totally-mixed 2SAT with exact cardinality? Given a 2HornSAT problem, it’s possible in linear time to find the minimum solution to the problem, i.e., a solution that minimizes the number of variables set to 1.

Now let us consider the following restricted variant of that problem:

  Input: A positive integer $K$ and a 2SAT instance in which all clauses are mixed, i.e., have a positive literal and a negative literal.

  Output: Is there a satisfying assignment such that exactly $K$ variables are set to 1?

Is this problem NP-complete? I am struggling with its reduction but it seems this might be difficult.

Your problem is NP-complete.

I prove NP-hardness below by reduction from the clique problem (given a graph and a number, does the graph have a clique of that many vertices).

reduction

Suppose we are given a clique instance consisting of a graph $G = (V, E)$ with $m = |E|$ and $n = |V|$ and a number $k$. Then we will produce an instance of your problem consisting of a formula $\phi$ and a number $K$ as described below

First of all, we set $K = k + (n+1) \times {k \choose 2}$.

Next, lets describe the variables used in $\phi$. For each vertex $v \in V$, $\phi$ will include a variable $x_v$. For each edge $e \in E$, $\phi$ will include $n+1$ variables: $y_e^0, y_e^1, \ldots, y_e^n$.

Finally, lets describe the clauses included in $\phi$. Each clauses has the form $(a \vee \neg b)$, which is logically equivalent to $(b \to a)$, so I will write all clauses in implication form. For each edge $e \in E$, we include clauses $(y_e^n \to y_e^0)$, $(y_e^0 \to y_e^1)$, $(y_e^1 \to y_e^2)$, ..., and $(y_e^{n-1} \to y_e^n)$. The effect of these clauses is to enforce the equality of all the $y_e^i$s (for any fixed $e$) in any satisfying assignment. Next, for any edge $(u, v) \in E$, we also include clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$. The effect of these clauses is that in any satisfying assignment, if the variables $y_{(u,v)}^i$ associated with an edge are true then the variables $x_u$ and $x_v$ associated with the endpoints must also be true.

clique $\to$ satisfying assignment

Suppose that there is a clique $C$ of size $k$ in $G$. Then we can create a satisfying assignment for $\phi$ with exactly $K = k + (n+1) \times {k \choose 2}$ true variables.

In particular, for $v \in V$, set $x_v$ to true iff $v \in C$, and for $e \in E$, set $y_e^i$ to true iff both endpoints of $e$ are in $C$.

There are $n+1$ variables $y_e^i$ for each $e$, and there are exactly $k \choose 2$ edges in $G$ with both endpoints in $C$ (since $C$ is a clique). Thus there are $(n+1) \times {k \choose 2}$ variables of the form $y_e^i$ that are set to true under this assignment. Furthermore, $|C| = k$, so there are exactly $k$ variables of the form $x_v$ set to true under this assignment. As desired, this assignment has exactly $K = k + (n+1) \times {k \choose 2}$ true variables.

Notice that $y_e^i = y_e^j$ for every edge $e$ and pair of indices $i, j$. Thus, the clauses of the form $(y_e^i \to y_e^{(i+1)~\text{mod}~(n+1)})$ are satisfied under this variable assignment.

Next, consider any edge $(u, v)$. If $y_{(u, v)}^0$ is true, then both $u$ and $v$ are vertices in $C$, so therefore both $x_u$ and $x_v$ are also true. Thus, clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$ are also satisfied.

Since all clauses are satisfied, this is a satisfying assignment (which we already noted has exactly $K$ true variables).

satisfying assignment $\to$ clique

Next suppose we have a satisfying assignment of $\phi$ with exactly $K = k+ (n+1) \times {k \choose 2}$ true variables.

Any satisfying assignment has $y_e^0 = y_e^1 = \cdots = y_e^n$. Then let $y_e = y_e^0$. Define $n_y$ to be the number of true $y_e$s. Similarly, define $n_x$ to be the number of true $x_v$s. Notice that the number of true variables in the assignment is equal to $n_x + (n+1) \times n_y$. Furthermore, $0 \le n_x < n+1$ since there are only $n$ different $x_v$s. Thus, we can conclude that $n_x = K~\text{mod}~(n+1) = k$ and $n_y = \lfloor \frac{K}{n+1} \rfloor = {k \choose 2}$.

Let $C = \{v \in V~|~x_v~\text{is true}\}$ and let $E' = \{e \in E~|~y_e~\text{is true}\}$. Note that $|C| = n_x$ and $|E'| = n_y$ by definition. Then $E'$ is a set of ${k \choose 2}$ edges, and $C$ is a set of $k$ edges.

Notice that if $(u,v) \in E'$, then $y_{(u,v)}$ is true, and therefore $y_{(u,v)}^0$ is true; as a result, since clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$ must be satisfied, we can conclude that $x_u$ and $x_v$ are also true, and therefore that $u,v \in C$. Thus, if $e \in E'$ and $v$ is an endpoint of $e$ then $v \in C$.

Thus the set of endpoints of edges in $E'$ is a subset of $C$. Then $E'$ is a set of ${k \choose 2}$ edges whose set of endpoints numbers at most $|C| = k$. A set of ${k \choose 2}$ edges has only $k$ endpoints in total only in the case that the $k$ endpoints are a clique. In other words, it must be the case that $C$ is a clique and the edges in $E'$ are the edges in the clique.

Thus we have identified a clique of size $k$ in $G$.


Cluster Edge Deletion on 2-trees Definitions:
Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced subgraph (that is, the resulting graph is a disjoin union of cliques).

The class of $k$-trees is defined as follows: a complete graph with $k$ vertices is a $k$-tree; a $k$-trees with $n + 1$ vertices $(n > k)$ can be constructed from a $k$-tree $T$ with $n$ vertices by adding a vertex adjacent to all vertices of a $k$-clique of $T$, and only to these vertices.

Question:
Does exist a linear-time algorithm to solve Cluster Edge Deletion on 2-trees?

The edge sets whose deletion leaves a cluster graph can easily be described as a formula with one free variable (the edge set) in monadic second-order graph logic. Therefore, by an optimization version of Courcelle's theorem, the minimum cardinality set can be found in linear time for graphs of bounded treewidth, which obviously include the 2-trees.

See e.g. Arnborg, Lagergren, and Seese, "Easy problems for tree-decomposable graphs", J. Algorithms 1991.


Algorithms with finite expected running time and infinite variance I am working on an algorithm for which the running time is a random variable $X$ that has finite expected value, but infinite variance. Are there examples of other algorithms for which this is the case?

Are any such algorithm used in practice, or does the infinite variance make the running time too unpredictable?

Though I'm having trouble finding the exact exponent of the power laws they purport to exist, Kroc, Sabharwal and Selman have a paper called "An Empirical Study of Optimal Noise and Runtime Distributions in Local Search" where they show WalkSat (a local solver for SAT) has power law tails in the runtime.  If the power law does not fall within the range of $(2,3]$, then obviously this isn't quite what you're looking for, but maybe it's still of some use.

It looks like Gomes, Selman, Crato and Klautz also have a paper called "Heavy-Tailed Phenomena in Satisﬁability and Constraint Satisfaction Problems" though from a quick spot check it looks like they're reporting the exponent in the power law in the range of $(1,2)$ which would violate your finite first moment condition.

Also Gomes, Selman and Crato published a paper called "Heavy-Tailed Distributions in Combinatorial Search" which might be of some relevance.

From what I understand, the sporadic nature of runtimes (for example, because of a power law behavior in running time) gives one a good reason to use random restarts and might even inform you as to when a restart should occur.  Figure 8a in the paper "Heavy-Tailed Distributions in Combinatorial Search" gives two run time plots, one without restarts and one with, where the algorithm with random restart clearly wins out.


Is there any reference on the hardness of approximation for 2-partition problem? I tried to look for some references but could not find any. I knew it is proved to be NP-complete via a transformation from Knapsack or 3DM problem. But I couldn't find a way to apply PCP theorem to get the hardness of approximation for this problem. Thank you.

From the Wikipedia page on the Partition problem: "...there are fully polynomial-time approximation schemes for the subset-sum problem, and hence for the partition problem as well". The references given there are
Kellerer, Pferschy, Pisinger and Martello, Toth.


Shortest distance problem with length as functions of time Motivation

The other day, I was travelling around the city with public transport and I made up an interesting graph problem modelling the problem of finding the shortest-time connection between two places.

We all know the classical "Shortest path problem": Given a directed graph $G=(V,E)$ with edge-lengths $w_e\in\mathbb{R}_0^+,\,e\in E$ and two vertices $s,t\in V$, find the the shortest path between $s$ and $t$ (i.e., the path minimizing the total edge-length). Assuming non-negative edge-lengths, there are various algorithms and the problem is easy.

This is a good model for the case that we are walking, for example. The vertices are crossroads in our network of roads and each edge has fixed length -- in meters, for instance. Another possible interpretation of the edge-weights $w_e$ is the time that it takes us to go from one of its vertices to the other. This is the interpretation that interests me now.

Problem

I now want to model the following situation. I want to travel from point A to point B in a city via public transport and minimize time. The public transport network can be easily modelled as a directed graph as you would expect. The interesting part are the edge-weights (that model time) -- public transport (buses, for instance) leave only in certain intervals, which are different for every stop (vertex in graph). In other words -- the edge-weights are not constant, they change depending on the time we want to use the edge.

How to model this situation: We have a directed graph $G=(V,E)$ and an edge-weight function $w\colon E\times \mathbb{R}_0^+\rightarrow\mathbb{R}_0^+$ that takes time as its argument and returns time that it takes to use the edge in our path. For example, if the bus from vertex $v$ to vertex $u$ leaves at $t=10$ and it takes $5$ time and we arrive at vertex $v$ at $t=8$, then $w(vu,8)=7$ is the edge-weight. Clearly, $w(vu,10)=5$.

It is slightly tricky to define total weight of path, but we can do it recursively. Let $P=v_1v_2\ldots v_{k-1} v_k$ be a directed path. If $k=1$ then $w(P)=0$. Otherwise, $w(P)=w(P')+w(v_{k-1}v_k,w(P'))$, where $P'$ is the sub-path of $P$ without $v_k$. This is a natural definition corresponding to the real-world situation.

We can now study the problem under various assumptions on the function $w$. The natural assumption is
$$w(e,t)\leq w(e,t+\Delta)+\Delta \text{ for all }e\in E,\Delta\geq 0,$$
which models "waiting for $\Delta$ time".

If the function "behaves nicely" it may be possible to reduce this problem to the classical Shortest path problem. But we could ask what happens when the weight-functions get wild. And what if we drop the assumption on waiting?

Questions

My questions are the following.

Has this problem been asked before? It seems kind of natural.
Is there any research on it? It seems to me that there are various subproblems to be asked and studied -- mainly regarding the properties of the weight-function.
Can we reduce this problem (possibly under some assumptions) to the classical shortest path problem?

This is known as the "time-dependent shortest path" problem.  Indeed research has been done for this problem; see for example the classical paper by Orda and Rom, and this recent SODA paper which proves that when the weight function of each edge is polynomial-size piecewise-linear, then the shortest path between two fixed points changes $n^{\Theta(\log n)}$ times.

Dijkstra's algorithm can indeed be used for this problem, when the waiting policy is imposed, that is, wait at a node if that reduces the final arriving time.  Without the waiting policy the situation is much wilder: the shortest path may not be simple, subpath of a shortest path might not be the shortest between the two endpoints of the subpath, paths traversing through infinite number of edges may have finite arriving time, etc.  See again the paper by Orda and Rom for more discussion.


On the faces of the multicommodity flow polytope Consider the multicommodity flow problem on an undirected graph with k source-destination pairs and specified capacity constraints on the edges. The set of concurrently achievable flows $(R_1,R_2,...,R_k)$ forms a polytope. We know that for $k=1$ (Ford-Fulkerson theorem) and $k=2$ (T.C. Hu's theorem), the cutset outer bound on the flow region is tight, so the polytope is completely specified by the cutset bound inequalities.

We also know that for $k=3$, the cutset outer bound is not tight in general. I am interested in what is known about the faces of this polytope for $k=3$.

Is there a universal bound on the number of faces of the polytope (for all graphs where $k=3$)? Or is it the case that given any $N>0$, one can construct a graph with 3 source-destination pairs whose flow polytope has more than $N$ faces?
Is it possible to express the equations for the new faces, namely the faces that don't correspond to the cutset bound, in terms of some combinatorial quantities associated with the graph?

Thanks.

This will be a bit long, but please bear with me.

First, let me clarify the terminology a bit. I think what you are interested in here are in fact the facets of the polytope (i.e., "the minimum set of irredundant valid inequalities" or the "maximal dimensional faces still distinct from the polytope itself") rather than the faces. Plus, as you write, the object you study is much better called the "aggregate-flow polytope" or, as some authors refer to it, the "demand polytope" or the "throughput polytope". Call this polytope $T$.

Here is what I know about $T$:

Associated with any capacitated graph $G$ and set of source-destination pairs $(s_k, d_k): k \in 1, \ldots, K$, there is an "aggregate-flow set" $T$.
This $T$ is a polyhedron and it is well-defined. You can see this for yourself by considering the following construction: take the multicommodity-flow polytope (i.e., the polyhedron of the feasible arc-flows or path-flows) and apply an affine mapping that to each commodity orders the sum of the individual flows. As affine maps of polyhedra are again polyhedra, you get the required result.
If $G$ is connected and the edge capacities $c$ are strictly positive, then $T$ is a full-dimensional, compact, convex polyhedron in $\mathbb{R}^n_+$ (so it  is in fact a polytope).
$T$ is down-monotone: $t \in T \Rightarrow \forall x \in [0, t]: x \in T$.
You can obtain all the valid inequalities that describe $T$ using the Japanese Theorem due to Onaga and Iri: for any non-negative weight set $w_{ij}: (i,j) \in E$ on the edges $E$ of $G$, the inequality:
$$\sum_{k=1}^K \beta_k . t_k \le \sum_{(i,j) \in E} w_{ij} c_{ij} $$
is valid for $T$, where $\beta_k$ denotes the shortest path distance from $s_k$ to $d_k$ for commodity $k$ over the weights $w$, $t_k$ is the aggregate-flow for the $k$th commodity and $c_{ij}$ is the capacity of edge $(i,j)$. In fact, you get all the valid inequalities for $T$ this way.
Any weight set that is not an extreme ray of the below projection cone $W$ generates redundant inequalities for $T$, where
$$W = \{(w,\beta): \forall k, \forall P \in \mathcal{P_k}: \sum_{(i,j) \in P} w_{ij} \le \beta_k, w \ge 0\}$$
where $\mathcal{P_k}$ denotes the set of all paths between $s_k$ and $d_k$. This sort of answers your second question.

Now, regarding the number of facets needed to describe $T$.

First, I believe your conjecture "for any $N$ there is a graph for which $T$ has more than $N$ facets" is not true. What we can show is that $T$ has finitely many facets, because the projection cone $W$ has only a finite number of extreme rays, and these generate all the facets (unfortunately, usually many more inequalities too). Note, however that this alone does not disprove your conjecture.

However, that this still allows the number of facets to be exponential, and curiously this is precisely the case. At least for directed graphs, I seem to have a proof somewhere that for the complete bipartite graph $K_{n,n}$ on $n$ nodes with $n$ distinct source nodes in one partition and $n$ distinct destination nodes in the other and capacities all equal to $1$, all the $\{0,1\}^n$ vectors $b$ except for the all-zero vector generate a facet $\sum_n b_n t_n \le q$ for some appropriate $q$, and this gives you $2^{n}-1$ facets. I don't know about the undirected case, the above may either hold or not hold.

For $K=3$ in particular, this gives 7 facets (plus the non-negativity conditions, but that's trivial) for $K_{3,3}$ in the directed case. As far as I can work it out now, the same applies to the undirected case as well. I have fairly good reasons to believe that this is in fact the upper bound for the directed case, but I may be completely wrong here.

You can find an awful lot of results on this topic in Schriver's heroic survey:

Alexander Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Volume 3, Part VII, Multiﬂows and Disjoint Paths

Should you have any comments, results, or further reading (apart from my own papers) on this topic, count me very very interested.


finding maximum weight subgraph My graph is as follows:

I need to find a maximum weight subgraph.

The problem is as follows:

There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in different Vertex cluster, there is a weighted edge, and in the same Vextex cluster, there is no edge among vertexes. Now I want to find a maximum weight subgraph by finding only one vertex in each Vertex cluster. And the total weight is computed by adding all weights of the edges between the selected vertex. I add a picture to explain the problem. Now I know how to model this problem by ILP method. However, I do not know how to solve it by an approximation algorithm and how to get its approximation ratio.

Could you give some solutions and suggestions?

Thank you very much. If any unclear points in this description, please feel free to ask.

This is the weighted, non-bipartite generalization of the Max-Rep problem, which is equivalent to LabelCover-Max. See Page 20 of Kortsarz. As far as I know, the best approximation algorithm to that problem is $O(n^{1/3})$, due to Charikar, Hajiaghayi, and Karloff

In terms of approximation, the original Max-Rep problem and your generalization are similar. Up to a factor of $O(\log n)$, the weights can be taken care of by a standard bucketing argument. Up to a factor of $2$, the graph can be made bipartite by randomly assigning each cluster one of two sets (say $A$ or $B$) according to a fair coin toss, and removing any edges that go from $A$ to $B$. So this gives an immediate $O(n^{1/3} \log n)$ approximation algorithm, using the algorithm of CHK as a subroutine.

The previous hardness of $O(2^{\log^{1-\epsilon} n})$ carries through (again, see the Kortsarz paper for more details), and there are some conjectures out there that for some $\epsilon>0$, the problem is hard to approximate to within $O(n^{\epsilon})$.


The number of clauses in an unsatisfiable CNF I am interested in generalisations of the following observation:
An unsatisfiable $k$-CNF has at least $2^k$ clauses.
A special case of the observation is when $k=n$, where $n$ is the number of variables. In this case, the clause-variable incidence graph is a complete bipartite graph.
I am particularly interested in the question:
Is there a lower bound on the number of clauses in a CNF $\phi$, in terms of the number of variables of $\phi$, when the clause-variable incidence graph of $\phi$ is $2K_2$-free (i.e. is a bipartite chain graph)?
But I am also interested in any generalisation of that question, or references to papers on questions about CNFs with this extremal flavour.
EDIT: Thanks to Christian Komusiewicz for highlighting that my question was ambiguous. The lower bound I'm after should be a function of the number of variables.

For arbitrarily large number $n$ of variables, the following CNF formula $\phi$ is not satisfiable, has only three clauses, and a $2K_2$-free clause-variable incidence graph:
$C_1=(x_1)$, $C_2=(\neg x_1)$, $C_3=(x_1,\ldots,x_n)$.
Thus, to get more interesting lower bounds one needs to make assumption about the minimum clause size or about the size of classes of clauses that contain the same variables (i.e. that have identical neighborhoods in the clause-variable incidence graph).
Observe that when the minimum clause size is $k$, then the example above can be adapted to give formulas with $2^k+1$ clauses and arbitrarily large number of variables $n$ that are not satisfiable. Moreover, when the number of clauses is $m<2^k+1$, then the formula is satisfiable even for arbitrarily large $n>k$: Let $C_m$ be the clause that has is incident with the largest set of variables. Since $n>k$, there is a variable $y$ that is not contained in the variable set of $C_1$, the clause with the smallest set of incident variables. Now, as for $k$-CNF formulas, the clauses $C_1,\ldots,C_{m-1}$ can be satisfied via an assignment of the first $k$ variables (which they all contain) and $C_m$ can be satisfied via the appropriate assignment of $y$.


Books on Mu-Calculus I need a book on Mu-Calculus with lots of examples that can be used for self-study and preparation for exams.

An excellent book is Rudiments of $\mu$-calculus. It's not cheap though. You'd be better of learning from survey articles such as

Bradfield, Julian and Stirling, Colin. Modal mu-calculi. In: P. Blackburn, J. van Benthem and F. Wolter (eds.), The Handbook of Modal Logic pp. 721-756. Elsevier (2006) or
Bradfield, J. C. and Stirling, C. P. Modal logics and mu-calculi: an introduction. In Handbook of Process Algebra (eds. J. Bergstra, A. Ponse and S. Smolka) 293--330. Elsevier (2001).


Fastest known deterministic algorithm for the undirected Graph Isomorphism problem What is the fastest known undirected graph isomorphism algorithm?

Babai invented the fastest known algorithm which runs in quasipolynomial time $2^{(\log n)^{O(1)}}$.


Does Pattern Calculus represent a step forward in languages or are we just going back to LISP? Barry Jay in his book makes some bold claims - basically by saying that, at the core of a program, everything is either atomic or composed. Then things can be easily iterated, filtered, updated, just by
navigating this composition relationship.

Is this a new frontier in Computer Science for computer languages - or are we just going back to LISP?

I'm not familiar with Barry Jay's recent work, but his older work includes things that you cannot do in Lisp, because the types give additional information.

For example, suppose you want to define the size of a Lisp data structure. It's 1 for an atom, and n for a list of n atoms, and more generally size(x)+size(y) for (cons x y).

Now throw in types into the mix. The size of a list would be its length. Now what's the size of a list of lists of atoms? If you consider this data structure as a list (whose elements happen to be lists of atoms), the answer is the length of the list. If you consider this data structure as containing atoms that happen to be stored in a list of lists, the answer is the sum of the lengths of the element lists.

Types allow you to distinguish between these two views (shapes) of the raw data. You need a type system that lets you discriminate between (List) (List Atom) and (List List) (Atom). The most common implementation of this distinction is with type classes (as in Haskell).


Searching for name of equivalence property in hamiltonian paths This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up.

Given a hamiltonian path, any subpath will consist of a start, end, and set of interior vertices. Any ordering of the interior vertices will possibly yield a path existing within the graph, that when substituted for the original will yield another valid hamiltonian path. These subpaths would therefore form an equivalence class.

Under this relation, two paths would be equivalent if they have the same start vertex, the same end vertex, and the same set of interior vertices.

Does this equivalence class have a name? If so, are there any TSP optimization algorithms that make use of this?

The 2-OPT heuristic for finding TSP tours is fairly close to what you're asking about. It's a local improvement algorithm which looks for sections of a TSP tour which, when reversed, will yield a shorter tour. The 3-OPT and the Lin-Kernighan heuristics work along the same lines, but use more complicated moves.

Looking for the optimal rearrangement of some subpath of a TSP tour is going to be inefficient unless it only involves a short section of this tour, and then I imagine it will be inferior to more global rearrangement algorithms such as 2-OPT (which can reverse a large subpath of a tour).

As far as I know, the concept that you're asking about has no name.


Dynamic Data structure for All nearest smaller values I need a data structure that stores a sequence of numbers and supports the following operations.  The input to each operation includes the position of an item in the current sequence (not the value or the memory address of that item).

$\mathtt{NearestSmaller}(i)$: Return the value of the last item in the sequence that occurs before position $i$ and whose value is less than the value at position $i$.
$\mathtt{InsertBefore}(x, i)$: Insert a new item with value $x$ into the sequence just before the item with position $i$.
$\mathtt{Delete}(i)$: Delete item at position $i$ from the sequence.

In short, my question is whether there is a dynamic version of the all nearest smaller neighbors algorithm.

For example, if the current sequence is $X = [9,7,3,1,8,12,10,20,15,5]$, then

$\mathtt{NearestSmaller}(6)$ should return $8 = X[5]$, and
$\mathtt{NearestSmaller}(10)$ should return $1 = X[4]$.

If you modify a balanced binary search tree (whose inorder traversal is the sequence order) so that each node stores the minimum value of its descendants (and if you know the path to x) then you can easily find the nearest smaller value: it must either be on the path to x, or in a left subtree descending from the path. In the first case, you have a logarithmic number of nodes to check, and in the second case you can use the extra information to find the closest left subtree with a value smaller than x and then descend through it along the rightmost path that still has a value smaller than x. So the time per query or update is logarithmic.

Edited to add: Now that you have clarified that you want to identify items in the sequence by their position, you should also augment the search tree so that each node stores its number of descendants. With this information, it is straightforward to find the path to the item at position $i$, in logarithmic time, matching the time described above for the NearestSmaller query.


What is the fastest known algorithm for finding conjugacy classes? Given a finite group $G$ of size $n$ by the table representation. I want to compute the conjugacy classes of group $G$. A trivial algorithm seems to take $O(n^2)$ operation ( $b = g^{-1}a g$ type checking ). For each pair (I know I don't need to do for all pairs ) of elements in $G$ check $b = g^{-1}a g$. I tried to search on internet but did not find anything specific about it in general.

Question : What is the fastest known algorithm for finding conjugacy classes?

I believe this can be done on $O(n \log n)$ on a RAM, where $n=|G|$; I don't know a reference so I'll just write it down here (but surely this is not original). Nor do I know if this is the fastest known, but clearly you can't do it faster than $\Omega(n)$, so it's gotta be close.

Let's assume the group elements are denoted in the computer by the integers $1,\dotsc,n$, with $g_i \in G$ being the group element corresponding to the integer $i$. Assume WLOG that $g_1$ is the identity.

1) Find a generating set $\Gamma$ of size $\leq \log_2 n$ in $O(n \log n)$ time:

G = list of group elements
Gamma = []
Gr = new graph with vertex set G and no edges           // O(n) steps
found = new array of length n, initialized to all false // O(n) steps
for i = 2 to n: // never need to add identity to generating set
    if not found[i] then
        Gamma.append(i)
        // Now update the graph Gr by adding new edges
        // Corresponding to the new generator G[i]=g_i
        for each vertex g in Gr:
            Gr.addEdge(g,g*G[i])
        end for
        do BFS on Gr starting from 1, ignoring any vertices already found
        (for any vertex j encountered, this sets found[j]=true)
    end if
end for

2) Build the following sparse graph (that is, in the edge list representation, not the dense adjacency matrix representation): vertices are the elements of $G$, and there is an (undirected) edge $(g,h)$ if $h = \gamma g\gamma^{-1}$ for some generator $\gamma \in \Gamma$. This is a graph with $n$ vertices and maximum degree $O(\log n)$. Its connected components are the conjugacy classes, and finding them can be done by BFS (say) in time $O(v + e) = O(n + n \log n) = O(n \log n)$.


What is the fastest algorithm to compute rank of a rectangular matrix? Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns?

I am aware it can be solved through linear matroid intersection, which implies
an $O(mn^{1.62})$ time deterministic algorithm and an $O(mn^{\omega-1})$ time randomized algorithm. Is there an $O(mn^{\omega-1})$ time deterministic algorithm that more directly reduce the problem (or Gaussian elimination) to matrix multiplication?

You can bring a $2n \times n$-matrix into echelon form in time
$O(n^{\omega + \epsilon})$ for any $\epsilon > 0$. See the book "Algebraic Complexity Theory" by Bürgisser, Clausen, Shokrollahi, Section 16.5.

Now you apply this procedure $m/n$ times to your $m \times n$-matrix.
This gives an algorithm with $O(mn^{\omega-1})$ arithmetic operations.

If you bring an $2n \times n$-matrix into echelon form, then it contains
a zero matrix of size $n \times n$ afterwards. You take the remaining $n \times n$-matrix,
add a new $n \times n$-block of your input matrix and bring this to echelon form and so on.


Is there a planar 4-regular graph that is 3-acyclic colourable? A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours).

Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me that no planar 4-regular graph is 3-acyclic colourable (might be even true for 4-regular graphs in general).

Am I wrong?
Is this already studied? (I admit I couldn't find any).

I can prove that no 4-regular graphs are 3-acyclic colorable.

Consider a 4-regular graph with a 3-coloring. If we call the colors $a, b, c$, then one of the three subgraphs generated by restricting to either $a$ and $b$ colored vertices, $a$ and $c$ vcertices, or $b$ and $c$ vertices must have as many edges as vertices. But all graphs with as many edges as vertices contain a cycle, so the coloring is not acyclic.

Let the graph have $k$ vertices. The graph must have $2k$ edges, because it is 4-regular. Let the number of $a$ colored vertices be $k_a$, and similarly for $k_b$ and $k_c$. Call $e_{ab}$ the number of edges between $a$ and $b$ colored vertices, and the same for $e_{ac}$ and $e_{bc}$. If we assume that none of the restricted graphs have as many edges as vertices, we must have
$$
e_{ab} < k_a + k_b \\
e_{ac} < k_a + k_c \\
e_{bc} < k_b + k_c \\
$$
Summing over all edges, we find that $e_{ab} + e_{ac} + e_{bc} < 2(k_a + k_b + k_c)$, and so $e < 2k$. But this contradicts the fact that 4-regular graphs have twice as many edges as vertices, mentioned above. Thus, the assumption is false, and some color-restricted subgraph has as many edges as vertices, and hence has a cycle.


is "spaghetti sort" really O(n) (even as a thought experiment) ? I`m referring to the notion described here: http://en.wikipedia.org/wiki/Spaghetti_sort

In the analysis section the author admits that considering it to be O(n) requires the assumption that the act of identifying and then removing the longest spaghetti rod which
has stopped your hand from descending further is an O(1)  rather than an O(n) or O(logn) operation - this seems to me a rather unreasonable assumption especially if many rodes of relatively simillar height exist.
Alternatively it seems equivalent to assuming that one can pick the longest rode from a heap of rodes arbitrarily spread on a table at O(1) without going through the "leveling" procedure at all.

The folklore analysis of spaghetti sort assumes a model where one can extract the longest noodle in constant time, perhaps by lowering a horizontal plate ("hand") over the vertical noodles until it stops, and then extracting the noddle touching the plate.  (Apparently the plate is pastamagnetic.)  Within this perfectly well-defined theoretical model, the analysis is clean and obviously correct.

So is the pastamagnetic-plate model reasonable?  For up to a few hundred strands of spaghetti, sure.  Beyond that, obviously not.  So should we make the model more reasonable by taking the physical costs of moving the plate, sensing collisions, or  choosing the right noodle?  What about the (nonzero!) physical cost of keeping all the noddles vertical (or at least parallel), and keeping the sensing plate and the table horizontal (or at least parallel to each other but not the noodles)?  Should we worry about the measuring process causing micro-fractures that change the exact length of the noddles, or the implication from quantum mechanics that there is no such thing as "exact length"?  Holy crap, is the spaghetti-sorting problem even well-defined?!

No, this way lies madness.  The original theoretical analysis is predictive within the context for which the algorithm was designed — manually sorting a handful of pasta #8.  That the analysis does not generalize to significantly larger values of $n$ or other types of pasta does not make the analysis "incorrect".  It merely limits its scope.


$L_0$ estimation, not in a stream What is the current state of the art for $L_0$ estimation when not in a stream?  I assume that the total number of (not necessarily distinct) objects is very large so you can only see a sample of them.

I found http://en.wikipedia.org/wiki/Good%E2%80%93Turing_frequency_estimation but that seems rather older than I was expecting.

For sampling-based algorithms, nearly tight upper and lower bounds are known for the query complexity of estimating the number of distinct elements in a sequence.

Charikar, Chowdhuri, Motwani and Narsayya showed that multiplicative approximation of the number of distinct elements to within a factor $\alpha$ can be achieved with $q= O(n/\alpha^2)$ queries into the sequence.

Here's the algorithm. Sample $q$ items uniformly at random from the sequence. Let $d$ be the number of distinct items in the sample, and let $f_1$ be the number of items that appear exactly once in the sample. Then, output $d + \sqrt{n/q} \cdot f_1$.

The analysis is also very clean. Assume without loss of generality that each element in the sequence is an integer in $[k]$, where $k$ is the number of distinct elements. Let $p_i$ be the probability of selecting $i$ when sampling uniformly from the sequence. Then, the expected output of the estimator is:

$$\mathbb{E}[d + \sqrt{n/q}\cdot f_1] =  \sum_{i=1}^k (1 - (1-p_i)^q) + \sqrt{n/q} \cdot p_i q (1-p_i)^{q-1}$$

Now, the point is that for any valid $p_i$, the value inside the summation is between $\Omega(\sqrt{q/n})$ and $O(\sqrt{n/q})$. (This uses the fact that $1/n \leq p_i < 1$.) So, the expected output of the algorithm is within $O(\sqrt{n/q})$ of $k$.

Charikar et al.'s estimator can also be used to get an additive approximation of the number of distinct elements. One can estimate the number of distinct elements upto $\pm \beta n$ by making $O((1-2\beta) n)$ samples. This was the state-of-the-art for a long while until STOC '11 when Greg and Paul Valiant showed that it's possible to reduce the sample complexity and time complexity to $O(\frac{n}{\beta^2 \log n})$. Their algorithm is based on a very general result that, given a probability distribution $D$, constructs a distribution $D'$ using $O(n/\log n)$ samples such that $D$ and $D'$ are close to each other in relative earthmover distance. So, one can make sure that the support size of $D'$ and the support size of $D$ are only an additive $\beta n$ away from each other.

As for lower bounds, Charikar et al. showed that for $\alpha$-multiplicative approximation, $\Omega(n/\alpha^2)$ queries are needed. The proof stems from the observation that $\Omega(n/\alpha^2)$ queries are needed to distinguish $n$ identical items from the same sequence with $\alpha^2$ unique elements inserted in random locations. For additive approximation, however, this bound is sort of trivial; for constant $\beta$, this would only give a constant lower bound on the query complexity. Raskhodnikova, Ron, Shpilka, and Smith showed a nearly linear bound even for additive approximation. Specifically, they prove that estimating to within additive error $n/23$ requires $n/2^{\sqrt{\log n} \log \log n}$ queries. The Valiants in their above-cited paper showed a lower bound of $\Omega(n/\log n)$ for estimating to any additive error less than $n/4$, implying that their upper-bound is tight upto constant factors.


Counting subsets with large sum Suppose that you have a multiset of positive integers $I$.

$I$ is not given, but it is known that the sum over all elements of $I$ = $k$.

(e.g. if $I$={2,5,7} then k=14 is given, but I is unknown).

We are also given another integer $r$.

$S\subseteq I$ will be called $r-minimal-subset$, if $sum(S)>r$,

and for every $x\in S$, $sum(S$\{x}$) \leq r$.

For example, if $I$={1,3,3,5,7,8} and r=10,

then {3,3,5} and {1,3,7} are r-minimal-subset, but {5,7,8} is not (as the subset {7,8} 's sum is 15. {7,8} is a r-minimal-subset).

What is the the best upper bound we can give on the number of $r-minimal-subsets$ of I?

(In this setting, we get is $(r,k)$, while $I$ is being chosen by an adversary).

~~~~~~~~~~~~~~~~~~~~~~~~~~

Edit:
Hmm, sorry for the question.

Obviously the answer is $k \choose r+1$, for I={1,1,..,1}, $|I|=k$.
It doesn't let me answer the question, so you could go ahead :/.

Let me know if I understood the question correctly: you want to count the sets of $n$ positive integers summing exactly $k$, right? This is $\binom{n+k+1}{k}$. If you want for non-negative integers version, add one more number to the count, $\binom{n+k+1}{k+1}$.


Ways to think formally about Satisfiability Modulo Theories Apologies if this is not a well-thought-out question, but I am interested in formalizing a problem which is ultimately described by a SMT formula in the theory of quantified arrays and linear arithmetic, and I realized that, while I understand what SMT formulas are useful for in a practical sense, I do not have a good sense for how to fit what I know about foundations of logic/computing/type theory/category theory with the idea of SMT theories and formulas.  What can be said formally about the general theory about statements which can in some way be turned into SAT instances?

Edit: I understand that SAT solvers work with propositional logic and SMT solvers work with fragments of first-order logic, but how exactly do we understand what a "fragment of logic" is and how it chops up the whole universe of first-order logic?  Obviously we have different predicates and functions for linear arithmetic vs the theory of data types, but how at a formal level can we come up with a mathematical universe in which certain statements can be combined and others can't?

It's actually surprisingly hard to relate SMT to type-theoretic/categorical approaches to logic -- the results in this area are very recent! This is because categorical logic is primarily conceived of as a semantics of proofs, and SMT arises from the model-theoretic view of logic, which is a semantics of provability.

A formula in SMT is a boolean combination of primitive assertions over some theory. For example, for linear arithmetic you might have the following terms and primitive formulas.

$$
\newcommand{\bnfalt}{\;\;|\;\;}
\array{
\mbox{Terms} & t & ::= & x \bnfalt n \bnfalt t + t \bnfalt -t \\
\mbox{Primitive Formulas} & p & ::= & t \leq t \bnfalt t = t \bnfalt t < t \\
\mbox{SMT Formulas} & \phi & ::= & p \bnfalt \top \bnfalt \phi \land \phi' \bnfalt \lnot \phi \\
}$$

Given a formula $\phi$, an SMT solver will either give you a satisfying assignment for the variables -- i.e., it will give you a number for each variable, such that substituting that number for each variable gives you a true boolean formula -- or it will tell you that the formula $\phi$ is unsatisfiable.

The fact that this is all happening in classical logic is quite important; the architecture of SMT solvers relies upon this fact. Basically, SMT solvers are built as a combination of an DPLL-based SAT solver, which communicates with a theory solver, which deduces equalities from pure conjunctions of theory formulas. There are also various conditions under which you can combine solvers for different theories, which is important because it gives researchers a good "API" for figuring out if particular theories will fit together nicely.

A good reference to the standard view of SMT is Clark Barrett and Cesare Tinelli's handbook chapter on Satisfiability Modulo Theories.

Work on how to interpret SMT in terms of proof theory is much newer. The basic idea is to relate DPLL(T) with "focused" or "polarized" calculi for proof search. Focused calculi are variants of the sequent calculus originally designed to optimize proof search, but which turned out to work because they expose fundamental ideas in proof theory.

Two good references to this are
Mahfuza Farooque's PhD thesis, Automated reasoning techniques
as proof-search in sequent calculus, in which she relates the actions of a DPLL(T) algorithm to search in a particular focused calculus, and Stéphane Graham-Lengrand's habilitation thesis Polarities & Focussing: a journey from Realisability to Automated Reasoning, in which he gives a broader perspective on this work (eg, by connecting it to work on biorthogonality).


converse relationship between the cut rule and the identity axiom On page 30 of "Proofs and Types" by Girard, Taylor, and Lafont, it is claimed that that the identity axiom for sequent calculus:

C ├ C

has a converse relation with the cut rule:

$$\frac{\vec{A} \vdash C,\vec{B}  \qquad \vec{A'},C \vdash \vec{B'}}
      {\vec{A},\vec{A'} \vdash \vec{B},\vec{B'}}$$

The explanation it gives is that the in the identity axiom, C on the left is stronger than C on the right. With the cut rule, it claims, C on the right is stronger than C on the left. While the claim about the identity axiom seems to follow from basic notions of sequents, I do not understand the claim about the cut rule. Could someone explain this?

Girard is talking about intuitionistic sequents, in which sequences to the right of the turnstile have length at most 1. So in the premiss of the cut rule, the sequence of formulas $\vec{B}$ is empty. We can rewrite the cut rule as follows, writing $B^?$ for a sequence which is either empty or contains a single formula.

$$
\frac{\vec{A} \vdash C \qquad \vec{A'},C \vdash B^?}
     {\vec{A}, \vec{A'} \vdash B^?}
$$

Now, it's easy to see why Girard says $C$ on the right is stronger -- it is the only formula that occurs to the right in the first premiss.


How can I optimize my brute-force solution to this problem? I am working on a solution to the problem explained below. I am using brute force, I have reached the point where solutions are prohibitive, so I need to optimize more (if possible).
Of course, it will be even better if there is a better way to solve the problem (not brute force).
Is there anything I can do to improve my solution, or reference I can look into (similar problems, etc)?
The problem
We start with a rectangular board. Each cell can be in N states, and the initial state for each cell is random (0 <= state < N) for each cell.
We also have a number of shapes, all fit inside the board. Every shape is continuous.

Each shape must be placed once (and only once) in the board.
When a shape is placed, each cell that belongs to the shape will have its value increased by 1. If the board value in any cell reaches N, it is changed to 0.
The goal is to find the positions each shape must be placed so that the final board has all cells with value 0. There is always at least one solution. Let's suppose the problem is generated by starting from the finished board and applying random shapes in random positions.

The board size, number of states N and number of shapes are the setup of the game, and keep increasing (at different rates) for each 'level'.
What I am doing currently
I am able to solve the problem up to a certain size by just using brute force. I have a few optimisations in place. I have reached a point where the solution is prohibitive, so I would like to improve my logic.
First thing I am doing is order the shape from larger to smaller, the smaller will be moved in the internal iterations. The assumption (which I haven't proved, but tested to be faster) is that it's better to move the smaller shapes more, since they have a higher chance to generate a solution.
Secondly, for repeated shapes, I avoid checking all the permutations, since they yield the same result. I also only check one set of positions when a pair of same shapes overlap (since all overlaps yield the same result).
One final optimisation that I think will help a lot, but I am still implementing is: at each shape in the sequence, count the total of cells in the shapes that remain to be moved. This number, minus the total cell flips needed to get a finished board, must be a multiple of N. If not, it's no point brute forcing the remaining shapes positions, and we must re-position a shape in an external loop.
Extra details
I am interested in any other tips on how to optimize this. Known algorithms, even a good naming for this set of problem, that I can use to research more would be great.

Integer linear programming
Your problem can be formulated in the following way: we are given vectors $v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, where the board has $d$ cells, and the goal is, given a vector $c \in (\mathbb{Z}/N\mathbb{Z})^d$, find a function $f$ so that $\sum_i v_{i,f(j)}=c$.  This problem could then be solved by integer linear programming.  This is related to a $d$-dimensional subset-sum problem, so you might also be able to find other algorithms for multi-dimensional subset-sum and try them out as well.
How do we formulate it in that way?  If the grid has $d$ cells, we can think of a shape as a $d$-vector of 0's and 1's, with 1's in the cells covered by the shape.  Each shape can be placed in a number of different positions, yielding different vectors.  $v_{i,j}$ corresponds to the $j$th place where shape $i$ can be placed.  $c$ corresponds to the the numbers originally in the grid (well, the negation of those numbers, modulo $N$).  All arithmetic is done modulo $N$.
Slightly smarter brute force
Alternatively, here is a way to improve brute force a little bit, by trading memory for time.  Suppose you have $k$ shapes.  Start by enumerating all ways to place the first $k/2$ shapes onto an empty board of all zeros, and store all resulting positions in a hashtable or sorted list.  Then, enumerate all ways to place the last $k/2$ shapes onto the starting position, and look up each of the resulting positions in the hashtable or sorted list.  If you find any match, then that yields a solution.  This will let you push brute force a bit further -- potentially to about twice as many shapes -- if you have an unlimited amount of memory.  There are a lot of details involved in optimizing this to the max, but it's an idea you could consider if you brute force gets you close but falls a little bit short.  It is still an exponential-time algorithm so it will still hit a limit.


Non-invertibility of RSA for two users In chapter 8 (page 288) of the "Handbook of Applied Cryptography," the authors describe an attack against RSA with small exponent. Let there be 3 parties with independent RSA public keys $(e_1,n_1)$, $(e_2,n_2)$, and $(e_3,n_3)$, with $e_1=e_2=e_3=3$. With very high probability, the moduli are coprime; otherwise, it would be possible to factor them.

Consider a forth party, who wishes to secretly send a single message $m$ to the 3 parties above. He computes $c_i = m^3 \pmod{n_i}$, and sends $c_i$'s on the channel. The adversary, who eavesdrops the ciphertexts, can simply apply the Chinese Remainder Theorem to recover $m$. (See the above chapter for exact computations.)

  My question is: Assume that there are only two recipients, instead of three. Given $c_1$ and $c_2$, is it possible to prove (under the RSA assumption) that the adversary cannot recover $m$ (except with negligible probability)?

More formally, let $G$ be an RSA public-key generator, and $A$ be a PPT adversary. Is it possible to prove, under the RSA assumption, that the success probability of $A$ is negligible in the experiment below?

$(e_1,n_1) \leftarrow G(1^k)$ and $(e_2,n_2) \leftarrow G(1^k)$
$m \leftarrow_R \{1,\ldots,\min\{n_1,n_2\}\}$
$c_1 \leftarrow m^{e_1} \pmod{n_1}$ and $c_2 \leftarrow m^{e_2} \pmod{n_2}$
$m' \leftarrow A(e_1,n_1,e_2,n_2,c_1,c_2)$
IF $m'=m$ OUTPUT "$A$ succeeded"; ELSE OUTPUT "$A$ failed".

PS: One can assume any technical condition to make the proof work; say $e_1=e_2$.

What you're asking for has been called "correlated product" security for a trapdoor function.  See this paper by Rosen and Segev, which lays out the definition.  Your question fixes $k$ from their Definition 3.2 to $2$;  as you (and their paper) note, we know that the RSA trapdoor function with exponent $e\leq k$ is not correlated-product secure.

I don't know how to give a reduction to plain RSA to prove what you want, and I'd guess that it's very hard.  The best I can think of is to try to prove this under the so-called Phi-hiding assumption (see Cachin, Micali, Stadler, Eurocrypt'99, or reference below).  This may follow by combining Theorem 3.3 of 1 (which says that a lossy trapdoor function is correlated-product secure) with Section 5 of this this paper by Kiltz, O'Neill, and Smith that shows the RSA function is lossy under that assumption.  I haven't checked that the parameters works out, though.


Purely(ish) functional data structure with fast append and forward iteration I find I have need for a data structure with a specific set of requirements:

It represents an immutable sequence of values (fixed sized integers if this matters)
Appending a new value to the end (and returning a new sequence) needs to be extremely fast and memory efficient. Ideally amortised O(1) and sharing the entire prefix, but there's no specific hard complexity requirement and O(log(n)) would probably be OK too.
Getting the length of a sequence needs to be cheap (obviously I can add this in after the fact with a wrapper if necessary)
I need to be able to efficiently iterate the sequence in the forward direction
I need to be able to lexicographically compare two sequences of the same length in the forward direction efficiently (this follows from the previous property, but might have simpler implementations and has fairly specific iteration patterns)
Sharing of prefixes is very common in the expected workloads, so solutions like vlists or copy-on-append aren't practical because the workload will essentially always trigger a full copy.
(practical rather than theoretical constraint but...) The simpler the design the better, because I'm almost certainly going to have to implement this from scratch in a couple of different languages, including C (with reference counting)

Non-constraints:

Although the data structure itself has to represent immutable sequences, I don't mind a certain amount of mutation of the values if it's invisible (it would be nice to avoid)
I certainly don't mind depending on e.g. some source of randomness
It's OK if the forward iteration depends on some sort of external data structure with extra space requirements

Obviously the ideal would be to just have a length prefixed cons list, but the forward iteration requirement makes that sub-optimal.

The following are the two things I've considered so far:

Just use a cons-list anyway and reverse it in an external buffer prior to iteration. Downsides: Forward iteration becomes fairly expensive, particularly
for cases where I'm likely to stop the iteration after only one or two elements (which is a common case because of lexicographic comparison being a major use case here).
A tree of bounded balance - it stores the size efficiently, has relatively cheap append and iteration. Downsides: Kinda fiddly to implement correctly, unclear whether the relatively high constant factors and the logarithmic complexity make it a win in practice.
A skip list. Downsides: Same as the upsides really - it's about halfway between the previous two in terms of complexity and performance. Requires more book-keeping for iteration than the others, but it's probably tolerable.

So of the three the skip list looks like it might be the best option and "just use a cons list and optimise later" looks like the one I'm most likely to start with, but I'm not exactly well versed in the purely functional data structure literature, so I was hoping there were a better option I was overlooking. Any suggestions?

You're quite right that the "queue = two lists" approaches don't give you the running time you want when you have the ability to re-use earlier versions.  To get O(1) running time (amortized or worst case), you need a way to reverse the rear list and append it to the front list incrementally.  Instead of doing the reverse&append all at once, taking O(N) time, you need to be able to do just a few steps of the reverse&append every time you add a new element or remove/traverse through an element.

Hood and Melville showed one way to do this back in 1980.  For your purposes, their approach would be straightforward to adapt to C (with reference counting).

In the early to mid 90's, I showed several ways to do this, some in O(1) worst-case time and some in O(1) amortized time. Most of these ways depended on lazy evaluation, which initially might seem hard to do in C, but in fact, there are only a very small of "shapes" needed for the lazy evaluation, each of which would be easy to represent using an ordinary node in C.

For example, a "Rotate" node has pointers to three sublists: L, R, and A.  Doing one step of the rotation replaces the "Rotate" node with an ordinary list node containing the head of L, and a pointer to a new Rotate node containing the tail of L, the tail of R, and the result of adding the head of R to the front of A.  Making this translation into explicit Rotate nodes instead of using generic lazy evaluation also means that you get O(1) worst-case bounds instead of O(1) amortized bounds.


Can Merlin convince Arthur about a certain sum? Merlin, who has unbounded computational resources, wants to convince Arthur that
$$m|\sum_{p\le N,\ p\text{ prime}}p^k$$
for $(N,m,k)$ with $k=O(\log N)$ and $m=O(N).$  Computing this sum in the straightforward way (modular exponentiation and addition) takes time $N(\log\log N)^{2+o(1)}$ with FFT-based multiplication.*  But Arthur can only perform $O(N)$ operations.

(Notation, for compatibility with earlier versions of this question: Let the sum equal $m\alpha$; then the question is whether $\alpha$ is an integer.)

Can Merlin convince Arthur with a string of length $O(N)$?  If not, can he convince Arthur with an interactive proof (total communication, of course, must be $O(N)$)?  If so, could Merlin use a string of length $o(N)$? Could Arthur use $o(N)$ time?

Arthur has no access to nondeterminism or other special tools (quantum methods, oracles other than Merlin, etc.) but has $O(N)$ space if needed.  Of course Arthur need not compute the sum directly, he merely needs to be convinced that a given triple (N, m, k) makes the equation true or false.

Note that with $k=0$ it is possible to compute the sum in time $O(N^{1/2+\varepsilon})$ using the Lagarias-Odlyzko method.  For $k>0$ the sum is superlinear and so cannot be stored directly (without, e.g., modular reduction) but it's not clear whether a fast algorithm exists.

I would also be interested in any algorithm to calculate the sum (modular or otherwise) other than by direct powering and addition.

* $N/\log N$ numbers to calculate, time $\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$ for each calculation.

I am posting this seperately from my earlier special case, because I believe it is a different approach to the problem, and has little relation to my other answer. It may not be exactly what you are looking for, but it is simple, and gets close.

There is a proof which Arthur will always accept whe the proof is correct, but will reject with probability $\frac{1}{(\log \log N)^{2+o(1)}}$. Here's how it works: Merlin sends Arthur the pair $(p_i,c_i = p_i^k\mbox{ mod }m)$ for each prime $p\leq N$. Arthur verifies the sum (taking time $O(N/\log(N)) \times O(\log(N)) = O(N)$). Arthur the checks that the correct number of primes was supplied (by calculating $\pi(N)$) which is sublinear in $N$. Lastly, for $S N$ random pairs, he confirms that $p$ is prime and that $p_i^k \equiv c_i \mbox{ mod }m$. This takes time $SN~O((\log \log N)^{2+o(1)})$. Taking $S = (\log \log N)^{-(2+o(1))}$, we obtain a linear time scaling. Thus, a fraction $S$ of all pairs are verified. If any of these fail, Arthur will of course reject. For Arthur to accept an incorrect proof, there must be at least one pair which fails one of these two tests (or the number of pairs must be less than $\pi(N)$ which was earlier checked). Thus as a fraction $S$ of all pairs are checked, the test will fail for an incorrect proof with probability at least $S$.

Note that for large $N$ this is much much better than random guessing, which succeeds with probability $\frac{1}{m} = \frac{1}{O(N)}$.


Extending semigroup theory? In an earlier question I proposed a definition of associativity for ternary relations generalizing the usual notion for composition laws. I'm still not sure whether this definition makes sense, but if so this leads to some interesting algebraic questions. In particular, what parts of "semigroup theory" can be extended to that setting, if any?

Consider such a relation $\cal{R}$ over $X$. Similar to semigroup theory, we can give the following definitions:

a set $S \subseteq X$ is a "substructure" if $a,b \in S$ and $\cal{R}(a,b,c)$ holds imply that $c \in S$;
a set $L \subseteq X$ is a "left ideal" if $a \in L, b \in X$ and $\cal{R}(a,b,c)$ holds imply that $c \in L$;
a set $R \subseteq X$ is a "right ideal" if $a \in X, b \in R$ and $\cal{R}(a,b,c)$ holds imply that $c \in R$;
given a substructure $S$, we can define an order relation $\leq_S$ such that for any $a,a' \in X$, $a \leq_S a'$ iff for every $b \in S,c \in X$, $\cal{R}(a,b,c)$ implies $\cal{R}(a',b,c)$. We can also define an equivalence relation $\equiv_S$ as $\leq_S \cap \geq_S$.

This leads to some natural questions: (i) what are the conditions on $S$ such that $\cal{R} / \equiv_S$ behaves as a substructure? (ii) how do chains of ideals behave with respect to inclusion? (iii) are there some possible generalizations of the isomorphism theorems? (iv) are there some connections with automata and possible extensions of Krohn-Rhodes theory?

This is probably pie in the sky though, as I don't even have any concrete example of such a structure...

The structure you suggest is known as a 'semihypergroup', a notion introduced by F. Marty in 1934. According to Google, some of your questions have already been attacked by a diverse community of mathematicians involving Greeks, Iranians and Thai people. The most challenging question seems point (iv) but I'm unsure about the outcome, though a positive result in that directions would probably have far-reaching consequences -- possibly in relation with Rhodes' interest in the separation of complexity classes.


How to implement a functional programming language efficiently? Thanks to Petr and Andrej for their feedback.
I'm rephrasing my question and give a bit of a context:

Functional programming languages are mostly based on lambda calculus.
Implementing a functional language straight forward is inefficient on today's hardware. For example:

\begin{eqnarray}
f &\equiv&\ \lambda x.\lambda y.\ x+y \\
g &\equiv&\ f\ v
\end{eqnarray}
Those functions will have the following types:
\begin{eqnarray}
f &\colon& a \rightarrow b \rightarrow c  \\
g &\colon& a \rightarrow b
\end{eqnarray}

Now the function $g$ needs to store the variable $v$ in an runtime environment, when the variable $v$ is only accessible in a specific context.
This concept is known as closure.

I'm looking for an method to eliminate all closures in a given program and avoid the allocation of environments at runtime.

Is this even possible?
What are the disadvantage of such an algorithm?

Thanks to Petr for mentioning the S-K basis.
As I understand, the combinator graph reduction will put any function in a point-free style. However by applicate arguments partially, there is still some form of environment necessary.

Original question:

Is a purely functional programming language like Haskell still turing
complete without the concept of closures?
Or the other way around: Is it possible to eliminate all closures in
a Haskell program in order to use no heap space?

It's not entirely clear what do you mean by a functional programming language without closures. Can you give an example?

Functional programming languages are usually based on lambda calculus, whose essential part is that you can have open lambda terms. For example the term for the constant function (the K-combinator) $\lambda x . \lambda y . x$ can be viewed as a function that given $x$ returns a constant function that returns $x$ on any argument - a closure of the open term $\lambda y . x$.

However you can use another basis, a combinatory calculus such that it's power is equivalent to the lambda calculus. Then you can take a lambda term and convert it into an equivalent combinator that doesn't use any variables at all, so there are even no closures to talk about - see Completeness of the S-K basis. Which I believe answers yes to your question.

This is actually what Haskell compilers do under the hood. Evaluating lambda terms with variables is very inefficient and cumbersome, so they convert the program to a representation without variables and use techniques such as combinator graph reduction.

I can recommend two books on the subject which are both available online, the first one more theoretical, the second one focused more on the actual implementation techniques:

The Implementation of Functional Programming Languages, Simon Peyton Jones, published by Prentice Hall, 1987.
Implementing functional languages: a tutorial


Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct integers $p_1, \ldots, p_n$, the sequence $\mathbf{p}$ is a subsequence of $s$, i.e., there exist $1 \leq i_1 < i_2 < \cdots < i_n \leq |s|$ such that $s_{i_j} = p_j$ for all $1 \leq j \leq n$.

What is the complexity of the following problem? Is it in PTIME, or coNP-hard? Note that it is in coNP as you can guess a missing sequence (thanks @MarzioDeBiasi).

Input: an integer $n$, a sequence $s$ of integers in $\{1, \ldots, n\}$
Output: is $s$ $n$-complete?

The notion of $n$-complete sequence is known in combinatorics because people have investigated what is the length of the shortest $n$-complete sequences as a function of $n$ (see, e.g., this mathoverflow thread for a summary). However, I was unable to find references to the complexity of recognizing them. Note that in particular we can easily build $n$-complete sequences of length polynomial in $n$, namely, of length $n^2$, as $(1, \ldots, n)$ repeated $n$ times (any permutation $\mathbf{p}$ can be realized by choosing $p_i$ in the $i$-th block). Hence we cannot afford in general to enumerate all permutations.

I believe the problem to be coNP-complete.
I have uploaded it as an arXiv preprint.


Class of functions computable by Coq Since it does not allow nonterminating computation, Coq is necessarily not Turing-complete. What is the class of functions that Coq can compute? (is there an interesting characterization thereof?)

Benjamin Werner has proved the mutual interpretability of ZFC with countably many inaccessibles and the Calculus of Inductive Constructions, in his paper Sets in Types, Types in Sets.

This means, roughly, that any function which can be shown to be total in ZFC with countably many inaccessibles can be defined in Coq. So unless you are a set theorist working on large cardinals, it is unlikely that any computable function you have ever wanted cannot be defined in Coq.


Distance of arbitrary vectors to Hadamard code Let $n$ be a positive integer and $N = 2^n$. The Hadamrd code of "block length" $N$ can be generated using the inner product $f_u(x) = \langle u,x \rangle$ mod $2$ for all $u \in \{0,1\}^n$. It is straight forward to show that two different elements of the Hadamard code differ on exactly a fraction of $1/2$ of their values, e.g. their relative distance is exactly $1/2$.

What about the distance of arbitrary vectors to the Hadamard code? I've read in certain papers that this distance is also bounded by $1/2$ but other papers explicetely consider the case of vectors having distance $> 1/2$ to all elements of the code. Can anyone help me?

What you are asking is the covering radius of the Hadamard code. I am not sure what the answer is but the covering radius of the punctured Hadamard code is at least $\frac{N}{2} - \frac{\sqrt{N}}{2}$, i.e. any Boolean vector is at most $\frac{N}{2}-\frac{\sqrt{N}}{2}$ Hamming distance away from some code word of the punctured Hadamard code. The $O(\sqrt{N})$ advantage over $\frac{N}{2}$ is optimal for any set of $O(N)$ points in $\{0, 1\}^N$.

The punctured Hadamard code maps $x \in \{0,1\}^n$ to the sequence $(\langle x, u\rangle\bmod 2)_{u \in \{1\}\times\{0, 1\}^{n-1}}$. It's not hard to see that the distance of the code is still $N/2$ as in the Hadamard code, but the number of codewords is $2N$. If we map each code word to a vector in $\{-1, 1\}^N$ by mapping $1$ to $-1$ and $0$ to $1$ we get vectors $v_1, \ldots, v_N, -v_1, \ldots, -v_N$ such that $\langle v_i, v_j \rangle = 0$ for any $i \neq j$. Taking any $x \in \{0, 1\}^N$ and mapping it to $u := 1 - 2x$ in the same way, we see that $x$ is Hamming distance $d$ away from a codeword if there exists an $i$ such that $|\langle v_i, u\rangle| = N-2d$. In other words, it's enough to show that for any $u \in \{-1, 1\}^N$ there exists an $i$ such that $|\langle v_i, u\rangle| \geq \sqrt{N}$. But this follows from the properties of the $v_i$:
$$
\max_i |\langle v_i, u\rangle|^2 \geq \frac{1}{N}\sum_{i = 1}^N{|\langle v_i, u\rangle|^2} = \sum_{i = 1}^N{u_i^2} = N.
$$
The inequality is by averaging and the first equality is true because $\frac{1}{\sqrt{N}}v_1, \ldots, \frac{1}{\sqrt{N}}v_N$ is an orthonormal basis of $\mathbb{R}^N$.

The fact that no set of $O(N)$ points in $\{0, 1\}^N$ can cover $\{0, 1\}^N$ with radius $\frac{N}{2} - \omega(\sqrt{N})$ is equivalent to the fact that for any $v_1, \ldots, v_M \in \{-1, 1\}^N$, $M = O(N)$, there exists a vector $u \in \{-1, 1\}^N$ such that $|\langle v_i, u\rangle| = O(\sqrt{N})$ for all $i$. This is a restatement of Spencer's "Six Standard Deviations Suffice" theorem from discrepancy theory.


The class CFL\cap co-CFL Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment is obvious.)? I hope I'm not being stupid here--don't laugh at me too much if this is totally trivial. I ask this because I'm trying to pin down a commutative closure of a regular language over a binary alphabet, and it's clear that it lies inside this set, via a result showing that slip-languages over an alphabet of size two have context-free commutative closure.

For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.


Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet For a given finite alphabet $\Sigma$, my goal is to write an algorithm
that receives as input a sequence $V=V_{1}V_{2}\dots V_{n}$ of subsets
($V_{i}\subseteq\Sigma$), and returns a weighted deterministic finite-state
automaton with the following property: for every input string $s$,
the automaton penalizes each substring $s_{1}s_{2}\dots s_{n}$ of
$s$ if $s_{i}\in V_{i}$ for every $1\le i\le n$.

For example, if $\Sigma=\{a,b\}$, $V=V_{1}V_{2}=\{b\}\{b\}$, the
returned automaton would penalize the string $s=bbbb$ $3$ times,
i.e. when accepting the string and summing over the weighted arcs,
the result would be $3$.

The algorithm should return the weighted DFA as a 4-tuple $<Q,\delta ,q_0 , F>$:

$Q=\{q_{0},q_{1}\}$

$\delta=\{(q_{0},a,0,q_{0}),(q_{0},b,0,q_{1}),(q_{1},b,1,q_{1}),(q_{1},a,0,q_{0})\}\subseteq Q\times\Sigma\times\{0,1]\times Q$

$q_{0}=q_{0}$

$F=\{q_{0},q_{1}\}$

The algorithm must return the DFA as a 4-tuple as described. My main concern is the size of the resulting DFA. Therefore, the structure of $V$ should be taken advantage of. Capitalizing on subset relations, it is possible to eliminate states from the resulting automaton. For example, when all subsets are pairwise disjoint,
the automaton would have $n$ states.

The problem arises in the general case, where the inclusion relation
between subsets is unknown.

For example, if $\Sigma=\{a,b,c,d,e\}$ and $V=\{a,b\}\{b,c,d\}\{d,e\}$,
the string $abde$ should be penalized twice (both $abd$ and $bde$
are penalized), where $acde$ should be penalized only once ($acd$
is penalized, but not $cde$). This happens since there is a chain
of non-empty intersections between subsets $(V_{1}\cap V_{2},V_{2}\cap V_{3}\not=\emptyset)$,
so having accepted a penalized substring, some paths taken must be
remembered in order to know how to move on. Paths in the required automaton
would have to be splitted accordingly. In this case the resulting automaton could be minimally built with 5 states.

When the sequence is longer, there is a chance for more complex inclusion
relations between its subsets.

I'm interested in a general algorithmic solution for this problem, currently not in any implementation or performance considerations. As stated, my main concern is the size of the DFA.

Any insight, reference or suggestion on how to tackle this problem
would be appreciated.

More specifically, I'm now trying to figure out how to capitalize on inclusion relations between subsets in order to eliminate states (in advance) when building the DFA.

EDIT:
Added a paragraph and a final comment about using the structure of V to minimize the DFA, emphasis on my need of a smallest DFA as possible.

I'm still not sure why you want it in strict quadruple form, with a set of structure-less states. That's a model that mainly intended for doing the abstract mathematics surrounding state-transition systems, but famously ill-suited to actual computation unless you are looking for the extreme speed offered by "pre-compiling" into deterministic form, at the expense of storage space.

User834 is correct that this is a fairly simple sub-problem of regular expression matching, with the added feature of counting matches, so you may take my solution in that vein.  I'm not a RE maven, but I think there is a way to get match counting out of REs in most implementations. So that's an approach you might consider for practical implementation without all the trouble of constructing your own FSAs.

I also agree that this probably belongs in the CS area rather than theoretical CS.

If I read your problem correctly, it amounts to taking a set of strings $V$ and looking for every occurrence of a string in $V$ as a maximal substring (prefix, suffix or interior) of $x$, the input to the DFSA we'll call $D$. That count is the "penalty" for $x$. Here's one way to do it, though following your prescription not to worry about performance, takes no advantage of any structure or redundancy in $V$.

In your example, $V=\{abd, abe, acd, ace, add, ade, b...\}$. Pre-multiply all the sets $V_i$ into strings of $V$ in tree form, with elements of $V_i$ all on level $i$, each descended directly from each element of $V_{i-1}$. Level $0$ is an abstract root, say $\epsilon$. For your example, descended from $\epsilon$ are $a$ and $b$, the elements of $V_1$. On level 2, descended from each of $a$ and $b$ are the members of $V_2$: $b$, $c$ and $d$. So there are 6 nodes on level 2 altogether, the 3 members of $V_2$ repeated twice. And so on to the leaves.  Each path from $\epsilon$ to a leaf of the tree represents one "penalty string" in V. You did not make clear what happens if a string appears more than once in $V$. If you don't want it to count for multiple penalties, then you should prune duplicate strings out of the tree by some suitable algorithm.

Construct the a non-deterministic FSA $D'$ as follows.  States of $Q$ are pointers to nodes of the tree. Each state thus represents a complete string in $V$ or a prefix of such a string, to be represented here by $[x]$ (though that $x$ isn't unique to a node -- I assume there is a pointer to the actual node of the tree).  The transition function $\delta$ contains three kinds of edges:

$\langle[x],a,0,[xa])\rangle$ where $a$ is a direct descendant of $[x]$, and $[xa]$ is that descendant node. Note that we output 0 at this point because we aren't sure we've reached the maximal match.

$\langle[x],a,1,[])\rangle$ where $a$ is not a direct descendant of $[x]$ in the tree, and $[]$ is a dead state. We output $1$ here because $[x]$ is matched but it is maximal, since $[xa]$ is not matched.

If we were dealing with prefixes only and not interior and suffix matches, we'd be done and this would be a deterministic automaton. To account for non-prefixes, we need to non-deterministically circle back to $[\epsilon]$, the start state, at every stage with an edge like this for every state $[x]$ except $[\epsilon]$ and $[]$:

$\langle[x], \epsilon, 0, [\epsilon]\rangle$

Convert that NFSA to a DFSA and you are done.


Count $k$-hop neighborhood for every vertex For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with  $k$ edges or fewer).  I would like to compute the cardinality of this $k$-hop neighborhood for very node $v$ in $G$.

One option is to simply raise the adjacency matrix of $G$ to the power $k$ using Boolean arithmetic and then sum the rows.  This is however rather slow and seems wasteful (consider for example the complete graph or a very sparse graph). Another approach is to naively search from each node but this is at least $O(n d^k)$ time for a $d$-regular graph, for example. This naive method is also wasteful as it doesn't take advantage of any previous computations it has done.  The sizes of the neighborhood of two adjacent nodes are surely not independent.

Is there a fast, perhaps randomized,  way of solving this problem?

There is this quasi-linear time approximation algorithm based on HyperLogLog: https://papers-gamma.link/paper/187


Definition of fractional in theoretical CS What is the definition of the word "fractional" in algorithms? I have encountered the word in phrases like "fractional algorithm", "fractional node routing problem".

Note: English is not my native language

The most common use of 'fractional' is when you're solving an integer program. You relax it by dropping the constraints that the solution be integers, thus yielding a linear program in which the variables can take fractional values (fractional comes from fraction). Later, you can convert the fractional values into integers via a process called 'rounding'.