Questions about P vs NP and geometric complexity theory Reading through various papers on geometric complexity theory (GCT), there is one thing, which pops up, while claimed in various places, that it is an approach to P vs NP, all the results seems to accumulate in conditional statements for VP vs VNP or NC vs #P. Are there any implications known, which connect the obstruction-based approach to VP vs VNP with P vs NP?
One more thing I keep wondering about is whether the attempts at separation through obstructions are strict, i.e. is there a class of obstructions, which exists if and only if $VP \neq VNP$?
Note: I use P vs NP here in the precise sense of Cook's hypothesis, not in the sense of P v NP in fields of certain characteristic as it sometimes appears in GCT papers.

The short answer is no these are not known, though they are certainly not out of the question. There are no direct implications known to P vs NP, and we do not even have a conjecture (let alone theorem) that such-and-such a representation is an obstruction iff $VP \neq VNP$.
One can start to get at an implication to ordinary P vs NP by trying to implement GCT in positive characteristic, using the polynomials from GCT I that more closely capture P/poly and NP. Since poly-size Boolean circuits are equivalent in power to poly-size algebraic circuits over a finite field, this would actually show NP not in P/poly. However, in positive characteristic both the geometry and the representation theory get harder (and it's not even clear if multiplicity is the right notion any more, because one is then dealing with modular representation theory, where representations need not be completely reducible).
Even in characteristic zero, we don't know the "general converse" about obstructions, namely, we don't know that $VP \neq VNP$ implies existence of multiplicity obstructions. But we do know that if $VNP \not\subseteq \overline{VP}$ then a separating module (equivalently, HWV obstruction, see Bürgisser-Ikenmeyer STOC '13, arXiv) must exist.


Online learning: Perceptron updates It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?

The perceptron algorithm as such is a simple case of Gradient Descent (which is widely used for convex optimization). It minimizes a convex function (here the sum of inner products of misclassified examples with the current hypothesis) by making a step in the direction of the gradient of the convex function. As such perceptron is not necessarily an online learning algorithm.

There is however work on primal dual interpretations of online learning algorithms that seem to be relevant to you:

http://ttic.uchicago.edu/~shai/papers/ShalevSi07_mlj.pdf


Complexity of Uniform Generation of Perfect Matchings Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (http://www.cc.gatech.edu/~vazirani/AppCount.pdf) talk about seeing problems related to relations in a "Existence, Construction, Uniform Generation and Counting" hierarchy.

In the case of the of M being a perfect matching in a bipartite graph G, we know that the problems of existence and construction are easy, and the counting problem is #P-Complete. The uniform generation problem is to generate a perfect matching in such a way that all perfect matching have the same probability

¿Is anything know about the problem of uniform generation of perfect matchings?

In [1], the author presents an acceptance/rejection algorithm for generating a uniform sample from the set of perfect matchings of a bipartite graph. While the samples are exactly uniform regardless of the structure of the graph, the run-time is only guaranteed to be polynomial if the graph has a particular structure -- essentially, if the degree of each node is $\gamma n \pm O(log (n))$ for some constant $\gamma$.

Huber, Mark. Exact sampling from perfect matchings of dense regular bipartite graphs. Algorithmica 44.3 (2006): 183-193.


Minimal context-free grammar for a regular language Are there any algorithms for solving exactly the following question?
Given a regular language L, represented as a finite automaton say, what is a CFG with minimal number of nonterminals that generates the language L?

Note that a CFG with $n$ non-terminals can generate a language consisting of a single (highly repetitive) word of length $2^n$, something that only a FSA with $2^n$ states will recognize. Hence in some case your minimal CFG will be much smaller than any FSA for $L$.

Actually, one can get much bigger reduction "factors". Take a deterministic Turing machine $M$ that happens to halt. One can define a CFG $G_M$ that recognizes exactly all words that are not (encodings of) the single run of $M$. This is a language $L$ consisting of all words except the single run, hence a regular language. The size of $G_M$ is polynomial in the size of $M$ while the size of a FSA for $L$ can be enormous (i.e., the single run can be very long, think Busy Beaver). Thus a regular language that requires an enormous FSA can be represented by a tiny grammar.

Your question evokes some notion of compression of regular languages. Indeed, the most popular schemes for compressing long words can be seen as some kind of CFGs,
see J. A. Storer and T. G. Szymanski,
Data compression via textual substitution.


Heap with $O(1)$ delete-key Fibonacci heaps have $O(1)$ insertion and $O(\log n)$ delete-min and delete-key (under amortized complexity).  Is there a heap data structure with $O(1)$ insertion and delete-key and $O(\log n)$ delete-min and find-min?  That is, can delete-key be reduced to $O(1)$ at the cost of more expensive other operations such as find-min, meld, and reduce-key?  Here delete-key means remove a particular key given a pointer to that key in the data structure.

This data structure would be necessary to fix my broken answer to this question: Nontrivial algorithm for computing a sliding window median.

To the best of my knowledge, no heap data structure matches your requirements. In terms of complexity, the best one is the Brodal queue, a heap data structure with worst case $O(1)$ time for insertion, find-minimum, meld (merge two queues) and decrease-key, and $O(\log~n)$ for delete-minimum and general deletion. However, this data structure is only of theoretical interest.

If you depart from the comparison-based model and adopt the RAM model where keys are regarded as binary strings, each one contained in one or more machine words, the best you can achieve for both insert and delete operations $\mathcal{O}(\sqrt{\log \log n}) $. See my answer to this question.


Why are sub-normalized states studied in quantum computation? By basic postulates of QM, any state of a system is described by a normalised density operator. Now i fail to see why people study sub-normalized states ( e.g.: In  generalised fidelity etc). I'd be glad to know any physical interpretations of the same.

It is often mathematically very convenient to work with sub-normalized states independently of the question whether they have a direct physical meaning.

However, you can always see them as states that are logically 'AND' with a certain event. For example, consider the c-q state

$\rho_{XB} = \sum_x |x\rangle\!\langle x|_X \otimes \rho_B^x$

where $\rho_B^x$ is sub-normalized so that the whole state is normalized. Then the trace of $\rho_B^x$ just gives the probability of finding the subsystem $B$ in the renormalized, conditional state $\rho_B^x / \text{tr}(\rho_B^x)$.

For example, the probability of measuring a certain event (POVM element) $E_B$ AND x is simply given by $\text{tr}(\rho_B^x E_B)$ and we never needed to renormalize the state to write this down.


For which k is PLANAR NAE k-SAT in P? The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth assignment of the variables such that each clause contains at least one true and at least one false literal.

The PLANAR NAE $k$-SAT problem is the restriction of NAE $k$-SAT to those instances where the incidence bipartite graph of $C$ and $X$ (i.e. the graph of parts $C$ and $X$ with an edge between $x\in X$ and $c\in C$ if and only if $x$ or $\overline{x}$ belongs to $c$), is planar.

It is known that NAE 3-SAT is NP-complete (Garey and Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness), but PLANAR NAE 3-SAT is in P (see Planar NAE3SAT is in P, B. Moret, ACM SIGACT News, Volume 19 Issue 2, Summer 1988 - unfortunately I do not have access to this paper).

Is PLANAR NAE $k$-SAT in P for some $k\geq 4$? Is there a value of $k$ for which it has been shown to be NP-complete?

PLANAR NAE $k$-SAT is in P for all values of $k$ .

Reason is that we can reduce PLANAR NAE $k$-SAT to PLANAR NAE $3$-SAT. Let $\phi$ be an instance of PLANAR NAE $k$-SAT, and suppose $\phi$ contains a clause $C$ with literals $\ell_1, \ell_2, \dots, \ell_k$. Introduce a new variable $v_C$, and replace $C$ with two NAE clauses $C_1$ and $C_2$. $C_1$ contains $3$ literals $\ell_1$, $\ell_2$, and $v_C$, while $C_2$ contains $k-1$ literals $\bar{v}_C, \ell_3, \ell_4, \dots, \ell_k$. It's easy to see that $C$ is satisfiable iff $C_1 \wedge C_2$ is and that the transformation preserves planarity. Now, we can repeatedly apply this procedure on the clauses to eventually obtain an instance $\phi'$ of NAE $3$-SAT as desired.


Simple question about decision problems (I am in the middle of my first theoretical cs course, so I apologize in advance for what is probably a stupid question.)

So, we say that some language L is in P, which means that a Turing machine can be constructed which outputs a 1 if x is in L and 0 otherwise; in addition, the machine runs in polynomial time. I understand this.

But many people say that there are certain problems in P which do not appear to me to be decision problems; for example, maximizing a function subject to linear constraints. What does it mean that "linear programming" is in P? Surely "find the maximal value" is not a decision problem?

You are right: formally P includes only decision problems. But many decision problems have corresponding optimization problems: find the size of the largest matching in a graph, find the length of the shortest path from s to t in a graph, etc.

Often, these can be reduced to decision problems by instead asking: "Does the graph have a matching using more than k edges?" or "Is there an s->t path of length less than k?"

Obviously, if you can solve the optimization problem, you can solve the decision problem. The converse is also often true, up to logarithmic factors. If you want to know the size of the largest matching in a graph, for example, you can make repeated calls to your algorithm for the decision problem "Does the graph have a matching using more than k edges?" and do binary search on the value "k". In this way, you will require at most log(m) calls, where m is the number of edges. For most problems there is an analogous reduction.


Source sending 0 transport units I have a network flow (with min and max capacities) where the only transport units flowing are within a cycle (of flow value 2). The source of the network does not send out any transport units into any direction and the transport units getting into the sink are all getting sent away directly, so 0 transport units "stay" there. Now my question is, is such a flow allowed as long as minimium neccesarry flow (given by min capacities) exists and the amount of incoming transport units is equal to the amount of outgoing transport units? Or is a flow network where the source doesn´t send out any transport units not permitted?

I look forward for any help.

You can make it valid depending on your definition of a valid network flow.
Let s and t be the source and sink, respectively. Depending on your problem you may no further restrictions of the network flow conservation of t and s. In most definitions there are even no further restrictions on that, as this would just complicate the definition (without helping much).

If you want to restrict such "superficial" network flows in your example, you may however further state that for each edge (u,v) with a flow (i.e. flow function f(u,v)>0) there must be a path from s to u where each edge on the path has a positive flow (i.e. f(e)>0).

You may further restrict the flow on s not to be negative and the flow on t not beeing positive, i.e. for sum for all u on f(s,u) must be positive and sum for all u on f(u,t) must be positive or 0.

This should then remodel a "more intuitive" network flow comparable with water flows :).

(Note that the restriction: the source must not send out any transport units does not help much to prevent such superficial flows as suggested in the question.)

However, typically one assumes that f(t,u)<=0 for all vertices u, i.e. the sink consumes everything which it retrieves.


3 dimensional matching shortest solution NP-hard? We have array of arbitrary number of elements - 3d vectors with positive integers components - for example

let a=[ [0,1,2], [1,0,2], [1,1,1], [1,2,0 ], [2,0,1 ], [2,1,0 ] ];

And we want to remove elements from that list, which have duplicate value on i-th index with other elements. This problem can have more than one solution:

solution with 3 elements: [0,1,2],[1,2,0],[2,0,1]
solution with 2 elements: [1,0,2],[2,1,0]

As you can see, the solution has this property that each solution element have unique value on i-th index (numbers on i-th position never duplicate) and if we add any other element from array a to that solution we loose this property.

Optimalization: from this wiki aricle I know that finding longest solution is NP-hard problem - but what about finding the shortest solution? Does exists algorithm which not use brute-force to find shortest solution (shortest 3-d matching)?

Here is interactive visualisation in javascript (works in browser, I put it also in wiki article). Here is implementation for find any solution in javascript.

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.)


Minimal set of Hyperrectangles covering an n-dimensional binary matrix with row permutations My input is a n-dimensional binary matrix.

My goal is to find the set of Hyperrectangles that covers every '1' at least once and covers not a single '0', which has minimal cardinality (the least amount of Hyperrectangles). The Hyperrectangles may overlap.

Before defining each next Hyperrectangle, I'm allowed to permute the 'rows' (along one or more dimensions) of the matrix.

An approximation algorithm will do, as long as it is always correct.

Is this problem reducible to some well-researched problem?

If "n-partitioned hypergraphs" are defined as "hypergraphs together with a partition of their vertices into n subsets such that each hyperedge has only one vertex from each of those subsets" then your problem can be reformulated as  n-clique hyperdge-cover for n-uniform

n-partitioned hypergraphs, and that reformulation preserves approximations and the parameter

(when your problem is parametrized by number of hyperrectangles).

In particular, your problem is NP-hard to approximate, even for n=2.

Those problems are equivalent to:

Find [the assignment of one positive integer to each '1' in the matrix] such that with

C being the largest of those positive integers, [for all elements H of {1,2,3,...,C-1,C}

and all '0's in the matrix, there is a coordinate such that no '1' [with the

same value for that coordinate as the '0'] was assigned H], which minimizes C.

Thus, your problem can be solved in

((minimum_number_of_hyperrectangles)^(number_of_'1's)) * poly(input_size)

time with an embarassingly parallel workload.

Aside from the reformulation and the equivalent problem I mentioned,

I don't know of any problems that your problem is reducible to for any reason

other than your problem being in NPO and the other problem being NPO-hard.


Is this variation of TQBF still PSPACE-complete? Deciding if a quantified boolean formula such as

$\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$

always evaluates to true is a classical PSPACE-complete problem. This can be viewed as a game between two players, with alternating moves. The first player decides the truth value of the odd-numbered variables and the second player decides the truth value of the even-numbered variables. The first player tries to make $\varphi$ false and the second player tries to make it true. Deciding who has a winning strategy is PSPACE-complete.

I am considering a similar problem with two players, one trying to make a boolean formula $\varphi$ true and the other trying to make it false. The difference is that on a move, a player can choose a variable and a truth value for it (for example, as the very first move, player one might decide to set $x_8$ to true and then in the next move, player two might decide to set $x_3$ to false). This means that the players can decide which of the variables (of those that have not yet been assigned a truth value) they want to assign a truth value, instead of having to play the game in the order $x_1 , \ldots , x_n$.

The problem is given a boolean formula $\varphi$  on $n$ variables to decide if player one (trying to make it false) or player two (trying to make it true) has a winning strategy. This problem is clearly still in PSPACE, since the game tree has linear depth.

Does it remain PSPACE complete?

It is an Unordered Constraint Satisfaction game and it is PSPACE-complete and it has been proved to be PSPACE-complete only recently;
a proof can be found in:

Lauri Ahlroth and Pekka Orponen, Unordered Constraint Satisfaction Games.
Lecture Notes in Computer Science Volume 7464, 2012, pp 64-75.

Abstract: We consider two-player constraint satisfaction games on systems of Boolean constraints, in which the players take turns in selecting one of the available variables and setting it to true or false, with the goal of maximising (for Player I) or minimising (for Player II) the number of satisfied constraints. Unlike in standard QBF-type variable assignment games, we impose no order in which the variables are to be played. This makes the game setup more natural, but also more challenging to control. We provide polynomial-time, constant-factor approximation strategies for Player I when the constraints are parity functions or threshold functions with a threshold that is small compared to the arity of the constraints. Also, we prove that the problem of determining if Player I can satisfy all constraints is PSPACE-complete even in this unordered setting, and when the constraints are disjunctions of at most 6 literals (an unordered-game analogue of 6-QBF).

From the content:

...
Our generic example of an unordered constraint satisfaction game is the Game on
Boolean Formulas (GBF). An instance of this game is given by a set of m non-constant
Boolean formulas $C = \{c_1,...,c_m\}$ over a common set of n variables $X = \{x_1,...,x_n\}$.
We refer to the formulas in $C$ as clauses even though we do not in general require them
to be disjunctions.
...
A game on $C$ proceeds so that on each turn the player to move selects one of the
previously nonselected variables and assigns a truth value to it. Player I starts, and
the game ends when all variables have been assigned a value. In the decision version
of GBF, the question is whether Player I has a comprehensive winning strategy, by
which she can make all clauses satisfied no matter what Player II does. In the positive
case we say that the instance is GBF-satisfiable. ..

...
Theorem 4: The problem of deciding GBF-satisfiability of a Boolean formula is PSPACE-complete.

EDIT: Daniel Grier's has found out that the result was also settled by Schaefer in the '70s, see his answer on this page for the reference (and upvote it :-). Schaefer proved that the game is still PSPACE-complete even if restricted to positive CNF formulas (i.e. propositional formulas in conjunctive normal form in which no negated variables occur) with at most 11 variables in each conjunction.


Kolmogorov complexity with weak description languages We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like $P$ might be the description of a Turing machine, or it could be a program in LISP or C). Even when we look at resource-bounded Kolmogorov complexity, we still look at Turing machines but with some bounds on their runtime or space usage. One of the consequences of this, is that the complexity of a string is undecidable. This seems like an awkward feature.

  What happens if we use non-Turing complete models of computation to define Kolmogorov complexity?

If we pick a restrictive enough model (say our model can only implement the identity), then the complexity of a string becomes decidable, although we also lose the invariance theorem. Is it possible to have a model strong enough to have complexity equal (upto a constant offset, or even a multiplicative factor) to the Turing-complete model, but weak enough to still allow the complexity of a string to be decidable? Is there a standard name for Kolmogorov complexity with non-Turing complete models of computation? Where could I read more about this?

Let's assume there exists some "decidable" complexity $D(s)$ differs from Kolmogorov complexity $K(s)$ by shift, by factor or, more generally, by any decidable monotonic unbounded numerical function $f(n)$ such that $K(s) > f(D(s))$.

As $D(s)$ is decidable, it is possible to choose (effectively) a sequence of strings $s_n$ such  that $f(D(s_n))> \mathrm{vff}(n)$ where $\mathrm{vff}$ is some "very very fast growing function" such as $\exp(\exp(\exp(n)))$.

Suppose that we have $K(s_n) > \mathrm{vff}(n)$, i.e. Kolmogorov complexity of string $s(n)$ grows fast with $n$. But index $n$ also identifies the string $s(n)$ and, therefore, may be treated as upper bound of $K(s_n)$ (with some const shift). Any number $n$ needs only $\log(n)$ bits to represent it, and this contradicts with fast growing of complexity of $K(s_n)$.

Thus for any decidable monotonic unbounded numerical function $f$, there exists strings $s$ such that $K(s) \not> f(D(s))$.


Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover In the paper The diameter of random regular graphs, Bollobás and Fernandez De La Vega give asymptotic lower and upper bounds on the diameter $d$ of random $r$-regular graphs. Roughly, the lower bound is $\Theta(log_{r-1}n)$, while the upper bound is $\Theta(log_{r-1}(nlogn))$, where $n$ is the number of nodes of the graph.

I would like to know (even just empirical) lower and upper bounds on the diameter of non-random $3$-regular graphs. More precisely, such non-random $3$-regular graphs in which I'm interested are those arising after reducing practical real world problem instances (which are known to be structured instead of random) to the $\sharp P$-complete problem $\sharp3$-regular Vertex Cover. In other words, suppose you have a real-world instance of a $NP$-complete problem, and suppose you want to count its solutions: following a chain of reductions, you come out with a $3$-regular graph $G$, whose number of vertex covers encodes the number of solutions of your initial instance.

  Questions

  How is $G$? Is it still structured, as the original instance? Or did it destroyed the initial structure?
  If $G$ is structured, which are the lower bound and the upper bound on its diameter? Do the bounds given by Bollobás and Fernandez De La Vega still hold? Or are such bounds completely different in the structured case?
  Does there exist any automated tool (along the lines of ToughSAT) that, given an instance of a $NP$-complete problem, produces the graph $G$?

A lower bound of approximately $\log_2 n$ still follows for arbitrary 3-regular graphs, based simply on the fact that there are at most $3\times 2^i$ different paths of length $i$ from any  given starting vertex and one needs the diameter to be large enough to give a different path to each of the $n$ vertices. The random graph example that you mention (or the example of a complete binary tree with some extra edges thrown in to make it 3-regular) shows that this is tight to within a constant factor, and I'm pretty sure the actual lower bound is really $(1+o(1))\log_2 n$.

As for an upper bound: there exist 3-regular graphs with diameter $\Omega(n)$, for instance the Möbius ladders.

If you want to know the diameters of graphs coming from specific hardness constructions, you'd have to look at the details of those constructions, but my guess is that in most such cases it would be straightforward to tack on either a large binary tree or a large ladder in order to make the diameter as small or as large as you want without much changing the hardness of the instance.


Separation of a preprocessed polyhedron and a plane I have serious trouble understanding one step in the paper of Dobkin and Kirkpatrick about the separation of polyhedra. I am trying to understand this version: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

It argues that after we know the best separation of $P_{i}$ and $S$, realized by $r_i$ and $s_i$, we can find the best separation of $P_{i-1}$ and $S$ in $O(1)$ steps. This is done in the following way. We take the plane parallel to $S$ through $r_i$ and cut $P_{i-1}$ into two parts with it. On one side, the closest point to $S$ is $r_i$ and on the other we have an ``elementary'' polyhedron that we can check in $O(1)$ time. My problem is - how do we find this elementary polyhedron? Note that the degree of $r_i$ in $P_{i-1}$ might be unbounded.

In the pdf to prove Thm 5.1 from page 9, they use Thm 3.1 from page 4, which makes the whole thing harder to follow.

Theorem 3.1 requires that the hierarchical representation of $P$ is compact.  One of the requirements for compactness is that the degree of $r_i$ in $P_{i-1}$ is bounded by a constant.  See the bottom of page 3.

The definition and construction of the Dobkin-Kirkpatrick hierarchy is much more explicit in their earlier papers (references [9,10,11] in the paper you're reading).  I strongly recommend reading them first.


Iteratively minimizing the function Consider the problem

\begin{equation}
\min_{x\in X, y \in Y} f(x,y)
\end{equation}

Can I solve the problem by iteratively solving the following two sub problems?

\begin{equation}
x_{k+1} = \arg\min_{x\in X} f(x,y_k)
\end{equation}

\begin{equation}
y_{k+1} = \arg\min_{ y \in Y} f(x_k,y)
\end{equation}

If yes, is there any books/papers talking about this kind of approach?

Thanks

This is a very popular heuristic method in machine learning, known as alternating minimization. You can easily find tons of papers using it. Often the setting in which it is used is when $f(x,y)$ is convex in $x$ and $y$ separately (so each minimization step can be done via some variant of gradient descent), but not jointly convex. In this case, as RB notes, it is not apriori clear that this method converges to an optimal solution at all. A classical paper by Csiszar and Tusnady gives a general "five point criterion" for convergance to the global optimum, and proves that it holds for $f$ equal to the KL-divergence. More recently, Jain, Nethrapalli and Singhavi, and Hardt have analyzed variants of this approach for the matrix completion problem.


Scope of active substitutions in the applied $\pi$-calculus As I have seen a few questions on calculi floating around, I figure this is the right place to ask. Suppose we have an extended process $P \equiv \nu \tilde{n}.\left( \{M/x\} \mid N \right)$ where $\{M/x\}$ denotes an active substitutions and $M$ and $N$ are some terms.

The question i ask myself is, whether we generally substitute $x$ for $M$ in $N$ if $x \in N$, or whether it depends on if $x \in \tilde{n}$ such that it is bound by $\nu \tilde{n}$. In other words, are processes computing in parallel in scope of active substitutions, and if yes, on what conditions?

Despite skimming through several papers, i did not manage to get a clear cut answer.

The key to understanding scope management in $\pi$-calculi is to look at the structural congruence $P \equiv Q$ and at the notions of free name $\newcommand{\FN}[1]{\text{fn}(#1)}\FN{P}$ and free variable $\newcommand{\FV}[1]{\text{fv}(#1)}\FV{P}$. The great novelty that distinguishes $\pi$-calculi from its predecessors is the ability to extrude scope. It is guided by the following law.

$$
   P \ |\ (\nu x)Q \ \equiv\ (\nu x)(P\ |\ Q) \qquad \text{if $x \notin \FN{P} \cup \FV{P}$}.
$$

This rule is also at the heart of the applied $\pi$-calculus, otherwise it would not be a $\pi$-calculus. In order to understand the scope of active substitution in the applied $\pi$-calculus, we need to understand the free names and variables of an active substitution. This is defined in Section 2.1 of "Mobile values, new names, and secure communication", the paper that introduces the applied $\pi$-calculus:

$\FV{\{M/x\}} = \FV{M} \cup \{x\}$.
$\FN{\{M/x\}} = \FN{M}$.

The full definition of structural congruence in applied $\pi$ is a bit more elaborate because the calculus parameterises the definition of structural congruence with application-specific equations that define cryptographic primitives, e.g. $\text{decode}_k(\text{encode}_k(msg)) \equiv msg$. In other words, the algebraic laws that give the (formal) cryptography are embedded in the structural congruence. In addition, active substitution itself has associated structural congruence laws:

$(\nu x)\{M/x\} \equiv 0$.
$\{M/x\} | P \equiv \{M/x\} | P\{M/x\}$.
$\{M/x\} \equiv \{N/x\}$ whenever the equation $M = N$ holds in the paramterisation.

None of these additional structural congruences does anything 'unusual' with extrusion, so, as Damiano says, whether $M$ substitutes for $x$ in $N$ has nothing to do with restrictions 'on the outside' in $(\nu \vec{n})(\{M/x\} | N)$, but only with $x$ occurring in $N$ or not.


An NP-complete variant of factoring. Arora and Barak's book presents factoring as the following problem:

$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$

They add, further in Chapter 2, that removing the fact that $p$ is prime makes this problem NP-complete, although this is not linked to the difficulty of factoring numbers.  It looks there can be a reduction from SUBSETSUM, but I got stuck finding it.  Any better luck around here?

EDIT March 1st: The bounty is for $NP$-completeness proof using deterministic Karp (or Cook) reduction.

This is not quite an answer, but it's close. The following is a proof that the problem is NP-hard under randomized reductions.

There's an obvious relation to subset sum which is: suppose you know the factors of $N$: $p_1$, $p_2$, $\ldots$, $p_k$. Now, you want to find a subset $S$ of $p_1$ $\ldots$ $p_k$ such that

$$\displaystyle \log L \leq \sum_{p_i \in S} \log p_i \leq \log U.$$

The problem with trying to use this idea to show the problem is NP-hard is that if you have a subset-sum problem with numbers $t_1$, $t_2$, $\ldots$, $t_k$,
you can't necessarily find primes in polynomial time such that $\log p_i \propto t_i$ (where by $\propto$, I mean approximately proportional to). This is a real problem because, since subset-sum is not strongly NP-complete, you need to find these $\log p_i$ for large integers $t_i$.

Now, suppose we require that all the integers $t_1$ $\ldots$ $t_k$ in a subset sum problem are between $x$ and $x(1+1/k)$, and that the sum is approximately $\frac{1}{2}\sum_i t_i$. The subset sum problem will still be NP-complete, and any solution will be the sum of $k/2$ integers. We can change the problem from integers to reals if we let $t'_i$ be between $t_i$ and $t_i+\frac{1}{10k}$, and instead of requiring the sum to be exactly $s$, we require it to be between $s$ and $s + \frac{1}{10}$. We only need to specify our numbers to around $4 \log k$ more bits of precision to do this. Thus, if we start with numbers with $B$ bits, and we can specify real numbers $\log p_i$ to approximately $B + 4 \log k$ bits of precision, we can carry out our reduction.

Now, from wikipedia (via Hsien-Chih's comment below), the number of primes between $T$ and $T+ T^{5/8}$ is $\theta(T^{5/8}/\log T)$, so if you just choose numbers randomly in that range, and test them for primality, with high probability get a prime in polynomial time.

Now, let's try the reduction. Let's say our $t_i$ are all $B$ bits long. If we take $T_i$ of length $3B$ bits, then we can find a prime $p_i$ near $T_i$ with $9/8B$ bits of precision. Thus, we can choose $T_i$ so that $\log T_i \propto t_i$ with precision $9/8\, B$ bits. This lets us find $p_i \approx T_i$ so that $\log p_i \propto t_i$ with precision $9/8\,B$ bits. If a subset of these primes multiplies to something close to the target value, a solution exists to the original subset sum problems. So we let $N=\Pi_i p_i$, choose $L$ and $U$ appropriately, and we have a randomized reduction from subset sum.


Is uniform RNC contained in polylog space? Log-space-uniform NC is contained in deterministic polylog space (sometimes written PolyL).  Is log-space-uniform RNC also in this class?  The standard randomized version of PolyL should be in PolyL, but I don't see that (uniform) RNC is in randomized-PolyL.

The difficulty I see is that in RNC, the circuit can "look at the random bits" as much as it wants; i.e., the random inputs can have arbitrary fanout.  But in the randomized version of PolyL, it's not like you get a tape of random bits you get to look at as much as you want; rather, you are only allowed to flip a coin at each time step.

Thanks!

Perhaps most people think that $\mathsf{RNC}\subseteq \mathsf{DSPACE(polylog)}$ (or even that $\mathsf{RNC}=\mathsf{NC}$), but I'm skeptical about this (see the second part of my answer, below). If $\mathsf{RNC}$ is indeed contained in $\mathsf{DSPACE(polylog)}$, then it is also contained in $\mathsf{NTIME(2^{polylog})}$ (more specifically, it is in $\mathsf{DTIME(2^{polylog})}$ by exhaustive search).

Valentine Kabanets explained to me the following (folklore) argument from his paper with Russell Impagliazzo that explains why $\mathsf{RNC} \subseteq \mathsf{NTIME(2^{polylog})}$ is unlikely.

Theorem: If $\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$, then either $\mathsf{NEXP}$ is not computable by Boolean circuits of size $o(2^n/n)$ (i.e. sub-maxsize by Shannon; irrelevant but see Lupanov for tightness), or Permanent is not computable by (division-free) arithmetic formulas over ${\mathbb Z}$ of quasipolynomial size.

Proof: assume $\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$. If Permanent has a quasipolynomial size formula, then we can guess and verify such a formula for Permanent using a quasipolynomial time polynomial identity tester by assumption. This places Permanent in $\mathsf{NTIME(2^{polylog})}$.

By Toda's theorem, $\Sigma_2$ is then also in $\mathsf{NTIME(2^{polylog})}$. By padding, the linear-exponential time version of $\Sigma_5$ is also in $\mathsf{NEXP}$. Hence the linear-exponential version of $\Sigma_5$ has a circuit of size $o(2^n/n)$ (i.e. submax). But, by a simple diagonalization argument, one can show that the linear-exponential version of $\Sigma_5$ requires max circuit size, which is a contradiction (by the way, this is a variant of a mid-level question for a graduate-level complexity course; okay, maybe proving that $\mathsf{EXPSPACE}$ requires max-size circuits is a simpler one). QED.

Now the unpopular direction.

We already know that randomness read many times can do something non-obvious. An interesting example can be found in "Making Nondeterminism Unambiguous" by Reinhardt and Allender (they state it in terms of non-uniformity but in principle it is about using read-many-times randomness). Another interesting example (less directly related) is "Randomness Buys Depth for Approximate Counting" by Emanuele Viola. I guess all I'm saying is that I wouldn't be surprised if the derandomization of $\mathsf{RNC}$ is not what most people would expect it to be.

(There are also a couple of other papers, like Noam Nisan's wonderful paper on read-once vs. read-many randomness, that show how to buy two-sided error with one-sided error.)

By the way, understanding how to construct PRGs fooling space-bounded models of computation with multiple accesses to their input (e.g. linear lengths Bps) is also very related to this question.

-- Periklis


Knapsack combining sum and product I cannot find references concerning the complexity of the variant of the knapsack problem (decision version) where one of the two conditions must be a product instead of a sum (0 not allowed).

A related question is this one: Combining subset sum and subset product problems .

It is well known that we can say that knapsack is the special case of subset sum (where each weight is equal to each profit and the bounds are the same) to satisfy the equality of subset sum with 2 inequalities. However, this is not possible here since there are 2 equalities to satisfy in the "subset sum product" problem and we have only 2 inequalities in the "knapsack sum product".

I don't know any reference, so just an extended comment:

If you allow a succinct representation for the input integers, i.e. you can represent the input integers as factors, then the "multiplicative" versions of Knapsack are NP-complete; indeed:

$\sum_{i=1}^n w_i x_i \leq W$ can be reduced to the equivalent $\prod_{i=1}^n 2^{w_i} x_i \leq 2^W$;

and $\sum_{i=1}^n v_i x_i$ maximization can be reduced to  $\prod_{i=1}^n 2^{v_i} x_i$ maximization.

I didn't think about it too much but the above reduction should work even if we require that in a mixed instance ( maximize sum of values under multiplicative weight constraint OR maximize product of values under addictive weight constraint ) all input values must be given with their prime factorization (building a direct reduction from exact cover).

Without a succinct representation the above reduction doesn't work because Knapsack is not strongly NPC.


Relation between tree-width and clique number Are there any nice graph classes for which the tree-width $tw(G)$ is upper-bounded by a function of the clique number $\omega(G)$, i.e. $tw(G)\leq f(\omega(G))$?

For example, it is a classic fact that for any chordal graph $G$, we have $tw(G)=\omega(G)-1$. So, classes related to chordal graphs could be good candidates.

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.


Complete problems or alternative definitions of the complexity class NP^GI? Definition: Let $GraphIso$ be the decision problem whose input is a pair of undirected graphs $(G_1, G_2)$ and the output is true if and only if $G_1$ and $G_2$ are isomorphic.

Definition: Define $\textbf{GI}$ to be the class of all decision problems $L$ for which there is a polynomial-time Turing reduction from $L$ to $GraphIso$.

Definition: Let $\textbf{NP}^{\textbf{GI}}$ be the class all decision problems which can be decided by a polynomial-time non-deterministic Turing machine with access to an oracle for a problem which is in $\textbf{GI}$.

My question is then: is this class known? Is it equivalent to a more standard complexity class? Is there any know complete problem for this class?

[Summarizing the answers in the comments by Ricky Demer and Josh Grochow.]

$\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}^{GraphIso}$, since these are nondeterministic poly-time Turing reductions, which can be simulated by the oracle machine (as detailed e.g. here).

The bounded-time halting problem for non-deterministic machines with a GraphIso oracle is complete for this class, by the usual proof.

Under standard derandomization assumptions (in particular, any that imply $\mathsf{AM} = \mathsf{NP}$), $\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}$, since under such assumption we have $\mathsf{GI} \subseteq \mathsf{NP} \cap \mathsf{coNP}$, and the latter is low for $\mathsf{NP}$.


What is the importance of linear languages? What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have been studied, or make them worthwhile to study?

The first obvious reason why linear languages were introduced is that mathematicians can hardly resist, facing a lateralized notion, to consider the symmetrical version as well. For instance, in algebra, you deal with left or right inverses, but also with inverses. In ring theory, you consider left or right ideals, but also ideals, etc.

Since left linear and right linear grammars define regular languages, studying linear grammars just came as a natural question to study in the early days of formal language theory. Furthermore, as you mentioned in your question, linear languages appeared to be a natural intermediate class between regular and context-free languages.

A nice characterization of linear languages was given by Arnold L. Rosenberg: A machine realization of the linear context-free languages, Information and Control 10 (1967) 175–188. The formulation below is Proposition V.6.5 in J. Berstel's book, Transduction and Context-free Languages, Teubner 1979.

A language $L$ of $A^*$ is linear if and only if there exists a rational subset $R$ of $A^* \times A^*$ such that
$$
L = \{ u\tilde v \mid (u, v) \in R \}
$$
where $\tilde v$ denotes the reversal of $v$. This result shows that, in a very loose sense, linear languages are a generalization of the language of palindromes.


Why does Fourier analysis of Boolean functions "work"? Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including property testing, pseudorandomness, communication complexity, and quantum computing.

While I got comfortable using Fourier analysis of Boolean functions as a very useful tool when I'm tackling a problem, and even though I have a pretty good hunch for which cases using Fourier analysis would probably yield some nice results; I have to admit that I'm not really sure what it is that makes this change of basis so useful.

Does anyone has an intuition as to why Fourier analysis is so fruitful in the study of TCS? Why so many seemingly hard problems get solved by writing the Fourier expansion and performing some manipulations?

Note: my main intuition thus far, meagre as it may be, is that we have a pretty good understanding of how polynomials behave, and that the Fourier transform is a natural way of looking at a function as a multilinear polynomial. But why specifically this base? what is so unique in the base of parities?

Here is my point of view, which I learned from Guy Kindler, though someone more experienced can probably give a better answer: Consider the linear space of functions $f: \{0,1\}^n\to\mathbb{R}$, and consider a linear operator of the form $\sigma_w$ (for $w\in\{0,1\}^n$), that maps a function $f(x)$ as above to the function $f(x+w)$. In many of the questions of TCS, there is an underlying need to analyze the effects that such operators have on certain functions.

Now, the point is that the Fourier basis is the basis that diagonalizes all those operators at the same time, which makes the analysis of those operators much simpler. More generally, the Fourier basis diagonalizes the convolution operator, which also underlies many of those questions. Thus, Fourier analysis is likely to be effective whenever one needs to analyze those operators.

By the way, Fourier analysis is just a special case of the representation theory of finite groups. This theory considers the more general space of functions $f:G\to \mathbb{C}$ where $G$ is a finite group, and operators of the form $\sigma_h$ (for $h\in G$) that map $f(x)$ to $f(x\cdot h)$, The theory then allows you to find a basis that makes the analysis of such operators easier - even though for general groups you don't get to actually diagonalize the operators.


How quickly can we decompose a number into a set of residues? Basically, if we are given a natural $x$, in binary, with $x < m_0 \cdot m_1 \cdot m_2 \cdot \dots \cdot m_n$, how quickly can we find $x \bmod m_0$, $x \bmod m_1$,..., and $x \bmod m_n$?  In other words, how quickly can we find $n$ residues in modular arithmetic?  Note that the residues needn't be primes.

I suppose that this is a fairly broad question, and I'm curious if there are special cases where we can find these residues much faster (in other words, if there are special values for the modulus that allow faster calculations).  My motivation is that I'm entertaining some ideas concerning integer multiplication.  Along these lines, I'd like to break apart numbers into smaller residues.  I'm interested in any results besides the trivial situation when some of the moduli are powers of 2.

If $m=2^k-t$ where $t$ is small, then you can reduce modulo $m$ faster.  In particular, $a \cdot 2^k + b \equiv at+b \pmod{m}$, so reducing an $\alpha k$-bit number modulo $m$ typically requires $\alpha$ multiplications by $t$ and $\alpha$ additions.  This can be significantly faster than the normal algorithms, if $t$ is small enough.

Something similar holds for $m=2^k+t$, too.

So, one plausible approach is to choose a modulus $m$ that is a product $m=m_1 m_2 \cdots m_n$ where each $m_i$ has the form $2^k \pm t$, where $k$ is the word size of your computer (e.g., $k=64$).


Expected travel time for regularly departing trains First a simple mathematical question: Suppose $n$ train lines service a train station. Each of the $i \in \{1, 2, ... n\}$ lines has trains departing every $x_{i}$ minutes and takes $y_{i}$ minutes to arrive at the destination. If the rider takes the first train on any line, what is the expected journey time (waiting + travel)?

Secondly: it may be the case that taking the first train on any line is not optimal. (For example, if one of the train lines takes $y_{j} = 30$ minutes to arrive at the next stop while others take 20 minutes, and the waiting times are such that it doesn't make sense to take the slower train anyway.) Unfortunately I'm at a total loss for how to compute this algorithmically. Mathematically it's minimizing the expectation over all subsets of $\{1, 2, ... n\}$, but I need to actually compute it so any tips would be helpful.

Here's a way you can find the optimal algorithm. Let's assume (for convenience) that all $x_i$ and $y_i$ are distinct.

First, we need to prove two theorems.

(1) If at time $t$, you would get on a train with travel time $y_i$, you would also get on any train with travel time less than $y_i$.

(2) If you would get on train $j$ at time $t_j$, you would also get on that train $j$ at any time $t \leq t_j$.

For (1), the proof is easy. For (2), the proof is based on the observation that the longer you wait, the higher the probability that any particular train shows up. So if there's some strategy of waiting for trains other than $j$ that has better performance than getting on a train $j$ with travel time $y_j$ at time $t_j$, that same strategy is going to give travel time $\leq y_j$ for all times $t > t_j$.

Now, if train $\alpha$ is the train with minimum $y_\alpha$, then you want to get on this train any time it arrives. Furthermore, if you've waited $x_\alpha - \epsilon$ time for sufficiently small $\epsilon$, your optimal strategy is to wait for train $\alpha$.

What we're going to do now is essentially continuous dynamic programming. If you've waited for time $t$, there are only $n$ possible optimal strategies. That is, get on any train with travel time $\leq y_i$. This optimal strategy changes at $n$ or fewer values of $t$. So, starting with time $x_\alpha$ and the strategy "wait for train $y_\alpha$", calculate the first time $t < x_\alpha$ where the strategy changes. You can do this by comparing $n$ possible strategies, each of which gives an expected travel time which is a function of $t$. Keep working to the left in this fashion, until you get to time $t= 0$.


Should reductions make us more or less optimistic for the tractability of a problem? It seems to me that most complexity theorists generally believe the following philosophical rule:

  If we can't figure out an efficient algorithm for problem $A$, and we can reduce problem $A$ to problem $B$, then there probably isn't an efficient algorithm for problem $B$, either.

This is why, for example, when a new problem is proved NP-Complete we simply file it away as "too hard" rather than getting excited about a new approach (problem $B$) that might finally show $P = NP$.

I was discussing this with a fellow grad student in another scientific field.  She found this idea hugely counterintuitive.  Her analogy:

  You're an explorer, searching for a bridge between the North American and Asian continents.  For many months you have tried and failed to find a land bridge from the mainland United States area to Asia.  Then you discover that the mainland US is connected by land to the Alaskan area.  You realize that a land bridge from Alaska to Asia would imply a land bridge from the mainland US to Asia, which you're pretty sure doesn't exist.  So you don't waste time exploring near Alaska; you just go home.

Our previous philosophical rule sounds pretty silly in this context.  I couldn't think of a good rebuttal!  So I'm turning it over to you guys: Why should we treat a reduction $A \to B$ as making problem $B$ harder rather than making problem $A$ easier?

What is missing from the analogy is some notion of the relative distances involved.  Let's replace Alaska in our analogy with the moon:

You're an explorer, searching for a bridge between the North American and Asian continents. For many months you have tried and failed to find a land bridge from the mainland United States area to Asia. Then you discover that the mainland US is connected by land to the moon.  You are already confident that the moon is a vast distance away from Asia, so you can now be confident that North America is also a vast distance away from Asia by the triangle inequality.


What requirements should a denotational semantics for a programming language satisfy to be correct? We have a programming language and its denotational semantic,
like Tony Hoare's CSP with its syntax and denotational semantic
e.g. stable failure and UTP.

We want to extend the language (its syntax and semantics) by
adding new operators to the language.
After given an informal definition for each new operator,
we want to provide a denotational semantic for the extended language.

We have been told that

the denotational semantic must be a domain,
the denotational semantic must distinguish what your language want to distinguish intuitively,
the denotational semantic must be consistent with its operational semantic or algebraic semantic.

What requirements should our denotational semantics for the extended language satisfy to be correct?
Are there any criteria to distinguish between correct and incorrect denotational semantic for a programming language?

What I am writing is essentially contained in babou's answer.
But I wanted to express it a bit differently
emphasizing the point of defining formal semantics.

A formal semantics is a mapping from one class of mathematical structures $P$
(e.g. programs in a programming language)
to another class of mathematical structure $S$ (e.g. domains):
$[[ \cdot]] : P \to S$.

Different conditions required from the mapping give different kinds of semantics.

What conditions should we require from the mapping?
That depends on what we want to do with the semantics.
The required denotational properties depend on
what your intention is in extending the language,
a formal semantics might be wrong or right depending on that intention.

Let's step back for a second and look more generally why we define formal semantics.

  The point of formal semantics is that
  we take the class of mathematical structures that we want to study and
  map it to another class of mathematical structures that we already know something about, and we use that knowledge to study the original class of structures.

If you don't know what denotational properties you require from your denotational semantics of your language and have no use for it,
what is the point of to providing a denotational semantics?
It will not add any confidence that your extended language will behave as you want.

On the other hand,
if you know how the denotational semantics should be
based on your intuitive informal semantics and your intention in extending the language,
then you can use that to formally check that
your programming language matches your intuitive semantics and
will work as you intended
(w.r.t. the requirements you had for your denotational semantics).


Algorithm for 'k'' most frequently occurring numbers I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: "Divide and conquer" data stream algorithms got me interested in it.

For example, suppose there are numbers: (4,3,5,1,6,2,4,3,3,8,9,1) and I query for the 3 most frequently occurring numbers (say), then I should get (3,4,1) as the answer.

I tried searching online, but couldn't find any place that gives an approach and says that that is the best. A trivial solution would be to use a heap or a balanced binary tree, but I think there is a better way and I wanted to know if it is documented somewhere.

Edit: I'm looking for an algorithm that always gives the correct answer as opposed to a appromixation algorithm (many of which pop up in search results) which rely on the distribution of data in some way or other

There's an extensive literature on this problem. Firstly, even for $k=1$, the problem is hard: as Alon, Matias and Szegedy show, you can't get a better than constant factor approximation to the frequency of the most popular element in $o(n)$ space, even if you're willing to be randomized.

However, if you're guaranteed that one element occurs strictly more than 50% of the time, then there's a simple trick that uses constant space and will find it (this is a popular google puzzle question). More generally, you can find elements that occur more than $n/k$ times using a generalization of this trick.

A definitive survey of what's known about the problem is the paper by Cormode and Hadjileftheriou from VLDB 2008. It covers the above methods and many of the latest methods. the general idea is that you can generate an approximate list of the top $k$ items (where approximate here means that you might get items whose counts are close to the counts of the top $k$ items).


Is graph isomorphism in UP ${\cap}$ coUP? Is graph isomorphism (the decision problem) in $\mathsf{UP}\cap \mathsf{coUP}$? Here $\mathsf{UP}$ is the class of decision problems accepted by an unambiguous Turing machine (see the complexity zoo).

Graph isomorphism is not known to be in $\mathsf{UP}$ nor known to be in $\mathsf{coUP}$.

For $\mathsf{UP}$: the natural nondeterministic algorithm - guess a map between the two graphs and check if it's an isomorphism - has either 0 witnesses (iff the graphs are not isomorphic) or $|\text{Aut}(G)|$ witnesses. Although most graphs have $|\text{Aut}(G)|=1$ (that is, if you pick a random graph on $n$ vertices, the probability that it has any nontrivial automorphsims goes to $0$ quite quickly with $n$), this is not enough to say that there is always at most one witness. This of course does not rule out some other algorithm that could show that graph isomorphism in $\mathsf{UP}$. (After all, it's possible that graph isomorphism is in $\mathsf{P} \subseteq \mathsf{UP}$.)

As for $\mathsf{coUP}$, as pointed out by Peter Shor, we don't even known if graph isomorphism is in $\mathsf{coNP}$, so we certainly don't know if it's in $\mathsf{coUP}$. (Under a plausible derandomization assumption it is in $\mathsf{coNP}$, but I don't know any natural assumption that puts it in either $\mathsf{UP}$ or $\mathsf{coUP}$.)


What's the point of stack judgement in CBPV? Call-by-push-value (CBPV) introduces two main families of types, values and computations, and their corresponding judgements. However, in some extensions/variants/adaptation of CBPV, there is a third judgement: stacks. What is the purpose of this judgement? Why it was not present in the original CBPV? What do we gain when we introduce them?

The kind of extensions I am talking about are for example Levy's CBPV with stacks, or Egger et al.'s Enriched Effect Calculus, or the calculus in Ahman et al.'s Dependent Types and Fibred Computational Effects.

The point of stacks is that they are in a sense the dual concept to computations.

A computation does not run in a vacuum. It is always "surrounded" by some sort of an environment, or evaluation context, telling us what the current "state of progress" is, or is recording "where we are, and where we're going". Often this sort of information has stack-like behavior, so we can call it simply a stack.

The duality between computations and stacks can be made quite precise and is useful in formalizing and discovering various mathematical aspects of computation. I am not sure where you're expecting a more technical answer, but that's the gist of it.


reference for lexicographic path ordering Can you recommend a good reference for reading about lexicographic/recursive path orderings?

I'm currently reading about lpo's in Chapter 2 of the Handbook of Automated Reasoning, 'Resolution Theorem Proving' by Bachmair and Ganzinger, but the presentation is really terse. I would ideally like a more tutorial-like introduction w/ examples.

Some information at the right level of abstraction can be found in:

Nachum Dershowitz's A Taste of Rewrite Systems

If you are near a library or bookshop, this book has even more details:

Baader and Nipkov's Term Rewriting and All That


What is the expected depth of a randomly generated tree? I thought about this problem a long time ago, but have no ideas about it.

The generating algorithm is as follows. We assume there are $n$ discrete nodes numbered from $0$ to $n - 1$. Then for each $i$ in $\{1, \dotsc, n - 1\}$, we make the $i$th node's parent in the tree be a random node in $\{0, \dotsc, i - 1\}$. Iterate through each $i$ in order so that the result is a random tree with root node $0$. (Perhaps this is not random enough but this doesn't matter.)

What is the expected depth of this tree?

I think there is a concentration result about $e \log n$, but I haven't filled in the details yet.

We can get an upper bound for the probability that node $n$ has $d$ ancestors not including $0$. For each possible complete chain of $d$ nonzero ancestors $(a_1,a_2,...,a_d)$, the probability of that chain is $(\frac{1}{a_1})(\frac{1}{a_2})\cdots (\frac{1}{a_d}) \times \frac{1}{n}$. This corresponds to $\frac{1}{n}$ times a term of $(1+\frac{1}{2} + \frac{1}{3}+ \cdots \frac{1}{n-1})^d$ where the terms are ordered. So, an upper bound for this probability is $\frac{1}{n (d!)} H_{n-1}^d$ where $H_{n-1}$ is the $n-1$st harmonic number $1 + \frac{1}{2} + ... + \frac{1}{n-1}$. $H_{n-1} \approx \log (n-1) + \gamma$. For fixed $d$ and $n \to \infty$, the probability that node $n$ is at depth $d+1$ is at most

$$\frac{(\log n)^d}{n (d!)} \left(1+o(1)\right)$$

By Stirling's approximation we can estimate this as

$$ \frac{1}{n\sqrt{2\pi d}} \left( \frac{e \log n}{d} \right)^d. $$

For large $d$, anything much larger than $e \log n$, the base of the exponential is small, so this bound is small, and we can use the union bound to say that the probability that there is at least one node with $d$ nonzero ancestors is small.

See

Luc Devroye, Omar Fawzi, Nicolas Fraiman. "Depth properties of scaled attachment random recursive trees."

B. Pittel. Note on the heights of random recursive trees and random m-ary search trees.
Random Structures and Algorithms, 5:337–348, 1994.

The former claims the latter showed the the maximum depth is $(e+o(1))\log n$ with high probability, and offers another proof.


How can one ACTUALLY minimize a regular expression? Minimizing regular expressions (in terms of number of symbols) is PSPACE-complete

(for example as discussed here: minimizing size of regular expression).

But how do you actually do that (i.e., what does an algorithm

for minimizing regular expressions in PSPACE look like)?

There are many results showing that it's hard in different contexts (such as when

an equivalent DFA is available), but I found none showing how it's actually done.

Probably it's so easy that I'm the only one not getting it. :-)

Finding the answer to your question is not overly difficult, if one is used to proving PSPACE upper bounds. But I think one cannot find an answer to your question in the literature, so here it is:

Given a regular expression r of alphabetic width n, i.e. with n alphabetic letters, you can enumerate all regular expressions of alphabetic width 1,2,3, one by one (see the paper by Gruber et al. 2012), and test for each such candidate expression c whether L(c) = L(r). The first expression where the test succeeds is clearly of minimum alphabetic width.

Apart from the test for language equivalence, this can be implemented using "only" linear space (and using exponential time).

The regular expression equivalence test can be done by converting r and c each to a nondeterministic finite automaton, and check if these automata are equivalent. The latter can be done in PSPACE as follows (this algorithm is mentioned in the paper by Bonchi and Pous 2013): For each word $w$ of length at most $2^n$, test whether $w \in L(r)$ if and only if $w \in L(s)$. If all these $2^{n+1}-1$ tests are successful, then $L(r)=L(s)$.

Notes

The paper by Gruber et al. (2012) also covers the computation of the number of regular languages whose minimal regular expression is of size n for small values of n. This actually uses an implementation of regular expression minimization. The test for language equivalence is not done in polynomial space as described above, but by computing the minimal DFA. This requires exponential space in the worst case. But there are more practical ways (all practical approaches seem to use exponential space) for testing the equivalence of NFAs, see
http://languageinclusion.org/

References

Hermann Gruber, Jonathan Lee, Jeffrey Shallit: Enumerating regular expressions and their languages, arXiv:1204.4982 [cs.FL]
Filippo Bonchi, Damien Pous: Checking NFA equivalence with bisimulations up to congruence. POPL 2013.


Graph Isomorphism Problem I am doing some literature review on Graph isomorphism problem. Most of papers which I am reading are written by E.M Luks and Laszlo Babai.
These papers uses the high level knowledge of group theory and complexity theory.
As I am new to this field many of the things are not clear to me.

Can some one suggest me a way to learn ideas and techniques which are presented in these papers so that I can come up with some other ideas.

Thank you so much

I highly recommend Paolo Codenotti's thesis for the group-theoretic aspects, and the book The Graph Isomorphism Problem: Its Structural Complexity by Johannes Köbler, Uwe Schöning, and Jacobo Torán for the complexity aspects.


Find the right/best track combination for a given distance, using a genetic algorithm or ?. I have a list of tracks (model railroad tracks) with different length, example: TrackA on 3.0cm, TrackB on 5.0cm, TrackC on 6.5cm, TrackD on 10.5cm

Then I want to find out of what kind of track I should put together to get from point A to point B with a given distance and a margin. And I should also be able to a prioritizes the use of track type.

Example; Distance from point A to B is 1.7m, and I have lot of TrackC and few of TrackB. And I will allow a margin on +/- 0.5cm to the distance.

What kind of tracks should I use, and how many of each track, and how many combination do I have, sorted after the track where I have most of.

I have Google after some C# help using genetic algorithm, but I am lost in, how I can implement this in a good method.

Or just a mathematical method, that can solve my problem..

Please help..

You could easily formulate this as a integer linear programming (ILP) problem. This is a linear programming problem where the solutions are constrained to be integers. The problem is NP-hard as indicated in other answers, but software does exist to address this sort of problem.

Let $L$ be the ultimate length you are aiming for, $a$ be the number of
Track A used, $b$ be the number of Track B used, and so forth. Finally,
let $A$, $B$, $C$, and $D$ be the amount of each kind of track you have.

($a,b,c,d$ are variables; the rest are constants.)

Then the integer linear programming problem is formulated as:

$L - 0.5 \le 3.0 a + 5.0 b + 6.5 c + 10.5 d \le L + 0.5$
$0 \le a \le A$
$0 \le b \le B$
$0 \le c \le C$
$0 \le d \le D$
$a,b,c,d$ are integers
minimise $a+b+c+d$

The condition $a+b+c+d$ can be changed to what you want to minimise/maximise to suit your needs so long as
it is linear in the variables $a,b,c,d$. The could be something capturing the costs of the various Tracks. All of the other ingredients can be changed in an obvious way, for different track lengths, different tolerance level, and so forth, so long as they are constants when you submit your question to an ILP system.

Plenty of software packages exist to solve such problems; many are listed on the page linked to above.


Algebra oriented branch of theoretical computer science I have a very strong base in algebra, namely

commutative algebra,
homological algebra,
field theory,
category theory,

and I am currently learning algebraic geometry.

I am a math major with an inclination to switch to theoretical computer science. Keeping the above mentioned fields in mind, which field would be the most appropriate field in theoretical computer science to which to switch? That is, in which field can the theory and mathematical maturity obtained by pursuing the above fields be used to one's advantage?

There have been recent developments in dependent type theory which relate type systems to homotopy types.

This is now a relatively small field, but there is a lot of exciting work being done right now, and potentially a lot of low hanging fruit, most notably in porting results from algebraic topology and homological algebra and formalizing the notion of higher inductive types.


bounded outdegree bipartite spanners Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties :

$G'$ is connected. (property $p _1$: connected)
The vertices of $G'$ are divided into two disjoint subsets $S$ and $T$ ($S \cup T = V$).
No pair of nodes in $S$ are neighbors in $G'$. The same applies for $T$. (property $p _2$ bipartite). [Note that they can be neighbors in $G$ - but we then eliminate the edge between them when constructing $G'$]
The nodes in $S$ are degree limited. (property $p _3$ call it outdegree bounded)

The problem seems to be NP-Complete, but I found no solution so far.

Here are some of my observations:

essentially, we are looking for a connected subgraph $G'$ that contains a dominating set $S$ such that every node in $S$ in $G'$ is degree limited to $k$. [and we need to know $S$ too]. [and no pair of nodes in $S$ are neighbors in $G'$]
$G'$ with $p _1$ and $p _2$ is easily obtained with a rooted spanning tree algorithm + 2-coloring of tree.
$G'$ with $p _1$ and $p _3$ is easily obtained with a rooted spanning tree algorithm + every node in the tree points to its parent.
$G'$ with $p_2$ and $p_3$ is trivial, (note that we are looking for any subgraph with the required properties!)
A close problem to this is the bounded degree spanning tree problem [proven to be NP-Complete with a reduction to Hamiltonian path]
I see the problem sometimes as a set cover problem. Find any set cover $C$ + restrict the size of each set in $C$ to at most $k$ while keeping the coverage  and connectivity properties. [I did not know how to use this observation though]

PS:  I am trying to forget it but it always come back to my mind

Perhaps this is a possible weird reduction from 3SAT. The idea is to use the set $S$ with restricted degree to simulate a true/false assignment to the variables using their odd/even distance from the clauses that contain them.

Given a 3CNF formula with $n$ variables; let $c$ be the maximum among the number of occurrences of the variables in the clauses, and let $k = c+2$.

Build $G$ in the following way:

add a source node $s^T$ linked with $k+1$ nodes of degree 1 (a "fan");
for every variable $x_i$ add a triangle made of three nodes $\{x_i^S,x_i^+,x_i^-\}$ and edges $(x_i^S,x_i^+)$ (left side), $(x_i^S,x_i^-)$ (base), $(x_i^+,x_i^-)$ (right side);
add edges from $s^T$ to every $x_i^S$;
add $k-2$ fan nodes to $x_i^S$;
for every clause $C_j$ add a node $C_j^T$ linked with $k+1$ fan nodes of degree 1;
if positive variable $x_k \in C_j$ then add a direct link from $C_j^T$ to $x_k^-$; if negative variable $\bar{x}_k \in C_j$ then add a link from $C^T_j$ to $x_k^-$ with an intermediate node $z_{jk}$

The resulting graph $G$ has a connected, bipartite subgraph ($S\cup T=V$) in which the nodes of only one of the two set (suppose $S$) has max dregree $k$ if and only if the original 3CNF formula is satisfiable.

First of all the fan of the source node $s^T$ forces it to be in the unrestricted set $T$; and the fan of every clause $C_j^T$ forces it to be in $T$, too. Furthermore all nodes $x_i^S$ connected to $s^T$ are forced in the set $S$.

Now, for every variable, only one among $x_i^+, x_i^-$ can be put in $T$ (traverse the base of the triangle or pass through its vertice) because $x_i^S$ is in $S$ and its $k-2$ fan nodes must be connected, so we must drop edge $(x_i^S,x_i^+)$ or edge $(x_i^S,x_i^-)$). Suppose we choose $x_i^+$, and drop the edge $(x_i^S,x_i^-)$; hence $x_i^-$ falls in $S$, and we can use the edges from it
to safely connect (satisfy) all the clauses (all because $k=c+2$) that contain $x_i$ and are directly connected to $x_i^-$, but not the clauses that are connected through $z_{ij}$ (which must be in $T$) because in that case $C_j^T$ would fall in $S$. Similarly, if we choose to put $x_i^-$ in $T$ then we can conect all the clauses that contain $\bar{x}_i$ (through $z_{ij}$ which now is in $S$).

At the end the graph $G$ is connected only if every clause contains at least one variable made true by the assignment.


What is a canonical term of $\text{Id}_A(x,y)$ if $x$ is not jugdmentally identical to $y$? In the context of constructive type theory, a term inhabiting some type is said to be in canonical form if it is explicitly built up using the constructors of that type.

Particularly, the only constructor of the identity type of $A$ is $\text{refl }:  \Pi x. \text{id}_A \text{ } x \text{ }  x$, so

  Question 1: What is a canonical term of $\text{Id}_A(x,y)$  if $x$ is not jugdmentally identical to $y$?

Apparently there cannot be such a canonical term, for neither $\text{refl } x$ nor $\text{refl } y$ type check.
Does this mean that the identity type of $A$ does not have a canonical form in general? That is, that $\text{Id}_A(x,y)$ only has a canonical form in the particular case where $x$ is judgmentally equal to $y$?

But in this case how propositional equality differs in practice from judgmental equality then – except for the fact that the former occurs as a type and the other as a judgment?

  Question 2: What is a closed term of $\text{Id}_A(x,y)$? Are there two closed terms $p, q$ of $\text{Id}_A(x,y)$ such that $p$ and $q$ are not judgmental equal?

Yes, in general $\mathrm{Id}_{A}(x, y)$ will not have a canonical form. Consider the case when $x$ and $y$ are distinct free variables -- obviously you can postulate that $x$ and $y$ are equal, but you can't provide a proof of it.
Even more simply, consider the empty type $0$. It has no canonical forms at all, but there's nothing stopping you from assuming that a variable has type $0$.

For standard type theory, it is provably the case that if you have a closed term $t$ of type $\mathrm{Id}_{A}(x, y)$, then $x$ and $y$ are definitionally equal.
Since the language is normalizing and $t$ is well-typed in the empty context, then we know that $t$ will evaluate to $\mathrm{refl}(z)$ for some $z$, and then by inversion we will be able to establish that  $z \equiv x \equiv y$ judgementally.


Sort with random deviations I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a sequence than a smaller element is proportional to the ratio of these elements' values.

For instance if we have a sorted sequence of elements: 1, 2, 3, then I'd like this algorithm to generate a permutation of this sequence in such a way that the probability of finding element 3 earlier in a sequence than the element 1 is 3 times smaller than the other way around. This property should hold for all pairs of the elements.

Is this possible?  If so, can you suggest an algorithm for this?

Here is an algorithm:
Choose a number from the sequence with probabilities proportional to their values, remove it and push_front it to the output sequence. Repeat the steps.

With your 1 2 3 example, consider the probability that 1 comes earlier than 3 ( so 1 is removed later than 3 in the input sequence ). Obviously the time 2 is removed is not relevant. So the probability is 1/(1+3)=1/4.

The algorithm can be implemented in time O(NlogN)


Lower bounds on simple hash table operations? There are a variety of hash tables that support worst-case O(1)-time lookups and deletions and expected O(1)-time lookups. Is there a known lower-bound on hashing that says that there cannot be a hash table with (possibly amortized) worst-case O(1) lookups, insertions, and deletions?

Thanks!

The best known lower bounds are discussed in Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems", and none preclude deterministic amortized constant-time operations.


How many edges are cut in a balanced partition of a graph? Consider a graph on n nodes and e edges that is partitioned into k "balanced" subgraphs in the sense that each block has an equal number of nodes and the number of cut edges is minimized. Is there a formula for the number of cut edges in this situation?

Even in the current updated version of the question, it still remains ill defined. There many different ways by which you can partition a graph into symmetric (or balanced if you like) clusters. One question that you might have in mind but have problem expressing is the minimum multisection (or partition): Given a graph $G$ find a symmetric partition $P$ of its vertices such that it minimizes the edges between different clusters.

In which case the answer is that the problem is NP-hard [1] and moreover it is NP-hard to approximate within a constant factor [2].

[1] L. Hyafil and R. L. Rivest. Graph partitioning and constructing optimal decision trees are polynomial complete problems. 1973.

[2] K. Andreev and H. Racke. Balanced graph partitioning. 2004.


Applications of algebraic geometry in type theory/programming language theory Lately, I have become interested in algebraic geometry and have started reading on it. I still know very little about this field, but I do want to know if it has any connection with my main field, type theory and programming languages.

I know that algebraic topology has a lot of applications in type theory (homotopy type theory, and many more), but what about algebraic geometry, besides that both type theory/PL theory and AG are good motivators of category theory?

To my knowledge (which is definitely incomplete), there has been relatively little work on this, presumably because it requires assimilating two relatively intricate bodies of knowledge. However, little does not mean nonexistent. Thierry Coquand and his collaborators have written quite a few papers on the connections between commutative algebra and constructive logic.

Thierry Coquand, Henri Lombardi. A logical approach to abstract algebra.

This paper made a huge impression on me as a grad student -- the confident and free way that it used ideas from proof theory and model theory to do nontrivial, proper mathematics is one I greatly admired, and to which I still aspire.
Henri Lombardi and Claude Quitté have a (freely-available) textbook, Commutative algebra: Constructive methods.

As the title suggests, this is commutative algebra rather than
algebraic geometry, but since commutative algebra provides much of
the infrastructure for algebraic geometry this will still be of
interest.

There are also a number of very interesting PhD theses in the area:

Andres Mörtberg's PhD thesis Formalizing Refinements and Constructive Algebra
in Type Theory

Once you have a constructive proof, you've got an an algorithm. This thesis looks at making those algorithms efficient.
Bassel Mannaa's PhD thesis, Sheaf Semantics in Constructive Algebra and Type Theory

In this thesis, he proves the correctness of the Newton-Puiseux theorem constructively, as well as the independence of Markov's principle. It offers a nice example of how sheaf-semantic methods have applications in both geometry and logic.
Ingo Blechschmidt's PhD thesis, Using the internal language of toposes in algebraic geometry,

This thesis looks at redoing many of the usual proofs of algebraic geometry in the internal language of the little  Zariski topos associated with a scheme, yielding a kind of "synthetic algebraic geometry".  (He also does "synthetic scheme theory" using the big Zariski topos). As you would expect, since topoi are not generally Boolean, the proofs have to be done in an intuitionistic style.

It's also worth pointing out the following reference:

Saunders Mac Lane, Ieke Moerdijk. Sheaves in Geometry and Logic Sheaves in Geometry and Logic: A first introduction to topos theory.

A lot of the technology used in this work comes via the connections between topos theory, logic and geometry. This is the standard reference, though I mostly learned it via the papers of Steve Vickers instead.


UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$? Background:

In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary alphabet admits an assignment satisfying 1-$\epsilon$ of the constraints or whether there exist no assignments satisying $\frac{8}{9}+\epsilon$ of the constraints, for arbitrarily small $\epsilon > 0$.

I'm curious whether this result has been generalized for any combination of $\ell$-ary constraints for $\ell \ge 3$ and variable domains of size $k \ge 3$ where $\ell \ne k \ne 3$. That is,

Question:

Are there any known hardness of approximation results for the predicate $NAE(x_1, \dots, x_\ell)$ for $x_i \in GF(k)$ for $\ell, k \ge 3$ and $\ell \ne k \ne 3$?

I'm especially interested in the combination of values $\ell = k$; e.g., the predicate Not-all-equal($x_1, \dots, x_k$) for $x_1 \dots, x_k \in GF(k)$.

I landed on this page from a search about NAE-3SAT.

I am pretty sure that for the problem you are asking, it should be NP-hard to tell if the instance is satisfiable, or if at most $1-1/k^{\ell-1}+\epsilon$ fraction of constraints can be satisfied. That is, a tight hardness result (matching what simply picking a random assignment would achieve), for satisfiable instances, and no need for the UGC.

For $k=2$ and $\ell \ge 4$, this follows from Hastad's factor 7/8+epsilon inapproximability result for 4-set-splitting (which can then be reduced to k-set splitting for $k > 4$). If negations are okay, one can also use his tight hardness result for Max ($\ell-1$)-SAT.

For $k=\ell=3$, Khot proved this in a FOCS 2002 paper "Hardness of coloring 3-colorable 3-uniform hypergraphs." (That is, he removed the original UGC assumption.)

For $\ell=3$ and arbitrary $k\ge 3$, Engebretsen and I proved such a result in "Is constraint satisfaction over two variables always easy? Random Struct. Algorithms 25(2): 150-178 (2004)". However, I think our result required "folding" i.e., the constraints will actually be of the form NAE($x_i+a,x_j+b,x_k$) for some constants $a,b$. (This is the analog of allowing negations of Boolean variables.)

For the general case, I don't know if this has been written down anywhere. But if you really need it, I can probably find something or check the claim.


"Embedding" a language in itself Main/General Question

Let $L$ be a language. Define the languages $L_i$ with $L_0 = L$ and
$$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$$
for $i \geq 1$. Consider $\hat{L} = \bigcup L_i$. So, we repeatedly "embed" $L$ into itself to obtain $\hat{L}$.

Has $\hat{L}$ been studied? Does it have a name?

Examples/Motivation

As requested in the comments by here are some examples to better illustrate what $\hat{L}$ is. Then since no one (so far) seems to have seen this notion I will discuss my motivation for looking at it.

Klaus Draeger beat me to adding examples. I'll put those examples from the comments here for increased visibility since they are good examples.

If $L$ is a unary language, then $\hat{L} = L^+$ (and hence is regular).

If $L = {ab}$, then $\hat{L}$ is the Dyck language.

Here is a alternative way to think of $\hat{L}$. Given a language $L$ over an alphabet $A$ we play the following game. We take any $w \in A^*$ the try to reduce $w$ to the empty string $\epsilon$ by repeatedly removing subwords that are in $L$. (Here we need to by a little careful how we treat the empty string itself to make sure that this is equivalent to the definition above, but this is morally correct.)

Originally I came the define $\hat{L}$ by considering deleting powers in words. Take $L = \{w^3 : w \in A^*\}$ to be the language of cubes over the binary alphabet $A = \{a,b\}$. Then $aaabaabaabbabab \in \hat{L}$ and we can consider the following "$L$-deletion"

$$a(aabaabaab)babab \to ababab \to \epsilon.$$

Observe not all deletions will work

$$(aaa)baabaabbabab \to baabaabbabab$$

and we are stuck with a cube-free word. So, there is another notation of "strongly $L$-deletable" which in general does not coincide with $\hat{L}$.

One final example, if $L$ in the language of squares over the binary alphabet $A = \{a,b\}$, then $\hat{L}$ is the strings with both an even number of $a$'s and an even number of $b$'s. Clearly this condition is necessary. One way to see it is sufficient is to consider deleting squares and recall every binary word of length 4 or great has a square. Here $\hat{L}$ is regular.

For larger alphabets this type of argument fails since there are arbitrarily long square-free words. With alphabets of size $k \geq 3$ I can show $\hat{L}$ is not regular using Myhill-Nerode and the fact there are arbitrarily long square-free words, but I have not been able to say much more. I was hoping looking at it in this more abstract way could shed some light on the situation (and this more abstract definition seems interesting in its own right).

This question is related to the so called insertion systems.

An insertion system is a special type of rewriting system whose rules are of the form $1 \rightarrow r$ for all $r$ in a given language $R$. Let us write $u \rightarrow_R v$ if $u = u'u''$ and $v = u'ru''$ for some $r \in R$. Let us denote by $\buildrel{*}\over\rightarrow_R$ the reflexive transitive closure of the relation $\rightarrow_R$. The closure of a language $L$ of $A^*$ under $\buildrel{*}\over\rightarrow_R$ is the language
$$
[L]_{\buildrel{*}\over\rightarrow_R} = \{ v \in A^* \mid \text{ there exists $u \in L$ such that $u \buildrel{*}\over\rightarrow_R v$} \}
$$
Recall that a well quasi-order on a set $E$ is a reflexive and
transitive relation $\leqslant$ such that for any infinite sequence $x_0,
x_1, \ldots$ of elements of $E$, there are two integers $i < j$ such
that $x_i \leqslant x_j$. The following theorem is proved in [1]:

  If $H$ is a finite set of words such that the language $A^* \setminus
A^*HA^*$ is finite, then the relation $\buildrel{*}\over\rightarrow_R$ is a well quasi-order on $A^*$ and $[L]_{\buildrel{*}\over\rightarrow_R}$ is regular.

[1] W. Bucher, A. Ehrenfeucht and D. Haussler, On total regulators generated by derivation relations, Theor. Comput. Sci. 40, 2-3 (1985), 131– 148.


Can one reverse a hash with partial plaintext knowledge? First off, please forgive my ignorance because I am not as well versed in cryptography and mathematics as I would like to be. I may say something obviously wrong/dumb; please point it out!

Is there any technique which may reduce the difficulty of recovering plain text from a hash if the attacker knows part of the plain text?

Here is an example.
Alice writes this letter:

Dear Bob,
   Run!
Yours Truly,
Alice

Alice sends the plaintext to Bob over channel X and the hash over channel Y.

Eve intercepts the hash but not the plaintext.

Eve knows Alice starts the message with "Dear Bob," and ends with "Yours Truly, Alice".
Eve also knows that Alice sends messages in fixed blocks and will pad the body content with whitespace to meet the required block length.

Can Eve use her knowledge of 1)fixed message size and 2)partial plaintext knowledge to reduce the computational difficulty of reversing the hash?

I would appreciate any help on this topic, even if your answer is just "read this whitepaper".

For an ideal hash function, the fastest way to compute a first or second preimage is through a brute-force attack. That is, if there's no structural weaknesses in the design of the hash function, your best bet is to mount a brute-force attack.

The knowledge of the message size (n bits) and some parts of it (m bits) will certainly reduce the complexity of finding a preimage under the brute force attack: The worst-case complexity will reduce from 2n to 2n-m.

A space-time trade-off over the brute-force attack is by exploiting rainbow tables. I believe  the partial knowledge of the preimage may prove useful in mounting this attack too.


SAT - Hardness of determining backbone literals Let $F$ be a CNF formula. Let $l$ be one of $F$'s literals.

  Question
  Which is the complexity of determining whether $l$ is a backbone literal or not? The obvious way to do that is to propagate $\lnot l$ on $F$, obtaining $F'$: $l$ is then a backbone literal of $F$ if and only if $F'$ is unsatisfiable. I'm asking if there is another way.

The complexity is co-NP complete because you're converting to unsatisfiability of $F \land \lnot l$. I have a proof of the completeness in my PhD thesis, Claim 2 (if I may blatantly advertise myself).

There's a small problem for unsatisfiable formulas, if your definition of a backbone means that all the literals are backbone for an unsatisfiable formula, then the problem stays in co-NP. If, however, the set of backbone literals is empty for an unsatisfiable formula, you also need NP.


Applications of Barendregt–Geuvers–Klop conjecture I was learning about type systems from Benjamin C. Pierce's Types and Programming Languages and came across the Lambda cube in the chapter on Higher-Order Polymorphism. After reading up more about it on Wikipedia I learnt about its generalization, Pure type system where it is mentioned that

  It is a major open problem in the field whether this is always the case, i.e. whether a (weakly) normalizing PTS always has the strong normalization property.This is known as the Barendregt–Geuvers–Klop conjecture.

However, I am unable to think of practical applications of a proof (or disproof) of the above conjecture (perhaps due to my limited knowledge of type theory).

Question: What are the practical applications of a proof (or disproof) of the Barendregt–Geuvers–Klop conjecture?

Update
I found a paper that proves that Weak normalization implies strong normalization in a class
of non-dependent pure type systems, however it says nothing about applications

I'm not (exactly) an expert, but my understanding is that there are very few practical applications of this conjecture, except possibly simplifying the decision procedure for type-checking in normalizing theories, by allowing one to choose any reduction strategy with confidence.

My feeling about this conjecture is that it is an important litmus test on our understanding of normalization proofs in general, which at the moment (though this is rapidly changing) are somewhat ad hoc.

In particular, weak normalization proofs seem remarkably simpler, possibly due to weakly normalizing terms having the structure of a Partial Combinatory Algebra, which is not the case for strongly normalizing terms, as explained at length in a '93 paper by Hyland and Ong. Even simpler are proofs of existence of normal forms, which are the result of applying the technique of Normalization by Evaluation, which, IMO, are the "conceptually correct" proofs.

Given the difference of these 3 notions (SN, WN, existence of normal forms), one might be surprised that we have no examples of "natural" type systems where they don't all coincide (though for the latter 2, one can simply reason about the combinatorics of reductions). In the limited case of PTSes, this is what the BGK conjecture asks.

A satisfying resolution to the question would explain why a proof of WN or NbE can be promoted to a proof of SN, possibly by building a notion of normalization model which coincides in the case of PTSes. This desire for understanding is the principal motivation for the conjecture.


Run Dijkstra's algorithm twice to detect negative-weight cycles? Dijkstra's algo (for finding single-source shortest path) assumes that once a vertex has been chosen for expansion (aka exploration), its shortest path has been found. This can only be true if there are no negative-weight cycles reachable from the source.

Therefore, I was thinking that in order to detect a negative-weight cycle, we could run Dijkstra's algorithm a 2nd time, but instead of initialising the vertex distances to -infinity, we use the ones found by the 1st iteration. If at any point during this 2nd iteration, there is a distance update, the assumption above is violated, therefore there is a negative weight cycle.

There must be a mistake in my reasoning, because if this works, it would have same time complexity as Dijkstra's algo, which would be better than the Bellman-Ford algorithm, which is the textbook algorithm for solving the single-source shortest-path in potential presence of negative weight cycles.

Is my mistake that a 2nd iteration may lead to no distance updates even in the presence of a negative weight cycle? If so, could someone provide such an example?

The mistake is in

  This can only be true if there are no negative-weight cycles reachable from the source.

Actually, this can only be true if there are no negative-weight edges reachable from the source.

So the "double Dijkstra" suggested above may wrongly return false in a graph with negative-weight edges but no negative-weight cycles, whereas Bellman-Ford will correctly return true.