expected number of sets generated by greedy set cover ? I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = \{S_1, ...., S_k\}$). The question is then what is the expected number of sets generated by the greedy set cover in this case ?

Given that a cover exists, greedy will return a cover of expected size $O(p^{-1}\log n)$.
As long as $k$ is not too large, with high probability every cover has size $\Omega(p^{-1}\log n)$

This implies that (for $k$ not too large) greedy gives an $O(1)$-approximation with probability $1-\delta$, for any constant $\delta>0$.

Here is the upper bound, followed by the lower bound.

Upper bound

Conditioning on the event that there exists a set cover,
the greedy set-cover algorithm returns a set cover with expected size
$O(p^{-1}\log n)$.

Proof of upper bound.
Condition on the event that a set cover exists.

Assume without loss of generality that $k\ge (12/p)\ln(n)$
(otherwise, since greedy chooses at most $k$ sets, we are done).

We prove that there is a fractional set cover $X$ of expected size at most
$$\frac{2}{p} + n\exp(-pk/12).$$
By the assumption on $k$ this is $$O(1/p).$$

The upper bound will follow, because
(as is well-known) greedy returns a cover of size $O(\log n)$
times the size of any fractional set cover (and so, here, $O(p^{-1}\log n)$)
(see here or Chvatal).

Define the fractional cover $X$ in two stages.

Give each set $s$ weight $X_s = 2/pk$.
For each element $e$ such that $\sum_{e\in s} X_s < 1$,
choose any set $s$ containing $e$ and raise $X_s$ enough to fully cover $e$.

This clearly gives a fractional set cover.  (Step 2 is well defined,
because we are conditioning on the event that there is a set cover,
that is, that each element is in some set.)

To finish we bound the expected total weight of $X$, that is, $\sum_s X_s$.

Stage 1 contributes exactly $k 2/pk = 2/p$ to the total weight.

Stage 2 contributes, in expectation, at most $n\exp(-pk/12)$,
because each of the $n$ elements has probability at most
$\exp(-pk/12)$ of being covered with weight less than 1
by stage 1.

(To verify this, fix any element.
The element is left insufficiently covered
iff it is contained in fewer than $kp/2$ sets.
The expected number of sets covering the element
is $kp$, so by a standard Chernoff bound the
probability that the number falls below $kp/2$
is at most $$\exp(-(1/2)^2 k p/3) = \exp(-kp/12).$$
This ignores the conditioning, but the conditioning
only decreases the chance that the element is contained
in fewer than $kp/2$ sets.)
QED

As an aside, note that if $k$ is large enough, then greedy will almost certainly return a cover of constant size.  (E.g. if $k$ is $2n2^n$ and $p=1/2$, then won't all possible subsets be present with high probability? And in that case greedy will return just one set of course.)

Lower bound

Assuming  $p\le 1/2$, $k\le \exp(n^{1-\epsilon})$ for some $\epsilon\in [0,1/2]$,
and $s = \min((\epsilon/4p)\ln n, n^{\epsilon/2})$,
then the probability that there exists a set cover of size $s$ or less is $o(1)$.

Of course this implies that greedy does not return a set cover of size less than $s$.

The proof is probabilistic, using direct calculation and the naive union bound.
Hopefully there are no mistakes in the calculations.

Proof.
Fix $p$, $k$, $s$, $\epsilon$ as above.

The number of ways of choosing $s$ sets from the $k$ sets available
is ${k\choose s}$.

For any fixed collection of $s$ sets, the chance that it covers all
$n$ elements is $(1-(1-p)^s)^n$.

Combining these two observations, the expected number of size-$s$ covers among the $k$ sets is
$${k\choose s} (1-(1-p)^s)^n
~\le~ k^s \exp(-n(1-p)^s)
~\le~ \exp\big(s\ln(k) - n e^{-2sp}\big).$$

To complete the proof, one shows that the right-hand side above is $o(1)$
(under the assumptions on $k$ and $s$).

To do that, it suffices to show that

$n e^{-2sp} \rightarrow \infty$, and
$s\ln k \le (1/e) n e^{-2sp}$.

The first of these follows from the assumption on $s$.
The second reduces (taking logarithms) to
$$1+2ps + \ln s \le \ln(n) - \ln\ln k.$$
By the assumption on $k$ this reduces to
$$(1+2ps) + \ln s \le \epsilon \ln n.$$
This holds because the assumptions on $s$ imply that each of the two summands
on the left is at most $(\epsilon/2)\ln n$.
QED


How is DHT different than regular hash tables in context to data/node lookup? How is DHT different than regular hash tables in context to data/node lookup?

This (introduction, 3rd paragraph) paper says:

  First, in addition to the insertion
  and deletion of items, DHTs must support the insertion and deletion of
  buckets: as machines join and leave
  the network, items must be migrated to
  other machines and the hash function
  revised to reflect their new location.

This problem is also in Hashtables (for example, if you implement a hashtable in C using LinkedList and Array, then if the size of the array increased (new node added) then the data needs to be redistributed to achieve good load factor)

  Second, some kind of routing protocol
  is usually necessary: since it is not
  feasible in a P2P system for every
  node to maintain up-to-date knowledge
  of all other nodes in the system, an
  item is looked up (or inserted) by
  following a sequence of routing hops
  through the peer-to-peer network.

Is this point talking about routing mechanism, if yes, then is this done is normal hashtable?

Your question in the first sentence is a bit vague and open-ended. I'm guessing you want to know about routing and mutual node knowledge in the context of lookup.

Each node shouldn't have to know about every other node. Assuming a hash ring topology, the simplest approach is to have each node know about its two neighbors on the ring. This defines a circular linked list. Unfortunately, as with all linked lists, it only supports slow linear search. It's also very sensitive to node removal: if any two nodes go offline, it breaks the connectivity of the ring.

If you try to repair this idea by having nodes maintain knowledge of their longer-range relatives then you eventually wind up with the idea of a skip graph, a generalization of skip lists that can handle node disappearance robustly. Unlike skip lists they are not explicitly stratified, which is important due to the non-hierarchical peer-to-peer nature of the problem.


Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton Problem statement :

Let $M$ be a (potentially nondeterministic) pushdown automaton and let $\cal A$ be its input alphabet. Is there a word $w \in \cal A^*$ s. t. $|w| \leq k$ that is accepted by $M$ ?

Is this problem NP-complete? Has it been studied? Is there an algorithm allowing to find such a word?

Compute the intersection of your CFG language with the regular language $\sum_{i=0}^k A^k$ (this amounts to multiplying the number of states by $k$ and adding a "dead end" state). Now check whether the result is empty: convert into a grammar (I think the result will have polynomial size) and "backtrack" from epsilon productions.

Edit: Kaveh mentioned that this is polynomial in $k$, so if $k$ is given as an input, the algorithm is exponential in $|k|$. However, Kaveh found a way to fix it. Convert the original automaton to a CFG, and replace all terminals by a fixed terminal. Now use an iterative algorithm to find the minimal size of a word generated by each non-terminal, as follows.

Initialize all lengths with $\infty$, and then iteratively update all lengths in the obvious way: given a production $A \rightarrow a^t \prod B_i$ (the order doesn't matter), put $f(A) = \min(f(A),t+\sum f(B_i))$. Claim: this converges in $O(n)$ iterations, where $n$ is the number of non-terminals. The reason is that in a tree generating the minimal-length word, no non-terminal is used twice; each "edge" takes at most one iteration to process (some edges can be "updated" in parallel).


Range searching: what is $\epsilon$? I am interested in range searching purely as a black box in another problem. One problem in particular is that of shooting 2D rays among 2D segments. It seems that Agarwal and Matousek have a well known method for doing this in [1] which requires $O(m^{1 + \epsilon})$ time preprocessing and space to answer ray shooting queries for any fixed positive $\epsilon$. It is not clear to me yet (having read the introduction and conclusion of the paper and skimmed the rest), whether this $\epsilon$ arises due to randomization, approximation, or something else. As I said I only need this as a black box and am somewhat trying to avoid becoming an expert in range searching just to know the answer, and since my initial skimming of the paper didn't produce results I decided to ask it here: which of these three is the algorithm: deterministic, approximate, or randomized? If not deterministic, what is the best that can be done deterministically?

[1] Agarwal P. K, Matousek, J. Ray shooting and parametric search. STOC '92 Proc. of the 24th annual ACM symp. on Theory of computing. Pages 517-526

In some of these bounds, the $\varepsilon$ doesn't come from an approximation, but rather from the degree to which you recurse in a partition tree. Roughly speaking, the idea goes like this. Find a small sample of the input objects that form an arrangement so that the remaining objects are "spread out nicely". In particular, each cell of the arrangement is not intersected by too many of the remaining objects. Then recurse in each piece.

Using things like $(1/r)$-cuttings, you get recurrences that look like

$$ S(n) = r^d( 1 + S(n/r) ) $$

Solving such recurrences gives you bounds like $S(n) = n^{d+\varepsilon}$, where $\varepsilon$ is roughly $1/\log r$.


Longest path among all pairwise shortest paths in unweighted undirected biconnected planar graphs Consider an unweighted undirected bi-connected planar graph.

Let $l_{v,u}$ be the length of the shortest path between nodes $v$ and $u$.

Let $l_{max}$ be the length of the longest shortest path from any node to any other node.

The question is:

  Are there any known non-trivial upper/lower bounds for $l_{max}$?

It would also help if the bounds are for more general types of graphs.

Another interesting way of looking at the problem is:

$l_{max}$ is the maximal number of hops it takes to send a packet in a network from any terminal to any other, when using the shortest possible path.

Please post any link/reference that might be relevant, even if it does not directly solve the problem.
Thanks in advance!

$l_{max}$ is called diameter of a graph.
I hope this paper will be helpful


Complexity of modal logic IK5 What is the complexity of local satisfiability problem for modal logic $\mathit{IK5}$? Herein we denote by $IK5$ the modal logic over euclidean frames extended with inverse modality. Could you provide any references? Is it in $NP$?

What I know about the topic?

  It's easy to see that $IK5$ is in $ExpTime$, since there is a
  reduction from it to $GF^2$ (the two-variable guarded fragment of
  first-order logic) - see Deciding Regular Grammar Logics with
  Converse Through First-Order Logic.

  On the other hand, the ordinary $K5$ is $NP$-complete.

  We can write an equisatisfiable formula in $FO^1$ (the one-variable
  fragment of first-order logic), because the models can be devided into
  three parts: (1) starting world $w$, (2) sucessors of $w$ (3)
  sucessors of sucessors of $w$. The example reduction for even harder
  logic ($K5$ with graded modalities) is described in A Note on the
  Complexity of the Satisfiability Problem for Graded Modal Logics.
  However in the presence of inverse modality we cannot do the same
  trick - the brief idea is that inverse worlds could require the
  different number of successors.

The logic is EXP-complete. One way to prove the lower bound is to note that the logic KTB augmented with universal modality, or even just the global consequence relation of KTB, is EXP-complete (Chen and Lin [1]; note that they denote KTB as B).

Note that a connected IK5-frame $(W,R,R^{-1})$ is either a single irreflexive point, or it consists of a reflexive cluster $C$ together with a (possibly empty) set $I$ of irreflexive points, each of which sees (in $R$) a nonempty subset of $C$. Thus,
$$R_s:=\{(x,y)\in C^2:\exists z\in I\,(R(z,x)\land R(z,y))\}$$
is a symmetric relation on $C$; if every element of $C$ is seen by an element of $I$, $R_s$ is also reflexive. Conversely, it is easy to see that every reflexive symmetric frame can be obtained in this way. It follows that

$${}\vdash_{\mathrm{KTB}^U}\phi\iff{}\vdash_{\mathrm{IK5}}\Diamond^-\top\land\Box^+\Diamond^-\Box^-\bot\to\phi^*,$$

where the translation $\phi^*$ commutes with propositional connectives, and is defined for modal operators by

\begin{align*}
(\Box\phi)^*&=\Box^-(\Box^-\bot\to\Box^+\phi^*),\\
(A\phi)^*&=\Box^+\phi^*.
\end{align*}

Here, $A$ denotes the universal modality of $\mathrm{KTB}^U$, and $\Box^+$ and $\Box^-$ respectively denote the forward and backward modalities of IK5.

Reference:

[1] Cheng-Chia Chen and I-Peng Lin, The complexity of propositional modal theories and the complexity of consistency of propositional modal theories, in: Proc. LFCS 1994 (Anil Nerode and Yu. V. Matiyasevich, eds.), LNCS 813, Springer, pp. 69–80, doi 10.1007/3-540-58140-5_8.


Clarification regarding Bounded Quadratic Congruence Problem Given: 3 positive integers $a, b, L$.
Problem: Is there a positive integer $x < L$ such that $x^2 \equiv \ a (mod\ b)$?

The above problem is NP Complete (as mentioned in G&J) even if we have the factorization of $b$ given. My query is the following:

Suppose we have a promise/condition imposed that, the number of total occurrences of the residue $a$ is polynomially bounded w.r.t. number of prime factors in $b$, i.e. the number of occurrences of $a$ is always less than ${pct}^C$.

$pct$ = number of Prime factors of $b$ , $C$ = some positive integer constant.

Does this problem still remain NP-Complete or it becomes P time solvable.

Essentially, does the number of times a residue occurs is what makes this problem difficult or it doesn't matter and its just dependent on the number of prime factors in $b$?

The NP-completeness of the original problem was proved by Manders and Adleman [1] using a reduction from 3-SAT. Their reduction is parsimonious. Thus, (taking into account that the number of prime factors is upper bounded by the length of the input $n$, while in the M–A reduction, it is at least $n^\epsilon$) your problem is complete for promise-FewP. Note that by Valiant–Vazirani, already promise-UP is NP-hard under randomized polynomial-time reductions, hence the same holds for promise-FewP. Thus, the problem is essentially as difficult as NP.

EDIT: The answer above assumes that in the question, the unclear phrase “the number of occurrences of $a$” means the number of residues $x<L$ such that $x^2\equiv a$. The OP indicates in a comment below that they rather intended it to mean the total number of residues mod $b$ that square to $a$. In the latter case, the problem is solvable in promise-ZPP: using the factorization of $b$, just compute all possible square roots of $a$ modulo $b$ by the usual algorithm (Tonelli–Shanks + Hensel’s lifting + Chinese remainder theorem).

Reference:

[1] Kenneth L. Manders and Leonard M. Adleman, NP-complete
  decision problems for binary quadratics, Journal of Computer and System
  Sciences 16 (1978), no. 2, pp. 168–184.


Decomposition of safety and liveness properties In Alpern,Schneider 86 is described how to extract the automata that recognize safety and liveness properties from a Buchi automaton $m$. This shows that any property rapresented by a Buchi automaton is equivalent to the intersection of these two automata.
In particular, the automata for the safety properties is represented by making all states of $m$ accepting. The question is: although it is a Buchi, can this automaton be determinized by using the subset construction?

Yes. The automata in question are often called "Looping" automata (so you have a keyword to start from).
A possible starting point is the following paper:
https://faculty.idc.ac.il/udiboker/files/MullerAutomata.pdf
A looping automaton can be described as $\left<Q,\Sigma,\delta,Q_0\right>$ where the components are states, alphabet, transition function $\delta:Q\times \Sigma\to 2^Q$ and $Q_0$ are the initial states. Then, the acceptance condition is that there exists a run on the word. That is, $w$ is accepted iff the automaton has some run on it.
It is easy to see (using
Kőnig's Lemma) that the acceptance condition can be equivalently described as follows: for a word $w\in \Sigma^\omega$, let $w_i$ be its prefix up to letter $i$, then $w$ is accepted iff $\delta^*(Q_0,w_i)\neq \emptyset$ for all $i\in \mathbb{N}$.
This shows that it's enough to track the subset construction in order to determine acceptance. What you end up is a deterministic automaton whose states are all accepting except for one, that corresponds to $\emptyset$.


How to compute powers of square matrices? Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N_0$. How fast can we compute the power $A^m$ of that matrix?

The next best thing in comparison to computing $m$-products is to utilize fast exponentation, that requires $\mathcal O(\log m )$ matrix products.

For diagonalizable matrices, the eigenvalue decomposition can be used. It's natural generalization, Jordan decomposition, is unstable under pertubation and therefore does not count (afaik).

Can matrix exponentiation in the general case be sped up?

Fast exponentation suggest a variation of this question is useful, too:

Can the square of a general matrix $A$ be computed faster than by known matrix multiplication algorithms?

As you note, computing $A^m$ can be done in $O(\log m)$ times the number of operations for matrix multiplication on $N \times N$ matrices. The answer to your second question is no, at least for asymptotic complexity -- matrix squaring and matrix multiplication have equivalent time/arithmetic complexity (up to constant factors). Reducing squaring to matrix multiplication is obvious. To reduce multiplication to squaring, suppose we wish to compute the product of $A$ and $B$. Form the $2n \times 2n$ matrix $C$ with the block structure:

$[0~~A]$

$[B~~0]$

That is, $C$ has an $n \times n$ all-zeroes matrix in its upper-left quadrant and lower-right quadrant. Note that $C^2$ contains $A\cdot B$ in its upper-left quadrant.


Complexity of topological sort with constrained positions I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$.

A topological sort of $G$ is a bijection $f$ from the vertices of $G$ to $\{1, \ldots, n\}$ such that for all $x$, $y$, if there is a path from $x$ to $y$ in $G$ then $f(x) \leq f(y)$. I wish to decide whether there exists a topological sort of $G$ such that for all $x$, $f(x) \in S(x)$.

What is the complexity of this decision problem?

[Notes: Clearly this is in NP. If you look at the graph of allowed vertex/position pairs, with undirected edges between pairings that conflict because they violate the order, you get a graph of disjoint cliques where you want to pick at most one pair per clique, at most one pair per position and at most one pair per vertex -- it seems related to 3-dimensional matching but I can't see if it is still hard with the additional structure of this specific problem.]

I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec

Divide the vertices into two groups - some will represent literals, the others clauses, so $n=2v+c$ where $v$ is the number of variables of the CNF (usualy denoted by $n$) and $c$ is the number of clauses. Direct an edge from each literal-vertex to the clause-vertex where it occurs. Define $S$ for a literal-vertex that represents $x_i$ as $\{i,i+v+k\}$ (where $k$ is an arbitrary parameter), so either $f(x_i)=i$ and $f(\bar x_i)=i+v+k$ or $f(\bar x_i)=i$ and $f(x_i)=i+v+k$. For each clause-vertix, let $S=\{v+1,\ldots,v+k,2v+k+1,\ldots,n\}$, so $k$ of the clause-vertices are ``small''.

Now the CNF has an assignment where at least $k$ clauses are false if and only if your problem can be solved for the above instance.  The MinSAT problem is exactly to test whether a CNF formula $\varphi$ has an assignment that makes at least $k$ clauses false, so this shows that your problem is NP-hard.

To help you understand this reduction, here's the intuition: small labels ($1,2,\dots,v+k$) correspond to the truth value False, and large labels ($v+k+1,\dots,2v+k$) correspond to True.  The constraints for literal-vertices ensure that each $x_i$ is either True or False and that $\overline{x_i}$ has the opposite truth value.  The edges ensure that if any literal is True, then all clause-vertices containing it are assigned True as well.  (In contrast, if all literals in a clause are assigned False, then this graph structure allows the clause-vertex to be assigned either False or True.)  Finally, the choice of $k$ ensures that $k$ of the clause-vertices are assigned False and $c-k$ of them are assigned True.  So, if there is a valid topological sort of this graph, then there is an assignment to the variables that makes at least $k$ of the clauses of $\varphi$ false (all of the clause-vertices that were assigned False, plus possibly some of the ones that were assigned True).  Conversely, if there is an assignment to the variables that makes at least $k$ of the clauses of $\varphi$ false, then there is a valid topological sort of this graph (we fill in the labels for the literal-vertices in the obvious way; and for each clause of $\varphi$ that is true, we give its corresponding clause-vertex a label that corresponds to True; the other clause-vertices can receive labels corresponding to an arbitrary truth value).


NIZK proofs: Why is the prove function necessary? In NIZK proofs, the prover can generate its proof for statement $y$ and witness $w$ using

$$\pi \gets \mathrm{Prove}(\sigma,y,w)\text{,}$$

where $\sigma$ is the common reference string. Source: Wikipedia.

However, the zero knowledge property tells us that everyone could have generated a pair $(\sigma, \pi)$ itself. Source: Wikipedia.

So what is prove needed for? I guess it is needed, because the verifier forces the prover to use a given common reference string $\sigma$? This is probably the reason why the verifier can not convince any other verifier?

Prove$\:\:$is needed to convince the verifer(s) that $y$ is true.
Sort of; the verifier(s) will have almost as much control as the prover over the choice of $\sigma$.

The verifier(s) can convince (every) other verifier by forwarding $\pi$ to the other verifier(s).

Unlike ZK protocols in the standard model, which have

deniability, NIZK proofs instead have transferability.

Related to NIZK but not otherwise related to your question:

multi-string NIZK uses a weaker setup
assumption.


Preservation under Substitution with Telescopes In the simply typed lambda calculus, one can show the following result, known as "preservation under substitution":

If $\Gamma \vdash v : \tau_1$ and $(x : \tau_1) \vdash t : \tau_2$,
then $\Gamma \vdash [v/x]t : \tau_2 $.

However, the proof of this relies on the property of permutation, that we can rearrange contexts and it will preserve typing of terms.

I'm wondering, can we prove a similar property for dependently typed languages? The problem is that, here, permutation may not hold, since telescopes are used in place of environments, and the types themselves may refer to variables. Moreover, since the types and terms overlap, we have to substitute in $\Gamma$ and $\tau_2$ as well.

Does anyone have a good reference to proving such a preservation property for a dependently typed language? Are there tricks that are used to avoid the permutations?

The most general form of substitution theorems speaks about arbitrary contexts:

Define what it means to have a substitution $\sigma : \Gamma \to \Delta$ from a context $\Gamma$ to a context $\Delta$ (it's a simultaneous substitution giving a term $\Gamma \vdash e : A$ for every $y : A$ appearing in $\Delta$, and in case of type dependencies we have to do it recursively).
Prove that if $\Delta \vdash e : A$ then $\Gamma \vdash e\sigma : A\sigma$.

In such generality there is no reliance on exchange rules and it all works in dependent type theory as well. The case suggested by Max New in his answer is a special case.


Implementation of alpha equivalence I'm reading through "Type Theory & Functional Programming" by Simon Thompson and it says

  We shall not distinguish between expressions which are equivalent up to change of bound variable names in what follows. (As an aside, this convention which is easy to state, and indeed for us to follow, is surprisingly difficult to implement.)

This seems quite straightforward to implement though:

Given two sets $\Gamma_1$ and $\Gamma_2$, where $\Gamma_1$ = $\Gamma_2$ = $\varnothing$, a $\lambda$-expression $e_1$ is $\alpha$-equivalent to a $\lambda$-expression $e_2$ (that is, $(e_1, \Gamma_1) \equiv_\alpha (e_2, \Gamma_2)$) iff

$e_1$ and $e_2$ are variables and $e_1 \in \Gamma_1$ and $e_2 \in \Gamma_2$
$e_1 \equiv (e_1'e_1'')$ and $e_2 \equiv (e_2'e_2'')$ are applications and $(e_1', \Gamma_1) \equiv_\alpha (e_2', \Gamma_2)$ and $(e_1'', \Gamma_1) \equiv_\alpha (e_2'', \Gamma_2)$
$e_1 \equiv (\lambda x_1.e_1')$ and $e_2 \equiv (\lambda x_2.e_2')$ are abstractions and $(e_1', \Gamma_1 \cup x_1) \equiv_\alpha (e_2', \Gamma_2 \cup x_2)$

Is there something wrong with my interpretation of the problem and consequent answer or is the author simply misinformed?

The author is not misinformed, I'm afraid; it's part of the development process of any computer scientist to go through several phases:

Phase 1: $\alpha$-equivalence is easy! Why is everyone making a big deal about this?
Phase 2: $\alpha$-equivalence is impossible! Why should I do computer science if such a basic notion is so impossibly complex?
Phase 3: I've finally understood $\alpha$-conversion! I should write up a paper to explain it to the world!

I'm currently in phase 2. However I'll try to explain my limited understanding.

Your algorithm is flawed: it doesn't distinguish
$$ \lambda x.\lambda y. x\ y$$
and
$$\lambda x.\lambda y. y\ x$$
It's not completely trivial to fix: if you want to prove the equivalence of $\lambda x.\lambda y.x\ y$ and $\lambda y.\lambda x. y\ x$ (which does hold!), you have to find a new variable $z$, and replace $x$ by $z$ in the first term, and $y$ by $z$ in the second. If you simply replace $y$ by $x$ in the second term, you'll get $\lambda x.\lambda x.x\ x$ which is not what you want.
It seems you can "pre-process" your terms by requiring all bound variables to be distinct. This is called hygiene. Unfortunately hygienic terms like
$$ (\lambda x. x\ x)\ (\lambda y.y)$$
become unhygienic when applying $\beta$-reduction:
$$ (\lambda x. x\ x)\ (\lambda y.y)\rightarrow_\beta (\lambda y.y)\ (\lambda y.y)$$

There is a vast literature on how to do this properly. The main approach on how to handle $\alpha$-equivalence that I know of is Nominal Logic which instead of re-naming, advocates "swapping" which is better behaved. The other (non)-solution is to do away with variable names altogether and simply have pointers from variable positions to $\lambda$s, as seen in the variants of the de Bruijn index method.


Definition of near-linear algorithm There are quite a lot papers describing near-linear algorithms. They are usually iterative, with linear complexity of one iteration. Others have $O(n\log^k n)$ time compexity.

I'm failed to find a decent source with the definition of "near-linear" time, which covers both types. Please, help me find one.

A natural definition of "near-linear" should be:

  A function $f:\mathbb{N}\to\mathbb{N}$ is near-linear, if $~f(n)\in O(n^{1+\varepsilon})~$ for all $\varepsilon>0$.


How do continuations represent negations (under the Curry–Howard correspondence)? Under the Curry–Howard correspondence, types can be thought of as propositions, and values inhabiting a type can be thought of as proofs that the corresponding proposition is true. (E.g., the Cartesian product is logical conjunction.)

Negation is represented as $A \to \bot$, where $\bot$ is the empty type. This works because if a type is inhabited, there can't be any function $A \to \bot$ (if you do you have such a function and the type is inhabited, feed the value into it and you get an element of the empty type, hence a contradiction), and vice versa (if $A$ is empty, the empty function $A \to \bot$ exists).

But once you add continuations to your language, an $A$-continuation can also be given the type $A \to \bot$. (see e.g. the symmetric lambda calculus). This apparently provides computational meaning to classical theorems; for example, the $\mathcal{C}$-operator (a basic operator for manipulating continuations), has type $\neg\neg A \to A$.

But can't you have continuations for non-empty types? If you add continuations, does $\neg A$ no longer express "$A$ is-empty/is-false/has-no-proofs"? It can't, right? This formulation makes an inhabitant of $\mathbb{N} \to \bot$ axiomatic, and $\mathbb{N}$ certainly isn't uninhabited. So what does "$\neg A$" actually express, if not "$A$ is-empty/is-false/has-no-proof"? And how do you actually express "$A$ is-empty/is-false/has-no-proof" when continuations exist?

When one associates negation with continuations, it is probably not ideal to think of it in terms of an 'empty' type. Continuation passing can be done with respect to any result type, and if that type is held abstract, it works a lot like 'false' in that there is no introduction rule for it.

With respect to the paper you linked (I'm by no means an expert on it, and just skimmed it, really), I think it might help to study the reduction rules. It appears to me that the goal of the logic is to construct an expression $e : +\mathsf{int}$ and reduce that expression to a numeral $n$. This means that the continuation $\bullet : ¬int$ is not something that would be valid as a program in itself. Rather it is a clue that the abstract 'result type' is actually $\mathsf{int}$, because we are interested in using continuation-based computations that eventually result in integers. $\bullet$ is something that immediately completes the computation, hence the rules:

$$(begin)\ \ \ \  e : +int \leadsto \langle e | \bullet \rangle$$
$$(end)\ \ \ \  \langle n | \bullet \rangle \leadsto n$$

I don't know what happens if you have $\bullet$ involved in other situations, or if you can, but I might expect it to abort other continuations and end the computation. It seems more like it can only be the initial continuation based on the rules, though.

Now, one answer to your question is that this system is not even trying to reason about uninhabited types. It is using a correspondence between the logical rules and control flow, without the specific semantic meaning of negation. One thing you might want to check out is linear logic, because it actually has two sorts of 'false' or zero, one which is about control flow, and one which is about emptiness. The linearity is important for keeping them separate.

In that setting, $⊥$ is the 'false' that has to do with control flow, and it gets things like double negation elimination and excluded middle (with a corresponding 'or' that is more related to representing functions via continuations than it is disjoint union), while there is also $0$, which gets the principle of explosion (which is arguably the distinct part of the empty type1). An interesting thing about this setting is that even though the logic seems classical, it is actually constructive because of the more restricted rules. Double negation by the 'control flow' bottom $⊥$ is just a different (possibly more convenient) way of structuring a program that computes the doubly-negated type (and 'excluded middle' is a decomposed identity function).

Fillinski's 'Linear Continuations' might be a good place to start reading, although there are probably other references as well.

In the continuation-with-abstract-result-type setting, you can also interpret explosion, but it has sort of a different meaning. Effectively such interpretations are always 'delimited' somewhere, even if it's only the end of your program. Explosion means that if you somehow get a value of the abstract result type, you can throw away your current continuation and jump to the delimiter. So it is an 'abort' operation. Linear logic doesn't allow this; all continuations must be used (and used exactly once), so explosion must be justified by involving an 'impossible' situation, like having a value of an empty type.


A simple proof that decidability of typability in System F ($\lambda 2$) implies decidability of type checking? Suppose we don't know Joe B. Wells's result from 1994 that both typability and type checking are undecidable in System F (AKA $\lambda 2$). In Barendregt's Lambda calculi with types (1992) I found a proof due to Malecki 1989 that type checking implies typability. This is because

  exists $\sigma$ such that $M:\sigma$

is equivalent to

  $(\lambda xy.y)M : (\alpha\rightarrow\alpha)$

(This is because if a term is typable in System F then all its subterms are.)

Is there a simple proof the other way around? That is, a proof that typability implies type checking in System F?

As far as I know, showing that this direction is the hard part of Wells proof! At least this is what Pawel (Urzyczyn) explained to me a few years back.

Apparently it is not too hard to show that type checking is undecidable; the hard part is showing that this implies undecidability of type reconstruction! Indeed there are some cases in which the first is undecidable and the second decidable: see e.g. Dowek 1993.


Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$ Is it decidable whether a computable analytic function $f(x_1,x_2,\dots,x_n)$ over $\mathbb{R}$, $\mathbb{C}$  in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm?

Also, I am wondering under what condition regarding the domain of the function, can it be decidable that $f$ is identically zero?

No, it is not decidable. A good heuristic to answer such questions is the following: every computable map is continuous. If you could decide whether $f(x) = 0$ for all $x \in \mathbb{C}$, then the characteristic map $d$ of such a decision procedure, namely
$$d : f \mapsto \begin{cases}
1 & \text{if $\forall x \in \mathbb{C} . f(x) = 0$}\\
0 & \text{otherwise}
\end{cases}
$$
would be a non-constant computable map from the vector space of all such functions to the discrete space $\{0,1\}$, but such a map is discontinuous. By the same reasoning you cannot even decide whether $f(x) = 0$ at a single given $x \in \mathbb{C}$. And for the same reason still it is impossible to decide whether $y = 0$ where $y \in \mathbb{R}$.

A similar heuristic in a slightly different form: computable maps are continuous, therefore in any computable procedure a small perturbation of the input must create only a small perturbation of the output. From this you can see immediately that the map which takes $f$ to one of its roots (assuming $f$ has one) is not computable, because it is easy to make roots jump around wildly with arbitrarily small perturbations of $f$. (This heuristic would not work if you know someting extra about $f$, for instance if you are guaranteed that it is an odd-degree polynomial).

Of course, you need to know what topology to put on the vector space, but as a heuristic it is good enough to just imagine "the usual" topology, whatever that is. (There are theorems in computable analysis which say that an admissible representation of a separable metric space gives induces the metric topology, so the heuristic is pretty safe.)


Compare similar N-Dimensional vector in a database I want to compute Euclidian distance between similar vectors in a database (SQLite).
So each column in the database is a value from my vector.

The first problem appears, I have a large number of values that I first need to reduce to fit a reasonable number of rows (<50) since the original data have thousands of columns.
I have also thought of storing a blob, load it in memory and do my computations ?

Since I am trying to find the best matches (similarity mesure), I am currently filtering the database by applying a threshold for each value. Applying a filter for a small number of column is feasible, doing this for many columns is too time consuming.

Sqlite has a RTree module limited to 5 dimensions (11 columns). But it is not the filtering that I want.

What is the best compromise or technique/algorithm to sort and compare vectors using a database ?

Thank you

What you're looking for is a procedure to do near-neighbor searching in a high dimensional Euclidean space, or do dimensionality reduction prior to doing such a near neighbor search.

There are two approaches that are likely to help:

Use a native near-neighbor search procedure that works in high dimensions. Locality-sensitive hashing is a popular choice in this regard.
Apply dimensionality reduction, and then use a technique that works for fewer dimensions. In this case, you should look at the ANN near-neighbor library, and also look into using the Johnson-Lindenstrauss transform for dimensionality reduction (or possibly even PCA to reduce dimensions).

(warning - self promotion alert: I have a paper that describes different implementations of Johnson-Lindenstrauss and how they compare)


The complexity of the dominating set problem in specific subclasses of chordal graphs I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of chordal graphs.

A graph is an undirected path graph if it is the vertex-intersection graph of a family of paths in some undirected tree. Let UP be the class of undirected path graphs.

A graph is an EPT graph if it is the edge-intersection graph of a family of paths in some undirected tree. An EPT graph may not be chordal, but let CEPT be the class of chordal EPT graphs.

A graph is a (rooted) directed path graph if it is the vertex-intersection graph of a family of directed paths in some rooted directed tree (i.e. all arcs directed away from the root). Let RDP be the class of (rooted) directed path graphs.

We have $RDP\subseteq CEPT \subseteq UP\subseteq chordal$

It is known that the DSP is linear-time solvable for graphs in RDP but NP-complete for graphs of UP [Booth and Johnson, 1981]

I am interested in special graphs which correspond to vertex-intersection graphs of families of undirected paths in caterpillar-like trees of maximum degree 3.
More precisely, these "caterpillars" are built from a path in which each second vertex has a pendant degree-one-vertex attached to.
Let us call this class cat-UP.

Moreover, my special graphs can also be constructed as the edge-intersection graphs of some families of undirected paths in specific trees of maximum degree 3.

So my questions are:

1) Is the complexity of the DSP for graphs of cat-UP known ?
(note that the reduction in [Booth and Johnson, 1981] produces a host tree which is of maximum degree 3, but quite far from a caterpillar)

2) What is the complexity of DSP for graphs of CEPT ? And for graphs of CEPT arising form a host tree of maximum degree 3 ?
(this is not known to ISGCI)

3) Is there any complexity result for the DSP in a closely related graph family ?

Too bad you have been waiting so long without getting any answer.
I don't know for the classes you asked for, but I know some related graph classes and new techniques you can try.

First I will mention that Steven Chaplick has done work on related graph classes, he finished his thesis earlier this year, you might find his research interesting.

I know some results in this direction follow from my own work
Graph Classes with Structured Neighbourhoods and Algorithmic Applications
This gives a general technique for solving various problems including DSP in certain graph classes.
We do this by introducing new graph decompositions (see my thesis).

For instance if we are give an intersection model of UP where the tree has max degree d and the paths have max length s we can solve dominating set in $(d-1)^{3(s-1)}poly(n)$.

Similar if we have a graph given with an intersection model consisting of $0$-bend paths in a $k \times n$ grid (for constant k).

The same technique might work for CEPT arising form a host tree of maximum degree 3, but I need some more time to understand this class.
If you have a link to some characterizations of this class that would help.


Is there any relationship of hardness between the two problems? Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D.

Consider the problem P1: With D as input, computes $(x^*,y^*)=argmax_{(x,y)}F(x,y|D)$ where x and y are two sets of variables.

Another problem P2: With y and D as input, computes $x^*=argmax_xF(x|y,D)$.

If we know P2 is NP-hard, can we infer the hardness of P1? Is P1 also NP-hard?

No, you cannot infer hardness of P1. (And your question looks suspiciously close to homework.) Consider the special case where

$D$ is an undirected graph $G=(V,E)$
$x$ is a subset $E_x\subseteq E$
$y$ is a non-negative integer

The function value $F(x,y,D)$

takes the value $2$, whenever $y\ge1$;
takes the value $1$, if $y=0$ and if $E_x$ induces a Hamiltonian cycle in $G$;
takes the value $0$, if $y=0$ and if $E_x$ does not induce a Hamiltonian cycle in $G$.

  Fact. The problem P1 of maximizing $F$ for a given graph $G$ is polynomially solvable.

(Just pick $E_x=\emptyset$ and $y=1$ to reach an objective value of $2$.)

  Fact. The problem P2 of maximizing $F$ for a given graph $G$ and a given number $y$ is NP-hard.

(By fixing $y=0$, the problem becomes the NP-hard Hamilton cycle problem.)


Shortest cycle separator for biconnected planar graphs An $(s,f)$- balanced separator in a graph $G$ is a set $S$  of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is said to be a cycle-separator.

  Question: for which smallest value of $\frac{s}{\sqrt{n}}$ such that $f$ is a constant there exists (and one which can be found in
  polynomial time) an $(s,f)$-cycle separator for all biconnected
  planar graphs which are not "easy" - the notion of easiness being (for
  example) bounded tree-width. Probably the parameters $s,f$ will depend
  on the tree-width $w$ of the easy class.

Notice that I do not care about $f$ as long as it is a constant but $s$
(as a fraction of $\sqrt{n}$) is crucial for me.

Some background:
Lipton-Tarjan gave a $(c\sqrt{n},\frac{2}{3})$-balanced planar (vertex) separator for some constant $c$. Subsequently Miller gave a similar separator that is also a cycle but in triangulated planar graphs.

If we omit the triangulated condition (say replace it by $2$-vertex connected) there might not exist an $(O(\sqrt{n}),O(1))$-cycle separator - case in point being a cycle on $n$ vertices. We can choose to ignore such easy (e.g. all bounded tree-width) cases.

This doesn't seem to be possible, at least not without finding the right notion of "easy".

Consider a graph formed by taking a grid graph with $k$ rows and $l+1$ columns, and identifying the leftmost column of vertices with the rightmost column of vertices. Here, we have $n = kl$ vertices, and we're interested in $k \le l$. The graph is planar, and has treewidth at least $k$, as it has a $k\times k$ grid graph as a minor.

Additionally, a cyclic separator achieving constant $f$ in this graph seems to need $\Omega(l)$ vertices (where the constant depends on $f$). Imagine the graph drawn on a cylinder of circumference $l$ and height $k$, where the graph forms an equally spaced grid on the surface of the cylinder. Then if a cyclic separator has length less than $l$, it cannot "go around" the cylinder. Hence a cyclic separator gives a way to find a region in a $k\times l$ rectangle whose perimeter is the length of the separator, and whose area is at least a constant ($1-f$) fraction of the whole rectangle's area. I don't know the exact isoperimetric inequality for this, but it seems like such a region would need perimeter $\Omega(l)$ in order to have enough area and fit into the rectangle.

Thus we have a graph with treewidth $k$ and whose separators need to be of size $\Omega(l)$. Choosing parameters like $k = n^\epsilon$ and $l = n^{1-\epsilon}$, we thus see that a cyclic $(s,f)$-separator for constant $f$ needs to have $s = \Omega(n^{1-\epsilon})$, even for graphs with treewidth $n^\epsilon$.


Does univ : univ always lead to a contradiction in a dependently typed language? I am currently following Checking Dependent Types with Normalization by Evaluation: A Tutorial by David Christiansen, where we consider the type of U (the universe of types) to be U itself [this can be seen section 7.4.1 in the implementation of synth where we have ['U (go '(the U U))]: That is, the untyped expression U is elaborated into the expression U of type U. Effectively, we have taken that Univ : Univ.
This cannot happen in ZFC due to the axiom of foundation. I suspect type-inferring U as having type U is inconsistent. I do not know how to prove this; I would attempt to encode a Russell-style paradox if I were pressed to produce a proof.

Is it really true that U : U is inconsistent?
Is it possible to write a term that produces a proof of False assuming U : U? Or is the encoding to large to write down easily "by hand", but can be believed to be done?
If U : U is not inconsistent (i.e., is consistent), then a couple of words on why the dependently typed world allows for U : U while ZFC cannot allow U ∈ U would be appreciated.

I understand that talking about "dependently typed languages" is broad enough to be senseless. As a beginner, I find it hard to restrict to one theory, because I don't know the trade-offs between the theories. For the sake of the answer, please feel free to restrict to, say, MLTT, or CoC, or LF.

U : U is inconsistent in a wide variety of settings. It is safe to say that it's inconsistent in any type theory. Deriving False from it is feasible by hand. The simplest version of this is called Hurkens' paradox:

Original source
Coq implementation.
Agda implementation.

The Coq source additionally describes the sufficient conditions for getting False. In short, we don't need U : U, it's enough to have two universes, where one is contained in the other, and both are closed under impredicative function types.


Sorting points such that the minimal Euclidean distance between consecutive points would be maximized Given a set of points in a 3D Cartesian space, I am looking for an algorithm that will sort these points, such that the minimal Euclidean distance between two consecutive points would be maximized.

It would also be beneficial if the algorithm would have a tendency toward a higher average Euclidean distance between consecutive points.

ETA: Everything below is in the paper "On the maximum scatter TSP", Arkin et al, SODA 1997.

I don't know about exact answers, but here's another approach that's a little different from Suresh's suggestion of Gonzalez clustering:

Assume for simplicity that $n$ is even. For each vertex $p$, find the median of the $n-1$ distances $d(p,q)$. Form an undirected graph in which every vertex $p$ is connected to the other vertices that are at least the median distance away. The minimum degree in this graph is at least $n/2$, so by Dirac's theorem it's possible to find a Hamiltonian cycle in this graph.

On the other hand, there are $n/2 + 1$ vertices in the disk centered at $p$ with radius $d(p,q)$, too many to form an independent set in the cycle, so any Hamiltonian cycle would have to have an edge connecting some two of these vertices, of length at most $2d(p,q)$. Therefore, the Hamiltonian cycle found by this algorithm is at worst a 2-approximation to the bottleneck max cycle.

This will work in any metric space, and gives the optimal approximation ratio among algorithms that work in any metric space. For, if you could approximate better than to within a factor of two then you could solve Hamiltonian cycle problems exactly, by reducing the input graph to the Hamiltonian cycle problem into a metric space with distance 2 for every graph edge and distance 1 for every non-edge.

Probably with some care you can massage this into an approximation algorithm for paths instead of cycles.


How to evaluate and compare the performance of algorithms in practice? Let $A$ be a heuristic algorithm for problem $Q$.
I want to evaluate the performance of my algorithm in a
specific practical environment and
compare it to other algorithms.
Is there a rigorous framework for comparison of algorithms in practice?

One method to evaluate the performance and compare it with other algorithms
is to run them on randomly generated inputs from a distribution
(based on actual inputs or a theoretical model of inputs) and
measure the average running time of the algorithms.
However I want to be able to express that one algorithm is better than other one
in stronger sense than just having better expected running time.

What do people use for to express stronger conditions?
Would standard deviation be a useful for this purpose?
What is the best way to measure the confidence level of the performance?

Are the any references (books/surveys/tutorials/...) on how to compare the performance of algorithms in practice?

I believe what you're looking for is the field of Experimental Algorithmics. There is a text by McGeoch, an ACM Journal, and a previous question on this site that provides a reading list for the field.


Two Hamiltonian path problem variants While formalizing the gadgets for the proposed reduction of the question
Efficient algorithm for existence of permutation with differences sequence? the following problems came to my mind:

Problem 1 (I call it the "crazy frog problem" :-))

Given a $n \times n$ partially filled board (some cells are empty, some are already filled), a starting cell $c_0 = (x_0,y_0)$ and a list of jump distances $(\Delta x_1,\Delta y_1),(\Delta x_2,\Delta y_2),...,(\Delta x_m, \Delta y_m),\; -n < \Delta x_i, \Delta y_i < n$; is there a sequence $(s_1,s_2,...,s_m), s_i \in \{+1,-1\}$ such that the sequence of
jumps: $$c_j = ( x_{j-1} + \Delta x_j * s_j, \quad y_{j-1} + \Delta y_j * s_j ) $$

makes the frog visit every empty cell of the board exactly once? (every jump must be within the boundaries of the board, at every jump the target cell must be empty, after the jump the cell becomes filled)

Figure 1. An instance of the CFP on the left and its solution on the right.

Problem 2

What is the complexity of the Hamiltonian path problem on grid graphs with holes, if we force the path to be an alternating sequence of horizontal/vertical moves (i.e. two consecutive horizontal/vertical moves along the path are forbidden).

Are these problems already known and what is their complexity?

Notes: there is an immediate reduction from problem 2 to problem 1; probably there is a reduction from problem 1 to the problem of finding a valid permutation from a difference sequence (which I'm trying to prove NPC).

I tried to write a formal proof of the NP-completeness of Problem 1 (Crazy Frog Problem, CFP).

It remains NP-complete even if restricetd to a one dimensional board (1-D Crazy Frog Problem, 1-D CFP) or to a one dimensional board without blocked cells, and there is an immediate reduction from the 1-D CFP without blocked cells to the Permutation Reconstruction from Differences sequence problem.

The reduction is from Hamiltonian path on grid graphs (a grid graph is a node-induced finite subgraph of the infinite grid: if two nodes are adjacent (distance 1 in the grid) then there is an edge between them; a grid graph can have holes, i.e. some nodes may be missing;  see "Hamilton Paths in Grid Graphs" by Alon Itai, Christos H. Papadimitriou, Jayme L. Szwarcfiter). Given a grid graph $G$ that fits in a $w \times w$ square, with nodes $u_i$ at coordinates $(x_{u_i},y_{u_i})$
and source, target nodes $s,t$; build a filled board of size $4n\times4n$ with all blocked cells except cells $(4x_{u_i},4y_{u_i})$ and target cell $(4x_t+1,4y_t)$. The initial frog position is $(4x_s,4y_s)$. This part of the board is called graph area. The first "logical" sequence of moves is the following sequence repeated $|V| - 1$ times:

(suppose that frog is in position $(x,y)$)

$(0,J_i)$: vertically jump to an empty part of the board (edge gadget)
$(-2,2)$: make a backward diagonal jump of length 2
$(0,p)$: vertically jump to another empty part of the board (on the same gadget)
$(2,2)$: make a forward diagonal jump of length 2
$(0,J_i+p)$: return to graph area in one of the cells $(x+4,y),(x-4,y),(x,y-4),(x,y+4)$

This forces the frog to make $n-1$ steps on the empty cells corresponding to the nodes of the original graph.

The sequence is followed by one horizontal step $(1,0)$ (that forces the last cell to be the one associated with the target node $t$) and a forced step that leads to a cleanup gadget. The sequence of jumps of the cleanup gadget allows it to visit all unvisited cells of the edge gadgets and completely fill the board.

This is a simple graphical outline of the gadgets used in the reduction:

Figure: Outline of a CFP instance (for better readability blocked cells are not shown, the cleanup gadget is not complete and space is compacted ). Black jumps represent the graph area traversal, green jumps represent the edge gadgets traversals, red jumps represent the vertical selection gadget traversal, blue jumps represent the horizontal hole gadget traversal.

The details can be found in the draft paper "The Crazy Frog Problem and Permutation Reconstruction from Differences" that can be download here.

The reduction is complex so perhaps it is wrong (or can be simplified), but I think that the results (if new?) are interesting ...


One Generalization of Graph Isomorphism Problem Say I generalize the language which consists of pairs of isomorphic graphs to take the following form:

$GI(f) = \{ (G, H) \mid \exists \psi : V_G \rightarrow V_H, Pr_{a, b \in V_G} ((a, b) \in E_G \Longleftrightarrow (\psi(a), \psi(b)) \in E_H) \geq f\}$

Is there any work on this language? The obvious question is whether there exists $f$ such that $GI(f) \in P$. The funny counterpart to this language is

$IG(f) = \{ (G, H) \mid \forall \psi : V_G \rightarrow V_H, Pr_{a, b \in V_g}((a, b) \in E_G \Longleftrightarrow (\psi(a), \psi(b)) \in E_H) \leq f \}$

Just wanted to hear the thoughts of anyone who wanted to have a go at constructing algorithms for different constant values of $f$ or perhaps for $f$ as a function of the size of the vertex sets or something.

I wasn't able to figure out whether $\mathrm{GI}(1/2)\in\mathsf P$, but here is a weaker result: The languages $\mathrm{GI}(1/2)$ and $\mathrm{GI}$ are not $\mathsf P$-inseparable.

Proof: It suffices to show the first reverse inclusion in
$$\mathrm{GI}(1/2)\supseteq\{(G,H): |V_G|=|V_H|, |E_G|=|E_H|\} \supseteq \mathrm{GI}(1)=\mathrm{GI}.$$
Let $p$ be the probability that $(a,b)\in E_G$ for uniformly random $a$, $b$.

Let $\Psi:V_G\to V_H$ be a uniformly random function and also let $a$ and $b$ be selected randomly, with $\Psi$, $a$, $b$ mutually independent.
Then the two events
$$\mathscr U = \{(a,b)\in E_G\}\text{,}\quad \mathscr V=\{(\Psi(a),\Psi(b))\in E_H\}$$
are independent. Therefore
$$\Pr_{\Psi,a,b}(\mathscr U\leftrightarrow\mathscr V)=p^2+(1-p)^2\ge 1/2.$$

So by Fubini's Theorem there is some $\psi$ such that
$\Pr_{a,b}(\mathscr U\leftrightarrow\mathscr V\mid \Psi=\psi)\ge 1/2.\qquad\Box$


Randomized identity-testing for high degree polynomials? Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime.

Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with  time $\mbox{poly}(n)$ and error probability $\leq 1-1/\mbox{poly}(n)$, even if the degree is not a priori bounded? What if $f$ is univariate?

Note that you can efficiently test if $f$ is identically zero as a formal expression, by applying Schwartz-Zippel over a field of size say $2^{2|f|}$, because the maximum degree of $f$ is $2^{|f|}$.

It’s not exactly clear to me what is the input of the problem and how do you enforce the restriction $p=2^{\Omega(n)}$, however, under any reasonable formulation the answer is no for multivariate polynomials unless NP = RP, due to the reduction below.

Given a prime power $q$ in binary and a Boolean circuit $C$ (wlog using only $\land$ and $\neg$ gates), we can construct in polynomial time an arithmetic circuit $C_q$ such that $C$ is unsatisfiable iff $C_q$ computes an identically zero polynomial over $\mathbb F_q$ as follows: translate $a\land b$ with $ab$, $\neg a$ with $1-a$, and a variable $x_i$ with $x_i^{q-1}$ (which can be expressed by a circuit of size $O(\log q)$ using repeated squaring).

If $q=p$ is prime (which I don’t think actually matters) and sufficiently large, we can even make the reduction univariate: modify the definition of $C_p$ so that $x_i$ is translated with the polynomial
$$f_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$$
On the one hand, $f_i(a)\in\{0,1\}$ for every $a\in\mathbb F_p$, hence if $C$ is unsatisfiable, then $C_p(a)=0$ for every $a$. On the other hand, assume that $C$ is satisfiable, say $C(b_1,\dots,b_n)=1$, where $b_i\in\{0,1\}$. Notice that
$$f_i(a)=\begin{cases}1&\text{if $a+i$ is a quadratic residue (including $0$),}\\
0&\text{if $a+i$ is a quadratic nonresidue.}\end{cases}$$
Thus, we have $C_p(a)=1$ if $a\in\mathbb F_p$ is such that
$$a+i\text{ is a quadratic residue }\iff b_i=1$$
for every $i=1,\dots,n$. Corollary 5 in Peralta implies that such $a$ always exists for $p\ge(1+o(1))2^{2n}n^2$.


Lower bound on the largest restrained cubic subset Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints:

Each row in the cube (in any of the three directions) has exactly 2 or 0 points.
If two points are in the same row (any of three), connect them with an edge. The subset must be connected by these edges.

It is easy to build such a set which is $\Omega(n)$, for instance a staircase, or stacking squares. Is it the case that these structures are also $O(n)$? Or is there an $\Omega(n^2)$ bound?

Building such a set would require adding a linear number of points for each added dimension, which is hard due to the first restriction.

This problem may also be reformatted graph-theoretically. We may express points in the cube as 3-edges in a 3-uniform tripartite hypergraph. In this case our restraints become that each set of 2 points contained in a 3-edge is contained in exactly two 3-edges, and the 3-edges are connected.

These subsets of grids, and your graph-theoretic interpretation of them, are studied in my paper

The complexity of bendless three-dimensional orthogonal graph drawing.
D. Eppstein.
J. Graph Algorithms and Applications 17 (1): 35–55, 2013.
http://dx.doi.org/10.7155/jgaa.00283

I don't think I included the quadratic example suggested in daniello's answer in this paper, but you can find it in one of my blog posts from ten years ago, https://11011110.github.io/blog/2006/06/09/topology-of-xyz.html (see the ETA at the bottom).

Incidentally, the same construction (points with coordinate sum 0 or 1) in the 3d integer lattice, without the mod $n$ part, produces a lattice embedding of the hexagonal tiling of the plane. Doing the same thing in 4d, similarly, produces a lattice embedding of the 3d diamond lattice. See another of my papers:

Isometric diamond subgraphs.
D. Eppstein.
16th Int. Symp. Graph Drawing, LNCS 5417, 2009, pp. 384–389.
https://arxiv.org/abs/0807.2218


Random 3-SAT: What is the consensus experimental range of the threshold? The critical ratio of clauses to variables for random 3-SAT is more than 3 and less than 6, and seems to be commonly described as "around 4.2" or "around 4.25".  Mezard, Parisi, and Zecchina prove (in the physics sense) that the critical ratio is 4.256, whereas the first and third authors prove that it is 4.267.

What is the range of values that the critical ratio could possibly take?

The motivation for me asking this question is that if the ratio could be $2+\sqrt{5} \approx 4.236$, then the standard reduction of 3-SAT to NAE-3-SAT (transforming $m$ clauses and $n$ variables into $2m$ clauses and $m+n+1$ variables) gives a ratio of $\phi$, which seems unlikely but would be pretty cool.

In light of the Ding--Sly--Sun verification of the 1-step Replica Symmetry Breaking picture for kSAT (when k is large enough) I think experts would now be pretty surprised if the MPZ/MMZ-conjectured formula for the 3SAT satisfiability threshold (approximate value: 4.2667) is incorrect.


Time Hierarchies in DSPACE(O(s(n))) The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time.
Does it hold in some way if the space is limited asymptotically?
How does $\textrm{DTISP}(g(n), O(s(n)))$ relate to $\textrm{DTISP}(f(n), O(s(n)))$ if $\frac{f}{g}$ grows fast enough?

I am especially interested in the case that $s(n) = n$, $g(n) = n^3$ and $f(n) = 2^n$.

In particular, I considered the following language:
$ L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w)  \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps}, $ $ k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \} $

However, $L_k$ could be decided in $n^3$ steps by using $(k+1)n \in O(n)$ space.

Without limiting $M$ to four tape symbols and thus allowing to compress $O(n)$ cells into $n$ cells, we get space issues when simulating an $M$ with too many tape symbols. In this case, the language is not in $\text{DSPACE}(O(n))$ anymore. The same happens when setting $k = h(|w|)$ for some $h$ that can be computed fast enough.

This question is basically a rephrase of my question here.

Edit Summary:
Changed $\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$ to $\textrm{DTISP}(f(n), s(n))$, however, I think the intersection is also worth to think about.

This is an open problem: It is open whether $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ (or even $\mathrm{NSPACE}(O(n))$). We only know that $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$.

However, under plausible computational complexity conjectures, there is a proper hierarchy.  For example, if for every $ε>0$, CIRCUIT-SAT ∉ i.o.-$O(2^{n-ε})$, then
$\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$
where $f(n)≥n$, $f(n)$ is $2^{o(\min(n,s(n)))}$, and $f$ is time-space constructible.

In particular (under the hypothesis), existence of a satisfying assignment for circuits with $⌊\mathrm{lg}(f^{1+ε/2})⌋$ inputs and size $(\log f)^{O(1)}$ serves as a counterexample to the equality of the classes.

Notes:

CIRCUIT-SAT is at least as hard as $k$-SAT (which is used in the strong exponential time hypothesis).
Per convention, in CIRCUIT-SAT, $n$ is the number of input wires; circuit size is $n^{O(1)}$.
If the assumption used CIRCUIT-SAT for quasilinear circuit sizes, then the bound on $f(n)$ can be relaxed to $O((2-ε)^{\min(n,s(n))})$.  Also, weaker/stronger assumptions on hardness of CIRCUIT-SAT give weaker/stronger hierarchies (that we can currently prove).
i.o. means infinitely often, and can be dropped for $f$ that are in a certain sense continuous (including $f(n)=n^a$).
It appears likely that the DTISP hierarchy is sharp enough to distinguish $O(f)$ from $o(f/\log f)$ (and perhaps $o(f)$) (when $f$ is not too large relative to the permitted space).
To distinguish $n^a$ from $2^n$, we only need the weaker assumption P≠PSPACE.


Two preorders with same glb I have a set $S$ with two preorders $\mathord{\le}_1,\mathord{\le}_2\subseteq S\times S$ which a priori are unrelated.  Let $\equiv_1$ and $\equiv_2$ be the induced equivalences (i.e., $x\equiv_1 y$ iff $x\le_1 y\le_1 x$ and $x\equiv_2 y$ iff $x\le_2 y\le_2 x$).

I also have an operation $\land$ which turns out to give greatest lower bounds for both preorders: for all $x,y\in S$, $x\le_1 y$ iff $x\land y\equiv_1 x$ and $x\le_2 y$ iff $x\land y\equiv_2 x$.

Can I conclude anything about the relationship between my preorders?

(Note that the problem becomes trivial if my preorders are partial orders: in that case, the above implies $\mathord{\le}_1=\mathord{\le}_2$.)

I'd say no. Consider the following example. Let $(A,\land)$ and $(B,\land)$ be two unrelated semilattices. Let $(S,\land)$ be their direct product, and put $(a,b)\le_1(a',b')$ iff $a\le a'$, $(a,b)\le_2(a',b')$ iff $b\le b'$. Then your conditions are satisfied, even though the two preorders look nothing like each other.


Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/n \right) $ (in fact almost all of them are such).

This follows from the fact that there are $2^{2^n}$ Boolean functions on $n$ variables and only at most $16^k (k+n+1)^{2k} k / k!$ different Boolean functions on $n$ variables can be computed by circuits of size $k$ (for each gate there are $16$ possibilities to choose its type and $b+n+1$ possibilities to choose its two predesscors (the other $k-1$ gates, $n$ variables and $2$ constants), $k$ possibilities to choose the final gate and there are $k!$ possibilities to renumber the gates)

I am interested in probabilistic circuits in the following (nonstandard) sense - using gates which can have arbitrary rational probability distribution of which binary function to output. For example a gate which works as AND(x,y) with probability $\frac{7}{13}$, as OR(x,y) with probability $\frac{5}{13}$ and outputs constant $0$ with probability $\frac{1}{13}$.
The computation is allowed to have 2 sided bounded error - that is, we say that the circuit computes a function f if for every input $x_1, \ldots, x_n$ it outputs the correct result $f(x_1, \ldots, x_n)$ with probability $\geq 2/3$.

Is it possible to similarly prove that there exists a Boolean function that requires probabilistic circuit of a superpolynomial size?
The problem is that there are infinitely many different types of gates. Is there any neat trick that could be applied?

The question I actually am interested in is the following - does there exist a Boolean function such that every 2-way probabilistic finite automata (having arbitrary rational transition probabilities) that recognizes it with 2-sided error has superpolynomial number of states? Just thinking that people are more familiar with circuits than 2-way automata and the proof could be transferred from one domain to another.

Update:

More formally I want to prove the following:

  There exists an infinite sequence of Boolean functions $f_1, f_2,
\ldots$ of $n_1, n_2, \ldots$ ($n_1 < n_2 < \ldots$) variables such
  that for every sequence of 2pfas $P_{f_1}, P_{f_2}, \ldots$ such that
  $P_{f_i}$ recognizes $f_i$ with 2-sided bounded error (that is for
  every word $x_1, \ldots, x_{n_i}$ accepts it with probability $\leq
\frac{1}{3}$ if $f_i(x_1, \ldots, x_{n_i}) =0$ and probability $\geq
\frac{2}{3}$ if $f_i(x_1, \ldots, x_{n_i})=1$) the number of states
  grows superpolynomially: for every polynomial $p(n)$ exists $i$ such that the number of
  states $\left| P_{f_i} \right| > p(n_i)$.

If we allowed the 2pfa to have only transition probabilities of $\{0, \frac{1}{2}, 1\}$ (or some other restricted set (size of which might depend on $n$ and even grow exponentially in terms of $n$)) then it is provable by a counting argument. Question is - is it still true if all rational transition probabilites are allowed?

You can still argue by counting. No matter how randomness is used, there is a way to fix the randomness in such a way that the function is computed correctly deterministically on at least $\frac{2}{3}2^n$ inputs. Thus assuming any function can be computed with error at most $\frac{1}{3}$ by some circuit in size $S$, any function can be described by a circuit of size $S$ together with a set of at most size $\frac{1}{3}2^n$ of inputs where the answer is incorrect.


Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$ Which natural (well studied) classes of graphs have treewidth that scales as $\Theta(n^\alpha)$ in the number $n$ of vertices, with $1/2 < \alpha < 1$?

The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth should be $\Theta(n^{1-1/d})$. This family of graphs is contained in the family of graphs of low density graphs in $\mathbb{R}^d$. I have a paper (with Kent Quanrud) on low density graphs: http://sarielhp.org/p/14/low_density/low_density.pdf. Sorry for the shameless self promotion, etc.


Choices for the group in Public Key Cryptography I am only aware of two alternatives for the group used in Diffie-Hellman scheme (and similar ones) where logarithms are conjectured to be hard. Those are $\mathbb{F}_p$ and Elliptic Curves. Are there any other explored choices?

Dan Boneh's survey article on the decisional Diffie Hellman problem lists several candidate groups for which the DDH problem is hard, reproduced here:

  Let $p=2p_1 + 1$ where both $p$ and $p_1$ are prime. Let $Q_p$ be the subgroup of quadratic residues in $\mathbb{Z}^*_p$. It is a cyclic group of prime order. This family of groups is parameterized by $p$.
  More generally, let $p = aq+1$ where both $p$ and $q$ are prime and $q > p^{1/10}$. Let $Q_{p,q}$ be the subgroup of $\mathbb{Z}_p^*$ of order $q$. This family of groups is parameterized by both $p$ and $q$.
  Let $N=pq$ where $p,q,\frac{p-1}2,\frac{q-1}2$ are prime. Let $T$ be the cyclic subgroup of order $(p-1)(q-1)$. Although $T$ does not have prime order, DDH is believed to be intractable. The group is parameterized by $N$.
  Let $p$ be a prime and $E_{a,b}/\mathbb{F}_p$ be an elliptic curve where $|E_{a,b}|$ is prime. The group is parameterized by $p,a,b$.
  Let $p$ be a prime and $J$ be a Jacobian of a hyper elliptic curve over $\mathbb{F}_p$ with a prime number of reduced divisors. The group is parameterized by $p$ and the coefficients of the defining equation.

In particular, #3 is not among the flavors listed in your question.


Improving Cook's generic reduction for Clique to SAT? I am interested in reducing $k$-Clique to SAT without making the instance much larger.

Clique is in NP so it can be reduced to SAT using logarithmic space.
The straightforward Garey/Johnson textbook reduction blows up the instance to cubic size.
However, $k$-Clique is in P for every fixed $k$ so there "ought" to be an efficient reduction at least for fixed $k$.

One way to build the reduction is by using the SAT variables as a characteristic vector, with a variable that is set to true indicating that the associated vertex is in the clique.
This reduction is natural but creates a SAT instance of quadratic size if the graph is sparse.
For a sparse graph, quadratically many clauses are required to enforce that in every pair of non-adjacent vertices at most one vertex may be in the clique.

Let's try to do better than $O(n^2)$.

The generic reduction of Cook/Schnorr/Pippenger/Fischer works by first taking a polynomially time-bounded NDTM that decides the language, simulating the NDTM by an oblivious DTM, simulating the oblivious DTM by a circuit, and then simulating the circuit by a 3-SAT instance.
This creates a 3-SAT instance of size $O(t(n)\log t(n))$ if the NDTM time bound is $t(n)$.
The log factor seems unavoidable due to overhead when simulating by an oblivious machine.
For $k$-Clique one seems to have $t(n) = O(nk)$, which yields a 3-SAT instance of $O(nk(\log n + \log k))$ size, which is quasilinear for fixed $k$.
In his 1988 paper Cook asked whether a better generic reduction exists for languages in NP, and as far as I know this is still open.
However, Clique has a lot of structure so perhaps one can do better in this case.

  Is there a better reduction known from Clique to SAT?

In particular, is it possible for fixed $k$ to reduce $k$-Clique to SAT while keeping the increase in instance size linear?
Or can one use an existing result to argue that this is unlikely to be possible?
I have tried using Fortnow/Santhanam and Dell/van Melkebeek but the overheads seem too large for these results to imply anything specific.

(I have been working with a reduction that seems to avoid the log factor, but before wasting more time on the gory details to verify its correctness, I'd like to know if such a reduction is already known, or if it is unlikely to exist.)

You can express $k$-clique as a SAT instance with $O(nk)$ variables and $O(nk^2)$ clauses.  For fixed $k$, this is linear in $n$.

Let $x_{iv}=1$ if $v$ is the $i$th vertex in the clique (by lexicographically sorted order).  In other words, $x_i$ is a "one-hot" encoding of the $i$th vertex in the clique (it is the characteristic vector for a set with one element).  This introduces $nk$ variables.

Now for each $(i,j)$ you can enforce that the corresponding two vertices are connected by an edge, using $n$ clauses.  e.g., one clause is $(\neg x_{iu} \lor x_{jv_1} \lor \dots \lor x_{jv_m})$ where $v_1,\dots,v_m$ are the vertices that are adjacent to vertex $u$.  You get one clause per vertex $u$.  This introduces a total of $O(nk^2)$ clauses.

For each $i$, you can enforce that $x_i$ is a vector of Hamming weight 1 and that $x_i < x_{i+1}$, using $O(n)$ clauses.  This adds a total of $O(nk)$ more clauses.

It might be possible to do better by using $k \lg n$ variables to represent the vertices in the clique ($\lg n$ bits suffice to represent the $i$th vertex in the clique) and then building a circuit to check whether a set of $k$ vertices correspond to a clique.  One approach to build such a circuit might be by constructing the list of all $k(k-1)/2$ pairs of these vertices, in sorted order, then comparing that to the list of edges using the Merge procedure from Mergesort, or something like that.  It might be possible to get something like a $O((n+m+k^2) \text{poly}(\lg n))$-size circuit, which then translates to a SAT instance of the same size (where $m = $ the number of edges in the graph).  I haven't tried to work out the details to see whether it's actually possible, though.


What is necessary and/or sufficient requirement for a subring of a field to be computable? As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring?

Conditions on either field or subring are fine.

The question of how to find computable substructures of algebraic structures was studied by Jens Blanck and myself in the paper "Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions". There we give general conditions on what it means for a substructure of an algebraic structure to be computable. Let me give a summary, but I recommend reading the paper for thorough understanding.

We work with respect to an arbitrary model of computation, such as Turing machines, Type II Turing machines, topological models, $\lambda$-calculus, a programming language, etc. The formalism which encompasses all of these is realizability theory.

There is an embedding $\nabla : \mathsf{Set} \to \mathsf{Asm}$ from the category of sets to the category of assemblies (over some partial combinatory algebra, see our paper). The category of assemblies can be thought of as a category of sets equipped with a computability structure. The embedding $\nabla$ maps sets to sets equipped with trivial computability structure, namely, if $S$ is a set then $\nabla S$ is the set $S$ in which every $x \in S$ is realized by every realizer (if you've never heard of realizability before, think of Gödel encodings of objects). Intuitively this says that when we look at a realizer we have absolutely no idea which element it represents.

Assume a fixed signature $\Sigma$ for an algebraic structure (such as one of a ring) and let $\mathcal{A}$ be a $\Sigma$-algebra in the category of sets, i.e., what people normally think of when they say $\Sigma$-algebra. Because $\nabla$ preserves products, it maps $\mathcal{A}$ to a $\Sigma$-algebra $\nabla \mathcal{A}$ in $\mathsf{Asm}$. Now, a computable $\Sigma$-subalgebra of $\mathcal{A}$ is just a subalgebra of $\nabla \mathcal{A}$ in the category $\mathsf{Asm}$.

When we unravel what this means in terms of realizers we see that it is the expected thing: for $\mathcal{B}$ to be a computable subalgebra of $\mathcal{A}$ it has to be a subalgebra in the usual sense (of course), you have to give a realizability relation for the carrier of $\mathcal{B}$ which explains how the elements of carrier are realized, and all the operations on $\mathcal{B}$ must be realized (computable) with respect to the chosen realizability relation on the carrier.

It occurs to me that maybe you are asking the following question: given a subalgebra $\mathcal{B}$ of an algebra $\mathcal{A}$ is there some computable structure on $\mathcal{B}$, i.e., is there some way of making all the operations on $\mathcal{B}$ computable? First note that $\mathcal{A}$ does not play a role here. Second, if the only requirement is that the operations on $\mathcal{B}$ be computable, then the answer is always "yes, just use the trivial computability structure $\nabla \mathcal{B}$". That is, represent every element of $\mathcal{B}$ with any realizer you want, say 42, and then all operations are implemented by functions that always return 42. In order to avoid such a silly answer you have to impose further conditions -- and that's what our paper is about.


Does every greedy algorithm have matroid structure? It is well established that for every matroid $M$ and any weight function $w$, there exits an algorithm $\mbox{GreedyBasis}(M,w)$ which returns a maximum weight basis of $M$. So, is the reverse direction also true? That is, if there is some greedy algorithm, then there must be some matroid structure also.

Actually, the complete and general description of a problem that can be solved by a greedy algorithm is a matroid embedding, which generalizes both the concept of a matroid and that of a greedoid. The answer is no—a problem solvable by a greedy algorithm need not have a matroid structure, but it will have the structure of a matroid embedding (which is, alas, much more complicated).

A mental model for some of this could be finding minimum spanning trees. The structure used by Kruskal's algorithm is a matroid, but that used by Prim's algorithm (which requires a start node) is not. (It is, however, a greedoid—and a matroid embedding.)

Helman et al. (1993), in their paper An Exact Characterization of Greedy Structures define their notion of a greedy algorithm in terms of set systems, which is the same formalism that is used for matroids and greedoids. A set system $(S,\mathcal{C})$ consists of a set $S$ and a collection $\mathcal{C}$ of subsets of $S$, the so-called feasible sets. A basis for the set system is a maximal feasible set, that is, a set that is feasible but not contained in any other feasible set. An objective function $f:2^S\rightarrow\mathbb{R}$ associates each subset of $S$ with a value. An optimization problem, in this formalism, consists in finding a basis of maximum objective value for a given set system and objective function.

The greedy algorithm, defined in terms of this formalism, is quite simple: You start with the empty set, and successively add a single element until you reach a basis, always ensuring that (i) your set is feasible at each step, and (ii) the element you add maximizes the objective function of the resulting result, wrt. all the alternative elements you could have added. (That is, conceptually, you try adding all feasible alternatives, and choose the one yielding the highest objective value.)

You could, perhaps, argue that there might be other forms of greedy algorithm, but there are several textbooks on algorithms and combinatorial optimization that describe this set-system based algorithm as the greedy algorithm. That doesn't prevent you from describing something that doesn't fit, but could still be called greedy, I suppose. (Still, this does cover anything that could potentially have a matroid structure, for example, though it is much more general.)

What Helman et al. do is that they describe when this algorithm will work. More specifically:

They show that for linear objective functions (where the objective value is the sum of element weights), the greedy algorithm will work exactly on the structure they define as a matroid embedding;
They give a similar characterization for so-called bottleneck objectives (where the objective value of a set is equal to the minimum over the individual element weights); and
They give an exact characterization of which objective functions (beyond linear ones) are optimized by the greedy algorithm on matroid embeddings.


What is the significance of abstract linear algebra in machine learning/computer vision research? I am a computer science research student working in application of Machine Learning to solve Computer Vision problems.

Since, lot of linear algebra(eigen-values, SVD etc.) comes up when reading Machine Learning/Vision literature, I decided to take a linear algebra course this semester.

Much to my surprise, the course didn't look at all like Gilbert Strang's Applied Linear algebra(on OCW) I had started taking earlier. The course textbook is Linear Algebra by Hoffman and Kunze. We started with concepts of Abstract algebra like groups, fields, rings, isomorphism, quotient groups etc. And then moved on to study "theoretical" linear algebra over finite fields, where we cover proofs for important theorms/lemmas in the following topics:

  Vector spaces, linear span, linear independence, existence of basis.
  Linear transformations. Solutions of linear equations, row reduced
  echelon form, complete echelon form,rank. Minimal polynomial of a
  linear transformation. Jordan canonical form. Determinants.
  Characteristic polynomial, eigenvalues and eigenvectors. Inner product
  space. Gram Schmidt orthoganalization. Unitary and Hermitian
  transformations. Diagonalization of Hermitian transformations.

I wanted to understand if there is any significance/application of understanding these proofs in machine learning/computer vision research or should I be better off focusing on the applied Linear Algebra?

In my experience (YMMV) linear algebra is very much used as a tool in Machine Learning and Computer Vision, with little interest in the underlying mathematics.

That said, you'll need a more mathematical understanding than, say, a games programmer or a basic researcher in the natural sciences. Basically you'll need to know enough to take a method like PCA apart and put it back together again, but you don't need to worry about your matrices containing anything other than real values.

It sounds like this course is starting off deeper and more general than you want, but the list of topics suggests that you are moving in the right direction. So long as some attention is given to how to translate the mathematical methods into the computer. It's one thing to suggest that an SVD decomposition exists, and another to actually compute it.

The deep mathematical understanding won't hurt, but there's no guarantee that all of it will be useful to you.


Best current space lower bound for SAT? Following on from a previous question,

  what are the best current space lower bounds for SAT?

With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses a binary worktape alphabet.
A constant additive term is unavoidable since a TM can use internal states to simulate any fixed number of worktape cells.
However, I am interested in controlling the multiplicative constant that is often left implicit:
the usual setup allows arbitrary constant compression via larger alphabets so the multiplicative constant is not relevant there, but with a fixed alphabet it should be possible to take it into account.

For instance, SAT requires more than $\log\log n + c$ space; if not then this space upper bound would lead to a time upper bound of $n^{1+o(1)}$ by simulation, and thereby the combined $n^{1.801+o(1)}$ space-time lower bound for SAT would be violated (see the linked question).  It also seems possible to improve this argument to argue that SAT requires at least $\delta\log n + c$ space for some small positive $\delta$ that is something like $0.801/C$, where $C$ is the constant exponent in simulation of a space-bounded TM by a time-bounded TM.

Unfortunately $C$ is usually quite large (and certainly at least 2 in the usual simulation, where the tapes of a TM are first encoded on a single tape via a larger alphabet).  Such bounds with $\delta \ll 1$ are rather weak, and I would be especially interested in a space lower bound of $\log n + c$.
An unconditional time lower bound of $\Omega(n^d)$ steps, for some large enough constant $d > 1$, would imply such a space lower bound via simulation.  However, time lower bounds of $\Omega(n^d)$ for $d>1$ are not currently known, let alone for large $d$.

Put differently, I'm looking for something that would be a consequence of superlinear time lower bounds for SAT, but which might be possible to obtain more directly.

Looks like the best bound known (for multitape Turing machines) is logarithmic.

Suppose $\delta\log n$ bits of binary worktape is enough to decide whether any $n$-bit CNF formula is satisfiable, for all large enough $n$.
By the standard simulation, a TM with $q$ states that uses at most $s$ bits of space can be simulated by a TM that has at most $qns2^s = 2^{s+\log n + \log s + \log q}$ different configurations.
Whenever the machine accepts, there is a sequence of (nondeterministic) moves reaching an accepting state that is at most as long as this number of configurations.
When $s = \Omega(\log n)$, this is at most $2^{s(2+o(1))}$ (note that $q$ remains the same for all input lengths $n$).
On a separate counter tape, $M$ can first write this quantity in unary, then at each step of the simulation erase one of the symbols of the counter, and terminate the computation if it ever runs out of counter symbols.
This creates a constant factor of overhead (something like 3), which is absorbed by the $o(1)$ term in the exponent.
Hence $2^{s(2+o(1))}$ steps are sufficient.

By assumption $s \le \delta\log n$, so the time-space product is at most $\delta\log n2^{\delta\log n(2+o(1))} = n^{\delta(2+o(1))}$.

Rahul Santhanam showed in 2001 (see doi:10.1016/S0020-0190(00)00227-1) that the space-time product for a Turing machine deciding SAT must be at least $\Omega(n^{2-o(1)})$; his argument applies also to nondeterministic machines.
Hence $\delta \ge 1$, and at least $\log n$ bits of binary worktape are needed.

More generally, additional worktapes and a larger worktape alphabet change the exponent by a constant factor.  This ultimately reduces the factor $\delta$, but the space lower bound is still $\Omega(\log n)$.


Positive topological ordering Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of the weights is non-negative. Or if you prefer order-theoretic terminology, I have a weighted partial order and I want a linear extension such that each prefix has non-negative weight. What is known about this problem? Is it NP-complete or solvable in polynomial time?

This problem appears to be very similar to SEQUENCING TO MINIMIZE MAXIMUM CUMULATIVE COST, problem [SS7] in Garey & Johnson. To wit:

  INSTANCE: Set $T$ of tasks, partial order $\prec$ on $T$, a "cost" $c(t) \in Z$ for each $t \in T$ (if $c(t) < 0$, it can be viewed as a "profit"), and a constant $K \in Z$.

  QUESTION: Is there a one-processor schedule $\sigma$ for $T$ that obeys the precedence constraints and which has the property that, for every task $t \in T$, the sum of the costs for all tasks $t'$ with $\sigma(t') \leq \sigma(t)$ is at most $K$?

I am uncertain whether the problem remains NP-complete when $K$ is fixed to 0. G&J mention that the problem remains NP-complete if $c(t) \in \{-1,0,1\}$ for all $t \in T$.


Almost universal string hashing in $Z_{2^n}$ and sublinear space Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$:

For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in \mathbb{Z}_p$. Dietzfelbinger et al. showed in "Polynomial Hash Functions Are Reliable" that $\forall x \neq y, P_a(h^1_a(x) = h^1_a(y)) \leq m/p$.
For $x_i \in \mathbb{Z}_{2^b}$, $h^2_{\vec{a} = \langle a_0 a_1 a_2 \dots a_{m+1}\rangle}(\vec{x}) = (a_0 + \sum a_{i+1} x_i \bmod 2^{2b}) \div 2^b$ for $a_i \in \mathbb{Z}_{2^{2b}}$. Lemire and Kaser showed in "Strongly universal string hashing is fast" that this family is 2-independent. This implies that $\forall x \neq y, P_\vec{a}(h^2_\vec{a}(x) = h^2_\vec{a}(y)) = 2^{-b}$

$h^1$ uses only $\lg p$ bits of space and bits of randomness, while $h^2$ uses $2 b m + 2 b$ bits of space and bits of randomness. On the other hand, $h^2$ operates over $\mathbb{Z}_{2^{2b}}$, which is fast on actual computers.

I'd like to know what other hash families are almost-universal (like $h^1$), but operate over $\mathbb{Z}_{2^b}$ (like $h^2$), and use $o(m)$ space and randomness.

Does such a hash family exist? Can its members be evaluated in $O(m)$ time?

Yes. Wegman and Carter's "New hash functions and their use in authentication and set equality" (mirror) shows a scheme meeting the requirements stated (almost universal, over $\mathbb{Z}_{2^b}$, sublinear space and randomness, linear evaluation time) based on a small number of hash functions drawn from a strongly universal family.

This is sometimes called "tree hashing", and it is used in "Badger - A Fast and Provably Secure MAC" by Boesgaard et al.


Number of bounded minimum vertex covers Minimum Vertex Cover problem

Input: $G=(V,E)$ and Parameter $k$

Output: Decide whether there exists minimum vertex cover of size at most $k$.

Question:-
Can we bound the number of minimum vertex covers of size at most $k$ on general graphs?

C=number of minimum vertex covers of size at most $k$

Is C bounded by $f(k)$? If not can you provide example? If yes what is $f(k)$

The number of inclusion-minimal vertex covers of size at most $k$ is at most $2^k$: They can be enumerated by a search tree algorithm that initially has a budget of $k$, then branches as long as the graph contains an edge $\{u,v\}$ into the two cases to add either $u$ or $v$ to the vertex cover. Each branch can be solved recursively and the parameter $k$ is reduced by one in each case.

The number of minimal vertex covers of size at most $k$ obviously bounds the number of minimum vertex covers of size at most $k$ as well.

Further information can be found in

Henning Fernau:
On Parameterized Enumeration. COCOON 2002: 564-573 dx.doi.org/10.1007/3-540-45655-4_60

and

Peter Damaschke:
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3): 337-350 (2006)
http://dx.doi.org/10.1016/j.tcs.2005.10.004


Is this constrained planar triangulation algorithm $O(m \log m)$? Background: I am implementing triangle mesh CSG using symbolically perturbed exact arithmetic.  One of the required subalgorithms is retriangulating a triangular face $T_0$ of the input mesh cut by some number of edges defined by intersections between other faces $T_i$.  This reduces to a constrained triangulation problem in the plane.  However, I would like to minimize the degree of the predicates involved, and ideally use only triangle orientation tests where only of the triangle edges is a constraint edge (this has the lowest possible degree when mapped up into 3D).

Concretely, my plane triangulation problem is the following: I have an outer triangle $T$ in the plane, and $n$ constraint segments $S_i$ inside $T$.  The segments may intersect in their interiors; let $m \ge n$ be the number of vertices including the intersection vertices.  I am seeking an $O(m \log m)$ algorithm.

Candidate algorithm: Generate a BSP tree by picking a random input segment $S_i$, dividing the remaining input segments into left and right sets (which will overlap whenever another segment $S_j$ crosses line $S_i$), and recursing.  Triangulate the resulting convex polygons arbitrarily, then incrementally remove all unnecessary points generated by the algorithm (those where segments $S_j$ crosses line $S_i$ but not segment $S_i$).

Question: Has this algorithm or a variant been studied previously?  Is it $O(m \log m)$ time worst case?  Note that the final removal step is not obviously linear time even if only $O(m)$ unnecessary points are generated, so the algorithm could easily be much slower.

Unfortunately, this algorithm is $\Omega(n^2)$ even if no unnecessary vertices are generated.  If the $S_i$ form a convex polygon inside $T$, the BSP tree is degenerate regardless of the order in which segments are inserted.


Moggi's computational metalanguage In Notions of Computation and Monads Moggi models the notion of a computation of type $A$, $TA$, using a monad $T$. Among other things this ensures the $T\eta$ rule:

$$\frac{x: A \vdash a:TB}{x:A \vdash let \,  y \Leftarrow a \, in\, [y] = a}$$

This rule prevents distinct computations having the same value. Is there a weakened notion of a monad that does not yield the $T\eta$ rule? Has this question already been studied? I'm particularly interested in the logic you get when you drop $T\eta$ from Moggi's rules for the simple metalanguage, but keep the other rules in place (table 4 in the pdf).

It is an interesting problem to figure out what bothers the OP. First of all, it is not at all the case that the equation put forward by the OP says "different computations have the same value". For instance, the computations

do _ <- putStr "foo"
   return 42

and

do _ <- putStr "bar"
   return 42

both "have" value 42 but are different, since one prints out foo and the other bar.

The problem really arises elsewhere, namely in the idea that "a computation has a value". Consider the following monads:

The Maybe monad: a computation may have a value (Just v), or have no value at all (Nothing).
The non-determinism monad: a computation results in a set of (possible) values. What does it mean that it "has" a value? Has all of them? One of them?
The probability monad: a computation results in a probability distribution of values. Again, in what sense does such a computation "have a value"?
The continuation monad: a computation results in a continuation. What does it mean for a continuation to "have a value"?

It is best to just forget the idea that in general a computation gives back a value, two values, possible values, or anything like that.

There may be particular monads for which it does make sense to speak about "computations having values", but not for all monads.

The OP also suggests that intensional features of computations (one computation takes a different number of steps than another) should be expressible with monads. This is true, but whatever intensional features you want to capture with the monad (memory usage, time), you have to expose them explicitly in the monad. For instance, we could do this:

data Timed a = Timing (a, Integer)

instance Monad Timed where
    return x = Timing (x, 0)
    (>>=) (Timing (x, n)) f = (let Timing (y, m) = f x in Timing (y, n + m + 1))

x :: Timed Integer
x = do u <- return 14
       v <- return 3
       return (u * v)

y :: Timed Integer
y = do u <- return 14
       v' <- return 1
       v'' <- return 2
       v <- return (v' + v'')
       return (u * v)

Here x and y both "have" value 42, but the timing is different since y takes four steps to compute and x takes just two.