A simplified version of card game Winner I've asked this problem in MathOverflow, without any satisfactory answer.

Consider the following two-player game, which is a simplification of the card game called Winner.  (The following formulation was taken from a comment by Guillaume Brunerie on MathOverflow.)

There are two players A and B. Each player has a set of cards (a subset of $\{1,\dots,n\}$), visible from both players. The aim of the game is to get rid of its own cards. The first player plays any card on the table, then the other player must play a (strictly) bigger card, and so on until one of the players cannot play or decides to pass. Then the cards on the table are discarded, and the other player start again by playing any card (which will be followed by a bigger card). And so on until one of the two players run out of cards and win the game.

I want to know the best strategy for the players (if he can win).

Formal definition

Denote by $w(i,A,B)$ the configuration of the game where the set of the first player's cards is $A$, the set of the second player's cards is $B$, and the largest card on the table is $i$, where $i=0$ means that there is no card on the table.  I would like an algorithm to compute, given $i,A,B$, whether the first player has a winning strategy in configuration $w(i,A,B)$.

Formally, I would like an algorithm to compute the function $f$ defined as follows:

Let $\mathbb{Z}_n = \left\{1, 2, \cdots, n\right\}$, $\mathrm{Bool} = \left\{\mathrm{False}, \mathrm{True}\right\}$.

Function $f:\;\left\{ 0, 1, \cdots, n \right\} \times 2^{\mathbb{Z}_n} \times 2^{\mathbb{Z}_n} \to \mathrm{Bool}$

where
$$  f ( i, A, B ) = \begin{cases}
        \mathrm{False} & B = \emptyset \\
        \mathrm{True} & B \ne \emptyset \land \exists j \in A: j > i, f(j, B, A - \left\{j\right\}) = \mathrm{False} \\
        \mathrm{True} & B \ne \emptyset \land f(0, B, A) = \mathrm{False} \\
        \mathrm{False} & \textrm{otherwise}
    \end{cases}
$$

Wrong strategies

Here are some wrong strategies:

Always play the smallest card. Let $n = 3, A = \{1,3\}, B = \{2\}$, the winning strategy for player A in configuration $w(0, A, B)$ is to play card $3$. If player A plays card 1, he will lose.
Play the smallest card unless the other player has only one card.
It is a stronger strategy than strategy 1, but it is also wrong.
Only think about configuration $w(0, \{1, 4, 6, 7\}, \{2, 3, 5, 8\})$. If player A uses strategy 2, he'll lose: $1\rightarrow2\rightarrow4\rightarrow5\rightarrow6\rightarrow8\rightarrow\textrm{pass}\rightarrow3$, thus player A lose.

This should probably be a comment, but it's too long.

A related game was studied by Jeff Kahn, Jeff Lagarias and Hans Witsenhausen, in the series of articles Single-Suit Two-Person Card Play I, II, III, and On Laskar's Card Game. In the game they studied, each player has $n$ cards, dealt from $2n$ cards numbered $1$ $\ldots$ $2n$. Each trick consists of two cards, the higher card wins the trick, and the winner leads. The object is to take the most tricks.

They proved a number of interesting facts about the optimal strategy, but were unable to find an efficient algorithm for optimal play, and were also unable to prove that it was NP-hard.

For the misère game, where each person tries to take the fewest number of tricks, they were able to give the optimal strategy.

For the most part, these results were obtained by first looking at the results of a computer program which found the optimal strategy for small instances, then looking for patterns to obtain conjectures, and finally proving these conjectures. I suspect that this would also be a fruitful approach to take for the OP's game.


Using Kolmogorov complexity as input "size" Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$.
Normally in the analysis of algorithms or computational complexity theory, we have some sets
$$I(n) = \{w \in S : |w| = n\}$$
of all inputs of length $n$, and a function $T(w)$ that gives the running time of some solution algorithm $A$ on input $w$.
The worst-case running time sequence for $A$ is then
$$ f_n = \max_{w \in I(n)} T(w). $$

Let us now define the sets
$$ I^K(n) = \{w \in S : K(w) = n \}$$
of all inputs with Kolmogorov complexity $n$, and let us define the sequence
$$ f^K_n = \frac{1}{\left|I^K(n)\right|} \sum_{w \in I^K(n)} T(w). $$
Here $f^K$ is the average running time sequence for $A$, except where the "size" of inputs is their Kolmogorov complexity, not their length.

Are there algorithms for which $f_n$ is asymptotically significantly different from $f^K_n$?  If so, are there problems whose time complexity changes when using this different way of analyzing algorithms?

Consider the parity function (or any other function that depends on all/most bits of the input). For the parity function, $T(w) = \Theta(|w|)$. So
$$f_n = \Theta(n).$$
On the other hand,
$$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$

Note that $K(2^{2^n}) = O(n)$. Thus $$\max_{w:K(w) = n} |w| \geq 2^{2^{\Omega(n)}}$$ and $f_n^K \geq 2^{2^{\Omega(n)}} / 2^n \to \infty$. Similarly, $K(2^{\dots^{2^{2^n}}}) = O(n)$; thus $f_n^K \geq 2^{\dots^{2^{2^{\Omega(n)}}}}/2^n$ “grows very rapidly”. Moreover, it's not hard to see that there is no computable upper bound for $f_n^K$.


Minimal non-negative linear combination of positive integers larger than a positive integer The problem is the following:

We have a positive integer $w$. A set of positive integers $A$ such that $\forall a \in A$ it's true that $a \leq w$. We search for the minimal integer $x$ such that $w \leq x$ and there is a convex integer combination of the elements of $A$ that is equal to $x$. The problem can clearly be written as an integer program but that's not much help.

My best approach is $O(w)$ in both time and space similar to knapsack's dynamic programming solution.

Could someone suggest a better one?

EDIT: I made 2 mistakes in the formulation. The first is that the combination is not convex only non-negative. The second is the algorithm I mentioned is not $O(w)$ but $O(|A|w)$.

The algorithm is like make an array size of $w$, sign $0$ in it and unsign everything else. Set a variable $\min$ to "infinite". Go through the array and to each signed element add each element of $A$. If it's not smaller than $w$ but smaller than $\min$ it's the new $\min$. If it's smaller than $w$ sign the according element. When we reach the end of the array $\min$ holds the $x$ in question.

Also the problem can be reformulated as a series of $n$ variable diophantine equation so if $A = \{a_{1}, \ldots, a_{n}\}$ and $d = \gcd(a_{1}, \ldots, a_{n})$ then we only need to check for $x \in \mathbb{N}, w \leq x, d \mid x$ if the diophantine equation $\sum_{i = 1}^{n}y_{i} a_{i} = x$ has an all non-negative $Y = \{y_{1}, \ldots, y_{n}\}$ solution.

I don't know the complexity for this second approach. I don't know how long the series can be.

EDIT.2: The length of the series is the smaller problem. Solving any of the above diophantine equations is like solving the subset-sum problem so this approach is not good either.

This is a variant of making change with a given set of coins, for which the knapsack/dynamic programming algorithm seems to be the best that is known. E.g., http://www.algorithmist.com/index.php/Coin_Change


Is there an additive time hierarchy theorem? I would like something like this to be true:

  Conjecture: There is a function $g(n)$ such that for all functions $f(n)$ (perhaps satisfying some reasonable properties, like time-constructability), there is a language in $TIME[f(n)]$ that is not in $TIME[f(n) - g(n)]$.

Is anything like this known?  Can this be proven under any reasonable assumptions?  Would this have any interesting consequences?

By $TIME[f(n)]$, I mean the set of problems solved by a Turing machine that halts in exactly $f(n)$ steps or less - not to be confused with $O(f(n))$ or less, in which case the conjecture is trivially false when $f(n) >> g(n)$.

I don't see the need for your clarification, since through linear speed-up those sets are exactly the same. It is clear why you need to avoid using asymptotics, since $f(n)-g(n)$ and $f(n)$ are asymptotically the same, but not using asymptotics doesn't somehow make the linear speed-up theorem not true.

Some further insight can be gained. $g(n)$ is actually $g(f(n))$,i.e. it must depend on $f(n)$ to work for all functions. Why? Suppose g(n) is non-constant. Pick $f(n) = 2 g(n)$ . Then clearly $f(n)$ and $f(n)-g(n)$ are equal by the linear speed-up theorem. If $g(n)=c$ is constant, then we can pick a non-constant $f(n)$ so that the conjecture doesn't hold.

What if we allow dependency on $f(n)$? Well then by taking the known deterministic hierarchy theorem and doing some basic arithmetic we can see that any $g(f(n))$ that is $o((1 - \frac{1}{ \log f(n)} ) f(n) )$ works. However I am not sure if just by stating the same theorem in a slightly different form opens up the possibility of some new insight.


Looking for a nice problem inside SC but not in the first two levels The complexity zoo doesn't have much about the $\mathsf{SC}$. I am looking for a nice$^\dagger$ problem that is in higher levels of the hierarchy, i.e. a problem in $\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$ but not known to be in $\mathsf{DTimeSpace}(n^{O(1)},\lg^2n)$.

As a side question, is there any known reason why finding examples of nice problems in higher levels of hierarchies ($\mathsf{AC}$, $\mathsf{NC}$, $\mathsf{SC}$, $\mathsf{PH}$, etc.) is more difficult than the first levels?

$\dagger$ although nice is not a mathematical term I think we intuitively understand what it means, e.g. accepting problem for NTMs is an artificial problem that people are not interested in it aside from it being complete for $\mathsf{NP}$, while the graph coloring problem was interesting before being known to be in/complete for $\mathsf{NP}$ and is still interesting aside from the complexity class it belongs to.

I don't have a suggestion for a natural problem in $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$, but I do have a suggestion for your side question, of why finding such a problem seems difficult. I think this has something to do with the folk-idea that people can only really comprehend (or maybe are only interested in? or both?) math that is a few quantifier alternations deep. For example, the definition of limit is two quantifiers deep (for all epsilon there exists a delta...); the definition of "$L \in \mathsf{NP}$" is two quantifiers (there exists a machine such that for all inputs...), and the statement "$\mathsf{P} \neq \mathsf{NP}$" is three quantifiers deep.

With regards to $\mathsf{PH}$, this is somewhat borne out by the fact that there are lots of natural problems that are $\mathsf{NP}$-complete, many natural problems that are $\mathsf{\Sigma_2 P}$-complete, and only a few known natural problems that are $\mathsf{\Sigma_3 P}$-complete (see the compendium by Schaefer and Umans). The most natural problems known to be complete for higher levels of $\mathsf{PH}$ come from logic itself, which is less surprising since within a given logic one often has the notion of "$k$-many quantifier alternations," or at least some natural way to simulate it. These perhaps fall into the same category as "accepting problems for NTMs," which you've declared "not nice enough" for this question.

It might also be worth mentioning that the same thing happens in the world of computability, which maybe suggests that it has to do more with our understanding of alternating quantifiers and less with complexity per se. Lots of natural problems are known to be $\mathsf{\Sigma^0_1}$-complete (equivalent to the halting problem), and many natural problems are known to be complete for the second and third levels of the arithmetic hierarchy. But as you go to higher levels of the arithmetic hierarchy fewer and fewer natural problems are known to be complete for those levels. I'm not sure I know of a natural problem complete for $\mathsf{\Sigma^0_4}$, and I've never heard of a natural problem complete for $\mathsf{\Sigma^0_5}$ (though maybe there is).

With regards to polylogarithmic space bounds, I think a similar reasoning applies, but even more so. Since $\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$, even problems that are in the "first few" levels of the "$\mathsf{NL}$ hierarchy" are all in fact in $\mathsf{NL}$ (the hierarchy collapses), which is contained in log-squared space.


What kind of mathematical background is needed for complexity theory? I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are considered helpful for TCS, especially (classical) complexity theory.

What fields do you consider essential for someone that wants to study complexity theory? Do you know of any good textbooks covering these fields and if yes, please include their difficulty level (introductory,graduate etc.).

If you consider a field that is not heavily used in complexity theory but you consider it critical for TCS, please also refer it.

If you look at the answers to this TCS StackExchange question, you'll see that there's a possibility that pretty much any area of mathematics could be important in complexity theory. So, if you're really interested in some area of mathematics that doesn't seem to be related, go ahead and study it anyway. If it ever does become relevant to complexity theory, you'll be one of the few complexity theorists who understands it.


Enumerating decidable languages [The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.]

Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a tape. How does one show that it's not possible that every decidable language $L$ is represented, but no undecidable $L$ is represented?

If we demanded that $M_E$ write out every $M$ representing a decidable $L$, then this could be shown impossible by Rice's Theorem II (for r.e. index sets).

If we demanded that every $M$ $M_E$ writes out is a decider, then this could be shown impossible by diagonalizing out of the set.

In this setup $M_E$ writes out $M's$ that aren't necessary deciders but that represent decidable languages. Every decidable language $L$ is represented by some $M$ on the tape, and no undecidable $L$ is represented. How does one show that this is impossible?

You can enumerate exactly the decidable languages. I've given this question as a homework problem so I'll just give a hint here: You can modify a TM $M$ to a machine $M'$ such that if $M$ is total (halts on all inputs) then $L(M')=L(M)$ and if $M$ is not total then $L(M')$ is finite.

By request I'm burning the homework question and putting in the full proof. I heard the problem from someone else (don't remember who) so this isn't original.

Define $M'(x)$ to accept if $M(x)$ accepts and $M(y)$ halts for all $y$ with $|y|\leq |x|$. Note $M'$ has the property mentioned above.

Let $M_1,M_2,\ldots$ be a standard enumeration of Turing machines. The enumeration $M'_1,M'_2,\ldots$ is an enumeration of Turing machines such that $D=\{L(M'_1),L(M'_2),\ldots\}$ is exactly the set of decidable languages.

DECIDABLE is contained in $D$: If $L$ is decidable then $L=M_i$ for some total $M_i$ so $L(M'_i)=L(M_i)=L$.

$D$ is contained in DECIDABLE: If $M_i$ is total then $L(M'_i)=L(M_i)$ is decidable. If $M_i$ is not total then $L(M'_i)$ is finite and thus decidable.


Are there any known NP problems which are conjectured to be exponentially hard on average? ETH states that SAT cannot be solved in the worst case in subexponential time. What about average case? Are there natural problems in NP that are conjectured to be exponentially hard in the average case?

Take average case to mean average running time with uniform distribution on the inputs.

It might be conjectured that the Learning Parity with Noise Problem (LPN) at constant error rate requires time $2^{n^{1-o(1)}}$.  The fastest known algorithm (Blum-Kalai-Wasserman) uses time $2^{O(n/\log n)}$.


Median finding with "green forests"? I have a vague memory of a series of papers working to reduce the constant factor in the number of comparisons for deterministic linear time median finding, using increasingly elaborate (but interesting!) techniques to do so.

In particular, I remember one of the papers using the term "green forests" for a data structure storing information from previous comparisons (in an attempt to reuse them and avoid future comparisons).

Does this ring any bells?  "median finding green forests" turns out to be a terrible search term.

Dorit Dor and Uri Zwick ("Selecting the Median", SODA 1995, pp 28-37) use green factories and analyze their amortized production costs.


Why is regularity a problem in cubical type theory? In my current understanding, regularity in cubical type theory is the following definitional equality (I'm using $A~\textbf{type}$ to emphasize the fact that $i \notin FV(A)$):
$$
\cfrac{A~\textbf{type} \quad a:A}
{\text{transport}(\langle i \rangle A, a) \mapsto a}
$$
I am not sure how is transport specified here (does it have a standard formulation?). I just assume it to be a special case of transp in de Morgan cubical type theory and a special case of coe in Cartesian cubical type theory.
In Cubical Agda, this definitional equality doesn't hold. It's proved as transportRefl in the cubical library. I'm not sure how it works in Cartesian cubical type theory, but I guess it is also a long-standing problem (Jon Sterling said he solved it a while ago, but it's on Twitter, which is not a reliable source of academic information).
I don't quite get the difficulty -- it seems like a problem in the model. In Arend's type theory, regularity is a part of the definition of coe, and it's implemented as "normalizing the path, reduce to $a$ if $i \notin FV(A)$". Why can't we do this in cubical type theory? We already have eta laws for functions where we need FV checks, so this is not a problem implementation-wise (or is it? Please tell me!).

The difficulty is in making such a reduction compatible with all the other reductions involving transport/coe. From one perspective it is a “confluence” problem. It is unfortunate that in the community, so much was said about "decidability of degeneracies" that we began to give the impression that this was the hard part of the algorithm (since as you say, in syntax you can decide degeneracy)...
The real problem is competing reductions. If you have both the type-based reductions and the regularity rule, then the term Transport(P, a) can reduce in potentially many different ways. It is necessary to ensure that the type-based reductions satisfy the regularity law, then. The problem in cubical type theory was that the type-based reductions do not satisfy the regularity law (actually, most of them do satisfy it, but ones involving the glue type do not). So the difficulty with regularity was to find new versions of these type-based reductions that preserve regularity, and I personally believe this cannot be done without extending the language of cofibrations beyond what appears in the CCHM or ABCFHL papers. (If you add further cofibrations, it is trivial to correct the reductions for CCHM & ABCFHL --- but my ideas in this direction do not seem possible to implement.)
The reason that Arend doesn't seem to have this problem is that Arend doesn't support the other reductions... So in principle it is possible to have a sound type theory that supports the regularity reduction for paths by simply deleting the other reductions that might conflict with it (but I do not want to make a claim about Arend's soundness).


In domain theory, what can the extra structure present in metric spaces be used for? Smyth's chapter in the handbook of logic in computer science and other references describe how metric spaces can be used as domains. I do understand that complete metric spaces give unique fixed points but I don't understand why metric spaces are important. I'd really appreciate any thoughts on the following questions.

What are good examples of the use of (ultra/quasi/pseudo)metric spaces in semantics?
In particular related to any example:
  Why do we need the metric structure?
  What do $\omega$-CPOs lack that the metric supplies?

Also:
Is the unique fixed point property important? What's a good example?

Thanks!

Relative to domain structure, metric structure gives you extra data on the carrier set. Basically, you can compare any two elements of a metric space and furthermore you know how much two elements are different, whereas in domains the order structure is partial, and you don't have a quantitative measure of how much elements differ.

Pragmatically, this extra structure is useful in that it makes solving domain equations hugely easier. Back in the 80s there were a lot of Dutch computer scientists using metric space equations to model concurrency, but it's also of current interest.

If you've been following the usual places (POPL/ICFP/ESOP/etc), you'll have noticed that so-called step-indexed models are big business these days, since they let you give models of languages with combinations of features (such as impredicative polymorphism and higher-order state) that are difficult to treat with classical domain-theoretic models. However, the constructions used in these models are hauntingly similar to solving domain equations, and it's natural to wonder what the heck the connection is. Lars Birkedal and his collaborators have had the general idea that solving domain equations on bisected (ie, distances between any two points are all of the form $2^{-n}$ for some $n$) ultrametric spaces is the secret denotational life of step-indexed models. See Birkedal, Stovring and Thamsborg's paper "The Category-Theoretic Solution of Recursive Metric Space Equations" for some recent work in this area.

Now, all this work has been focused on getting models at all, but that's not the only thing we're interested in -- we can't just replace partial orders with metric structure in a denotational model and expect it to mean exactly the same thing. So you might wonder what the impact of metric models on properties like full abstraction, for example.

Escardo showed in his 1999 paper "A Metric Model of PCF" that a straightforward metric model of PCF was adequate but not fully abstract -- the extra metric structure could be used to model timeout constants. Concretely, you could model a constant $\mathrm{timeout}\;n\;e$ which would raise an error if $e$ did not return in $n$ steps or fewer. This is information that a metric model can see, because it has distance information, but it's information a domain model can't, since the information order doesn't tell you "how evaluated" a value is.

This extra resolving power is both the strength and the weakness of metric techniques. In their note "Step Indexing: the Good, the Bad, and the Ugly", Benton and Hur show that the extra structure of step-indexed models is very useful for them give to give realizability-style correctness proofs of programming languages implemented in terms of bad low-level languages. However, the extra structure also keeps them from performing optimizations that are in some sense "too effective", because it might mess up the distance information. So it both helps and hurts them.

EDIT: I should also give an example of when Banach's fixed point theorem of metric spaces can be useful. In domains, we find fixed points by, basically, Kleene's fixed point theorem. This says that if we have a pointed domain $D$, and a continuous function $f$ on it, then iterating from $\bot$ gives us the least fixed point. This theorem makes no claims about the uniqueness of fixed points in general -- iterating from something other than $\bot$ can give us other fixed points. So if you want to consider recursion definitions on a domain, you have no choice but to admit nontermination into it.

However, you might not want to do that. For example, in my own recent research (with Nick Benton), I've been working on higher-order synchronous dataflow programming. Here, the idea is that we can model interactive programs through time as stream functions. Naturally, we want to consider recursive definitions (for example, imagine writing a function which receives a stream of numbers as inputs, and outputs a stream of numbers corresponding to the sum of the stream elements seen so far).

But an explicit goal of this work is to ensure that only well-founded definitions are allowed, while still allowing recursive definitions. So, I model streams as ultrametric spaces and functions on them as nonexpansive maps (as an aside, this generalizes the causality condition of reactive programming). Under the metric I use, a guarded definition on stream functions corresponds to a contractive function on streams, and so by Banach's fixed point theorem, a unique fixed point exists. Intuitively, the uniqueness property means that computing fixed points works the same no matter what element of the space we start with, so as a result we can compute fixed points of contractive functions on a space, even if the space doesn't have a minimal element in the sense of domain theory.


Converting a Hardware description language to a functional programming language I am looking for some guidelines on converting a Hardware description language such as VHDL or Verilog to a Typed Language. The reason I want to do this is to formally verify a hardware whose behavioral description is written in HDL.

You could write an interpreter for VHDL or Verilog in e.g. Coq or Isabelle/HOL and then prove that translated hardware descriptions do the right thing. I know that people have done this, at least for fragments of the hardware description languages, see e.g. A Formal Executable Semantics of Verilog.  Companies like Intel or AMD formally verify (parts of) the design of their chips. Have a look at Roope Kaivola's work.


Is there a gap between weak learning and PAC-learning? For concreteness lets use the definitions of PAC and weak-learning as in the notes of Avrim Blum (http://www.cs.cmu.edu/~avrim/ML12/lect0208.txt) and also his notes on SQ-Learning (http://www.cs.cmu.edu/~avrim/ML12/lect0321.txt)

It seems to me that the following are true,

That what is difficult to PAC-learn is also difficult to weak learn
If a binary valued/classification concept class has a weak learner then AdaBoost can produce a PAC-learner for it.

My questions are two fold,

But its not clear if one can boost a weak learner for an arbitrary concept class into a PAC learner for the same class. Or what is the best known statement in this direction?
Why is SQDim presented as a measure of hardness of weak learning? Is that a limitation of theory that we cannot get hardness of PAC-learning from SQDim? (..except in the case of binary classification when AdaBoost will lift from weak to PAC..)

I think you're confusing two notions of hardness: computational and statistical.

In Q1, you point out, essentially, that boosting produces an improper learner. I think what you're asking then, is: Is there a concept class which is (computationally) hard to learn properly but can be efficiently learned via boosting? I believe there should be such examples, but can't think of one off-hand.

In Q2, please note that SQDim refers to hardness in a statistical sense -- i.e., the minimal number of statistical queries required. (We don't have any unconditional computational hardness results but plenty of statistical ones.)


What algorithms exist for construction a DFA that recognizes the language described by a given regex? All of my textbooks use the same algorithm for producing a DFA given a regex: First, make an NFA that recognizes the language of the regex, then, using the subset (aka "powerset") construction, convert the NFA into an equivalent DFA (optionally minimizing the DFA). I also once heard a professor allude to there being other algorithms. Does anyone know of any? Perhaps one that goes directly from the regex to a DFA without the intermediate NFA?

There are different algorithms to convert regular expressions to finite automata. You can go directly from regular expressions to DFAs without building any other automaton first by implicitly doing the subset construction while generating the automaton. Another option to directly obtain deterministic automata is to use the method of derivatives.

Checking if a regular expression represents the language containing all strings is a PSPACE complete problem (see this answer for a reference). Checking if a DFA accepts that language can be done in polynomial time, so if you go directly from a regular expression to a DFA, there will be a blow-up somewhere.

My understanding of the literature is that we can choose translations that allow us to localise the blow-up. Meaning, there are different ways to go from a regular expression to a finite automaton, and methods that are linear, or polynomial are preferred. Usually, the exponential costs are pushed into determinization of automata.

There has been a lot of work on identifying sub-families of regular expressions from which we can efficiently generate DFAs. This line of work is dependent on the translation you use. Meaning, you fix a mapping from regular expressions to NFAs and try to characterise the regular expressions which map to DFAs.

The standard construction of automata from regular expressions is not the preferred construction in such work. The constructions of choice produce automata which closely resemble the structure of the regular expression. These constructions use the notion of a derivative of a regular expression.

  Derivatives of regular expressions, J. A. Brzozowski. 1964.

A derivative $s$ of a regular expression $r$ with respect to a symbol $a$ from the alphabet is a regular expression representing the language of $r$ with the leading $a$ removed from strings. This notion was extended to partial derivatives of regular expressions by Antimirov.

  Partial Derivatives of Regular Expressions and Finite Automata Constructions, V. Antimirov. 1995.

If you think of a state of an automaton as a representation of all strings accepted from that state, (partial) derivatives allow you to treat regular expressions as states. Contrast with the standard textbook construction which intuitively treats regular expressions as automata, not states.

  From regular expressions to deterministic automata, G. Berry and R. Sethi, 1986.

The correspondence between regular expressions and states of an automaton and determinism is discussed explicitly by Berry and Sethi, who combine the notion of Brzozowski derivatives with the idea of distinguishing between occurrences of the same symbol to give a syntax-based translation of regular expressions into finite automata.

  One-Unambiguous Regular Languages, A. Brüggemann-Klein and Derick Wood, 1998.

This paper builds on earlier work by Brüggemann-Klein and studies cases in which you can use derivatives to generate DFAs in polynomial time. There is a large amount of work following this paper. It was significant from the perspective of web technologies because regular expressions that can be manipulated efficiently (aka, corresponding to DFAs) were important for processing SGML and XML.

There has been much work studying other special cases of deterministic regular expressions. A very recent paper studying when some of these problems can be solved in linear time is from 2012.

  Deterministic Regular Expressions in Linear Time, Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012.


$NP\cap coAM$ Languages What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references?

Update: I forgot to mention that I'm interested in languages not known to be in $coNP$.

The only other ones I know of are also isomorphism problems: group isomorphism and ring isomorphism.  The $coAM$ protocols for both of these are essentially the same as for graph isomorphism.

Group isomorphism reduces to graph isomorphism reduces to ring isomorphism.

Interestingly, unlike (what is known for) groups and graphs, for rings, determining whether a ring has a nontrivial automorphism is in $P$, while finding a nontrivial automorphism is equivalent to factoring integers.  See Neeraj Kayal, Nitin Saxena. Complexity of Ring Morphism Problems. Computational Complexity 15(4): 342-390 (2006).


What is the folk model of linear logic? Probably the most common application of linear types in PL is to use them to give languages which control aliasing (i.e., a linear value has a single pointer to it, more or less).

But there's a slight mismatch between this usage and typical denotational models of linear logic. IIRC, Benton showed that if a Cartesian closed category has a strong commutative monad, then its category of algebras will be symmetric monoidal closed (ie, a model of linear logic). But this theorem doesn't apply to the alias-control usage, since the state monad is not commutative. And indeed, in the past few years Simpson and his coworkers have given calculi for general strong monads, which are not term calculi for linear logic.

So my question is, what is the denotational semantics of linear languages with state? Is there a non-degenerate (ie, tensor is not a Cartesian product) symmetric monoidal closed category in which allocation, reading, and linear update can be modeled?

It seems to me that the direction you should consider looking in revolves around game semantics for general references and the related semantics for linear logic,
such as those based on Conway games.  An algebraic account of references in game semantics by Paul-André Melliès and Nicolas Tabareau is probably the best place to start. In this paper linear logic is relaxed to so-called tensor logic to get things to work, so it is not quite the setting you want. But they do rely on Conway games, so there is certainly a connection with models of linear logic. They also do not really exploit linearity as in linear types, but the machinery is there to do so if you want to, I believe.

The work of Jim Laird (such as A Game Semantics of Names and Pointers) and Guy McCusker may also contribute to your quest. The recent interesting thesis Game semantics for an object-oriented language by Nicholas Wolverson pushes these ideas further in an OO setting. He considers in detail linear threading, only one operation active at a time, and describes how to add linear classes. Both rely on linear typing.
Again, however, the underlying model is not strictly a model of linear logic, but it's close.


Implications of a problem being in XP when parameterized by diameter Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if it can be solved in $n^{f(k)}$ time). Does this imply solvability in XP time for other interesting parameters?

If so, is there maybe even some more or less "standard" list or web of parameters and how they relate documented somewhere?

I think Figure 1 (page 4) of the paper "New Races in Parameterized Algorithmics" of Komusiewicz and Niedermeier is what you are looking for.

In particular, being in XP for the parameter diameter implies being in XP for parameters: min dominating set, max independent set, minimum clique cover, distance to cograph, distance to co-cluster, distance to clique, distance to cluster, vertex cover, and cluster editing.


Does there exist a complexity class such that the number of accepting paths is a prime number? #P asks the total number of accepting paths.
PP asks at least half of paths be accepting.
Parity-P asks the number of accepting paths be even.
UP asks the number of accepting paths to be one.
Are there any other Complexity Classes like this? For example, does there exist a complexity class where the number of accepting paths is a prime number?

Many other complexity classes which have appeared in literature are defined in terms of the number of accepting paths.  Just for fun, examples from the Complexity Zoo include GapP, AWPP, C=P, Few, FewP, LWPP, ModkP, SPP and WPP.  Also do not forget the logarithmic-space versions of these classes.

A serious fact is that the definition of randomized complexity classes such as the very important BPP can be viewed as based on the number of accepting paths.

As for the class of decision problems which have a nondeterministic polynomial-time Turing machine such that yes-instances have a prime number of accepting paths and no-instances have a composite number of accepting paths: As Philip White and other people wrote in comments on the question, you could define it.  Whether that class has any interesting property or not is a separate issue.


VC-dimension of Cylinders within a Cylinder I wish to know the VC-dimension of a range space $(X,\mathcal{R})$ constructed as follows:

$X$ is the cylinder $\{(x,y,z)\in\mathbb{R}^3|x^2+y^2\leq 1\}$
The ranges in $\mathcal{R}$ are formed by taking the union of circular disks such that:

the plane containing the disk is orthogonal to the z axis (we "stack" the disks in the z direction)
a disk is tangent to the cylinder boundary at the point $(1,0,z)$
a disk has diameter $f(z)+1$, where $f(z)$ is bounded (strictly) by $-1<f(z)<1$, and strictly monotonically increasing, strictly monotonically decreasing, or constant.

Any set constructed by rotating one of these ranges about the z axis by an arbitrary angle is also a range.

Intuitively, imagine taking a set of coins (circular, of course) and sorting them by diameter, either decreasing or increasing. Then drop them carefully into a tube (the main cylinder) in that order, so each rests on the last. Now tip the tube slightly so that they all rest against the side of the cylinder. If our coins had zero thickness and we had one for every real number, this would be our range.

I'm mostly interested in the case that $f(z)$ is sigmoid, like the error function or $\tanh$. Specifically, I'm interested in the cylindrical ranges formed by the family of functions $\tanh(\alpha(z-\beta))$, where $\alpha,\beta\in\mathbb{R}$.

I know that this range space has at least VC-dim 4 (I can construct a set of four points that it shatters), but I'm interested in putting an upper bound on it and understanding why. I know that:

Circular disks in $\mathbb{R}^2$ have VC-dim 3
Subsets of the strip $\{-1\leq y\leq 1\}\subset\mathbb{R}^2$ that are bounded above or below by $\tanh(\alpha(z-\beta))$ have at least VC-dim 3, probably equal to 3, because the slope part of the $\tanh$ function acts much like a line

Is there any way to combine these facts to obtain an upper bound on the VC-dimension? Is there anything to say about general $f(z)$ that meet the criteria in (2)?

You need the sigmoid restriction on $f$ for the VC-dimension to be finite.  Otherwise, you can let $f$ behave like a staircase, with arbitrarily many steps.  Then these staircases can have arbitrarily many intersections.  This allows $n$ ranges to admit $2^n$ different subsets.

If $f(z)$ is a polynomial, then you can bound the VC-dimension using the degree of the polynomial (combined with the degree of the polynomial (2) describing the disc).  But not sure how to apply this type of result for $\tanh$.


how to prove bidimensionality I'm looking for a formal proof that a problem (say, dominating set) is bidimensional/contraction-bidimensional. Either a reference or a proof sketch is fine.

There are two elements in the definition of (contraction-)bidimensionality (1) taking minor/contraction does not increase the parameter (2) on r*r-grid/triangulated grid, the solution value is at least theta(r*r).
In particular, I'd like to know how the proof goes regarding (2).

Here's how to do (2) for Dominating Set. Since Dominating Set is contraction-bidimensional, we need to show the solution value is $\Omega(r^2)$ on a partially triangulated $r*r$ grid. So consider a partially triangulated $r*r$ grid. There might be vertices on the outer cycle of the grid of large degree (for example, one vertex might be adjacent to all other vertices on the outer cycle). Therefore, we are going to ignore the outermost 2 cycles of the grid, so we look at the $(r-4) * (r-4)$ partially triangulated subgrid "in the center", which has $\Omega(r^2)$ vertices, and we consider which vertices may be used to dominate this subgrid. Due to planarity, no vertex in this inner grid can be adjacent to a vertex on the outer cycle. All vertices which do not lie on the outer cycle have degree at most 8, as the partial triangulation has to keep the graph planar and can only make edges to the 8 vertices which are above, below, left, right, and diagonally adjacent to a vertex. So the $\Theta(r^2)$ vertices of the inner $(r-4)*(r-4)$ grid must be dominated by vertices which have degree at most 8 each. So when it comes to this inner grid, at best each vertex can dominate 8 other vertices and itself, for a total of 9. So you need at least $(r-4)^2 / 9$ vertices to dominate the inner grid, so a dominating set on the partially triangulated grid has size $\Theta(r^2)$.


Finding the longest path between two nodes in a bidirectional unweighted graph I'm looking for an algorithm to find the longest path between two nodes in a bidirectional, unweighted, cyclic graph.

The path must not have repeated vertices (otherwise the path would be infinite of course).

Would someone point me a to a good one (site or explain)?

The graph will be sparse.

Thanks for any help!

Williams (2009) [arXiv version] gives a randomized $2^k poly(n)$ time algorithm finding a path of length at least $k$ in a graph on $n$ vertices. The paper contains pointers to previous deterministic and randomized algorithms. Many of these algorithms can probably be modified to find a $k$-path whose endpoints are given in the input.


A dominate vector subset sum problem Let $k$ be some constants (e.g. one can take $k=2$ for simplexity), for any $u,v\in \mathbb{R}$, we say $u$ dominate $v$ if $\forall 1\le i\le k,~ u[i]\ge v[i]$, write it as $u\succ v$.

Consider the following problem:

  Let $v_1,v_2,\cdots,v_n\in \mathbb{R}^k$, integer $m\le n$, and a target vector $t\in\mathbb{R}^k$, decide if there exist an index set $I\subset [n]$, such that
  $$\sum_{i\in I}v_i\succ t,$$and $|I|\le m$

Is this problem NP-hard? (Note that, when $k$ is not constant but scale as $n$, this problem is NP-hard by reduction from set cover problem.)

In particular, is this problem hard for $k=2$? (Note that, there is a pseudo-polynomial dynamic programming algorithm for integer vectors).

It's hard for $k\ge 2$ by a reduction from Partition. Let's first look at $k = 3$. Suppose that the input to Partition is the numbers $x_1, \ldots, x_n$, and their sum is $S$. For each $i$ create a vector $v_i$ whose first coordinate is $x_i$, second coordinate is $-x_i$, and the third coordinate is $0$. Add another vector $v_{n+1}$ with first coordinate $0$, second coordinate $S$, and last coordinate $1$. Define $t$ to have first and second coordinates $S/2$, and last coordinate $1$. Then any solution $I$ to this instance of your problem must include $n+1$, and the sum $\sum_{i \in I}{v_i}$ has first coordinate $\sum_{i \in I\setminus \{n+1\}}{x_i}$ and second coordinate $\sum_{i \in [n] \setminus I}{x_i}$, so it's only feasible if $I \setminus \{n+1\}$ is a valid solution to the Partition instance.

This can be extended to $k=2$ with a trick. Define the same instance but $v_i$ for $i \in [n]$ has only the first two coordinates. Let $A = \sum_{i=1}^n{|x_i|}$ and $b = \lceil \log_2 A\rceil$. Define $v_{n+1}$ to have first coordinate $2^b$, and second coordinate $S$, and $t$ to have first coordinate $2^b+S/2$ and second coordinate $S/2$. This forces the $b$-th bit (from the right) of the first coordinate of $\sum_{i \in I}{v_i}$ to be $1$, which can only happen if $n+1 \in I$. The rest is the same as above.


Does the order of insertion affect the topology of an R-Tree Say I have 2 permutations of the the same set of elements.
I create 2 R-Trees, one for each permutation.
Do I end up with 2 structurally identical R-Trees or not?
PS: My elements are rectangles on a plane.
Edit:
Reformulation of the question: is there an insertion algorithm that reconstructs the same R-Tree regardless of the order of elements in use?

the R tree algorithms typically create "R"s (rectangles) iteratively/sequentially based on the order of insertion of the data. the "R"s are built directly out of the coordinates of the data seen so far. it does not appear that there are widely studied R-tree variants that build identical trees no matter what the order is, it does not seem to be a generally desired design criteria for the algorithms, which are judged on other criteria such as performance of search, insertion, overflow splitting etc.

except in artificial/contrived/"pathological" cases, the resulting R-trees will be "close" in structure and performance no matter what order the insertion. however it is not inconceivable that such an algorithm could be devised with the property of "resultant tree invariance" based on adjusting the insertion and overflow splitting logic.

on the other hand if you dont require an online algorithm you could just sort your data according to any criteria beforehand and the R tree will end up with the same structure of course.

a close alternative that can be adjusted to have the "order invariant" property you describe is the Quadtree because it is based on partitioning the overall space (assuming its dimensions are known) in a fractal "4-square" pattern that does not depend on ordering of the input or directly use the individual points for bounding coordinates.


Recursive types and the empty type In John Mitchell's book "The Foundations of Programming Languages", he considers a typed lambda calculus with unit, exponential, product, (binary) coproduct types, and arbitrary recursive types (p126). Later in the book he shows how to construct models of all these types. (I'm pretty new to all of this, but I assume this is a pretty standard system.)

It looks as though it is not possible to extend this system with a 0 type for the following reason:

Let $\sigma$ be $\mu t.t\to 0$. $\mbox{unfold}: \sigma \to \sigma \to 0$ and $\mbox{fold}: (\sigma \to 0)\to \sigma$. Then $W(\mbox{unfold})(\mbox{fold}(W(\mbox{unfold}))): 0$, where $W = \lambda xy.xyy$.

From this you can prove all equations between terms (e.g. from the existence of a closed term $t:0$, $\lambda x.t:A \to 0$ is an isomorphism between any type $A$ and $0$.)

A natural thought would be to work in a linear or affine type theory where the $W$ combinator isn't allowed, and which therefore might allow solutions to type equations like $\sigma = \sigma \to 0$.

My questions is: Is the resulting type theory consistent, and can anyone explain to me how to go about constructing models? (References would also be welcome, but the papers I've looked at so far have generally presupposed more knowledge than I have).

First, note that nothing turns on the presence or absence of the empty type: if you have a nonlinear calculus with function types and unrestricted recursive types, then it is inconsistent. Indeed, your derivation works regardless of the type of the answer -- the very same term you have works for $\mu a.\; a \to X$ for any $X$.
This is known as Curry's Paradox, and is also known as the Y combinator. There is a nice discussion of this in Greg Restall's paper Curry's Revenge: the costs of non-classical solutions to the paradoxes of self-reference.

Next, your observation that the fixed point combinators rely upon contraction is astute. Curry's paradox depends on all three of contraction, unrestricted recursive types, and a function space, and removing any one of them suffices to block it.
For example, I asked a very similar question here a few years back, and learned that multiplicative-additive linear logic with recursive types is not Turing-complete. This is called the "Small Normalization Theorem" (Theorem 4.22) in Girard's original paper on linear logic.

You can still construct models of this language (with or without units) using domain theory. The main technical difficulty is the interpretation of recursive types. I don't know a good introduction to how to solve recursive domain equations. I learned it from Plotkin and Smyth's The Category-Theoretic Solution of Recursive Domain Equations, but that was really not a good tutorial for me: I needed a fair amount of help to understand it. The critical intuitions are all there, but it's quite dense. Maybe Abramsky and Jung's handbook chapter might be more accessible? I don't really have any great suggestions.


Relative consistency of PA and some type theories For a type theory, by consistency, I mean that it has a type which is not inhabited. From the strong normalization of the lambda cube, it follows that system $F$ and system $F_\omega$ are consistent. MLTT + inductive types also has a normalization proof. However, these should all be powerful enough to construct a model of PA, which proves that PA is consistent from these theories. System $F$ is quite powerful, so I expect it to be able to prove the consistency of PA by constructing a model using Church numerals. MLTT + IT has a natural numbers inductive type and should prove consistency as well.

This all implies that the normalization proofs for these theories can't be internalized in PA. So:

Can system $F$, system $F_\omega$, and MLTT + IT actually prove the consistency of PA?
If they can, then what metatheory is needed to prove normalization for system $F$, $F_\omega$, and MLTT+IT?
Is there a good reference for the proof theory of type theories in general, or for some of these type theories in particular?

The short answer to your question 1 is no, but for perhaps subtle reasons.

First of all, System $F$ and $F_\omega$ cannot express the first-order theory of arithmetic, and even less the consistency of $\mathrm{PA}$.

Secondly, and this is really surprising, $\mathrm{PA}$ can actually prove consistency of both those systems! This is done using the so-called proof-irrelevant model, which interprets types as sets $\in\{\varnothing,\{\bullet\}\}$, where $\bullet$ is some dummy element representing an inhabitant of a non-empty type. Then one can write down simple rules for the operation of $\rightarrow$ and $\forall$ on such types rather easily to get a model for system $F$, in which the type $\forall X.X$ is interpreted by $\varnothing$. One can do a similar thing for $F_\omega$, using a bit more care to interpret higher kinds as finite functions spaces.

There's an apparent paradox here, where $\mathrm{PA}$ can prove consistency of these seemingly powerful systems, but not (as I'll show in a moment) normalization.

The missing ingredient here is realizability. Realizability is a way to make certain programs correspond to certain propositions, typically in arithmetic. I won't go into the details here, but if a program $p$ realizes a proposition $\phi$, written $p\Vdash \phi$, then we have a certain piece of evidence for $\phi$, in particular if $p$ is normalizing, then $p\not\Vdash\bot$. We have:

  Theorem: If $\phi$ is a theorem of 2nd order arithmetic $\mathrm{PA}_2$, then there is some closed term $t$ of system $F$ such that $$ t\Vdash\phi$$

This theorem can be proven in $\mathrm{PA}$, and so we have
$$\mathrm{PA}\vdash F\mbox{ is normalizing}\Rightarrow\mbox{$\mathrm{PA}_2$ is consistent} $$
and Gödel's argument applies (and $\mathrm{PA}$ cannot prove normalization of system $F$). It's useful to note that the reverse implication holds as well, so we have an exact characterization of the proof-theoretic power needed to prove normalization of system $F$.

There is a similar story for system $F_\omega$, which, I believe, corresponds to higher arithmetic $\mathrm{PA}_\omega$.

Finally, we have the tricky case of MLTT with inductive types. Here again a somewhat subtle issue arises. Certainly here we can express the consistency of $\mathrm{PA}$, so that isn't an issue, and there is no proof-irrelevant model, as we can prove that the type $\mathrm{Nat}$ has at least 2 elements (an infinite amount of distinct elements, in fact).

However we run into a surprising fact of higher-order intuitionistic theories: $\mathrm{HA}_\omega$, the higher-order version of Heyting Arithmetic is conservative over $\mathrm{HA}$! In particular, we cannot prove consistency of $\mathrm{PA}$, (which is equivalent to that of $\mathrm{HA}$). An intuitive reason for this is that intuitionistic function spaces do not allow you to quantify over arbitrary subset of $\mathbb{N}$, since all definable functions $\mathbb{N}\rightarrow \mathbb{N}$ must be computable.

In particular, I don't think you can prove consistency of $\mathrm{PA}$ if you add only natural numbers to MLTT without universes. I do believe adding either universes or "stronger" inductive types (like ordinal types) will give you enough power though, but I'm afraid I have no reference for this. With universes, the argument seems quite simple though, since you have enough set theory to build a model of $\mathrm{HA}$.

Finally, references for the proof theory of type systems: there's really a gap in the literature here I think, and I would relish a clean treatment of all these subjects (in fact, I dream of writing it myself some day!). In the meantime:

The proof-irrelevant model is explained here by Miquel and Werner, though they do it for the Calculus of Constructions, which complicates matters somewhat.
The realizability argument is sketched in the classic Proofs and Types of Girard, Taylor and Lafont. I think they also sketch the proof-irrelevant model, and a great deal of useful things besides. It's probably the first reference to read.
The conservativity argument of higher-order Heyting arithmetic can be found in the elusive second volume of Constructivism in Mathematics by Troelstra & van Dalen (see here). Both volumes are extremely informative, but quite difficult to read for a novice, IMHO. It also somewhat avoids "modern" type theory subjects, which is unsurprising given the books' age.

An additional question in the comments was about the exact consistency strength/normalization strength of MLTT+Inductives. I don't have a precise answer here, but certainly the answer depends on the number of universes and the nature of the inductive families allowed. Rathjen explores this question in the excellent paper The Strength of some Martin-Lof Type theories.

Wrt normalization, the basic idea is that if, for 2 theories $\cal{T}$ and $\cal{U}$, we have
$$\mathrm{PA}\vdash\mathrm{Con}(\cal{T})\Rightarrow\mathrm{Con}(\cal{U}) $$

then, generally

$$\mathrm{PA}\vdash \mbox{1-$\mathrm{Con}$}(\cal{T})\Rightarrow\mathrm{Norm}(\cal{U}) $$

where 1-$\mathrm{Con}$ is 1-consistency and $\mathrm{Norm}$ is (weak) normalization.

MLTT + the type of natural numbers (and recursion) is a conservative extension of $\mathrm{HA}_\omega$, which is proven in Besson Recursive Models for Constructive Set Theories.

As far as MLTT with induction-recursion or induction-induction, I don't know what the situation is, and AFAIK, the problem of exact consistency strength is still open.


Classes of boolean functions where reasonable lower bounds on approximate degree is unknown? Let $\underline{x}\triangleq x_1,\dots,x_n$.
Given a Boolean function
$f:\{0,1\}^n\to\{0,1\}$,
we say that $p(\underline{x})\in\Bbb{R}[\underline{x}]$ is an $\epsilon$-approximation to $f$
if  for all $\underline{x}$, $|p(\underline{x})-f(\underline{x})|\leq\epsilon$.
$\newcommand{\apxdeg}[0]{{{\mathsf{deg}}}}$
Let $\mathsf{deg}_\epsilon(f)$ be the minimum degree of
multilinear real polynomial that $\epsilon$-approximates $f$.

  Supposing that $\mathsf{deg}_{1/3}(f)\geq(\mathsf{deg}_0(f))^b$ with some $b\in(0.00001,1]$, are there constants $a_f\in(0,0.00001]$ such that,
  $\mathsf{deg}_\epsilon(f) \geq(\mathsf{deg}_0(f))^{a_f}$ at every $\epsilon\in(0,1)$?

  Or is there an $f$ such that
  $\apxdeg_\epsilon(f) \leq \mathsf{polylog}(\apxdeg_0(f))$ at some $\epsilon\in(0,1)$?

  Note that $a_f$ is unlikely to be independent of $f$. A closely related question corresponds to what is the highest error $\eta_f<1/2$ as it approaches $1/2$ beyond which no further decrease happens in degree except at exactly $\epsilon=\frac{1}2$.

  Nisan-Szegedy result implies only a trivial lower bound of
  $$\lim_{\epsilon\rightarrow\frac{1}2^-}\mathsf{deg}_\epsilon(f)\geq 1.$$

For symmetric $f$ we can have $a_f$ close to $0.5$.

Is there a class of functions where a non-trivial lower-bound is not known?

Is there a class of functions it is conjectured approximate degree $\mathsf{deg}_{ \epsilon}(f)$ at some $\epsilon\in(0,\frac{1}2)$ can be polylogarithmically smaller than the exact degree given that $\mathsf{deg}_{1/3}(f)\geq(\mathsf{deg}_0(f))^b$ with some $b\in(0.00001,1]$?

When error approaches $1/2$. The bound is $\deg_{0}(f)\leq C_\epsilon(\deg_{\epsilon}(f))^8$ where $C_\epsilon$ depends on $\epsilon$. As $\epsilon$ approaches $0$, $C_\epsilon\rightarrow\infty$. So it is possible the upper bound is because  $C_\epsilon\rightarrow\infty$ and $\deg_{\epsilon}(f)\rightarrow1$. This corresponds to $a_f=0$ in the question. Can this degenerate situation actually happen in a boolean function $f$?

If I understand correctly you are asking about the relationship between the degree necessary for exact representation and the degree necessary for approximate representation.  The seminal paper by Nisan and Szegedy shows that for $\epsilon$ constant these degrees are polynomially related.


What are practically computable properties of Labelled Transition Systems? I found labelled transition systems to be a good model for my application, namely there is a paper about modeling use cases using LTSs. The question is, what can be easily proven about LTSs? I would like to re-use existing solutions to see if they are useful for my appication. I would like to know what properties of LTSs (and use cases) can be easily automatically proved, so I can decide, if there is a practical counterpart to the problem for use cases.

The formulas of Hennessy-Milner logic are very easy to prove about labelled transition systems. However, this logic is inexpressive enough (there is no way to state properties of infinite paths) that you will probably wish to consider some extension to it, such as linear temporal logic. LTL has a decidable, but PSPACE-complete, problem.

The SPIN model checker is a widely-used tool for model-checking LTL properties.


What is the complexity of this game? This is a generalization of my previous question.

Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be some string.

Consider the following Alice and Bob game. Initially, Alice and Bob have $m_A$ and $m_B$ dollars respectively. Alice wants $M^A(x)=1$ and Bob wants $M^A(x)=0$.

At every step of the game a player can add some string $y$ to $A$; this costs $f(y)$ dollar, where $f: \{0,1\}^* \to \mathbb{N}$ is a polynomial-time computable function. Also a player can miss his or her step.

The play ends if both players spends all money or if some player missed step when he or she in a losing position (that defines by the current value of $M^A(x)$).

Question: is the problem of defining the winner of this game for given
$M, f, x, m_A, m_B$ is an

EXPSPACE-complete task?

Note that $M$ can ask (for belonging to $A$) only strings of polynomial length so there is no  sense for Alice or Bob to add more longer strings to $A$. Hence, this problem is in EXPSPACE.

In my previous question adding of every string to $A$ costs one dollar (i.e. $f \equiv 1$). Then (as it was shown by Lance Fortnow) this game belongs to EXPH and even to PSPACE if $m_A = m_B$.

This should be EXPSPACE-complete. I'll sketch how to achieve an exponential number of alternations, without reducing any EXPSPACE-complete problem to this one, but from here it should be simple to finish.

Denote the words in the oracle after $t$ rounds by $A_t$, so initially $A_0=\emptyset$.
Denote the words queried by $M^{A_t}$ by $Q_t$.
The main observation is that whoever is losing with $A_t$, can be assumed to add something from $Q_t$ to $A$.
This is because in this game every move costs money, we want to move as little as possible; there's no point making a move until we're winning.
But this also implies that if we're losing, there's no point adding anything from outside $Q_t$.

Assume for simplicity that $M$ runs for exactly $2n$ steps and at steps $2i$ and $2i+1$ it queries a word of length exactly $i$.
The cost function $f$ will simply be $2^{-i}$ on words of length $i$.
The game will be such that Alice always needs to add odd length words and Bob always needs to add even length words to $A$.
Suppose that $n$ is odd and initially Alice is losing.

The budgets $m_A$ and $m_B$ will be set so that she can choose exactly one of the length $n$ words queried by $M^{A_0}$ to be added to $A$.
The game will be such that this makes her the winner, so Bob will have to move.
Again due to budget constraints, he will have to choose exactly one of the length $n-1$ words queried by $M^{A_1}$ to be added to $A$.
After any of these are added, $M^{A_2}$ will query two new length $n$ words (the same ones, regardless of what word Bob added to $A$), and Bob will win.
Alice will be forced to add exactly one of these new length $n$ words to $A$ to make her win.

The game goes on in this manner, which can be imagined as following the branches of a complete binary tree of depth $n$, though at each branching node one of the players (determined which by the parity of the depth of the node) needs to make a choice about which word to add to $A$.
After they go through the tree, they will run out of their budget.
If at any stage of the game one of them decides to add some word that is shorter (e.g., Alice a length $k<n$ word from $Q_0$ in the first step), then if the other player (in our example Bob) just plays always the longest word he can in the binary tree, he will have some money left at the end and we make the game so that he can use this to win.
(Note that Alice might also have some money left, but Bob will have more, so we design the end-game that if one of them has more money, then that player can win.)

This way Alice decides for exponentially many pairs of odd-length words, and Bob about exponentially many even-length words which one of each pair goes to $A$, and they make these choices in an alternating manner.


Does this graph problem have a formal name? Given an undirected weighted graph where an edge exists between every pair of nodes (n1,n2) with cost C(n1,n2), find the shortest path (possibly revisiting nodes, possibly revisiting edges) through the graph that visits each node.  Algo can pick any source node it wants.  No need for the path to terminate back at the source node.  Path cost is cumulative over all edge visits, so, if you traverse an edge with cost 5 and then traverse it again later it costs you 10 (i.e. re-traversing an already explored edge isn't free!)

The TSP problem, given a graph and an edge-weight function, asks to find a tour visiting each vertex exactly once having minimum length.

I think your problem is equivalent to the Metric TSP problem, that is the TSP problem on the complete graph where the weight of each edge $uv$ is the length of a path between $u$ and $v$ with minimum weight in your original graph.

Indeed, a minimum walk on your original graph corresponds to a minimum tour in the newly defined clique, and vice-versa.

For the first side, consider a minimum walk in the original graph. If some node is repeated (say $v$ is repeated: $\ldots, v, \ldots, u, v, w, \ldots$) one can get rid of the repetition by replacing the portion $u,v,w$ by $u,w$ in the shortest path graph. Doing this for each repetition one gets a tour in the shortest path graph having the same length as the original walk. Since the walk was optimal the tour is optimal too.

For the other side, given an optimal tour of the new graph, replace each edge $uv$ of the tour by a shortest weighted path from $u$ to $v$ is the original graph. This walk may contain some repetitions, but has now the same length as the tour, and it is optimal.


Is there a method for proving non-regularity of string transformations? There are a number of different models for defining transformations between languages. Finite state transducers and MSO-definable graph transformations over string graphs are the two that I am best acquainted with. We know that 2-way finite state transducers (which are more expressive than their 1-way counterparts) and MSO-definable string transformations capture the same set of transformations along with some other less well-known models that use combinators. This class of transformations is considered regular, and so it is easy to show then that a transformation is regular if you can provide a description of it with one of these models.

Is there a straight-forward way to say that a transformation is outside of this class? Something akin to the pumping lemma for regular languages or the Myhill-Nerode theorem but for string transformations is the sort of thing I am looking for.

Your question is not entirely well defined: how are you given the transformation you start with?
For example, if you assume the transformation is given by e.g. a Turing machine, then clearly there is no algorithmic way of deciding whether it's a regular transduction.

However, it seems that what you're asking is whether there is some "machine-independent" characterization of string transductions (e.g., Myhill-Nerode).

While I don't know of such a characterization in general (I'm pretty sure no such characterization is known), there is such a characterization for string transducers with origin information, developed by Bojnaczyk.

You can start here.


Exponential gap on neural network layers I read it here that there are function families which need $\mathcal{O}(2^n)$ nodes on neural network with at most $d - 1$ layers to represent the function while need only $\mathcal{O}(n)$ if the neural network has at least $d$ layers. It was referring to a paper by Hastad. I didn't find it. Could someone tell me the title of the paper? I think this is a really fascinating theoretical result.

The paper that people usually cite is Almost Optimal Lower Bounds for Small Depth Circuits, which appears in STOC 1986. The main result pertaining to your question is:

  There exists a family of functions admitting linear size, depth $k$ circuits (of unbounded fan-in AND/OR and NOT) that requires exponential size at depth $k-1$.

What's possible even more relevant is the fact that $\mathsf{TC}^0$ admits an exponential separation between depth 3 and depth 2. This is relevant because threshold gates are commonly used in deep networks.


Can a polynomial sized arithmetic ciruits perform integer division? Can we perform integer division with a polynomial size arithmetic circuit over $\mathbb{Q}$ that takes as input the numerator and denominator?

See Eric Allender's survey of "recent" breakthroughs (circa more than a decade ago) in the complexity of division. The bottom line is that

  Division is complete for DLOGTIME-uniform $\mathsf{TC}^0$

so in particular there is a poly-sized circuit (of constant depth) that takes $x$ and $y$ as input and produces $x/y$. Notice that this circuit doesn't even need to be arithmetic (it only needs MAJORITY gates in addition to boolean gates)


Can complexities differ w.r.t. different computational models? I understand that a decision problem can be decidable with respect to certain computational models. For instance, the question whether an arbitrary sequence of parenthesis is balanced is undecidable for finite state automata and decidable for pushdown automata.

Does something similar hold for the complexity of problems? For instance, are there problems that are in $\mathbf{P}$ with respect to one computational model, but are in $\mathbf{EXPTIME} \setminus \mathbf{P}$ with respect to a strictly weaker one?

Niel De Beaudrap's point is an important one: a complexity class is defined with respect to a machine model. But if I were to re-interpret your question as:

  Can the complexity of a problem differ greatly in different computational models ?

Then the answer is yes. JeffE's answer to my earlier question about decision tree complexity presents an example of an NP-hard problem (SUBSET SUM) that has polynomial decision tree complexity.


Lower bound for NFA accepting 3 letter language Related to a recent question (Bounds on the size of the smallest NFA for L_k-distinct) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from communication complexity bounds. What follows is a special version of that problem.

Suppose $L$ is a language over some $n$ letter alphabet whose words all have length $3$. Denote the size of the smallest NFA accepting $L$ by $NFA(L)$. Define an $n\times n^2$ matrix $M$ as $M(a;bc)=1$ if $abc\in L$ and otherwise $0$. Denote the minimal number of $1$-submatrices (submatrix that contains only $1$'s) covering all the $1$'s in matrix $M$ by $COV(M)$. (So $\log(COV(M))$ is the non-deterministic communication complexity of $M$.)
It is easy to see that $NFA(L)\ge COV(M)$. If we similarly define a matrix $N$ as $N(ab;c)=1$ if $abc\in L$ and otherwise $0$, then we also have $NFA(L)\ge COV(N)$.

Is there an $L$ for which $NFA(L)>COV(M)+COV(N)?$

By what function of $COV(M)$ and $COV(N)$ can we upper bound $NFA(L)?$

The bounds...

We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper.

...cannot be substantially improved

There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof of the gap, is an adaptation of a similar example illustrating the limitations of 2-party protocols for proving lower bounds on nondeterministic state complexity from (Hromkovič et al. 2009):

We use the alphabet $[n]= \{\,1,2,\ldots,n\,\}$. Let $L=\{\,xyz\in [n]^3 \mid x=y \vee x\neq z \,\}$.

We first take care of $Cov(M)$. Observe that if $w=xyz$ with $y=z$, then
$w \in L$: in case $x=y$, $w\in L$ and in case $x\neq y$, we also have
$x\neq z$ and thus $w\in L$. Also, if $w$ is of the form $xyz$ with
$y\neq z$, then $w\in L$ iff $x\neq z$. So we can write $L = L'\cup L''$,
with $L'=\{xyz\in [n]^3 \mid y=z\}$ and $L''=\{\,xyz\in [n]^3 \mid y\neq z
\wedge x \neq z \,\}$.

Now consider the bipartite graphs $G' = (U',V',E')$ with $U'=[n]$, $V'=
\{yz \in [n]^2 \mid y=z\}$, $E' = U' \times V'$, as well
as $G'' = (U'',V'',E'')$ with $U''=[n]$, $V''= \{ yz \in [n]^2 \mid
y\neq z\}$,
$E'' = \{(x,yz) \mid x\neq z\}$, and $G = (U' \cup U'',V' \cup V'', E'\cup E'')$.
Then a biclique edge cover for the graph
$G$ gives rise to a covering of $M$ with $1$-monochromatic
submatrices, and vice versa (Theorem 21 in Gruber & Holzer 2006).

A simple kernelization trick for computing a biclique edge cover for $G'$
is to put the twin vertices from $U'$ into equivalence classes. Then we do the same in the resulting graph for the twin vertices from $V'$.
Twin vertices are those with identical neighborhood.
This step does not alter the minimum number of bicliques needed to cover all
edges in the respective graph.

The kernelization step collapses $G'$ into a graph with two vertices and
a single edge. Thus, the edges of $G'$ can be covered with a single
biclique. Applying the kernelization step to $G''$ yields a crown graph
on $2n$ vertices, whose bipartite dimension (the minimum biclique edge
cover number) is known to be $\sigma(n)$, where $\sigma$ is the inverse
function of the middle binomial coefficient (De Caen et al. 1981). Notice that $\sigma(n)=O(\log n)$.
Thus the bipartite dimension of $G$ is $1+\sigma(n)$, which is identical
to $Cov(M)$.

Now consider $Cov(N)$. Observe that if $w=xyz$ with $x=y$, then $w \in
L$. If $x\neq y$, then $x\in L$ iff $x\neq z$. So we can write $L = L'''
\cup L''''$
with $L'''=\{xyz\in [n]^3 \mid x=y\}$ and $L''''= \{xyz\in [n]^3 \mid
x\neq y \wedge x\neq z\}$. Almost the same argument as above yields
$Cov(N)=1+\sigma(n)$.

It remains to give a lower bound on the nondeterministic state
complexity of $L$. Observe that $L$ contains all words of the form $xxx$
with $x\in[n]$. For each such word $xxx$ fix an accepting computation of a minimal
NFA accepting $L$. Let $p_x$ denote the state reached after reading the
prefix $x$, and let $q_x$ denote the state reached after reading the
prefix $xx$ of the input word $xxx$. Then all pairs $(p_x,q_x)$ must be
different. For the sake of contradiction, assume $(p_x,q_x)=(p_y,q_y)$
for some $x\neq y$. Then we can construct an accepting computation
on input $xyx$, such that the NFA is in state $p_x=q_x$ after reading
the prefix $x$, and in state $q_y=q_x$ after reading the prefix $xy$.
But the string $xyx$ is not in $L$. For the state set $Q$ of the NFA, this shows
that $|Q|^2 \ge n$. Thus,
for large $n$, we obtain a subexponential separation between $Cov(M)+Cov(N)$ and $|Q|$ (the nondeterministic state complexity of $L$).

References

Dominique de Caen, David A. Gregory, Norman J. Pullman: The Boolean rank of zero-one matrices, in: Cadogan, Charles C. (ed.), 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173 (1981)
Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Report TR06-027, Electronic Colloquium on Computational Complexity (ECCC), March 2006. Short version appeared in: Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of LNCS, pages 363-374. Springer, June 2006.
Juraj Hromkovic, Holger Petersen, Georg Schnitger: On the limits of the
communication complexity technique for proving lower bounds on the size
of minimal NFAs. Theor. Comput. Sci. 410(30–32): 2972–2981 (2009)


Are all turing machines paths predictable? I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has a certain path in terms of its movement on the tape. A positive answer to the below would give a complete characterization of the paths for which the decision problem of whether a given turing machine has said path is computable.

Define the path of a turing machine to be the sequence of left and right movements it makes on an empty input. For example, this turing machine has a path which looks like LRRRLLRRRLLLRR...

Define a turing machine $M$ to be predictable if there exists another turing machine $N$ (not necessarily computable from $M$) with the following properties:

$N$ has the same path as $M$. That is, when $M$ turns left, so does $N$. When $M$ turns right, so does $N$. Although this seems like a strong restriction at first, $N$ is not required to have the same states or even the same tape alphabet as $M$ so using both of these it may still be able to do some pretty complicated stuff relative to what $M$ does.
There is a subset of $N$'s states, $Q'\subset Q$ such that whenever $N$'s head reads from a square for the last time, it must also be in a state in $Q'$. Also, we require $N$ to only enter a state from $Q'$ if it is reading from a square for the last time. Thus, in a way, $N$ is able to predict the path $M$ and $N$ are simultaneously taking.

My question is: Are all turing machines predictable?

Any help or pointers to reference materials would be appreciated, especially since the terminology here is my own and I don't know what to search to get information on this subject.

This is another way to prove that not all Turing machines are predictable.

First it's easy to note that:

all halting machines are predictable;
all machines that loop forever on a finite portion of the tape are predictable;
all machines that expand towards both sides of the tape are predictable ($N=M, Q' = \emptyset$).

The interesting case is when a machine runs forever and visits an infinite number of cells expanding only in one direction.

The following $M_{u}$ that expands rightwards is unpredictable.

at the beginning it writes $\# \langle M_0 \rangle$ on the tape;
if the rightmost part of the tape contains  $...\#\langle M_i \rangle$ then it shift it on the right adding a $H:$ before it:

$$...H:\#\langle M_i \rangle$$

($...$ is the old untouched content of the tape)

then it simulates $M_i$ on empty tape (using the rightmost part of the tape) and check if it halts in $2^{ |M_i|^i}$ space (number of cells);
if it halts in $2^{|M_i|^i}$ space it returns back to $H$, otherwise it never visits $H$ again;
at the end it clears the right part of the tape and leaves

$$...H:\# \langle M_{i+1} \rangle$$

and jump back to step 2.

Suppose that $M_u$ (possibly padded with some dummy states to increase its size) is predictable by $N_u$.

There exists $M_k$ that simulates the whole computation of $M_u$ up to $...\# \langle M_k \rangle$ (recursion theorem) and in parallel simulate $N_u$ using no more than $2^{2|M_{k-1}|^{k-1}}$ space. Indeed $N_u$ has the same path of $M_u$ by hypothesis, so after processing every $M_u(\#\langle M_i \rangle)$, $M_k$ can shift the whole tape to the leftmost cell and continue with $M_u(\#\langle M_{i+1} \rangle)$ (both $M_u$ and $N_u$ will never use space on the left of $\#$ again). Finally it can discover if $M_k$ (itself) halts in space $2^{|M_k|^k}$ immediately after step 2: it's enough to examine whether $N_u$ is in a $Q'$ state when the simulated $M_u$ writes the $H$ or not.

If it uses less than $2^{|M_k|^k}$ space then $M_k$ can loop right and never halt, otherwise it halts; this leads to a contradiction ($M_k$ would be able to diagonalize itself).


Distributing a binary relation into bins such that each element is in a small number of bins We are given pairs of objects (say, numbers). Each object appears in at most $q$ pairs. Our goal is to distribute the pairs into equal-size  bins, such that each object occurs in as few as possible different bins.

More precisely, we are interested in a function $f$ with the property that for every binary relation with $m$ pairs with at most $q$ pairs per object, there is a distribution of the pairs to $p$ bins, such that each bin receives $m/p$ pairs ($p$ should divide $m$), and no object occurs in more than $f(m,q,p)$ bins.

This question came up in our research on parallel query evaluation. One would expect that $m$ is large compared to $p$. The "right" size of $q$ is less clear. An interesting size for $q$ could be, e.g., $\sqrt{\frac{m}{p}}$. A function that does not depend on $q$, but only works for a certain range of $q$ would also be useful (but not $q=O(1)$).

Actually, we are after bounds of the form $p^{1-\epsilon}$, with $\epsilon>0$ as large as possible...

This is not an answer.  It is just the somewhat trivial observation that WLOG you can relax the requirement that there be exactly $p$ edge subsets $\{E_i\}_i$ of exactly the same size, and instead just look for any number of edge subsets of of size $O(\textsf{the desired size})$.  Maybe this helps think about the problem.

Fix any graph $G=(V,E)$ and integer $p\ge 1$.  Let $s=\lceil |E|/p\rceil$

Lemma. Suppose there are subgraphs $\{G'_j=(V'_j,E'_j)\}_j$ such that $\{E'_j\}_j$ partitions $E$ into (any number of) parts of size $O(s)$.
Let $$M = \max_{v\in V} |\{j : v\in V'_j\}|$$
be the maximum number of parts that any vertex is in.

Then there are $p$ subgraphs $\{G_i=(V_i,E_i)\}_i$ such that $\{E_i\}_i$ partitions $E$ into exactly $p$ parts each of size at most
$s=\lceil |E|/p\rceil$, and
$$\max_{v\in V} |\{i : v\in V_i\}| = O(M).$$

Proof.  Starting with the sequence $E'_1, E'_2, \ldots, E'_{p'}$, replace each part $E'_j$ in the sequence by any ordered sequence of the edges contained in that part.  Let $e_1, e_2, \ldots, e_m$ be the resulting sequence (a permutation of $E$ such that each part $E'_j$ is some "interval" $\{e_a, e_{a+1}, \ldots, e_b\}$ of edges in the sequence).  Now partition this sequence into $p$ contiguous subsequences such that each except the last has size $s$, and let $E_i$ contain the edges in the $i$th contiguous subsequence.  (So $E_i = \{e_{i\,s+1}, e_{i\,s+1}, \ldots, e_{(i+1)s}\}$ for $i<p$.)

By assumption each part $E'_j$ has size $O(s)$, and by design each part $E_j$ except the last part $E_p$ has size $s$, so (because of the way $\{E_i\}_i$ is defined) the edges in any given part $E'_j$ are split across $O(1)$ parts in $\{E_i\}_i$.  This, and the assumption that each vertex occurs in at most $M$ of the parts in $\{E'_j\}_j$, imply that each vertex occurs in at most $O(M)$ of the parts in $\{E_i\}_i$.  QED


Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs? Given an undirected graph $G$ with $n$ vertice and $m$ edges, can we construct $p$ complete $k_i$-partite graphs, where $p$ is finite (of course) and each vertex appears at most a constant number of times, satifying " the sum of such $p$ complete $k_i$-partite graphs is $G$ " ?  Moreover, such construction can be done in poly-time ?

I think the answer to your first question is "no".

In particular, if you take a random bipartite graph $G=([n],[n],E)$
where $Pr[(i,j)\in E] = 1/2$ for each pair $(i,j)$,
the answer is no with probability close to 1.

I am interpreting your first question as follow:

Given any graph $G$, is it always possible to find a collection of subgraphs such that

each subgraph is a complete $k$-partite graph for some $k$,
each edge in $G$ occurs in at least one of the subgraphs, and
each vertex in $G$ occurs in at most a constant number of the subgraphs?

Proof.
Fix $n$.  Let $G$ be the random graph described above.

Since $G$ is bipartite any complete $k$-partite subgraph has to be bipartite.

First, I claim that with probability $1-o(1)$, every complete bipartite subgraph of $G$ has at most $4n$ edges.

(Here's why.
For any pair of subsets $L\subseteq [n]$ and $R\subseteq [n]$ with $|L\times R| \ge 4n$,
the probability that the complete bipartite subgraph with edge set $L\times R$
is in $G$ is $2^{-|L\times R|} \le 2^{-4n}$.
There are fewer than $2^n\times 2^n = 4^n$ such pairs $L$ and $R$,
Thus, by the naive union bound, the probability that any of
the corresponding subgraphs is present in $G$ is at most $4^n 2^{-4n} \le 2^{-2n}$.)

Also, with probability $1-o(1)$, the graph $G$ has at least $n^2/4$ edges.

Thus, with probability $1-o(1)$, every complete bipartite subgraph in $G$
has at most $4n$ edges, and $G$ has at least $n^2/4$ edges.
Assume this happens.

Now suppose for contradiction that a collection of subgraphs with the desired properties exists.
Each of the subgraphs has edge set $L\times R$ for some pair of subsets $L$ and $R$.
In $G$, direct all the edges in $L\times R$ from the larger side to the smaller side
(to the left if $|L|\le |R|$, and to the right otherwise).
Since $|L\times R|\le 4n$, the smaller of $L$ or $R$ must have size at most $2\sqrt n$.

Since each vertex is in $O(1)$ of the subgraphs, each vertex now has $O(\sqrt n)$
edges directed out of it.  But all edges are directed one way or the other,
so the number of edges in $G$ is at most the number of vertices
times the maximum out-degree of any vertex, that is, at most $O(n\sqrt n)$.
This contradicts the graph having at least $n^2/4$ edges.


What relations has different bounds for NP? this is my first question here so I hope I've done everything correctly.

I know that if someone finds a polynomial solution to any of the famous NP problems, all of them has one (polynomial solution).

Does this hold for say a k^n solution (and if, must they all have the same exponent) ?

And my real question, is there some relation among NP problems in the sense that say one solution is n! then another can't be (n²)! or is that (the n²) 'eaten up' by the "!" ?

Please point me in the right direction if you can.

Thanks for your time and I hope my question is clear enough.

NP-complete problems can be polynomial-time reduced to each other via Karp/Cook/Levin reductions. Since polynomials are closed under composition, if there's a polynomial bound $f(\cdot)$ on the running time of an algorithm to solve NP-complete problem $A$, then for every NP-complete problem $B$ which reduces to $A$ in polynomial-time $g(\cdot)$, there will be an algorithm which solves  $B$ in time bounded by $f(g(\cdot))$ which is a polynomial.

This does not hold for bounds other than polynomial. For instance, if there's a $2^n$ bound on solving $A$, there can be a $2^{n^{10}}$ bound on solving $B$. See this topic for more info.


Should the Schedule of ``High-level Operations'' Respect the Linearizability of ``Low-level Operations'' in Proof of Simulation Algorithm? Backgroud

I am reading Chapter 10 ``Fault-Tolerant Simulations of Read/Write Objects'' of the Book Distributed Computing (by Hagit Attiya & Jennifer Welch). Specifically, in section 10.2.3, it simulates a multi-writer multi-reader read/write register from single-writer multi-reader registers.

Simulation Algorithm

  The idea of the algorithm is to have each writer announce each value it desires to write to all the readers, by writing it in its own (single-writer multi-reader) registers; each reader reads all the values written by the writers and picks the most recent one among them.

The algorithm uses vector clock to compare the values written by the writers and find the most recent one among them. The pseudocode appears in Figure , where

  $TS[i]:$ The vector timestamp of writer $p_i$, $0 \le i \le m - 1$. It is written by $p_i$ and read by all writers.
  $Val[i]:$ The latest value written by writer $p_i$, $0 \le i \le m - 1$, together with the vector timestamp associated with that value. It is written by $p_i$ and read by all readers.

Correctness Proof

There are two types of operations in the algorithm:

high-level operation: operation on simulated object $R$ (i.e., $read_r(R)$ and $write_w(R,v)$ in the pseudocode).
low-level operation: operation on $TS[i]$ and $Val[i]$.

  To prove that the simulation is correct we have to show that every admissible execution is linearizable. Consider any admissible execution $\alpha$. To show that $\alpha$ is linearizable, we have to show that there is a permutation $\pi$ of the high-level operations in $\alpha$ that preserves the order of non-overlapping operations, and in which every read operation returns the value of the latest preceding write.

My Problem

As the last paragraph indicated, we consider the schedule of high-level operations. So my problem is:

  Should the schedule of high-level operations also respect the linearizability of low-level operations?

To illustrate, consider the following admissible (according to the simulation algorithm) execution:

  Assume $TS[i][i] = 0, \forall 0 \le i \le m - 1$ initially. $m$ writers write concurrently. They all first execute Line 10 - Line 11 in procedure $NewCTS_w()$ and thus obtain $TS[i][i] = 0, \forall 0 \le i \le m - 1$. Then, they execute Line 12 in some order (for example, in the order of pid). In this scenario, when all writers finish, the system state can be stated as
  $$S = \left\{ \begin{array}{ll}
\langle 1, 0 , 0, \ldots, 0 \rangle \\
\langle 0, 1 , 0, \ldots, 0 \rangle \\
\langle 0, 0 , 1, \ldots, 0 \rangle \\
\langle 0, 0 , 0, \ldots, 1 \rangle
\end{array} \right.$$

In the linearizability proof, the $m$ high-level writes will be put in an order, for example, according to their pids. However, if we consider the low-level operations in such order, the second writer cannot obtain $\langle 0, 1, 0, \ldots, 0 \rangle$. Instead, it should obtain $\langle 1, 1, 0, \ldots, 0 \rangle$, because it is put after the first writer's high-level write operation.

  Problem: I am confused about the situation. What is wrong of my argument? Should the schedule respect the linearizability of low-level operations in simulation algorithm? Or, what does it mean to respect it?

I understand the proof as follows.
Start with an arbitrary execution of the above algorithm. In this execution each operation on $TS[i]$ and $Val[i]$ has already been linearlized by assuming that these are single-writer multi-reader atomic registers. Therefore, by assumption, the schedule linearizes these low level operations.

The remainder of the proof shows that there exists some unique assignment of distinct times for each high-level operation such that the following are true.

For each such operation that starts at time $t_s$ and ends at time
$t_e$, the assigned time $t_a$ is in the interval $[t_s,t_e]$.
The sequence of high-level  reads and writes, as determined by this assignment of times, satisfies the linearlizability.


Expected empirical entropy I'm thinking about some properties of the empirical entropy for binary strings of length $n$ when the following question crosses my way:

$\underbrace{\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize nH_{0}(w)}_{\large\#}\;\overset{?}{=}\;n-\varepsilon_{n}\;\;\;$
with $\;\;\lim\limits_{n\rightarrow\infty}\varepsilon_{n}=c\;\;\;$ and $\;\;\;\forall n:\;\varepsilon_{n}>0$
where $c$ is a constant.
Is that equation true? For which function $\varepsilon_{n}$ respectively which constant $c$?
$ $
$n=2\;\;\;\;\;\;\;\rightarrow\;\#=1 $
$n=3\;\;\;\;\;\;\;\rightarrow\;\#\approx 2.066 $
$n=6\;\;\;\;\;\;\;\rightarrow\;\#\approx 5.189 $
$n=100\;\;\;\rightarrow\;\#\approx 99.275 $
$n=5000\;\rightarrow\;\#\approx 4999.278580 $
$n=6000\;\rightarrow\;\#\approx 5999.278592 $

$ $
Backround
$ $
$H_{0}(w)$ is the zeroth-order empircal entropy for strings over $\Sigma=\left\{0,1\right\}$:

$H_{0}(w)=\frac{|w|_{0}}{n}\log\frac{n}{|w|_{0}}+\frac{n-|w|_{0}}{n}\log\frac{n}{n-|w|_{0}}$

where $|w|_{0}$ is the number of occurences of $0$ in $w\in\Sigma^{n}$.
The term $nH_{0}(w)$ corresponds to the Shannon-entropy of the empirical distribution of binary words  with respect to the number of occurences of $0$ respectively $1$ in $w\in\Sigma^{n}$.
More precise:
Let the words in $\left\{0,1\right\}^{n}$ be possible outcomes of a Bernoulli process. If the probability of $0$ is equal to the relative frequency of $0$ in a word $w\in\left\{0,1\right\}^{n}$, then the Shannon-entropy of this Bernoulli process is equal to $nH_{0}(w)$.
At this point, my question should be more reasonable since the first term normalizes the Shannon-entropies for all empirical distributions of words $w\in\left\{0,1\right\}^{n}$.
Intuitively I thought about getting something close to the Shannon-entropy of the uniform distribution of $\left\{0,1\right\}^{n}$, which is $n$.
By computing and observing some values I've got the conjecture above, but I'm not able to prove it or to get the exact term $\varepsilon_{n}$.
It is easy to get the following equalities:
$\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize nH_{0}(w)\;\;=\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize |w|_{0}\log\frac{n}{|w|_{0}}+(n-|w|_{0})\log\frac{n}{n-|w|_{0}}$
$=\large\frac{1}{2^{n}}\normalsize\sum\limits_{k=1}^{n-1}$ $n\choose k$ $\left(k\log\frac{n}{k}+(n-k)\log\frac{n}{n-k}\right)$
and it is possible to apply some logarithmic identities but I'm still in a dead point.
(the words $0^{n}$ and $1^{n}$ are ignored, because the Shannon-entropy of their empirical distributions is zero)
Any help is welcome.

Here is another approach, based on information theory and heavily inspired by @usul's answer. It shows that $\epsilon_n=O(1)$ with very few calculations, and can be used to prove that $\epsilon_n \rightarrow \log_2 \sqrt{e}$ and to derive good estimates on the rate of convergence with less calculations than @usul's approach. In fact, I find a closed-form expression for $\epsilon_n$ : $$(1)  \; \; \; \; \epsilon_n = n \left( H(Binom(n,1/2)) - H \left( Binom \left( n-1, 1/2 \right) \right) \right) \ .$$

Details:

Let $X$ be a uniform random variable in $\{0,1\}^n$. Let $K$ be a random variable equal to the number of 1's in $X$. The expression $\#$ that @Danny wants to analyze is exactly equal to $n \cdot \mathbb{E}_{k} [H(X_1 | K=k)]$. (Here $X_1$ is the first bit of $X$.) By the basic properties of the entropy operator,
$$(2)  \; \; \; \; \# = n\mathbb{E}_{k} [H(X_1 | K=k)]=nH(X_1|K)=n(H(X_1K)-H(K))=n(H(K|X_1)+H(X_1)-H(K)) = n(1-H(Binom(n,1/2)) + H(Binom(n-1,1/2))) \ .$$
The last equality follows from the fact that $X_1$ is just a uniformly random bit, $K$ is the binomial distribution, and $K|(X_1=x_1)$ is distributed either as $Binom(n-1,1/2)$ or as $Binom(n-1,1/2)+1$, depending on the value of $x_1$, both of which have the same entropy.

This already gave us equation (1). Now we just need to calculate to get the value of $\lim_{n \rightarrow \infty} \epsilon_n$

We use any known estimation for the entropy of a binomial RV, such as here. We see that $$ (3)  \; \; \; \; H(K)=H(Binom(n,1/2))=\frac12 \log_2 ( \pi en / 2) + O(1/n) \ ,$$ and, similarly, that $$H(K|X_1)=H(Binom(n-1,1/2))=\frac12 \log_2 ( \pi e(n-1)/2) + O(1/n) \ .$$ Canceling out terms and substituting into (1), we get $$ (4)  \; \; \; \; \epsilon_n = n \cdot (H(K)-H(K|X_1)) = n \cdot \frac12 (\log_2 (n/(n-1)) + O(1/n)) = \\ \frac12 \log_2 ((n/(n-1))^n) + O(1) \rightarrow \log_2(\sqrt{e}) + O(1) \ . $$

By slightly improving the approximation (3) we should be able to replace the $O(1)$ term in (4) by $O(1/n)$ and therefore get that, indeed, $\lim_{n \rightarrow \infty} \epsilon_n = \log_2 \sqrt{e}$. To get this better estimation it should be enough to check that $H(Binom(n,1/2))=\frac12 \log_2 ( \pi en / 2) + err(n)$ where $err(n)=O(1/n)$ and $err$ is a monotone function.


Regular language that discriminates between two deterministic CFGs Suppose you are given two deterministic push down automata which recognize languages $A$ and $B$, and wish to determine whether there is a regular language $R$ such that $A \subseteq R$ and $R \cap B = \emptyset$. Basically, the challenge is to determine whether there is a DFA that can recognize which of the two languages any given string comes from, given that it comes from one of those languages.

Is this decideable? If so, what is the complexity? Can the DFA be constructed explicitly?

Eryk Kopczyński[1] showed in 2015 that separability (that's the name of your problem) of visibly pushdown languages by regular languages is undecidable.  The class of visibly pushdown languages is a strict subset of deterministic CFL.

[1]:    Eryk Kopczyński, Invisible Pushdown Languages, LICS'16, available at https://arxiv.org/abs/1511.00289


Is BQP equal to BPP with access to an Abelian hidden subgroup oracle? Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Like many complexity-class separations, our best guess is that the answer is that BPP^{HSP} != BQP, but we can only prove this rigorously relative to oracles.  This separation was observed by Scott Aaronson in this blog post
where he observed that the welded-tree speedup of Childs, Cleve, Deotto, Farhi, Gutmann and Spielman was not contained in SZK.

On the other hand, BPP^{HSP} is contained in SZK, at least if the goal is to determine the size of the hidden subgroup.  This includes even the abelian HSP, although I'm not sure how exactly to find the generators of an arbitrary hidden subgroup in SZK.  The reason we can decide the size of the hidden subgroup is that if f:G->S has hidden subgroup H, and we choose g uniformly at random from G, then f(g) is uniformly random over a set of size |G|/|H|. In particular, f(g) has entropy log|G| - log|H|.  And entropy estimation is in SZK.


Is parameterized complexity going to be the future of complexity theory? I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I don't mean that other are not) in terms of number of research papers. I have seen that researchers from communication complexity, arithmetic complexity etc. are also using various parameters to greater extent.

Question :  Is parameterized complexity going to be the future of complexity theory? Future just means number of research papers, number of researchers working in that area etc.

Please note that I am naive and may not be aware of many things.

Predicting the future is nigh impossible, especially so for cutting-edge research. I don't think anyone predicted how much impact deep learning is now having or that cryptography would be taken over by indistinguishability obfuscation.

That said, I will say this much: I don't see any particular reason to expect parameterized complexity to take over. It's a mature field that has been active for something like 20 years. It doesn't really strike me as an up-and-coming area. To be clear, I think it's a successful area that will continue to thrive.

If you look on google trends, search interest in parameterized complexity has been declining. (Stick in some other terms for a comparison if you're interested.) If you look up the combined citations for the Downey-Fellows textbook Parameterized Complexity and their updated textbook, you see that they are pretty stable:

(Source: Google scholar. I added both books to my own profile, merged them, took a screenshot of the combined citations, and then deleted them from my profile.)

This is a healthy number of citations, but it is not the exponential growth that would make you think parameterized complexity is going to take over. Of course, this data is very flawed, but it's the best indication I can find of the global popularity of parameterized complexity.

Note that things can be very popular locally even if they aren't popular globally.
When I was an undergrad, I thought that I needed to learn about category theory because everyone around me was talking about it; I even bought a book. Then I moved on to grad school and never heard about it again; the book remains unread to this day.
Perhaps you are in a similar situation -- you are in a department where there is a lot of parameterized complexity going on, but, if you move somewhere else, the story will be completely different.