Any algorithmic problem has a time complexity dominated by counting? What I refer to as counting is the problem that consists in finding
the number of solutions to a function. More precisely, given a
function $f:N\to \{0,1\}$ (not necessarily black-box), approximate
$\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|$.

I am looking for algorithmic problems which involve some sort of
counting and for which the time complexity is greatly influenced by
this underlying counting problem.

Of course, I am looking for problems which are not counting problems themselves. And it would be greatly appreciated if you could provide documentation for these problems.

This is a followup to Suresh's answer.  As he says, there are lots of construction problems in computational geometry where the complexity of the output is a trivial lower bound on the running time of any algorithm.  For example: planar line arrangements, 3-dimensional Voronoi diagrams, and planar visibility graphs all have combinatorial complexity $\Theta(n^2)$ in the worst case, so any algorithm that constructs those objects trivially requires $\Omega(n^2)$ time in the worst case.  (There are $O(n^2)$-time algorithms for all three of those problems.)

But similar constraints are conjectured to apply to decision problems as well.  For example, given a set of n lines in the plane, how easily can you check whether any three lines pass through a common point?  Well, you could build the arrangement of the lines (the planar graph defined by their intersection points and the segments between them), but that takes $\Theta(n^2)$ time.  One of the main results of my PhD thesis was that within a restricted but natural decision tree model of computation, $\Omega(n^2)$ time is required to detect triple intersections.  Intuitively, we must enumerate all $\binom{n}{2}$ intersection points and look for duplicates.

Similarly, there is a set of numbers where $\Theta(n^2)$ triples of elements sum to zero.  Therefore, any algorithm (modeled by a certain class of decision trees) to test whether a given set contains three elements that sum to zero requires $\Omega(n^2)$ time.  (It's possible to shave off some logs via bit-level parallelism, but whatever.)

Another example, also from my thesis, is Hopcroft's problem: Given $n$ points and $n$ lines in the plane, does any point contain any line.  The worst-case number of point-line incidences is known to be $\Theta(n^{4/3})$.  I proved that in a restricted (but still natural) model of computation, $\Omega(n^{4/3})$ time is required to determine whether there is even one point-line incidence.  Intuitively, we must enumerate all $\Theta(n^{4/3})$ near-incidences and check each one to see whether it's really an incidence.

Formally, these lower bounds are still just conjectures, because they require restricted models of computation, which are specialized to the problem at hand, especially for Hopcroft's problem).  However, proving lower bounds for these problems in the RAM model is likely just as hard as any other lower-bound problem (ie, we have no clue) — see the SODA 2010 paper by Patrascu and Williams relating generalizations of 3SUM to the exponential time hypothesis.


References for the computational complexity of training neural networks I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems.

In particular, I'm trying to study questions like:

How is training complexity related to network topology ?
How is training complexity related to the complexity of the decision boundary?

See the papers by Roi Livni and coauthors:

*Roi Livni, Daniel Carmon, Amir Globerson:
Learning Infinite Layer Networks Without the Kernel Trick. ICML 2017: 2198-2207

*Roi Livni, Shai Shalev-Shwartz, Ohad Shamir:
On the Computational Efficiency of Training Neural Networks. NIPS 2014: 855-863


Separating $DSPACE(f)$ and $DTIME(2^f)$: is there any function computable in time $2^{O(f)}$ but not in space $O(f)$? For $f(n)\ge n$,

$$\mathsf{DSPACE}(f(n)) \subseteq \mathsf{DTIME}(2^{O(f(n))}).$$

Is there any function $f$ for which this containment is known to be proper?

If $\mathsf{L} = \mathsf{P}$ then $\mathsf{DSPACE}(O(f(n))) = \mathsf{DTIME}(2^{O(f(n)})$ for all time-constructible functions $f(n) \geq \log n$ using standard padding arguments. I am not sure what happens if $f(n)$ is not time-constructible.

If $\mathsf{L} \neq \mathsf{P}$ then $f(n) = \log n$ will be an example. Therefore there is a time-constructable function $f(n)$ where the containment is proper iff the containment is proper for $f(n) = \log n$ .


How to know if X and Y have coauthored? Is there any tool where one can figure out if two people have coauthored or not? Like the tool where one can figure out somebody's Erdos _number_ .

In computer science, DBLP might be a better idea than MathSciNet. Your own page in DBLP lists all your coauthors; the database is certainly not complete, but usually the information is correct.

You can also try to use Google Scholar, with a search similar to this:

author:foo author:bar

As always with Google Scholar, double-check the results.


Avalanche like stochastic process Consider the following process:

There are $n$ bins arranged from top to bottom. Initially, each bin contains one ball. In every step, we

pick a ball $b$ uniformly at random and
move all the balls from the bin containing $b$ to the bin below it.
If it already was the lowest bin, we remove the balls from the process.

How many steps does it take in expectation until the process terminates, i.e., until all $n$ balls have been removed from the process? Has this been studied before? Does the answer follow easily from known techniques?
In the best case, the process can finish after $n$ steps. In the worst case it can take $\Theta(n^2)$ steps. Both cases should be very unlikely though. My conjecture is that it takes $\Theta(n\log n)$ steps and I did some experiments which seem to confirm this.
(Note that picking a bin uniformly at random is a very different process that will obviously take $\Theta(n^2)$ steps to finish.)

Not really an answer, but an extended comment on András's answer.

András's answer contains a nice intuition, though I do not believe it is a rigorous calculation of the expected number of steps. I think it is perhaps a good approximation to an answer, but it does not seem to properly deal with cases where the bin below the highest occupied bin becomes empty before that the upper bin is emptied downwards. Still, this might be a reasonable approximation to make (I'm not sure).

His calculation contains an error which affects the scaling. I'm going to take exactly the same starting point, and redo and expand the calculation.

It misses a factor of p inside the summation, as the probability of randomly choosing the correct bin is $\frac{p}{n}$ rather than $\frac{1}{n}$. As a result we have

$\begin{eqnarray*}
n + \sum_{p=1}^n \sum_{k=0}^{\infty} (k+1) \frac{p}{n} \left(\frac{n-p}{n}\right)^k
& = & n + \sum_{p=1}^{n} \frac{p}{n} \sum_{k=0}^{\infty} (k+1) \left(\frac{n-p}{n}\right)^k
\\\\& = & n + \sum_{p=1}^{n} \frac{p}{n} \cdot \frac{n^2}{p^2}
\\\\& = & n + n\sum_{p=1}^{n} 1/p
\\\\& = & n (1+H_n)
\end{eqnarray*}$

where $H_n = \sum_{p=1}^{n} 1/p$ is the nth Harmonic number. To approximate $H_n$ we can simply replace the summation with an integral: $H_n \approx \int_{1}^{n+1} \frac{1}{x} dx = \log(n+1)$. Thus the scaling is $n (1+\log(n+1))$ or approximately $n \log(n+1)$. While this scaling does not match the scaling of the problem exactly (see simulation below) it is out by almost exactly a factor of $\log(2)$.

Red circles: Data points from simulation of process averaged over 10k runs. Green: $n \log_2(n+1)$. Blue: $n \log(n+1)$.


Delegating all of the work to the prover in $\mathcal{MA}$ protocols An $\mathcal{MA}$ communication complexity protocol is communication complexity protocol that starts with an omniscient prover that sends a proof (that depends on the the specific input of the players, but not on their random bits) to both players. The players then communicate with each other, in order to verify the proof (for more details, see: On Arthur Merlin Games in Communication Complexity, by Hartmut Klauck).

The are quite a few lower bounds (e.g., On the power of quantum proof, by Ran Raz and Amir Shplika) of the following form: Suppose we have a communication complexity problem $\mathcal{P}$ with a tight bound of $\Theta(T(n))$ on its communication complexity (for some function $T$). There exists a lower bound that shows that every $\mathcal{MA}$ communication complexity protocol that communicates $c$ bits and uses a proof of size $p$, must satisfy $c \cdot p = \Omega(T(n))$. So one can think of it as a tradeoff between the work that prover has to do, and the work that the verifiers have to do.

Moreover, it seems that for every communication complexity problem that I know of (with a tight bound of $\Theta(T(n))$ on its communication complexity), there exists a protocol wherein the prover sends a proof of size $\tilde O(T(n))$, and the verifiers only uses $\tilde O(1)$ bits of communication (cf. the two papers I mentioned above). Thus, in a sense, all of the work has been delegated to the prover (achieving the extreme case of the aforementioned lower bounds).

Is there a result that shows that a verifier-"heavy" protocol implies the existence of a prover-"heavy" protocol? Is there a counter example? What about other models (such as $\mathcal{MA}$ decision trees/query complexity) wherein our understanding of the behaviour of $\mathcal{MA}$ protocols is deeper?

This is an answer to the last question: MA in the query complexity model.

It isn't always possible to make the prover do all the work (or even any work at all). The reason is that an MA-prover is trying to convince you that the answer is YES. But the problem can be chosen so that in the YES case, there's nothing interesting that the prover can tell you. There are hard problems for which having a YES-prover is completely useless (i.e., it will not reduce the verifier's work at all).

For example, consider the AND problem, where you have to compute the AND of all the bits in the black box. This requires $\Omega(n)$ queries for a bounded-error algorithm. Now if you have access to a YES-prover, there's nothing interesting he can tell you. The most he could do is give you the entire contents of the black box. But since it is the AND function, and he is trying to convince you that the function evaluates to 1, he will always give you the all ones string. So you could have simulated this yourself.

Added: Does this protocol work in communication complexity? Take any CC problem that requires $T(n)$ bits of communication without Merlin. In the MA protocol, Merlin sends the entire transcript of communication to Alice and Bob, had they used the original protocol. Since equality is easy to check in randomized CC, they check that the transcripts are the same with high probability. Once they are convinced that the transcripts are the same, they output the outcome of that transcript of conversation.


Is there an expressiveness hierarchy for type systems? Inspired by the extensive hierarchies present in complexity theory, I wondered if such hierarchies were also present for type systems. However, the two examples I've found so far are both more like checklists (with orthogonal features) rather than hierarchies (with successively more and more expressive type systems).

The two examples I have found are the Lambda cube and the concept of k-ranked polymorphism. The first one is a checklist with three options, the second is a real hierarchy (though k-ranked for specific values of k is uncommon I believe). All other type system features I know of are mostly orthogonal.

I'm interested in these concepts because I'm designing my own language and I'm very curious how it ranks among the currently existing type systems (my type system is somewhat unconventional, as far as I know).

I realise that the concept of 'expressiveness' might be a bit vague, which may explain why type systems seem like checklists to me.

There are several senses of "expressiveness" that you might want for a type system.

What mathematical functions can you express in a particular type system.  For example, in the simply typed lambda calculus, not all computable functions can be expressed.  The same is true of System $F$, but strictly more functions can be expressed.  This is not very interesting once you get to type systems for Turing-complete languages.
Can system $A$ typecheck every program written in system $B$.  This is basically what cody's first notion of strength is about for PTSs.  Again, System $F$ is stronger than the STLC in this ordering, since every STLC program types in System $F$.  Similarly, a system with subtyping will be stronger than a system without.
Are there local transformations (in the sense of Felleisen's paper On the expressive power of programming languages) that allow a program that types in system $A$ to type in system $B$, but not vice versa.
Does one type system guarantee stronger properties than another.  For example, linear type systems just reject more programs, but that allows them to make stronger statements about the programs they do accept.

Unfortunately, I don't believe that there's been work on categorizing or formalizing these notions, with the exception of Barendregt's lambda-cube, as @cody discusses.


Can we efficiently convert from NFA to smallest equivalent DFA? Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.

Conversion Problem: NFA to smallest equivalent DFA
Input: A nondeterministic finite automaton $A$.
Output: A smallest possible deterministic finite automaton $B$ such that $L(A) = L(B)$.

We can solve this problem by converting from NFA to DFA using the powerset construction and then minimizing the resulting DFA.  However, this seems inefficient.
In particular, it seems that this could run for $O(2^{sc(L)})$ time where $L = L(A)$ if the powerset construction gives us a suboptimal DFA.

Question: Is there an algorithm for this problem that runs in linear time in terms of the state complexity?  By this, I mean that it runs in $O(n + sc(L))$ time where $n$ is the size of $A$ and $L = L(A)$?  What about $poly(n + sc(L))$ time?

See here:
https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings
"checking whether an NFA accepts all strings is PSPACE-complete".
In particular, if an NFA accepts all strings then its smallest equivalent DFA has size 1, and so a positive answer to your question would imply P=PSPACE.


Relation between group theory and information theory Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory).

Question:
Is there any paper/survey paper on group-theoretic information theory?

Sadly, group structure is nearly so limited that there isn't much one can do with it to be of use in information theory, thus the literature is prone to be fairly sparse. Even Abelian groups aren't enough structure.

Even basic abstract algebra texts which have some basic coding theory applications generally provide examples using field theory or linear algebra. If there were useful examples for groups, they'd most likely be introduced there.

Hungerford, Thomas; Abstract Algebra: An Introduction
Rotman,J.J.; A First Course in Abstract Algebra, Third Edition

As most of Rotman's work was in group theory, if anyone would have had examples there, certainly he would. Steven Roman at UCI also did a good bit of textbook writing (separately) on coding theory and field theory and has a text Fundamentals of Group Theory: An Advanced Approach (Birkhauser), but not having read it, I suspect you'll find it barren of the group theoretical work you're looking for.

In the late 90's I seem to recall some work on binary codes defined by using codes over the alphabet $ \mathbb {Z}_4$. For some background (and possible references) see J.H. van Lint's Introduction to Coding Theory, Third Edition (Springer, 1999).

Once you take the algebraic step up to even finite fields, you're far more likely to find overlap with more coding theory. For this, try taking a look at Error-Correcting Linear Codes: Classification by Isometry and Applications (Springer) by Betten, Braun, et al. which may have some scant material on applications to groups as I recall.


Maintaining order in a list in $AC^0$ in $O(1)$ time The order maintenance problem (or "maintaining order in a list") is to support the operations:

singleton: creates a list with one item, returns a pointer to it
insertAfter: given a pointer to an item, inserts a new item after it, returning a pointer to the new item
delete: given a pointer to an item, removes it from its list
minPointer: given two pointers to items in the same list, returns the one closer to the front of the list

I am aware of three solutions to this problem that perform all operations in $O(1)$ amortized time. They all use multiplication.

Athanasios K. Tsakalidis: Maintaining order in a generalized linked list
Dietz, P., D. Sleator, Two algorithms for maintaining order in a list
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito, “Two Simplified Algorithms for Maintaining Order in a List”

Can order be maintained in a list in $O(1)$ amortized time without using any arithmetic operations not in $AC^0$?

Yes!

Use a two-level structure as discussed at the end of Section 2 of the Dietz and Sleator paper. For the top structure, use a scapegoat tree. By using a balance factor that can be implemented in $AC^0$ (like $2$), we get the result.

See also exercise 8.12 from open data structures and Roura's "A new method for balancing binary search trees".


Can Curry-Howard prove a theorem from the types in your program, that has nothing to do with your program? The following link states:

  Curry-Howard means that any type can be interpreted as a theorem in some logical system, and any term can be interpreted as a proof of its type.
  This does not mean that those theorems have anything to do with your program. Take the following function:

swap : forall a,b. (a,b) -> (b,a)
swap pair = (snd pair, fst pair)

  The type here is forall a,b. (a,b) -> (b,a). The logical meaning of this type is (a and b) => (b and a). Note that this is a theorem in logic, not a theorem about your program.

My question is: Can Howard-Curry prove a theorem from the types in your program, that has nothing to do with your program?

I'll answer the opposite question which is:

  can Curry-Howard prove a theorem for your program, which has nothing to do with the type?

The answer is yes, depending on the meaning of "nothing to do". I'll leave the Curry-Howard aspect aside somewhat, but it underlies a lot of this approach.

The key idea is Wadlers' Theorems for Free! building on ideas from Reynolds, which allow you, given a program type, to deduce something about the program. For example, a program $f$ of type

(a, b) -> (b, a)

in haskell must satify

$$ \forall x\ y,\ f\ (x, y) = (y, x)$$

and therefore be the swap function.


Evidence that Graph Isomorphism problem is not $NP$-complete Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph Isomorphism can not be $NP$-complete unless the polynomial hierarchy [1] collapses to the second level. Also, the counting[2] version of GI is polynomial-time Turing equivalent to its decision version which does not hold for any known $NP$-complete problem. The counting version of $NP$-complete problems seems to have much higher complexity. Finally, the lowness result [3] of GI with respect to $PP$ ($PP^{GI}=PP$) is not known to hold for any $NP$-complete problem. The lowness result of GI has been improved to $SPP^{GI}=SPP$ after Arvind and Kurur proved that GI is in $SPP$ [4].

  What other (recent) results can provide further evidence that GI can not be $NP$-complete?

I posted the question on Mathoverflow without getting an answer.

[1]: Uwe Schöning, "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124

[2]: R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131–132

[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity 2 (4): 301–330

[4]: V. Arvind and P. Kurur. Graph isomorphism is in SPP, ECCC TR02-037, 2002.

Due to Babai's recent result (see the paper) $GI$ is in quasi-polynomial time ($QP$). If $GI$ is $NP$-complete, then it implies $NP\subseteq  QP=DTIME(n^{polylog\, n})$. This, in turn, implies $EXP=NEXP$, see
here. Therefore, if the commonly accepted conjecture $EXP\neq NEXP$ holds, then $GI$ cannot be $NP$-complete.


Finding cycle with constraints Given a graph in which each vertex $A_i$ has float value $B(i)$ between 0 and 1 inclusive.
How can we find a cycle (if such exists) with vertices $[C_1, C_2, ..., C_k]$ which violates following condition: $\sum(B(C_i)]) \le k/2$ (integer division)?
Thank you.

I assume that your graph is undirected.

If you allow $k/2$ without integer division,
then you can reduce your problem to computing the maximum mean weight cycle. Replace every undirected edge by two directed egdes. Every edge leaving a node $A_i$ gets value $B(i)$. Compute a cycle of maximum mean weight (i.e., with maximum average edge weight).
You condition is violated if and only if the maxium mean weight is $> 1/2$.

The maximum mean weight cycle as well as the minimum mean weight cycle can be computed
in polynomial time by Karp's algorithm, see Cormen, Leiserson, Rivest, Stein.

If you insist on integer division, things get more delicate, since there could be several
maximum mean weight cycles and a longer one can satisfy the bound but a shorter one need not. You can slightly reduce the weights (by a constant $\epsilon$ which is negligble
compared to your edge weights). This will favour shorter cycles and you might get away with this.


Edge-weight updates in all pair shortest path problem I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network.  An answer to my previous question led me to Hiroki Yanagisawa's paper "A multi-source label-correcting algorithm for the all-pairs shortest paths problem" [IPDPS 2010] which is performing really well.

But what about updates?  I couldn't produce a technique which can update the shortest paths quickly when the weight of an edge changes.  On researching, I came across a paper "On Dynamic Shortest Path problems", which states that

  Reductions that show that the incremental and decremental single-source
  shortest-paths problems, for weighted directed or undirected
  graphs, are, in a strong sense, at least as hard as the static all-pairs
  shortest-paths problem.

So the question is: Are there useful heuristic approaches to solve this problem?

your question seems quite advanced and it seems unlikely anyone has considered the incremental problem for the particular algorithm you are implementing when the new nonincremental algorithm was published by Yanagisawa as recently as 2010.

the algorithm you cite is apparently designed to be parallelizable therefore that seems like the 1st approach to optimizing it. ie implement it in a highly parallel implementation and just recompute all paths.

I have not seen a paper describing this, but how about this approach which seems to work in theory & in general but details could be tricky (maybe it appears in a paper somewhere-- would be interested if anyone has seen a similar technique). every algorithm to solve the problem must basically reduce to a (2-way?) comparison of edge weights. the resulting paths are built out of the results of these comparisons. the "comparison tree" for every optimal path can be stored during the 1st computation of all pairs.

then when any weights are changed, traverse through all prior stored/built-up comparison trees to recompute the answer. probably, for small changes, one would not have to descend "deeply" into those trees because the results of some or "many" prior comparisons are unchanged. one may have to modify the trees if new "comparison paths" in the trees are triggered but again this might not be expensive. however there would be a threshold where it is simpler to recompute everything from scratch when there are too many weight changes.

the main question of course is the memory cost of storing all the comparison trees.

(fineprint: and if all this actually worked, it would likely be a significant advance & publishable result.)


Understanding graph minor theorem This question is two-fold, and is mainly reference-oriented:

Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know the proof is long and difficult, but surely there must be key ideas that can be communicated in an easier way.
Are there other relations on graphs that can be shown to be well quasi-orders, maybe in a simpler way than for the minor relation? (obviously I am not interested in trivial results here, like comparing sizes). Directed graphs are also in the scope of the question.

The following book covers some material related to the proof of the graph minor theorem (Chapter 12).

Reinhard Diestel: Graph Theory, 4th edition, Graduate Texts in Mathematics 173.

The author states: "[...] we have to be modest: of the actual proof of the minor theorem, this chapter will convey only a very rough impression. However, as with most truly fundamental results, the proof has sparked off the development of methods of quite independent interest and potential."

An electronic version of the book can be viewed online.
http://diestel-graph-theory.com/


Coupon collector - the effect of randomization Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x _1, ..., x _k\}$ until all elements of $S$ are seen, where $x _i$ is the element drawn at the $i^{th}$ draw. In here, $k = n H_n$ following the standard solution of the coupon collector problem.

Note that $x _k$ have been seen only once. We create the $S'$ = $\{S - x _k\}$ and $X' = \{X - x _k\}$. We shuffle $X'$ and get a shuffled series $\{p(x'_1), ..., p(x' _{k-1})\}$, where $p(x' _i)$ is the $i^{th}$ drawn element from the shuffled set $X'$. What is the smallest index $m$ such that the sequence $\{p(x' _1), ..., p(x' _m)\}$ contains all elements in $S'$ ?

Can we simply assume that $m = (n-1) H _{n-1}$ following the same logic of coupon collector ?  or is $k$ is too small to assume that the distribution of $X'$ is uniform ?

If not, then what is the expected value of $m$ ?

$E[m]$ equals $n(H_n-1)$.

Here's a more complete proof sketch, following the argument suggested in my comment.

We start by showing that each permutation of the first $k-1$ elements is equally likely.

More precisely, let $X^*=(X_1,X_2,\ldots,X_K, \ldots)$ be an infinite random sequence where each $X_i$ is drawn independently and uniformly from $S$.  Let r.v. $K$ be the first index at which all elements of $S$ have been seen. Let r.v. $X'=(X_1,X_2,\ldots,X_{K-1})$.

Let $i$ denote any positive integer. Let $s$ denote any element of $S$.
Let $x=(x_1,x_2,\ldots,x_{i-1})$ denote any value of $X'$ that can occur,
given that $K=i$ and $X_K = s$.  (That is, $x$ is any length-$(i-1)$ sequence in which
each element of $S-\{s\}$ occurs, and $s$ does not occur.)

Let $\pi$ be any permutation of $[i-1]$.
Let $\pi(x)$ denote sequence $x$, permuted by $\pi$.

Lemma: Fix any such $i$, $s$, $x$, and $\pi$. Conditioned on $K=i$ and $X_k=s$, the probability that $X' = x$ is the same as the probability that $X' = \pi(x)$.

Proof.  To save typing, let $(i,s)$ denote the event that $K=i\wedge X_K=s$.

We want to show $\Pr[X'=x ~|~ (i,s)] = \Pr[X'=\pi(x) ~|~ (i,s)]$.

Let $x\prec X^*$ denote that $x$ is a prefix of $X^*$.
Let $x,s\prec X^*$ denote that $(x_1,\ldots,x_{i-1},s)$ is a prefix of $X^*$.
Note that
$$\Pr[X' = x ~|~ (i,s)]\,\Pr[(i,s)] ~=~ \Pr[X' = x \wedge (i,s)] ~=~ \Pr[x,s\prec X^*] ~=~ \frac{1}{n^i}.$$
Thus,
$$\Pr[X' = x ~|~ (i,s)] ~=~ \frac{1}{n^i \Pr[(i,s)]}.$$
Since the right-hand side is independent of $x$,
and $\pi(x)$ is also a possible value of $X'$,
$\Pr[X' = \pi(x) ~|~ (i,s)]$ also equals the right-hand side above.  QED

Corollary: Randomly permuting the first $k-1$ elements of $X$
(as described in the question) does not change the distribution of $X$.

This implies that the distribution of the r.v. $m$ as defined in the question
(with permutation of the first $k-1$ elements)
is the same as the distribution of $m$ if the elements are not permuted.
That is, $m$ is distributed as the first index at which $n-1$ distinct
elements in $S$ have been seen.  By a standard calculation,
$E[m]$ equals $n(H_{n}-1)$.


Are there Similar Distance Binary Error Correcting Codes? I'm trying to find a low distortion embedding of the trivial metric space into hamming space.

It seems this should be doable by using a large set of low dimensional vectors, with approximately equal pairwise distance.

My question is if it makes sense to expect error correcting codes to have this property?

Usually when designing error correcting codes, we are interested in finding the highest achievable rate, given a minimum distance between points. A similar question is to consider, instead of the minimum distance, the ratio between the maximum and minimum distance, $\rho=max/min$. Given $\rho$, what codes should one consider for maximizing the rate?

I tried to count the distances in some of the codes from this list of optimal binary codes:

The $(7,2^3,4)$ code has all distances equal to four, so $\rho=1$.
The $(8,2^4,4)$ code has $112$ pairs of distance $4$ and $8$ of distance $8$, so it has $\rho=2$.
The $(9,40,3)$ code has maximum distance $8$, so $\rho=8/3$.
The $(24,2^{12},8)$ golay code has maximum distance $24$, so $\rho=3$.

The two later codes are nearly as bad as possible. Are there any codes for which I shouldn't expect this to be the case? If not, can I at least say something about the distribution of distances being fairly concentrated?

Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$.

To see it, write the elements of the set as the rows of a matrix, and then define the code to be the span of the columns of the matrix. The $\epsilon$-biased property of the set is equivalent to saying that the relative distance between codewords is always between $0.5 - \epsilon$ and $0.5 + \epsilon$.

One particular construction of such sets will give you a code whose dimension is linear in its block length. It is mentioned here:
http://www.wisdom.weizmann.ac.il/~benaroya/SmallBiasNew.pdf

Basically, the idea is to take AG codes of constant rate and relative distance close to $1$, and concatenating them with the Hadamard code.


Big-O bounds on the k-th largest element of iid Gaussians I'm interested in the following problem. Let $X_1, \dots, X_n$ be iid samples with a $N(0,1)$ distribution. Let $X_{[k]}$ be the $k$-th largest element of $\{X_1, \dots, X_n\}$, so e.g. $X_{[1]} = \max_i X_i$.

Are there simple big-O bounds on $X_{[k]}$ for, say, all $k < n/2$? I know that $X_{[1]} = O(\sqrt{\log{n}})$ (see here), and more generally, $X_{[c]} = O(\sqrt{\log{n}})$ for constant $c$ (see here). But what about $X_{[\log{n}]}$ or $X_{[n/4]}$, for example?

My motivation is that I want to calculate $\sum_{i=1}^k E[X_{[i]}]$ for various values of $k$.

Thanks!

This is not a complete answer by any means, but just a quick estimate on $\mathbb{E}[\sum_{i=1}^k X_{[i]}]$ that is slightly better than the trivial bound of $O(k\sqrt{\log n})$. If this is your goal, I would think it is easier to go directly for it than consider any given $X_{[k]}$. Let $X_S=\sum_{i\in S} X_i$ for a subset $S\subseteq [n]$ and $Y_k=\sum_{i=1}^k X_{[i]}$. Using the same technique as in the first link,
\begin{align}
\exp(t\mathbb{E}[Y_k])&\leq \mathbb{E}[\exp(tY_k)]\\
&=\mathbb{E}\bigg[\max_{S\subseteq [n]:\vert S\vert=k}\exp(tX_S)\bigg]\\
&\leq \sum_{S\subseteq [n]:\vert S\vert=k}\mathbb{E}[\exp(tX_S)]\\
&=\sum_{S\subseteq [n]:\vert S\vert=k}\exp\bigg(\frac{kt^2}{2}\bigg)\\
&={n \choose k}\exp\bigg(\frac{kt^2}{2}\bigg).
\end{align}
Taking (natural) logarithms, we find
$$
\mathbb{E}[Y_k]\leq \frac{\log{n \choose k}}{t}+\frac{kt}{2}.
$$
Optimizing gives $t=\sqrt{\frac{2\log{n \choose k}}{k}}$ so we deduce
$$
\mathbb{E}[Y_k]\leq \sqrt{2k\log{n \choose k}}.
$$

For $k=o(n)$, it is known that $\log{n \choose k}=(1+o(1))k\log(n/k)$, so in this regime, we get
$$
\mathbb{E}[Y_k]\leq k\sqrt{2(1+o(1))\log(n/k)},
$$
which for $k=\log n$, say, is a bit better than the naive bound.

When $k=\alpha n$ for some constant $\alpha$, one instead has $\log{n \choose k}=(1+o(1))H(\alpha)n$, where $H(p)=-p\log p-(1-p)\log(1-p)$ is the entropy function. So in this regime, that would give
$$
\mathbb{E}[Y_k]\leq n\sqrt{2(1+o(1))\alpha H(\alpha)}.
$$

Lower bounds added for completeness: for linear $k$, one can get decent linear lower bounds that degrade as $\alpha\to 0$ but is tight at $\alpha=1/2$. Let $\alpha<1/2$, then by the Chernoff bound,
$$
\Pr(X_{\alpha n+1}\leq 0)\leq \exp\bigg(\frac{-(1/2-\alpha)^2n}{2}\bigg).
$$
It is known that for $i<j$, the conditional distribution of $X_{[i]}$ given $X_{[j]}=x$ is the same as the unconditional distribution of $X_{[i]}$ taken from a sample of size $j-1$ conditioned to be larger than $x$. As we are summing over all $i\leq \alpha n$ and taking expectations, we find that
$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}\vert X_{\alpha n+1}\geq 0]\geq \mathbb{E}[\sum_{i=1}^{\alpha n} Y_i],
$$
where the $Y_i$ are normal random variables conditioned to be larger than $0$, which are known to have expectation $\sqrt{2/\pi}$. We also find that
$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}\vert X_{\alpha n+1}\leq 0]\geq 0,
$$
as for each $x<0$, conditioning on $X_{\alpha n}=x$, by the same reasoning we are now taking expectations over a sample of size $\alpha n$ normal random variables conditioned to be at least $x$, which by symmetry of the normal distribution is at least $0$ (formally, we are using that the sum over the whole sample makes the labelling of the order statistics irrelevant). We conclude that
$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}]\geq \bigg(1-\exp\bigg(\frac{-(1/2-\alpha)^2n}{2}\bigg)\bigg)\alpha n\sqrt{2/\pi}=(1-o(1))\alpha n \sqrt{2/\pi}.
$$
This holds for all $\alpha<1/2$, and by monotonicity of the left hand side in $\alpha$ for $\alpha<1/2$ and taking limits, we can further conclude using the upper bound in the comments
$$
\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}]=(1-o(1))n\sqrt{1/(2\pi)}.
$$

Obviously similar lower bounds hold for $k=o(n)$ but these aren't super useful as they are of vastly different order than the upper bound.

Numerical Simulations: Numerical simulations suggest that these bounds are surprisingly decent in the two regimes mentioned in the post. Note that for any $k$, the function $f(x_1,\ldots,x_n)=\sum_{i=1}^k x_{[i]}$ is Lipschitz, so by Gaussian concentration, one expects simulations to roughly approximate the expectation. For instance, for $k=\log(n)$, here is a plot of the upper bound with that of simulation, with the top curve being the naive bound of $\sqrt{2}\log(n)^{3/2}$ and the lower curve the given bound:

In the linear $k$ regime, for the few values I tried, the constant of the upper bounds seems to be off by a factor of at most $3$ (at $\alpha=1/2$, where we have computed the exact asymptotics). For instance, for $k=n/4$, the plot with the bound looks like:

The upper bounds seem pretty good for small constant $\alpha$, while the lower bounds degrade. For instance, here is $\alpha=.001$:

Here's one more plot (because I can't resist) with $k=\sqrt{n}$: Hope this helps!


Collection of failed attempts to solve X I've been half-jokingly entertaining the idea of trying to blog about "n ways not to solve P vs NP" in the indefinite future, and in my search came across the How not to solve P=NP? question on cs.stackoverflow.

Clearly P vs NP is a great starting point, being the source of so much development in TCS. But this got me wondering if there are other problems where people have consistently published their failures, or just any thoughts on why some things don't work. Surely not in papers, unless a strong negative result came out, but probably in blog format (which is increasingly becoming its own medium for communicating science).

Of course, this doesn't seem very practical (unless you store all your progress in digital or easily-convertible-to-digital format), but maybe the benefits outweigh the costs. So the other natural question is, how useful do you think it would be if we started doing it as a community? How often is a failed attemp one (or several) steps away from a success?

I've idly entertained the idea of an online arxiv overlay "journal" of negative results. The idea would be to allow negative results or counterexamples that don't seem suitable for a full publication in traditional venues. It would be lightly reviewed, so that we can guarantee that every paper has at least been looked over and approved by an expert in the area. It wouldn't necessarily be archival or "official", but it would at least be citable.

I think such a resource could be very helpful for publicizing dead ends in some lines of inquiry as well as "folklore negative results" that may not be widely known. I can think of a few examples from my own experience. A main challenge would be in finding and connecting with reviewers, due to the variety of possible research areas involved.

If there seems to be enough interest in this idea from the cstheory community, particularly people saying they'd be willing to submit and to review, then I'd be willing to take a lead in organizing. I'm pretty sure I can find some colleagues willing to join and help organize for the first few years.


What logic correponds via Curry-Howard to a Monad? According to Moggi's 1991 paper "Notions of computation and monads" one can represent monadic equational logic with the well known monad $(T, \eta, \mu)$ with T an functor and the two natural transformation
$\eta: Id \to T$ and $\mu: T^2 \to T$ that arise out of an adjunction.  Monadic Equational Logic limits one to a single formula on each side of the turnstile such as $x_1 : \tau_1 \vdash_{pl} e: \tau_2$.

In order to go beyond monadic equational logic to allow programs of the form
$x_1: \tau_1, \dots, x_n:\tau_n \vdash e: \tau$ one needs an extra strength natural transformation

$t_{A,B}: A \times TB \to T(A \times B)$

This allows one to take a context $\Gamma$ into account, represented by the $A$ in $t_{A,B}$ above.

This corresponds to the formula in modal logic

$A \land \diamond B \supset \diamond(A \land B)$

which is logically quite weird as it would allow one to have propositions $A$= "S can board the plane" and $B$="S cannot board the plane" and reason "S can board the plane and it could have been the S cannot board the plane" to "it is possible that S can board the plane and that S cannot board the plane".

Moggi writes in his conclusion:

  The semantics of computations corroborates the view that (constructive) proofs and programs are rather unrelated, although both of them can be understood in terms of functions. Indeed, monads (and comonads) used to model logical modalities, e.g. possibility and necessity in modal logic or why not and of course of linear logic, usually do not have a tensorial strength. In general, one should expect types suggested by logic to provide a more fine-grained type system without changing the nature of computations.

Have I understood this correctly? Is the Curry-Howard isomorphism for monads illogical?

The two papers to look at it are Benton, Bierman and de Paiva's Computational Types from a Logical Perspective, which directly gives a proof theory for Moggi's computational lambda-calculus; and Rowan Davies and Frank Pfenning's A Judgmental Reconstruction of Modal Logic, which gives a constructive proof theory for S4 modal logic with box and diamond, and then translates Moggi's metalanguage into it.

Both papers note that the axioms of a strong monad were originally introduced by Curry in 1952, which was independently re-invented by Fairtlough and Mendler as lax logic. Giving the action on types and contexts below, we see:

$$
\begin{array}{lcl}
( \to )^+ & =& ◻^+ \to ^+ \\
(◯)^+ & = & ◊◻^+ \\
^+ & =&  \;\;\mbox{for atomic}\;  \
\end{array}
$$

The translation of Davies and Pfenning is very similar to Gödel's embedding of intuitionistic logic into classical logic, and to Girard's embedding of intuitionistic logic into linear logic.


Cartesian factorization of a finite set of n-tuples (NB: I asked this question in Math Overflow, and based on the one reply [a comment, actually] that it received so far, I realized that this may be a more appropriate forum for it.  I've added a few comments to this post, connecting the problem to the theory of databases.)

I'm interested in factoring a finite set of $n$-tuples as the Cartesian product of two "factor sets", of which the first factor is itself the Cartesian product of some of the set's projection images, and the second factor is an unfactorizable "remainder".

To describe the problem more precisely, let $X$ be a non-empty, finite set of $n$-tuples, and let $A_1,...,A_n$ be the images of $X$ upon projection onto its various coordinates.  Hence, $X \subset \prod_{i=1}^{n} A_i $.  Furthermore, assume that this inclusion is strict; that is, $X \neq \prod_{i=1}^{n} A_i $.  (From this it follows that $n > 1$.)  If $\sigma$ is some permutation of $\{1,...,n\}$, let $X_\sigma$ denote the set of $n$-tuples derived from $X$ by permuting the coordinates of its elements according to $\sigma$: $X_\sigma = \{(x_{\sigma(1)},...,x_{\sigma(n)})|(x_1,...,x_n)\in X \}$.  (See the end of this post for a restatement of the problem using OLAP terminology.)

For any $n$-permutation $\sigma$, I'm interested in factorizations of $X_\sigma$ having the form $X_\sigma = (\prod_{i=1}^{k} A_{\sigma(i)}) \times Z$, where $0 \leq k \lt n$ and $Z \subsetneq \prod_{i=k+1}^{n} A_{\sigma(i)}$.  This factorization means that every $n$-tuple in $X_\sigma$ can be written (obviously uniquely) as the concatenation of one $k$-tuple from $\prod_{i=1}^{k} A_{\sigma(i)}$ and one $(n-k)$-tuple from $Z \subsetneq \prod_{i=k+1}^{n} A_{\sigma(i)}$, and, conversely, every concatenation of such tuples represents some element of $X_\sigma$.  (If $k = 0$, then $Z = X_\sigma$; i.e. the factorization is a trivial one.)

I am primarily interested in factorizations for which the factor $\prod_{i=1}^{k} A_{\sigma(i)}$ has maximal cardinality, over all possible choices of $\sigma$ and $k$.  I am also interested in factorizations for which $k$ is maximal, over all possible choices of $\sigma$.  [Edit: both criteria actually lead to the same result; see Tsuyoshi Ito's answer.]

[(This bracketed paragraph is intended by way of background; it is tangential to the questions of this post.  Please disregard it if it is not useful or clear.)  One area where this problem arises is in the theory of databases and OLAP: given a facts table $X$ with $n$ dimension (aka "metadata") columns, how can it be "most efficiently" converted to a collection of perfectly dense (i.e. no empty cells) multidimensional data "(hyper)cubes" having identical domains.  (These domains correspond to the sets $A_{\sigma(1)},...,A_{\sigma(k)}$ above.)  This formulation leaves the optimization criterion fuzzy.  I use the term "efficient" here to describe solutions that pack "as much information as possible" in the regular hypercubes, but even with this clarification the criterion is ill-defined, because "most information" could be defined as "the greatest number of cells" or "the greatest number of dimensions" (i.e. potential explanatory factors) for the regular hypercubes.  These correspond to the two classes of factorizations I described in the previous paragraph.]

I'm looking for keywords I may use to search for algorithms to compute such maximal factorizations, given some concrete set of $n$-tuples $X$.  Do such factorizations, or the problem of computing them, have a name?  Are their complexity classes known?  Any pointers to the relevant literature would be appreciated!

~kj

If I understand the question correctly, the problem is easy (once we understand the problem).

As I understand it, you are given a finite set X⊆A1×…×An and want to find the “best” set I⊆{1,…,n} of indices that is feasible, where we say that a set I is feasible when X can be written as the direct product of the sets Ai for i∈I and some set of (n−|I|)-tuples (where indices are permuted appropriately).

You consider two formulations of the meaning of “best”: (1) the product ∏i∈I |Ai| is maximized, (2) the size |I| is maximized.  However, it does not matter which criterion you use because both can be maximized at the same time.

For each i=1,…,n, test whether the singleton set {i} is feasible (this can be done efficiently).  Let J be the set of indices i such that {i} is feasible.  It is easy to see that J is also feasible, and moreover J is the maximum with respect to inclusion among the feasible sets of indices.  Therefore, the index set J maximizes both criteria (1) and (2) stated above.


Are Alice and Bob allowed to copy qubits in quantum communication complexity model? In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the $\Omega(n)$ lower bounds of parity.

What happens if we assume that Alice and Bob can do something a quantum algorithm cannot do? One particular ability that I'm interested in is when they can copy qubits, i.e., Alice can send Bob a copy of her qubits and also keep a copy of that qubit sent to Bob. Do the lower bounds still hold in this model?

A particular result that I'm interested in is the lower bound in Razborov's paper "Quantum communication complexity of symmetric predicates".

Also, is this ability already included in the formal definition, e.g., as defined in Razborov's paper?

(As you can guess, my understanding in quantum algorithm is very limited. So, besides the full answers, I would appreciate any pointer to anything in the literature as well.)

Update: I realized after reading Artem Kaznatcheev's answer that the model I ask is too general so I　asked a new question here

Let me add to Artem’s nice explanation a pedantic point about your wording “something a quantum algorithm cannot do.”

In the usual setting of communication complexity, each party is allowed to perform any local operations, regardless of whether it is computable or not.  This is true in both classical and quantum cases.  In this sense, each party is indeed allowed to do something a quantum algorithm cannot do.  However, Alice and Bob are still constrained by the law of physics, and cloning is disallowed because of this.  In short, cloning is disallowed not because there is no quantum algorithm for it, but because it is ruled out by the law of physics.


Recovery of preimage of hash function given part of it Suppose $m = m_1 \| m_2$ (concatenation, with $|m_1| = |m_2|$) and $h(m) = s$ (hash). Is it possible to recover the whole preimage $m$ in feasible time with non-negligible probability given $m_1$ (or $m_2$) and $s$? Is there such a guarantee that this can't be done theoretically or provided by concrete schemes such as SHA1/SHA256/SHA512, etc.?

You don't specify how long $m_1$ and $m_2$ are. If $|m_1| = |m_2| > s$, then there is no way to recover $m$ given $s=h(m)$ (or $m_1$ given $m_2$ and $s=h(m_1\|m_2$) simply because there are exponentially many solutions to the equation $h(X)=s$ (resp., $h(X \| m_2) = s$).

Or are you asking to find any solution, not necessarily the original one? Even in this case, the above property (namely, existence of multiple solutions) can be used to show that solving either of the stated problems is hard if $h$ is collision resistant. In fact, this remains true even if $|m_1|=|m_2|=s$.


Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$ It is known that some (non-relativized) syntactic complexity classes between ${\bf P}$ and ${\bf PSPACE}$ have the following property, ${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P} \subseteq {\bf PP} \subseteq {\bf PSPACE}$. I am wondering if there exists a (non-relativized) syntactic complexity class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$? What are the implications of existence or non-existence of complexity class ${\bf X}$ ?

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

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

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


Shortest number of editing move between two words I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes are

add a letter at one of the extremities (for example, AB -> ABC),
duplicate and concatenate the whole word (for example, ABC -> ABCABC),
cut a word in two (the dual of the duplication move, ABCABC -> ABC + ABC),
delete one of the letters (for example, ABC -> AC), and
repeat one of the letters (for example, ABC -> ABBC).

For example, a minimal sequence of moves from ABC to BCBC is ABC -> BC (delete A) -> BCBC (duplication).

I don't have a background in computer science. Perhaps this is a well-known problem, but my Google search gave me nothing.

Do you know some related, well-defined problem?

Edit: As suggested in the answer by Anthony Labarre, I read some papers about the poset permutation/arrangement problem which is similar to the problem described above. Does anyone know more about this problem? Is this relevant?

I don't know whether this exact problem has been studied, but  Chaudhuri et al. studied the related tandem duplication-random loss problem: you are given a permutation, and you want to transform it into the identity permutation by
 (1)  duplicating a segment of any length and appending the copy right after the original, then (2) deleting elements so that you obtain a new permutation instead of a string. Note that applying (1) then (2) accounts for one operation.

Different variants can be defined according to the weight given to each operation, which in their paper depends on the width of the duplicated segments.
They also study a similar problem with the whole genome duplication, which is exactly the kind of duplication you allow. I don't remember reading about work on this problem in the context of strings, but I hope this can at least give you a starting point for your searches.


Implications of a recent negative result to geometric complexity A paper was posted in arxiv http://arxiv.org/pdf/1512.03798.pdf titled 'Rectangular Kronecker coefficients and plethysms in geometric
complexity theory' by Christian Ikenmeyer and Greta Panova with first line in abstract stating 'We prove that in the geometric complexity theory program the vanishing of rectangular Kronecker coefficients cannot be used to prove superpolynomial determinantal complexity lower bounds for the permanent polynomial'.

If correct what is the implication of this result to the geometric complexity theory program for separating permanent from determinant?

It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an inequality that rules out an inclusion of complexity classes, and/or (b) seriously consider multiplicities in the coordinate ring of the orbit closure of the determinant, and not merely use those on the orbit of the determinant as an upper bound. In using (a), one might at least still hope for a significant difference in the magnitude of the multiplicities, rather than small differences in their exact values - this should make such differences easier to detect.

The possibilities to use both (a) and (b) have been known for several years, though perhaps not everyone agreed regarding their necessity. (I personally have always thought that at the very least we'd need to do (b); it is very nice that their paper actually proves this.)

(Both (a) and (b) are clearly spelled out in Section 5 of the paper, entitled "Consequences for geometric complexity theory." Although my answer duplicates the points from the paper, I am posting it here both to give what I think is needed for a complete answer, and to assert that I agree with the authors that these are the ways forward.)


Why spectral norms are used for computing the complexity of adiabatic Hamiltonian? In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum computation. He showed that $$\Delta || H_P - H_B || << 1 $$. Later on van Dam et. al. also used spectral norm of Hamiltonian for computing the complexity. Daniel Nagaj also commented in chapter 2 of his PhD thesis that

  It is thus usual to think the required resources of an AQC algorithm as $T.||H|| ...$

Why do we need spectral norm for computing adiabatic Hamiltonian complexity? Why can't we just express it in terms of the eigenvalue of $\tilde{H}(S)$?

The spectral norm $||H||$ determines the maximum energy involved in driving the evolution of the quantum system and thus the quantum computation. Any quantum evolution could be sped-up by a factor of $\lambda$ by simply driving the system with Hamiltonian $\lambda H$ as a simple consequence of Schrödinger's equation. The energy involved is simply another physical resource invested into solving the problem, that needs to be considered in complexity considerations, besides time. For example, if your Hamiltonian has a tiny spectral gap, you could of course enlarge it by simply rescaling the strengths of all interactions in your system until the gap is large enough in absolute terms. Of course, after having solved the engineering challenges involved, this will linearly accelerate your computationion, similar to overclocking your classical PC. But the speed gained was only achieved by investing another resource that needs to be kept track of.


Approximation algorithms used in exact algorithms Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms.

However, constant factors are ignored in time complexity.

So I wonder if the following trick is possible or was used, to solve some problem $B \circ A$:

Use an approximation algorithm solving problem $A$ to get solution $S$ within constant factor;
Use an exact algorithm, solving problem $B$, whose runtime depends on weight of $S$ but works as long as $S$ is a correct solution.

This way the approximation is a "subprocedure" of an exact algorithm, and the constant factor lost in step 1 is swallowed in step 2.

An example from the parameterized complexity is a kernelization for the vertex cover problem using a theorem of Nemhauser and Trotter.

In the minimum vertex cover problem, we are given an undirected graph G, and we need to find a vertex cover of G of minimum size.  A vertex cover of an undirected graph is a vertex subset that touches all edges.

Here is an exact algorithm that uses an approximation at the first phase.

Phase 1: Set up the integer linear programming formulation of the minimum vertex cover problem.  It's known (or easy to show) that a basic optimal solution of the linear programming relaxation is half-integral (i.e., every coordinate is either 0, 1, or 1/2).  Such a basic optimal solution can be found by a usual polynomial-time algorithm for linear programming (or in this special case, we can formulate it as a network flow problem, so we can solve it combinatorially in polynomial time).  Having such a basic optimal solution, we round it up to obtain a feasible solution to the original integer linear programming problem.  Let S be the corresponding vertex subset.  It's good to note that S is a 2-approximation of the given minimum vertex cover instance.

Phase 2: Find a minimum vertex cover in the subgraph induced by S (for example by an exhaustive search).  A theorem by Nemhauser and Trotter states that this subgraph contains an optimal solution of the original input graph.  So, the correctness of this approach follows.

You may consult a book by Niedermeier on fixed-parameter algorithms for this algorithm.


Why is plus-comm a b $:\equiv$ refl (plus a b) not a proof of the commutativity of addition? I've been curious about the 'geometric situation' that one has when considering the type
$\prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ m\ n)$.
Here, addition is defined in the usual inductive way.
This proposition has an informative proof, which I will denote by $\textrm{plus-comm}$. One interesting property that I've observed of this proof is that it computes to reflexivity on any specific $\textrm{Nat}$ values. I conjecture that this should be true of all terms of this type in my system.
That is, if $a$ and $b$ are $\textrm{Nat}$ values, then $(\textrm{plus-comm}\ a\ b) \equiv \textrm{refl}\ (\textrm{plus}\ a\ b)$. For instance, this says that answering the question 'Why is 2+3 = 3+2?' with 'Because the commutative law of addition holds' reduces to 'Because both equal 5'. (In reference to a passage by Morris Klein. :P)
We have a term
$$\lambda n, m. \textrm{refl}\ (\textrm{plus}\ n\ m) : \prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m).$$
If we could show that the type $ \prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m)$ equaled the type $\prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ m\ n)$, then this term yields* a valid proof of commutativity, which is something that I proximally find highly intuitively unappealing.
Now, I can't seem to prove the equality stated above from commutativity, and I imagine that there is a good reason for why this is impossible.
* I am assuming extensionality and univalence. Thus, an equality of said types would yield an equivalence by which I could map the reflexivity term. However, the types in question shouldn't have any non-trivial higher groupoid structure, so I don't imagine that HoTT operations would perform any non-trivial computations (such as identifying these two proofs) in this setting. If the resolution of this question involves HoTT ideas, then I would be very intrigued.
What is going on in this situation?
TL;DR: We have that:
$$n, m:\textrm{Nat} \vdash (\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m).$$
Why does it not follow that:
$$\vdash \left(\prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m)\right) = \left(\prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ m\ n)\right)?$$

But it does follow. The types
$$A = \prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m)$$
and
$$B = \prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ m\ n)$$
are both contractible. Indeed, they are both inhabited and because $\mathrm{Nat}$ is a set, its identity type is a proposition, hence so are $A$ and $B$, as they are products of propoitions. An inhabited proposition is contractible.
Any two contractible types are equivalent, $A \simeq B$, thus by univalence also propositionally equal (as elements of a universe), $A = B$. However, $A$ and $B$ are not judgementally equal.
Consequently, the term $t = \lambda n, m \,.\, \mathrm{refl} (\mathrm{plus}\,n\,m)$ has type $A$ but it does not have type $B$. We can however transport $t$ along an equivalence $e : A \to B$ to obtain a term $e\,t : B$.


What is the relation of HOL Light type theory and some of the intuitionistic type theories? I'm trying to understand how HOL Light deductive rules relate to mainstream intuitionistic type theories.
Here is a sample of questions that come to my mind.

Does HOL Light derivations admit cut-elimination and what sub-formula property would mean? Is there some kind of canonicity result?

Can HOL equality be modeled with Identity types (with J axiom)?

Somewhat specific question: DEDUCT_ANTISYM_RULE axiom allows us to deduce that if you have  (entilement) both $q \vdash p$ and $p \vdash q$, we can deduce $\vdash p=q$. How can we assert that rule without a condition that the entailments are "each other inverses forming an isomorphism"?

I realize that many of these question might be wrong questions to ask. Perhaps I even am wrong to focus on the deduction rules?
How should I be thinking when comparing theories such as HOL Light and some intuitionistic type theories?

HOL is a simple type theory, while Martin-Löf's is a dependent type theory. That is the fundamental difference between the two.

One can embed HOL into extensional type theory, i.e., type theory with identity types and the equality reflection principle
$$\frac{\vdash p : \mathrm{Id}_A(s,t)}{\vdash s \equiv_A t}$$
You could try a less drastic principle, such as Streicher's $K$ axiom or uniqueness of identity proofs, in which case you will be interested in conservativity of intensional type theory with $K$ over extensional type theory. But perhaps you don't want to dig into such details right now.


canonical complete problems for $\Delta^P_n$ Finding whether or not a QBF can be satisfied is a canonical complete problem for both $\Sigma^P_n$ (start from $\exists$) and $\Pi^P_n$ (start from $\forall$). What is the canonical complete problem for $\Delta^P_n$?

(This is a slightly more detailed version of my earlier comment, in response to the asker’s request by email.)
Since $\Delta_k^{\rm P} = {\rm P}^{\Sigma_{k-1}^{\rm P}}$ by definition, it should be clear that the following problem is $\Delta_k^{\rm P}$-complete: fix some $\Sigma_{k-1}^{\rm P}$-complete problem L.  (For example, L can be the special case of QBF where there are k−1 groups of consecutive quantifiers of the same kind and the first quantifier is existential (∃).)  Then given a Turing machine M with the L oracle, a string x and a tally string 1t, decide whether M accepts the input x in time at most t.  (A tally string simply means a string on the unary alphabet, that is, a string of the form 1n.)
I would not mind calling this problem a “canonical” $\Delta_k^{\rm P}$-complete problem, but this may not be what you are looking for.
In my earlier comment, I removed the input string x and assumed it was always the empty string.  This variant is also $\Delta_k^{\rm P}$-complete because you can hardwire the input string into a Turing machine.


Minimum cut through vertices/nodes - not edges we all know and love s-t minimum cut algorithms, but they all cut through the edges in the graph. Are there any variants that cuts through nodes?

You are looking for Minimum Vertex K-cut. Also, if you search for k-node-connectivity you will get papers related to the structural properties of such cuts.


How to solve the Shortest Hamiltonian Path problem on Sparse Graphs? Problem: Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once.

For a subset $S$ of nodes and a node $i\in S$, let $D[S][i]$ denote the length of the shortest path within $S$ that ends at $i$.

A common solution to the SHP problem is using dynamic programming for computing $D[S][i]$ for all subsets $S$ and all nodes $i$. If $n$ is the number of nodes then the time and memory complexities of this solution are respectively $\mathcal{O}(2^nn^2)$ and $\mathcal{O}(2^nn)$, which is not feasible for large graphs (having $100$ nodes for example).

However, if the graph is very sparse (e.g. a node has only a few neighbors), then one would expect these complexities to drop significantly would expect the above solution to be practical. I would appreciate a lot if somebody can give me some insights on how to solve/implement the SHP for very sparse graphs. I am looking for practical algorithms/implementations that do not necessarily have lower theoretical complexities and if they can also check if a Hamiltonian path exists before finding the shortest one (and still remaining practical), then that would be great.

Thank you in advance for your help!

Indeed: Eppstein has shown that the TSP can be solved in time $O(1.26^n)$ if all vertices are of degree at most 3.

  David Eppstein:
  The Traveling Salesman Problem for Cubic Graphs.
  J. Graph Algorithms Appl. 11(1): 61-81 (2007)

Some tiny improvements of this result are also known, for instance by Liśkiewicz and Schuster (2014) to $O(1.255^n)$.


Extension to the Stable Marriage Problem ? This may sound more like a social sciences question more than a TCS one, but it is not. When reading "Randomized Algorithms" which describes the Stable Marriage Problem, one can read the following (p54)

" It can be shown that for every choice of preference lists there exist at least one stable marriage. (Curiously enough, this is not the case in a homosexual monogamous society with even number of inhabitants)...."

Are there any very simple extensions of the Stable Marriage Problem that allows some type of steady state that includes a homosexual monogamous society, or a society in which a certain subset of the population follow a different set of rules than the larger set ?

In the affirmative, are there algorithms that perform such a matching ?

There is an open conjecture regarding 3 types of people. Suppose you have men women and dogs so that men have preference lists on women, women have preference lists on dogs, and dogs have preference lists on man. Is there always a stable marriage?

(For other preference structures on 3-types society the answers are known to be negative).

Another comment is that stable marriage represent a non empty core and there is a well known condition by Scarf that implies the existence of nonempty core. It is known that Scarf conditions are satisfied for the original stable marriage problemand for the house allocation problem. (But failed for the men/women/dogs problem).

Some references:

A reference to Scarf's paper: H.E. Scarf, The core of an $N$ person game, Econometrica 35 (1967) 50--69.
A paper showing various applications for Scarf's crucial lemma and quote quite a few others: (In particular, a fractional version of Gale-Shapley theorem for hypergraphs by Aharoni and Holzman is described): R. Aharoni, and T. Fleiner, On a lemma of Scarf, J. Combin. Theory Ser. B 87 (2003), 72--80.
A solution of the men-women-dogs problem when there are at most 4 of each gender appears in a paper by Eriksson et al (Math Soc Sci 2006).


Find items that are in at least $k$ of $n$ sets Consider $n$ sets of values (represented as sorted arrays with no duplicates, and with a known size (ie. the size can be obtained in O(1)). The values can be tested for equality in O(1) time. I want to obtain the set of values that are present in at least $k$ different sets among the $n$.

The obvious algorithm to do this is to go through all the sets, count the number of occurrences of each value, and return those with a count higher than $k$. Yet, in some cases, you can do better: for instance, when $n = k = 2$ and when one set $S_1$ is much smaller than the other set $S_2$, it is more efficient to look at all items of $S_1$ and perform a binary search for each of them in $S_2$: the binary search approach costs $O(|S_1| \log(|S_2|))$ whereas the naive approach costs $O(|S_1| + |S_2|)$ which is worse when $|S_1| << |S_2|$.

With this in mind, in which situations can we do better than the naive algorithm? (If this is a well-known problem, I would be happy to know its usual name and have references.)

OK, I think I found something relevant: this paper mentions a "T-occurrence problem" in section III (p. 2) which is exactly our problem (where $T$ is what we called $k$), hidden behind some domain-specific jargon. The ScanCount algorithm that they propose is the naive approach I suggested in my question. The MergeOpt algorithm is a generalization of the binary search trick. Their main proposal (DivideSkip) is a combination of this binary search trick and a different trick (MergeSkip) to skip multiple values. It even seems that experimentally the clever approaches are much better than the naive approaches (look at the "No filters" column in page 8, the filters are heuristics for their domain-specific stuff).

This can be combined with David Eppstein's trick to make multiple binary searches in $S_2$ more efficient, and with the idea of using interpolation search instead of binary search (an idea from this other paper from the same field).


Polynomial-time reductions between undecidable languages The Turing degree $\mathbf{0}'$ is defined as
all languages Turing-equivalent to the halting problem.
In fact any recursively enumerable language is
polynomial-time reducible to the halting problem.

My question is, are all languages with Turing degree $\mathbf{0}'$ Turing-reducible to each other in polynomial time?
If not, can the fastest reduction between two $\mathbf{0}'$ languages get arbitrarily slow, and
are there known subsets of $\mathbf{0}'$ that are polynomial-time reducible to each other?

Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a careful analysis of the running time would show that it is indeed a polynomial time reduction.

Not every such reduction is polynomial time, however. You can observe that a reduction from the Halting problem $\langle i \mid TM_i \text{ halts on input } i\rangle$ to the unary language $\langle 1^i \mid TM_i \text{ halts on input } i\rangle$ has exponential blowup in instance size.


Maximum difference between two shortest paths My problem is the following maximization problem:

Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two targets $v$ and $w$.

Problem: Compute
$$ \max\{ c_p - c_q | p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path}, c \in [l,u] \} $$
with $c_p$ and $c_q$ being the costs of path $p$ and $q$, respectivly.

I cannot image that that this problem has not been studied, but i cannot find anything. Does someone know the name of this problem and any resources.

Thanks in advance.

The problem can also be formulated as the following bilevel program:

$$ \max ~~~~~~~~~~~~~ c^Tx - c^Ty ~~~~~~~~~~~~~~~~~~~\\
s.t. x \in \arg\min \{ c^Tx| Mx=b^{s,w} \}, \\
~~~~~~~  y \in \arg\min\{ c^Ty | My=b^{s,v} \},  \\
 l \leq c \leq u  $$

with $M$ being the vertex-edge incidence matrix of the graph and $b^{s,v},b^{s,w} \in \{0,1\}^V$ defined as follows: , $b_s^{s,v} = b_s^{s,w} = 1$, $b_v^{s,v} = b_w^{s,w} = -1$, and $0$ otherwise.

There exists an optimal solution $p,q,c$ such that $c_e = l_e$ for all edges $e$ in the path $q$ and $c_e = u_e$ otherwise.
For the optimal solution from point 1 exists a vertex $x$ at which the paths $p$ and $q$ split. The subpath $p^x$ of $p$ from $x$ to $v$ is a shortest path from $x$ to $v$ for the edge weights $u$ (the upper bound).

To solve the problem consider the following procedure:

For all $x \in V$:

Compute the length of the shortest path from any vertex $y \in V$ to $w$ for the edge weights $u$. The lengths are stored in $d \in \mathbb{N}^V$.
Define the node potentials $\pi_y = d_x - d_y$.
Compute the shortest path from $x$ to $v$ that respects the node potentials $\pi$, i.e. choose the edge weights such that the shortest path to $v$ with respect to $c$ is greater or equal to $\pi_y$ for all $y \in V$. This can be done by a modified Dijkstra algorithm. The Dijkstra algorithm normally takes fixed edge weights $c$. We choose the edge weights as follows: $\min\{ c \in [l_e,u_e] \mid \pi_w \leq d(u) + c \}$. Furthermore, make sure to take the shortest path that only uses edges with edge weights at their lower bound if possible.
If the above procedure finds a shortest path from $x$ to $v$ that only uses edges with edge weights at their lower bound, then $x$ might be a splitting point from point 2. Remember that $x$ as well as the resulting edge costs $c^x$

For all the remembered pairs of vertices $x$ and corresponding edge costs $c^x$, compute the shortest path to $x$, simillar to the shortest path from $x$ to $v$. Now change $c_e^x$ to $l_e$ for all edges in that shortest path. The solution to problem is now given by
$$ \max_{x}\{c_p^x - c_q^x \mid p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path} \}. ~~~~~~~ (1)$$

Illustration of correctness:

Let $\mathcal{D}$ be the domain of the original problem and $p,q,c^x$ the solution of (1), then we have $(p,q,c^x) \in \mathcal{D}$. Hence, the solution of (1) is smaller or equal to the solution of the original problem.

Now let $(p,q,c)$ be the solution of the original problem and let $x$ be the splitting point of the two paths $p$ and $q$. The described procedure considers $x$ and computes the shortest path to $v$, which is exactly $p(x \rightarrow v)$, such that the shortest path $\rho$ to $w$ is the shortest path with respect to the edge weights at their upper bound $u$. We therefore get:
$$ c_p - c_q = c_{p(s \rightarrow x)}  + c_{p(x \rightarrow w)} -  c_{q(s \rightarrow x)}  + c_{q(x \rightarrow v)} \\
= c_{p(x \rightarrow w)} - c_{q(x \rightarrow v)} \leq c_{p(x \rightarrow w)} - c_{\gamma}. $$
Hence, the solution of (1) is greater or equal to the solution of the original problem.

To prove the correctness of the modified Dijkstra algorithm, one can modify the original proof.


Set partitioning algorithm I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem.

I have some finite set $ U $ of some distinct elements $ e_i \in U $.

I have some subsets $ A_i \subset U $, where $ i \in \{1, 2, \cdots, N\} $.

I have an array of integers $ <k_1, k_2, \cdots, k_N > $. Each integer $ k_i \leq |A_i| $ and $$ \sum_{i \in \{1, 2, \cdots, N\}} k_i \leq | \cup_{i \in \{1, 2, \cdots, N\}} A_i | $$.

I want to find sets $ B_i $, where $ i \in \{1, 2, \cdots, N\} $, such that $ |B_i| = k_i $ and $$ \forall i \in \{1, 2, \cdots, N\} .  B_i \subset A_i $$ and $$ \forall i, j \in \{1, 2, \cdots, N\} . B_i \cap B_j = \emptyset $$

The choice of actual $ B_i $ doesn't matter at all.

I'd like to find is it possible at all. It seems to me that it is, since it's obviously possible for not intersecting $ A_i $, and if they intersects we can reduce the problem to not intersecting $ A'_i $
I'd like to find fast algorithm that will not-deterministically choose any $ B_i $. I'd like to find the complexity of the problem. It seems that there should be some fast algorithm and problem doesn't seem similar to NP-hard problems, but I somehow feel that it can be NP-hard.

The actual environment is that there are around 50 000 000 elements in $ U $ and N is around 100.

Is it some known problem? Where can I read on the matter? Is there any fast algorithm? What is the best way to perform such partitioning in given environment.

The problem can be solved via the assignment problem/network flow. Create a bipartite graph with the left side consisting of $N$ vertices $a_1,\ldots,a_N$ corresponding to the sets $A_1,\ldots,A_n$. The right side has $m$ vertices $u_1,\ldots,u_m$ one for each element in $U$. Connect $a_i$ via directed arcs of capacity $1$ to each element vertex that $A_i$ contains. Now add a source vertex $s$ and connect it via an arc of capacity $k_i$ to $a_i$. Connect each $u_j$ to a sink vertex $t$ with an arc capacity of $1$. The problem has a solution if and only if there is an $s$-$f$ flow of value $\sum_i k_i$ in this network. An integral flow would give you a desired solution.


Reference for checking primitive recursiveness There is a theorem that states a function $f$ can be computed with a Turing-machine in time $O(g)$ with primitive recursive $g$ (of the length of input) iff $f$ is primitive recursive.

Where can I find a reference for this theorem? Wikipedia seems to state it but gives no references, nor does my books.

This is known as a Ritchie-Cobham property, or a honesty property of primitive-recursive functions.  See for instance Theorem VIII.8.8, page 297 in P.G. Odifreddi, Classical Recursion Theory, vol. 2, 1999.

Odifreddi refers to

Kleene, General recursive functions of natural numbers, Math. Ann. 112:727--742, 1936,
Cobham, The intrinsic computational difficulty of functions, Log. Meth. Phil. Sci. 2:24--20, 1964,
Meyer, Depth of nesting and the Grzegorczyk hierarchy, Not. Am. Math. Soc. 12, 1965.


Additive combinatorics applications in algorithm design I'm reading surveys by Trevisan and Lovett on applications of additive combinatoric in TCS. The majority of these applications fall under computational complexity, e.g., lower bounds. I wonder if additive combinatorics has found applications in algorithm design too.

The motivation for my question is the following: while the connection between additive combinatorics and complexity seems somewhat natural, I'm curious to see how algebraic structure uncovered by additive combinatorics might be exploited in designing efficient algorithms, if any. Pointers to literature would be appreciated.

Timothy Chan and Moshe Lewenstein have a paper on 3SUM and related problems in the upcoming STOC, which applies an effective version of the BSG theorem from additive combinatorics to solve variants of 3SUM faster than n^2 time.

See this link to Chan's papers.


What algorithms are known for computing Craig interpolants? Is there any survey of algorithms for computing interpolants? What about papers on only one algorithm? The case I'm most interested in is $A=\lnot p\land q$ and $C=q$, plus the constraint that the interpolant is as small as possible. (I know of McMillan's paper from 2005, which describes how to get interpolants, while avoiding quantifiers.)

Background: Craig's interpolation theorem (1957) says that if $\vdash_{T_A\cup T_C}A\to C$, where $A$ is a (fol) formula in $T_A$ and $C$ is a formula of $T_C$, then there is a formula $B$ such that $\vdash_{T_A}A\to B$ and $\vdash_{T_C}B\to C$. Formula $B$ is a Craig interpolant of $A$ and $C$ (or, in alternative definitions, of $A$ and $\lnot C$). A trivial interpolant of $\lnot p\land q$ and $q$ is $q$, but I want a small interpolant, for some reasonable definition of 'small' (such as syntactic size). (Interpolants have many uses and, in case you are curious, here's one.)

Motivation: This would be useful in (very) incremental program verification via verification condition generation.

Take a look at the Phd thesis of Himanshu Jain, Verification Using Satisfiability Checking, Predicate Abstraction, and Craig Interpolation.  He considers the performance of several fundamental techniques with an eye to applications in verification, and has a chapter on interpolation of formulae involving linear equations and Diophantines.

He takes a particular look at what I know as Bibel's connection method, and which he calls General Matings. These are graph-based, rather than formula-inference -based approaches to satisfiability.  If you are interested in them generally, let me recommend Dominic Hughes' reasonably short (11 pages) Proofs without syntax.


Check if graph stays connected after edge swap Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after repeated modifications, specifically: repeated edge swaps. An edge swap removes two edges $\{a - b, c-d\}$ and adds $\{a-c, b-d\}$ instead.  Is there a way to do better than a full linear-time check after each and every modification?

Check this paper https://arxiv.org/pdf/1209.5608.pdf which uses cluster forest which support operations like:

connected(u, v) : if vertex u and v are connected ,
insert(u, v) : Insert edge (u, v)
delete(u, v) : delete edge (u, v)

It answers your query in O(log n / log log n) time with O(log2n / log log n) update time.


Problem teaching computability I have difficulty teaching the concept of computable functions. I tried to develop the idea of why researchers like Hilbert/Ackermann/Godel/Turing/Church/... invented the notion of 'computability'. The students immediately asked: "what does computability mean?" and I can't answer unless I teach them Turing machines, and then answer "a function is computable if a Turing machine computes it."

So,

  Is there a description of computability which does not require resorting to Turing machines, λ-calculus, or similar models of computation? Even an intuitive description will suffice.

75 years ago there were no computers around. So one had to explain very carefully the mathematical idea of a computer.

Today everybody knows what a computer is, and is probably carrying one around most of the time. This can be used very successfully in teaching because you can skip the rather outdated idea of a machine with a tape. I mean, who uses a tape? (I know, I know, you feel insulted and Turing was a great man and all that, and I agree with you).

You just walk into the class and ask: so it there anything your iPhones can't compute? This immediately gets you into questions about bounded resources. Then you say: well suppose your machine actually had unlimited memory, is there anything it couldn't compute? And you idealize a bit more and limit attention to number-theoretic functions (because you are not interested in Facebook at the moment). You'll have to explain a bit how computers work (as mentioned in the comments, it's good if the students know a programming language because you can use that instead of describing hardware), but after that you can use all the classical arguments of computability theory to derive results. It doesn't matter that your students' mental picture of a machine is iPhone. In fact, it matters: it makes it easier and more relevant for them to know that their iPhone can't do certain things.


Rapidly mixing Markov chains on 3-colorings of a cycle The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a 5-cycle: there are 30 3-colorings, but only 15 of them can be reached by single-vertex recoloring steps. More generally, it can be shown not to mix for 3-colorings of an n-cycle unless n=4.

The Kempe chain or Wang-Swendsen-Kotecký dynamics is only a little more complicated: at each step one chooses a random vertex v and a random color c, but then one finds the subgraph induced by two of the colors (c and the color of v) and swaps these colors within the component containing v. It is not hard to see that, unlike the Glauber dynamics, all 3-colorings of a cycle can be reached.

Is the Wang-Swendsen-Kotecký dynamics rapidly mixing on 3-colorings of an n-vertex cycle graph?

I know of the results e.g. by Molloy (STOC 2002) that Glauber is rapidly mixing when the number of colors is at least 1.489 times the degree (true here) and the graph to be colored has high girth (also true), but they also require that the degree be at least logarithmic in the size of the graph (not true for cycle graphs), so they don't seem to apply.

I got the following solution by email from Dana Randall, so any credit for the solution should go to her (which I guess means: don't upvote this answer) and any bugs were likely introduced by me.

The short version of Dana's solution is: instead of using the Markov chain I described, in which potentially-large two-colored regions are recolored, use a "heat bath" in which we repeatedly remove the colors of two vertices and then choose a valid coloring for them at random. It's not hard to show that, if this chain mixes, then the other one does as well. But a standard path coupling argument turns out to work to show that the heat bath does indeed mix.

The long version is too long to include here, so I put it in a blog post instead.


Distinguishing between two coins It is well known that the complexity of distinguishing an $\epsilon$ biased coin from a fair one is $\theta(\epsilon^{-2})$. Are there results for distinguishing a $p$ coin from a $p+\epsilon$ coin? I can see that for the special case of $p=0$, the complexity will be $\epsilon^{-1}$. I have a hunch that the complexity will depend on whether $p$ is of the order of $\epsilon$, but can't prove so rigorously. Any hints/references?

I suggest you use the framework found in the following paper:

How Far Can We Go Beyond Linear Cryptanalysis?, Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.

The crucial result says that you need $n \sim 1/D(D_0 \,||\, D_1)$, where $D(D_0 \,||\, D_1)$ is the Kullback-Leibler distance between the two distributions $D_0$ and $D_1$.  Expanding out the definition of the K-L distance, we see that in your case

$$D(D_0 \,||\, D_1) = p \log \frac{p}{p+\epsilon} + (1-p) \log \frac{1-p}{1-p-\epsilon},$$

with the convention that $0 \log \frac0p = 0$.

When $p \gg \epsilon$, we find $D(D_0 \,||\, D_1) \approx \epsilon^2/(p(1-p))$.  Thus, when $p \gg \epsilon$, we find that you need $n \sim p(1-p)/\epsilon^2$ coin flips.  When $p = 0$, we find $D(D_0 \,||\, D_1) = -\log(1-\epsilon) \approx \epsilon$, so you need $n \sim 1/\epsilon$ coin flips.  Thus, this formula is consistent with the special cases you already know about... but it generalizes to all $n,\epsilon$.

For justification, see the paper.

When $p \gg \epsilon$, the justification is easy to work through by hand.  With $n$ observations, the number of heads is either $\text{Binomial}(n,p)$ or $\text{Binomial}(n,p+\epsilon)$, so you want to find the smallest $n$ such that these two distributions can be distinguished.

You can approximate both of these by a Gaussian with the right mean and variance, and then use standard results on the difficulty of distinguishing two Gaussians, and the answer should fall out.  The approximation is fine if $p \ge 5/n$ or so.

In particular, this comes down to distinguishing $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$ where $\mu_0 = pn$, $\mu_1 = p+\epsilon)n$, $\sigma_0^2 = p(1-p)n$, $\sigma_1^2 = (p+\epsilon)(1-p-\epsilon)n$.  You'll find that the probability of error in the optimal distinguisher is $\text{erfc}(z)$ where $z = (\mu_1-\mu_0)/(\sigma_0+\sigma_1) \approx \epsilon \sqrt{n / 2p(1-p)}$.  Thus, we need $z \sim 1$ to distinguish with constant success probability.  This amounts to the condition that $n \sim 2p(1-p)/\epsilon^2$ (up to a constant factor)... when $p \gg \epsilon$.

For the general case... see the paper.


Current tightest bounds for critical 3-SAT density I'm interested in the critical 3-satisfiability (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or more, they are almost surely unsatisfiable.
(Here $\epsilon$ is any small constant and $n$ is the number of variables.)
If the number is $(\alpha - \epsilon) n$ or less, they are almost surely satisfiable.

The thesis Belief propagation algorithms for constraint satisfaction problems  by Elitza Nikolaeva Maneva challenges the problem from the angle of belief propagation known in information theory. On page 13, it says $3.52<\alpha<4.51$ if $\alpha$ exists.

What are the best known bounds for $\alpha$?

Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \epsilon$) and the unsatisfiability threshold ($\alpha + \epsilon$) as separate entities.

The unsatisfiability threshold is known to be at most 4.4898, a slight improvement since Maneva's 2001 thesis.

J. Díaz, L. Kirousis, D. Mitsche, X. Pérez-Gimenéz.  On the satisfiability threshold of formulas with three literals per clause, Theoretical Computer Science 410, 2009, 2920–2934. doi:10.1016/j.tcs.2009.02.020 (preprint from one of the authors)

The satisfiability threshold is known to be at least 3.52, which is unchanged from the time of Maneva's thesis.

A. C. Kaporis, L. M. Kirousis, E. G. Lalas.  The Probabilistic Analysis of a Greedy Satisfiability Algorithm, Random Structures and Algorithms 28, 2006, 444–480.  doi:10.1002/rsa.20104

These bounds were recently cited by Achlioptas and Menchaca-Mendez as the best known to date.

D. Achlioptas, R. Menchaca-Mendez.  Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method, ICALP 2012, LNCS 7391, 1–12.  doi:10.1007/978-3-642-31594-7_1


Randomized algorithms using a stack I have developed a new derandomization technique which is aimed at recursive randomized algorithms (or) more generally randomized algorithms that use a stack. Unfortunately, I could not find natural randomized algorithms to apply my techniques. Recursive Markov Chains and Stochastic grammars are very close to what I am looking for. Are there other (more natural) randomized algorithms that make "essential" use of stack ? Any help is greatly appreciated, since I am stuck with this for more than six months now.

To give you more context, I am looking for a list of problems similar to those in SivaKumar's Paper. Note that SivaKumar used Nisan's Pseudo-random generator to derandomize these problems.

How about Welzl's randomized algorithm for minimal enclosing ellipsoids? It has recursion depth O(d) where d is the dimension of the space.

I know next to nothing about derandomization, so this might not be what you're looking for. If my example doesn't qualify (maybe by your definition it only makes inessential use of recursion?), perhaps you could clarify why that is. That would increase the chances of higher quality, more pertinent answers from others.


Constraint satisfaction problem on a graph Consider the set $S = \{1, \dots, n\}$ and $n$ subsets $S_i \subseteq S$ of size $d$ each (think of $S_i$ as neighborhoods of vertex $i$ in some $d$-regular graph, although the graph structure is not important here). Each vertex can have label $0$ or $1$. Each set $S_i$ comes with 2 constraints: there can be at most $k_i$ zeroes in $S_i$ and at most $l_i$ ones in $S_i$ (assume that $k_i + l_i \geq d$, otherwise constraints are clearly inconsistent). The problem - is it possible to check in time $\mathrm{poly}(n)$ (with fixed $d$) whether this constraint problem is satisfiable by at least one labelling of vertices?

It smells like something NP-hard, but I don't see an obvious reduction e.g. from $d-SAT$ since it's not clear you can implement negation by only this type of constraints.

1 in 3 Sat reduces to this problem.
http://en.wikipedia.org/wiki/One-in-three_3SAT

Set d=3, each k_i = 2 and each l_i=1

To implement negation add $x,\overline{x},a$ and $x,\overline{x},b$ and $a,b,c$.
The only possible assignment is a=0,b=0 and c=1, so $x$ and $\overline{x}$ must be different.


How do conference proceedings add to academic prestige? I come from mathematics and, for whatever reason, am trying to publish in theoretical computer science. I'm still trying to understand the role of conference proceedings, and I have two specific question about them. I have tried to phrase the questions so that the analogous questions in mathematics would not be opinion based; if you think they are opinion based here then that is interesting in an of itself, so I would be grateful if you could comment to explain this!

In maths, a common marker of academic prestige is the specific journals someone's articles appear in, while I understand in TCS conference proceedings are more important.

  Are some conferences better thought of than others? If not, then how do conference proceedings add to prestige?

In maths, there are four un-disputed "top" journals (Acta Mathematica, Annals of Mathematics, Inventiones Mathematicae, Journal of the American Mathematical Society), and then there is a large second tier of world-class journals which is too large to mention here and varies wildly between different areas of mathematics. Getting a single paper in one of these four journals is a fast track to a permanent job.

  Are there a small number of top, world-class conferences where getting an article in the proceedings stands out like a gold star? If so, what are they?

Any suggestions for further reading is also appreciated :-)

I don't think there is any TCS conference that would be a fast track to a permanent job.

STOC, FOCS, and SODA are the most competitive conferences, and papers in those will certainly look very good in your CV, but just one paper won't help that much with the career. To really stand out, you will need something more than that (say, lots of papers in STOC, FOCS, and SODA).


Is finding an optimal solution to this Knapsack-like problem NP-hard? Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $ \sum_{i=1}^{n} p_i(1-x_i)+\alpha_i v_iw_ix_i$ such that $x_i \in \{0,1\}$ subject to:

$\sum_{i=1}^{n} \alpha_iw_ix_i\leq W$
$0 \leq \alpha _i \leq 1$
$\alpha_iv_iw_ix_i \geq p_i x_i $

In other words, we can sell any amount of whole objects at profit $p_i$, and some subset of object fractions whose weight does not exceed $W$ at price $v_i$ (but then we can't sell the remaining fractions of those objects).

Is this problem NP-hard?

(Credit for this question goes to the author of the reddit post at https://www.reddit.com/r/compsci/comments/4e7q9t/polynomialtime_algorithm_for_modified_knapsack/).

NOTE: My original reduction didn't work. Fixed now.

Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are proportional to the weights, so
$p_i = \beta w_i$ with $\beta < 1$.

Now, if there's a set of weights $S$ such that $\sum_{i\in S} w_i = W$, you can get a profit of
$$
\sum_{i \in S} w_i + \sum_{i \not\in S} p_i = W + \beta \left(\sum_i w_i -W\right) = (1-\beta)W + \beta \sum_i w_i,$$ which is optimal. If there's not such a set of weights, then we can't.


Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)? I'm following course material from the course Advanced Data Structures.

The result by Driscoll et al 1989 states the following (wording of the following theorem taken from lec notes, page 4, which cites the original paper "Making data structures persistent")

  Any pointer-machine data structure with O(1) pointers to any node can be made partially persistent with O(1) ammortized multiplicative overhead and O(1) space per change

I understand the argument for why reads are O(1). The key idea is that during a write to n when a new node n' is created due to mod table overflow, we guarantee existence of a mod entry pointing to n' in any node x which has a field pointing to n.

During a read, you can look at appropriate mod entry in x which will point to either n or n' depending on the version, so you only have to look at O(mod table size) entries at every read.

So in summary, the backpointer update guarantees efficient reads.

However, in my program I start out with a pointer to the head of the linked list in a variable. With backpointer updates, it'll always point to the latest version. Which means that if I have to look up an older version of the list, I'll have to go through all mod tables of the first node of the linked list till I arrive at the correct version, making it O(n) in number of versions and not O(1). Is that correct?

I think this is really a question about the API features. Access to an older version, in Driscoll et al.'s sense, requires a pointer to that version, not just a predicate used to traverse a version tree to locate the version.

For a similar API/modelling question, you can look at the question of how long delete takes in a priority queue. Plenty of papers advertise that they offer $O(1)$ delete, but this assumes one already has a pointer to the item to be deleted.


Creating HMAC keys using a fixed prefix and a random string In a system that uses HMAC for a number of different applications, it is important to use different keys for different applications.  Suppose:

there is just a single random string available (50 bytes long, in this case)
we are using HMAC-SHA1
we will shorten keys longer than the blocksize using SHA1 (as per RFC 2104)

Is it safe to generate unique keys by prefixing the application name to the secret, so that the key for application 1 ends up as SHA1("application1" + secret) and the key for application 2 ends up as SHA1("application2" + secret)? The strings "application1" and "application2" are not kept secret. Or does this open up significant weaknesses compared to using completely different secret keys for each application?

Thanks.

Let's put it more formally first. Let $s$, $t$ be strings known to the adversary, and $k$ be a secret key. Let $k_1$ and $k_2$ be the keys obtained as $k_1 = H(s|k)$ and $k_2 = H(t|k)$ respectively, where $H(\cdot)$ is a collision-resistant hash function, and $|$ denotes the concatenation. The question is,

  Is function $f_i(\cdot)=HMAC(\cdot, k_i)$ a MAC?

The answer is yes. I don't have a formal proof, yet the following reasoning seems just fine (see also this topic):
Given $s$ and $t$, and keeping $k$ secret, the adversary will be unable to deduce $k_1$ or $k_2$ with non-negligible probability. Lacking access to $k_i$, the key to HMAC, function $f_i$ will indeed act as a MAC.