Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties:

The size of $\psi$ is polynomial in $|\phi|$
$\psi$ has an odd number of satisfying assignments if and only if $\phi$ has an odd number of satisfying assignments
The number of satisfying assignments of $\psi$ is polynomial in $|\psi|$.

Unless I'm wrong, that would mean that having a $\mathbf{NP}$ oracle allowed to formulate polynomially many queries would somehow be equivalent in power to having a $\oplus \mathbf{P}$ oracle.

Question
What would be the consequences of the existence of such reduction? Which surprising collapses would happen, if any? Would any widely believed conjecture be disproven?

The polynomial hierarchy would collapse to the fourth level (indeed, the third, see below).
Proof. First, we get that $\oplus P\subseteq \Sigma_2^P$. This is because a $\Sigma_2^P$ machine can use its $\exists$ quantifier to guess a polynomial number of assignments and then, using its $\forall$ quantifier, verify that this list contains all of the formula's satisfying assignments. By Valiant-Vazirani we have $PH\subseteq BPP^{\oplus P}$. We have $BPP\subseteq \Sigma_2^P$, so we get $BPP^{\oplus P}\subseteq {\Sigma_2^P}^{\oplus P}\subseteq {\Sigma_2^P}^{\Sigma_2^P}=\Sigma_4^P=PH$. $\square$
@Emil Jerábek gives a stronger argument; the polynomial hierarchy collapses to the third level. This is because counting assignments can be done in $P^{NP}$, which is better than the $\Sigma_2^P$ method described above.
Proof. We get $\oplus P\subseteq P^{NP}$, because a $P^{NP}$ algorithm can count a formula's satisfying assignments, if it is polynomially-bounded. (algorithm below). Consequently, we get $PH\subseteq BPP^{\oplus P}\subseteq BPP^{P^{NP}}=BPP^{NP}\subseteq \left(\Sigma_2^P\right)^{NP}=\Sigma_3^P=PH$.
Algorithm [For counting satisfying assignments in $P^{NP}$].$\quad$ Given a Boolean formula $\psi$, query the oracle. If the formula is not satisfiable, return. Otherwise, find a satisfying assignment $x$ using $n$ more queries to the oracle. Remove the assignment, i.e., construct a new formula $\psi^\prime:=\psi\wedge \neg x$. Repeat this procedure until the oracle returns ``not satisfiable''. This happens exactly after all the satisfying assignments have been "removed". This procedure therefore runs in time polynomial in the number of satisfying assignments, which, by assumption, is polynomial.
The inclusion $\oplus P\subseteq P^{NP}$ is obtained by simply returning ``yes'' at the end of the computation if and only if the number of satisfying assignments is discovered to be odd. $\square$
Perhaps there are other consequences; I hope others can give some.


On complexity class $\mathsf{\Pi_2 L}$ I suggest the following definition of $\mathsf{\Pi_2 L}$  (similarly to the certificate definition of $\mathsf{NL}$):

A language $L$ belongs to $\mathsf{\Pi_2 L}$ iff there exists a deterministic Turing Machine $M$ and polynomials $p$ and $q$ such that

$$x \in L \Leftrightarrow \forall z \in \{0,1\}^{p(|x|)} \exists y \in \{0,1\}^{q(|x|)} M(x, z, y) =1.$$
Here $x$ is placed on its input tape and $z$ and $y$ are placed
on its special read-once tapes, and $M$ uses at most $O(\log |x|)$ space on its read/write tapes for every
input $x$. We can read $z$ and $y$ simultaneously.

What can we say about this complexity class? Since $\mathsf{NL} \subseteq \mathsf{P}$
we have  $\mathsf{\Pi_2 L} \subseteq \mathsf{coNP}$. Can we say something else about this class? An example of a language from $\mathsf{\Pi_2 L}$ is here: Is unary $\Pi_2$-SUBSETSUM coNP-complete?

If I got this right, $\Pi_2L$ as defined above is equal to co-NP. The co-NP-complete DNF tautology sits in $\Pi_2L$: Use z for the assignment and y to choose which clause to check. To show $\Pi_2L$ in co-NP, universally guess z and the rest can be computed in P.


Binary matrix column subset selection complexity Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no row containing only zeroes, in other words, every row contains at least one $1$?

For example, given the $4 \times 3$ matrix

$\begin{bmatrix} 1 & 0 & 0 & 1 \\
                 0 & 1 & 1 & 0 \\
                 0 & 0 & 0 & 1 \\
                 1 & 1 & 0 & 1 \end{bmatrix}$

a subset of $k=3$ columns that fails to fulfill this condition is that of the first columns, as the third row has all zeros within this submatrix, but the column set $\{1, 3, 4\}$ would be a solution.

I suspect this is a hard problem, but I haven't been able to find a direct reference. I'm interested in this problem because of its applications in cryptography.

Rephrasing as a set system, each row represents a subset $E_i$ of some set $X$, for $i=1,2,\dots,m$.  You want a set $Y \subseteq X$ with at most $k$ elements, such that $E_i \cap Y \ne \emptyset$ for each $i$.  In other words, you want a hitting set of size at most $k$; this problem is NP-complete.


Proving that inclusion is antisymmetric in Coq I'm a Coq newbie and I'd like to prove that the inclusion relation is antisymmetric, that is: $\forall x\forall y(x\subseteq y\land y\subseteq x\rightarrow x=y)$.

I wrote the following thing:

Section Test.
Variable set : Type.
Variable element : set -> set -> Prop.
Definition subset (x:set) (y:set) := forall z:set, element z x -> element z y.
Axiom equality : forall x y:set, x = y <-> forall z:set, element z x <-> element z y.
Theorem inclusion_is_antisymmetric : forall x y:set, subset x y /\ subset y x -> x = y.
Proof.
intros a b.
unfold subset.
intro H.
destruct H as [H0 H1].

At this point I get the following output:

1 subgoal
set : Type
element : set -> set -> Prop
a : set
b : set
H0 : forall z : set, element z a -> element z b
H1 : forall z : set, element z b -> element z a
______________________________________(1/1)
a = b

I'm stuck now because I don't know how to:

change the goal from $a=b$ to $\forall z(z\in a\leftrightarrow z\in b)$ and then to $c\in a\leftrightarrow c\in b$
change H0 from $\forall z(z\in a\rightarrow z\in b)$ to $c\in a\rightarrow c\in b$
change H1 from $\forall z(z\in b\rightarrow z\in c)$ to $c\in b\rightarrow c\in a$

That is, I know how to prove this theorem on paper but not with Coq.

Theorem inclusion_is_antisymmetric : forall x y:set, subset x y /\ subset y x -> x = y.
Proof.
  firstorder using equality.
Qed.


What are some good references for mathematical optimization for the layman? I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' behind achieving it. Basically the 'big-picture' view of things excluding the complicated math if possible.

I've read numerous articles on the web and TCS too :) but still would like to know some good references for the layman (i.e. if you were to explain the various concepts/ideas to your wife/mother/child what you recommend them?) I know they wouldn't all be listed in one book but even if they are spread out across books that's fine.

I'm quite interested in learning about nonlinear programming, semi-definite programming, convex optimization, I'm fairly well versed with linear/integer programming and do have a decent background in algorithms and a strong CS background too :)

I may not have a strong mathematical background as probably required by these topics and before I develop it I'd like to have some 'fun' understanding the 'what, why and how' at a more humane level before diving into the math :)

What would be some good references for the above? Good books/links covering other aspects of optimization but not listed above would be welcome to.

This is a very vast topic. For nonlinear optimization the book by Bertsekas is a standard reference. For convex optimization you should look at Boyd and Vandenberghe. For linear programming, the book by Schrijver is a reasonable (but dense) source.

But you should also look at course material. Each of the authors mentioned above also has course material/lecture slides that might be useful.


What will go wrong if a recursive record type has a negative eta rule? In the context of Agda like dependent type theory:

This short paper https://jesper.sikanda.be/files/vectors-are-records-too.pdf says some inductive type can be seen as records, for example Vector of fixed-length list can be seen as inductively-defined family of non-recursive types.

But they argue that for example natural number type should not have a eta rule because it is a recursive type (the original paper says N = Unit \/ N is non-terminating.)

So what will go wrong if we have this type:

data out where
  cons : out => out

in : out => out
in (cons a) = a

and give it a negative eta-rule:

(a: out)  then  a = cons (in a) judgementally

Can it proof False? Or just this is a bad idea....?

edit: It seems Agda has eta-rule for recursive records? but not for the one previously defined, see this issue https://github.com/agda/agda/issues/402 . but the previously defined one is ruled out I think by implementation issues, not theoretical one?

Having a recursive record type with eta-equality wouldn't destroy consistency of the theory, but it would destroy decidability of typechecking.

For example, let's define your out type as a record type in Agda:

record Out : Set where
  inductive
  constructor cons
  field
    in : Out

Agda doesn't use eta-equality for this type. Suppose it did, then Agda's typechecker would loop whenever it tries to solve an equation of the form x = y : Out (where x and y are two variables or neutral terms): x = y iff in x = in y iff in (in x) = in (in y) iff in (in (in x)) = in (in (in y)) ...


What is the value of this "game" (counters rebalancing)? This question was posted in CS.SE two weeks ago, but it didn't get a satisfying answer.

Suppose you have the following game:

There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized to 0.

In each step, you choose a counter $c_i$ and increase it's value by 1.

Unfortunately, every $T$ steps, each counter that has a positive value is decremented by 1.

Also, the values of the counters are bounded by $M$, so you can't increment a counter any further.

  1. Given as many steps as you like, can many positive valued counters can you reach?

  2. How many positively valued counters are reachable after $T\cdot M - 1$ steps?

For question (1), here's a a detailed buildup for $\approx T\log(M)$ positive counters:

While you have less than $T-1$ counters at value $M$:

Increment the minimal index counter whose value is strictly less than $M$.

(This has to converge as the sum of the counters are bound to increase every $T$ steps.)

Let $r = T$.
While ($c_0>1$)

a.  while ($c_0>c_r$)

Increment $c_r$

b. $r = r + 1$

Now for the analysis: first observation is that the number of positive counters is $r$.

Now let $m_r$ be the maximal value $c_{r}$ have reached. For $r=T$ we get $M(1-\frac{1}{T})$. For $r=T+1$ we get $m_r(1-\frac{1}{T})=M(1-\frac{1}{T})^2$, or in general $$\forall r\geq T:m_r = M(1-\frac{1}{T})^{r-T+1}$$

Next we notice that when $\forall m_r$ is achieved, $c_0=m_r$.
This means the loop will halt when $m_r < 1$ (give or take integrality and end-of-game-strategies).

This gives us
$$M(1-\frac{1}{T})^{r-T+1} < 1$$
$$(1-\frac{1}{T})^{r-T+1} < M^{-1}$$
$$({r-T+1}) \log (1-\frac{1}{T}) < -\log M$$
$${r-T+1}  < \frac{-\log M}{\log (1-\frac{1}{T})}$$
$$r  < \frac{-\log M}{\log (1-\frac{1}{T})} + T - 1$$
$$r  < \frac{\log M}{\sum_{k\geq 1}^{\infty} {\frac{1}{kT^k}}} + T - 1 < T(\log M + 1) -1$$

Is it possible to do better? Can anyone prove this is optimal?

Here is an upper bound for question 2.

Theorem: After $TM$ steps, you can have at most $T \log M$ positive counters.

Notation: we assign each step a number, ending with the $0$th step, and starting with the $(-TM+1)$th step.

Observation: in the optimal strategy, if you increment a counter, you do not let it return to $0$.

Proof: Let us assign a value of $1$ to each time you increment a counter in the last $T$ steps; $\frac{1}{2}$ to each time you increment a counter in the previous $T$ steps; $\frac{1}{3}$ to each time you increment a counter in the $T$ steps before that, etc. That is, if you increment a counter between step $-kT+1$ and $-(k-1)T$, it gets a value of $\frac{1}{k}$.
We need a lemma that we will prove later.

Lemma: for a counter to be positive, it must have had a total value of at least $1$ assigned to it.

With the lemma, the proof is easy:  the total value we have to assign is $T \sum_{i=1}^M \frac{1}{i} \approx T \log M$, and each positive counter requires us to have assigned total value of at least $1$ to it.

Proof of Lemma: Look at the first time you made that counter positive. If that was between $-kT$ and $-(k-1)T$, then it has been decremented at least $k-1$ times, and so you need to have incremented it $k$ times to have it end up positive. But each of these increments assigns it a value of at least $\frac{1}{k}$.

And here is an upper bound for question 1. Let's use the same overall proof strategy as before.  Again, we assign a value of $\frac{1}{k}$ when we increment a counter on a step between $-kT+1$ and $-(k-1)T$. We also assign a value of $\frac{1}{M}$ when we increment a counter on a step between $-2MT$ and $-MT$, and a value of $0$ if we increment a counter before that. By the same reasoning as before, any counter that was $0$ at step $-2MT$ must be assigned a value of at least $1$. But now, if a counter was positive at step $-2MT$, it still must have been assigned a total value of at least $1$, since it must have been incremented $M$ times to end up positive. Now, the total value we have to assign is $T\log M + T$, so we can have at most $T (\log M + 1)$ positive counters.


PCPs with imperfect completeness The traditional definition of PCPs have perfect completeness -- If $x\in L$, then the prover can give a proof on which the verifier (on reading constantly many bits) always accepts. Suppose we modify the definition as follows:

  A language $L$ is in $iPCP(r,q)$ such
  that there exists a verifier who
  tosses $r$ coins and queries $q$
  locations of a proof $\pi$ such that:

  If $x\in L$, then there exists a $\pi$ that makes the verifier accept
  with probability at least $3/4$.
  If $x\notin L$, then for every proof $\pi$, the verifier accepts with
  probability at most $1/4$.

There is an easy reduction from $3SAT$ to $\text{Max}2SAT$ (problem 5 in this) that gives a simple $iPCP$ for $3SAT$. And by definition, the class is closed under complement so it includes $coNP$ as well. Therefore, it is unlikely that there is a way to convert an $iPCP$ to a $PCP$ with the same parameters (well, that would at least mean $coNP = NP$).  (thanks to Peter Shor for pointing this out)

Have such incomplete PCPs been studied earlier?

Yes, PCPs with imperfect completeness have been studied before. The main motivation is that for some natural and interesting problems, finding whether there is a perfect solution is actually easy (polynomial-time), while approximating the best solution, if this best solution is not perfect, is (or believed to be) hard.

Here are some examples:

The Unique Games Conjecture. Unique games with perfect completeness are easy, so the Unique Games Conjecture focuses on unique games with imperfect completeness.
Feige and Reichman showed NP-hardness for unique games for some constant completeness and soundness values (not c=1-delta s=epsilon as conjectured).
Linear equations. Linear equations with perfect completeness are easy (using Gaussian elimination), so hardness results for linear equations (e.g., Hastad's) focus on imperfect completeness.


Proper PAC learning of 2-DNF under uniform distribution What is the state of art result about query complexity of proper PAC learning 2-DNF formulas with sample queries and under uniform distribution? Or any non-trivial bound on it?

Because I am not familiar at all with learning theory and this question is motivated by a different field, the answer might be obvious. I checked the book by Kearns and Vazirani, but they don't seem to consider this setting explicitly.

upd. Although the main parameter of interest is query complexity, running time is also important. If possible, running time should preferably be roughly the same as query complexity or at most polynomial.

upd. Appendix B (top of the page 18) of the paper "Learning Submodular Functions" by Balcan and Harvey mentions that "It is well known that 2-DNFs are efﬁciently
PAC-learnable." However, they don't mention, whether this result is for proper learning or give any reference.

I don't know if you'll consider the following a non-trivial bound, but here I go.

First, to be clear so that we're not confusing $c$-DNF with $k$-term DNF (which I often do), an $c$-DNF formula over variables $x_1, \ldots, x_n$ is of the form $\vee_{i=1}^{k}(\ell_{i,1} \wedge \ell_{i,2} ... \ell_{i,c})$ where $\forall 1 \le i \le k$ and $1 \le j \le c$, $\ell_{i,j} \in \{x_1, \ldots, x_n, \bar{x}_1, \ldots, \bar{x}_n \}$.

We can first ask how many distinct terms can exist in an $c$-DNF.  Each term will have $c$ of the $n$ variables, each either negated or not -- making for $2^c\binom{n}{c}$ different possible terms.  In a 2-DNF instance, each term will either appear or not, making for $|\mathcal{H}| = 2^{2^c\binom{n}{c}}$ possible "targets," where $\mathcal{H}$ is the hypothesis space.

Imagine an algorithm that takes $m$ samples and then tries all of the $|\mathcal{H}|$ hypotheses until it finds one that predicts perfectly on the samples.  Occam's Razor theorem says that you only need to take about $m = O(\frac{1}{\epsilon}|(\mathcal{H}|+\frac{1}{\delta})$ samples for this algorithm to find a target with error $\le \epsilon$ with probability $\ge 1-\delta$.

In our case, for $c=2$, $\lg|\mathcal{H}| = O(n^2)$, which means you'll need about $n^2$ samples to do the (proper) learning.

But the whole game in learning is not really sample complexity (though that's part of the game, especially in attribute-efficient learning), but rather in trying to design polynomial-time algorithms.  If you don't care about efficiency, then $n^2$ is the simplest answer for PAC sample complexity.

UPDATE (given the changed question):

Because you explicitly stated that you only cared about sample complexity, I presented the brute-force Occam Algorithm, which is the probably the simplest argument.  However, my answer was a bit coy.  $2$-DNF are actually learnable in polynomial time!  This is a result from Valiant's original paper, "A Theory of the Learnable."  In fact $c$-DNF are learnable for any $c = O(1)$.

The argument goes as follows.  You can view a $c$-DNF as a disjunction of $\approx n^c$
"meta-variables" and try to learn the disjunction by eliminating the meta-variables inconsistent with the examples.  Such a solution can be easily translated back to a "proper" solution, and takes $O(n^c)$ time.  As a side-note, it is still open whether there is polynomial-time algorithm for $c = \omega(1)$.

As to whether the $n^2$ sample complexity is also a lower bound, the answer is pretty much yes.  This paper by Ehrenfeucht et al. shows that the Occam bound is almost tight.


Is it possible to create a "quote" function that, given a native λ-term, returns its λ-encoded representation? Suppose we implement the λ-calculus inside the λ-calculus itself with λ-encodings and Bruijn indices:

Lam = λ body .        λ Lam . λ App . λ Var . Lam body
App = λ fun . λ arg . λ Lam . λ App . λ Var . App fun arg
Var = λ idx .         λ Lam . λ App . λ Var . Var idx

Is it possible to implement a quote() function that, given a native term, returns its own λ-encoded representation? For example:

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

Would return:

Lam (Lam (App (Var 1) (App (Var 1) (Var 0))))

If not, is it possible if given a type?

quote(Arr(Arr(T,T),Arr(T,T)), λ f . λ x . f (f x)))

Where Arr(Arr(T,T),Arr(T,T)) represents that the term we want to quote has the following STLC type: (o -> o) -> o -> o.

No, this is not possible, assuming you want to go from an arbitrary lambda term to some first-order AST.

The lambda calculus is extensional, which means that the lambda calculus cannot distinguish between two lambda-terms which are behaviourally equivalent. Eg, if you have terms implementing quick sort and merge sort, then no other lambda-term can distinguish them, since they are both extensionally the same function. As a result, full quotation is impossible, since it should let you get different source code for those two terms.


Are there distribution properties which are "maximally" hard to test? A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required to decide (w.h.p) if $D\in P$ or $d(D,P)>\epsilon$ ($d$ here is usually the $\ell_1$ distance). The most common measure of complexity is the number of samples used by the algorithm.

Now, in standard property testing, where you have query access to some object, a linear lower bound on query complexity is obviously the strongest lower bound possible, since $n$ queries would reveal the entire object. Is this the case for distribution testing as well?

As far as I understand, the "trivial" upper bound for testing properties of distributions is $O(n^2\log n)$ --- by Chernoff bounds, this is enough to "write down" a distribution D' which is close to D in $\ell_1$ distance, and then we can just check if there are any distributions close to D' which are in P (this might take infinite time, but this is irrelevant to sample complexity).

Is there a better "trivial" test for all distribution properties?
Are there any distribution properties for which we know sample lower bounds stronger than linear?

Sorry for unearthing this post -- it is quite old, but I figured having it answered may not be that bad an idea.

First, it looks like you performed your Chernoff bound with some slightly odd setting of parameters. Note that to perform your suggested "testing by learning" approach, it is sufficient to learn the distribution in total variation distance (or $\ell_1$, if you prefer, which is the same up to a factor 2) to distance $\frac{\varepsilon}{2}$. (before checking "offline" if there is any distribution $p'$ having the property $\mathcal{P}_n$ which itself is at distance at most $\frac{\varepsilon}{2}$ from your learnt hypothesis $\hat{p}$). This would naively lead to an $O\big(\frac{n\log n}{\varepsilon^2}\big)$ sample complexity upper bound for this approach; however, it is known (and "folklore") that learning an arbitrary distribution over a domain of size $n$ up to distance $\varepsilon$ (in total variation distance) can be done with only $O(\frac{n}{\varepsilon^2})$ samples (and this is tight).

So the baseline should actually be $O(\frac{n}{\varepsilon^2})$, which is already linear in $n$. Now, one can ask the next question -- are there "natural" properties for which testing (say, for constant $\varepsilon$) requires a linear dependence in the domain size $n$?

The answer is (as far as I know) "not quite, but close." Namely, following a significant line of work on estimating properties of distributions (or equivalently, tolerant property testing), the results of Valiant and Valiant imply (STOCS'11, FOCS'11, and some others) that the rather contrived property "being $1/10$-close to uniform" has sample complexity $\Theta_\varepsilon(\frac{n}{\log n})$.

(Note that it's a bit "cheating," in the sense that the property is simply a way to take a tolerant testing question and relabel it as testing of an ad hoc property).

If that is not entirely sufficient to quench your thirst, one can also show that for the (natural?) property of "being a $k$-histogram" (is the distribution piecewise constant on a set of $k$ unknown intervals?), setting $k=n/10$ for instance also results in an $\Omega(\frac{n}{\log n})$ lower bound (it's in a paper of mine from 2016; the lower bound follows from a rather simple reduction to the Valiants' result). Now, whether you consider "being an $\frac{n}{100}$-histogram" to be a natural property is up to you.


Question about non-private databases and $1^n$ I am reading a paper called "Revealing Information while Preserving Privacy", by Dinur and Nissim.  There is a definition in the paper called

Definition 3 (Non-Privacy).  A database $\mathcal{D} = (d, \mathcal{A})$ is $t(n)$-non-private if for every constant $\epsilon > 0$ there exists a probabilistic Turing Machine $\mathcal{M}$ with time complexity $t(n)$ so that Pr[$\mathcal{M}^{\mathcal{A}}(1^n)$ outputs $c$ s.t. $dist(c, d) < \epsilon n$] $\geq 1 - neg(n)$.  The probability is taken over the coin tosses of $\mathcal{A}$ and $\mathcal{M}$.

As I understand it, this basically means that with high probability, we can always find some algorithm that essentially outputs the database (or a version of the database that differs on an arbitrarily small fraction of rows) in $t(n)$ time.

But I am having trouble understanding the part about $\mathcal{M}^{\mathcal{A}}(1^n)$.  Is $1^n$ just the number $1$ repeated $n$ times?  Why would we want to use $1^n$ as the input to the algorithm?

Thanks.

As Huck Bennett pointed out, $1^n$ is the "security parameter", which is a cryptographer's way of expressing that the input has length n.  They express the input this way to make it easier to prove theorems about time complexity, resource requirements, etc, that are all supposed to be expressed in terms of the size of the input, instead of its value.


Equivalent formulation of complexity theory in Lambda Calculus? In complexity theory the definition of time and space complexity both reference a universal Turing machine: resp. the number of steps before halting, and the number of cells on the tape touched.

Given the Church-Turing thesis, it should be possible to define complexity in terms of lambda calculus as well.

My intuitive notion is that time complexity can be expressed as the number of β-reductions (we can define away α-conversion by using De Brujin indexes, and η is barely a reduction anyway), while space complexity can be defined as the number of symbols (λ's, DB-indexes, “apply”-symbols) in the largest reduction.

Is this correct? If so, where can I get a reference? If not, how am I mistaken?

As you point out, the λ-calculus has a seemingly simple notion of time-complexity: just count the number of β-reduction steps. Unfortunately, things are not simple. We should ask:

 Is counting β-reduction steps a good complexity measure?

To answer this question, we should clarify what we mean by complexity measure in the first place. One good answer is given by the Slot and van Emde Boas thesis: any good complexity measure should have a polynomial relationship to the canonical notion of time-complexity defined using Turing machines. In other words, there should be a reasonable encoding tr(.) from λ-calculus terms to Turing machines, such that for each term $M$ of size $|M|$: $M$ reduces to a value in $poly(|M|)$ exactly when $tr(M)$ reduces to a value in $poly(|tr(M)|)$.

For a long time, it was unclear if this can be achieved in the λ-calculus. The main problems are the following.

There are terms that produce normal forms in a polynomial number of
steps that are of exponential size. See (1). Even writing down the
normal forms takes exponential time.
The chosen reduction strategy
plays an important role, too. For example there exists a family of terms
which reduces in a polynomial number of parallel β-steps (in the
sense of optimal λ-reduction (2), but whose complexity is
non-elementary (3, 4).

The paper (1) clarifies the issue by showing a reasonable encoding that preserves the complexity class PTIME assuming leftmost-outermost Call-By-Name reductions. The key insight appears to be that the exponential blow-up can only happen for uninteresting reasons which can be defeated by proper sharing of sub-terms.

Note that papers like (1) show that coarse complexity classes like PTIME coincide, whether you count β-steps, or Turing-machine steps. That does not mean lower complexity classes like O(log n) also coincide. Of course such complexity classes are also not stable under variation of Turing machine model (e.g. 1-tape vs multi-tape).

D. Mazza's work (5) proves the Cook-Levin theorem (-completeness of SAT) using a functional language (a variant of the λ-calculus) instead of Turing machines. The key insight is this:

$$
  \frac{\text{Boolean
circuits}}{\text{Turing machines}}=\frac{\text{affine
  $\lambda$-terms}}{\text{$\lambda$-terms}}
  $$

I don't know if the situation regarding space complexity is understood.

B. Accattoli, U. Dal Lago, Beta Reduction is Invariant, Indeed.
J.-J. Levy, Reductions correctes et optimales dans le lambda-calcul.
J. L. Lawall, H. G. Mairson, Optimality and inefficiency: what isn't
a cost model of the lambda calculus?
A. Asperti, H. Mairson,
Parallel beta reduction is not elementary recursive.
D. Mazza, Church Meets Cook and Levin.


Is it beneficial to regularly read papers outside your field? What do you think about regularly reading papers outside one's own field, even those which are not related to one's area? My intuition is that it can give a totally different perspective or technique that may help someone in solving his or her own problems. But at the same time I am a bit skeptical about it as it will be a waste of time if the new knowledge doesn't help him in his own work.
What are your thoughts on this? Is there any other way one can look for results unrelated to his own work? What about TCS+ series?

Understanding papers outside your field can be surprisingly difficult --- every field develops its own specialized terminology and shared background knowledge. A much better advice I once received from a very productive researcher was: Try to attend research seminars outside your field. These are typically more accessible than "cold" paper reads, and you have the advantage of being able to interactively ask questions. Just talking to people about their research can be extremely useful as well. You'll occasionally hear stories about how someone from field A happened to join a lunch table with people from field B and realized that he has the tools to solve their long-standing open problem (or, conversely, they have a tool to solve his).


What parts of homotopy type theory are not possible in Agda or Coq? When we look at the book, Homotopy Type Theory - we see the following topics:

Homotopy type theory
2.1 Types are higher groupoids
2.2 Functions are functors
2.3 Type families are ﬁbrations
2.4 Homotopies and equivalences
2.5 The higher groupoid structure of type formers
2.6 Cartesian product types
2.7 S-types
2.8 The unit type
2.9 P-types and the function extensionality axiom
2.10 Universes and the univalence axiom
2.11 Identity type
2.12 Coproducts
2.13 Natural numbers
2.14 Example: equality of structures
2.15 Universal properties

Now we know that not all of homotopy type theory is possible is Agda and Coq.

My question is: What parts of homotopy type theory are not possible in Agda or Coq?

If you look at Notes on Chapter 8 you will see what has already been formalized, and I think that's a lot. There are the Coq HoTT library and the Agda HoTT-Agda library which formalize large chunks of Homotopy Type Theory.

To get things done in Coq we needed a special version of Coq that was patched just for the purposes of HoTT. However, Coq is moving in the direction of supporting homotopy type theory, so before long we might be able to do it with standard Coq.

In Agda one has to turn on the --without-K option, otherwise Agda thinks all types are 0-types. There are some lingering doubts as to whether --without-K really gets rid of the assumption that everything is a 0-set, or perhaps one could reintroduce it into Agda with tricky uses of pattern matches.

The following aspects of Coq and Agda formalizations are not satisfactory:

The Univalence axiom is stated as a hypothesis. It would be better if it were built into the system. In particular we would like Coq and Agda to understand the computation rules about the Univalence axiom.
Likewise, we have to use hacks to get workable higher-inductive types. Again, it would be better to have direct support.

The trouble with the above deficiencies is that nobody knows how to fix them even in theory. This is an active area of research.

Other than that, I think it's fair to say that HoTT can be mostly done in Coq and Agda, just not in the optimal way.


Set optimization problem - is it np-complete? Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective function:
$$\sum_{e_i\in M} w_i + \frac{\sum_{e_i\notin M} w_i c_i}{\sum_{e_i\notin M} c_i}$$.

Is the problem NP-hard?

Since the objective function seems weird, it is helpful to explain an application of the objective function.

Suppose we have n items $e_1$ to $e_n$ and there are $c_i$ copies of each object $e_i$ in our inventory. We have some customers and they are interested in these objects in proportion with their weight $w_i$, which means the object with greater $w_i$ is more popular. We have an online sale system and we need to answer our customer's requests correctly. We cannot recognize objects by their shapes (They all look the same!). But we have some classifier to find them. Each classifier can be used for detecting copies of an object. We aim to run k classifier in order to maximize our customer's satisfaction.

P.S: It may be useful to think about the case that $w_i c_i=p$ for all $i\leq n$; however, I'm not sure.[I was wrong about this! It is in P by this assumption]

The answer below observes that a special case of the problem is solvable in polynomial time.  This does not fully answer the question in the post, but may give some insight on what might be needed for an NP-hardness proof, and may provoke additional interest in the post...

Observation. The problem in the post has an algorithm that, given any instance where each $c_i$ is an integer, runs in time polynomial in $n$ and $D = \sum_i c_i$.

Proof sketch.
Fix any input $(S, w, c, K)$ where $w,c\in\mathbb{R}_+^n$ and (WLOG)
$S=\{1,2,\ldots,n\}$.  Rephrasing the problem slightly, the goal is to find $M\subseteq S$ of size $K$ maximizing $\frac{\sum_{i\in M} w_i c_i}{\sum_{i\in M} c_i} - \sum_{i\in M} w_i$.

Consider the following dynamic program.
For any integers $(d_1, d_2, k, m)$ with $0\le d_1 \le d_2 \le D$, $0\le k \le K$, and $k\le m\le n$, define
$$\textstyle\phi(d_1, d_2, k, m)
= \max \Big\{ \sum_{i\in M} w_i (c_i / d_1 - 1) ~:~
M \subseteq [m],\, |M| = k, \, \sum_{i\in M} c_i = d_2\Big\}.$$
The desired solution is $\max_d \phi(d, d, K, n)$.

Partitioning the possible solutions for $\phi(d_1, d_2, k, m)$ into those that contain $m$ and those that don't, we get the recurrence
$$\textstyle\phi(d_1, d_2, k, m)
= \max\begin{cases}
\phi(d_1, d_2 - c_m, k-1,m-1) + w_m(c_m/d_1-1) \\
\phi(d_1, d_2, k, m-1).
\end{cases}$$
We leave the boundary cases as an exercise.

The number of subproblems is $O(n^2 D^2)$, and for each the right-hand side of the recurrence can be evaluated in constant time, so the algorithm runs in time polynomial in $n$ and $D$. $~~\Box$

Corollary. Unless P=NP, any reduction showing NP-hardness will reduce to instances where $D$ is not polynomial in $n$.

Remark. Unless I am mistaken, there is also a PTAS for the problem in the post, based on rounding the $w_i$'s then using dynamic programming. However, the existence of a PTAS has no direct bearing on whether the problem is NP-hard, as asked in the post.

I am also curious --- does anyone know whether the special case when $w_i=c_i$ (for each $i$) has a poly-time algorithm? (EDIT: it does, per Willard Zhan's comment this seems to be optimized by taking $M$ to contain the $k$ largest elements.)


Can this randomized greedy algorithm be made online? Or being proved impossible? I am going to edge color an undirected simple graph. The following randomized offline algorithm is showed at Online Algorithms for Edge Coloring.

Offline: The potential colors are ordered 1, 2, . . . , 2$\Delta$−1. The edges are ordered at random, and we greedily assign color 1 until a
maximal matching is colored 1, then we start over with a random order of the remaining uncolored edges and we greedily assign color 2 until a maximal matching of the remaining edges is colored 2, and so on with the remaining edges and maximal matchings for colors 3, 4, . . .

In paper Online Algorithms for Edge Coloring, the authors claimed the offline algorithm is the same as the online algorithm as follows.

Online: The edges are ordered at random only once, and each edge in turn is
colored with the least valid color out of 1, 2, . . . , 2$\Delta$ − 1.

The "same" means, for a given graph. If the first algorithm needs $c$ colors with probability $p$, then the second algorithm uses needs $c$ colors with probability $p$. So there is not clear justification that the given two algorithms are same.

The paper claims "For the second algorithm, if we consider sequentially when colors 1, 2, . . . are assigned, the same bound holds.".

In fact, they turn out to be different (see the examle below). So my question is: can the offline algorithm be made onlne? I cannot handle the multi-times random ordering ( after each maximal matching is removed, the order of the remaining edges is shuffled).

Example.

Let $E_r=\{e_0, e_1, e_2\}$, $X_i$ be the indicator random variable that whether color $i$ is assigned to one edge from $E_r$.  $X_i=1$ iff the i-th color is not assigned to the edges e_0, e_1, e_2. We calulate the expected number of colors from clolrs $\{1, 2\}$ which are not assinged to any of $\{e_0, e_1, e_2\}$.

For the "first algorithm":
$E[X_1+X_2] = Pr(X_1=1)+Pr(X_2=1) $
$=Pr(X_1=1)+Pr(X_2=1|X_1=1)\cdot Pr(X_1=1) + Pr(X_2=1|X_1=0)\cdot Pr(X_1=0)$
$=(\frac{2}{3})^3 + (\frac{1}{2})^3 \cdot (\frac{2}{3})^3 + (\frac{1}{2})^2 \cdot (1- (\frac{2}{3})^3 )$
$=\frac{1}{2}$

For the "second algorithm": We list all the $9!$ orderings, and get $E[X_1+X_2]=12/27=0.44444$.

The follwoing is responce for @vzn, thanks very much.

In fact, the paper was not published as far as I know. I have contacted the first author, he have not respond it in detail. The key is that, it does not "fit" clearly.
Why I only concern the first two colors in the example. If $x$ edges from $\{e_0, e_1, e_2\}$ are not assigned to colors in $\{1,2\}$, then the algorithms needs exactly $2+(3-x)=5-x$ colors. Because for the remaining $(3-x)$ edges incident to the root not colored, $(3-x)$ new colors have to be used. While the other edges will be colored in the third color definitely. Put another way, if the two algorithms were the same, all the characterizations of them should be the same? (For example, $E[X_1+X_2]$ here. Am I right? I am not sure.)

as far as I can tell after looking into this somewhat, there is a misunderstanding of the paper in the question. the question states that some of the algorithms are offline vs some online. but the algorithms in the paper are all online it appears (but agree the authors are not clear on this point). that is what is accomplished by having random edge orderings-- the random edge ordering reflects edges coming "online" in whatever order, right?

the authors seem to make no reference to "offline" algorithms in the paper and they refer to "online" only in the introduction that I see. they dont state this but the 1st algorithm seems to allow edges to come "online" in "batches" (ie random reordering in stages) whereas the 2nd algorithm does not.

while you dont state it exactly you appear to be checking the math in proof for theorem 2.3 in the paper (p3) which establishes a lower bound on the number of colors in a tree and the authors assert it works for both algorithm 1 and 2 ("for the 2nd algorithm.. the same bound holds"). the proof is that no less than $1.23\Delta$ colors ($\Delta$=graph degree) are sufficient for all trees. it seems if this theorem is wrong as you are suggesting then one should be able to exhibit a tree that can be colored with fewer than $1.23\Delta$ colors using those algorithms. from what I can tell your math is off because you are not expressing it using the same formulas in the proof eg you do not calculate the exponential formula in the proof.

a way to empirically verify this lower bound would be to generate many random trees, or some sample from some distribution, run the two algorithms and verify that they always use at least $1.23\Delta$ colors.


Lower bound for enumerating k closest pair of points Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ pairs of points in increasing order of distance.

The trivial algorithm takes $O(n^2 \log n)$ time but we can do better if we are allowed to build a data structure in a pre-processing phase. It is easy to see that one can build a data structure that takes $O(n \log n)$ time and $O(n \log n)$ space in the following way - we simply sort all of the input points and store the closest candidate for each point in a heap. Then, with $O(\log n)$ delay, I can get an output element. For the point which was popped from the heap, we can add the next closest point using binary search over the input and inserting into the heap (both operations take $O(\log n)$ time). Although this method is better, it still takes $O(n^2 \log n)$ time in total.

Question 1 - My question is whether there is a known lower bound that total enumeration cannot be done in $o(n^2 \log n)$ time. This was listed as an open problem here. I am looking for references that prove a lower bound or a more recent paper that confirms this is still an open problem.

Question 2 - What happens if I replace distance function to $d(x_i, x_j) = x_i + x_j$? Does this make the problem easier and admit $o(n^2 \log n)$ time algorithm?

This is only a partial answer.

I think it is not complex to show that if question 1 can be done in $o(n^2 \log n)$, then so can be question 2. So according to the comment by Willard Zhan in the OP's question, your first question should be open as well.

A reduction could be as follows:

Assume your input to question 2 is $\{x_i\}_{1 \leq i \leq n}$. Then construct an input for question 1 as follows:

$\{T + x_i\}_{1 \leq i \leq n} \cup \{- x_i\}_{1 \leq i \leq n}$ for a sufficiently large constant T.

Then the answer to question 1 with these $2n$ points could be easily translated to an answer to question 2, as pairs of the form $(T + x_i, -x_j)$ in the answer to question 1 are easily differentiated from the rest, and correspond directly to the answer of question 2, taking into account that:

$|(T + x_i) - (- x_j) | = |T + x_i + x_j | = T + x_i + x_j > T / 2$
$|(T + x_i) - (T + x_j) | = |x_i - x_j | < T / 2$
$|-x_i - (-x_j) | = |- x_i + x_j | < T / 2$


Can we partition NP-complete problem into finite number of polynomially solvable problems? Let $\Pi$ be NP-complete problem.
Can we partition set of instances of $\Pi$ into finite number of subsets (subproblems) each of which is polynomially solvable (and not necessarily polynomially recognizable)?
For example, $\Pi$ is NP-complete for graphs with maximal degree $\Delta=3$, but polynomially solvable for cubic and graphs with $\Delta=2$?

I have obtained two answers on my question: "trivially yes" (by Peter Shor and mikero) and no, unless $P=NP$ (by Sadeq Dousti and Antonio E. Porreca). I'm curious why such easy question gets such contradicting answers (not taking into account the reason that I have formulated it ambiguously). So the question is:
how to formulate two questions such that for each of them corresponding answers would hold.

The last edition of this question has been answered in full by Peter Shor on Math.SE here.
Here is the answer:

"There are two different possible questions here. When you ask for the solution of an NP-complete problem, you can either (a) require the computer to give you a witness in the "yes" cases or (b) just require the computer to give you the answer."

If you partition the input into sets of instances, each of which has the same solution, then each of these sets of instances is indeed polynomial-time solvable. I'm sure this isn't what you're looking for, but I don't see how to naturally exclude it from your question.


What is the worst case of the randomized incremental delaunay triangulation algorithm? I know that the expected worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in Computational Geometry) is $\mathcal O(n \log n)$.
There is an exercise which implies the worst-case runtime is $\Omega(n^2)$.
I've tried to construct an example where this actually is the case but haven't been successful so far.

One of those tries was to arrange and order the point set in a manner such that, when adding a point $p_r$ in step $r$, about $r-1$ edges are created.

Another approach might involve the point-location structure:
Try to arrange the points such that the path taken in the point-location structure for locating a point $p_r$ in step $r$ is as long as possible.

Still, I'm unsure which of these two approaches is correct (if at all) and would be glad for some hints.

The first approach can be formalized as follows.

Let $P$ be an arbitrary set of $n$ points on the positive branch of the parabola $y=x^2$; that is,
$$
P = \{ (t_1, t_1^2), (t_2, t_2^2), \dots, (t_n, t_n^2) \}
$$
for some positive real numbers $t_1, t_2, \dots, t_n$.  Without loss of generality, assume these points are indexed in increasing order: $0 < t_1 < t_2 < \cdots < t_n$.

Claim: In the Delaunay triangulation of $P$, the leftmost point $(t_1, t_1^2)$ is a neighbor of every other point in $P$.

This claim implies that adding a new point $(t_0, t_0^2)$ to $P$ with $0 < t_0 < t_1$ adds $n$ new edges to the Delaunay triangulation.  Thus, inductively, if we incrementally contract the Delaunay triangulation of $P$ by inserting the points in right-to-left order, the total number of Delaunay edges created is $\Omega(n^2)$.

We can prove the claim as follows.  For any real values $0<a<b<c$, let $C(a,b,c)$ denote the unique circle through the points $(a,a^2), (b,b^2), (c,c^2)$.

Lemma: $C(a,b,c)$ does not contain any point $(t,t^2)$ where $a<t<b$ or $c<t$.

Proof: Recall that four points $(a,b), (c,d), (e,f), (g,h)$ are cocircular if and only if
$$
\begin{vmatrix}
1 & a & b & a^2 + b^2 \\
1 & c & d & c^2 + d^2 \\
1 & e & f & e^2 + f^2 \\
1 & g & h & g^2 + h^2 \\
\end{vmatrix}
=
0
$$
Thus, a point $(t,t^2)$ lies on the circle $C(a,b,c)$ if and only if
$$
\begin{vmatrix}
1 & a & a^2 & a^2 + a^4 \\
1 & b & b^2 & b^2 + b^4 \\
1 & c & c^2 & c^2 + c^4 \\
1 & t & t^2 & t^2 + t^4 \\
\end{vmatrix}
=
0
$$
It's not hard (for example, ask Wolfram Alpha) to expand and factor the $4\times4$ determinant into the following form:
$$
(a-b)(a-c)(b-c)(a-t)(b-t)(c-t)(a+b+c+t) = 0
\tag{$*$}
$$
Thus, $(t,t^2)$ lies on $C(a,b,c)$ if and only if $t=a$, $t=b$, $t=c$, or $t=-a-b-c < 0$.  Moreover, because $0<a<b<c$, these four roots are distinct, which implies that the parabola actually crosses $C(a,b,c)$ at those four points.  It follows that $(t,t^2)$ lies inside $C(a,b,c)$ if and only if $-a-b-c<t<a$ or $b<t<c$.$\qquad\Box$


Applications of $p$-adic numbers in CS Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?

De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper Fast integer multiplication using modular arithmetic, in which the p-adic numbers replace the complex numbers used by Fürer. Both algorithms give the best bit-complexity for integer multiplication.


(Self-)citation etiquette This is particularly pertinent to the CS culture, where competitive conferences are often the main publication unit, which are then (sometimes) followed by journal versions.

Suppose that a paper was published at a conference as version A, and say, 5 years later, in a journal as version B (with the same title and authors). Assume also that during those 5 years, additional relevant papers on the topic were published.

When doing literature review in the introduction of future papers, the author of A and B is faced with a dilemma. To accurately reflect the historical development, he wants to cite version A and then the papers that followed it. However, the paper he actually wants people to read and cite is version B -- since it's cleaner, expanded, improved, etc. He can cite both versions, but then it looks like he's trying to rack up citations.

Does the CS community have a set etiquette for dealing with this situation? Is there perhaps a bibtex format where a single bib-entry covers both versions? Something that conveys the point "published first in year Y at venue V [so precedence is established] and then expanded version appeared in year Y' at venue V' [so just go read that one]"?

Usually I just cite the journal version. But (if the history is important) I would add a note to the same citation about earlier conferences or preprints.

I think this style is preferable to making one paper look like two citations, except possibly in cases where the conference and journal papers have other significant differences than completeness (such as changes to the author list or claimed results). It is also unrelated to whether the citation is to my own paper or someone else's.

For harvard-style Name (year) citations, it might also make sense to mention the earlier version in-text as Name (year, announced earlier-year), as well as putting the information in the actual reference.

[Converted from a comment to an answer at the suggestion of Kaveh]


Approximation Algorithms for MAXSAT Trying to find the optimal solution to WEIGHTED-MAX-3SAT, the weighted version of the 3-SAT optimization problem, is NP-hard. In fact, even approximating the non-weighted version of MAX-SAT arbitrarily well is provably NP-hard by the PCP Theorem.

A canonical algorithm for approximating WEIGHTED-MAX-3SAT is MAX-WalkSAT. Looking around I found some information on other algorithms (i.e. branch-and-bound, the DPL algorithm) which are commonly used to find solutions to 3-SAT or (unweighted) MAX-3SAT, but I didn't see any discussion of how well these would work for the weighted version. Intuitively, without being adapted they would not work as well.

I'm wondering what other algorithms are commonly used to approximate WEIGHTED-MAX-SAT, if there are well-known WEIGHTED-MAX-SAT solvers, and the relative quality of these algorithms/solvers.

Well, this can be formulated as the problem of finding the ground state of an Ising-like Hamiltonian with 3-local terms. These don't occur naturally, but you would expect them to cool similarly to other systems, so simulated annealing should work just fine for the weighted version.


Efficient graph isomorphism for similar graph queries Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one node from G2, and we have the result of F(G1,G2), can we compute F(G1,G3) without computing it from scratch by extending any existing state-of-the-art methods?

For example, if G2 is formed by nodes 2,3,4,5 and G3 is formed by nodes 3,4,5,6, can we make use of the result of F(G1,G2) to compute F(G1,G3) more efficiently?

This is a simple polynomial time reduction to show that the problem is GI complete: even if you know that $G_1, G_2$ are isomorphic, checking if $G_3$, built from $G_2$ deleting and adding a node, is isomorphic to $G_1$ is as hard as graph isomorphism itself (in the worst case).

Given two graphs $G = (V, E), G'= (V', E')$ build

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

i.e. the union of the two graphs plus an extra node $u$ connected to all the vertices of $V$

pick $G_2 = G_1$; and clearly they are isomorphic.

Now build $G_3$ deleting $u$ and adding $u'$ connected to all the vertices of $V'$:

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ are isomorphic iff $G, G'$ are isomorphic.


What does $\#P\subseteq FP^{PPAD}$ imply? We know $\#P\subseteq {PPAD}\implies PH\subseteq P^{{PPAD}}\subseteq P^{{NP}}$ and the polynomial hierarchy collapses ($FP^{PPAD}=PPAD$ following Emil Jerabek's comment).

Can $\#P\subseteq {PPAD}$ give a stronger collapse such as $\oplus P=UP=NP=coNP=PP$ or $NP=coNP=P^{PPAD}$?

What other consequences follow in $\#P\subseteq {PPAD}$ holds?

First, $\mathrm{PPAD\subseteq FP^{NP}}$, hence $\mathrm{\#P^{PPAD}\subseteq\#P^{NP}\subseteq FP^{\#P}}$. Moreover, $\mathrm{PPAD}$ is closed under Turing reductions, i.e., $\mathrm{FP^{PPAD}\subseteq PPAD}$. Thus, if we assume
$$\mathrm{\#P\subseteq PPAD},$$
then
$$\mathrm{\#P^{PPAD}\subseteq PPAD},$$
which by induction implies
$$\mathrm{FCH=PPAD}.$$
Passing to decision problems, since $\mathrm{P^{PPAD}\subseteq P^{TFNP}\subseteq NP\cap coNP}$, this shows
$$\mathrm{\#P\subseteq PPAD}\implies\mathrm{CH=P^{PPAD}=NP=coNP}.$$
(Note that using the closure of $\mathrm{PPAD}$ under Turing reductions, $\mathrm{P^{PPAD}}$ consists of predicates whose characteristic functions can be computed as projections of $\mathrm{PPAD}$ problems.)

As for $\oplus\mathrm P$, I believe $\mathrm{PPA\supseteq PPAD}$ can be solved by binary search on the predicate “the sum of degrees of vertices whose labels start with a given string is odd”, which means
$$\mathrm{PPAD\subseteq FP^{\oplus P}},$$
thus (using $\mathrm{P^{\oplus P}=\oplus P}$)
$$\mathrm{\#P\subseteq PPAD}\implies\mathrm{CH=P^{PPAD}=NP=coNP=\oplus P}.$$
A similar argument applies with $\mathrm{Mod}_p\mathrm P$ in place of $\oplus\mathrm P$ for any prime $p$.

I don’t know about UP.


Maximum common subgraph of two planar graphs of bounded degree k Given two planar graphs of bounded degree (i.e. each node has no more than D edges), I'd like to find their maximum common subgraph. I know that the more general problem applied to maximal planar graphs is NP-complete w.r.t to the number of vertices per David Eppstein[1].

However, the MCS of partial k-Trees of Bounded degree, (including outerplanar graphs, etc.), can be evaluated in polynomial time [2].

Is there a result for something in-between? Practical answers are also welcome.

[1] Largest common subgraph of two maximal planar graphs

[2] http://link.springer.com/chapter/10.1007%2F978-3-642-32589-2_10#page-1

Maybe I misunderstood the question, but it seems it's NPC and this is trivial. Finding hamiltonian cycle in planar graphs of max degree $3$ is NPC. Therefore this problem is also NPC (input: A planar graph of max degree $3$ on $n$ vertices and a cycle on $n$ vertex.


Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings We say that a pair $(P,N)$ of subsets of strings from $\{0,1\}^n$ is an $n$-pair if $|P|=|N|=n$. Intuitively, sucha a pair consists of a set $P$ with $n$ positive $n$-bit strings, and a set $N$ with $n$ negative $n$-bit strings. We say that a circuit $C$ separates $(P,N)$ if $C$ accepts all strings in $P$ and rejects all strings in $N$.
I'm looking for any non-trivial lower bound for the size of circuits/formulas separating $n$-pairs.

Question: Is it the case that every $n$-pair $(P,N)$ can be separated by a circuit/formula with $O(n)$ gates?

Note that each such pair can be trivially separated by a circuit/formula with $O(n^2)$ gates: given an input $w\in \{0,1\}^n$, the circuit/formula simply runs through each string $u$ in $P$ and tests whether $w$ is equal to $u$. It accepts if and only if it finds a $u$ that is equal to $w$.
On the other hand, I could not find an argument that implies that a super-linear number of gates is necessary.
Since this type of question seems to be well studied in by the machine learning community I was wondering if anyone could point me to some reference about lower bounds for separation problems as above?

Yes, any such pair can be separated by a formula of size $O(n)$. More generally, any disjoint pair $P,N\subseteq\{0,1\}^n$ of size $s=|P|+|N|$ can be separated by a decision tree of size $O(s)$, which can be implemented as an $O(s)$-size formula by replacing each query node with $(p\land\cdots)\lor(\neg p\land\cdots)$.
It suffices to observe that there exists a decision tree such that every path to a leaf is consistent with exactly one element of $P\cup N$ (which means that it has $s$ leaves and $s-1$ inner nodes). One way to show this is to consider the full binary tree of height $n$ that queries all variables along every path, take its subtree consisting of the union of paths to leaves in $P\cup N$, and eliminate inner nodes that do not branch.
Another way is to build it inductively. Start with the trivial one-element decision tree, and repeat: pick a leaf $x$ that is consistent with $\ge2$ elements of $P\cup N$, and make $x$ into a query node for some variable $p$ such that each of the $p$ and $\neg p$ branches is still consistent with an element of $P\cup N$. Notice that this actually gives a polynomial-time algorithm to construct the decision tree, given $P$ and $N$.
[The first version of this answer presented a different construction, using a linear hash function $h\colon\mathbb F_2^n\to\mathbb F_2^{O(\log s)}$ such that $h(P)\cap h(N)=\varnothing$. This only gives a separating circuit of size $O(n\log n)$, or $O((n+s_0)\log s)$ in the general case, where $s_0=\min\{|P|,|N|\}$.]
For $s\le n$, the $O(s)$ bound is optimal up to a multiplicative constant: it is easy to see that any circuit separating $P=\{0^n\}$ from $N=\{0^i10^{n-1-i}:i<s-1\}$ must
include all of the first $s-1$ variables, and as such it has size at least $s$.
For larger $s$, an optimal bound is given by Theorem 1.1 of Andreev, Clementi, and Rolim [1] (with $\varepsilon=1/2$): the maximum circuit size required to separate $P,N\subseteq\{0,1\}^n$ with $|P|+|N|=s$ is
$$\Theta\left(\frac s{\log s}\right)+O(n).$$
They do not seem to particularly care about the case of small $s$, but combined with the discussion above, we obtain the following complete characterization:

Theorem: The maximum circuit size required to separate disjoint pairs $P,N\subseteq\{0,1\}^n$ with $|P|+|N|=s$ is
$$\begin{cases}\Theta\left(\frac s{\log s}\right)&\text{if }n\log n\le s,\\
\Theta(n)&\text{if }n\le s\le n\log n,\\
\Theta(s)&\text{if }s\le n.\end{cases}$$

And while it does not yield improvement on any of the above, let me mention the following fun fact: for every nonempty $X\subseteq\{0,1\}^n$ of size $s=|X|$, there exists $I\subseteq[n]$ of size $|I|<s$ such that the restrictions $x\restriction I\in\{0,1\}^I$ of the elements $x\in X$ are pairwise distinct. To see this, fix $I$ of minimal size with this separation property. For each $i\in I$, the minimality of $I$ implies that there exist $x_i,y_i\in X$ such that $x_i\restriction I$ and $y_i\restriction I$ differ only at the $i$-th position. Put $E=\{\{x_i,y_i\}:i\in I\}$. Then $(X,E)$ is a graph with $s$ vertices and $|I|$ edges, and it is acyclic (if we start from a $\{0,1\}$ vector, and flip a sequence of distinct bits, we cannot arrive where we started from). Thus, $s>|I|$.
Reference:
[1] Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim: Optimal bounds for the approximation of boolean functions and some applications, Theoretical Computer Science 180 (1997), no. 1–2, pp. 243–268, doi: 10.1016/S0304-3975(96)00217-4.


Can Scheme's call/cc implement all known control flow structures? The page "Advanced Scheme: Some Naughty Bits" states:

  Continuations are a powerful control-flow construct from which
  nearly any other control-flow structure [...] may be derived.

I thought that Scheme's call/cc, being related (*) to Peter Landin's J operator, could be used to implement any known control flow structure?

With "control flow structure" I'm specifically thinking about Wikipedia's description of them, e.g. exceptions, coroutines, green threads and so on.

Specifically, are there any examples of control flow structures that cannot be implemented using call/cc?

(*) I haven't been able to dig up any paper that establishes that call/cc is as powerful as the J operator.  A paper by Felleisen (which I haven't read and admittedly have problems understanding it fully) investigates this, and seems to conclude that even though they are in different complexity classes, they are formally equivalent.

(Also note that I have updated the question based on the comments below)

Update

Based on the excellent answer by @Neel below, I've looked at sites commenting on delimited and undelimited continuations, and it does indeed seem that while call/cc, being undelimited, is not sufficient. Meanwhile, first-class, delimited continuations (like shift/reset) can be used, it seems, to express any control-flow structure.

In this answer, I'll take "expressible" to mean "macro-expressible" in the sense of Felleisen 1991, On The Expressive Power of Programming Languages. (Intuitively, a language feature is macro-expressible if you can define it as a local source transformation, without using a whole-program transformation.)

With this definition, the answer is no: delimited control is not macro-expressible in the lambda-calculus + call/cc. To express delimited control operators using call/cc. In order to implement the control delimiters (the reset part of shift/reset), you need some state to simulate the continuation marks, essentially to encode a stack to simulate the dynamic lifetimes of the continuation marks.

However, delimited control is a universal effect, in the following sense. In his PhD thesis, Andrzej Filinski showed that any expressible side effect is encodable using either delimited continuations, or call/cc and a single cell of state. Roughly, an "expressible side effect" is any effect whose monadic type can be defined in terms of the types of the programming language.

Surprisingly, this idea seems quite interesting in practice. Over the last decade, Gordon Plotkin and John Power have advocated the idea of taking an algebraic semantics of effects theories: the idea is that you specify the side-effecting operations you are interested in, and the equations you expect them to satisfy, and then you can generically get a semantics by taking the free monad over this theory.

Matija Pretnar and Andrej Bauer took this mathematical approach, and then implemented it in their Eff language to invent a new language construct dubbed "effect handlers": you can write code that uses a set of imperative features, and then give the imperative features a semantics by writing a set of handlers which say how to implement each effectful operation.


Maximum Independent Set using Maximal MIS I want to use multiple runs of maximal independent set (Luby's algorithm) to find a lower bound on the size of maximum independent set.

Are there any bounds on the number of times the maximal algorithm has to be run to find the true maximum with a high probability ?

The graphs don't possess any special properties.

If the graph is a clique (or a set of disconnected cliques), then Luby's algorithm succeeds on the first iteration.


Unique Shapes of Binary Search Trees Say you have a set of numbers {1,2,3,4,5,6,7,8,9,10} of which you have all different permutations.

You place each permutation into a BST and then compare all the shapes of the BSTs.  How many different (unique) shapes are there for trees of height 6 for example?

The question does not need to be answered directly, instead maybe an algorithm to help determine the shape instead and compare.

While Per Vognsen's comment works well for labeled trees, your question uses the word "unique" (which should probably be "distinct") to describe the shape of the tree.  This makes me think you mean "How many isomorphism classes of unlabeled binary trees are there?"

To compute this exactly, you will probably want to use Brendan McKay's "Isomorph-free exhaustive generation" which he uses in his program geng to list each isomorphism class of simple graphs on a given number of vertices and edges, and do it quickly.

To summarize his process, he uses a depth-first search on graphs, where each deepening step adds a vertex.  To make sure no isomorphism class is repeated (which would happen a lot if this was done naïvely) the vertex-added graph decides if this was the "canonical" subgraph to use in the search.  The algorithm essentially picks a vertex in the graph to be deleted using a canonical labeling of the graph and tests if this was the vertex that was added.  A canonical labeling can be found by McKay's nauty library.

In your binary tree example, you would add a leaf somewhere in the tree.  You can fix the root, but the other vertices may permute based on the automorphism group.  Hence, you only need to test adding a leaf to each orbit of vertices that has fewer than two children.  After adding the leaf, compute the canonical labeling of the tree and find the lexicographically-least leaf.  If this leaf is in the same orbit as the leaf you added, then the search can deepen; otherwise try a new leaf.  When $n$ vertices are reached, increment your counter.


The number of triangulations of a set of $n$ planar points: Why so difficult? After hearing Emo Welzl speak on the subject this summer, I know the number of
of triangulations of a set of $n$ points in the plane is somewhere between
about $\Omega(8.48^n)$ and $O(30^n)$. Apologies if I am out-of-date; updates welcomed.

I mentioned this in class, and wanted to follow up with brief, sage remarks to give
students a sense for (a) why it has proved so difficult to nail down this quantity,
and (b) why so many care to nail it down.  I found I did not have adequate answers
to illuminate either issue; so much for my sageness!

I'd appreciate your take on these admittedly vague questions.  Thanks!

Here's one more "applied" reason why we care about triangulations. There's a body of work on mesh compression where the goal is to use as few bits per vertex as possible to encode a mesh (mainly to aid in storage and transmission). The particular base of the exponent in the number of triangulations of a planar point set provides an information-theoretic lower bound on the number of bits needed per vertex (specifically, $8.48^n$ triangulations means you need at least 8.48 bits per vertex). Such bounds can then be compared with actual mesh compression schemes to determine their efficacy.


History of recursion Who introduced the idea of recursion?
Can someone explain where it came from and how it impacted computer science?

Computability and Recursion, by Soare.
http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

This paper is the first of the history of computation papers available here:
http://www.people.cs.uchicago.edu/~soare/History/


CFG parsing using $o(n^2)$ space There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.

However, all algorithms for parsing arbitrary CFGs I know have a worst-case space usage of $\Omega(n^2)$ (although, admittedly, I have no idea what the space usage of that matrix multiplication algorithm is). I was wondering whether there are any algorithms that improve upon this space usage (so disregarding the time bound).

The question popped up into my mind after mentally linking $CSG = NDSPACE(n) \subseteq DSPACE(n^2)$ with the $\Omega(n^2)$ space bound on all the CFG parsing algorithms I knew. It's probably of no practical interest, but merely something I'd be interested in knowing.

The first half of this answer is nothing more than an efficient ($\log^4(n)$ to $\log^2(n)$) rephrasing of David's answer in complexity theoretic terms.

Context free languages live in the complexity class $LOGCFL.$ This class is equivalently characterized by log depth semi-unbounded circuits. These are polynomial sized circuits wherein OR gates have unbounded fan-in and AND gates have bounded fan-in (say 2). By increasing depth by a log factor, we can replace every unbounded fan-in OR gate with bounded fan-in ORs. This put the problem in $NC^2.$ It is not difficult to see how $NC^2$ can be evaluated by a $DSPACE(\log^2(n))$ by say a depth first search that maintains the left/right sequence of children at the gates explored thus far. The result goes back to the Lewis-Hartmanis paper. And while this improves David's space bound,  this can take $n^{\log n}$ time. We do not know any better.

The traditional way to understand time space tradeoff is to use pebble games. There have been a few papers on CYK; a more recent attempt is in the first part of this presentation. Here it is shown that (a) linear space can be achieved at exponential time and (b) if time is restricted to $O(n^2)$, then CYK would use at least $n^2$ space.

Certainly a very interesting problem worthy of a look.


To what extent is it possible to use genetic algorithms to make wind mill turbine blades more efficient? I recently watched  this video on youtube. It featured someone explaining how he used genetic algorithms to improve the efficiency of wind mill turbines by finding the optimal shape for the blades. Eventually, the narrator found a non-trivial shape for the blades that seemed to be more efficient than windmills that have blades with a "standard" shape.

He did, however, use the wrong viscosity for the substance in which the wind mills are situated. Therefore the preliminary questions are:

Would the shape of the new blades be the same if the same procedure would be carried out in a substance with the correct viscosity? Would the blades still be more efficient than the "standard" blades?

Now to the real question(s). The narrator in the video carries out this genetic algorithm procedure with two-dimensional wind turbine blades.

I was wondering, though, if a similar procedure could also be carried out in a tree-dimensional environment? I guess it would be more complicated, and perhaps would require more computing power/time, but if it can be used to enhance the efficiency of wind turbine blades, it would be a good idea to do so, right? Has this already been done? Why or why not?

Last question:

if the genetic algorithm would indeed create novel, more efficient wind turbine blades, would that mean that some company would actually pick up on the idea and start producing them? Or would the novel shape be too complicated and therefore too expensive to produce, rendering the design useless from a financial perspective?

Thanks a lot in advance!

Short answer, yes you could build a GA that worked on a 3D model of a turbine with the correct viscosity, and (probably) yes, it would still find good designs. Exactly what those designs would be is somewhat unpredictable -- they might be very conventional blade arrangements or they might be completely novel and weird.

However, that's also true of many other search algorithms. GAs are, at heart, just one of a class of hundreds of stochastic search algorithms. All you need for a GA to work is three things: (1) a way of describing what a possible solution looks like, (2) a way of trying to combine good solutions to get more good solutions, and (3) a way of determining when one solution is better than another. The former can be as simple as just a vector of numbers ([number of blades, distance between blades, angle of attack, ...]) or may be arbitrarily complex, allowing for each blade to have an independent length and position, etc. For number three, you need a model that tells you how good a turbine is. This is where you need to get the viscosity of air correct, embed the right equations governing the electrical outputs, etc.

That just leaves the genetic operators -- how do you take good designs and produce more or better ones? Again, this can be very complex, but it can also be quite simple. For instance, you have a design with three blades, each five meters long. OK, make a small random change to that. Try blades that are 5.2 meters long. If the model tells you this is better, keep it. If not, throw it away and keep the original five meter blades. It's in this stage where domain knowledge is often invaluable. Having someone who can say, "the number of blades is really important -- taking a good five blade design and removing a blade isn't going to work unless you also change lots of other aspects of the design" allows you to simply say, "OK, my algorithm will avoid making that type of change in favor of making changes that are more likely to help.

Like I said, GAs are just search algorithms. They tend to often perform a "broader" search, which can sometimes make them more likely to find these off-the-wall solutions than some other methods. On the flip side, they typically take much longer to find good solutions than some other methods. That's also an approximation; sometimes a GA works great, sometimes it works very poorly. Understanding which cases will be which is one of the great unsolved problems for people working in optimization.

Finally, would companies adopt them if better designs were found? As you say, that's a more complex question. It isn't even just a matter of "too complicated". Suppose you find a 5% better turbine design that's completely feasible. You'll still likely have to redesign manufacturing equipment and processes, perhaps find new suppliers, etc. In the real world, "good enough" is often just that. However, there are numerous examples of real-world problems where methods like GAs or other random search methods have found solutions that were adopted. A lot of them are tucked behind corporate walls, but there have been notable successes in things like antenna design and aircraft design, as well as non engineering optimization problems like vehicle routing problems, scheduling problems, etc.


Lower bound of real valued bounded function Is well known that the lower bound on number of example necessary to reach a given error for concept classes $\Omega(d/\varepsilon)$ (cf. also
Agnostic PAC sampling lower bound
)
I am looking for the lower bound of example necessary to define a real value bound function as PAC learnable, given a VC dimension, bound and precision.
I have found in this '92 paper by Haussler some bounds for finite and infinite sets some bounds. E.g. for a finite set of $|F|$ bounded function $0 \leq f \leq M$, theorem 1 states that
$$ m \geq \frac{M^2}{2\epsilon^2} \left( \textrm{ln}|F| + \frac{2}{\delta}\right),$$
with probability $\delta$. Where $m$ is the number of training examples needed, and $\epsilon$ is defined as the "regret", that is the difference between the optimal and empirical risks.
I was wondering:

if there is a result regarding the optimal risk as well and evaluate the total risk, like for the concept classes bounds
if there are new results regarding these bounds for real-valued functions.

You have to specify a loss -- say, $\ell_1$ for simplicity, so the risk of a hypothesis $h$ is $E|h(X)-Y|$. Then at the very least, by reduction to the VC case, to achieve accuracy $\epsilon$ you will need at least
$$\Omega(d_F(\epsilon)/\epsilon^2)
\qquad (*)$$
examples, where $d_F(\epsilon)$ is the fat-shattering dimension of the class $F$ at scale $\epsilon$. Just take an $\epsilon$-shattered set of size $d_F(\epsilon)$ and put uniform point masses on the $x$'s, while setting the $y$'s to be $\pm\epsilon$ with appropriate probabilities (just as in the binary case -- which is carefully worked out in these notes:
https://www.cs.bgu.ac.il/~asml162/wiki.files/agnostic-pac-lb.pdf
).

I don't know if this is the tightest bound possible; the best upper bound I know, given here,
https://www.sciencedirect.com/science/article/pii/S0022000097915579
behaves as
$$ O(\Omega(d_F(\epsilon/5)\log(1/\epsilon)/\epsilon^3.$$

Update.
The lower bound $(*)$ is for excess risk -- i.e., in the agnostic PAC setting. The realizable PAC lower bound can be straightforwardly be adapted to give a lower bound of $\Omega(d_F(\epsilon)/\epsilon)$ for the absolute risk.


Planar separator theorem and tree decomposition The Wikipedia article about the Planar Separator Theorem states that it is possible to use a hierarchy of separators to construct a tree decomposition for a planar graph and moreover provides an $\mathcal{O}(\sqrt{n})$ upper bound for the tree width of an $n$ vertex planar graph.

I have difficulties in understanding the hierarchy and moreover in checking that the resulting binary tree is a tree decomposition.

I would really appreciate if you could help me or point to a reference that elaborates on it.

As far as i know the simplest (in my opinion) self contained proof of the planar separator theorem is unpublished; it is a combination of the following (somewhat non-trivial) theorem with the "Baker layering" trick.

The treewidth of a planar graph of diameter d is <= 3d-1
[H. L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth.
Theor. Comput. Sci., 209(1-2):1–45, 1998, Theorem 83]

Now to the "Baker layering" trick: do a BFS from an arbitrary vertex and number the layers
1,2....sqrt(n), 1, 2, ... sqrt(n) .. etc
Now there exists an i such that the total number of vertices living in layers labelled i is at most sqrt(n). Let the set of these vertices be S. Consider any connected component of G-S. Such a component must live in at most sqrt(n) consecutive layers, and thus it has diameter <= 2sqrt(n). Since planar graphs of diameter sqrt(n) have treewidth at most 3sqrt(n) we have that G-S has treewidth <= 6sqrt(n) and so G has treewidth <= 7sqrt(n). Tada.

There is a small silly bug in the proof above; the fact that a connected component of G\S lives inside sqrt(n) layers does not mean that the diameter is actually at most sqrt(n) ... but thus is easily fixed by contracting the layers up until the layer of this component into a single vertex. Then diameter of (a supergraph of the component) is at most 2sqrt(n), and we are done.


Generalization of independent set I know the definition of the independent set problem in graph theory.  An independent set cannot contain any two adjacent vertices.

How about if you allow no more than $k$ pairs of adjacent vertices?  Does this more general problem have a name?  Are there techniques for solving it?  In particular, are there any techniques for solving it with linear programming?

Not exactly what you're looking for, but Dinur and Safra, in their celebrated paper on the hardness of vertex cover, prove that the following promise problem is NP-hard for every fixed $r,\epsilon > 0$ (using the PCP theorem and Raz's parallel repetition theorem).

Instance: A graph $G$ whose vertex set is composed of $m$ sets $V_1,\ldots,V_m$ of size $r$, each of them forming an $r$-clique.

Problem: Distinguish between the following two cases:

YES case: $G$ has an independent set of size $m$.
NO case: Every set $A \subseteq V$ containing more than $\epsilon m$ vertices contains a clique of size $h = \lfloor \epsilon r^{1/c} \rfloor$ (where $c$ is some universal constant).

More explicitly, for any NP language $L$ there is a polytime $f$ mapping instances of $L$ to instances of this promise problem, in such a way that if $x \in L$ then $f(x)$ is a YES instance, and if $x \notin L$ then $f(x)$ is a NO instance.


Preferable way to express $O(n2^n)$ Is it preferable to write $O(n2^n)$ or $O((2 + \epsilon)^n)$? If neither, what is the best way? Since I see a lot of papers with $O(1.42^n)$ instead of $O(2^{\frac{n}{2}})$ and similar transformations, I was wondering what people prefer.

If you have an exact and simple formula like $O(n2^n)$ I would go with that. It is more precise than $O((2+\epsilon)^n)$ because it tells you what the epsilon really is. For the same reason I would generally prefer $O(2^{n/2})$ (but with a slashed fraction not a vertical one in the exponent) to $O(1.42^n)$, although in some cases you might want to give the numerical value (or both forms) to show more clearly how a bound compares to previous bounds for the same problem.

If the formula is more complicated ($c^n$ where $c$ is the largest real root of a higher-degree polynomial, say) it can be helpful to replace $c$ by a numeric value. In this case $c$ should always be rounded up, not down, and lower-order terms like the factor of $n$ in the first formula should be omitted (because they are covered by the rounding of $c$).


What algorithms do you know for beltway reconstruction? I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of non-identical integers between 0 and N, we only have pairwise distances of points of that set mod N, How can we reconstruct the original set using this?

Paul Lemke Steven S. Skiena Warren D. Smith, Reconstructing Sets From Interpoint Distances, gave backtracking algorithm that runs in time $O(n^n \log n)$ for the beltway reconstruction problem. As far as I know, this is the best known. The exact complexity of the problem is not known. It is not known to be in $P$ and neither known to be $NP$-complete.


Looking for papers and articles on higher-order sequent systems I am looking for work on systems that are similar to K. Dosen's higher-order sequents ("Sequent Systems for Modal Logic", JSL 50).  The only work that I am aware of is recent work by Iemhoff and Metcalfe ("Proof theory for admissible rules", Annals of Pure and Applied Logic 159 (1-2), 2009).

Are there other papers on such systems?

Again I'm not exactly sure what you are looking for because there are potentially many "similar" systems, but for recent work that I think is very related you can read Part II ("Mixing Derivability and Admissibility") of Dan Licata's thesis, as well as Constructive provability logic by Rob Simmons and Bernardo Toninho.


Closure ordinals for inductive types with function spaces Functors built from finite products and sums have closure ordinal $\omega$, detailed nicely in
this manuscript by Francois Metayer. i.e. we can reach the inductive type $nat := \mu X. 1 + X$ by iterating the functor $1 + X$, which reaches its fixed point after $\omega$ iterations.

But once we allow constant exponentiation, such as in $\mu X. 1 + X + (nat \rightarrow X)$, then $\omega$ isn't enough.

I'm looking for results that include exponentiation. What kind of ordinals are sufficient?

Especially appreciated would be a reference that presents a proof that such functors are $\alpha$-continuous for some ordinal $\alpha$ like in the above manuscript.

The answer to your question depends on several things, the most important of which is the size of your function spaces. I'll explain. Define
$$O_0 = nat $$
$$O_{n+1} = \mu X.\ 1+X+(O_n\rightarrow X)$$
As you noted in your answer, each $O_n$ can be considered internally to be the $n$-th regular cardinal of your system. In set theory, this datatype can be represented by an actual ordinal and is appropriately huge.

However, such constructions may be added to some version of type theory, and the question becomes: what ordinal is needed to give a set-theoretic interpretation to this construct? Now if we restrict ourselves to constructive semantics, a natural idea is to try to interpret each type by the set of "realizers" of this type, which is a subset of the set of $\lambda$-terms, or equivalently, the natural numbers $\mathbb{N}$.

In this case, it is easy to show that the ordinal is countable for any $O_n$, but that this ordinal grows very quickly. How quickly? Again, this depends on the amount of freedom you have when trying to build functions. The theory to building such ordinals is described in the theory of Large Countable Ordinals, of which Wikipedia has, surprisingly, a lot to say. In general it is easy to show that the ordinals in question are smaller than the Church-Kleene Ordinal, unless you allow non-constructive means of building functions (say $Beaver(n)$ that computes the busy beaver number for machines with $n$ states).

This isn't saying much though, except that in a constructive theory, you only require constructive ordinals to build interpretations. There is a bit more to say though. First, there is a very nice presentation by Thierry Coquand that details that in the absence of an eliminator for all other types but $nat$, you can build $O_1$ in exactly $\epsilon_0$ steps.

In general there seems to be a correspondence between the logical strength of a type theory, and the size of the largest ordinal that it can represent in this manner. This correspondence is the subject matter of Ordinal Analysis, which has been studied at great length since the late sixties, and is still under study today (with some amazing open questions). Warning though: the subject matter is as technical as it is fascinating.

Hope this helps.


NP-complete problem with polynomially many certificates? Let's call a language $L \in$ NP sparsely certificated if and only if:

There exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every input $x \in \Sigma^*$ of size $n$, if $x \in L$ then the set $U_x$ of certificates $u$ which verify that $x \in L$ is polynomially sized, i.e. $|U_x| \leq p(n)$.

In shorter terms, every input $x$ has at a most polynomial amount of certificates which verify its inclusion in $L$.

Example: To illustrate, consider the $\mathbf{CLIQUE}$ problem:

$\mathbf{CLIQUE} = \{\; (G,k) \;\mid\; G \text{ has a clique of size } k \;\}$

The language $\mathbf{CLIQUE}$ is not sparsely certificated, as an input $x = (G,k)$ could easily have an exponential amount of $k$-cliques acting as certificates which prove that $x \in \mathbf{CLIQUE}$.

End Example

The question, then, is: are there any known NP-complete sparsely certificated languages? Any insights are welcome, even if they don't answer the question!

Note: this definition is different from that of a sparse language!

No, there is no known sparsely certified $NP$-complete languages. The class that you are describing is known as $fewP$. It is widely believed that $fewP \ne NP$, So, No $NP$-complete problem is known to be in fewP. (It is impossible unless $fewP=NP$).


Communication problems for which a deterministic direct-sum theorem is not known to hold It is an old open problem whether a direct-sum theorem holds for deterministic communication complexity, that is, whether solving $t$ independent instances of a problem is $t$ times harder than solving a single instance. [FKNN95] showed the following results:

A negative result: There is partial function (due to [O90]) whose deterministic communication complexity is $\Theta(\log n)$, but computing it on $t$ independent instances has complexity $\Theta(t + \log t \cdot \log n)$.
A positive result: For every function $f$, if the deterministic communication complexity of $f$ is $c$ then the complexity of computing $f$ on $t$ independent instances is at least $\Omega(t \cdot (\sqrt{c} - \log n))$.

I am not aware of any other general positive results on the direct-sum problem. However, it seems that for specific problems that are usually considered in communication complexity, e.g. equality or disjointness, a direct-sum theorem is known to hold.

My question is, are there other examples of problems for which a deterministic communication complexity theorem is not known to hold, or even known not to hold (beside the function of [O90])?

References:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan: Amortized Communication Complexity. SIAM J. Comput. 24(4): 736-750 (1995)

[O90] Two Messages are Almost Optimal for Conveying Information. Alon Orlitsky. PODC, page 219-232. ACM, (1990)

I think I can suggest the problem, which is not widely known, but for which I'm interested in. Suppose we have $n$ permutations $\pi_i$ in $S_3$. Alice, Bob and Carol receive first, second and third elements of all permutations, respectively. The goal is to compute $\prod_i sgn(\pi_i)$, where $sgn(\pi_i)$ is a sign of permutation $\pi_i$ (can take -1 or +1). I'm interested in communication complexity in NiH model.

Some time ago I've tried to apply direct-sum theorem, but here we have some obstacles with dependence of input of different participants. I still don't know whether $\Omega(n)$ lower bound holds for this problem.


Regarding proper form of production rules of Context-free tree grammars Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$?

$\{a^nb^nc^n | n>0\}=\{Yield(t)|t\in L(G_t)\}$

I've tried to do it, using commonly used definition of CFTG (for instance see here), but I failed to express proper context-sensitive rules, using rules of the form $A(x_1,\dots,x_n)\rightarrow\alpha$. Looks like its description power is not enough, as I we can not operate subtrees structure in left side of the rule.

This question induced by well-known obvious relation between Regular Tree Grammars and Context-free word languages.

I would be happy if somebody would build such CFTG or confirm my assumption, that it is simply not possible.

UPD: More specifically, the problem is definition of variables inside rules: $A(x_1,\dots,x_n)\rightarrow\alpha$. It seems to be quite blur, as it is not quite clear: what are these variables? Can we say, that $x_i\in T_{\Sigma\cup X_n}$, where $X_n=\{x_1,\dots,x_n\}$, or not?

If we can describe CFTG rule as: $A(f(x))\rightarrow A_t(a, A(x))$, then problem goes away, it solves the question. But would it satisfy CFTG definition?

After a couple of hours of thinking I found at least proper form of grammar. Thanks to @Sylvain's commentary and link to Fisher's paper, which given me a clue.

Proper context-free tree grammar, which yield language coincides with $\{a^nb^nc^n|n>0\} $ will have simplest form:

$G=\{\Sigma,N,S,P\}$, where $\Sigma=\{a,b,c\}$, $N=\{S_t,F,A,B,C\}$, $S=\{S_t\}$, and set of production rules:

$S_t\rightarrow F(a,b,c)\\
F(x_1,x_2,x_3)\rightarrow F(A(a,x_1),B(b,x_2),C(c,x_3))$

That is it. Core idea is to wrap "stack" into subtrees of the form $A(a,x_1)$.

Thereby we receive following productions:

$S_t\Rightarrow F(a,b,c)$, $yield(F(a,b,c))=abc$
$S_t\Rightarrow F(a,b,c)\Rightarrow F(A(a,a),B(b,b),C(c,c))$, $yield(F(A(a,a),B(b,b),C(c,c)))=aabbcc$
$S_t\Rightarrow F(a,b,c)\Rightarrow F(A(a,a),B(b,b),C(c,c))\Rightarrow F(A(a,A(a,a)),B(b,B(b,b)),C(c,C(c,c)))$,
and so on.


Collapses under the assumption that $NEXP\subseteq P/Poly$ It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma_2^{P}$ and $MA = AM$.

What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$?

A whole lot of fun things happen. Most of the ones I know of start with the IKW paper. There, the collapse $\textrm{NEXP} = \textrm{MA}$ is shown, and (I think) is the strongest literal collapse of complexity classes that we know of. There are other sorts of "collapses" though that I think should be pointed out.
Most importantly, I think, is the "universal succinct witness" property (also from the IKW paper). For one, it gives you a tool from which many of the other collapses are straightforward consequences; for another, the recent circuit lower bounds (eg here and here) for $\textsf{NEXP}$ exploit this connection. Briefly, the property says that, for every $\textsf{NEXP}$ language $L$, and any $\textsf{NEXP}$-machine $M$ deciding $L$, every $x \in L$ has a succinctly describable witness according to $M$. Formally, there is a polynomial $p$ depending on $M$ so that for every $x \in L$, there is a circuit $C_x$ of size $p(|x|)$ so that the truth table of $C_x$ is a sequence of nondeterministic choices for $M$ that lead to acceptance on input $x$.
The succinctness of the witnesses comes in handy, because you can straightforwardly rederive a lot of the other collapses from it. For instance, it follows trivially that $\textsf{NEXP} = \textsf{coNEXP} = \textsf{EXP}$. For example, suppose $L$ is in $\textsf{NEXP}$ via a $\textsf{NEXP}$-machine $M$. The succinct-witness property says there's a polynomial $p$ so that $M$ has succinct witnesses of size $p$. We can then decide $L$ in $\textsf{EXP}$ by, on input $x$, brute-forcing all the circuits of size at most $p(|x|)$, and checking whether they encode a sequence of choices that lead to $M$ accepting on input $x$. You can combine this with the (previously known via interactive proofs) result that $\textsf{EXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{EXP} = \textsf{MA}$ to conclude $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{NEXP} = \textsf{MA}$.
It's worth emphasizing that we get to pick $M$ and hence the form of the witnesses. For example, you can actually conclude from "$\textsf{NEXP}$ has universal succinct witnesses" that $\textsf{NEXP} = \textsf{OMA} = \textsf{co-OMA}$. Here $\textsf{OMA}$ is "oblivious-MA", meaning that there is an honest Merlin which depends only on the input length.
It's easy to see that $\textsf{OMA} \subseteq \textsf{P}/\textrm{poly}$, so basically this is just giving a normal form for how $\textsf{NEXP}$ languages are computed in $\textsf{P}/\textrm{poly}$ under the assumption that $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$ in the first place.
Here's one way to see the collapse to $\textsf{OMA}$:

For a language $L \in \mathsf{NEXP}$ decided by a machine $M$, construct a $\mathsf{NEXP}$ machine $M'$ as follows. View the $n$-bit input as a number $N$ between $1$ and $2^n$. For every $x$ of length $n$, guess a witness $w_x$ and run $M(x,w_x)$ to verify it. $M'(N)$ accepts if and only if $M$ accepts for at least $N$ values of $x$. The guesses are arranged such that a succinct description of a witness for $M'$ is a circuit $C$ which computes the map $(x,i) \mapsto$ the $i$-th bit of $w_x$. Now suppose that $N$ is precisely the number of strings in $L$ at length $n$. Then succinct witnesses for $M'$ on input $N$ are circuits that simultaneously encode all of $M$'s witnesses for length-$n$ inputs. In particular, if $M'$ has succinct witnesses, then all of $M$'s witnesses can be simultaneously described by the same circuit.
To complete the claim, we'll recall that $\textsf{NEXP} = \textsf{PCP}[\textrm{poly}, \textrm{poly}]$. Letting $M$ be the machine which guesses the PCP and then deterministically simulates the verifier, the above paragraph tells us the existence of simultaneously succinctly describable PCPs for every language in $\textsf{NEXP}$. So now to get $\textsf{NEXP} = \textsf{OMA}$, we have Merlin send the succinct description of the PCPs for all inputs of the current input length, which Arthur can check by just plugging in his input and then running the PCP verifier.

[Thanks to Cody Murray for pointing out the trick of using the input to count the number of strings in $L$. Previously I had $M'$ use that if $\mathsf{NEXP}\subseteq\mathsf{P/poly}$ then $\mathsf{NEXP}=\mathsf{EXP}$ to write down the truth table of $L$, but Cody's strategy is more elegant.]
As a final note, while technically implied by $\textsf{NEXP}=\textsf{MA}$, the collapse $\textsf{NEXP}=\textsf{PSPACE}$ has another interesting implication. It's known that $\textsf{PSPACE}$ has a complete language which is both downward self-reducible as well as random self-reducible. Ordinarily, all such languages sit inside $\textsf{PSPACE}$ and so we shouldn't hope to say (unconditionally) that $\textsf{NEXP}$ has such a complete language as long as we hope that $\textsf{NEXP} \ne \textsf{PSPACE}$. However, if $\textsf{NEXP} = \textsf{PSPACE}$, then $\textsf{NEXP}$ does have such complete languages. A similar statement (replacing $\textsf{NEXP}$ by $\textsf{EXP}$) was used by Impagliazzo and Wigderson to conclude a sort of "derandomization dichotomy" for $\textsf{BPP}$ in relation to $\textsf{EXP}$, so it may be useful in discovering other consequences of $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$.


Examples of nontrivial non-discriminatory functions I am reading Cybenko's "Approximation by Superpositions of a Sigmoidal Function".
The paper defines a discriminatory function as:

$\sigma$ is discriminatory if for a measure $\mu$,
\begin{align}
\int \sigma (y^\top x + \theta) d \mu(x) = 0
\end{align}
for all $y \in R^n$ and $\theta \in R$, then $\mu=0$.

What is an example (with proof) of a non-discriminatory function? (besides 0)

Let $n=1$. Let $\mu$ be the usual Lebesgue length measure on $[1/2,1]$, and let $\mu$ be the negative of the usual Lebesgue length measure on $[0,1/2]$.

In particular, Lebesgue measure is $|\mu|$.

Let $\mathcal U\subseteq [0,1]$ be a set of Lebesgue measure 0. (For instance, $\mathcal U$ could be the set of all numbers whose binary expansion does not satisfy the law of large numbers...)

Let

$\sigma(x)=1$ for $x\in\mathcal U$, and
$\sigma(x)=0$ for $x\not\in\mathcal U$.

Then given $y$ and $\theta$, there are two cases.

Case 1: $y\ne 0$. Then
$$|\mu|\{X:y^\top X+\theta\in\mathcal U\}=0,$$ hence
$$|\mu|\{X:\sigma(y^\top X+\theta)\ne 0\}=0,$$
so $\int \sigma(y^\top X+\theta)d|\mu|(x)=0$,
so $\int \sigma(y^\top X+\theta)d\mu(x)=0$.

Case 2: $y=0$. Then $\sigma(y^\top X+\theta)$ is the constant $\sigma(\theta)$, which satisfies
$$\int \sigma(\theta)\,d\mu(x)=\sigma(\theta)\int d\mu(x)=\sigma(\theta)\mu([0,1])=0.$$

So, $\sigma$ is non-discriminatory.