Categories a computer scientist should know about

Note that most of the categories you considered are 'abstract', i.e., they require structure or properties of an abstract category. As computer scientists we should also be familiar several concrete categories which turn out to be useful:

Concrete categories

Set
Set$_{\mathcal P}$ (objects are sets, morphisms are relations)
Rel (objects are relations, morphisms are functions preserving these relations)
Pred (objects are predicates (= subsets) morphisms are functions preserving these relations.
Posets
$\omega$-CPOs
Nominal sets
Lawvere theories

Abstract categories

Functor categories
Presheaf categories, in particular, monoid actions, which are equivalent to finite automata iianm
Locally presentable categories
Monads
Enriched categories (in particular, O-categories)
Kleisli and Eilenberg-Moore categories
Embedding-projection categories
Profunctors

Also, sometimes properties don't commute on the nose, and the structure under consideration is of higher-dimensional (i.e., 2-categorical).

As to your question 3: you can define a category without mentioning objects at all (though it's conceptually clearer if we do mention the objects).


No, you can't do much better than encoding your problem as a satisfiability problem, as it is NP-complete. Here is an example reduction to 3SAT to your problem:

For every clause, instantiate three vertices (one for every literal), which form one of your sets A_i. Chosing a vertex means that your 3SAT-solution should satisfy the clause by satisfying the respective literal. Then, add an edge between a node $x$ and $\neg x$ between of any clause for all variables $x$ in order to enforce that solutions are consistent. A solution to your problem for this graph then almost represents a 3SAT solution. I am writing "almost" as some variables may not occur in a chosen literal. These can have any value, however.


Yao's Minimax Principle on Monte Carlo Algorithms

I'll give it a try on this. I'm going to use Yao's original notation. This way it will be easier to contrast with his paper and his definitions.

Let $\mathcal{I}$ be a finite set of inputs, and let $\mathcal{A}_0$ be a finite set of deterministic algorithms that may fail to give a correct answer for some inputs. Let also $\epsilon(A,x)=0$ if $A$ gives the correct answer for $x$, and $\epsilon(A,x)=1$ otherwise. Also denote by $r(A,x)$ the number of queries made by $A$ on input $x$, or equivalently, the depth of $A$'s decision tree.

  Average Cost: Given a probability distribution $d$ on $\mathcal{I}$, the average cost of an algorithm $A\in \mathcal{A}_0$ is $C(A,d)=\sum_{x\in\mathcal{I}} d(x)\cdot r(A,x)$.

  Distributional Complexity: Let $\lambda\in[0,1]$. For any distribution $d$ on the inputs, let $\beta(\lambda)$ be the subset of $\mathcal{A}_0$ given by $\beta(\lambda)=\{A : A\in \mathcal{A}_0, \sum_{x\in\mathcal{I}} d(x)\cdot \epsilon(A,x)\leq \lambda\}$. The distributional complexity with error $\lambda$ for a computational problem $P$ is defined as $F_{1,\lambda}(P)=\max_{d} \min_{A\in \beta(\lambda)} C(A,d)$.

  $\lambda$-tolerance: A distribution $q$ on the family $\mathcal{A}_0$ is $\lambda$-tolerant if $\max_{x\in \mathcal{I}} \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x)\leq \lambda$.

  Expected Cost: For a randomized algorithm $R$, let $q$ be a probability distribution that is $\lambda$-tolerant on $\mathcal{A}_0$. The expected cost of $R$ for a given input $x$ is $E(R,x)=\sum_{A\in \mathcal{A}_0} q(A)\cdot r(A,x)$.

  Randomized Complexity: Let $\lambda\in[0,1]$. The randomized complexity with error $\lambda$ is $F_{2,\lambda}=\min_R \max_{x\in\mathcal{I}} E(R,x)$.

Now we are ready to go into business. What we want to prove is given a distribution $d$ on the inputs and a randomized algorithm $R$ (i.e., a distribution $q$ on $\mathcal{A}_0$)

  Yao's Minimax Principle for Montecarlo Algorithms \begin{equation}\max_{x\in\mathcal{I}} E(R,x)\geq \frac{1}{2}\min_{A\in \beta(2\lambda)} C(A,d) \end{equation}
  for $\lambda\in[0,1/2]$.

I will follow an approach given by Fich, Meyer auf der Heide, Ragde and Wigderson (see Lemma 4). Their approach does not yield a characterization for Las Vegas algorithms (only the lower bound), but it is sufficient for our purposes. From their proof, it easy to see that for any $\mathcal{A}_0$ and $\mathcal{I}$

Claim 1. $\max_{x\in \mathcal{I}} E(R,x)\geq \min_{A\in \mathcal{A}_0} C(A,d)$.

To get the correct numbers there, we'll do something similar. Given that the probability distribution $q$ given by the randomized algorithm $R$ is $\lambda$-tolerant on $\mathcal{A}_0$ we have that
\begin{align*}
\lambda &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\\
  &\geq \sum_{x\in\mathcal{I}} d(x) \sum_{A\in \mathcal{A}_0} q(a)\cdot \epsilon(A,x)\\
  &= \sum_{A\in \mathcal{A}_0} q(a)\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\
  &\geq \min_{A\in \mathcal{A}_0}\left\{ \sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}.
\end{align*}
If we replace the family $\mathcal{A}_0$ with $\beta(2\lambda)$ we see that

\begin{align*}
\lambda &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\\
     &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\beta(2\lambda)} q(A)\cdot \epsilon(A,x) \right\}\\
     &\geq \sum_{x\in\mathcal{I}} d(x) \sum_{A\in \beta(2\lambda)} q(a)\cdot \epsilon(A,x)\\ &= \sum_{A\in \beta(2\lambda)} q(a)\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\
     &\geq \min_{A\in \beta(2\lambda)}\left\{ \frac{1}{2}\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\},
\end{align*}

where the second inequality follows because $\beta(2\lambda) \subseteq \mathcal{A}_0$, and the last inequality is given by the definition of $\beta(2\lambda)$ where the summation divided by 2 cannot be greater than $\lambda$. Hence,
\begin{equation}\max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\geq\frac{1}{2} \min_{A\in \beta(2\lambda)}\left\{ \sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}. \end{equation}

By noting that $\epsilon$ maps to $\{0,1\}$ and $r$ maps to $\mathbb{N}$ and Claim 1 above, now we can safely replace the function $\epsilon$ in the inequality above by $r(A,x)$ to obtain the desired inequality.


There is a really nice talk on the dynamic lower bounds on graphs by Mihai Pătraşcu. In summary (on p.20 of the slides), we have the lower bounds in terms of query time $t_q$ and update time $t_u$ (insert an edge):

See the paper for details. Some other papers by Mihai are relevant and nice, too.

UPDATE: I found that his PhD thesis "Lower Bound Techniques for Data Structures" providing lower bounds for many central data-structure problems using the techniques he developed. It certainly worths a read.


Are there works on "quantum parametrized complexity"?

As far as I'm aware, parameterized complexity theory has not been formally introduced to quantum computing so far.

Many problems in the field, though, are well-known to be tractable once a key parameter is fixed, such as constant spectral gaps of local Hamiltonian operators, or bounded condition numbers of various matrices. Fixing the parameter often lead to tractable subclasses of problems (see Matrix Product States and Lieb-Robinson bounds) or efficient classical or quantum algorithms (e.g. Harrow-Hassidim-Lloyd algorithm), for which the general problem is usually exponential in that parameter.

There are some works that explicitly use standard parameters of the fixed-parameter tractability (FPT) literature, e.g.

Markov and Shi [https://arxiv.org/abs/quant-ph/0511069] show how to efficiently and classically compute acceptance probabilities of quantum circuits viewed as tensor networks with bounded tree-width
Bravyi [https://arxiv.org/abs/0801.2989] shows how to contract matchgate circuits on non-planar graphs with bounded genus
Van den Nest and Briegel [https://arxiv.org/pdf/quant-ph/0610040.pdf] show that measurement-based quantum computing, which is performed on a family of graph states G, can be classically efficiently simulated if G has a decidable C$_2$MS logic theory (based on a result of Courcelle and Oum implying bounded rank-width of such graphs).


Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

There are large classes of queries which are "easy", even in the worst case.  In particular, if the class of queries contains conjunctive queries only and each query has bounded width (for instance treewidth, treewidth of its incidence graph, fractional hypertree width, or submodular width) then the query can be answered by using something like a join tree, together with brute force enumeration for the local parts of the query that deviate from the tree.  This requires polynomial time, with the degree of the polynomial determined by the width parameter.

It seems that many queries encountered in practice are both conjunctive and have small width.  So the polynomial runtime has low degree in this case.

Dániel Marx presented a paper at STOC 2010 on submodular width recently, the full version of which includes a nice summary of the various notions of width and how the CSP formulation relates to the database formalism (the conference version lacks this).

Dániel Marx, Tractable hypergraph properties for constraint satisfaction and conjunctive queries, 2010. arxiv:0911.0801

This is not a complete answer, since it does not deal with the "typical" complexity of database queries, but even with worst-case analysis there are easy queries.


Problem conditions to use Laplacian solvers

It's a good question. You can use a Laplacian solver if $A$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition of the proof (which was originally by Gremban) can be found in Appendix A of the paper by Kelner, Orecchia, Sidford and Zhu (arXiv:1301.6628).
A recent result by Kyng and Zhang (arXiv:1705.02944) suggests that current Laplacian solvers are probably restricted to this class.


Ref question: K-nearest neighbours in a graph

In Victor Teixeira de Almeida, Ralf Hartmut Güting: Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases. SAC 2006: 58-62, Teixeira and Güting describe a new storage schema with a set of indexed structures to support an efficient
execution of a slightly modified version of the Dijkstra's algorithm.

In the introduction they simply use the reference to the original Dijkstra's paper:

... An obvious modification on Dijkstra's algorithm
[reference to the original Dijkstra's 1967 paper] that computes shortest path between objects could be done in order to compute the k-NN using the network space.
But, in this case, sepcial storage schemas are necessary in order to
efficiently support this algorithm. In this paper, ...

So I think you can use the same approach: if your work is NOT focused on a new variant of a k-NN algorithm you can simply mention it and cite Dijkstra's paper; otherwise you should also include other references on the subject; I think there are many of them because the k-NN problem is important, for example, in navigation systems; googling around I found: Fast Nearest Neighbor Search on Road Networks, Alternative Solutions for Continuous K-NN Queries in Spatial Network Databases, ...


Partition of a set of integers into subsets with prescribed sums

For any fixed $k$, isn't it in P, by dynamic programming?

For each $i\in\{0,\ldots,n\}$ and $t_1, t_2, ..., t_k$ such that each $t_i \in \{0,\ldots,m_i\}$, define $S(i, t_1, t_2, \ldots, t_k)$ to be true iff $(t_1, t_2, .., t_k)$ is $i$-realizable.  Then there are $O(n^{2k+1})$ such subproblems (assuming WLOG that $\max_i m_i\le n^2$), and you have a recurrence like

$ S(i, t_1, t_2, \ldots, t_k)$

$~ = S(i-1, t_1 - i, t_2, \ldots, t_k) $

$~\vee~ S(i-1, t_1, t_2 - i, t_3, \ldots, t_k)$

$~\vee~ \cdots$

$~\vee~ S(i-1, t_1, t_2 , t_3, \ldots, t_{k-1}, t_k- i)?$


Usually, you should be able to figure out who are the leading researchers or research groups in your research area.

Everything else is then usually fairly straightforward: just find out in which conferences the leading researchers publish their work, and in which conferences they serve in programme committees, etc. Most likely those would be the most relevant conferences for your work as well.

The same applies to journals as well.

(Note that the most relevant conference is not necessarily the same as the most prestigious conference, but it might be a good idea to start with relevant conferences... Your work might have much more impact that way, even if it does not look that impressive in your CV.)


Deterministic Parallel algorithm for perfect matching in general graphs?

$NC$ algorithms for perfect matchings in general graphs is still open but there has been some progress. Here are a few that I am aware of:

For general graphs, Agrawal-Hoang-Thierauf showed that given the promise that the number of perfect matchings is small, there is an $NC^2$ algorithm to enumerate all of them.

For the class of planar graphs, the pfaffian plays a big role. Kastelyn showed how every planar graph can be oriented in a way such that the pfaffian exactly equals the number of perfect matchings. (This was used by Valiant in to give "Holographic algorithms" for various problems) Mahajan-Subramanya-Vinay showed how the pfaffian can be computed in $NC$ using modifications of clow sequences. (Kastelyn in fact gives an algorithm to find the embedding in $P$ but I'm not sure if the pfaffian embedding can also be computed in $NC$; if yes, that would mean that counting perfect matchings in planar graphs is in $NC$.)

And a recent result of Vinodchandran-Tewari show that the isolation lemma can be "derandomized" for planar graphs (using Green's theorem!) to put planar reachability in $UL$. But $NC$ algorithms for planar matchings are still open (thanks to Raghunath for correcting my claim that it is in $UL$). An $NC$ algorithm for bipartite planar matchings was given by Datta-Kulkarni-Roy

Hope this helps.


Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers

Here is a grammar that should meet your specification, though it
generates the very simple language $a^+(b+c)$.  (A simpler grammar has been added below)

$S \rightarrow ab \mid aBb \mid ac \mid aCc$
$B \rightarrow a \mid aB \mid aBB$
$C \rightarrow a \mid aC \mid aCC$

How was it built:

I started from the grammar
$\{S \rightarrow S S \mid a\}$ which is very ambiguous, so that trying all
parses of a string $a^n$ takes exponential time.

I put it in Greibach Normal Form, so as to remove any left recursion,
giving

$S \rightarrow a \mid aB$
$B \rightarrow a \mid aB \mid aBB$

Then I introduced $C$ to duplicate the possibilities of derivation,
with $b$ or $c$ as end marker to discover at the very end whether I
should have been using $B$ or $C$ as non-terminal in my derivation,
i.e,, whether the first rule to apply was $S \rightarrow aBb$ or $S
\rightarrow aCc$. But if the choice of rule made at the very beginning
was wrong, the backtracking process will have first to try all parsing
possibilities for the string of $a$, which has exponential cost.

Since the recursive descent has to try first one of the two rules,
there will always be a string (requiring the other rule) that takes
exponential time to parse, because of the useless backtracking with the wrong non-terminal.

Memoisation brings this down to cubic time. Naive memoisation will make it $O(n^4)$, but a bit of currification can correct that to cubic time.

A simpler solution (thought of later)

All that matters in the above grammar is to force an early choice of
the terminal marker $b$ or $c$, while having that choice checked only at the end
of the parsing process.

Hence the following grammar is enough to get the desired exponential
behaviour. Actually it is a (renaming) homomorphic image of the first
grammar above, and leads to exactly the same computation up to that
renaming.

$S \rightarrow ab \mid aXb \mid ac \mid aXc$
$X \rightarrow a \mid aX \mid aXX$

The rules $S \rightarrow ab \mid ac$ are not actually necessary for
our purpose, but that is minor. Removing them would change the language to $aa^+(b+c)$. Then, it is also possible to remove the initial $a$ in the rules $S \rightarrow aXb \mid aXc$ without introducing left recursion, thus getting back the initial language $a^+(b+c)$. But the grammar is no longer in Greibach normal form (which was not a requirement of the problem). This gives a solution with only 5 rules:

$S \rightarrow Xb \mid Xc$
$X \rightarrow a \mid aX \mid aXX$


maintaining a balanced spanning tree of a growing undirected graph

Every time you add a new vertex with an edge, you don't have options.
Every time you add a new edge, if the current distance to the root is bigger than the distance through the new edge, you remove the old edge in the old shortest path and add the new one. Otherwise, you just keep your tree unchanged. I think this way you get something very similar to a BFS tree in the sense that the levels of the tree will contain the same vertices and the distance from a vertex to the root will be the same as the distance in the BFS tree (and in the graph), but I don't know if that's enough to satisfy your "ideal balanced spanning tree" condition.


Relation between tree-width and clique number

On this page a theorem is mentioned that provides such classes:

Theorem (Scheffler [1]) If $G$ is the intersection graph of connected subgraphs of another graph $H$, then $tw(G)\leq tw(H)\omega(G)-1$.

This generalizes the bound for chordal graphs (for which $H$ is a tree) and also applies to circular-arc graphs (then $H$ is a cycle). I do not know if other "standard" classes are captured by this theorem.

[1] P. Scheffler, What graphs have bounded tree-width? Rostocker Math. Kolloq. 41 (1990) 31-38.


Just an extended comment to better explain ARi's comment (I was writing it while I saw it).

It is sufficient to use a "large gap" approach similar to the one used in Lardner's theorem; for example:

$A_1 = \{ x \mid x \in SAT \land f(|x|) \text { is even}\} \cup \{x \mid f(|x|) \text{ is odd} \}$

$A_2 = \{ x \mid x \in SAT \land f(|x|) \text { is odd}\} \cup \{x \mid f(|x|) \text{ is even} \}$

Where $f$ is a slow enough increasing function computable in polynomial time. See for example its construction in Ladner's theorem proof in Appendix A.1 of Uniformly Hard Languages.

By construction $A_1, A_2$ are not NPC, but $A_1 \cap A_2 = SAT$


Good Survey paper for k-means/k-median/k-center/facility-location

Recently, I came across the following survey: Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems
The authors only discuss the major results and mention some interesting open problems at the end.


A starting point might be this survey:

T. Terlaky and S. Zhang, "Pivot Rules for Linear Programming:A Survey on Recent Theoretical Developments", Annals of Operations Research, 46, 203 - 233, 1993.(Technical Report, pdf)


Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

Makespan minimization on identical machines under precedence constraints

  Open problem 1. Provide a $4/3+\delta$ inapproximability result for $P|prec|C_{max}$.

Here what comes first to mind is the paper of this year by Ola Svensson "Conditional Hardness of Precedence Constrained Scheduling on Identical Machines". In his paper Ola proves that

  "if the single machine problem is hard to approximate within a factor of $2-\epsilon$ then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of $2-\zeta$, where $\zeta$ tends to 0 as $\epsilon$ tends to 0."

In 2008 there was published the paper "Precedence constrained scheduling in $(2−\frac{7}{3p+1})$ · optimal" describing an algorithm for $P|prec,p_j=1|C_{max}$ with the performance ratio, mentioned in its title. This improves upon Coffman-Graham algorithm with bound $2-\frac{2}{p}$, where $p$ is the number of machines.

The paper "Approximation algorithms for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba contains PTAS for $Qm|chains|C_{max}$, and, as a consequence, for $Pm|chains|C_{max}$ as a special case of the former problem.

This year there was appeared the article "Approximation schemes for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba (journal version of the previous one), which concerns PTAS for $P|chains|C_{max}$ with a fixed number of jobs in every chain and $P|prec|C_{max}$ with a constant number of jobs in every order's connected component.

Makespan minimization on uniform machines under precedence constraints

The 2003 year's paper "Approximation algorithms for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba contains PTAS for $Qm|chains|C_{max}$.

Makespan minimization under precedence constraints with communication delays

Makespan minimization on unrelated machines

Makespan minimization in open shops

Makespan minimization in flow shops

In the paper of Nagarajan and Sviridenko from 2008 "Tight Bounds for Permutation Flow Shop Scheduling" we can find the upper bound on the ratio between optimal makespan and the makespan of the best permutation schedule. This bound is the approximation ratio of an algorithm proposed, and it is the best possible among algorithms based on the trivial lower bounds, up to $2\sqrt{2}$ factor. Incidentally, the algorithms proposed are currently the ones with the best approximation ratios.

Makespan minimization in job shops

  Open problem 7. Decide whether there exists a polynomial time approximation algorithm
  for $J||C_{max}$ whose worst-case performance is independent of the number $m$ of machines and/or independent of the maximum number $\mu$ of operations. Provide a $5/4+\delta$ inapproximability result for $J||C_{max}$. Provide an inapproximability result for $J||C_{max}$ whose value grows with the number $m$ of machines to infity.

  Design a PTAS for $J2||C_{max}$ for the case where $\mu$ is part of the input; or disprove the existence of such a PTAS under P$\ne$NP.

Dissertation by Svensson "Approximability of Some Classical Graph and Scheduling Problems" contains results showing that $J||C_{max}$ cannot be approximated within $O((\log lb)^{1-\epsilon})$ assuming $NP\subseteq ZTIME(2^{\log n^{O(1/\epsilon)}})$ and that $J2||C_{max}$ has no PTAS unless $NP\subseteq DTIME(n^{O(\log n)})$.

Total job completion time without precedence constraints

Total job completion time under precedence constraints

  Open problem 9. Prove that $1|prec|\sum C_j$ and $1|prec|\sum w_jC_j$ do not have polynomial time approximation algorithms with performance guarantee $2−\epsilon$ unless P=NP.

In "Optimal long code test with one free bit" Bansal and Khot proved that it is so, but assuming a new variant of the unique games conjecture.

Flow time criteria

  Open problem 10. Design polynomial time approximation algorithms with constant performance guarantees for $1|pmtn;r_j|\sum w_jF_j$ and for $P|pmtn;r_j|\sum F_j$.

In "Weighted ﬂow time does not admit $O(1)$-competitive algorithms" Bansal and Chan proved that $1|pmtn;r_j|\sum w_jF_j$ "does not admit $O(1)$-competitive algorithms". Interestingly, the authors don't cite the paper of Schuurman and Woeginger.

In "Minimizing Average Flow-time: Upper and Lower Bounds" Garg and Kumar proved a lower bound $\Omega(\sqrt{\frac{\log P}{\log\log P}})$ on the approximation ratio for $P|pmtn;r_j|\sum F_j$. Later this bound was improved to $\Omega(\frac{\log P}{\log\log P})$ in "Minimizing Total Flow-Time: The Unrelated Case" by Garg, Kumar and Muralidhara.


Problems in $\mathsf{BPP}$ not known to be in $\mathsf P$?

If you're asking for independent problems, how about:

  Find a prime in the interval $[N, 5N/4]$,
  Find two primes whose product is in the interval $[N, 9N/8]$,
  Find three primes whose product is in the interval $[N, 17N/16]$,
  Find four primes whose product is in the interval $[N, 33N/32]$,
  Find five primes whose product is in the interval $[N, 65N/64]$,
  $\ldots$.

It's overwhelmingly likely that if you actually had a polynomial algorithm to solve the first of these, you would have a polynomial algorithm for all of them. But I don't see how to formally reduce any of these to any of the others. Of course, the problem

  Find a prime in the interval $[N, N+\log^{17} N ]$

solves all of these.


Maximum matching versus preferential assignment

After some introspection, I'd like to suggest the following natural problem. A  skew-symmetric digraph is a digraph $G$ where each vertex comes in two copies $v,v'$ (possibly identical) and such that for each arc $(u,v) \in A(G)$ we also have $(v',u') \in A(G)$. The problem consists of packing cycles in a skew-symmetric digraph under a weight constraint. That is to say, we are given a ssd $G = (V,A)$, a weighting $w : V \rightarrow \mathbb{N}$ s.t. $w(v') = w(v)$ for each $v \in V$, and an integer $k$, and we seek a family of $k$ cycles $\cal{C}$ in $D$ such that (i) $V(\cal{C})$ has maximum cardinality, (ii) each $C \in \cal{C}$ is skew-symmetric, i.e. if it contains $(u,v)$ then it also contains $(v',u')$, (iii) each vertex $v$ is contained in at most $w(v)$ cycles of $D$.

This problem would generalize two well-known problems in combinatorial optimizations: (1) maximum matchings in undirected graphs and (2) maximum $k$-chains in posets. Here is a sketch of the reductions. For problem (1) we start with an undirected graph $G$, and we let $D$ be the symmetric digraph obtained from $G$ with each vertex self-symmetric, assigning a weight one to each vertex. For problem (2) we start with a poset $P_0$ with underlying digraph $D_0$, and we let $D$ be the digraph obtained by taking the disjoint union of $D_0$, its symmetric copy, and arcs $(v,v'), (v',v)$ for each vertex $v$ of $P$; we assign a weight one to each vertex.

I'm not sure about the practical application of your problem, but I expect it to be P-hard: a reduction from 3HornSat to the weighted version seems possible although I didn't check the details. If this problem turned out to be in P (with a corresponding min/max result) it would be very interesting, at least from a theoretical standpoint.


The problem that you are describing seems to be a variation of a critical node detection problem. In general, most critical node detection problems aim to identify a set of at most $B$ nodes (or if you are considering the weighted case, a set of nodes with a weighted sum of at most $B$ ) whose deletion results in the maximum disruption of a given property of the graph. In many of the papers that you can find in the literature, the property that is being disrupted often represents a measure of how well connected the residual graph is. For instance, such property may account for the total number of node pairs that remain connected, the number of maximally connected components, or the size of the largest connected component after the critical nodes are removed (you can also search for node interdiction or node blocker problems for other versions). Some references are: Arulslevan et al [1], Shen et al [2], Di Summa et al [3], Addis et al [4], Oosten et al [5] among others. There is also a very short survey [7] on some of these problems. Although, several other papers have been published after that chapter was in press.

These problems are indeed NP-Hard for general graphs. However, there are some polynomially solvable cases (trees and series-parallel graphs, see [3], [4], and [6]).

For the version that you mention, which is somehow a complement of the above problems (instead of maximizing the disruption, you minimize the number of critical nodes to achieve the desired disruption) there is an article that proves inapproximability for the version of the problem in which the disrupted property is the total number of pairwise connections [8]. Your intuition is correct, vertex cover is commonly used to as a steeping stone.

If have some other questions or ideas, you can send me an email. This is one of my research interests. I will be happy to provide you with more ideas and to collaborate.

There is also something to keep in mind. These problems lay in the intersection of several fields, so there may be some similar versions with different names (I have found problems that belong to the same family, like graph separators, pivotal vertices, and articulation points).

[1]: Detecting critical nodes in sparse graphs

[2]: Exact interdiction models and algorithms for disconnecting networks via node deletions

[3]: Complexity of the critical node problem over trees

[4]: Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth

[5]: Disconnecting graphs by removing vertices: A polyhedral approach

[6]: Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs

[7]: Selected Topics in Critical Element Detection

[8]: On New Approaches of Assessing Network Vulnerability: Hardness and Approximation


What is a really good problem to get your hands dirty in computational-geometry?

To mix Suresh V.'s and Dave C.'s suggestions, it might be fun to try to gain experimental evidence
on an unsolved problem by implementing the necessary algorithms.  For example, it is now known that the Delaunay triangulation is not a ($\pi$/2)-spanner
[Prosenjit Bose, Luc Devroye, Maarten Löffler, Jack Snoeyink, Vishal Verma: "The spanning ratio of the Delaunay triangulation is greater than $\pi$/2." CCCG 2009: 165-167.]
You could implement a Delaunay triangulation algorithm, and shortest paths, and try to
determine experimentally what the true spanning ratio might be.
Or, more challenging, try to compute the combinatorial complexity of the Voronoi diagram of lines in $\mathbb{R}^3$,
another unsolved problem (and in the list that Suresh mentions as Problem 3.)


Equivalence of feasibility checking and optimization for linear systems

The answer is yes, and in fact one can even reduce to the decision problem of linear inequalities feasibility!

We are as input given a LP instance P:
$\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$.

We furthermore have access to an oracle that given a system of inequalities $S=\{Bz \leq d\}$ returns yes/no, whether the system is feasible.

The reduction now proceeds as follows:

Test if $S_1=\{Ax \leq b\ ;\ x \geq 0\}$ is feasible. If not, we can report that P is INFEASIBLE.
Form the dual program D: $\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$.
Test if $S_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$ is feasible. If not, we can report that P is UNBOUNDED.
Iterate over the inequalities of $S_1$ and try to add them one-by-one as equalities (i.e. add the reverse inequality) to the system $S_2$. If the system remains feasible we keep the constraint in $S_2$, and otherwise remove it again. Let $S_3$ be the system of constraints (linear equalities) that gets added in this way. The system $S_3$  will now completely determine an optimal basic solution to P.
Using Gaussian Elimination on the system $S_3$ compute an optimal solution $x$ to P.


Representing non-planar graphs with overlapping circles

The definitive article is a paper by Hlineny and Kratochvil from 2001. In it they show that the problem of recognizing a disk intersection graph (your question) is NP-hard, which suggests that it will be difficult to come up with a clean characterization. They also point out that $K_{3,3}$ cannot be represented as the intersection of disks, answering the other part of your question.


Negative results on identical particles approach to Graph Isomorphism (GI) problem

You can do much better than checking all n! permutations when brute forcing a solution, http://oeis.org/A186202  The grail is showing that you can't do much better than that, or exploiting the fact that most graphs have no symmetry in them and using this to speed calculation.


$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$?

It seems to me that you are not familiar with the basic complexity theory and therefore your question is probably not suitable for cstheory.

You probably mean to ask if the following statement is true:

  $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$.

Note that the $\mathsf{NTime}$ hierarchy theorem is tight. If the answer to your question was positive then it would separate $\mathsf{NTime}$ from $\mathsf{DTime}$ which is not known as explained in the answers to the question linked by Robin.


Does a multilayer perceptron taught by simple backprop learn the shape of a character or the exact image of a character?

I would be very surprised if a backpropagation-trained multilayer FFN spontaneously learned concepts of shape. It's not that the notion of "shape" isn't representable by a FFN (given enough layers, anything is). It may even be the case that the globally optimal configuration does capture something about shape. But there must be a strong local minimum about the exact-image replicator, meaning that typical backpropagation (i.e., gradient descent) algorithms will get stuch in such local minima. Unless you've specifically primed your FFN to learn shape, I would be very surprised if it did.


When does a graph admit an orientation in which there is at most one s-t walk?

It's NP-complete by a reduction from not-all-equal-3SAT. To see this, observe that

The only valid orientation of a $4$-cycle is one in which the edges alternate orientations.
Let $P$ be a three-edge undirected path, and add a degree-two vertex adjacent to the endpoints of $P$ to form a $5$-cycle. Then the only orientations of $P$ that can be extended to valid orientations of the entire $5$-cycle are the ones in which $P$ is not consistently oriented as a directed path.

We form a variable gadget for a variable $v$ that belongs to $k$ different clauses of the NAE-3SAT instance, by gluing together $k$ shared $4$-cycles on a shared edge. Then in each of the $4$-cycles, the opposite edge to the shared edge has to be oriented consistently with all of the other $4$-cycles. We will associate the truth value of the variable with this consistent orientation of these edges. Additionally, in any valid orientation of each of these $4$-cycles, there is no path from one $4$-cycle into another $4$-cycle, so these gadgets can interact with each other only in the orientation of their edges and not through the existence of longer paths.

We form a clause gadget for a 3-variable clause of the NAE-3SAT instance by gluing together three of $4$-cycle edges, opposite the shared edges of the appropriate three variable gadgets, into a 3-edge path $P$ and then adding a degree-two vertex to complete $P$ into a $5$-cycle. As discussed above, this $5$-cycle can be consistently oriented if and only if its three edges are not all oriented as a directed path, which (when glued correctly) is true if and only if the truth values associated with these orientations are not all equal.

By the way, DAGS with at most one $s$-$t$ walk for each $s$-$t$ pair have been studied previously, as "multitrees", "strongly unambiguous graphs", or "mangroves"; see https://en.wikipedia.org/wiki/Multitree


This appears to be a very hard problem, related to a more widely-studied one.

Suppose we consider a square invertible matrix A, and define c(A) as the minimal number of elementary row operations needed to reduce A to the identity matrix.  This complexity measure is larger than the one Moritz suggests, so proving superlinear bounds for it can only be easier.

Now, row operations are reversible.  It follows that c(A) can be equivalently defined as the minimum number of row operations needed to produce A, starting from the identity matrix.

Notice that producing A in such a fashion gives rise to an arithmetic circuit to compute the map taking x to Ax.  The fanin of each gate is 2, and the number of non-input gates corresponds to the number of row operations.

There isn't any obvious reduction in the reverse direction (from circuits to row-op sequences).  Still, we can characterize c(A) in terms of the arithmetic circuit complexity of Ax in a restricted circuit model: I claim that c(A) is equal to one-half the minimum number of edges in an arithmetic circuit for A, of fanin at most 2 and width n, where we don't charge for edges leading into gates of fanin 1.
(I'm using the usual notion of circuit width here.)  This can be shown using the simple idea sketched before.

Now here's the connection to well-studied problems: it's been a famous open problem for over 30 years to exhibit an explicit linear map Ax (over any finite field) which requires a superlinear number of gates in a fanin-2 circuit.  The classic reference is Valiant, "Graph-theoretic arguments in low-level complexity", and a recent FTTCS survey by Lokam is also helpful.

In studying c(A), we are imposing an additional width restriction, but since our restriction is so weak (width n) I don't anticipate the problem becoming much easier.  But hey--I'd love to be proved wrong.


Known algorithms to go from a DFA to a regular expression

Two more constructions: Brzozowski-McCluskey aka state elimination [1], and Gaussian elimination in a system of equations using Arden's Lemma.  The best source on these is probably Jacques Sakarovitch's book [2].

[1] J. Brzozowski, E. McCluskey Jr., Signal ﬂow graph techniques for sequential circuit state diagrams, IEEE Transactions on Electronic
Computers EC-12 (1963) 67–76.

[2] J. Sakarovitch, Elements of Automata Theory.  Cambridge University Press, 2009.


You asked a similar question some time ago about concatenation.  I gave the references back then and they still apply here.    See Yu, Zhuang, and K. Salomaa in their paper, "The state complexities of some basic operations on regular languages", TCS 125 (1994), 315-328, where the state blow-up for Kleene * is described in detail; it is exponential in the worst-case for languages over 2-letter alphabets or larger, with a bound of the form $3 \cdot 2^{n-2}$.  The result for Kleene * was also published (without proof) by Maslov in Dokl. Akad. Nauk SSSR (1970) (and in English in the translation journal Soviet Math. Dokl.)

Evidently the complexity of actually computing the DFA could be exponential in the worst-case, too, then.


Is there an oracle such that SAT is not infinitely often in sub-exponential time?

You can just take the oracle A s.t. NP$^A$=EXP$^A$ since EXP is not in i.o.-subexp. For SAT$^A$ it depends on the encoding, for example if the only valid SAT instances have even length then it is easy to solve SAT on odd-length strings. But if you use a language like $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$ then you should be fine.


Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$

One such class is the counting hierarchy $\mathsf{CH}$. It is defined as the union of a hierarchy that is defined similarly to the polynomial hierarchy:

$\mathsf{C}_{0}\mathsf{P} := \mathsf{PP}$,
$\mathsf{C}_{i+1}\mathsf{P} := \mathsf{PP}^{\mathsf{C}_{i}\mathsf{P}}$
$\mathsf{CH} := \bigcup_i \mathsf{C}_{i}\mathsf{P}$

The counting hierarchy has a nice syntactic characterization due to
H. Vollmer and K. Wagner "Recursion theoretic characterizations of complexity classes of counting functions", Theoretical Computer Science 163:245-258, 1996:
$\mathsf{CH}$ ist the set of $0$-$1$-valued functions in the closure of basic arithmetic functions $0,1,+,-,\cdot$ under composition and bounded sums.


How to construct a special data structure that allows for "fast" subset operation?

Represent sets as Bit Sets. Java has built-in implementation. A is subset of B if A & B = A. These operations on bit sets are fast (O(1) ).


Applications of algebraic geometry in Boolean complexity

In addition to the Geometric Complexity Theory Program already mentioned by Sasho Nikolov (see e.g. here, and - shameless self plug, but has tons of references on uses of AG in complexity - here), there's also:

Work on matrix multiplication (Strassen's work especially come to mind, as well as the more recent GCT-style work of Burgisser and Ikenmeyer, but also some other stuff in between)
Mulmuley's "P vs NC" result (this is a Boolean result - if you need convincing I'm happy to), which can be seen as building off of Ben-Or's sorting lower bound and others
Work on derandomizing polynomial identity testing (several papers of M. Agrawal come to mind). (Which, in retrospect, is deeply related to GCT.)
Coding theory (there's a whole "subfield" on AG codes)


Initial population for a genetic algorithm from one individual

One nice thing about QAP is that local search methods can take advantage of incremental evaluation of modified solutions, and GAs typically can't. So a pure GA needs O(n^2) time for every fitness evaluation, but a local search can do many fitness calculations in O(1) time, and the rest in O(n).

What I've often done for QAP is to employ something like a tabu search method to do much of the search. See Eric Taillard's paper on Robust Tabu Search for a good example of how to apply it to QAP in particular, including how to do the incremental fitness update.

You can generate multiple good initial points by running multiple tabu searches from random starting points, or you can integrate it directly into the GA as a hybrid method.


What are the outstanding questions in purely functional data structures?

I'll interpret the question somewhat liberally. For Okasaki-style data structures, memoization is a form of implicit mutation that has a side effect on running time. Thus I'll take the question to concern persistent data structures in the strict sense rather than data structures with a purely functional implementation, which are a subset of the former. By strict I mean that you should able to access older versions of a data structure without penalty, the tree of versions can branch arbitrarily, etc.

In that context, I consider persistent UNION-FIND an important open problem. There's the Conchon-Filliâtre paper that was mentioned in the other thread. A commenter already brought up an issue with their so-called persistent array: it's really only semi-persistent. But suppose you replace it with a hash trie or some other truly persistent array that behaves better in the worst (and arguably average) case but worse in the best case. That still leaves an important issue open:

The paper gives a formal proof of correctness in Coq. But they fail to address the amortized complexity either formally or informally. It's very much not clear to me that the complicated behind-the-scenes mutation results in the expected amortized complexity in all cases. When I last thought about it, I felt somewhat confident I could construct a counterexample if I put effort into it. Even if I'm wrong about that last part, the lack of a proper analysis is a major gap; it's clear that Trajan's classical amortization analysis of UNION-FIND doesn't directly transfer.


It looks like there are some known lower bounds (see page two of Sorting Short Keys in Circuits of Size $o(n\log n)$). The relevant section is copied below:

More specifically, Lin, Shi, and Xie [LSX19] showed that any stable compaction circuit that treats the payload as indivisible must have at least $\Omega(n \log n)$ selector gates — here the indivisibility assumptions requires that the circuit only move the payload around through selector gates but not perform boolean computation on the encoding of the payload.  The indivisibility restriction in Lin et al.’s lower bound [LSX19] can be removed if one assumes the Li-Li network coding conjecture [LL04] — this is implied by Afshani et al. [AFKL19]’s recent work$^2$.

Given that this is the case, it seems like the best thing to do is to use sorting networks. There seem to be a few new ones which may be competitive (see for example this), but I can't say anything definitive.


How good of an approximate 2-coloring can you get of the halved cube graph?

The answer is $\epsilon_n = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2}$.

First, here's a formal definition of the halved cube graph $H_n$. The vertices are bitstrings of the form $a_1a_2\ldots a_n$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$. Two vertices $a_1a_2 \ldots a_n$ and $b_1b_2\ldots b_n$ are adjacent if and only if they differ in exactly two bits.

Define coloring $col_n$ of $H_n$ as follows: $$col_n(a_1a_2\ldots a_n) = a_1 \oplus a_2 \oplus \cdots \oplus a_{\lceil\frac{n}{2}\rceil}$$.

Consider the probability that a uniformly random edge has different colors on its two endpoints. It should be easy to see from the definition that an edge whose endpoints differ in bits $i$ and $j$ has different colors on both end points if and only if exactly one of these two indices is at most $\lceil\frac{n}{2}\rceil$. Furthermore, if we choose a uniformly random edge, then the pair of indices at which that edge's endpoints differ also ends up uniformly random (among all possible pairs of indices). Thus, the probability we are looking for is equal to the probability that a uniformly random pair of indices has the property that one index is at most $\lceil\frac{n}{2}\rceil$ while the other is not. There are $\left(\lceil\frac{n}{2}\rceil\times \left(n-\lceil\frac{n}{2}\rceil\right)\right) = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ pairs with this property and $n \choose 2$ pairs in total. Thus, the probability we are looking for is $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2} = \epsilon_n$. In other words, we have shown that coloring $col_n$ is an $\epsilon_n$-approximate coloring.

If $v = a_1a_2\ldots a_n$ is a vertex and $i$ is an index, then define $V(v, i) = \{v\} \cup \{b_1b_2\ldots b_n \in N(v)~|~a_i \ne b_i\}$ (where $N(v)$ is the set of neighbors of $v$). It is easy to show that all vertices in $V(v,i)$ are adjacent.

Consider the following procedure:

choose a vertex $v$ uniformly at random from $H_n$
choose an index $i$ uniformly at random from $\{1, 2, \ldots, n\}$
choose two vertices in $V(v, i)$ uniformly at random
output the edge between those vertices

This procedure samples an edge of $H_n$ with some probability distribution. It is possible to show that every edge is sampled with the same probability (this is somewhat annoying to prove, but you could argue this by symmetry). Therefore, this procedure can be thought of as a method of uniformly sampling an edge from $H_n$. We will prove below that for any fixed $v$ and $i$, the probability that a two random vertices from $V(v, i)$ have different colors is always at most $\epsilon_n$. Then if we sample an edge using the above procedure, the conditional probability that the two vertices at the third step have two different colors (given the outcomes of the first two steps) will be at most $\epsilon_n$. We conclude that the unconditional probability is also at most $\epsilon_n$. But then we have that the probability that an edge has two different colors at its endpoints when the edge is chosen uniformly at random is at most $\epsilon_n$. Thus, no coloring can be an $\epsilon$-approximation for any $\epsilon > \epsilon_n$.

All that's left is to show that two random vertices from $V(v, i)$ have different colors with probability at most $\epsilon_n$. There are $n$ vertices in $V(v, i)$. If $a$ vertices are colored in one color, then there are $a(n-a)$ pairs with different colors. Thus, the probability of choosing two vertices with different colors is $a(n-a) / {n \choose 2}$. But the closer $a$ gets to $\frac{n}{2}$, the larger $a(n-a)$ gets. In particular, for $n$ even, $a(n-a)$ achieves a maximum value of $n^2/4 = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ at $a = \frac{n}{2}$ and for $n$ odd, $a(n-a)$ achieves a maximum value (for integer $a$) of $(n^2-1)/4 = \left(\frac{n-1}{2}\times\frac{n+1}{2}\right) = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ at $a = \frac{n\pm 1}{2}$. In all cases, the maximum value of $a(n-a)$ is $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$, so we can conclude as desired that two random vertices from $V(v, i)$ have different colors with probability at most $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2} = \epsilon_n$.


Fixed set of type constructors to simulate all intensional inductive families?

I am not 100% sure this is what you want, but assuming you are looking for a  type theory with a closed set of type constructors, which can model inductive families, then what you want are indexed containers or dependent polynomial functors. What you should look at first is:

Thorsten Altenkirch, Neil Ghani, Peter Hancock, Conor McBride and Peter Morris's 2014 draft Indexed Containers.

This paper is an expanded version of Altenkirch and Morris's 2009 LICS paper. It is all formalized in Agda, and gives a set of codes for defining all the strictly positive families. If you need it, it also gives an interpretation of them into W-types (and M-types for coinductive families). This is probably what you want to look at first.

It may also be worth looking at Containers: Constructing Strictly Positive Types by Michael Abbott, Thorsten Altenkirch and Neil Ghani for the non-dependent case.

Category theorists also invented this concept, which they dubbed dependent polynomial functors. The original paper, and some I found helpful for reading it are:

Wellfounded trees and dependent polynomial functors by Nicola Gambino and Martin Hyland. TYPES 2003.
Generalized Polynomial Functors Marcelo Fiore, ICALP 2012. There is a bit more logical intuition in this paper.
A foundation for GADTs and inductive families: dependent polynomial functor approach. Makoto Hamana and Marcelo Fiore, WGP 2011. This paper shows how to interpret indexed families as polynomial functors.

Now, you might also ask whether or not inductive families are "the morally correct" syntax for indexed containers. The answer is: probably not, but this is because containers/polynomials are too rich to have an obvious syntax.

Tamara von Glehn's PhD thesis, Polynomials and Models of Dependent Type Theory, builds models of dependent type theory out of polynomial functors. This implies that the correct syntax for datatypes in type theory is type theory itself, and I just don't know how to connect that to language design. Someone should give it a try, though!
Pierre Hyvernat has an LMCS 2014 paper, A Linear Category of Polynomial Functors, which uses a different notion of morphism to give polynomials a monoidal closed structure. So perhaps datatype declarations should be written in a linear type theory?


Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy?

Your problem is equivalent to testing, given $M$, whether $PER(M) > 0$.

Proof: Assume you are given $M$ and you want to decide whether $PER(M) > 0$. We construct $M'$ as follows:
\begin{bmatrix}
    1 & 0 & \dots & 0 \\
    0 & & & & \\
    \dots & & M & &\\
    0 & & & &
\end{bmatrix}
It is easy to see that $PER(M) = PER(M')$. Now, define $\hat{M'}$ to be $M'$ where we replace the $(0,0)$ entry of $M'$ by $-1$. By multilinearity, it follows that $PER(M) = PER(M') = -PER(\hat{M'})$. Thus $PER(M) > 0$ if and only if $PER(M') > PER(\hat{M'})$.

Now assume you are given $M$, $(i,j)$ and $a$ and define $\hat{M}$ as in your question, that is, by changing $M[i,j]$ to $a$. We have
\begin{align}
PER(M) > & PER(\hat{M}) \text{ iff} \\
\sum_{\sigma} \prod_{k=1}^n M[k,\sigma(k)] > &\sum_{\sigma} \prod_{k=1}^n \hat{M}[k,\sigma(k)] \text{ iff} \\
\sum_{\sigma, \sigma(i)=j} M[i,j] \prod_{k \neq i}^n M[k,\sigma(k)] > &\sum_{\sigma, \sigma(i)=j} a \prod_{k \neq i}^n M[k,\sigma(k)] \text{ iff}\\
(M[i,j]-a) \cdot \sum_{\sigma, \sigma(i)=j} \prod_{k \neq i}^n M[k,\sigma(k)] > & 0 \text{ iff}\\
(M[i,j]-a) \cdot PER(M') > 0
\end{align}

where $M'$ is the $(n-1) \times (n-1)$ matrix obtained from $M$ by removing line $i$ and column $j$. $\square$


How can I find tight asymptotic bounds for this half-history recurrence relation?

It is $n^{\Theta(\log n)}$, although I'm not sure exactly what the constant in the theta is. For the upper bound (the one you already have), note that, even without the $n^2$ term but with a base case of $1$ rather than $0$, this recurrence is dominated term-by-term by the recurrence
$$U(n)=nU(\frac{n}{2}).$$
For the lower bound, note that it dominates the recurrence
$$L(n)=\frac{n}{2}L(\frac{n}{4}).$$


Try these:
Quantum Error Correction by Todd Brun
Quantum Error Correction: An Introductory Guide by Joschka Roffe
For surface codes, Dan Browne's lecture notes might help.


Complexity of a parametrized min-cost flow problem

this is too long for a comment, but it's not an answer

One reformulation of your problem might prove to be useful in terms of finding related work.

Note that $f$ and $g$ essentially define probability distributions over the $s_i$ and $t_i$. If we treat the $c(e)$ as a "length", then the mincost flow is basically the earthmover distance between the two distributions $f$ and $g$.

Now your maximization over $f$ is really saying: find the farthest neighbor to $g$ lying in a box defined over the simplex.

Formulating the problem this way suggests that you want some kind of projection from $g$ to the box.


The problem of determining whether there is an equivalent CNF formula with at most a given number of literals is $\Pi_2^p$-complete.  The version minimizing the number of clauses is within a factor of $n$ of the formula size, where $n$ is the number of variables.  See section 6 of:

Christopher Umans, The Minimum Equivalent DNF Problem and Shortest Implicants, JCSS 63(4), 597–611, 2001.  doi:10.1006/jcss.2001.1775 (preprint)

A recent result shows that computing a particular lower bound for the size of the shortest equivalent CNF formula (measured by number of clauses, as you specify) is NP-complete.  This paper also states that your problem of minimizing the number of clauses is $\Pi^p_2$-complete as well, citing the Umans paper above, although why this follows is not immediately obvious to me.

Ondřej Čepek, Petr Kučera and Petr Savický, Boolean functions with a simple certificate for CNF complexity, DAM 160(4–5), 365–382, 2012.  doi:10.1016/j.dam.2011.05.013


Split or merge Binary Search Trees in O(log n)

Treaps support both operations in $O( \log n)$ time with high probability. The trick is to give the splitting element $0$ priority making it the root, splitting the trees, and then reverting its priority to the original value. Merging is done similarly.


Understanding the "gap theorem" in geometric spanners

Let's write $C = (1+2/w) wt(MST(S))$. The set $E$ satisfies the $w$-gap property and has $m$ edges. It can be partitioned into 2 sets:

One set is $E'$, which is a special subset of $E$. It is chosen such that we can easily prove that its weight is at most $C$.

The other set $E''$ (which is $E \setminus E'$) has $m/2$ edges; we only know that it satisfies the $w$-gap property. By the induction hypothesis, the weight of $E''$ is at most $C \log(m/2)$.

From this, it follows that the set $E$ has weight at most $C + C \log(m/2) = C \log m$.


Proof that the theory of rationals is convex

The key idea here is that for any conjunction of equations $F\equiv u_1=v_1\wedge\ldots\wedge u_k=v_k$, the set $S_F$ is convex in the geometric sense, i.e. for any two points $p,q\in S_F$, all points between $p$ and $q$ are also in $S_F$.

Now suppose that $F\Rightarrow G$, where $G$ is a disjunction of equations $x_1=y_1\vee\ldots\vee x_n=y_n$ (note that the variables $u_i,v_i,x_i,y_i$ are not assumed to be pairwise distinct). Without loss of generality, we may assume that $G$ is minimal in the sense that for each $i$, there is a point $p_i$ in $S_F$ which satisfies $x_i=y_i$, but not $x_j=y_j$ for any $j\neq i$. Any equation for which this is not the case can simply be removed from $G$ to obtain a smaller disjunction $G'$ which still satisfies $F\Rightarrow G'$. We will show that for such a minimal $G$, $n\le 1$.

Suppose not, i.e. $n>1$. Then the line segment $l$ between (say) $p_1$ and $p_2$ is contained in $S_F$ due to (geometric) convexity. Since $p_1$ and $p_2$ cannot be the same due to their definition, $l$ has infinitely many points. Therefore there must be some $i$ such that $l\cap S_{x_i=y_i}$ has infinitely many points, and so $l\subseteq S_{x_i=y_i}$; in particular, $p_1\in S_{x_i=y_i}$, implying $i=1$, and $p_2\in S_{x_i=y_i}$, implying $i=2$ for a contradiction.


Fast sparse boolean matrix product with possible preprocessing

I was reluctant to answer this, because the only theoretical result I know of along these lines has my name on the paper...

Theoretically, it is possible to preprocess a dense $n \times n$ Boolean matrix $A$ so that sparse matrix-vector multiplications with $A$ (over the semiring of OR and AND) can be done faster than the naive running time. Probably a significant amount of hacking would be needed to implement it in practice, but I do think it would fare well in practice for large enough $n$ and the right implementation.

(Note: this algorithm is only really useful for the case where one matrix is dense and the other is sparse. This case comes up a lot though, e.g., when computing transitive closure of a sparse graph, the transitive closure matrix will eventually get dense compared to the original adjacency matrix.)

The paper is

  Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: A New Combinatorial Approach for Sparse Graph Problems. ICALP (1) 2008: 108-120

and the relevant result from the paper is that for every $\varepsilon > 0$, there is an $O(n^{2+\varepsilon})$ time algorithm that, given any $n \times n$ 0-1 matrix $A$, the following operations are supported:

-- For any vector $v$ with only $t$ nonzeroes, $A v$ can be computed in $O(n(t/k + n/\ell)/\log n)$ time, where $\ell$, $k$ are free parameters satisfying ${\ell \choose k} \leq n^{\varepsilon}$. (One nice setting is $\ell=\log^c n$ and $k=\varepsilon(\log n)/\log \log n$, so that the running time is about $nt/\log n + n^2/\log^c n$ for any desired constant $c$.

-- Row and column updates to $A$ can be computed in $O(n^{1+\varepsilon})$ time.

We used this data structure to give faster theoretical algorithms for APSP in sparse unweighted graphs.


Consequences of nondeterminism speeding up deterministic computation

I found one related consequence.

Let's say $NEXP$ contains $DTIME(2^{O(t)})$, where $t = n^{\omega(1)}$.  It turns out this is just enough time to diagonalize against $P/poly$.  Specifically, build the following machine:

On input $x$ of length $n$, consider the $n^{th}$ Turing machine $M$.  For every possible advice string of length $t$ and every possible bitstring $b$ of length $n$, run $M$ on $b$ with advice $a$, and reject after $t$ steps if you haven't accepted yet.  Record your results in a table.  This procedure runs in $DTIME(2^{O(t)})$.

On input $0^n$, if at least half the advice strings cause $M$ to reject, then instead we define it to be correct for our algorithm to accept (otherwise, it is correct for our algorithm to reject).  Any advice strings that caused $M$ to get $0^n$ wrong (that is, at least half the advice strings) now get thrown out of the table.  We then repeat the process on input $0^{n-1}1$: if at least half the surviving advice strings cause $M$ to reject, then our algorithm will accept (and reject otherwise).  Continue like this for all inputs of length $n$ (although really, only $t$ of them are needed - after that many inputs, we have thrown out all possible advice strings).

Clearly this language can be decided in $DTIME(2^{O(t)})$, which we have assumed is in $NEXP$.  On the other hand, it cannot be in $P/Poly$: the set of length $n$ inputs diagonalizes against the prospect of $M_n$ being used to decide the language.

So we get $NEXP \not \subset P/poly$, which would be interesting.

I'm going to leave the question open in case someone comes up with something else.


What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

The number of satisfying assignments to a boolean formula equals the number of valid quantifications of the formula.  The inductive proof is quite elegant. So #P = #PSpace.


Simple spatial ordering or TSP algorithms?

A relatively simple way of implementing this would be to simply divide your map recursively into a quad-tree until every node of the quad-tree is either empty or contains at most one point.

Now simply apply your Z-ordering to the nodes of the quad-tree.


Is there any second-order logic finite satisfiability checker?

There are Nitpick and Nunchaku that are model finders for higher-order logic.
Nunchaku is more recent and can build models for axioms containing higher-order quantification. But, as the problem is generally undecidable, it may not find a (finite) model even if one exists.


Finding smallest context free grammar that generates a set of sets

Define a language $L$ to be nicely-ordered if $L \subseteq a^*b^*c^*d^*\cdots$, i.e., in every word of $L$, the letters appear solely in lexicographic order.

Conjecture: the optimum is always obtained by some nicely-ordered language, i.e., if $G$ is the smallest such grammar that generates $S$, then there exists a grammar $G'$ of the same size that also generates $S$ and such that $L(G')$ is nicely-ordered.

If this conjecture is true, then your problem reduces to a kind of grammar induction.  In particular, we are given a finite language, and the goal is to find the minimal context-free grammar that generates that language.

There are heuristics for this problem.  For instance, see the Sequitur, Lempel-Ziv-Welch, and byte pair encoding algorithms, as well as others.

In the general case (given an arbitrary finite language, find the smallest context-free language that generates it), the problem is NP-hard; I don't know if it remains NP-hard when restricted to nicely-ordered finite languages.  You could take a look at the standard proof of NP-hardness and see if it can be adjusted to apply to nicely-ordered languages.  See also Lower bounds on the size of CFGs for specific finite languages for other results in this space.

So, back to the conjecture.  One angle of attack on the problem might to try to prove or disprove this conjecture.  For instance, you might try writing a program to search for counterexamples (generate small random sets, look for the optimal grammar, check whether the conjecture holds, and repeat millions of times).  If the conjecture is true, it might make your problem much easier to solve.  If it's false, it might shed light on what makes the problem challenging.


Simplest Machine Model for a langauge $ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$

Just to refine Abuzer's answer, the language can also be recognized by a
Stateless 2-head 1-way DFA which is usually defined in this way [Ibarra et al., On stateless multihead automata: hierarchies and the emptiness problem (2010)]:

For an input string $w \in \Sigma$, machines work on a tape containing $\text{^} w \$$ and
start with all heads on the left end marker. At every step of the computation,
the symbols $a_1,..., a_k$ currently scanned by all $k$ heads are considered, any
corresponding transition $a_1,...,a_k \to d_1,...,d_k \in \delta, a_i \in \Sigma \cup \{\text{^}, \$\}$ is chosen, and each $i$-th heads is moved according to $d_i \in \{ Stay, Right \}$. If no such transition exists, the automaton rejects. If any of the heads falls off the tape, the automaton rejects as well.
If the transition instructs all heads to Stay, the automaton halts and accepts. The string is accepted if there exists a computation resulting in acceptance.

If $\Sigma = \{0,1,\#\}$, then your language is recognized by the following Stateless 2-head 1-way DFA:

   ^   ,  ^   -> S , R
   ^   ,{0,1} -> S , R
   ^   ,  #   -> R , R
   0   ,  0   -> R , R
   1   ,  1   -> R , R
   #   ,  #   -> R , R
{0,1,#},  $   -> S , S


Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?

I would say that a "simple" reduction to bipartite matching is highly unlikely. Firstly, it would give an algorithm for finding a perfect matching in a general graph using the Hungarian method. Hence, the reduction should contain all the complexity of the Edmond's blossom algorithm.
Secondly, it will give a compact LP for perfect matching polytope and hence the reduction should not be symmetric (which are ruled out by a result of Yannakakis) and inherently very complicated.


Explaining Applicative functor in categorical terms - monoidal functors

There are actually two uses of the word "strength" in play here.

A strong endofunctor $F : C \to C$ over a monoidal category $(C, \otimes, I)$ is one which comes with a natural transformation $\sigma : A \otimes F(B) \to F(A \otimes B)$, satisfying some coherence conditions with respect to the associator which I will gloss over. This condition is sometimes also pronounced "$F$ has a strength".
A lax monoidal functor $F : C \to D$ is a functor between two monoidal categories $(C, \otimes, I)$ and $(D, \oplus, J)$ with natural transformations $\phi : F(A) \oplus F(B) \to F(A \otimes B)$ and $i : J \to F(I)$, again satisfying a coherence condition with respect to the associators.
A strong monoidal functor $F : C \to D$ is one in which $\phi$ and $i$ are natural isomorphisms. That is, $F(A \otimes B) \simeq F(A) \oplus F(B)$, with $\phi$ and its inverse describing the isomorphism.

An applicative functor, in the sense of Haskell programs, is a lax monoidal endofunctor with a strength, with the monoidal structure in question being the Cartesian products. So this is why you get the paradoxical-sounding term "strong lax monoidal functor".

As an aside, in a Cartesian closed category, $F$ having a strength is equivalent to the existence of a natural transformation $\mathrm{map} : (A \Rightarrow B) \to (F(A) \Rightarrow F(B))$. That is, having a strength means that the functorial action is definable as a higher-order function in the programming language.

Finally, if you're interested in the type theory of Haskell-style applicative functors, I've just blogged about it.


3 dimensional matching shortest solution NP-hard?

Your problem is NP-complete, even in two dimensions.
There is a straightforward reduction from MINIMUM MAXIMAL MATCHING in bipartite graphs:

  MINIMUM MAXIMAL MATCHING in bipartite graphs
  INSTANCE: a bipartite graph $G=(V_1\cup V_2,E)$ with $E\subseteq V_1\times V_2$; an integer $k$
  QUESTION: Does $G$ possess a maximal matching $E'$ of cardinality at most $k$?

(A maximal matching is a subset $E'\subseteq E$ such that no two edges in $E'$ share a common endpoint, and such that every edge in $E-E'$ shares a common endpoint with some edge in $E'$.)

NP-hardness of MINIMUM MAXIMAL MATCHING in bipartite graphs has been shown in

  M. Yannakakis, F. Gavril
  Edge dominating sets in graphs.
  SIAM J. Appl. Math. 38, 364–372 (1980)
  https://epubs.siam.org/doi/10.1137/0138030

For the reduction, take the vertex set $V_1\cup V_2$ as ground set.
For every edge $\{u,v\}\in E$ with $u\in V_1$ and $v\in V_2$, create a corresponding vector $[u,v]$.
The equivalence to your problem is immediate.

(And if you insist on 3-dimensional vectors, then you should add a third component to these vectors and fill it with a lot of different values.)


Complexity of generically inverting a class of near linear monotonic functions

A simple variant of binary search takes $O(\log a(n))$ time assuming $a(n) = O(n)$ is monotonic.  To compute $f^{-1}(n)$, find $k$ s.t.
$$f(n-2^k) \le n \le f(n+2^k)$$
by trying $k = 0, 1, 2, \ldots$ until the bound holds.  This takes $O(\log a(n))$ steps and produces a window of size $O(a(n))$ which can be finished off with binary search.

Unfortunately, this is the best you can do without a stronger condition on $f(n)$.  Proof sketch: assume that after $O(1)$ queries we've reduced to an interval $[a,b]$ s.t.
$$\begin{aligned}
b-a &\ge c a(n) \\
f(b)-f(a) &= \Theta(a(n))
\end{aligned}$$
Then $f(n)$ within $[a,b]$ is an arbitrary monotonic function subject to the end constraints, and we can adversarily choose $f$ to make $\Theta(\log a(n))$ optimal.


Why have computer scientists chosen recursor instead of iterator in primitive recursion?

Iterators of any kind are just a form of recursion, i.e., a thing "using itself". For example, the basic equation governing the while loop is

  (while b do C)  =  (if b then (C; while b do C))

You may think I am doing something exotic, but as soon as you try to explain what recursion and iteration mean, you will end up writing such equations. For example, people tend to explain the while loop by saying things like "and so on" (imprecise) or "do C while b" (not explaining anything), or "keep doing" (circular explanation). The above equation tells you everything there is to know about the while loop. Similar arguments can be made about other forms of iteration.

The above equation is recursive, as the defined term appears on both sides. The general form is $$x = \phi(x),$$ which of course is just a general recursive definition of $x$. In this sense iteration is just a special form of recursion. So as far as theory is concerned, there is pratically no difference between recursion and iteration, except that the latter is a special case of the former. And both concepts are special cases of fixed point equations, a very important and general mathematical concept. This answers why "they chose recursor instead of iterator".

Your claim that iteration is more efficient than recursion is bogus. Modern programming languages are quite efficient at both of these tasks. In any case, it is not the job of humans to think about low-level details of execution of programs (maybe that was the case in the 1960's when the total amount of CPU power and memory on the planet was comparable to what kids carry in their pockets these days). We have better things to do as programmers, such as how to write programs most efficiently and how to make sure they are actually correct.


Uniformity vs. nonuniformity in algebraic complexity theory

Blum, Shub and Smale created their model based on known algebraic models of computations, to unify (as much as possible) complexity theory and numerical analysis (cf. [1]). They wanted to give solid theoretical foundations to numerical analysis, and they wanted uniformity since the algorithms used in real life are uniform. Also, their model is a generalization of the Turing Machine, and having uniformity implies that $\mathsf {(N)P}_{\mathbb Z_2}$ in their model equals precisely $\mathsf{(N)P}$ in the classical model.

Uniformity is much less central for lower-bound questions, or as Bürgisser states it [2]:

  Before, uniformity was not studied systematically in algebraic complexity, mainly because it is unknown how to exploit the uniformity condition for lower bound proofs.

Note that non-uniformity in the BSS model can be studied also. This is the viewpoint taken for instance by Poizat [3].

As a final note, BSS model and Valiant's model have different goals, and I am not sure that uniformity is "preferable", neither that non-uniformity is preferable. As a argument for this, both models are used today to study different questions.

References

[1] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. "Complexity and real computation: A manifesto." International Journal of Bifurcation and Chaos 6, no. 01 (1996): 3-26.

[2] Peter Bürgisser. Completeness and reduction in algebraic complexity theory. Vol. 7. Springer, 2000.

[3] Bruno Poizat. Les petits cailloux: une approche modèle-théorique de l'algorithmie. Aléas, 1995.


What would you advise someone who wants to do research as a hobby?

If you intend to publish it is essential that you learn how to write academic papers. Even if you can already write well, it still takes effort to get the style, focus, and, in particular, the quality right. Academic writing is highly compressed, rather formal, and precise. Theorems and so forth must be written in a particular way. Writing proofs is an art. There are even (implicit) standards for referencing the literature. Get any of these wrong and your article looks amateurish, which lends itself to rejection irrespective of the quality of the contents.

Here are some general tips that will help in this direction:

Use LaTeX. Papers, especially formal papers, written with Word look like crap.
Read a book on academic writing (and do the exercises). We use Academic Writing: A Handbook for International Students, mostly because our students are non-native English speakers.
Read Writing for Computer Science: The Art of Effective Communication  by Justin Zobel.
Learn how to write theorems and proofs correctly. One way of doing this is to find a high quality book in the area and mimic its style, even if it comes down to copying the text word for word to get the feel for how things are written. Then when you write your own results, consult the book regularly so that you can mimic the style. I know people who have used Relation Algebras by Games by Hisrch and Hodkinson as an exemplary model of mathematical writing. Undoubtedly there is such a text in your area.
Learn the conventions of the venues/communities where you plan to publish. Most papers have an abstract and introduction, body, discussion, related work, conclusions and future work sections, but different venues/communities may vary the ordering or have different expectations about how much attention goes into which part of the document. Issues such as how much background information is added to your paper depend very much on the expected audience, and it always pays to know the background of the average reader in the community. Critically reading many papers from the target community and trying to comprehend the stylistic expectations, is the only way to address this issue (without a supervisor in the area).


CNF encoding of set cover - NExpTime-completness

As I suspected in my question, they are useful results in the literature that can be exploited to characterize the complexity of the problem. There is a reduction from the dominant set problem for graphs succinctly defined using CNF formulas to the problem that I have described. The dominant set problem is known to be NExpTime complete [1] for graph succinctly defined using CNF formulas.
An instance of DominantSet^{2^n}{CNF} is defined by an CNF formula E(X,Y) over X={x_1,x_2,…,x_n} and Y={y1,y2,…,y_n}, two sets of n Boolean variables, and an integer K (encoded in binary) . The formula E(X,Y) succinctly defines the following graph: the set of vertices is the set of all Boolean valuations over n variables: 2^n, so any valuation v for the set of variables X, or for the set of variables Y, defines a vertex. Let v_1 and v_2 be two such valuations, then there is an edge={v_1,v_2} in the graph iff E(v_1,v_2) is true or E(v_2,v_1) is true.  An instance is positive, if there exists a set of K valuations V={v_1,v_2,…,v_K} such that \cup{v \in V} { v’ | E(v,v’) \lor E(v’,v) }=2^n (i.e. all vertices are adjacent to a vertex in V).
We can reduce in polynomial time this problem to our succinct set cover problem as follows:
Define (U) to be the empty CNF formula over the set of n variables U (which is equivalent to true) and so [A(U)]=2^n. Then define B(Z,U) to be the CNF equivalent to E(Z,U) \lor E(U,Z). This last formula has a size which is polynomial in the size of the CNF E that defines the graph. Keep K unchanged.
Then it is direct to see that the instance of succinct set cover is positive iff the DominantSet instance is positive. Indeed, there is a set V of K valuations for the variables in Z such that \bigcup_{v \in V} { v' | B(v,v') } covers 2^n iff V is a dominant set.
[1] Patrick Schafenacker. Problems on succinctly encoded graphs. PhD dissertation. Universität Ulm 2017.


Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

The first problem comes to my mind is the 2-path problem (or more generally k-path problem). Given $(s_1,t_1)$ and $(s_2,t_2)$, find two disjoint paths from $s_1$ to $t_1$ and $s_2$ to $t_2$, respectively. The problem is NPC for directed graphs but polynomial-time solvable for undirected graphs (although not trivial).


Public-key encryption without the assumption that $P \neq NP$

In a CPA game, a key pair $(sk,pk)$ is generated, and $pk$ is given to the adversary.
The adversary outputs a pair of messages $(m_0,m_1)$ in the message space, such that $|m_0|=|m_1|$. A random bit $b \in \{0,1\}$ is then generated, and $m_b$ is encrypted and returned as the cipher $c = E_{pk}(m_b ; r)$, where $r$ is the randomness used for encryption. The task of the adversary is to guess $b$ correctly.

Lemma. There do not exist $r_0$ and $r_1$ such that $c = E_{pk}(m_0 ; r_0)$ and $c = E_{pk}(m_1 ; r_1)$.

Proof. If such $r_0$ and $r_1$ exist, $c$ can be decrypted to both $m_0$ and $m_1$, which contradicts the uniqueness of decryption.

Note. In some texts, uniqueness of decryption is not required. It is only required that decryption is unique with overwhelming probability. In such cases, the above lemma must be changed accordingly.

Now, assume that $\mathsf{P = NP}$. The adversary can then find in polynomial time whether there exists an $r$ (i.e., an $\mathsf{NP}$-witness) such that $c = E_{pk}(m_0 ; r)$. If so, the adversary outputs $b=0$. Otherwise, he outputs $b=1$.

Therefore, if $\mathsf{P = NP}$, there exists a polynomial-time adversary which always succeeds in the CPA game, and no encryption scheme will be CPA-secure.


Natural candidate against the Isomorphism Conjecture?

I think the answer is yes, even today there is no known natural problem that is a candidate for violating the Isomorphism Conjecture.

The primary reason is that typically natural NP-complete problems are very easily seen to be paddable, which Berman and Hartmanis showed suffices to be isomorphic to SAT. For natural graph-related problems this typically involves adding extra vertices that are, e.g., disconnected from the graph, or connected in a very particular (but usually obvious) way. For the decision version of optimization problems, it typically involves adding new dummy variables with no constraints on them. And so on.


Careers for theoretical computer scientists

There are the obvious academic positions. Apart from that, many industrial research (or research-like) labs are very interested in hiring theoreticians who are comfortable applying theoretical foundations to solving problems as well as coming up with new theorems. Theoreticians also find positions (though may be not as many) in financial institutions as "quants".


Is it possible to find a non-cut vertex in O(|V|) time?

It's not possible for a deterministic algorithm: an adversary can always either fool the algorithm or make it look at $\Omega(n^2)$ entries of the adjacency lists.

Let $H$ be a disjoint union of two $n/4$-regular complete bipartite graphs. The adversary will remove a path of three vertices (not revealed to the algorithm) from each of the two components of $H$, and then replace these four removed edges by a different four edges that reconnect the two components, preserving $n/4$-regularity. It can do this in either of two ways:

Swapping the middle vertices of each path results in a graph $H'$ with no non-cut vertices.
Replacing one path by an edge connecting its endpoints, and splicing its former middle vertex into the interior of the other path, results in a graph $H''$ with one cut vertex. The cut vertex can be made to be either of the two former middle vertices.

However, by employing the strategy of making the removed path be in the last place the deterministic algorithm will look for it, it can force the algorithm to either not find the path (and not be able to distinguiish $H'$ from $H''$) or examine $\Omega(n^2)$ edges of the graph. In particular, as long as it is possible to answer a query (what is the $i$th entry of the adjacency list for vertex $v$) consistently with $H$, the adversary does so. Once the adversary is forced to choose the remaining path edges, it makes this choice arbitrarily, along with the choice of $H'$ or $H''$, and then answers the remaining queries according to the choice it made.

In order to force the adversary to choose between $H'$ or $H''$, the deterministic algorithm must see a set of edges that covers all two-edge paths on at least one of the two components on $H$. But each component of $H$ has $\Omega(n^2)$ disjoint two-edge paths, so the deterministic algorithm must see $\Omega(n^2)$ edges before it covers them all. And if it doesn't force the adversary to choose, then it is unable to distinguish graphs that have a cut vertex from those that don't, or to tell which vertex is the cut vertex.


Stochastic multi-armed bandit problem with transition costs

Yes, it's been studied -- for example you can look at this survey, which is from the econ community.

Also, [Auer '02] considered a similar problem, which he called "shifting bandits" where the learner has to compete with the optimal policy that's allowed to make $s$ shifts, in the adversarial setting -- see section 3 of this paper.


Guidelines to reduce general TSP to Triangle TSP

Here is a simple reduction for the TSP problem to the metric TSP problem:

For the given TSP instance with $n$ cities, let $D(i,j) \geq 0$ denote the distance between $i$ and $j$. Now let $M = \max_{i,j} D(i,j)$. Define the metric TSP instance by the distances $D'(i,j) := D(i,j)+M$. To see that this gives a metric TSP instance, let $i,j,k$ be arbitrary. Then $D'(i,j) + D'(j,k) = D(i,j) + D(j,k) + 2M \geq 2M \geq D(i,k) + M = D'(i,k)$. Since any tour uses exactly $n$ edges, the transformation adds exactly $nM$ to any tour, which shows the correctness of the reduction.

Remark: We can of course also allow for negative distances in the original TSP instance if you prefer by changing the reduction slightly.


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

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

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

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


This isn't a "nice" property, because whether it's true or false depends upon the encoding.

See David et al's Asymptotically almost all $\lambda$-terms are strongly normalizing, which proves what it says in the title. However, this paper also shows that the opposite holds for SKI-combinators (into which lambda-terms can be compositionally embedded).

In the lambda calculus, a reduction is the equivalent of a step of a Turing machine, and strong normalization is the property that every reduction sequence eventually reaches a normal form -- ie, no further reductions are possible. (Since a given lambda-term may have many valid reductions, strong normalization is a bit like saying a given nondeterministic Turing machine always halts.) So the fact that asymptotically almost all $\lambda$-terms are strongly normalizing means that with probability approaching 1, reducing a large lambda terms will always reach a normal form.

However, lambda-terms can be translated in a meaning-preserving way into a combinatory calculus such as the SKI combinators (and vice-versa), and in combinator calculi asymptotically all terms loop.


Shortest string in the intersection of a context-free language and a regular language

Thank you very much for posting this question!

I am very enthusiastic about these kinds of research problems.  Although I don't have a precise answer, I think that the following will be of help.

The Input Format Matters

A context-free language can be represented as CFG or a PDA.  Given that there is a polynomial blow-up in converting from one form to another, we have to be particular about whether $n$ denotes the number of non-terminals from the CFG or the number of states from the PDA.

Similarly, for regular languages, $n$ could denote the length of the regular expression or the number of states from the DFA.

Given that I am personally more comfortable with automata, I will assume that the inputs are given as automata and $n$ will denote the number of states from the larger (or largest) automaton.

A More General Problem

  Consider that we are given a PDA $P$ and $k$ DFA's $D_1, D_2, ..., D_k$.

  If we are promised that the intersection of these automata is non-empty (that is, $L(P) \cap \bigcap_{i\in [k]} L(D_i)$ is non-empty), then in terms of $n$ and $k$, what is the length of the shortest string in the intersection?

Now, you may ask, in the worst case, how large can this shortest string be?  It turns out that there is a constant $c \leq 1$ such that it is always possible to construct a PDA $P$ and DFA's $D_1, D_2, ..., D_k$ so that the shortest string in the intersection has length $2^{n^{c \cdot k}}$.

Note: You will see where $c$ comes from below, but you can probably make it close to $1$.  Maybe even $1 - \varepsilon$?

Construction

  Disclaimer: This is one possible construction although, it might not be the
  preferred construction nor is it necessarily optimal.  One interesting thing about the construction is that there is only one string in the intersection.  The
  construction is inspired by Cook (1971).

Let a number $n$ be given.  Consider an auxiliary pushdown automaton.  That is, a state machine with a stack and a bounded work tape.

If we have $k\log(n)$ bits on the work tape, then we can represent any integer from $1$ to $n^k$.  You can use this integer to represent a stack height.  Now, it is possible to design an auxiliary pushdown automaton with only $k\log(n)$ bits of memory on the tape that counts from $1$ to $2^{n^k}$ and then accepts.  It does this by enumerating through every single configuration of the stack of height at most $n^k$ where the current height is always stored in the $k\log(n)$ bits on the work tape.

  Please let me know if you need more detail in the preceding description.  Otherwise, we will continue our construction.

Now that we have an auxiliary pushdown automaton with only $k\log(n)$ bits on the work tape that runs for $2^{n^k}$ steps before accepting, we can construct $P$ along with $D_1, D_2, ..., D_k$.  This construction is inspired by Kozen (1977) and related works.

The idea is to build the PDA and DFA's to read in a string that encodes a computation of the auxiliary pushdown automaton.  The computation is accepting if and only if the PDA and DFA's all accept its encoding.

The computation is a sequence of configurations.  Each configuration can be encoded by a string so that all of the strings concatenated together make up the computations encoding.  Then, the DFA's each are assigned to a $\log(n)$ length chunk of the work tape and verify that the computation for their respective chunk of the work tape carries on correctly.  Finally, the PDA pushes, pops, and peeks, as is instructed by the configurations and simultaneously verifies that what is on the stack actually matches what the configuration says is on top of the stack.  They accept if both their respective verification is successful and the accepting configuration is reached.

Because the auxiliary pushdown automaton requires a computation of length $2^{n^k}$, the smallest string in the intersection has length at least $2^{n^k}$.  And, although it wasn't discussed in detail, the automata can be built to have polynomial in $n$ states.  The smaller the degree of the polynomial, the closer that $c$ can be made to 1.

Other Works

There is a great master's thesis by Thomas Ang on the length of the
shortest string in the intersection of regular languages.
Also, I made a small contribution to a paper with D. Chistikov, W.
Czerwinski, P. Hofman, and M. Pilipczuk where we show that the
shortest string accepted by a one counter automaton has length at most $c
   n^2$ for an appropriate constant $c$ (the previously known upper bound was $n^3$).

Dmitry and I have been discussing for a couple years about what the upper bound is for the shortest string accepted by a PDA.  You can get a lower bound of $2^n$ and an upper bound of $2^{n^2}$, but can you improve either of these bounds?  Even just a small improvement on the upper bound to $2^{\frac{n^2}{\log(n)}}$ would be a breakthrough.

Sorry for such a long reply and for excluding many details.  Feel free to shoot me an email if you would like to discuss offline.  Thank you and I hope you have a great week!


It can be proved that DSPACE$(f(\frac 32 n))\ne $ DSPACE$(f(n))$ if $f$ grows at least linearly by using a simple variant of the standard padding argument.
For a language $L$, let $L'=\{x0^{|x|/2}\mid x\in L\}$.

Claim. $L\in$DSPACE$(f(n))$ if and only if $L'\in$DSPACE$(f(\frac 23n))$ if $f(n)\ge \frac 32n$.

(My first answer had several incorrect statements, thanks to Emil for spotting this.)

I will first show how to use the claim to prove the hierarchy.
Since $f$ grows at least linearly, we have DSPACE$(2f(n))\subset$DSPACE$(f(2n))$.
Take a language $L\in$DSPACE$(f(2n))\setminus$ DSPACE$(f(n))$.
Using the claim, $L'\in$DSPACE$(f(\frac 43 n))=$ DSPACE$(f(n))$, where the last equality is by the indirect assumption.
But then $L\in$DSPACE$(f(\frac 32 n))=$ DSPACE$(f(n))$, where the last equality is again by the indirect assumption, giving a contradiction.

Proof of the claim.
If $L'\in$DSPACE$(f(\frac 23 n))$, then to prove $L\in$DSPACE$(f(n))$, we just need to write $|x|/2$ 0's to the end of the input $x$ and simulate the machine that accepted $L'$.
Since $f(n)\ge \frac 32 n$, this won't increase the space we use.
(In fact, knowing how many 0's to write is not clear at all if $f$ is small and we cannot increase the alphabet size - instead, we can use another tape and write on that everything that would come after the end of $x$.)

The other direction is just this simple by replacing the 0's with *'s, if we are allowed to write *'s. (See the issues with this in my comment to the question.)
If we are not allowed to write stars, then we slightly modify the definition of $L'$ as $L'=\{x10^{|x|/2}\mid x\in L\}$.
Now, instead of writing stars, we keep the original input $x10^{|x|/2}$ and work with that.
But whenever we reach a 1, we go right until we hit another 1 to check whether it was the end-of-word 1 or not.
If we've found another 1, we just go back to our 1.
If we haven't, we still go back, but we'll know that it should be treated as a star - if we were to write on it, then we also write a 10 after it to have a new end-of-current-word marker.
(In fact, there's also a small catch in this part if $f$ is small - how can we check if the input is of the form $x10^{|x|/2}$? Without destroying the input, I can only solve this by using multiple heads for small $f$.)


How do you initialize your seed in the preferential attachment model?

As you noted, any vertex with degree $0$ will have zero probability of being selected for attachment, and thus will always remain disconnected. Thus, only vertices of degree $1$ or higher matter in the initial network. In an experimental setting, it doesn't matter what connectivity you pick for your initial $m$ vertices (beyond the non-zero degree, constraint) since the network starts to forget its initial conditions pretty quickly (especially if all the initial vertices have the same degree). The two most popular implementations in practice are:

$1$ vertex connected to $m$ other vertices. This creates a distinguished vertex to start with (the high-degree vertex has a much higher chance of becoming a hub than the others), but otherwise the network is very typical.
$m + 1$ fully connected vertices. This creates a balance between any vertices being biased to become a hub, but has the unfortunate effect of artificially increasing the clustering coefficient of your network when it is young. This usually takes longer for the network to forget.

If you want more exact analytic results on the BA model, than you can't rely on the original heuristic arguments given in the Science paper, and I recommend looking at these lecture notes for a formal treatement. To prove things about the BA model, usually self-loops and multiple edges are allowed. In that case the network can be initialized as one vertex with $m$ self-loops.


The answer is yes, for the first game you list! This result was only established in 2019. Here is a link to the paper: Costa et al. 2019
Even more recently, some variants of the first game were proved to be PSPACE-complete. This result can be found here: Marcilon et al. 2019.


How is SDP an extension of spectral algorithms?

This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the leading eigenvector of a symmetric matrix". So spectral algorithms that use the latter as a starting point can be interpreted as SDP rounding algorithm.

To see that SDPs can compute leading eigenvectors, let's take $A$ to be a symmetric matrix, and recall that the leading eigenvectors of $A$ are $\arg \max\{v^\top A v: \|v\|_2 = 1\}$. You can write $v^\top Av$ as $\mathrm{tr}(Avv^\top)$, and observe that $vv^\top$ is a PSD matrix of trace $1$. Then it's easy to check that the leading eigenvalue of $A$ is $\lambda_{\max} = \max\{\mathrm{tr}(AX): \mathrm{tr}(X) = 1, X \succeq 0\}$, which is the solution to an SDP, and every eigenvector of an optimal solution $X$ to this SDP will be a leading eigenvector of $A$. Similar tricks work for the minimum eigenvalue.

Let me give an example from spectral graph theory. Suppose $L$ is the normalized Laplacian of a graph. Then its smallest non-trivial eigenvalue is

$\lambda_2(L) = \min\{v^\top L v: \|v\|_2 = 1, \sum_i{\sqrt{d_i} v_i} = 0\},$

where $d_i$ is the degree of vertex $i$. (This is because $(\sqrt{d_1}, \ldots, \sqrt{d_n})$ is the eigenvector of eigenvalue $0$). You can rewrite this as the SDP

$\min\{\mathrm{tr}(LX): \mathrm{tr}(X) = 1, \mathrm{tr}(DX) = 0, X \succeq 0\}$,

where $D$ is the matrix with entries $D_{ij} = \sqrt{d_id_j}$. Cheeger's inequalities relate $\lambda_2$ to the conductance of the graph, and the proof of the inequalities can be seen as a rounding algorithm for the SDP.


Attribute efficiently learning the relevant attributes of juntas with membership queries

Juntas can be tested in an attribute efficient manner given a membership query oracle: http://www.cs.cmu.edu/~eblais/papers/TestingJuntas.pdf Testing is an easier problem than learning, and the attribute efficient result is relatively recent. This might be a good place to start poking around.

Incidentally, the hard part about learning juntas is just identifying the set of $k$ relevant variables. Once that is done, you can learn the junta through exhaustive querying with $2^k$ queries (which might be "attribute efficient" since it is independent of $n$. In any case, you can't hope to do much better since the function can be arbitrary on these $k$ bits...). The testing algorithm linked to seems to work by trying to identify relevant variables, so it might solve your problem if you go through the details.


Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs?

The simplest node-weighted network design problem is the node-weighted Steiner tree problem. Klein and Ravi considered this problem and obtained an $O(\log k)$-approximation (here $k$ is the number of terminals). They also showed that the Set Cover problem reduces to it in an approximation preserving fashion and hence we should not expect any better approximation. It is not hard to show that iterated rounding is not helpful for the  Set Cover problem. Consider the following example. We have $n$ elements $\{e_1,\ldots,e_n\}$ and $n$ sets $S_1,\ldots,S_n$ where $S_i$ contains all elements except $e_i$. If you look at the natural LP with a variable $x_i$ for set $S_i$ then a basic feasible optimal solution is to set $x_i = 1/(n-1)$ for each $i$. From this one can see that iterated rounding in the plain vanilla fashion won't give a good bound. Note that the integrality gap of the LP is $O(\log n)$. This example for Set Cover can be extended to the node-weighted Steiner tree problem.


There is more in recognition that appears at the first sight. It is naturally generalized into recognizing all the substrings of a given string so that the output is a matrix A where matrix element A[i,j) corresponding to semiopen interval/segment [i,j) contains all the symbols derived for the substring cut by this interval. For example, given a grammar

S → S + M
   | M
M → M * T
   | T
T → number

and an input

6 + 7 * 8

we have

A[2,5) = {M,S}

i.e. the symbols M and S were derived for the substring 7 * 8 at the interval [2,5). It is essentially a table used by CYK parser. “Principles and Implementation of Deductive Parsing” by Shieber, Schabes, Pereira describes how Earley parsing fits into this framework as well.

Given a parsing matrix, one can recover a parse tree (and contrary to what wikipedia CYK page says, one doesn't have to store backpointers), but the takeout message here is that parsing matrix is more fundamental than the parse tree; in particular, it is well defined even for ambiguous derivation.


Is being fooled by limited independence preserved by products?

I have figured out that the answer to this question is yes.

The proof goes via sandwiching polynomials. It's a simple modification of a proof in [GMRTV12] $\S 4$. (Instead of keeping track of $\mathrm{L}_1$, we keep track of degree.)