Can the mutual information of a "cell" be negative? Please forgive me if this is not the right Stack Exchange (I also posted it at Cross Validated).  Please also forgive me for inventing terms.

For discrete random variables X and Y, the mutual information of X and Y can be defined as follows:
$I(X;Y) = \sum_{y \in Y} \sum_{x \in X}
                 p(x,y) \log{ \left( \frac{p(x,y)}{p_1(x)\,p_2(y)}
                              \right) }, \,\!$

I will define the mutual information of a "cell" $x_0$ to be:
$CI(x_0,Y) = \sum_{y \in Y} p(x_0,y) \log{ \left( \frac{p(x_0,y)}{p_1(x_0)\,p_2(y)}
                              \right) }, \,\!$

I'm not sure if this quantity goes by another name.  Essentially I'm restricting focus to a single state of variable X (and then the full MI can be calculated by summing all the cell MIs).

My question: is it guaranteed that $CI(x_0,Y) \ge 0$?  We know $I(X;Y)\ge0$ and we know that the pointwise mutual information can be negative.  I feel like CI should be nonnegative and that I might be missing some obvious proof.

By the simple transformation $p(x_0, y) = p(x_0) p(y | x_0)$ your expression merely becomes $p(x_0) KL(p (y|x), p(y))$, where $KL(p,q)$ is the Kullback-Leibler divergence, and is always positive. therefore, your expression is always positive.


Minimum True Monotone 3SAT I am interested in a SAT variation where the CNF formula is monotone (no variables are negated). Such a formula is obviously satisfiable.

But say the number of true variables is a measure of how good our solution is.  So we have the following problem:

MINIMUM TRUE MONOTONE 3SAT

INSTANCE: Set U of variables, collection C of disjunctive clauses of 3 literals, where a literal is a variable (not negated).
SOLUTION: A truth assignment for U that satisfies C.
MEASURE:  The number of variable that are true.

Could someone give me some helpful remarks on this problem?

This problem is the same as the Vertex Cover problem for $3$-uniform hypergraphs:
given a collection $H$ of subsets of $V$ of size $3$ each, find a minimal subset $U\subseteq V$ that intersects each set in $H$.

It is therefore NP-hard, but fixed parameter tractable.
It is also NP-hard to approximate to within a factor of $2-\epsilon$ for every $\epsilon>0$. This was shown in the following paper:

Irit Dinur, Venkatesan Guruswami, Subhash Khot and Oded Regev.
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover,
SIAM Journal on Computing, 34(5):1129–1146, 2005.


Complexity of the coset intersection problem Given the symmetry group $S_n$ and two subgroups $G, H\leq S_n$, and $\pi\in S_n$, does $G\pi\cap H=\emptyset$ hold?

As far as I know, the problem is known as the coset intersection problem. I am wondering what's the complexity? In particular, is this problem known to be in coAM?

Moreover, if $H$ is restricted to be abelian, what does the complexity become?

Moderately exponential time and $\mathsf{coAM}$ (for the opposite of the problem as stated: Coset Intersection is typically considered to have a "yes" answer if the cosets intersect, opposite of how it's stated in the OQ.)

Luks 1999 (free author's copy) gave a $2^{O(n)}$-time algorithm, while Babai (see his 1983 Ph.D. thesis, also Babai-Kantor-Luks FOCS 1983, and a to-appear journal version) gave a $2^{\tilde{O}(\sqrt{n})}$-time algorithm, which remains the best known to date. Since graph isomorphism reduces to quadratic-sized coset intersection, improving this to $2^{\tilde{O}(n^{1/4-\epsilon})}$ would improve the state of the art for graph isomorphism.


Cover a Concave Polygon with a minimum number of rectangles I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.

I thought about trying to decompose my concave polygon into triangles that produce a set of minimumally overlapping rectangles minimally bounding each triangle and then merging those rectangles into larger ones. However, I don't think this will work for small notches in the edges of the polygon. The triangles created by the reflex vertices on those notches will create the wrong rectangles. I am looking for rectangles that will span/ignore notches.

I don't really know anything about computational geometry, so I'm not really sure on how to begin asking the question.

I found other posts that were similar, but not what I need:

split polygon into minimum amount of rectangles and triangles
Covering an arbitrary polygon with minimum number of squares
Find $k$ rectangles so that they cover the maximum number of points
Algorithm for finding the fewest rectangles to cover a set of rectangles

Some examples: Black is the input. Red is the acceptable output.

Another exmaple: The second output is prefered. However, generating both outputs and using another factor to determine preference is probably necessary and not the responsibility of this algorithm.

Polygons that mimic curves are extremely rare. In this scenario much of the area of the rectangles is wasted. However, this is acceptable because each rectangle obeys the max width constraint.

Also, I found this article to be close to what I need:

Covering with rectangular pieces by Paul Iacob, Daniela Marinescu, and Cristina Luca

Maybe a better question is "How can I identify rectangular-like portions of a concave polygon?"

Here is an image showing the desired implementation:

The green is the actual material usage. The red rectangles are the layouts. The blue is the MBR of the entire polygon. I am thinking I should try to get little MBRs and fill them in. The 2-3 green rectangles in the upper left corner that terminate into the middle of the polygon are expensive. That is what I want to minimize. The green rectangles have a min and max width and height, but I can use as many rows and columns necessary to cover a region. Again, I must minimize the number of rectangles that do not span across the input. I can also modify the shape of the green rectangle to fit in small places that is also very expensive. In other words, getting as many rectangles as possible to span as much as possible is ideal.

This is a variant of geometric set cover. Depending on the exact settings, you might be able to do some good approximation. The problem is of course NP-Hard. The natural huersitics are to use greedy algorithm (always pick the rectangle/strip that covers the most area not covered yet. The alternative technique is to use reweighing. There are some interesting theoretical results, but frankly, nothing that should be too useful in practice. One interesting hueristic you might want to try, is to first decompose your polygon into minimal number of convex shapes (using Keil dynamic programming algorithm), and then covering each convex polygon separately...


List of theorems stating that P does not equal NP if and only if I think it would be a good idea to make a list of theorems stating that P does not equal NP if and only if such and such exits, some complexity class is contained in another complexity class and so on and so forth.

Here is a one:

Mahaney's Theorem: There is no sparse NP-complete set if and only if $P \ne NP $
(under Karp reduction).

Another one is:

$P \ne NP$ if and only if $P \ne PH$


Vertex Cover applications in the real world What applications does the Vertex Cover Problem have in the real world?

Which industry or research projects use actually implemented software that is based on theoretical results for the Vertex Cover problem? In particular, are any of the following theoretical results implemented in used software?

Approximation algorithms for Vertex Cover
Exponential-time algorithms for Vertex Cover
Fixed-parameter tractable algorithms for Vertex Cover
Kernelization algorithms for Vertex Cover

Some problems in the area of computational biology seem suitable for practical applications that are not artificial - or at least not as artificial as the problems mentioned by Jukka Suomela.

For instance, people often mention the work by F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters C. Symons, Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments, Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX), ACM/SIAM, Proc. Applied Mathematics 115, 2004.

As the authors state, "One of the applications to which we have applied our methods involves finding phylogenetic trees based on protein domain information, ..." (section 8 of above paper).

A subset of the authors have similar papers on this topic, see, e.g., Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag and Christopher T. Symons, Scalable Parallel Algorithms for FPT Problems, Algorithmica, Volume 45, Number 3, 269-284.

I'm not sure whether the instances used in the experiments were real-world instances or artificial, but I hope the two references give you a good starting point.


What are regular expressions good for? If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous rant. Though there is not a canonical rant for it, I've also been told that regex aren't powerful enough to parse SQL.

I'm a self-taught programmer, so I don't know much about languages from a theoretical perspective. Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

Edit: To clarify, I'd really like a few examples of languages that are used in the real world that fit in the category of regular languages, rather than some axioms or equivalent conditions, etc.

Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

A short answer is: Probably nothing that you call a language.

In theoretical computer science (TCS), a language simply means a set of words.  But in most cases, what people call a “language” outside TCS has some recursive structure.  “Recursive structure” is ambiguous here, but intuitively regular expressions cannot parse them because regular expressions even cannot parse balanced parentheses.

Many compilers use regular expressions for lexical analysis before parsing.  For example, you can decide whether a certain string is a valid identifier in C++ or not by using a regular expression.  This is possible because the language consisting of valid identifiers in C++ is a regular language.  But the set of valid C++ identifiers is usually not called a language outside TCS.

Disclaimers:

Some people distinguish “regular expression” and “regex.”  In this answer, I am talking about regular expressions, not regexes, if we use this convention.
Actual C++ compilers do not probably use a regular expression for valid identifiers because excluding keywords makes the regular expression unmanageable.  They use a different technique to cope with this, but that is not the main point here.


How can I find dependent rounding procedures with the desirable properties? I'm seeking for materials on dependent rounding. However, what I've found are two papers:

Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A., 2006. Dependent rounding and its applications to approximation algorithms. J. ACM
Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K., 2015. An Improved Approximation for K-Median, and Positive Correlation in Budgeted Optimization. SODA ’15

The first one can be used to deal with problems with hard cardinality constraints, while the second one can be used to deal with weighed constraints. I'd like to use dependent rounding as a tool to design (approximation) algorithms and I'm not interested in the mechanism behind the specific dependent rounding procedure. (I think)There should be other dependent rounding procedures with other nice properties. My question is:

How can I find dependent rounding procedures with the desirable properties when designing  approximation algorithms?
Are there tuitorial-level materials on how to use dependent rounding to design approximation algorithms?

Dependent randomized rounding is a broad tool that is used in many approximation algorithms. Lot depends on the problem structure, objective and constraints and there is no single unified answer/framework. Some papers like the ones you mention identify generic settings where one has some nice probabilistic tools and provide some applications. I list a paper below that provides a more general framework and also has pointers to other work on dependent rounding. I also recommend looking at approximation algorithms books such as the ones by Williamson and Shmoys, and Vazirani to see the variety of dependent rounding schemes that are used.

https://arxiv.org/abs/1811.01597 by Nikhil Bansal unifying iterated and dependent rounding.


Complexity of maximising weighted sum of and functions on a set of binary variables Suppose we have a set of binary variables $a_1, ..., a_n$ that $a_i\in\{0,1\}$. Now we define $m$ and functions over a subset of them: $$j\in\{1,...,m\}: f_j=x_1\land x_2\land...\land  x_k$$ in which
$$\{x_1,...,x_k\}\subset\{a_1,...,a_n\}$$

Suppose that each variable $a_i$ has also a cost $c_i$ assigned to it and every function $f_j$ has a profit $p_j$ associated with it. Both variables are non-negative $\forall i,j: p_j,c_i\ge 0$.

The problem is how to maximise profits minus costs over the set of all possible $a_i$s:
$$(1) \max_{a_1,...,a_n} \left\{\sum_j^m p_j f_j - \sum_i^n c_i a_i \right\}$$

Another related problem is to maximise the profit with constrained costs for some constant $C$:
$$(2)   \max_{\sum_i c_i a_i \le C} \left\{\sum_j^n p_j f_j \right\}$$.

Now here here the questions I have:

Can $(1)$ be solved in a strictly polynomial, or
pseudo-polynomial way?
Can $(2)$ be solved in
pseudo-polynomial time?

By pseudo-polynomial we mean assuming bounds on $|c_i|$ and $|p_j|$, can a polynomial time algorithm be achieved?

It's clear that if $(2)$ pseudo-polynomial solution $(1)$ will also have a pseudo-polynomial solution, by iterating over various values of $C$. Therefore in some sense $(2)$ is a more difficult problem. Moreover, knapsack can be seen as a special case of $(2)$ if we set $f_j=a_j$. Therefore it can't be strictly polynomial. But I can't tell much more about the complexity of these two problems.

(1) has a polynomial solution. Consider a graph with source $s$, sink $t$, vertices $U$ corresponding to the variables and vertices $V$ corresponding to the functions. If $f_j = x_1 \land \ldots \land x_k$ then add edges $f_j \to x_i$ for each $i \in \{1,\ldots,k\}$ with capacities equal to $C$ for $C > \sum p_j$. Add edges $x_i \to t$ with capacities $c_i$ and edges $s \to f_j$ with capacities $p_j$. Consider minimum cut between $s$ and $t$ in this graph (it could be easily found with almost any maximal-flow algrorithm). Let $U_s \subseteq U$ and $V_s \subseteq V$ be the sets of vertices in the component of $s$. Then the value of the minimum cut is $$\sum\limits_{i \in U_s} c_i + \sum\limits_{j \not\in V_s} f_j = \underbrace{\sum\limits_{j\in V} f_j}_{\text{constant}} - \underbrace{\left(-\sum\limits_{i \in U_s} c_i + \sum\limits_{j \in V_s} f_j\right)}_{\text{objective function}}$$
Thus if this value is minimised, the objective function is maximised. On the other hand $U_s$ and $V_s$ for minimum cut have the property that if $x_1 \land \ldots \land  x_k = f_j \in V_s$ then $x_1, \ldots, x_k \in U_s$ since otherwise the value of the cut is $\ge C$ which is not optimal. Thus setting $x=1$ for $x \in U_s$ and $x=0$ for $x \not\in U_s$ gives an optimal solution for (1).

The case with arbitrary $p_j$ is $\mathbf{NP}\text{-}\mathrm{complete}$ even with polynomially-bounded $|p_j|$.

If you allow $p_j$ to be negative, you can reduce $\mathrm{max}\text{-}\mathrm{SAT}$ to this problem. For each variable $x_i$ of $\mathrm{max}\text{-}\mathrm{SAT}$ add two variables $x_i$ and $\lnot x_i$ to your input. For each of these pair add the condition $x_i \land \lnot x_i$ with the cost $-C$ for a large enough constant $C$. For all clauses of $\mathrm{max}\text{-}\mathrm{SAT}$ input add the corresponding conjunction with all literals reversed: $x \lor \lnot y \lor z$ becomes $\lnot x \land y \land \lnot z$ (here $\lnot x$ and $\lnot z$ are variables in the new problem). $\lnot x \land y \land \lnot z \iff \lnot (x \lor \lnot y \lor z)$ therefore each unsatisfied conjunctions correspond to satisfied clauses. Thus you can set the cost $p$ for each conjunction as $-1$. For $c_i = 0$ for all $i \in \{1,\ldots, n\}$, $m -\max \left\{\sum\limits_j f_j p_j - \sum\limits_i a_i c_i\right\}$ (where $m$ is the number of clauses in the $\mathrm{max}\text{-}\mathrm{SAT}$ instance) is the maximum number of clauses that could be satisfied in the instance of $\mathrm{max}\text{-}\mathrm{SAT}$ or a value greater than or equal to $C - n$ if the instance is unsatisfiable. Thus $C = 3n$ is "big enough". I.e. for negative $p_j$ there is no polynomial solution even with bounded $|p_j|$ and $|c_j|$ unless $\mathbf{P} = \mathbf{NP}$.


Complexity: simulated annealing vs. quantum annealing How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms?

In Convergence theorems for quantum annealing by Morita and Nishimori, it has been shown that QA performs better than SA. Let's me quote from the Discussion section:

  We have proved strong ergodicity of the inhomogeneous Markov chains
  associated with Quantum Annealing using both Path Integral Monte Carlo
  and Green's Function Monte Carlo methods, mainly with the application
  to the Transverse Field Ising Model in mind, which covers a wide range
  of combinatorial optimization problems. Our proof is quite general in
  the sense that it does not depend on the spatial dimensionality or the
  lattice structure of the system. The convergence of QA is guaranteed
  if the transverse field decreases as $\Gamma(t) \approx
 \frac{const}{t^c}$ asymptotically. This annealing schedule for the
  transverse field is faster than the temperature-annealing schedule,
  the log-inverse law, found by Geman and Geman for Simulated Annealing.

Does this result settle the question of the performances for Simulated vs. Quantum annealings? I have a feeling that we should put a little more context here.

I assume to settle the question we need to find a quantum annealing schedule which is faster than all simulated annealing schedules. The problem can be reduced to finding a quantum annealing schedule which is faster than the fastest simulated annealing schedule. Now, to me, the fastest simulated annealing schedule makes sense only when we know what optimization problem we are talking about. We cannot find the fastest simulated annealing schedule for all conceivable optimization problems. That just doesn't make sense to me.

So, is the performance comparison between SA and QA settled? Is yes, how? If no, how can we do it?

In Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential Schedules a theoretical justification for the exponential cooling schedule was given. The results there basically state that for a fixed computation time N you can always choose an appropriate constant $ C= f(N)$  for an exponential cooling schedule $ \beta = \beta_0 \cdot \exp \left( n f(N) \right) $ with $ f(N) \sim N^{-1} \ln\left(N\right) $, such that simulated annealing will converge. So in light of these results I would say it is clear that simulated annealing can converge faster than quantum annealing, at least for the quantum annealing schedule result you cited. Although, it seems you have to tweak the cooling schedule to the computation time.

A nice overview of theoretically grounded acceleration of simulate annealing is given here Theoretically Grounded Acceleration Techniques for Simulated Annealing


Diameter of Cayley graphs of subgroups of $S_n$ without inverses Babai and Seress proved that given a subgroup $G \leq S_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators and their inverses of length $e^{(1+o(1))\sqrt{n\log n}}$. This bound is optimal since $S_n$ has an element of order $e^{(1+o(1))\sqrt{n\log n}}$.

The classical fact that every element in $S_n$ has order at most $e^{(1+o(1))\sqrt{n\log n}}$, combined with the result of Babai and Seress, shows that given a subgroup $G \leq S_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators of length at most $e^{2(1+o(1))\sqrt{n\log n}}$.

  Can we improve the upper bound $e^{2(1+o(1))\sqrt{n\log n}}$ to $e^{(1+o(1))\sqrt{n\log n}}$?

This question has been inspired by the recent question Automata and a kind of pumping lemma on state transition function.

The answer is yes, we can improve the upper bound to $\mathrm{e}^{(1 + o(1))\sqrt{n\ln n}}$. It was proved in a more recent paper of Babai (Corollary 2.9).


How do you call a subsequence of consecutive elements ? I wrote a function that returns the position of a given subsequence in a sequence. However, I just realized that I used the term "subsequence" incorrectly: according to Wikipedia, the elements of a subsequence don't need to be consecutive. But my function is actually looking for a "subsequence of consecutive elements"... is there a name for this notion? I thought of substring, but it seems to imply a sequence of characters, and my function is not specific to character strings..

I realize it isn't a very critical issue, but I'd like to give my function an accurate name...

Any idea would be appreciated !

In programming languages and libraries, it is usually called either a substring or a slice.

The former term is ubiquitous, and I would not mind using it even if your "characters" are a bit weird.

The latter term is neutral in the sense that it does not refer to strings. See array slicing in Wikipedia for more information and examples.


DFSA and NFSA intersection problem Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem.

For unbounded $k$ it is known the problem is $PSPACE$ complete. What is the scale of $k$ for the problem to be PSPACE complete? Is it $k=\Omega(n)$?

What is the consequence the problem is in $FPT$ having $f(k)poly(n)$ complexity for $f(k)=2^{poly(k)}$?

Is there a result on intersection of deterministic DFSAs which is consistent to $CH$ is $NL$ or $L$ hypothesis (which provides $P=CH\neq PSPACE$)?

How about if the $FSA$s are all non deterministic?

Regarding question (1):
As long as $k$ is $\Omega(n^c)$ for some $c > 0$, then the problem is $PSPACE$-complete.  See this paper by Klaus-Jörn Lange and Peter Rossmanith (1992) for some related results.
https://doi.org/10.1007/3-540-55808-X_33
Regarding question (2):
Say that the intersection problem is parameterized by the number of FSA's.  If this parameterized problem is in $FPT$, then $PTIME \neq NLOGSPACE$.
In fact, the result is quite a bit stronger than that.  Essentially, it says that if for every $\alpha > 0$, there exists $k$ sufficiently large such that the $k$th slice of the parameterized problem is solvable in $O(n^{\alpha \cdot k})$ time, then $PTIME \neq NLOGSPACE$.
See here and here.
Regarding question (3):
I am still trying to understand this question.
Regarding last question:
Both the DFA and NFA parameterized intersection problems (when parameterized by the number of automata) are fpt-equivalent.  In fact, the fpt-equivalence is very strong and preserves the parameter (I called it an LBL-equivalence).  Regarding your question, this implies that if one of them is in $FPT$, then the other is in $FPT$ too.
Additional information:
Part of the reason why we have these hardness results for the parameterized FSA intersection problem is because it is $XNL$-complete under a strong form of fpt-reduction.  $XNL$ is a parameterized complexity class that is related to $k \cdot log(n)$ binary space nondeterministic Turing machines.


Unique SAT vs Exactly $m$ models Unique SAT is the well known problem : given a CNF formula $F$, is it true that $F$ has exactly one model ?

I am interested in « Exactly $m$-SAT » problem : given a CNF formula $F$ and an integer $m>1$, is it true that $F$ has exactly $m$ models ?

Both problems look similar. So my questions are :

1- Is «Exactly $m$-SAT » polytime (many-one or Turing) reducible to Unique SAT?

2- Do you know any reference on the subject ?

Thank you for your answers.

Addendum, first articles about complexity of Exactly $m$ SAT :

1- Janos Simon, On the Difference Between One and Many, In Proceedings of the Fourth Colloquium on Automata, Languages and Programming, 480-491, 1977.

2- Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 23, 325-356, 1986.

In both articles, Exactly $m$ SAT ($m \geq 1$) is shown to be $C=$ complete (under many-one reductions), where the class $C$ is from the Counting Hierarchy (CH) of complexity classes. Informally, $C$ contains all problems which can be expressed as deciding whether a given
instance has at least $m$ many polynomial size proofs (the class $C$ is known to coincide with the class $PP$). The class $C=$ is a variant of $C$, where “exactly $m$” replaces “at least $m$".

For general $m$, exactly-m-sat is strictly harder than u-sat (thus does not reduce to it) unless the PH collapses.  The reason is that PP can be obtained using an existential quantifier over exactly-m-SAT queries (exists m>(half of the assignments) such that exactly-m-SAT), thus if exactly-m-sat is in the k'th level of PH, then PP is in the (k+1)'st level, and then the hierarchy collapses (since P^PP contains PH).  But u-sat is clearly in the second level of PH (actually in a subclass called DP).

On the other hand, as @Tsuyoshi mentioned above, if $m$ is polynomial, then exactly-m-sat is many-one reudcible to u-sat.


Bidirectional typing for dependent types: Why are Sigma, Pi synthesized? According to the Pfenning philosphy of bidirectional typing, as also explained by Dunfield and Krishnaswamy 2013, constructors should be checked, while eliminators should be synthesized. Cconvention is followed for the most part in the tutorial Checking Dependent Types with Normalization by Evaluation: A Tutorial
by David Christiansen. I cannot explain some choices in the tutorial according to the Pfenning philosophy:
The types Sigma x A B and Pi x A B, Nat, Eq A from to, Trivial, and Absurd are all checked in synthesis mode. However, these are kind constructors, as they let us construct values that live in Univ. Why are they checked in synthesis mode?
Can we view these as eliminators of some object that I am unaware of? As an example of what I mean by this, recall that identifiers such as x are also run in synthesis mode. With a bit of squinting, one can convince themselves that identifiers are projections on the context Γ
, and thus deserve to be run in synthesis mode.
Is there a similar explanation for why Pi, Simga, Eq, Trivial, Absurd are typed in synthesis mode? what rule-of-thumb does one use to decide whether these should be typed  in checking or synthesis mode?

IMHO, it's not like constructors are checked, but introduction rules (including tuples, lambdas, data constructors, etc.) are checked (while elimination rules are synthesized). The kind constructors you mentioned are called formation rules, which are not introduction rules. You can also think this way: if a constructor is checked, then it has a corresponding eliminator which is synthesized. If type constructors should be checked, there should be a corresponding thing synthesized. But there's no such thing (you can't pattern match on $\cal U$).


Can all linear lambda calculi be linearity checked syntactically? Given a lambda calculus with explicit linearity and usual application and abstraction, can the linearity check be done on an untyped syntax tree if we keep track of the structural types? Are the explicit operators necessary?

I suspect the answer is yes, from these course notes by Frank Pfenning because syntactic constructs are needed to use $A \& B$, $A \otimes B$, and $A \oplus B$.

However, if named functions exist (as in an actual programming language), some types are clearly necessary: consider the function $cond \colon Bool \to A \& A \multimap A$.

Can type checking and linearity checking be done in two steps, and can linearity checking happen before type checking?

Edit: The algorithm provided in the above course notes type checks linear lambda calculus terms, which includes determining if the term is linearly well-formed. Is it possible to determine if a term is well-typed via a syntactic linear well-formedness check (which would eliminate $\lambda x. x x$) followed by a type check which does not consider linearity? Or is this interaction essential to complete type inference?

I don't want to make a statement about "all linear lambda calculi" since it's hard to make that precise, but for pure linear lambda-calculus the answer is yes.  One way to enforce linearity in pure lambda calculus is by trying to type application and abstraction using the linear implication $A \multimap B$,
$$
\frac{\Gamma \vdash t:A\multimap B\quad \Delta\vdash u:A}{\Gamma,\Delta\vdash t(u):B}
 \qquad
\frac{x:A,\Gamma \vdash t:B}{\Gamma\vdash \lambda x.t:A\multimap B}
$$
together with the linear identity and exchange rules:
$$
\frac{}{x:A\vdash x:A}
 \qquad
\frac{\Gamma,y:B,x:A,\Delta \vdash t:C}{\Gamma,x:A,y:B,\Delta \vdash t:C}
$$

But if you just want to check that a lambda term is linear, types are overkill, and it suffices to check syntactically that every free or $\lambda$-bound variable is used exactly once.

A way to make that a bit more precise is to define the set of linear lambda terms $\Lambda_1(\gamma)$ with a given list $\gamma = x_i,\dots,x_1$ of distinct free variables.  This is really a family of sets (indexed by $\gamma$) generated by the following rules (which can be seen as an abstraction of the typing rules above):
$$
\frac{}{x \in \Lambda_1(x)}
 \qquad
\frac{t \in \Lambda_1(\gamma,y,x,\delta)}{t \in \Lambda_1(\gamma,x,y,\delta)}
 \qquad
\frac{t\in \Lambda_1(\gamma)\quad u \in \Lambda_1(\delta)}{t(u) \in \Lambda_1(\gamma,\delta)}
 \qquad
\frac{t \in \Lambda_1(x,\gamma)}{\lambda x.t \in \Lambda_1(\gamma)}
$$
Then a term $t$ of pure lambda calculus with free variables $\gamma$ is linear just in case $t \in \Lambda_1(\gamma)$.  Note that these rules (like the typing rules) also have the effect of performing scope checking, and thus ruling out certain syntactic expressions which might look linear but violate scoping (e.g., an expression like "$\lambda x.x(y)(\lambda y.\lambda z.z)$", where the variable $y$ is used before it is bound).

Finally, pure linear lambda calculus has the remarkable property that every term is typable (which is related to the fact that it is strongly normalizing).  So, once we know that a lambda term is linear it is always possible to go back and give it a type.  Even more remarkably, the principal type of a term uniquely identifies its $\beta$-normal form, so type inference is in fact equivalent to normalization.  Harry Mairson had a nice paper discussing some aspects of these remarkable properties in Linear lambda calculus and PTIME-completeness (JFP 14:6, 2004).


Concurrent transactions satisfying "serializability" but not "snapshot isolation" In [Lin et al@TODS'2009] (Page 5), a history of concurrent transactions satisfying "serializability" ($\textrm{SR}$) but not "snapshot isolation" ($\textrm{SI}$) is given as follows:

  $H_{example}: s_1 \; s_2 \; w_1(x_1) \; r_2(x_1) \; w_2(x_2) \; w_2(y_2) \; c_1 \; c_2 \; s_3 \; r_3(x_1) \; c_3 \; s_4 \; w_4(y_4) \; a_4$

where, $s_1$ denotes the start of transaction $T_1$; $w_1(x_1)$ denotes the write of $T_1$ of version $v_1$ to data item $x$; $c_1$ denotes the commit of $T_1$; and $a_4$ denotes the abort of transaction $T_4$.

Pictorially (horizontal axis is time),

T1: s1    w1(x1)                      c1
T2:    s2        r2(x1) w2(x2) w2(y2)    c2
T3:                                         s3 r3(x1) c3
T4:                                                      s4 w4(y4) a4

My Confusion:

However, as my basic understanding, Serializability is strictly stronger than snapshot isolation. In particular, we have a hierarchy of isolation levels as shown in the following figure copied from [Berenson et al@MSR-TR'1995].

My question:

  What is wrong with my understanding and what is going on here?

  Any comprehensive references on the relationships among $\textrm{SI}$, $\textrm{SR}$, and maybe other isolation levels are appreciated.

References:

([Lin et al@TODS'2009]) Snapshot Isolation and Integrity Constraints in Replicated Databases

(Berenson et al@MSR-TR'1995) A Critique of ANSI SQL Isolation Levels

Answer my own question:

I am not sure with the ideas below. Both comments and answers from experts are highly appreciated. Any references are also welcome.

I think the confusion arises from the fact that the two definitions of serializability ($\textrm{SR}$, for short) adopted in [Lin et al@TODS'2009] and [Berenson et al@MSR-TR'1995] are different.

The SR in [Lin et al@TODS'2009]:

In [Lin et al@TODS'2009] (at least in the test of $H_{example}$), the serializability is the classic One-Copy Serializability (or, $\textrm{1-SR}$) introduced in [Bernstein et al@TODS'1983].

To tell if an multiversion (or MV) history is $\textrm{1-SR}$, we should first decide on a version order $\ll$ (which is a total order) for each data item. Given a history $H$ and a version order $\ll$, an multiversion serialization graph $MVSR(H, \ll)$ can be constructed. As a consequence, we have

  1-SR Theorem: An MV history $H$ is $\textrm{1-SR}$ iff there exists a version order $\ll$ such that $MVSG(H, \ll)$ is acyclic.

Back to the history $H_{example}$, the version order for $x$ can be chosen as $x_1 \ll x_2$. It is easy to show, according to the above theorem, that $H_{example}$ is $\textrm{1-SR}$ because it is equivalent to the serial history of $T_1 \; T_3 \; T_2$.

The SR in [Berenson et al@MSR-TR'1995]:

The $\textrm{SR}$ adopted in [Berenson et al@MSR-TR'1995] is defined by avoiding phenomena ($P$) and anomalies ($A$). In this sense, Snapshot Isolation (or $\textrm{SI}$) avoids $P_0, P_1, A_3, A5A, P4$. The $\textrm{SR}$ here is thus strictly stronger than $\textrm{SI}$ because it further avoids $A5B$.

Back to the history $H_{example}$, it even does not avoid $P_1$ which indicates a "dirty read". Notice that $P_1$ (instead of $A_1$) prohibits an execution sequence if something anomalous might in the future. Although $r_2(x_1)$ reads-x-from $w_1(x_1)$ that is committed later on, it is still a "dirty read". In this way, it does not satisfy $\textrm{SR}$.

The perspective of computational complexity:

[Bernstein et al@TODS'1983] also shows that

  It is $\textrm{NP}$-complete to decide whether an MV history is 1-$\textrm{SR}$.

However, if we know that $H$ is $\textrm{SI}$ in advance, we can decide efficiently whether it is 1-$\textrm{SR}$. The key here is that the version order $\ll$ has been determined by $\textrm{SI}$. See [Cahill et al@SIGMOD'2008].

Furthermore, I guess that, for an $\textrm{SI}$ history, the above two different definitions of serializability coincide. More precisely,

  A guess: With $\textrm{SI}$, a history $H$ is 1-$\textrm{SR}$ in [Bernstein et al@TODS'1983] iff it is $\textrm{SR}$ in [Berenson et al@MSR-TR'1995].

References:

([Bernstein et al@TODS'1983]) Multiversion Concurrency Control — Theory and Algorithms

([Cahill et al@SIGMOD'08]) Serializable Isolation for Snapshot Databases


On the complexity of Bandwidth Minimization The graph bandwidth problem is defined as follows. Given a graph $G=(V,E)$, a layout $f$ of $G$ is a one-to-one mapping of the vertices of $G$ onto the integers $\{1, \ldots, |V|\}$. The bandwidth of $f$ is defined as

$bw(f) = \max \{|f(u) - f(v)| \mid \{u,v\} \in E\}$.

The bandwidth of $G$, denoted $bw(G)$, is defined as the minimum bandwidth of a layout, the minimum being taken over all possible layouts.

The decision question is: given a graph $G$ and an integer $k$, is $bw(G) \le k$?

This problem is known to be NP-complete even for trees of maximum degree three [Complexity Results for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, No.3, 1978]. The authors show that one can test whether a graph has bandwidth at most two in polynomial time. The case $bw \le 3$ was open.

Is the complexity of the case $bw \le 3$ known? What do we know about the complexity of the problem when $k$ is not part of the input but a fixed constant at least $4$?

References would be nice.

The bandwidth problem is $W[t]$-hard for all $t$. It was shown by Bodlaender et al. in "Beyond NP-completeness for problems of bounded width." See the paper.

On the other hand, it is also known that for any $k$, whether a given graph has bandwidth at most $k$ can be decided in $O(f(k)n^{k+1})$ time. This implies that the bandwidth problem is in $XP$. See the another paper by Saxe.


Are regular languages closed under addition? Specifically what I mean by addition is, we define $\Sigma_i$ to be the alphabet $\{0, 1, 2, ..., i\}$. Given regular languages $A$ and $B$ under some alphabet $\Sigma_i$, look at $A\times B$.

For every ordered pair $(a, b) \in A\times B$, define the "sum" of this ordered pair as $a+b$, where $a$ and $b$ are numbers in base i. Leading 0's are ignored, so $0^*$is in front of every accepted string. This implies $\epsilon$ is defined as 0.

The language $A+B$ is the set of strings representing all such possible sums.

So far, I know:

This is true in unary ($\Sigma_1$).
This is true for any finite regular languages $A$ and $B$, because any finite language is regular and $A+B$ is finite.
The language $C_n$ = $\{$s $|$ s is a multiple of n in base b$\}$ under $\Sigma_b$ is regular for any $b >= 1$. This means any languages of the form $C_n$ can also be added, as $C_i+C_j=C_{i + j}$, which is also regular. However there are languages like $D$=$\{$s $|$ s starts and ends with a 1} which don't fit this criteria, so this doesn't describe all regular languages.

Yes, they are.

First, consider the alphabet $\Sigma_i^3$ whose symbols are triples of digits (stacked one above each other into a pile of three digits). Over this alphabet, we can define a regular language $A'$ where the string formed by the topmost of the three digits belongs to $A$, a regular language $B'$ where the string formed by middle of the three digits belongs to $B$, and a regular language $C$ where the top two strings sum to the bottom one. $A'$ and $B'$ just use modified automata for $A$ and $B$, while $C$ uses the fact that you can do addition by scanning right-to-left while keeping only a single digit of carry as state.

Then $A'\cap B'\cap C$ is (by closure under intersection) a regular language that recognizes stacks of three strings, one in $A$, one in $B$, and the third in the sum. The homomorphism that strips off the top two digits from a stack leaving only the bottom one takes this to the language you want, and the result follows by closure under homomorphism.


Entropy of a byte in a compression algorithm? I have a (fixed, long) string of bytes that I want to compress, $C$. I use a typical (good) lossless compression algorithm on it, to generate a compressed string of bytes, $C^*$. Then I define a random variable $X$ which samples a bit uniformly at random from $C^*$. Should I expect Prob[X = 0] to be close to 1/2?

A good compression algorithm is defined as one that achieves good information-theoretic bounds, such as Shannon coding.
A counter-example would be a compression algorithm that achieves, on average, a non-equal proportion of bits as the length of $C$ goes to infinity, where the contents of $C$ itself are chosen uniformly at random among all strings of that length.
This is to say the following: Let $S(n)$ be a string of length $n$ chosen uniformly at random. Let $C(s)$ be the result of the compression algorithm with input $s$. Let $X(s)$ denote the proportion of '0's in the string $s$. Then the question is whether $X(C(S(n)))$ necessarily converges to $1/2$ as $n$ goes to infinity.

I define a random variable X which samples a bit uniformly at random from C∗. Should I expect Prob[X = 0] to be close to 1/2?

Roughly, yes. The compression algorithm is lossless (bijective), so the entropy of the input is the same as the entropy of the output. Under your hypothetical, the output's length is asymptotically larger than its entropy, so asmyptotically larger than the input's entropy. So the compression algorithm does not reach the Shannon entropy bound.

To see one somewhat-formal argument for why the output's length is asymptotically larger than its entropy, suppose for simplicity the length is $n$ and formalize your hypothesis by, e.g. supposing the fraction of ones is always at least $p$, with $p > 0.5$. Using a Chernoff bound, the total number of such strings is at most $q 2^n$ where $q = 2^{-cn}$  for some constant $c > 0$, and so the maximum entropy of the output is at most the log of this number, which is $n(1-c)$, which is significantly smaller than $n$.

OK, this isn't totally formal, but I hope it's a useful answer.


How does Theoretical Computer Science relate to security? When I think of software that is insecure I think that it is "too useful" and can be abused by an attacker.  So in a sense securing software is the process of making software less useful.  In Theoretical Computer Science you aren't working with the real world.  So are there any security concerns when working with pure theory?  Or the other side of the coin, does Theoretical Computer Science affect the real world of people getting hacked?  If so,  what security topics are considered Theoretical?

Your intuition that "insecurity" is due to software that is "too useful" is correct, in a sense. There is a large and growing theoretical literature on "differential privacy" that formalizes your intuition. See for example, here: research.microsoft.com/en-us/projects/databaseprivacy/dwork.pdf

Here, we think of the input to an algorithm as being a "database", and the algorithm is "insecure" if it reveals too much information about any one person's data in the database. An algorithm is $\epsilon$-differentially private if the algorithm's output does not depend much on any one input: specifically, changing a single entry in the input database should only change the probability of any output of the algorithm by at most an $e^\epsilon$ factor.

Of course, making an algorithm private makes it less useful: a $0$-differentially private algorithm produces outputs that aren't even a function of the inputs at all! But it turns out you can try and carefully balance the tradeoff between privacy and utility, and can get very private algorithms that nevertheless are very non-trivially useful.


"Combining" two mealy machines How could you combine two mealy machines, the first one $M_1$  has as input $\sum_{1}^*$ and as output $\sum_{2}^*$,
the second machine $M_2$ uses the output $\sum_{2}^*$ as the input and outputs $\sum_{3}^*$.
So what is the resulting $M_2◦M_1(w)$ machine, where $w$ is a word from $\sum_{1}^*$?

A Mealy machine consists of a state set $S$, an initial state $s \in S$, and a transition function $A \times S \to B \times S$ (which takes as input a letter from the alphabet $A$ and a current state $S$, and produces an output letter drawn from $B$ and an updated state from $S$).

We can write this as a type declaration in Ocaml like so:

type ('a,'b) mealy = M : 's * ('a * 's -> 'b * 's) -> ('a,'b) mealy

Then the compose operation in looks like this:

let compose : type a b c. (a,b) mealy -> (b,c) mealy -> (a,c) mealy =
  fun (M(s, f)) (M(t, g)) ->
    let state = (s,t) in
    let trans (a, (s, t)) =
      let (b, s') = f(a, s) in
      let (c, t') = g(b, t) in
      (c, (s',t'))
    in
    M(state, trans)

So the state of the composite machine are the products of the two state sets, and the new initial state is the pairing of the two initial states, and the composite transition function feeds the input to the first transition function and uses its output as the input to the second transition function.


A reading list on experimental algorithmics As in, the area of the papers in the ACM Journal on Experimental Algorithmic JEA.

Which were the foundational works? What are the main results? How are they characterized? Any interesting connections to other areas of computer science?

Probably the single most important guide to experimental algorithmic is David Johnson's article on how to do it, which also has lots of references.
http://www2.research.att.com/~dsj/papers/experguide.pdf


Programming language supporting infinitary rewriting of regular term graphs? Do any practical programming languages support term graph rewriting of infinite but regular terms? For example the toy language CoCaml [1] supports computations on infinite regular streams. Coq supports coinduction [2] but not infinitary rewriting, as far as I can tell. By "infinite regular term graph", I mean those inhabitants of coalgebraic datatypes that can be defined in terms of finitely many equations.

[1] Jean-Baptiste Jeannin, Dexter Kozen, Alexandra Silva (2017)
CoCaml: Functional Programming with Regular Coinductive Types
[2] Yves Bertot, Ekaterina Komendantskaya (2008)
Inductive and Coinductive Components of Corecursive Functions in Coq

Yes, Prolog.

The specification of unification in the Prolog standard omits the occurs check, and as a result variables range over rational trees. Additionally,  many Prolog (such as SWI Prolog and YAP) implementations support tabling, which permits defining and using coinductively defined predicates.


Convexity and efficient algorithms. [Edit 21 July 2011: I edited the question to ask for more examples]

This question is asking for documented discussion of or more examples of a heuristic observation.

Some mathematical problems that admit efficient algorithms appear to be convex in nature. I'm thinking of linear and semi-definite programs and various combinatorial problems that reduce to these.

First, are there other families of problems that admit efficient algorithms for the convex/conjunctive case? (I would be particularly grateful for examples of  decision procedures for logical theories) Second, I would appreciate pointers to articles or sections of articles that discuss an opinion such as "lurking under a lot of efficient algorithms is a convex structure."

[Edit, 21 July 2011: Added the following.]

I would like to add some clarifications. I'm sorry I didn't include them earlier. I am interested in logical decision problems. It appears to me that efficient decision procedures exist for the conjunctive fragment of several logical problems. Here are two examples.

Efficient solvers for quantifier-free first order theories (such as SMT solvers for equality, equality with uninterpreted functions, difference arithmetic, etc.) typically have an efficient solver for the conjunctive fragment and use various techniques to cope with disjunction and negation. In static analysis of programs, the commonly used (and efficient) abstractions are based on integer intervals, affine equalities, octagons or polyhedra. In predicate-based abstraction and program verification, there is something called the Cartesian abstraction, which is intuitively about having conjunctions of predicates rather than arbitrary Boolean combinations. All these cases appear to me to be about gaining efficiency by exploiting the conjunctive fragment of the problem.

The conjunctive fragment of the first order theory of linear, real arithmetic can express convex polyhedra. This is why I originally asked about convex programming.

I am interested to know of other problems or examples where efficient solutions (in the theoretical or practical sense) are based on a convex or conjunctive sub-problem. If there is another general condition (Suresh mentioned sub-modularity) please mention it and problems whose solutions exploit that condition.

Regarding Question 1.

The examples you gave, linear programs and SDPs (both of which are linear programs over convex cones), can be generalized to convex programs: minimization of a convex function over a convex feasible set.  Since you are looking for 'other families of problems' that are efficient thanks to the presence of convexity, the natural thing to drop is the convex function part, and just look at convex sets.  This is the realm of convex geometry, and here there are lots of algorithms.

One of the standard favorites is:

Martin Dyer,  Alan Frieze,  Ravi Kannan. A Random Polynomial Time Algorithm For Approximating The Volume Of Convex Bodies.

The difficulty here is that the dimension is (at it should be) a part of the input; on the other hand, a naive algorithm samples points on the grid, which sticks the dimension in the exponent of the running time.  The reason why convexity helps is intuitive: convexity gives separation results, things like Farkas's lemma which say that a point is either in a closed convex cone, or you can separate them with a hyperplane.  The relevance here is say that you know some point is in the convex body, whereas some constellation of points around it is not in the body: from here you can lop off a huge piece of the input and never bother sampling from it.  Perhaps I should clarify that the above paper does the estimation by producing a nice sampling algorithm within the body (both of which are useful).  Last I checked, there is still no deterministic analog to this; I just googled to see if the status has changed (seems not), and was fed these notes that have a few references which may interest you: http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf .  I never took this class and only looked briefly, so my apologies if there are some problems, but the references there at least seem to have value to you.

For more examples of algorithms exploiting convex geometry, one place to look is the 'Bibliography and Remarks' subsections concluding each section (of each chapter!) of Jiri Matousek's book "Lectures on Discrete Geometry".

Another thing that gets cited a lot, and which seems to have topics for you (but I've never looked beyond the table of contents myself; Matousek on the other hand is .. in my other hand), is "Geometric algorithms and combinatorial optimization" by Grotschel, Lovasz, and Schrijver. (Yes, that Lovasz.)

I think these references have a lot for you so I'll move onto the next question.

Regarding Question 2.

While it is definitely true that convexity is powerful, I have not seen a comment like the one you seek, and I think people are very careful to communicate such a sentiment.

I have an anecdote on this.  One way people 'inject' convexity into problems is to simply.. approximate/model them with something convex.  (For example: replacing rank constraints with norms on the matrix, replacing integers (nonconvex and not even connected) with convex sets of reals.)  A go-to text for this stuff is Boyd & Vandenberghe's "Convex Optimization".  But once I was watching Boyd's videos, and someone gave him the "is convex = efficient" question, and he immediately said SVD.  Note that SVD can be written as a rank constrained minimization problem.  Anyway, my point is that even Boyd is very quick to correct a comment like this.

That said, I have a desire to share two places where I was personally surprised by convex structures (experts can roll their eyes and doze here).  The first are so called 'sum of squares' problems, which are minimization problems over nonconvex polynomials.  Thanks to the interpolation properties of polynomials, you can rewrite these as SDPs.  There are some beautiful course notes on this topic by Pablo Parrilo; you can find that and more info on his web page and some other info in this MO post by Noah Stein:
https://mathoverflow.net/questions/32533/is-all-non-convex-optimization-heuristic/32634#32634 .

Another beautiful place is in exponential families.  Now, this is all "obvious" once you realize these are solutions to max entropy (a convex optimization problem), but it's amazing how much convex structure informs the behavior of exponential families (a reference I like here is Wainwright and Jordan's book on graphical models).  This in turn gives one justification for some of the things people do with this sort of modeling.


What is the axiomatic (set theory) context of the P vs NP and NP=EXPTIME conjectures? When the conjecture $\mathbf{P} = \mathbf{NP}$ or $\mathbf{P} \neq \mathbf{NP}$ is set (e.g. by the Clay Mathematical Institute by S. Cook, see here) what mathematical axiomatic system is assumed?

In order to prove or disprove such statements, you need to assume some axioms. Which ones? Only the Peano (2nd order formal language) arithmetic? The Zermelo–Fraenkel set theory with the axiom of choice? Smaller axiomatic set theories (e.g. Gödel's constructible sets, where the continuum hypothesis holds too, see here)?

Obviously, it should be an axiomatic theory that accepts the countable infinite. But which in particular? Is there any published result that would prove them consistent in a particular axiomatic set theory? (In other words, defining a model in which it is true, but not claiming to be true in all models).

It's not specified. When there is a serious enough candidate paper purporting to resolve P ≟ NP, a Special Advisory Committee will be formed to decide whether (and to whom) to award the prize. I presume that the Special Advisory Committee will decide whether your system of axioms is acceptable. If you assume Z-F with choice, I guarantee you they will take it. If you assume P ≠ NP as an axiom, I guarantee you they won't.


When a process spawns another process My background is in complexity theory/logic (where there is just one process most of the time), and in distributed computing (where there are $n$ processes, and one or more might fail over time).  However, I now want to be able to say something about a process spawning/creating/spinning off another process.  Is there rigor in parallel computing, operating systems, etc., that accounts for this?
Motivation:
I am trying to construct models that abstract out certain features of molecular interactions.  I'd like to say that the set of chemical reactions $S$ is an independent process, and that at a certain time step $t$, it spawns another independent process $S'$.  Intuitively, these things feel like independent processes, because they have no contact with each other after time $t$ - or very little contact, only interchanging "messages."
More formally:

(1) Are there pre-existing CS definitions that capture the notion of one process spawning another independent process?  I am especially interested in being able to demarcate where $S$ stops and $S'$ starts, and why that is "reasonable" to do.
(2) If there is more than one answer to (1), what do you consider the pros and cons to the various definitions?

(Note: I have no idea how to tag this appropriately, and plan to re-tag depending on the answers.)

Of course there are many systems for modelling processes. These fall under the category of process algebras.  The key examples are $\pi$-calculus, CCS, ACP and CSP.

Process calculi have basic mechanisms for specifying process behaviour including: sending and receiving of messages (synchronously or asynchronously), creating parallel processes, nondeterministic choice between behaviours, and the replication of processes. Although the calculi are small in terms of the number of constructs, they are very expressive and a vast amount of research has gone into studying their properties.

The $\pi$-calculus differs from the others in that it allows, in essence, processes to be passed as first class values. It actually allows channel names to be passed around as first class values, enabling changes in the dynamic topology. This is probably the calculus you want because it offers the greatest dynamicity.

CSP (communicating sequential processes) is a little odd, when seen from a perspective of modelling molecules. It does have plenty of backing theory and tool support. (Invented by C. A. R. Hoare.)

CCS and ACP have less dynamicity than the $\pi$-calculus, but they are much easier to analyse and simulate. A solid toolset called $\mu$CRL (and $\mu$CRL2) are available for ACP. Similar tools are sure to exist for CCS.

I'd start examining the related work (see below) and then find which of the modelling formalisms suit what you are looking for.

There has in fact been quite a lot of work modelling chemical reactions and biological processes using process algebra.
Probably the best place to look  is Luca Cardelli's publication list. His whole line of research on BioComputing has probably 30 papers on the topic. This talk gives an overview of much of his work. This one is slightly more formal, though reading the papers is really the only way to see the details.

One approach that directly models chemical processes is CHAM (the chemical abstract machine). The key ingredient here is a solution of molecules and membranes. There are heating and cooling rules for rearranging the molecules and for removing junk. These rules are reversible. Finally there reaction rules which model reactions. In contrast to process algebras, CHAM models are not so worried about the syntax of processes, so you can invent your own representation of the molecules.

Rewrite logic as realised in the toolset Maude offers another more or less direct approach to specifying such reactions. One need only specify the rewrite rules, the handing of the "soup" is automatic. The toolset would enable the simulation and analysis of (smallish) chemical reactions. A probabilistic variant of Maude also exists.


Representations of Planar Graphs in Coq I would like to formalize some simple properties of planar graphs in the Coq proof assistant.

1) How are planar graphs formalized in the Coq proof assistant? Is there a "standard" definition that is widely used? For instance, a definition that is already in some library for the manipulation of planar graphs?

2) Even better: Is there any inductive definition that is widely used?

The obvious resource for planar graphs in Coq would be the (modern port of) the four color theorem in Coq/SSReflect, by Georges Gonthier (and others) which obviously does need to define planar graphs.

It's not immediately obvious to me how planar graphs are characterized, though the relevant file is here and it seems to involve a combination of Euler characteristic and Jordan paths.

One could conceivably use the forbidden minor characterization, and use the modern library by Doczkal and Pous though I have a hard time imagining that it's easy to prove anything using that characterization. It'd be more interesting to prove that it is a characterization. This again uses SSReflect. See also the paper.

Finally, using any of the existing (mature) libraries for graphs, one might want to use the definition used in the flyspec project, described here, which defines (in section 2.3) planar graphs in terms of faces, which need to be orientable, connected to other faces with inverse orientation, with a cycle around each vertex, and obeying the Euler theorem. The paper is very nice, and describes the Gonthier approach as well in the subsequent sections.


Finding the number of independent rows of a matrix There is a $n\times n$ matrix $A$, and we are asked to find the number $N(A)$ of independent rows in it, i.e. rows that are not a linear combination of the other rows. Clearly, if $rank(A)=n$, then $N(A)=n$, but for $rank(A)=n-1$  $N(A)$ can be anywhere between $0$ and $n-1$.

A straightforward way to check if a row is independent is to check if removing it from $A$ lowers the rank of $A$. Assuming calculating rank requires $O(n^\alpha)$ operations, calculating $N(A)$ this way would require $O(n^{\alpha+1})$. Are there more efficient ways to find $N(A)$?

(what follows solves the question for columns, easily adapted to rows either by transposing or by doing a column echelon instead of a row one)

You can do the following: put your matrix in reduced echelon form by the Gauss-Jordan elimination method. Note that this preserves $N(A)$.

Let's say we work on a 5x5 matrix and that we get:

\begin{bmatrix}
1 & a_1 & 0  & 0 & b_1 \\
0 & 0 & 1 & 0 & b_2 \\
0 & 0 & 0 & 1 & b_3 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}

From this form you can read $N(A)$ immediately: the only columns that can be independent are the ones holding the $1$s (the pivots of the elimination). Now it is obvious that they actually are independent iff. the coefficients on the right of the $1$ they hold are all $0$.

(in our example: the 1st column is independent iff. $a_1=0$ and $b_1=0$; the 3rd column is independent iff. $b_2=0$;
the 4th column is independent iff. $b_3=0$)

This way you get $N(A)$ in $O(n^e)$ where $n^e$ is the complexity of computing the echelon form. (the naive algorithm gives $e=3$).


Do there exist groups with word problems in arbitrary P-degrees? It has been known for a long time that, given any r.e. Turing degree, there is a finitely presented group whose word problem is in that degree.  My question is whether the same thing is true for arbitrary polynomial time Turing degrees.  Specifically, given a decidable set, $A$, does there exist a finitely presented group, with word problem, $W$, such that $W\leq_T^P A$ and $A\leq_T^P W$?  I would also be willing to relax finitely presented to recursively presented.

I suspect that the answer is yes, and I have heard others say they read this somewhere, but I haven't been able to chase down a reference.

I think this is not known. (I apologize - I think I was also one of the people that said I had remembered reading this somewhere.) For example, I believe that Sapir-Birget-Rips, Annals of Math 2002 were the first to show the existence of a group with $\mathsf{NP}$-complete word problem (which would be a trivial consequence of the result asked for in this question). Their Corollary 1.1 states:

  There exists a finitely presented group with NP-complete word problem. Moreover, for every language $L \subseteq A^*$ for some finite alphabet $A$ there exists a finitely presented group $G$ such that the nondeterministic time complexity of $G$ is polynomially equivalent to the nondeterministic time complexity of $L$.

While the second half of this corollary is kind of in a similar spirit to this question, it is a far cry from proving that every $\leq_T^p$-degree contains a word problem.


Relationship between Turing Machine and Lambda calculus? Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?

The lambda calculus is older than Turing's machine model, apparently dating from the period 1928-1929 (Seldin 2006), and was invented to encapsulate the notion of a schematic function that Church needed for a foundational logic he devised.  It was not invented to capture the general notion of computable function, and indeed a weaker typed version would have served his purposes better.

It seems to be incidental to the purpose of that the calculus Church invented turned out to be Turing complete, although later Church used the lambda calculus as his foundation for what he called the effectively computable functions (1936), which Turing appealed to in his paper.

Church's simple theory of types (1940) provides a more moderate, typed theory of functions that suffices to express the syntax of higher-order logic but does not express all recursive functions.  This theory can be seen as being more in tune with Church's original motivation.

References

Church (1936).  An unsolvable problem in elementary number theory.  American Journal of Mathematics 58:345—363.
Church (1940).  A formulation of the simple theory of types.  Journal of Symbolic Logic 5(2):56—68.
Seldin (2006). The logic of Curry and Church.  In Handbook of the History of Logic, vol.5: Logic from Russell to Church, p. 819—874.  North-Holland: Amsterdam.

Note This answer is substantially revised due to objections by Kaveh and Sasho.  I recommend the Wikipedia timeline that Kaveh suggested, History of the Church–Turing thesis, which has some choice quotes from seminal articles.


Is refuting candidate deciders of the halting problem computable? No Turing machine can decide whether any given Turing machine will halt for a given input. That is:

If you give me a Turing machine which you claim can take a Turing machine and an input for that machine and will tell me whether the machine will halt,
There is some counterexample TM/input pair I can provide to that machine for which it will fail.

This is the undecidability of the halting problem. Old news.

My question is: Can such a counterexample be computed for any candidate decider of the halting problem?

That is, is there a Turing machine which can take as input some Turing machine and compute a TM/input pair for which the given Turing machine fails to decide the halting problem?

(Incidentally, I'm slightly over my head here, so I may be asking my question wrong, or asking a wrong question. Thoughts and pointers are welcome.)

The usual proof that the halting problem is undecidable already gives you exactly such an algorithm. Given an algorithm $A$, we construct an algorithm $B$ that on input $x$ computes $A$ on program $x$ and input $x$, and then enters an infinite loop iff $A$ answered "halts". Now consider giving $B$ itself as an input. If $A(B,B)=\text{"halts"}$ then $B$ doesn't halt on $B$, so $A$ is wrong. Same if $A(B,B)=\text{"doesn't halt"}$. So $\langle B,B\rangle$ is an example input on which $A$ is wrong.


Local Graph Isomorphism to construct Global Graph Isomorphism Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism?

For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq H$.

Now assume there exists an algorithm that splits graph $G$  in to  Subgraph  $G_1, G_2$(in $G$, $G_1$ and $G_2$ are connected through a  set of edges, say, $R_1$) and finds Isomorphism to corresponding graph $H_1 , H_2$(Local Isomorphism), then merge those Isomorphism to check whether $G\simeq H$ (Global isomorphism).

Does there exist such algorithm in Graph Isomorphism Literature ?

EDIT:

I apologize for a vague description, I should be more specific, but it is really hard to specify at the moment. For the time being, note that I do not mean a splitting based on vertex classification entirely or something like that.  An algorithm that is based on  $K$  Dimensional  Weisfeiler-lehman(depth $K$  neighborhoods) entirely,  is not what I meant, that is for sure**.  if $K=1$, then it can not handle  regular graph. You can "construct" graph that makes $K$  Dimensional  Weisfeiler-lehman ineffective, for example Cai-Furer-Immerman pair. Certainly  I do not mean that.Note that NAUTY  uses  1 Dimensional  Weisfeiler-Lehman method.

This question is the closest I got to mine, but it does not answer  my query.

This is actually how many graph isomorphism algorithms work (often in combination with Weisfeiler-Lehman). For example, bounded color class isomorphism (Luks 1983) works by first finding isomorphisms within each color class, then combining those using the edges between color classes. Zemlyachenko's trick could then be used to individualize $\tilde{O}(\sqrt{n})$ vertices, so that the resulting graph had bounded color classes (which led to the previous-best algorithm for GI).

Babai's recent algorithm does another kind of divide-and-conquer that is sort of along the lines you mention. It either finds a partition of the graph into small parts (where "small" here means some constant fraction smaller than the original graph; the result is that such recursion can only happen $O(\log n)$ times) or finds a large embedded Johnson scheme. In the latter case, it handles the Johnson scheme by a different recursive technique, but then handles the vertices that aren't in the Johnson scheme essentially along the lines you suggest. (Indeed, if you look at the table of contents of Babai's paper you will see there is quite a lot of talk about "local to global" principles, though it's not really the same "local to global" you're talking about here.)


NP-complete problems with optimal approximation in poly-time I'm looking for examples of hard optimization problems, for which we have an optimal approximation (not that this is not the same as $PTAS$, as we require a completely tight approximation, and not $1+\epsilon$-multiplicative approximation), in a sense defined as follows:

Formally, let $L\subseteq\Sigma^*\times \mathbb N$ be the decision version of some minimization (or maximization, flipping the definitions) problem, i.e.
$$\forall n\leq m:(w,n)\in L\implies (w,m)\in L$$

Which examples of such known languages $L$ is $NP$-hard, but if we are allowed of a minimal relaxation, it is poly time solvable.

By minimal relaxation I mean that there exists a TM such that given an input $(w,n)$:

The machine accepts if $(w,n+1)\in L$.
The machine rejects if $(w,n-1)\not \in L$.
The machine may act arbitrarily on other cases.

An example for such problem is the Degree-constrained spanning tree, where the problem is finding an MST with minimal maximum vertex degree.

  Which other languages are NP-hard but subject to optimal approximation in poly time?

One example is the chromatic index (edge-coloring number) of undirected graphs. By Vizing's theorem, the chromatic index either equals the max-degree $\Delta$ or equals $\Delta+1$.

Vizing's proof gives a polynomial time (inductive) procedure for finding a coloring with $\Delta+1$ colors.
Holyer has proved that deciding whether the chromatic index equals $\Delta$ is NP-complete.


Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$ For a Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$, the influence of the $i$th variable is defined as
$$
\operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})]
$$
where $x^{\oplus i}$ is the string obtained by flipping the $i$th bit of $x$. The minimum influence of $f$ is then $$\operatorname{MinInf}[f] \stackrel{\rm def}{=} \min_{i\in[n]}\operatorname{Inf}_i[f].$$

Given a parameter $p\in[0,1]$, we choose a $p$-random function $f$ by choosing its value on each of the $2^n$ inputs independently at random to be $1$ with probability $p$, and $-1$ with probability $1-p$. Then, it is easy to see that, for every $i\in[n]$
$$
\mathbb{E}_{f}[\operatorname{Inf}_i[f]] = 2p(1-p)
$$
and a fortiori
$$
I_n(p) \stackrel{\rm def}{=}\mathbb{E}_{f}[\operatorname{MinInf}[f]] \leq 2p(1-p).
$$

My question is:

  Is there an asymptotically (with regard to $n$) tight expression for $I_n(p)$? Even for $p=\frac{1}{2}$, can we get such an expression?

  Specifically, I do care about the low order terms, i.e. I'd be interested in an asymptotic equivalent for the quantity $2p(1-p)-I_n(p)$.

(The next question, but which is subordinate to the first, is whether one can also get good concentration bounds around this expectation.)

By Chernoff bounds one can  also show that each $\operatorname{Inf}_i[f]$ has good concentration, so that by a union bound we get (if I did not mess up too badly)
$$
 \frac{1}{2} - O\left(\sqrt{\frac{n}{2^n}}\right) \leq I_n\left(\frac{1}{2}\right) \leq \frac{1}{2}
$$
but this is most likely loose on the lower bound (due to the union bound) and definitely on the upper bound. (I am in particular looking for an upper bound strictly less than the trivial $\frac{1}{2}$).

Note that one of the issues in doing that, besides taking the minimum of $n$ identically distributed random variables (the influences), is that these random variables are not independent... although I do expect their correlation to decay "pretty fast" with $n$.

(For what it's worth, I have computed explicitly the first few $I_n(1/2)$'s up to $n=4$, and have run simulations to estimate the following ones, up to $n=20$ or so. Not sure how helpful this could be, but I can include that once I am back to my office.)

Here's a step in the right direction...

I'll argue that for $p=1/2$,
you have $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$.

(This is not quite as strong as it should be.
Maybe someone can strengthen the argument to show $\Omega(\sqrt{n/2^n})$.)
Here's a proof sketch.

It suffices to show $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$. We do that.

Note that if $\text{Inf}_1[f]$ and $\text{Inf}_2[f]$ were completely independent, we'd be done because the expectation of the minimum of the two independent sums is $1/2-\Omega(\sqrt{1/2^n})$.  First, we'll argue carefully that the two sums are almost independent.

Consider the universe of points $X=\{-1,1\}^n$.  Call $x$ and $x'$ in $X$ $i$-neighbors if they differ in just the $i$th coordinate.  Say the two neighbors contribute (to $\text{Inf}_i[f]$) if $f(x) \ne f(x')$.  (So $\text{Inf}_i[f]$ is the number of contributing $i$-neighbors, divided by $2^{n-1}$.) Note that, if $x$ and $x'$ are $i$-neighbors, and $y$ and $y'$ are $i$-neighbors, then either $\{x,x'\}=\{y,y'\}$ or $\{x,x'\}\cap\{y,y'\}=\emptyset$.  Hence, the number of contributing $i$-neighbors is the sum of $2^{n-1}$ independent random variables, each with expectation $1/2$.

Partition the universe $X$ into $2^{n-2}$ groups of size four, where $x$ and $x'$ are in the same group iff $x$ and $x'$ agree on all but their first two coordinates. Then for each pair $(x,x')$ of 1-neighbors, and each pair $(x,x')$ of 2-neighbors, $x$ and $x'$ are in the same group.  For a given group $g$ and $i\in\{1,2\}$, let r.v. $c^g_i$ be the number of contributing $i$-neighbors in $g$. Then, for example, the number of contributing 1-neighbors overall is $\sum_g c^g_1$, a sum of $2^{n-2}$ independent random variables, each in $\{0,1,2\}$.

Note that $c^g_1$ and $c^{g'}_2$ are independent if $g\ne g'$. By a case analysis, if $g=g'$, the joint distribution of $c^g_1$ and $c^g_2$ is
$$\begin{array}{c|ccc}
 & 0 & 1 & 2 \\ \hline
0 & 1/8 & 0 & 1/8 \\
1 & 0 & 1/2 & 0 \\
2 & 1/8 & 0 & 1/8 \\
\end{array}$$

Let r.v. $N=\{ g : c^g_1=c^g_2=1\}$ denote the set of neutral groups. (They contribute exactly their expected amount to the 1-influence and the 2-influence.) The number of contributing 1-neighbors is then
$$|N| + \sum_{g\in \overline{N}} c^g_1.$$

Conditioned on $N$, for each $g\in \overline N$ r.v.'s $c^g_1$ and $c^g_2$ are independent (by inspection of their joint distribution above), so (conditioned on $N$) all r.v.'s $\{c^g_i : i\in\{1,2\}, g\in\overline N\}$ are i.i.d. uniformly over $\{0,2\}$ so,
$$\textstyle E\Big[|\overline N|- \min\big(\sum_{g\in \overline N} c^g_1, \sum_{g\in \overline N} c^g_2\big) ~\Big|~ N\Big] \ge \Theta(\sqrt{|\overline N|}).$$

Finally, note that each group is neutral with probability 1/2, so $\Pr[|\overline N| \le 2^{n-2}/3]$ is extremely small, say $\exp(-\Omega(2^n))$ (and even in that case the left-hand-side above is at least $-2^n$). From this the claimed lower bound follows...


Worst-case asymptotic-complexity of the Set-cover problem? What's the worst-case asymptotic-complexity of the Set-cover problem in Big O notation?

I've been developing some novel techniques to try and solve this problem but am having trouble finding the theoretical limits I need to surpass.

Thanks for all information

I don't see how you can say that SCP or any other problem has "worst-case asymptotic complexity", but surely an algorithm solving it can have. However, the problem is NP-complete, and the optimization version is NP-hard.

For an exact algorithm, this is clearly a "theoretical limit". For an exact algorithm, see for example E. Balas and M. C. Carrera, A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering, Operations Research 44, 875-890, 1996. According to A. Caprara et al., Algorithms for the Set Covering Problem, 2000, this algorithm of Balas and Carrera is the fastest known exact algorithm. The result is a bit old already, so I'm not sure if there are newer and faster exact algorithms.

There is a simple greedy polynomial time approximation algorithm with an approximation ratio of $H_n$, where $H_n$ is the $n$th harmonic number. Under reasonable assumptions, this is the best one can do, since if there exists a $c \ln n$-approximation algorithm for the (unweighted) set cover problem for some constant $c < 1$, then there is an $O(n^{O(\log \log n)})$-time deterministic algorithm for each NP-complete problem. I think the Wikipedia page gives the essential references.


Rademacher complexity for piecewise-linear convex function Consider a function family $$\ell(x)=\max_{1\leq k\leq K} a_k^\top x + b_k,$$ where $a_k,b_k \in \mathbb{R}^d$ are bounded in the sense of some norm and $K\geq 2$. What is the best upper bound on the capacity (e.g., Rademacher complexity, etc) of such a family, in terms of dependence on dimension $d$, number of pieces $K$ and sample size $n$?

Since we're talking about real-valued functions, rather than VC-dimension, you probably want the fat-shattering one. The $\gamma$-fat-shattering of linear functions with $\ell_2$ norm bounded by $B$ is of order $(B/\gamma)^2$. For a $k$-fold maximum of such functions, the bound grows as $O((B/\gamma)^2k\log k)$, as shown here:
https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf

This translates immediately into a Rademacher bound, given therein.

The $\log(k)$ factor cannot be removed in this case, as recently shown in
https://arxiv.org/abs/1807.07924

Edit: I had originally neglected to mention that the fat-shattering bound of $(B/\gamma)^2$ implicitly assumes that the instance space is confined to the Euclidean ($\ell_2$) unit ball. More generally, if the linear functions have $\ell_p$ norm at most $B$ and the data is confined to an $\ell_q$ ball of radius at most $R$, the bound becomes $BR/\gamma^2$,
where $1/p+1/q=1$, $p,q\ge1$.
This readily follows from the classic Rademacher analysis of "fat" hyperplanes: in the step where Cauchy-Schwarz is invoked, invoke instead Hölder.


Converting Kuroda normal form rules to the Penttonen normal form Let us say we have some abstract context-sensitive grammar in the Kuroda normal form, which is where all production rules are of the form:

$AB\rightarrow CD$ or

$A\rightarrow BC$ or

$A\rightarrow B$ or

$A\rightarrow a$

There is also the one-sided normal form or the Penttonen normal form for context-sensitive grammars (described in the same wikipedia article), which is where all rules are of the form:

$AB\rightarrow AD$ or

$A\rightarrow BC$ or

$A\rightarrow a$

Question: how to generally convert a rule of the Kuroda normal form $AB\rightarrow CD$ into bunch of rules in the Pentonnen normal form?
In particular I am stuck with understanding how to deal with an intermediate rule of the form $AZ\rightarrow WZ$.

You can find the proof in Penttonen's original research article:

Martti Penttonen, One-Sided and Two-Sided Context in Formal Grammars. Information and Control 25, pp. 371-392 (1974). https://doi.org/10.1016/S0019-9958(74)91049-3


Maximizing a submodular function of two sets with different size constraints I have two totally distinct domains (apples and oranges) and I have a function $f$ that takes a set of objects from the first domain and a set of objects from the second domain and returns a real number.

$f(S,T)$ has the following interesting properties:

fixing $T$, it is non-negative, submodular and monotone w.r.t. $S$;
fixing $S$, it is non-negative, submodular and monotone w.r.t. $T$.

I want to maximize $f(S,T)$ with two cardinality constraints $|S| = s$ and $|T| = t$.

How can I do that?
If I consider the product space, the function is monotone and submodular.
Thus I can apply the standard greedy algorithm.
Dealing with the two different size constraints, might not be an issue: adding $(a, x)$ and $(a, y)$ in sequence allows me to increase $|T|$ without increasing $|S|$.

The question is whether the $1-1/e$ approximation still holds.

The problem is likely to be hard to approximate. The densest bipartite subgraph problem can be cast as a special case. Given a bipartite graph $(V,E)$ where $V=V_1 \uplus V_2$ define $f(S,T)$ for $S \subseteq V_1, T \subseteq V_2$ to be the number of edges between $S$ and $T$. Then $f$ satisfies the desired property. In fact $f(S,\cdot)$ is modular and so is $f(\cdot,T)$. If $a=b=k$ then we are asking for a $k$ by $k$ densest bipartite subgraph problem. Only a polynomial ratio approximation is known, and under some assumptions this problem can be shown to be hard.


Popular Journals for Theoretical CS Are there some popular journals in the field of theoretical CS that serve the kind of purpose that a journal like "Physics Today" does for the Physics community ?

From the information I could find online, I assume that the purpose of "Physics Today" is to summarize the incredibly vast field of physics and promote results that are considered important enough to be known from researchers with a different specialization from the subject matter. The focus is also on newly published results, rather than re-examining classical ones or establishing a "must-know" basis.

With this assumption, I believe the answer is no. The field has embraced Web technologies to a degree where results are usually known months before their official publishing in conferences and years before the journal version is out, with preprints being available typically via arxiv and rigorous discussions being held in popular blogs (for example Lipton&Regan, Fortnow&Gasarch , Aaronson ), TCS+ and questions appearing on this site as well.

Perhaps the one that comes the closest is Journal of the ACM (JACM).

See also this question.


Proofs that expose a deeper structure The standard proof of the Chernoff bound (from the Randomized Algorithms textbook) uses the Markov inequality and moment generating functions, with a bit of a Taylor expansion thrown in. Nothing too difficult, but somewhat mechanical.

But there are other Chernoff bound proofs that expose the deeper structure driving the result. For example, there's an information-theoretic version that goes via the method of types, exemplified by this paper of Impagliazzo and Kabanets, as well as this brief post by Sanjoy Dasgupta. These latter proofs are more "intuitive" in that they provides a generalization of the standard result, as well explaining where the funny terms in the exponent come from (it's a KL-divergence).

  What are good examples of such things
  ? To be more concrete, here are the
  rules:

  The statement should be reasonably well-known (the kind of thing that
  would be taught in some kind of
  graduate class)
  There should be a "standard" proof available in textbooks or standard
  reference material that is "commonly"
  taught
  There should be an alternate proof that is not so well known, is NOT
  commonly taught, and either proves a
  more general statement or links the
  statement to a deeper mathematical
  structure.

I'll start off with two examples.

The chernoff bound

"textbook" proof: markov inequality, moment generating functions, Taylor expansion (MR)
Uncommon and insightful proof: method of types, exponent of tail involving KL-divergence

The Schwartz-Zippel Lemma

"textbook" proof: base-case involving univariate polynomial. Induction on number of variables
"uncommon" proof: geometric argument via Dana Moshkovitz (and Per Vognsen)

One example per answer please.

p.s I'm not necessarily implying that the uncommon proof should be taught: a direct proof is often easier for students. But in the sense that "proofs help us understand", these alternate proofs are very helpful.

I'm not sure this is quite what you're looking for, since I've seen the "uncommon" proof in textbooks, but: the O(n log n) time bound for quicksort.

"Textbook" proof: set up a randomized recurrence relation, prove by induction that it has the desired solution.
"Uncommon" proof: find a simple formula for the probability that any two elements are compared (it's just 2/(d+1) where d is the difference between their ranks in the sorted order), and use linearity of expectation and harmonic series to compute the expected number of pairs that get compared.

The textbook proof requires less creative insight, but the uncommon proof introduces a technique that's very useful in other algorithm analysis e.g. for randomized incremental algorithms in computational geometry.


Succinct Problems in $\mathsf{P}$ The study of Succinct representation of graphs was initiated by Galperin and Wigderson in a paper from 1983, where they prove that for many simple problems like finding a triangle in a graph, the corresponding succinct version in $\mathsf{NP}$-complete. Papadimitriou and Yanakkakis further this line of research, and prove that for a problem $\Pi$ which is $\mathsf{NP}$-complete/$\mathsf{P}$-complete, the corresponding Succinct version, namely Succinct $\Pi$ is respectively, $\mathsf{NEXP}$-complete and $\mathsf{EXP}$-complete. (They also show that if $\Pi$ is $\mathsf{NL}$-complete, then Succinct $\Pi$ is $\mathsf{PSPACE}$-complete.

Now my question is, are there any problems $\Pi$ known for which, the corresponding Succinct version is in $\mathsf{P}$? I'd be interested in knowing about any other related results(both positive and impossibility results, if any) which I might have missed above. (I couldn't locate anything of interest by a google search, since search words like succinct, representation, problems, graphs
lead to just almost any complexity result! :))

Here is an interesting problem whose succinct version has interesting properties. Define Circuit-Size-$2^{n/2}$ to be the problem: given a Boolean function as a $2^n$-bit string, does this function have a circuit of size at most $2^{n/2}$?  Note this problem is in $NP$.

One way to define Succinct-Circuit-Size-$2^{n/2}$ would be: for a constant $k$, given an $n$-input, $n^k$-size circuit $C$, we want to know if its truth table is an instance of Circuit-Size-$2^{n/2}$. But this is a trivial problem: all inputs which are actual circuits are yes-instances. So this problem is in $P$.

A more general way to define Succinct-Circuit-Size-$2^{n/2}$ would be: we are given an arbitrary circuit $C$ and want to know if its truth table encodes an instance of Circuit-Size-$2^{n/2}$. But if $n$ is the number of inputs to $C$, $m$ is the size of $C$, and $m \leq 2^{n/2}$, we can automatically accept: the input itself is a witness for the language. Otherwise, we have $m \geq 2^{n/2}$. In that case, the input length $m$ is already huge, so we can try all possible $2^n$ assignments in $m^{O(1)}$ time, obtain the truth table of the function, and now we are back to the original $NP$ problem again. So this is a problem in $NP$ whose succinct version is also in $NP$.

This problem is believed to be not $NP$-hard; see the paper by Kabanets and Cai (http://www.cs.sfu.ca/~kabanets/Research/circuit.html)


how to formalize the class(?) of computational models and their equivalence Introductory books to theoretical computer science usually introduce a the Turing machine and some of its variants, as well as the Random Access machine as computational models. Sometimes more specialized or even exotic systems (such as quantum computers) can be found briefly sketched.

The equivalence of these models ( say two models A and B ) is usually proven by mimicing the mechanics of A with the "gears" of B and then providing "cheap" conversion functions which convert input of A to input B and output of B back to output A - the same is then done for A and B reversed.

Whereas proofs provide valid statements about well-defined mathematical objects, I don't think they prove what is ought to be proved, namely the equivalance of two computational models, because that question is non mathematically defined. I doubt that this can be done.

First of all, the conversion functions between the different input/output formats cannot necessarily be formalized as computations, because they act in "both worlds" (say binary strings and a cell setting in the game of life), and thus require a new computational model for themselves. Hence at least two further computational models are introduced. The triviality of the conversion functions doesn't seem be formalized. - One might argue that the conversions are the most vital part of the proof, because the "mimicry" of one model A within another model B has no mathematicly well-defined relation with the model A.

Second, I wonder whether the "class" of computational models can be formalized. I don't think it is a set, because, for example, you could build several Turing machines with 0 and 1 represented by arbitrary inequal sets. - One might define a category of computational models, with the arrows, say from object A to object B, present when A can be simulated by B. This raises the question what we would want the objects to be. I do not know.

I regard these points, (i) non having a formal definition for the conversion functions to be trivial, (ii) having no definition of a (Turing-equivalent) model of computation as unsatisfying.

Does anybody know whether and how this has been treated in literature so far? I am aware this touches what to understand the question of what to call "computation", but so do the usual practices in computer science anyway, in my opinion.

I recommend that you look at realizability theory. In realizability computational models are known as partial combinatory algebras (PCA). They cover a wide range of computational models. There is a 2-category of PCAs in which we can speak not only of equivlence, but also about general morphisms from one computational model to another.

Some references:

Jaap van Oosten's book on realizability.
John Longley's Ph.D. thesis.

John's Ph.D. is probably the best source to read about comparison of PCAs. An abridged version can be found in my Ph.D. thesis.

I should point out that realizability theory is just one way of organizing and structuring the world of computational models in a mathematically precise way. Nevertheless, it is a very sophisticated machinery which shows what can be done.


Does PPAD really capture the notion of finding another unbalanced vertex? Complexity class PPAD was invented by Christos Papadimitriou in his seminal 1994 paper. The class is designed to capture the complexity of search problems where the existence of a solution is guaranteed by "Parity argument in directed graphs": if there is an unbalanced vertex in a directed graph then there must exist another one. But usually the class is formally defined in terms of the $\mathsf{ANOTHER\ END\ OF\ THE\ LINE}$ ($\mathsf{AEOL}$) problem, where the argument is applied only to graphs with both in- and outdegrees $\le 1$. My question is: why are these notions equivalent?

Up to this point it is a duplicate of this question. Now I want to state the problem formally and to clarify why I am not satisfied with the answer there.

Search problem $\mathsf{ANOTHER\ UNBALANCED\ VERTEX}$ ($\mathsf{AUV}$): we are given two polynomial-sized circuits $S$ and $P$ that get $x\in\{0,1\}^n$ and return a polynomial list of other elements in $\{0,1\}^n$. These circuits define a directed graph $G=(V,E)$ where $V=\{0,1\}^n$ and $(x,y)\in E\Leftrightarrow (y\in S(x)\land x\in P(y))$. The search problem is the following: given $S$, $P$ and $z\in V$ such that $indegree(z)\ne outdegree(z)$, find another vertex with the same property.

Search problem $\mathsf{AEOL}$: the same, but both $S$ and $P$ return either an empty list or one element.

The notion of reducibility (corrected according to Ricky's suggestion): total search problem $A$ is reducible to total search problem $B$ via polynomial functions $f$ and $g$ if $y$ is a solution to $f(x)$ in problem $B$ implies $g(x,y)$ is a solution to $x$ in problem $A$.

Formal question: why is $\mathsf{AUV}$ reducible to $\mathsf{AEOL}$? Or should we use another notion of reducibility?

Christos Papadimitriou proves analogous theorem about PPA (Theorem 1, page 505) but the argument seems not to work for PPAD. The reason is that a vertex with degree balance $\pm k$ will be transformed into $k$ vertices with degree balance $\pm1$. Then the algorithm for $\mathsf{AEOL}$ may get one of these vertices and return another one. This would not yield a new vertex for $\mathsf{AUV}$.

Things are getting worse because in $\mathsf{AEOL}$ there is always an even number of unbalanced vertices but in $\mathsf{AUV}$ there might be an odd number of them. This is why one cannot build a bijection between these two sets and $g$ could not be always equal to $f^{-1}$. If $g(x,f(x))\ne x$ then we obtain a method for solving $\mathsf{AUV}$ in polynomial time at least for some instances. If $g$ does not depend on $x$ and $g(y_1)=g(y_2)$ for $y_1\ne y_2$ then $y_2$ may be returned as an answer for $y_1$. That would not give a solution for $\mathsf{AUV}$.

Final question: can the obstacles listed above be somehow overcome? Can one employ possible dependence of $g$ on $x$?

This is an interesting question, and I can only give a partial answer.

It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of AUV with its special case

  MANY ENDS OF THE LINE (MEOL): Given a directed graph $G$ with in-degree and out-degree at most $1$ (represented by circuits as above), and a nonempty set $X$ of sources of $G$, find a sink or a source $v\notin X$.

On the one hand, I find it hard to imagine a transformation of such graphs that could reduce a larger number of sources to one.

However, on the other hand, MEOL belongs to all commonly studied classes containing PPAD except possibly PPAD itself:

First, obviously,

  MEOL is in PPADS.

I will sketch below an argument that

  MEOL is in PPA

by reduction to the standard PPA-complete problem (the undirected version of AEOL). Assume we are given $G=(V,E)$ and $X$ as in the definition of MEOL.

If $|X|$ is odd, we can just make the graph undirected, include a matching on all but one vertex from $X$ (as in the argument on p. 505), and pass the result along with the remaining source from $X$ to the PPA oracle.

In general, let $s=|X|$, and $2^k$ be the largest power of $2$ that divides $s$. We define a new graph $G'=(V',E')$ whose vertices are $2^k$-element subsets of $V$. If $A,B\in V'$ are such sets, we put the edge $(A,B)$ in $E'$ if we can enumerate the sets as $A=\{a_0,\dots,a_{2^k-1}\}$, $B=\{b_0,\dots,b_{2^k-1}\}$ in such a way that $(a_i,b_i)\in E$ for each $i<2^k$.

Clearly, $G'$ is a directed graph with in-degree and out-degree at most $1$. An $A\in V'$ is a source (sink) iff it contains a source (sink, resp.) of $G$. (That is, if it contains both, it is an isolated vertex.) So, any such vertex would lead to a solution of the MEOL instance, unless $A$ is a “known source”: that is, $A\cap X\ne\varnothing$. We intend to make the graph undirected, and manipulate it so that the number of known sources is reduced to $1$ by including a matching on the remaining ones.

So, if $A$ is a known source, let $t=|A\cap X|$, which satisfies $0<t\le2^k$. If $t=2^k=|A|$, then simply $A\subseteq X$. The number of such sets is $\binom{s}{2^k}$. Recall that the multiplicity of a prime $p$ in $\binom ab$ equals the number of carries in the addition $b+(a-b)=a$ performed in base $p$. By the choice of $k$, it follows that $\binom{s}{2^k}$ is odd. Moreover, there are polynomial-time bijections between $[0,\binom ab)$, and $b$-element subsets of $[0,a)$. Using this, we can define a polynomial-time matching on all but one of $2^k$-element subsets of $X$. We include it in the graph, which reduces the number of known sources with $t=2^k$ to $1$.

For $0<t<2^k$, the carry-counting formula shows that $\binom st$ is even. Again, we can find an explicit matching on $t$-element subsets of $X$. We extend it to known sources $A$ with $|A\cap X|=t$ by applying the matching to $A\cap X$, and leaving $A\smallsetminus X$ fixed.

In this way, we produce an undirected graph with one known leaf vertex. We ask the PPA oracle for another leaf, and by construction, we can extract from it an answer for the MEOL instance.

As briefly mentioned by Papadimitriou, we can generalize PPA to classes PPA-$p$ for any prime $p$. An example of a PPA-$p$ complete problem is

  AUV-$p$: Given a directed graph $G$, and a vertex whose degree balance is ${}\not\equiv0\pmod p$, find another such vertex.

(See this answer for the equivalence of AUV-$p$ with Papadimitriou’s definition of PPA-$p$.)

PPA-$2$ is just PPA. The classes PPA-$p$ are assumed to be pairwise incomparable, and incomparable with PPADS. They all include PPAD.

There was nothing particularly special about $p=2$ in the argument I outlined above, and it can be easily modified to yield

  MEOL is in PPA-$p$ for every prime $p$.


Super-polynomial time approximation algorithms for optimization problems This is motivated by my previous question, Super-polynomial time approximation algorithms for MAX-3SAT.
For many optimization problems, for each one we have inapproximability lower bound $\alpha$ assuming some widely believed complexity theoretic conjecture. In other words, there is no polynomial time algorithm for such optimization problems with approximation ratio better than some $\alpha$ (different ratio $\alpha$ for each problem).

Are there optimization problems for which we can achieve approximation ratio better than $\alpha $ if we allow super-polynomial time algorithms? Can we achieve better approximation ratios using quasi-polynomial time algorithms ( $n^{O(\log n)}$) or even using sub-exponential time algorithms($2^{o(n)}$)?

I would appreciate a survey of such results.

One example is Maximum Independent Set. It is NP-hard to approximate the problem with ratio $n^{1-\epsilon}$ (Zuckerman, 2007). However, Bourgeois et al. (2011) give a simple $n^{1/2}$-approximation algorithm with running time $O^*(2^{\sqrt{n} \log n})$. Here, $n$ denotes the number of vertices of the input graph and the $O^*$-notation hides polynomial factors.

Another example is the Bandwidth problem. Dunagan & Vempala (2001) design an algorithm with approximation ratio $O(\log^3 n)$ and running time $O(n^{\log n})$. To my knowledge, the best known polynomial time approximation has approximation ratio $O(\log^3 n (\log \log n)^{1/4})$ (Lee, 2009); however, no $\omega(\sqrt{\log n / \log \log n})$ lower bound is known for the best approximation ratio achievable in polynomial time.