Separation between existence of crypto primitives I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My question is how can we show this is not possible? For example, AFAIU, the existence collision resistant hash functions does not follow from the existence of one-way functions (at least not in a black box manner), but how is this formally stated?

The motivation is to understand what it means to show that DDH against subexponential ($2^{n^\epsilon}$) size circuits does not follow from DDH against polynomial size circuits. Note that the situation is more complicated here because DDH is a hardness assumption about a particular function, so it is not clear what would it meant to relativize it. I would also be interested in references if this is already known.

There are several techniques which prove the nonexistence of black-box reductions. They are all inspired by the seminal work of Impagliazzo & Rudich. Let me describe the Impagliazzo-Rudich (IR) technique at a high level.

In crypto, it is well-known how to construct a secure secret-key exchange protocol from trapdoor one-way permutations. However, all attempts to construct such protocols from general one-way permutations were failed. So, it was an open problem whether such constructions were possible at all.

The hard part of refuting those constructions is as follows: It is believed that both one-way permutations and secure secret-key exchange protocols exist; so how can we refute the latter if we merely assume the former? In IR words:

  The implication, "if one-way permutations exist, then secure secret-key agreement is possible," is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model.

While they were not succeeded to refute the existence of such black-box reductions, they were able to provide strong evidence that the implication is not provable by standard techniques. To this end, IR came up with the following model:

Assume that all parties (including the adversary) have access to a random-permutation oracle (RPO), i.e. a function chosen uniformly from all n-bit to n-bit permutations (where 1n is the security parameter). RPO models the black-box access to some one-way permutation. Now, IR prove that in this model, secure secret-key agreement is possible if and only if P ≠ NP. Since standard techniques cannot resolve the P vs. NP problem, it follows that proving (or disproving) the implication "if one-way permutations exist, then secure secret-key agreement is possible" is as hard as proving (or disproving) P ≠ NP.

Other excellent resources on this topic:

Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions: rules out black-box constructions of collision-resistant hash functions from one-way functions (as pointed out in the question). Excerpt:

  We prove the existence of an oracle relative to which there exist several well-known cryptographic primitives, including one-way permutations, but excluding (for a suitably strong definition) collision-intractable hash functions. Thus any proof that such functions can be derived from these weaker primitives is necessarily non-relativizing; in particular, no provable construction of a collision-intractable hash function can exist based solely on a "black box" one-way permutation.
  Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins.
  Notions of Reducibility between Cryptographic Primitives.

The papers are inspired by the work of IR, and extend their techniques.

5 recent papers on the topic can be found in the proceedings of TCC 2011 (see chapters Black-Box Constructions and Separations and Black-Box Separations, pages 541--629).
They have surveys of previous results, which are certainly useful.

An important technique: Black-box reductions are by definition relativizing. So, if relative to some oracle, one primitive exists but the other does not, the existence of the latter cannot be deduced in a black-box manner from the existence of the former.


Hardness of approximation assuming NP != coNP Two of the common assumptions for proving hardness of approximation results are $P \neq NP$ and Unique Games Conjecture. Are there any hardness of approximation results assuming $NP \neq coNP$ ? I am looking for problem $A$ such that "it is hard to approximate $A$ within a factor $\alpha$ unless $NP = coNP$".

It is known that "showing factor $n$ NP-hardness for shortest vector problem would imply that $NP = coNP$". Note that this is the "opposite" of what I am looking for.

Clarification : It is possible that $NP=coNP$ and still the P vs NP question is open. I am looking for hardness of approximation result which will become false if $NP=coNP$ but is unaffected (i.e., still remains as a conjecture) by $P \neq NP$.

Here's a straightforward observation. If you assume $NP \neq coNP$, then it is pretty easy to see there are $NP$ optimization problems which do not even have good nondeterministic approximation algorithms, in some sense.

For example, the PCP theorem says that you can translate SAT into the problem of distinguishing whether $1-\varepsilon$ of the clauses are satisfied and all of the clauses are satisfied, for some $\varepsilon > 0$. Suppose there is a nondeterministic algorithm which can distinguish between these two cases, in the sense that the nondeterministic algorithm can report in each computation path either "all satisfied" or "at most $1-\varepsilon$", and it says "at most $1-\varepsilon$" in some path if at most $1-\varepsilon$ can be satisfied, otherwise it says "all satisfied" in every computation path if all equations can be satisfied. This is enough to decide SAT in $coNP$, so $NP=coNP$. It seems clear that the existence of such a nondeterministic algorithm has no bearing on whether $P = NP$.

It's quite plausible that a more "natural" scenario exists: an optimization problem which is hard to approximate in deterministic polynomial time under $NP \neq coNP$ but not known to be hard under $P \neq NP$. (This is probably what you really wanted to ask.) Many hardness of approximation results are first proven under some stronger assumption (e.g. $NP$ not in subexponential time, or $NP$ not in $BPP$). In some cases, later improvements weaken the necessary assumption, sometimes down to $P \neq NP$. So there is hope that there's a slightly more satisfactory answer to your question than this one. It is hard to wonder how there could be a problem that cannot be proved hard to approximate in deterministic polytime under $P \neq NP$, but it can be proved hard under $NP \neq coNP$. That would mean that $NP \neq coNP$ tells us something about deterministic computations that $P \neq NP$ doesn't already say; intuitively, this is hard to grasp.


Monitoring PhD positions in TCS Are there any ways of getting to know about new PhD positions in TCS other then just looking trough ubniversity/research groups web sites?

Maybe people from different branches (type theory, verification, complexity, etc.) can name some specialized mailing-lists where PhD positions announcements are quite usual.

PS In my university we haven't got huge TCS research and we always have smart students “at hand” which are good candidates for sending for PhD positions, but in order to make this process more effective it would be nice to have some sources of new positions opening.

PhD positions in TCS and Discrete Math are sometimes announced on TheoryNet and DMANET. These are mailing lists to circulate announcements and questions regarding conferences, workshops, seminars, books and jobs in these areas.


What is the difference between System F and Hindley-Milner type system? Hindley-Milner type system is some restriction of System F, which allows type inference.

But from simple descriptions I cannot see, what is the difference between them?

Yes, In Hindley-Milner universal quantifiers are allowed only at the outside of a type (and therefore omitted). For example, in HM you can have the type $\forall \alpha.(\alpha\to\alpha) \to (\alpha\to\alpha)$ usually abbreviated as $(\alpha\to\alpha)\to(\alpha\to\alpha)$, but you cannot have $(\forall \alpha.\alpha\to\alpha) \to (\forall \alpha.\alpha\to\alpha)$.

A special feature of HM (that does not make sense for system F) is the distinction between let-bindings and beta reducts. In a let-binding the type of the bound variable may be polymorphic in the sense that its free type variables are quantified separately. For example,

let f = λ x . x in λ x . f f x

can be typed in HM and in system F (by giving f the polymorphic type $\forall \alpha.\alpha\rightarrow\alpha$), but

(λ f . λ x. f f x) (λ x . x)

cannot be typed in HM, only in Sytem F.

The advantage of these restrictions is that type inference for HM
is decidable and rather efficiently so whereas it is undecidable
for F.


n-dimensional pattern matching What are some known results for finding an exact n-dimensional subarray inside a n-dimensional array?

In 1D, it is just a string matching problem, KMP does it in linear time.

In 2D, this paper shown it can be done in linear time with little extra space.

Can this problem be solved in linear time worst case for any fixed dimension?

You can solve the problem in a fixed number of dimensions by extending the linear time original solution of Bird from 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (subscription needed sadly).

The general idea (in 2D) is in step 1 to build an Aho-Corasick automaton of the rows of the 2D pattern and then feed in the rows of the 2D text one by one. You will then find all the positions that the pattern rows match in the text.  To finish you now only need to do a 1D search for the (labels of) the rows of the pattern in the right order in a column in the output of step 1, using KMP say.  This all takes linear time.

Using the same method you can reduce from any dimension d exact matching problem to a dimension d-1 problem. In this way you get a linear time solution for any fixed dimension d.


"Any" Subset Sum. Is it hard? Here is a variant of the classic partition problem: Given a list of integers can it be partitioned into $S_1$, $S_2$, and $S_3$, with $S_1$ and $S_2$ nonempty, so the sum of elements in $S_1$ equals the sum of elements in $S_2$?

Is this problem NP-hard?

The problem is known to be NP-complete: On the equal-subset-sum problem, Woeginger and Yu, IPL'92.


How to model degree variable in logic (new type of modal logic?)? I am trying to model domain in logic (first order logic or some of modal logics) and I have variable which is degree and not true-false variable. There can be different conclusions depending on the degree of this variable. How to model such variable? If v ir degree variable and n degrees are possible, then v can be modelled by introduction of n propositional variables v1=true <= v=1, v2=true <= v=2 and so on. Additional constraints (axioms) should be introducted - e.g. only one variable from v1, ..., vn can be true.

Introduction of additional variables is not good, because: 1) it increases complexity; 2) it is not extendable in simple manner.

The question is - maybe there is some syntactic sugar available for degrees, or maybe special logics are already available for handing degrees of even variables whose domain is set of natural numbers?

Prolog and other logical programming environments has this feature, maybe this can be brought back to the theory as well.

What semantics of the logical operators would you like to have? Two of the best studied semantics for degrees are (propositional) Łukasiewicz logic and Gödel-Dummet logic. The latter enforces the domain to be a linear order which would allow you to model them via the naturals. It is also axiomatizable, since it is equivalent to intuitionistic propositional logic with the axiom of linearity (A => B) \/ (B => A).

It also has a hyper-sequent calculus which is sound and complete (have a look at e.g. A. Avron "A Simple Proof of Completeness and Cut-elimination for Propositional Gödel Logic"), which you could implement in Prolog.


Chromatic number of a particular graph Assume I have a parametrized graph. The parameters are two integers $x$ and $y<x$.
Let $S(x)=\{1, \ldots, x\}$.
The vertices of the graph are all the subsets of $S(x)$ of size $y$. Two vertices share an edge if their intersection is empty.
I need to find the chromatic number of this graph.
Is this problem NP-hard ?

Thank you in advance for your help.


Maintaining the product of a queue of semigroup elements I have a queue $Q$ where elements can be popped from the left and added to the right in $O(1)$ time.  The elements are members of a fixed semigroup $S$ with $O(1)$ time multiplication.  Let the current state of the $Q$ be the sequence $(s_1,\ldots,s_n)$.  I am interested in the product

$$\prod Q = s_1 \cdots s_n.$$

Question: Is it possible to maintain this product in amortized constant time as elements are added and removed?

A queue can be represented as two stacks and be maintained in amortized constant time. It's then easy to maintain product of all elements of a stack.

See Purely Functional Data Structures by Chris Okasaki. (More specifically, figure 3.2 on pp. 18. )

About how to maintain on stacks:

Suppose the stack is $s_1, s_2,\ldots, s_n$ from bottom to top. For one stack, we need to maintain $s_1 s_2 \ldots s_n$; for the other, we need to maintain $s_n\ldots s_2 s_1$. We only consider the first case.

Let $p_k=s_1\ldots s_k$, then $p_n$ is the answer we need.

When pop, simply delete $p_n$ and $s_n$.

When push, $p_{n+1}=p_n s_{n+1}$.


Examples of successful derandomization from BPP to P What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)?

The only example that comes to my mind is AKS deterministic polynomial time primality testing (even for this there was a methodology assuming GRH). So what specific evidence through example do we have for derandomization (again not the hardness or oracle connection)?

Please keep examples to only where time complexity improvement was shown from randomized poly to deterministic poly or something that is very close for specific problems.

Following is more of a comment and I do not know much it will help this query.

Chazelle has a very intriguing statement in http://www.cs.princeton.edu/~chazelle/linernotes.html under 'The Discrepancy Method: Randomness and Complexity   (Cambridge University Press, 2000)'.

'It's been an endless source of fascination for me that a deeper understanding of deterministic computation should require the mastery of randomization. I wrote this book to illustrate this powerful connection. From minimum spanning trees to linear programming to Delaunay triangulations, the most efficient algorithms are often derandomizations of probabilistic solutions. The discrepancy method puts the spotlight on one of the most fruitful questions in all of computer science: if you think you need random bits, please tell us why?'

$SL = L$.

$RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace") that $SL = L$, where $S$ stands for "symmetric" and $SL$ is an intermediate class between $RL$ and $L$.

The idea is that you can think of a randomized logspace Turing machine as an polynomial-sized directed graph, where nodes are states of the machine, and an RL algorithm takes a random walk that has good properties. SL corresponds to undirected graphs of this form. Reingold's proof built on work on expander graphs, particularly Reingold, Vadhan, and Wigderson's "zig-zag product", to take any random walk on an undirected graph with good properties and turn it into a psuedorandom walk retaining those properties.

edit this question was posted before the question was explicitly changed to focus exclusively on P vs BPP ... I am leaving it up because it seems to be of interest.


Enumerating Planar Graphs of Bounded Treewidth I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical and practical results, but mostly practical algorithms that are possible to code and run for as large as possible values of $n$ and $k$ (think $k \leq 5$ and $n \leq 15$). If you already have an answer, ignore the ramblings below.

The following approach works sort of ok for enumerating all non-isomorphic graphs on $n$ vertices and treewidth $\leq k$ (i.e when the planarity constraint is dropped):

(a) Enumerate all non-isomorphic graphs on $n-1$ vertices and treewidth $\leq k$.

(b) For each vertex $G$ on $n-1$ vertices and treewidth $\leq k$, every clique $C$ on $\leq k$ vertices in $G$ and every subset $S$ of edges in $C$, make $G'$ from $G - S$ by adding a new vertex $v$ adjacent to $C$. Add $G'$ to the list ${\cal L}$ of grahs on $n$ vertices and treewidth $\leq k$.

(c) Trim ${\cal L}$ by removing copies of the same graph.

A tempting way to extend this to enumerate planar graphs of treewidth $\leq k$ is to simply filter out the non-planar graphs at every iteration. Unfortunately this fails to generate all planar graphs of treewidth $\leq k$ (for example because it only enumerates $4$-degenerate graphs).

Of course we could enumerate all graphs on $n$ vertices and treewidth $\leq k$ and only then filter out the non-planar ones, but this fails to exploit that most graphs are non-planar and seems very sub-optimal.

There is a nice software which generates small planar graphs with respect to isomorphism which might help. As I see one of the problem was to generate non-isomorphic planar graphs and most of those planar graphs (on less than 15 vertices) are of small treewidth.

For checking whether their treewidth is smaller than given value $k$, one way is to use heuristic algorithms to speed up this calculation, just in the case that exact algorithms are not practical. e.g in a planar graph $G$ first we can find a diameter of $G$ and the corresponding path $P$ of length $d$ (which is a diameter). Then find a vertex $v\in P$ which has shortest longest distance ($l$) to any other vertex $u\in G\setminus P$ among all vertices $w\in P$. The treewidth of $G$ is at most $d+l$, if this is smaller than $k$ then we are done otherwise either apply some other heuristic algorithms or run the exact algorithm.

For less than 3-connected graphs it's also possible to apply heuristics by finding cut vertices and then fixing those vertices and finding the tree width of a remaining graph. But as the number of nodes is small ($15$) if the graph is $4$-connected then the diameter is not big and I think the first heuristic should work there. (I don't know if there is any 5 connected planar graph on at most 15 vertices, but as we know there is no $t$-connected planar graph for $t>5$)

As the size of largest obstruction for tree width $k$  is not known we cannot simply guess the upperbound value of treewidth of a given graph $G$. But it seems that at least for planar graphs it should not be so big (one should give a proof for this).


Is there a result in computability theory that does not relativize? I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that

  Our axiomatization has its limit: it cannot prove any results in computability
  theory that fail to relativize to oracle computations. This is so because the
  theory can be interpreted in a variant of the effective topos built from partial
  recursive functions with access to an oracle.

This made me wonder about non-relativizing results in computability. All results I know from computability theory do relativize to computation with oracles.

Are there results in computability theory that do not relativize? I.e. results which hold for computability but do not hold for computability relative to some oracle?

By result I mean a known theorem in computability theory, not some cooked up statement. If the notion of relativization doesn't make sense for the result then it is not what I am looking for.

It is also interesting to know if the result can be stated in the language of Synthetic Computability Theory or not.

Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented group (even ones countably generated) is a subgroup of a finitely presented group.

Note that this statement could relativize to: "The $O$-computably presented groups (with some oracle $O$) are precisely the finitely generated subgroups of finitely presented groups," but it does not, as one can prove that for some uncomputable $O$ there are $O$-computably presented groups that are not computably presented.

Indeed, I think any non-relativizing result of computability theory must have something of this flavor, as some part of the result or its proof must somehow "nail down" true computability from computability with an oracle $O$. In this case, it is the finiteness which nails down "actual computability." Note that, as Scott Aaronson asked for, this result is invariant to any of the usual models of computation (Turing machine, RAM, etc), but does not relativize (again, because all of the usual models of "actual" computation share some common "finiteness property").

On the other hand, one might argue that this "doesn't count" for this question, as it is more akin to a definition of computability using groups than it is a "result of computability theory." On the other other hand, it is a definition of computability that is robust to model yet that doesn't relativize. (In contrast to, say, Kleene's characterization of the computable functions which easily relativizes, by simply adding the characteristic function of your oracle to the generating set of functions. There seems to be no analogous operation for groups in the context of Higman Embedding.)


Is there a non Turing-complete model of computation whose halting problem is undecidable? I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton?

This would almost disprove Wolfram's "Principle of Computational Equivalence":

  Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication

You can easily build artificial models which are not Turing complete but the halting problem for them is undecidable. E.g. take all TMs that do not halt on anything but $0$.
Regarding the statement:
You cannot disprove a statement that is not precise enough. Almost none of the words in the statement is well-defined (please provide the definition for them if this is not the case).


Real world applications of quantum computing (except for security) Let's assume that we have built an universal quantum computer.

Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it?

I am interested in both:

problems currently unsolvable for a practical entry,
problems which currently are being resolved, but a significant speedup would greatly improve their usability.

Efficiently simulating quantum mechanics.


Permutations of maximum period: applications to Rubik's cube Dear Mods: this may be a non-research question, but I am asking it because from my knowledge, the question appears nontrivial.

This video claims that a Rubik's cube can be "solved" from any starting position with the repeated application of two fixed moves. The method is easily seen as wrong because the specific moves he suggests actually leave the bottom right $2\times 2 \times 3$ block unaffected. My question is more general: does there exist a finite set of moves which if applied repeatedly from any starting position, yield a solved Rubik's cube?

Moves can be thought of as permutations on the set configurations of a Rubik's cube. A solved Rubik's cube is a specific configuration of interest. If these moves get you from any configuration to a solved configuration, then (by symmetry) these moves must get you from any configuration to any other configuration. This means these moves constitute a permutation of maximum period. Does such a permutation even exist? What is known about the existence of such a permutation?

Copy/paste from another (slightly different) cstheory question on Rubik's cube:

"What is the shortest sequence that scans all cube's configurations", or "does the configuration graph of the cube have a Hamiltonian path?" is a special case of a more general unsolved problem:

For an arbitrary permutation group with a given generating set, is its Cayley graph Hamiltonian?

There are some good info available online, you can download the lecture notes by W.D.Joyner: Mathematics of the Rubik's cube (downloadable in pdf format).

Chapter 6 of the lecture notes is devoted to Cayley graphs and God's algorithm.

EDIT: If I correctly interpret the question "Does such a permutation even exist?", the answer is yes (the Cayley graph of a finite group is connected); a trivial argument:

let $k$ be the total number of wrong configurations;
for every wrong configuration $W_i, 1 \leq i \leq k$ write down the solving sequence of moves $S_i$;
let $S_i^{-1}$ be the inverse sequence of $S_i$;
obviously the (long) sequence $S_1 \cdot S_1^{-1} \cdot S_2 \cdot S_2^{-1} ... \cdot S_{k-1}^{-1} \cdot S_{k-1}^{-1} \cdot S_k$ will lead you to the solved configuration from any wrong starting configuration, but you must "look at the cube" to see when to stop (there is no "synchronizing sequence").


Containment problem of an acyclic NFA in an NFA Let $A$ and $B$ be NFAs, such that $A$ is acyclic.

In the general case, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$-hard. However, since $A$ is acyclic, we know that for every $w \in L(A)$, it holds that $|w|$ is linear in $|A|$. It follows that if $L(A) \nsubseteq L(B)$, there must be a polynomial witness $w\in L(A)\setminus L(B)$. Thus, the containment problem when $A$ is acyclic is in $coNP$.

Can it be shown that it is $coNP$-hard?

This is coNP-hard even if $B$ is also acyclic.

Let $D = \bigvee_{i=1}^m T_i$ be a DNF on variables $x_1, \dots, x_n$. We can easily contruct an NFA $B$ accepting exactly the satisfying assignment of $D$, that is, the words $w \in \{0,1\}^n$ such that the assignment $a$ defined as $a(x_i) = w_i$ satisfies $D$.

To do this, you build an automaton $B_i$ with $n+2$ states recognizing $T_i$ and add an initial state that non-deterministically chooses $i$ and jumps into $B_i$ with an $\epsilon$-transition.

$B_i$ has states $q_1, \dots, q_{n+1}$, and $reject$. Initial state is $q_1$. When in state $q_j$ for $j \leq n$: if $x_j$ does not appear in $T_i$, then you go in state $q_{j+1}$ for every value of the next letter. If $x_j$ appears positively in $T_i$, then you go in $q_{j+1}$ only if you read letter $1$. If you read letter $0$, you go in state $reject$. If $x_j$ appears negatively in $T_i$, you do the same by swapping $0$ and $1$. $q_{n+1}$ is the only final state.

Now you build $A$, acyclic, which accepts every word of length $n$ (same construction as before for $T_i$ empty).

It is clear that $L(A) \subseteq L(B)$ iff $D$ is a tautology, which is
coNP-complete.


Minimal polynomial reduction of dominating set to max clique Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$

It is well known that it is NP complete to determine the  minimal dominating set of $G$ and that is usually done via the vertex-cover problem.

As the title suggests, I would like to reduce dominating set to the max clique problem. One can of course use the standard reductions to do so, but I would like to find a as "small as possible" reduction. That is I would like to be able to reduce a graph $G$ to a graph $\widehat{G}$ that is as small as possible and so that $\gamma(G)$ can be efficiently determined from $\omega(\widehat{G}).$ Here $\gamma$ and $\omega$ are the size of the dominating set and clique number respectively.

Can someone suggest such a reduction?

There are good reasons to expect that there is no polynomial time reduction that takes as input a graph $G$ and outputs a graph $\hat{G}$ such that $\omega(\hat{G})$ depends only on $\gamma(G)$. In particular the Clique problem is complete for $W[1]$ while Dominating Set is complete for $W[2]$, see the Wikipedia page for Parameterized Complexity. A reduction from Dominating Set to Clique where the size of the clique only depends on the size of the dominating set would imply that $W[2] = W[1]$, which is considered unlikely.

On the other hand it is not too hard to make a reduction where $\omega(\hat{G})$  depends only on $\gamma(G)$ and $|V(G)|$. For every edge $uv \in G$ make two vertices $[u,v]$ and $[v,u]$ in $\hat{G}$. For two vertices $[u_1,v_1]$ and $[u_2,v_2]$ of $\hat{G}$ we put an edge between them if $u_1 \neq u_2$, $u_1 \neq v_2$ and $u_2 \neq v_1$. We claim that $\omega(\hat{G}) = |V(G)| - \gamma(G)$.

The intuition is that the vertex $[u,v]$ is interpreted as ``$u$ is dominated by $v$''. Then each vertex of $G$ not in the dominating set should choose exactly one vertex in the dominating set to dominate it. Someone who has chosen to be dominated may then not be a dominator.

Consider a dominating set $S$ in $G$. We make a set $\hat{S}$ as follows: for each vertex $u \notin S$, pick an arbitrary neighbor $v \in S$ of $u$ and add $[u,v]$ to $\hat{S}$. Clearly $\hat{S}$ is a clique of size $|V(G)| - |S|$.

On the other hand consider a clique $\hat{S}$ in $\hat{G}$. Let $S$ be the set of vertices $u$ in $V(G)$ such that there does not exist a $v \in V(G)$ such that $[u,v] \in \hat{S}$. Observe now that $|S| \geq |V(G)| - |\hat{S}|$, since each element of $\hat{S}$ rules out at most one vertex of $G$. Consider a vertex $u \notin S$. There must be some vertex $v \in V(G)$ such that $[u,v] \in \hat{S}$. We know that $uv \in E(G)$, it remains to show that $v \in S$. Suppose not, then there must be some $v' \in V(G)$ such that $[v,v'] \in \hat{S}$. But $[u,v]$ and $[v,v']$ are non-adjacent in $\hat{G}$, contradicting that $\hat{S}$ is a clique. So $S$ is a dominating set.


Is this a known learning problem? Let $(\mathcal{X},\rho)$ be a metric space (say, $\mathcal{X}=[0,1]$ with the Euclidean metric). Let $\alpha:\mathcal{X}\to[0,1]$ be unknown. Suppose that $\mathcal{X}$ is endowed with a distribution $\mu$ from which $(X_1,\ldots,X_n)$ is sampled iid. Further, for each $X_i$, we observe $Y_i\sim\mathrm{Bernoulli}(\alpha(X_i))$.

Our goal is to recover $\alpha$ from the finite sample, under some loss function (I tend to favor the pointwise loss $\ell(\hat\alpha,\alpha)=$
$$KL(\hat\alpha||\alpha)
=
\hat\alpha\log(\hat\alpha/\alpha)
+
(1-\hat\alpha)\log[(1-\hat\alpha)/(1-\alpha)]
,$$
but other loss functions can be considered also.)

Obviously, there is no hope of recovering $\alpha$ without some regularity condition, such as Lipschitz continuity.

Does this problem fall under some known framework?

Edit: Following Clement's comment, a clarification. The loss I defined above is pointwise, at each $x$ --- so it should really be $\ell(\hat\alpha(x),\alpha(x))$. The overall risk is then
$$R(\alpha)=E_X[\ell(\hat\alpha(X),\alpha(X))].$$

Well, we wrote a paper on it, so now it's definitely known:
https://arxiv.org/abs/2010.09886


Confidentiality of "partial private keys" in certificateless public key crypto I'm looking at alternatives to PKI and I'm having trouble understanding exactly how certificateless public key algorithms (e.g. Al-Riyami and Paterson, Liu et al) work in practice.  It seems like the "partial private key" generated by the KGC in these systems is not actually confidential information (which would be awfully convenient for practical use of the system), but if it isn't, then I don't understand why the KGC and its master secret are necessary.

(I hope this isn't too "practical" a question for this site.)

The best way to answer this is to look at the security model in that paper.  If the adversary is allowed to request the partial private key for the target identity (i.e. the one it uses in the left-right query during the attack), then partial-private-keys are not meant to be kept secret.  If the adversary is not allowed to do so, then they must remain confidential.

After scanning their model, it seems that all partial private keys are readily supplied to adversary via Extract-Partial-Private-Key-of-A queries. This means they don't need to be kept secret.

I've got to run now, but I'll edit later if I've gotten this wrong.


Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits? There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an optimum value. And another theory, that of differential approximation where the approximation ratio is $\inf\frac{\Omega-A}{\Omega-OPT}$, $\Omega$ - the worst value of a feasible solution for the given instance. The authors of this theory claim that it has some definite advantages over classical one. For example:

it gives the same approximation ratio for such problems as Minimum vertex cover and Maximum independent set which are known to be just different realizations of the same problem;
it gives the same ratio for max and min versions of the same problem. At the same time we know in standard theory MIN TSP and MAX TSP have very different ratios.
It measures distance not only to the optimum but also to the pessimum $\Omega$. So in the case of Vertex Cover standard approximation theory says that $2$ is the best upper bound. But essentialy $2$ is the maximum ratio between the pessimum and the optimum. Thus such algorithm is guaranteed to output the solution with the worst value.

My argument pro is: in asymptotic analysis we don't take into consideration constants and low-order terms (here I recalled the quote by Avi Widgerson: "We are successful because we use the right level of abstraction.") and this is the level of abstraction for comparing algorithm's usage of resources. But when we study approximation we by some reason introduce the difference in those places where we can avoid it.

My question is

  why the differential approximation theory so poorly studied. Or the arguments involved are not strong enough?

I am not familiar with the notion of differential approximation, and I do not have any theory why it is not well-studied.  However, I would like to point out that it is not always desirable to describe the performance of an approximation algorithm by a single measure.  In this sense, I find it difficult to agree that some measure is better than another.

For example, as you stated, minimum vertex cover admits a polynomial-time 2-approximation algorithm whereas it is NP-hard to approximate maximum independent set to any constant ratio.  Although I understand that this can be surprising at first sight, it has a legitimate meaning: (1) minimum vertex cover can be approximated well when it is small but (2) it cannot be approximated well when it is large.  When we state that it is NP-hard to approximate minimum vertex cover (and maximum independent set) with any positive constant differential approximation ratio, we are effectively ignoring the property (1).  It is probably good enough for some purposes to ignore the property (1), but certainly it is not always the case.

Note that we do not always use approximation ratio to describe the performance of approximation algorithms.  For example, to state an inapproximability result based on the PCP theorem in its full generality, we need the formulation based on gap problems.  See my answer to another question for details.  In this case, neither using the standard approximation ratio nor using the differential approximation ratio allows us to state the result in the full generality.


Partition edges into edge disjoint walks Consider an undirected graph $G=(V,E)$ and two sequences of $k$ vertices $S=s_1,\ldots,s_k$ and $T=t_1,\ldots,t_k$.
A set of $k$ walks is called a $(S,T)$-walk partition if

the walks form a partition the edges of $E$, and
there exists a permutation $\pi:[k]\to[k]$, such that the $i$th walk is a $s_it_{\pi(i)}$-walk. (A $st$-walk is a walk that starts with vertex $s$ and ends with vertex $t$)

We consider the following problem.

  $k$-walk partition

  Input: Graph $G$ and two sequence of $k$ vertices $S$ and $T$.

  Output: Does there exists a $(S,T)$-walk partition in $G$.

Is this problem studied? I'm interested when $k$ is a constant.
When $k=1$, this is the same as checking if there is a Eulerian trail from $s_1$ to $t_1$.

Create a new source and connect it to $s_1,\ldots,s_k$, and create a new sink and connect it to $t_1,\ldots,t_k$.
Every edge has capacity $1$ and cost $−1$.
With this, the problem is a special case of the min-cost flow problem.


Complexity of Computing Lexicographically Minimal Element of Orbit Given strong generators for a group $(G \leq S_n, *)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, the orbit of $s$ in $G$?

This problem is NP-hard.

Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world looks, finding the lexicographically least isomorphic string is NP-hard. This is precisely the content of Proposition 3.1 here. In fact, they show it remains NP-hard even when $G$ is an elementary abelian 2-group (=every nontrivial element of $G$ has order 2).


"Correctness" of type theory How to "proof"  that type theory is correct? Or at least explain that it's meaningful in some sense. In what extent is this a mathematical question and in what is a philosophical one?

When type theories are introduced for example in Luo's book, the following properties are proved:

Subject reduction
Reduction termination
Church-Rosser property

As far as I understand, what these properties describe is that we have a decidable type checking, and that the language of type theory is meaningful in some sense, but nothing more than this.

I asked a question on violation of strict positivity for inductive types (Example of where violation of strict positivity condition in inductive types leads to inconsistency) and in the answer I was told that non strictly positive types might lead to non existence of set theoretic model. Why we need type theoretic model here? And what it gives to us?

Type theories have multiple uses, and with each kind of usage comes a different
notion of correctness. They two key uses are

As a foundation of mathematics. In this context correctness means
primarily that we can't deduce falisity.
As a tool in programming. Here correctness means primarily that that
well-typed programs "don't go wrong" in Milner's famous words, i.e. that they do not
exhibit a certain forms of error, such as trying to execute 3 +
"hello".

Both notions of correctness are related, but not the same.

Gödel's second incompleteness theorem puts serious restrictions in the way of showing the 'correctness' of type theories as a foundation of mathematics. The best you can hope for is to show 'correctness' (understood as consistency) relative to some other foundation, e.g. by giving a set-theoretic model.

The key thing we worry about with type theories is  that a given type-theory is inconsistent because we can define a non-terminating term. Modern type-theories are fairly complicated beasts, and it's quite easy to make them too powerful  so  that a fix-point combinator
becomes definable. Such fixpoint combinators inhabit every type, making the type-theory inconsistent as a foundation of mathematics. Since fixpoint combinators can be subtle, it is quite easy to overlook how one's typing system allows them to be defined. Indeed, famous foundationalists have a habit of
proposing foundations of mathematics that are unsound for this reason.  For example Martin-Löf's original proposal for type-theory made the kind of types itself a type (that approach to typing is now referred to as Type:Type). This is
extremely convenient, and gives you the most general form of impredicative polymorphism. Alas,  Girard discovered that this was unsound, when he managed to express the Burali-Forti paradox in Type:Type, see this discussion for more details.  Every since, Martin-Löf's type theories have been predicative, but with added inductive definitions to recover (much of) the expressive power of impredicativity.

Encoding a type theory in another foundation such as set theory gives us a fuzzy feeling of security: it says there are unlikely to be  an obvious unsoundness bugs in our type-theory. The justification behind this intuition is strictly empirical (!): in the century of since Cantor invented and Zermelo formalised it, nobody has found a soundness bug in conventional set theory. (As an aside, this situation is similar to cryptography where we trust RSA, Diffie-Hellman, AES or 3DES for little other reason than that they have withstood sustained attempts at breaking.)

Note that while a system with Type:Type is wrong as a foundation of
mathematics, it is perfectly acceptable as a typing system for
programming languages, because we can still show that no typeable program goes "wrong".

Regarding proof techniques for correctness, the different properties you mention relate to different notions
of correctness. Termination is the key step to showing correctness
of a type-theory as a foundation of mathematics, while subject
reduction is usually the key step to showing that a type-theory
is usable as a tool in programming. Note that since a termination
proof is the high-road to consistency as a foundation, by
Gödel's second incompleteness theorem, we can prove termination of a type-theory only by using a stronger system.


Hierarchies in NP (under the assumption that P != NP) Assuming that P != NP, I believe it has been shown that there are problems which are not in P and not NP-Complete. Graph Isomorphism is conjectured to be such a problem.

Is there any evidence of more such 'layers' in NP? i.e. A hierachy of more than three classes starting at P and culminating in NP, such that each is a proper superset of the other?

Is it possible that the hierarchy is infinite?

Yes! In fact, there is provably an infinite hierarchy of increasingly harder problems between P and NP-complete under the assumption that P!=NP. This is a direct corollary of the proof of Ladner's Theorem (which established the non-emptiness of NP\P)

Formally, we know that for every set S not in P, there exists S' not in P such that S' is Karp-reducible to S but S is not Cook-reducible to S'. Therefore, if P != NP, then there exists an infinite sequence of sets S1, S2... in NP\P such that Si+1 is Karp-reducible to Si but Si is not Cook-reducible to Si+1.

Admittedly, the overwhelming majority of such problems are highly unnatural in nature.


Lower bound on the support size of an $\epsilon$-biased distribution Let $D$ be an $\epsilon$-biased distribution we want to show that
$$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$
I know that there are some proofs for this but I am intrested in the following particular way.

Let $X,Y$ be two distributions over $\{0,1\}^n$. Consider the "convolution" of distributions $Z=X\circledast Y$ to be defined by sampling $x\sim X$ and $y\sim Y$ independently and outputting $x\oplus y$ where $\oplus$ is just bit-wise xor.

Now if we define a distribution $D^{(t)}=D\circledast\cdots\circledast D$ ($t$ times) we can use some Fourier analysis and combinatorics to show that

$D^{(t)}$ is $\epsilon^t$-biased.
$|\text{Supp}(D^{(t)})|\leq\binom{|\text{Supp}(D)|+t}{t}$

We can also show that for every $\delta$-biased distribution $Z$ we have $\lVert Z\rVert_2^2\leq\delta^2+2^{-n}$ when considering the distribution as a vector of probabilities. Now, I was told that I can use the latter to obtain a lower bound on $|\text{Supp}(D^{(t)})|$ and then choose $t$ accordingly to get the desired bound.

However, the only bound I can get for $|\text{Supp}(D^{(t)})|$ is
$$|\text{Supp}(D^{(t)})|\geq\sqrt{\frac{1}{\epsilon^{2t}+2^{-n}}}$$
And I don't see how that helps...

You shouldn't have a square root. Namely, for every $\delta$-biased distribution $Z$ (using your notation), we have
$$
\delta^2+2^{-n} \geq \lVert Z\rVert^2_2 \geq \frac{1}{\lvert\operatorname{supp} Z\rvert}\tag{1}
$$
since the squared $\ell_2$ norm of a distribution over support of size $N$ is at least that of the uniform distribution on $N$ elements, which is $1/N$.
This gives you, for $t\geq 1$ to choose suitably,
$$\lvert\operatorname{supp} D^{(t)}\rvert \geq \frac{1}{\varepsilon^{2t}+2^{-n}} \tag{2}
$$
since as you have shown $D^{(t)}$ is $\delta$-biased for $\delta=\varepsilon^t$. A natural choice of $t$, in view of (2), is the one balancing the denominator, i.e., such that $\varepsilon^{2t}=2^{-n}$. This leads to taking
$$
t \stackrel{\rm def}{=} \frac{n}{2\log(1/\varepsilon)}\tag{3}
$$
Recalling the standard bound $\binom{n}{k}\leq \left(\frac{en}{k}\right)^k$ for $1\leq k\leq n$ along with (2), (3), and what you mentioned as 2. in your question, we thus get
$$
\left(\frac{e(\lvert\operatorname{supp} D \rvert+t)}{t}\right)^t \geq \binom{\lvert\operatorname{supp} D \rvert+t}{t} \geq \frac{1}{\varepsilon^{2t}+2^{-n}} = \frac{1}{2\varepsilon^{2t}} \tag{4}
$$
so that
$$
 \frac{e(\lvert\operatorname{supp} D \rvert+t)}{t} \geq \frac{1}{2^{1/t}\varepsilon^{2}} \tag{5}
$$

Rearranging and recalling again the choice of $t$ in (3) yields
$$
 \lvert\operatorname{supp} D \rvert\geq  \Omega\!\left(\frac{n}{\varepsilon^{2}\log(1/\varepsilon)} \right) \tag{6}
$$
as claimed.


Decentralized algorithm for determining influential nodes in social networks In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social networks.

Basically the algorithm goes as follows:

$S = {\rm empty~set}$
pick the node with highest individual influence, call it $v_1$; $S = S\cup v_1$
remove $v_1$ and all edges connecting $v_1$ to the rest of the network
repeat until $S$ has $k$ vertices

I have two questions about influential nodes in social networks.
a) Is there any algorithm to find the solution, or an approximation of it in a decentralized fashion?
b) Did anyone apply other algorithms, such as Page-Rank and similar, to solve the same problem?

Decentralized algorithms for variants of this problem have been published in A distributed and privacy preserving algorithm for identifying information hubs in social networks and  Social Influence Analysis in Large-scale Networks.


What is known about the complexity of finding minimum circuits for SAT? What is known about the complexity of finding minimal circuits that compute SAT up to length $n$?

More formally: what is the complexity of a function which, given $1^{n}$ as input outputs a minimal circuit $C$ such that for any formula $\varphi$ with $|\varphi| \leq n$, $C(\varphi) = SAT(\varphi)$?

(I'm specifically interested in lower bounds.)

The naive deterministic algorithm (compute SAT by brute force up to length $n$, then try all circuits in order of size until you find one that correctly computes SAT up to length $n$) takes $\leq 2^{O(n)}$ time to compute SAT, and then an additional $O(2^n 2^M)$ time to find a minimal circuit, where $M$ is the size of the minimal circuit.

  Is there a deterministic algorithm that finds minimal circuits for SAT whose running time is $o(2^n 2^M)$, where $M$ is the size of the minimal circuit?  Or does this imply some complexity collapse?

Here are two things that, although related to my question, are definitely not what I'm asking about (which is, I think, why I found it a little difficult to search for):

The circuit minimization problem: given a circuit $C$ (or a function $f$ given by its truth table, or several other variants) find a minimal circuit $C'$ computing the same function as $C$.  Even if circuit minimization were easy, it would not necessarily imply that the above task is easy, as even computing the function we want to minimize (SAT up to length $n$) is believed to be hard, whereas in the circuit minimization problem the function we want to minimize is free (it's given as the input).
$NP$ versus $P/poly$.  My question is not merely about what size the minimal circuit has; it is about the complexity of finding a minimal circuit, regardless of its size.  Obviously if we can compute minimal circuits in polynomial time then $NP \subseteq P/poly$ (and in fact $NP \subseteq P$, since then the circuit family is $P$-uniform), but the converse need not be true.  Indeed, I believe Immerman and Mahaney were the first to construct an oracle where $NP \subseteq P/poly$ but $P \neq NP$ -- that is, $NP$ has polynomial-size circuits but they cannot be found in polynomial time.

Let's assume that one cannot solve SAT much faster non-uniformly than uniformly. That is, there is a TM M solving SAT in time T(n), and the smallest circuit for SAT has size T'(n) that's not much smaller than T(n) (say, $T(n) = poly(T'(n))$ - in particular this holds if the smallest circuit for solving SAT has size $2^{\Omega(n)}$ which may very well be true).

So, you could get an "almost" minimal circuit by just running some canonical simulation of M by a circuit, in time that's basically optimal (as much time as it takes you to write the output). Just for this reason, am guessing there will be no lower bound for this question based on any "nice" assumption. However, I don't know how to go from an "almost minimal" to actually minimal. One way to do so will be to use the fact that finding the circuit up to size $S$ is a question in the polynomial hierarchy, and so you should be able to solve it in roughly $T(T(n))$ time which will be $2^{o(M)}$ if $T(n)=2^{n^{o(1)}}$.


Fast computation of Frobenius norm under memory limits Given a large dense matrix $A^{n \times n}$, that does not fit to the memory (RAM). Is there any fast way to compute the exact Frobenius norm of the matrix or its accurate approximation (perhaps, via sampling with reasonable bounds provided)? What if this matrix is a subtraction of two $n \times n$ matrices: $\| A - B \|_F$, where $A$ is sparse, and B is dense?

Some of the results depend on the model under which the matrix is presented, but there's a large collection of results that use sampling or sketching techniques to estimate norms accurately. Among some of the key results are:

sketching methods based on the use of 2-stable distributions: these work even if the entries are "streamed in" in some order, and also work if you are presented instead with the A and the B entries.
column sampling methods.

Again, it would be unfair to single out a single paper, also because it's not exactly clear which model you're working in: best to google 'norm estimation' or 'column sampling' to find some of the related results. This survey by Mahoney is a useful reference for sampling methods.


Machine characterization of $SAC^i$ $SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It is known that $SAC^i$ for $i \geq 1$ is closed under complement and $SAC^0$ is not. Also, $SAC^1 = LogCFL$ and hence has a machine characterization, since LogCFL is the set of languages accepted by an $O({\log}n)$ space bounded and polynomial time bounded auxiliary PDA. Are there similar machine characterizations of $SAC^i$ for $i \geq 2$ ?

Yes. Stack heights.  $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$, that is, with $O(\log n)$ space and $O(\log n)$ stack height; this implies $\log n$ configurations and therefore $\log^2(n)$ bits.  We have

$$\mathsf{SAC^k} = \mathsf{NAuxPDA}(\log n, \log^k n);$$

these machines will run in time $2^{\log^{k}(n)}$.  Without restriction on stack height, we will get exactly $\mathsf{P}$.  The result should follow from: W. Ruzzo, Tree-size bounded alternation. JCSS 1980.


Is there a simple game with asymmetric complexity? Consider full information two-player combinatorial games that end after a polynomial number of moves, and in an alternating way, the players picks from a finite number of allowed moves.
The usual question is, how difficult it is to tell from a given position the winner.
Another would be, how difficult it is to pick a winning move from a winning position.
(Here I call a move winning, if the position remains winning after playing it.)
To differentiate, I will call the former POSITION-COMPLEXITY and the latter MOVE-COMPLEXITY.

It is easy to see that if the MOVE-COMPLEXITY is in $P$ or $PSPACE$, then so is the POSITION-COMPLEXITY - we can calculate the optimal moves and check who wins at the end.
(I have not really thought through what happens if the MOVE-COMPLEXITY is in $NP$, probably the POSITION-COMPLEXITY is in something like $P^{NP}$.)
However, there are dummy examples when the MOVE-COMPLEXITY is trivial and the POSITION-COMPLEXITY is arbitrary hard - like the (not very interesting) game of checking what is the output of an algorithm, with the players making the next steps, being allowed only one move.
I have digressed a bit, my main question is the following.

  Is there a natural game, where the MOVE-COMPLEXITY of the two players is different?

For example, the game where the first player picks the values of the variables of a CNF (that might not have a solution), while the second player is trying to solve a SOKO-BAN puzzle (that might not have a solution), is such an example.

Perhaps a fairly natural game is the following:

Player 1 is placed in the middle of a maze and must reach the exit in order to win.

Player 2 is in the same maze and must collect a set of "components" to build  a radio controller that lets him close the exit (and win).

Deciding the next move from a winning position is easy for Player 1: just follow the shortest path from his current position and the exit; but can be very hard for Player 2.
Indeed if the (remaining) components of the radio controller are on the vertices of a grid graph of $n$ nodes (suppose that Player 2 is himself on an adjacent vertex) and the distance between Player 1 and the exit is exactly $n$, then he must find an Hamiltonian path in order to move.

To make the game more "interactive", we can also add some extra actions to Player 2 that can only cause a polynomial slowdown in the calculation of the next move for Player 1; for example allowing him to block a fixed numbers of corridors of the maze.


Bloom filter hashes: more or bigger? In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions.  Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as linear combinations thereof.

My question is: what, really, is the difference between two hash functions and one with twice the entropy?

This comes from looking at what you actually do with the output of your hash functions: you're going to take your (say) 64-bit hash value and scale it to the size of your bit vector, which is probably significantly smaller than 264.  This is clearly an entropy-losing transformation (except in the rare case your hash size and filter capacity exactly coincide).  Assuming my filter has less than 232 entries, what's to stop me from splitting my 64-bit hash value into two 32-bit hashes and taking linear combinations of those?  Or using it to seed a PRNG?

In other words, how much information do I actually need to know about each element I insert into a Bloom filter to ensure the standard false positive rate holds?  Or more generally, what is the relationship between how well I can distinguish elements (how many bits I use to describe them) and how my Bloom filter performs?

It sure seems like I can get away with $2\lg(m)$ bits for a filter size of $m$, or equivalently $2(\lg(-n\ln{p}) - 2\lg(\ln2))$ bits to store $n$ elements with false positive probability $p$....

You're right to think of hash functions in terms of "random bits produced".  So if you have a hash function that produces a 64 bit hash, you can treat is as 4 16-bit hashes (by splitting), and so on.

For the scheme described above (which should be attributed to Dillinger and Manolios;  Kirsch/Mitzenmacher just analyzed it), that means you're correct; if you have a single hash function with $2 \lg(m)$ bits, you should be fine.


Can we sort without permutations? It is well-known that sorting permutations by transposition is in $\sf{P}$, as the minimum number of transpositions required to sort $\pi \in S_n$ is exactly $inv(\pi) = \{ (i,j) \in [n] \times [n] : i < j \text{ and } \pi(i) > \pi(j) \}$. This notion of "inversion number" has also applications in algebraic combinatorics, for instance it allows to endow $S_n$ with a structure of lattice, called the permutohedron and based on the weak Bruhat order.

It can be illuminating to recast the problem in group-theoretic terms. We are given a group $G$ with generator set $\Gamma$ and a mapping $i_G : \Gamma^* \rightarrow G$, and another group $H$ on which $G$ acts transitively, and we want to solve the following problem: given $h \in H$, find a minimum-length $w \in \Gamma^*$ such that $i_G(w).h = 1_H$. In the permutation case, $G = H = S_n$ and $\Gamma$ is the set of transpositions.

Question: are there other instances of this problem which admit efficient algorithms?

I don't have a definite answer to your question, but "braid sorting" seems a possible candidate. According to this wikipedia entry we can define it as follows. Let $X$ be a group, and let $H$ denote the set of tuples $(x_1,\ldots,x_n) \in X^n$ such that $x_1 \ldots x_n = 1_X$. If we let $G$ be the braid group $B_n$ generated by the moves $\sigma_i$,  we can define an action of $B_n$ over $H$ by:

  $\sigma_i(x_1,\ldots,x_n) = (x_1,\ldots,x_{i-1},x_{i+1},x_{i+1}^{-1} x_i x_{i+1},\ldots,x_n).$

That is to say, $\sigma_i$ combines the effect of a swap and a conjugation at positions $i$ and $i+1$. It might be possible to solve this problem optimally in polynomial time, which would  answer to your question.


What is the correct definition of $k$-tree? As the title says, what is the correct definition of $k$-tree? There are several papers that talk about $k$-trees and partial $k$-trees as alternative definitions for graphs with bounded treewidth, and I've seen many seemingly incorrect definitions. For example, at least one place defines $k$-trees as follows:

  A graph  is called a $k$-tree if and only if either $G$ is the complete graph with $k$ vertices, or $G$ has a vertex $v$ with degree $k − 1$ such that $G \setminus v$ is a $k$-tree. A partial $k$-tree is any subgraph of a $k$-tree.

According to this definition, one can create the following graph:

Start with an edge $(v_1, v_2)$, a $2$-tree.
For $i=1\ldots n$, create a vertex $v_i$ and make it adjacent to $v_{i-1}$ and $v_{i-2}$.

Doing this would create a strip of $n$ squares with diagonals. Similarly, we can start creating a band from the first square in a direction orthogonal to the strip above. Then, we would have the first row and first column of an $n \times n$ grid. Filling in the grid is easy by creating vertices and joining them to the vertices to its above and to its left.

The end result is a graph that contains an $n\times n$ grid, which, in effect, is known to be of treewidth $n$.

A correct definition of $k$-trees has to be the following:

  A graph is called a $k$-tree if and only if either $G$ is a complete graph with $k$ vertices, or $G$ has a vertex $v$ with degree $k-1$ such that the neighbor of $v$ forms a $k$-clique, and $G \ v$ is a $k$-tree.

Then, the grid-like graph described as above cannot be created.

Am I correct?

I basically agree with you, with just a tiny modification:

  A graph $G$ is a $k$-tree if and only if either $G$ is a complete graph with $k+1$ vertices, or $G$ has a vertex $v$ such that the (open) neighborhood of $v$ forms a $k$-clique, and $G - v$ is a $k$-tree.

In other words, $v$ should have degree $k$, instead $k-1$ in your definition.

I personally prefer the bottom-up definition, but this is just a matter of taste:

  The complete graph on $k+1$ vertices is a $k$-tree.
  A $k$-tree $G$ with $n+1$ vertices ($n\ge k+1$) can be constructed from a $k$-tree $H$ with $n$ vertices by adding a vertex adjacent to exactly $k$ vertices that form a $k$-clique in $H$.
  No other graphs are $k$-trees.

This definition is a slightly modified version of the definition from Pinar Heggernes' lecture notes.


Chomsky normal form method: CYK parser performance implications? Chart parsers can be implemented based on Chomsky normal form or
directly based on production rules. Lets for the moment assume
we have a CYK chart parser that uses Chomsky normal form. The
binarization is not uniquely defined. Does this impact the
performance of the CYK chart parse. Can this be exploited to
improve the performance of a CYK chart parser?

While the obvious answer is that the fundamental complexity can't change, there may be better or worse algorithms for parsing the strings you're actually going to encounter. However, it seems like the issue is less the relative frequency of individual grammar productions (the A's, B's, and C's in the question) and more an issue of the unused, dead end parses that one binarization versus another may produce.

With a bit of searching I found Better Binarization for the CKY Parsing (Song, Ding, and Lin, EMNLP 2008), which seems to definitively conclude that you can pick a "better" or "worse" binarization relative to the strings you actually expect to have to parse. Their name for the "dead end parses" that one would hope to minimize in practice seems to be incomplete constituents, and there is a good example on the first page.


Cantor's theorem in type theory Cantor's theorem states that

  For any set A, the set of all subsets of A has a strictly greater cardinality than A itself.

Is it possible to encode something like this using only types / propositions without referring to ZFC sets? Code or pseudocode for encoding this proposition in a dependently typed language would be appreciated.

Short answer: yes! You don't need that much machinery to get the proof to go through.

One subtlety: it seems on the face of it that there is a use of the excluded middle: one builds a set $D$ and a number $d$, and shows that either $d\in D$ or $d\not\in D$ which leads to a contradiction. But there is a lemma, true in intuitionistic logic, that states:

$$ \mbox{ for all statements } P, (P\iff \neg P) \Rightarrow \bot$$

This suffices, along with the usual proof. Note that in general "surjection" may have some subtle nuance in constructive/intuitionistic logic (without choice) so you have to make due with "right invertible" instead.

A very standard proof in Coq (which for some reason I couldn't find online) might go as follows:

Inductive right_invertible {A B:Type}(f : A->B):Prop :=
| inverse: forall g, (forall b:B, f (g b) = b) -> right_invertible f.

Lemma case_to_false :  forall P : Prop, (P <-> ~P) -> False.
Proof.
  intros P H; apply H.
    - apply <- H.
      intro p.
      apply H; exact p.
    - apply <- H; intro p; apply H; exact p.
Qed.

Theorem cantor :  forall f : nat -> (nat -> Prop), ~right_invertible f.
Proof.
  intros f inv.
  destruct inv.
  pose (diag := fun n => ~ (f n n)).
  apply case_to_false with (diag (g diag)).
  split.
  - intro I; unfold diag in I.
    rewrite H in I. auto.
  - intro nI.
    unfold diag. rewrite H. auto.
Qed.

Of course, the "right" framework in which to think about these maters, which can be seen as the minimal requirements for this proof to go through, is Lawvere's fixed point theorem which states the the theorem holds in every Cartesian Closed Category (so in particular, in any reasonable type theory).

Andrej Bauer writes beautifully about this theorem in the paper On fixed-point theorems in synthetic computability, and I suspect might have some interesting things to add to this answer.


Temporal Logic and Access Control Models What is the best way to describe the semantics of a new access control model?. I heard the temporal logic is the way to go. Is it true?

There were a lot of publication on extending and or formalizing RBAC/SOD with LTL or other flavors of temporal logics, not sure of other AC models. Google Scholar (or simple google) search with yield a bunch of articles. Most of them might be not sufficiently formal for somebody like yourself, yet might be of some interest. Not sure is LTL the best way. Yet for a hammers everything is a nail, so if temporal logic is your specialty you might be more successful with it than without.. Consider also traditional programming language semantics approaches such as Z and alike, Game Theoretical/Modular/HyperProperties, dedicated logics. Totally depends on your AC.

Check example articles and see what you feel is the way
https://www.sciencedirect.com/science/article/pii/S1571066109003107


Kolmogorov Complexity applications in Number Theory What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.)

One of the nice proofs i have come across is the proof of the existence of infinite number of primes, using the definition of Kolmogorov Complexity and the compression factor.

Also, what is the importance of Kolmogorov Complexity in Cryptography?

Every integer has an associated Kolmogorov complexity; the shortest program that prints that integer.

There are $\approx {x \over ln(x)}$ primes up to $x$ so primes have lower Kolmogrov complexity than composites on average; $\approx ln({x \over ln(x)})$    vs  $\approx ln(x)$.

As a side effect you have to have some large gaps between primes; otherwise you could encode every number as the previous prime plus some small number of bits.


Generalizations of planar graphs that include hypercubes with large side length in $R^d$ A lot of people have asked about generalizations of planar graphs on other forums. Some topics include:

https://mathoverflow.net/questions/7650/generalizations-of-planar-graphs
https://math.stackexchange.com/questions/22714/higher-dimensional-analog-to-planar-graphs

Many have talked about minor-closed family generalizations of planar graphs, but they cannot possibly include even 3D n by n by n grids. If they did, then n by n by n grids would have to have balanced separators of size $n^{3/2}$, but in reality all of their balanced separators have size at least $n^2$. Qiaochu's definition focuses more on the direction that I am interested in. Ideally, I would like to look at graphs that are 1-skeleta of $(k-1)$-dimensional cell complexes that can be embedded in $\mathbb{R}^k$ injectively (which may be the same thing that Qiaochu is looking for). These are not minor closed for $k\ge 3$, but might be face-contraction closed.

Have these graphs been studied algorithmically? For example, can one generalize the planar separator theorem to these graphs? Or is there something particularly nasty about this definition that I am overlooking that prevents these objects from being algorithmically interesting?

You may want to look at nowhere dense graphs.
http://www.sciencedirect.com/science/article/pii/S0195669811000151

One of the reasons why minor-closedness is natural is the following. We typically want to work with families of graphs rather than specific graphs. And we want to solve problems with arbitrary weights/capacities on edges/nodes. Suppose we want to solve the shortest path problem in a family of graphs. Then, if we allow for zero length and infinite lengths then basically we are allowing minor operations on the family. In some settings it makes sense to work with unweighted graphs where positive results can be obtained for larger families of graphs that are not necessarily minor-closed.


Has this generalization of the vertex cover problem been researched? I have the following problem, let's call it the $n$ vertex cover:

  Given a directed graph $G,$ find a minimum subset of vertices $S$ such that each trail of length $n$ has at least one vertex in $S$.

Has this problem been researched before? Is there a good way to approximate $S$?

A trail is a walk in which no edge appears twice, but vertices are allowed to repeat. I am also interested in variants where we consider paths or walks instead of trails.  Here $n$ is a small constant that is not part of the input; in my application, $n$ is probably something like 5.

This problem has been studied at least for paths. The problem is NP-complete for any $n \geq 2$ (see for example this).

It is know that the problem is hard even for very special graph classes. For example, in the case $n = 3$, it is NP-hard for cubic planar graphs of girth 3.

On the positive side, there are constant-factor approximations algorithms, at least for some special cases.


Conditioning Probability on a Language With Measure 0 Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you can think of an infinite word $w$ over $\Sigma$ as a result of tossing the n-sided coin infinitely many times.
With this view, I can think of $\omega$-regular langauges over $\Sigma$ as events. There are interesting languages that have measure $0$. For example, consider the language $L = \bigcup\limits_{i\in \Sigma } \Sigma^* \cdot (\Sigma \setminus \{i\})^\omega$. That is, $L$ consists of all infinite words over $\Sigma$ that have finitely many $i$'s, for some $i$.
Now I am interested in computing $P(L_2|L)$ for some language $L_2 \subseteq L$. Sometimes, I can guess the answer by "symmetry" considerations in case $L$ and $L_2$ are "simple" enough, but my question is: how can I condition on a language $L$ which is of measure $0$ in the general case?
Example:
assume again that $L = \bigcup\limits_{i\in \Sigma } \Sigma^* \cdot (\Sigma \setminus \{i\})^\omega$. Consider the following event (or language):
$$ L_2 = L\setminus \{ w \in \Sigma^\omega: \text{$w$ has finitely many 1's, and every $j\neq 1$ appears infinitely often in $w$}\}$$
What is $P(L_2|L)$? In other words, how can I compute the fraction of words that I did not through out from $L$.
I believe there is a way to condition on a language of measure $0$ but I'm not sure how. A similar simple situation appears in the following: one can sample a random $(x, y)$ point in a rectangle $[0, 1]\times [0, 1] \subseteq\mathbb{R}_2$ and then ask what is the probability $P(y \geq \frac{1}{2} | x = \frac{1}{2})$. Clearly, this probability is $\frac{1}{2}$ although we condition on the line $x = \frac{1}{2}$ which has measure $0$ in $[0, 1]\times [0, 1]$. The way I think about the line-rectangle example is as follows. I imagine the line $x = \frac{1}{2}$ as a rectangle of width $\epsilon \to 0$. Is there a similar approach that can be adapted to $\omega$-reuglar languages?

I don't know of a general approach to handle this, but in the case of $\omega$-regular languages, this has been done.
One approach, which I think is first introduced in the paper Computing Conditional Probabilities
in Markovian Models Efficiently is the following:
Given the language $L$, let $D$ be a DPW for it. Now, start by constructing a Markov chain $M$ that captures your distribution on $\Sigma^\omega$ (uniform, in your case).
Then take the product of $M$ and $D$.
Now, in the product MC, you have the property that the probability that the run is accepting is exactly the probability of $L$ (0, in your case, but it works for any $L$).
We now modify the product by "redistributing" the probability: whenever the MC reaches an end-component (ergodic component) in which the probability of acceptance is 0, the run restarts in the initial state. This ensures that all $0$-probability-of-acceptance runs get "another chance".
You can use this to essentially restrict yourself only to words in $L$, and now you can ask what the probability of another language is, in this MC, and this provides a reasonable definition of conditional probability.
I'm slightly sketchy on the details, but I think this should work.
I've used this technique in a paper here: https://arxiv.org/abs/1608.06567.


Can Isorecursive types capture mutually recursive data types? I've been reading TAPL, and reached the section on recursive types. I understand the type operator $\mu$. For example, the two type expressions are equivalent

NatList = {nil: Unit, cons: (Nat, NatList)}

and
$$ \mu X. 1 + \text{Nat} \times X $$

I'm confused how I would, using the $\mu$ operator, describe mutually recursive types such as

Forest = List<Tree>
Tree = (Value, Forest)

Obviously the type above can be reduced to a single type

Tree = (Value, List<Tree>)

But is there any way to write this using type-theoretic notation? Specifically I am wondering how the isorecursive operations fold and unfold operate on mutually recursive types, since I feel like unfold would have to expand both the definition of Tree and of Forest.

In general, for any type (or domain, or complete lattice) $X$ we can consider the least fixed-point operator $\mu_X : (X \to X) \to X$. For recursive types we take $X = \mathsf{Type}$, i.e., we apply $\mu$ at the universe of all types. Given a system of mutually recursive equations
\begin{align*}
A &= F(A, B)\\
B &= G(A, B)
\end{align*}
where $F, G : X \times X \to X$, rewrite this as a single equation
\begin{align*}
(A,B) = (F(A,B), G(A,B))
\end{align*}
and then define $H : X \times X \to X \times X$ by $$H(A,B) = (F(A,B), G(A,B))$$ so that the original system becomes an ordinary fixed point equation
$$P = H(P)$$
where $P = (A, B)$. This shows that mutual recursion at $X$ is ordinary recursion at $X \times X$. In terms of the $\mu$-operator we may therefore solve the original system as
$$(A,B) = \mu_{X \times X} P . (F(P), G(P)).$$
In the case of recursive types, just set $X = \mathsf{Type}$.

We may further wonder whether we can replace $\mu_{X \times X}$ with two nested applications of $\mu_X$, i.e., perhaps it is the case that
$$\mu_{X \times X} P . H(P) = \mu_X A . \mu_X B . H(A, B),$$
or something like it. Indeed, Bekić's Lemma [1] explains how to compute the fixed point on $X \times X$ in terms of fixed points on $X$, namely
$$\mu_{X \times X} (A,B) .(F(A,B), G(A,B)) = (A_0, B_0)$$
where
\begin{align*}
A_0 &= \mu_X A . F(A, \mu_X B . G(A,B)), \\
B_0 &= \mu_X B . G(A_0,B).
\end{align*}
Note however that the inner $\mu_X$ in $A_0$ computes a fixed point in the presence of a free parameter $A$, which may be tricky depending on the exact situation.

In summary, you have a choice in solving systems of recursive type equations: either you generalize $\mu$ to pairs of types, or you allow parameters to appear when you apply $\mu$.

[1]: Hans Bekić (1969) Definable operations in general algebras, and the theory of automata and flowcharts. Published posthumously in: Jones C.B. (eds) Programming Languages and Their Definition. (1984) LNCS, vol 177.


Most frequent $aXa$ substring Let $s\in\Sigma^*$ be a string, for some alphabet $\Sigma$.
We want to find the most frequent repeated substring $q$ of $s$ such that its first character equals its last one, i.e. the most frequent repeated substring of type $q=aXa$ for $a\in\Sigma, X\in \Sigma^*$.

Can we solve this problem with standard techniques ? I'm thinking about suffix-trees here. What is the most efficient algorithm for this problem ?

Yes, you can solve the problem using standard techniques. However, the question may easily be homework, so here is just a hint:

You never need to consider words of the form $aXaYa$, as they cannot be the only most frequent ones.


Intuitionistic fragments of classical logic For what conditions on P and Q, does P ⊢ Q in classical logic imply P ⊢ Q in intuitonistic logic (for higher-order logic, though of course results for more restricted logics are relevant too)?

As requested, I'm turning my comment into an answer:

For first order logic, the term you want to search for is “Glivenko classes”. Probably, very similar characterizations and techniques apply for higher order logic. See Sara Negri's Glivenko sequent classes in the light of structural proof theory.


What are some examples of sequential-decision tasks? I ask this because I'm currently learning about Neural Networks as a subset of the machine learning algorithms

Just trying to get some intuition on what sort of problems out there are categorized as "sequential" while others "non-sequential"

Thanks :)

One kind of sequential problem is making control decisions in real time. Consider the problem of driving a vehicle. The system will have a state, you can observe some measurements, and you must make a decision. You decision generates and input which then affect the future state of the vehicle and the whole process repeats. A problem which interacts with an external entity that changes its behavior based on a decision is sequential in nature. Other examples include things like optimally managing a stock portfolio, searching for an evading opponent, optimally playing a card game.

One non-sequential problem is classifying the fruit on a scanner in a grocery store. A measurement is taken, the data is processed and and output is determined. When the output generated does not alter the nature of of future outputs, it is non-sequential.


Transitive feedback arc set (TFAS): NP-complete? Some time ago, I posted a reference request for graph problems where we want to find a 2-partition of the edges where both sets fulfill a property not related to their cardinality. I was trying to prove that the following problem is NP-hard:

  Given a tournament $G = (V,E)$, is there a feedback arc set $F \subseteq E$ in $G$ that defines a transitive relation?

I do have a construction for an attempt at a proof, but it seems that that is going to run into a dead end, so I thought I might ask here to see whether I'm missing something obvious. In order to not confine your creativity to lines of thought similar to the ones I used, I won't post my attempt here.

Is this problem NP-hard? If so, how to prove it?

To add a little context, here's a construction for a graph that doesn't have a transitive feedback arc set. For this construction, I'll use the following gadget graph:

This tournament has the following properties (which I checked using a program, I didn't prove it formally):

if (2,7) is not in a given TFAS, then (1,3) is
if (5,1) is in a given TFAS, then so is (3,6)
if (7,3) is in a given TFAS, then (5,1) is not

or slightly abusing predicate logic notation:

$\neg (2,7) \rightarrow (1,3)$
$(5,1) \rightarrow (3,6)$
$(7,3) \rightarrow \neg (5,1)$

You'll notice that for each implication, the two edges are pairwise disjoint, so the following construction works:

I hope you can make out the idea of the graph: using the implication properties of the tournament above, we can construct a graph in which each transitive feedback arc set both includes and doesn't include the edge $A$, i.e. a contradiction, which means the graph doesn't have a transitive feedback arc set. Any completion of that graph cannot have one either since the same contradiction will remain in any completion. I left out a large number of vertices, all of which can be derived from substituting the tournament above for the implications.


Defintion of a Data Structure? Lately I have been looking around for a formal definition of a what a data structure is. I cannot find neither a paper, nor a book with such a definition. Even the famous "The Art of Computer Programming" is missing one. Even for just a linked data structure, e.g., binary search tree, I couldn't find one.

So, is there one? Perhaps a paper that is talking about it?

By formal definition I'm thinking of something like "A data structure is a tuple (Op, El, ..) where ...".

Data structures is nothing but the ways how data of different kinds can be structured in a systematic way. The actual definition may be somewhat lengthy and descriptive which can be found on different sources. But it is all about defining structures of your data that will satisfy your need to solve any particular problem.


When are two algorithms said to be "similar"? I do not work in theory, but my work requires reading (and understanding) theory papers every once in a while. Once I understand a (set of) results, I discuss these results with people I work with, most of whom do not work in theory as well. During one of such discussions, the following question came up:

When does one say that two given algorithms are "similar"?

What do I mean by "similar"? Let us say that two algorithms are said to be similar if you can make either of the following claims in a paper without confusing/annoying any reviewer (better definitions welcomed):

Claim 1.  "Algorithm $A$, which is similar to algorithm $B$, also solves problem $X$"

Claim 2. "Our algorithm is similar to Algorithm $C$"

Let me make it slightly more specific. Suppose we are working with graph algorithms. First some necessary conditions for the two algorithms to be similar:

They must be solving the same problem.
They must have the same high level intuitive idea.

For instance, talking about graph traversal, breadth-first and depth-first traversal satisfy the above two conditions; for shortest-path computations, breadth-first and Dijkstra's algorithm satisfy the above two conditions (on unweighted graphs, of course); etc.

Are these also sufficient conditions? More specifically, suppose two algorithms satisfy the necessary conditions to be similar. Would you indeed call them similar, if

they have different asymptotic performance?
for a special class of graphs, one algorithm requires $\Omega(n)$ time while the other requires $O(n^{1/3})$ time?
they have different terminating conditions? (recall, they are solving the same problem)
the pre-processing step is different in the two algorithms?
the memory complexity is different in the two algorithms?

Edit: The question is clearly very context dependent and is subjective. I was hoping that the above five conditions, however, will allow getting some suggestions. I am happy to further modify the question and give more details, if needed to get an answer. Thanks!

It is a tough problem to give even a coherent definition of "Algorithm A is similar to Algorithm B". For one, I don't think that "they must be solving the same problem" is a necessary condition. Often when one says in a paper that "the algorithm $A$ of Theorem $2$ is similar to the algorithm $B$ in Theorem $1$", the algorithm $A$ is actually solving a different problem than that of $B$, but has some minor modifications to handle the new problem.

Even trying to determine what it means for two algorithms to be the same is an interesting and difficult problem. See the paper "When are two algorithms the same?" http://research.microsoft.com/~gurevich/Opera/192.pdf


Variant of Subset Sum Problem with Changing Bound Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T $ and a positive real $k\geq 1$, find a subset $S$ such that
$$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$
$$s.t., \sum_{i\in S/\{t\}} a_i \leq k \cdot a_t,$$
where $a_t$ represents the smallest one of subset $S$.

Note that $a_t$ is the smallest of set $S$ and may be different for different set $S$. I am wondering whether this problem is still NP-complete. Any comments or suggestions will be very appreciated.

It's still NP-complete, via a reduction from the partition problem (in the form of: given a collection of $n$ positive numbers $x_i$, where $n$ is even, partition the numbers into two subsets with equal sums). This exact form of the partition problem is not one of the ones mentioned by Garey and Johnson (SP12); in particular they don't mention the constraint that the numbers be positive. But they do mention a variation of partition in which the numbers are paired and you have to use one from each pair. By adding the same positive number to both numbers in a pair you can make them all positive, and then by adding different large powers of two to different pairs you can get an instance where
the one-from-each-pair constraint is the only way to solve it, and doesn't need to be specified as an explicit constraint.

In the partition problem, we can assume without loss of generality that $\sum x_i=1$, since multiplying or dividing the inputs by a scalar doesn't change the problem. We'll also assume that $n$ is even, since that's what you get from the reduction from the paired variation of partition. Thus, we are trying to find a subset whose sum is $1/2$. Note that, if there is such a subset, then its complement is also a solution; in particular, one of the two solutions has at least $n/2$ elements.

Given such a partition instance, set up an instance of the changing-bound problem with $T=2n$ input values: $n$ of them of the form $1+x_i$, and another $n$ of them that are all equal to $1$. Set $k=(3n-1)/2$. Because $k$ is so large, any near-optimal solution must include at least one of the values that is equal to $1$, so this will necessarily be the minimum value. The goal of the changing-bound problem is then to have the sum of the whole set (including its minimum) come as close as possible to $(3n+1)/2$ without exceeding it. If the partition problem has a solution, then we can turn it into a solution to the changing-bound problem that exactly reaches this goal of $(3n+1)/2$, by choosing a partition solution with at least $n/2$ elements and padding them with the desired number of $1$s. And conversely, if the changing-bound problem has a solution with the exact value $(3n+1)/2$, then the subset of this solution consisting of the values of the form $1+x_i$ also give a solution to the partition instance.


What is the Turing degree of Kleene's O? It's not computable whether a number is a member of Kleene's ${\mathcal {O}}$. What is that set's Turing degree? I can almost see an argument that ${\mathcal {O}} \leq_T \emptyset^{(2)}$ but I can't see how to be sure that the set I'm thinking of is the smallest that meets the criteria. It also seems plausible that ${\mathcal {O}} =_T \emptyset^{(\omega_{CK})}$. Is this known?

There is a talk given by Stephen Simpson, located here http://www.personal.psu.edu/t20/talks/pisa0104/talk.pdf, where he discusses the relative consistency strengths of various subsystems of second-order arithmetic $Z_2$. In particular, the theory $\Pi^1_1-CA_0$ denotes a subsystem of $Z_2$ whose set of true $\Pi^1_0$-consequences is of Turing degree $\emptyset^{(\omega^{CK}_{1})}$, which is the Turing degree corresponding to Kleene's $\mathcal O$. However, no proof is given, but I'm sure that one can be found in his bibliography for the talk (or perhaps even in his text on reverse mathematics http://www.personal.psu.edu/t20/sosoa/).

The relevant information in the PDF is on page 29.


Hitting sets with a subfamily Let $F$ be a family of $d$-element subsets of a finite universe $U$ of objects.
A family $H$ of $k$-element subsets of $U$, with $1 \le k < d$, is a $(k,d)$-hitting-set of $F$ if for each $V \in F$ there exists at least one set $W \in H$ such that $W \subset V$.

Given a collection $F$ as above, the $(k,d)$-hitting-set problem is to find a smallest $(k,d)$-hitting-set $H$ for $F$.

When $k = 1$ we have the standard hitting-set problem, and there are lots of previous results for it.
I know of parameterized analyses for the case with $k = 1$ and $d \le 3$ (see Brankovic and Fernau, for example).

Does anyone know any results regarding the complexity or the hardness of approximation of the $(k,d)$-hitting-set problem with:

$k = 1$ and $d = 4$?
$d = 4$ and $1 < k < d$?
$1 \le k < d$ and $d$ arbitrary?

For a constant $d$ the $(k,d)$-hitting set problem is not harder than the original $d$-hitting set (i.e. $k=1$) in view of both approximation and parametrized complexity.
There is a simple reduction from $kd$-HS to $d$-HS. For an instance $(U,\mathcal{F},d,k)$ of the first problem we get an instance of $(U',\mathcal{F'},d)$ of the second one in which every element $e \in U'$ corresponds to a $k$-element subset of $U$, and each set in $\mathcal{F'}$ corresponds to a set in $\mathcal{F}$ in the same way (i.e. mapping all $k$-element subsets of $U$ to elements in $U'$). Since $k$ is a constant the size of new instance is a polynomial function of the size of the first instance ($O(n^k)$).
A hitting set for the first problem corresponds to a hitting set of same cardinality for the second problem and vice versa, hence the reduction is approximation preserving.


Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time? This question is about subset problems (the solution is a subset of the instance, so trivially enumerable in $2^n \cdot n^c$ time), and the parameter is the solution size, so-called the standard parameterization.

The answer to the question in the title is obviously yes: the clique problem on sparse graph ($m = O(n)$) remains W[1]-hard but can be trivially solved in $2^{o(n)}$ time. The trick here is that the solution can never be $\omega(\sqrt n)$. So to make the question nontrivial, we have the requirement that

$f_k(n)$ is an unbounded function for any $k$, where $f_k(n)$ is the number of instances with instance size $n$ and optimal solution size $k$.

Informally speaking, the W[1]-hardness characterizes the hardness of instances with extremely small solutions, while the subexponentional solvability concerns with the solution being almost half of the instance size. So it seems perfectly fine that such a problem exists (?).

How about Planar Capacitated Dominating Set? It is W[1]-hard (see the paper by Bodlaender, Lokshtanov, Penninkx in IWPEC 2009), but should be solvable in $2^{O(\sqrt{n}\log n)}$ by using the fact that planar graphs have treewidth $O(\sqrt{n})$.

In this problem we are given a graph with integer capacities on the vertices. We are asked to select a minimum size dominating set, with the added restriction that a selected vertex can dominate at most as many of its neighbors as its capacity. Even though the solution is not exactly a subset of $V$, I think it is known that, if we are given a supposed dominating set $D$ we can check if it can be turned into a valid (capacity-respecting) solution in polynomial time by reduction to Max Flow.


D. Knuth definition of a computational method I am new to the site and I hope after reading the guide lines i am in line with them.
I am reading The Art of Computer Programming by Donald E. Knuth. The question is addressed to those having a copy of Volume 1. At pages 27-28, Knuth formally defines a computational method to be a quadruple (Q, I, $\omega$, f). I am interested in the first computational method.

1/ Then he goes on defining Q as being states of the computation. What exactly are states of computations?

2/ The Euclid algorithm on page 22 is formalized in the defined computational method, but if Q is made up of (m,n), (n), (m,n,r,1), (m,n,r,2) and (m,n,p,3) are those the states of computation and how do you come up with them? and how does one recognize them from an algorithm. more precisely, how do you translate a given algorithm into the given computational method?

3/ How are the values of f deduced from the algorithm?

P.S. In case my question is vague please mention in comments where i need to make things clear.
And I am more after understanding the theory than any algorithm usefulness, hope that will be useful.

1/ Then he goes on defining Q as being states of the computation. What exactly are states of computations?

Q consists of the input $I$, output $\Omega$, and all the intermediate "states" or values during the computation. (it will be clear in the Euclid example.)

  2/ The Euclid algorithm on page 22 is formalized in the defined computational method, but if Q is made up of (m,n), (n), (m,n,r,1), (m,n,r,2) and (m,n,p,3) are those the states of computation and how do you come up with them? and how does one recognize them from an algorithm. more precisely, how do you translate a given algorithm into the given computational method?

Yes, those are the states of computation. Note that the input $I$ consists of all pairs of $(m,n)$, which can be seen as the initial state, and $\Omega$ consists of all singleton $(n)$, which is the output and final computation state. The quadruples ends with 1,2,3 define various states of the computation and how $f$ maps each of those states corresponds to the various steps of the Euclid's algorithm as he described earlier in the book.

Now let's run through the steps.

  $f((m,n)) = (m,n,0,1);$

this just says that given an initial input of (m,n), the algorithm will transform into "state #1" of the computation. How $f$ handles state #1 is defined below. Note that the value 0 here is simply a placeholder, because the 3rd value in the quadruple is ignored in "state #1".

  $f((n)) = (n);$

given a singleton (only obtained as the final result), it is mapped to itself, which indicates the termination of the computation.

  $f((m,n,r,1)) = (m, n, m\bmod n, 2);$

this is the first step of the Euclid's algorithm. Given $(m, n)$ (note, value $r$ is ignored here.), compute the remainder of $m$ divided by $n$ and this new state will be mapped as follows:

  $f((m,n,r,2)) = (n)$ if $r = 0$, $(m,n,r,3)$ otherwise;

note the $r$ is the remainder computed in the 1st step. If $r=0$, then this state is mapped to the singleton $(n)$, which indicates the termination of the algorithm because $(n) \in \Omega$, which means $f((n)) = (n)$. Else, it's mapped to another state and how $f$ handles this state is defined below:

  $f((m,n,p,3)) = (n,p,p,1)$

Here $p$ gets the value of $r$ from the previous step. $p$ is introduced because $p >0$ as opposed to $r>=0$. This is the final step in Euclid where $m\gets n, n\gets r$, and a new state is produced with those values and f will handle this state according to "state rule #1" as defined earlier (basically computation returns to step 1).

  3/ How are the values of f deduced from the algorithm?

I guess you mean the final output, which is $(n)$.

hopefully this helps!


Continuous mathematics and formal language theory Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics.

For example, solving the intersection non-emptiness problem for a context-free language and a regular language.

Lamine commented on the connection to the Chomsky-Schützenberger enumeration theorem. Recently, a few research problems in formal language theory were solved using continuous mathematics via this connection. For example:

Hermann Gruber, Jonathan Lee, and Jeffrey Shallit. Enumerating Regular Expressions and their Languages. available online at arxiv.org as arXiv:1204.4982, 2012
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
A Hitchhiker's Guide to descriptional complexity through analytic combinatorics. Theor. Comput. Sci. 528: 85-100 (2014)
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
Average Size of Automata Constructions from Regular Expressions. Bulletin of the EATCS 116 (2015)
Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
On the Average Complexity of Partial Derivative Automata for Semi-extended Expressions. Journal of Automata, Languages and Combinatorics 22(1-3): 5-28 (2017)

The first two of the above references also give a survey of the mathematical and/or historical background.


Type system based on naive set theory As I understand, in computer science data types are not based on set theory because of things like Russell's paradox, but as in real world programming languages we can't express such complex data types as "set that does not contain itself", can we say that in practice type is an infinite set of its members where instance membership is defined by of number of features that are intrinsic to this type/set (existence of certain properties, methods)? If no what would be the counterexample?

The main reason for avoiding sets in semantics of types is that a typical programming language allows us to define arbitrary recursive functions. Therefore, whatever the meaning of a type is, it has to have the fixed-point property. The only set with such a property is the singleton set.

To be more precise, a recursively defined value $v$ of type $\tau$ (where typically $\tau$ is a function type) is defined by a fixed-point equation $v = \Phi(v)$ where $\Phi : \tau \to \tau$ can be any program. If $\tau$ is interpreted as the set $T$ then we would expect every $f : T \to T$ to have a fixed point. But the only set $T$ with this property is the singleton.

Of course, you could also realize that the culprit is classical logic. If you work with intuitionistic set theory, then it is consistent to assume that there are many sets with fixed-point property. In fact, this has been used to give semantics of programming language, see for example

  Alex Simpson, Computational Adequacy for Recursive Types in Models of Intuitionistic Set Theory, In Annals of Pure and Applied Logic, 130:207-275, 2004.