Do combinatorial discrepancy upper bounds lead to smaller $\epsilon$-nets (as with $\epsilon$-samples)? An $\epsilon$-sample (or $\epsilon$-approximation) of a family of subsets $\mathcal{S}$ of a ground set $X$ is a subset $P \subseteq X$ which preserves relative sizes of sets up to $\epsilon$. I.e., for any $S \in \mathcal{S}$,

$$
\left| \frac{|S\cap X|}{|X|}  - \frac{|S \cap P|}{|P|} \right| < \epsilon
$$

The (combinatorial) discrepancy $\mathsf{disc}(\mathcal{S})$ of $\mathcal{S}$ on the other hand is the minimum of

$$
\max_{S \in \mathcal{S}} \left|\sum_{e \in S}{\chi(e)} \right|
$$

over all colorings $\chi:X \rightarrow \{\pm 1\}$. You can think of this as coloring $X$ with blue and red so that each set is as balanced as possible; the discrepancy is the imbalance of the most imbalanced set in the most balanced coloring.

Finally, an $\epsilon$-net is a set $P \subseteq X$ such that every set $S$ of size $|S| \geq \epsilon |X|$ has non-empty intersection with $P$.

There is a close relationship between combinatorial discrepancy and $\epsilon$-samples. More precisely, if $\mathsf{disc}(\mathcal{S})<\frac\epsilon2 |X|$, taking either the red or the blue colored points, whichever set is smaller, gives an $\epsilon$-sample of size at most $|X|/2$. This construction can be repeated recursively. Thus upper bounds on discrepancy imply better size vs. error tradeoffs for $\epsilon$-samples.

The question is if small discrepancy also implies better size vs error tradeoffs for $\epsilon$-nets.

For example for set systems with finite VC-dimention we have discrepancy bound $O(\sqrt{|X|\log |X|})$. We can construct an $\epsilon$-net of size $O(\frac1\epsilon\log\frac1\epsilon)$.
How much smaller $\epsilon$-nets can we get  from better bounds for discrepancy?

First, and more obviously, an $\epsilon$-sample is an $\epsilon$-net.

Of course, the above observation gives usually very loose bounds for $\epsilon$-nets. The bound you mention at the end of our post relies not just on small discrepancy but also on VC-dimension itself, so the relationship is not so clear. Let me elaborate.

Let $s(\epsilon)$ be the size of the minimum $\epsilon$-sample for your system. As you mention this can be bounded in terms of discrepancy.

We call a restriction of $\mathcal{S}$ to $Y$ the set system $\mathcal{S}|_Y = \{S \cap Y: S \in \mathcal{S}\}$. Finally, the shatter function $\pi(s)$ is equal to the maximum number of distinct sets in any restriction $\mathcal{S}|_Y$ to a set $Y$  of size at most $|Y| \leq s$.

We can show that there exist $\epsilon$-nets of size at most $O(\frac{1}{\epsilon} \log \pi(s(\epsilon/2)))$. This goes as follows.

any set system of $m$ sets has an $\epsilon$-net of size $O(\frac{1}{\epsilon} \log m)$;
an $\epsilon/2$ net of an $\epsilon/2$-sample for $\mathcal{S}$ is an $\epsilon$-net for $\mathcal{S}$;

Let us instantiate this for $\mathcal{S}$ of constant VC-dimension. For such $\mathcal{S}$, $s(\epsilon) \leq \epsilon^{-2}\log \epsilon^{-1}$. Also, by the Sauer-Shelah lemma, for constant VC dimension $\mathcal{S}$, $\pi(s) = s^{O(1)}$. Plugging this into the bound we got above gives $O(\frac{1}{\epsilon}\log \frac{1}{\epsilon})$ for the size of an $\epsilon$-net.

As you see, the bound on the size of $\epsilon$-nets depends on $\pi$ and not just on the discrepancy. I am not sure if there are any tighter connections. There is a bound on $\pi$ in terms of discrepancy, but the bound is exponential in the discrepancy, so it's not terribly useful.

Finally a note: for $\mathcal{S}$ with VC-dimension $d$ we can show there exist $\epsilon$-samples of size $O(\epsilon^{-\frac{2d}{d+1}})$. This is because the discrepancy of such set system is bounded by $n^{\frac12 - \frac1{2d}}$. The reason why most older references state the loose bound of $\sqrt{n\log n}$ is that until the very recent work of Nikhil Bansal, there were no known polynomial time algorithms for constructing such low discrepancy colorings. Even now, the algorithm giving the loose bound is just a random coloring, so it's very simple and very efficient, and the loose bound makes practically no difference if your end goal is an $\epsilon$-net.


Why use joint trees in Graphical Models? I am wondering why some methods transform the underlying DAG-based graphical model (Bayesian Networks for example) to a joint tree$^1$? What are the advantages?

I believe it's for computational purposes. If that's the case under what circumstances it is not recommended to transform the underlying DAG to jointtrees?

Speaking about graphical models in general (whether they are probabilistic or not), is there some guidelines when to transform them i.e. decompose them?

$^1$ Also known as jointree, junction tree, tree decomposition.

My only background on this subject is a course I took as a grad student, so take my answer with a grain of salt:

The reason that some methods transform the DAG to a tree because some algorithms work on trees but do not work on graphs with cycles. For example, belief propogation is guaranteed to converge on a tree after every node received two messages. On general graphs, on the other hand, no general convergence theorem is known, and we know that convergence occurs only in some special cases. Intuitively, the reason is that on a general graph, a message that goes through a cycle can loop in it indefinitely, each time changing the information stored at the nodes.

Regarding under what circumstances it is recommended to transform the graph into a tree: In the process of transforming the graph into a tree, every node of the new tree is identified with a set of nodes of the original graph. The size of the maximal set with which a node is identified (in the best decomposition) is called the tree-width of the graph. Now, the complexity of belief propagation, as well as other algorithms, is exponential in the tree-width, so you want to transform the graph to a tree only if the tree-width is sufficiently small.

Unfortuantely, it is $NP$-complete to compute the tree-width of a graph exactly, but there are some approximation algorithms. You can read more about it in Shiva Kintali's blog:
http://kintali.wordpress.com/2010/01/28/approximating-treewidth/


What evidence do we have for (and against) Unique Games Conjecture? Subhash Khot's Unique Games Conjecture is one of active research areas in complexity theory.

  What evidence do we have for it? What evidence do we have against it?

Khot gave a UGC survey talk at CCC 2010. The write-up is here. The final segment (bottom of page 30) has his opinions on this question.


Generating Graphs with Trivial Automorphisms I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.

It is "commonplace" (yet controversial!) to assume the existence of BPP algorithms capable of generating "hard instances of the Graph Isomorphism problem." (Along with a witness of isomorphism.)

In my contrived protocol, I'm gonna assume the existence of such BPP algorithms, which satisfy one additional requirement:

Let the generated graphs be $G_1$ and $G_2$. There's just one witness (permutation) that maps $G_1$ to $G_2$.

This implies that $G_1$ has only trivial automorphisms. In other words, I'm assuming the existence of some BPP algorithm, which works as follows:

On input $1^n$, generate an $n$-vertex graph $G_1$, such that it has only trivial automorphisms.
Pick a random permutation $\pi$ over $[n]=\{1,2,\ldots,n\}$, and apply it on $G_1$ to get $G_2$.
Output $\langle G_1,G_2,\pi \rangle$.

I'm gonna assume that, in Step 1, $G_1$ can be generated as needed, and
$\langle G_1,G_2 \rangle$ is a hard instance of the Graph Isomorphism problem. (Please interpret the word "hard" naturally; a formal definition is given by Abadi et al. See also the paper by Impaliazzo & Levin.)

  Is my assumption reasonable? Could anyone please point me to some references?

At least the first naive approach one might think of does not work.  The approach I have in mind is to simply generate $G_1$ purely at random.  Since almost all graphs have no symmetries (that is, the proportion of graphs on $n$ vertices with no nontrivial automorphisms approaches 1 as $n \to \infty$), $G_1$ will have no nontrivial automorphisms with high probability, which is what we want.  However, the average-case version of graph isomorphism, where graphs are chosen uniformly at random, can be solved in linear time [BK], so this does not generate a distribution of hard instances.

But a second naive approach has a chance of working: generate a random regular graph (of non-constant degree, since constant-degree graph isomorphism is in P).  This also has no nontrivial automorphisms with high probability [KSV], but the Babai-Kucera result does not apply (as they point out in the paper).  Proving that this is an invulnerable generator obviously requires some assumptions, but one could imagine proving unconditionally that average-case regular graph isomorphism is as hard as worst-case graph isomorphism, though I don't know how likely this is.  (Note that worst-case regular graph isomorphism is equivalent to worst-case (general) graph isomorphism.)

[BK]. Laszlo Babai, Ludik Kucera, Canonical labelling of graphs in linear average time. FOCS 1979, pp.39-46.

[KSV] Jeong Han Kim, Benny Sudakov, and Van H. Vu. On the asymmetry of random regular graphs and random graphs. Random Structures & Algorithms, 21(3-4):216–224, 2002.  Also available here.


Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$ Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence Number of such a $G$.

Question
Which is the best known upper bound on the Indipendence Number $\alpha(G)$ of such a so dense $G$?

The closest references I've found are:

The Independence Ratio of Regular Graphs by Béla Bolobás, October 1981. Here there is no random restriction, and the degree is considered to be a constant. But at top of page $4$ it is written that for a general $\Delta$ relation the Independence Number is asymptotically upper bounded by $\frac{2 \log \Delta}{\Delta}|V|$. This alone should nail down the question. But see below.
This presentation where, at slide 16, it is said that $\alpha(G) = \frac{2 \log \Delta}{\Delta}|V|(1+O(\xi))$ is asymptotically almost surely satisfied, where $\xi \to 0$ as $\Delta \to \infty$. To be noted that such slide says "Fix $\Delta \geq 3$...", the verb "to fix" seems to suggest that $\Delta$ is a constant. Such slide cites the result here below.
On the Independence and Chromatic Numbers of Random Regular Graphs by A. M. Frieze and T. Łuczak, May 1988. From the very abstract, it is already clear that they allow $\Delta$ to grow with $|V|$. However: for their result to hold, they require that $\Delta \in o(|V|^\theta)$ where $\theta < \frac{1}{3}$. Such requirement is clearly false in my case. Does it mean that the general $\Delta$ mentioned by Bolobás is not as general as to encompass the $\Theta(\sqrt{|V|} \log^2 |V|)$ case...? For if it encompasses it (as I hope), then why Frieze and Łuczak would have proven a result less powerful than the result already proven $7$ years before by Bolobás? This confusion makes me asymptotically almost sure that I'm missing something here.

I don't think the Bollobás paper asserts the bound on the independence number; rather, it seems to me that it asserts that for any given maximum degree $\Delta$ and lower bound on the girth $g$, there exists graphs of degree at most $\Delta$ and girth at least $g$ with independence ratio at most $2\log \Delta/\Delta$. In contrast, as you mention, the Frieze and Łuczak paper seems to give concentration of random $\Delta$-regular graphs that holds for $\Delta=o(n^{1/3})$, so that the desired upper bound holds with probability $1-o(1)$. This result is thus incomparable to the Bollobás paper, I think.
For your specific application, I think one can give an upper bound of roughly $\alpha(G)\leq O(n/\sqrt{\Delta})=\tilde{O}(n^{3/4})$ that holds with probability $1-o(1)$ (in fact, at least inverse polynomial error probability). I have no idea if this bound is closer to the truth for this regime, and this is of course much weaker than the bound that you want (note that no bound better than $\tilde{O}(n^{1/2})$ is possible anyway, for any $\Delta$-regular graph with $\Delta=\tilde{O}(n^{1/2})$-here, I'm using the tilde notation to mean up to logarithmic factors, in either direction).
Here's two ways that I hope work to get this bound: one is to note that the Frieze and Łuczak paper upper bound does not seem to rely on the constant degree restriction. In particular, just mimicking their proof of the upper bound (which is by far the easier direction in their concentration result), it seems to me like everything should go through to show that the probability of having an independent set of size greater than $\tilde{O}(n^{3/4})$ is $1-o(1)$. The reason their bound degrades this much when the degree is not constant is because it incurs a $e^{\Delta^2}$ loss when moving between simpler random graph models.
Another way to get it is to use some recent high-powered results that show that if $\Delta\to \infty$ with $n$ but $\Delta=o(n^{1-\epsilon})$ for some fixed $\epsilon>0$, then the spectral radius of the adjacency matrix (excluding the trivial eigenvalue $\Delta$) is $O(\sqrt{\Delta})$ with probability $1-o(1)$ (where the constant depends on $\epsilon$, but not $\Delta,n$). If $\lambda=\lambda(G):=\max\{\vert \lambda_2(G)\vert,\vert \lambda_n(G)\vert\}$ is the second largest eigenvalue of the adjacency matrix of a graph $G$, Hoffman's bound asserts that for a $\Delta$-regular graph on $n$ vertices:
\begin{equation}
\alpha(G)\leq \frac{\lambda}{\Delta-\lambda}n.
\end{equation}
For $\Delta=\tilde{O}(n^{1/2})$ and using the estimate above gives with probability $1-o(1)$ that $\alpha(G)\leq O(n/\sqrt{\Delta}) = \tilde{O}(n^{3/4})$.


Sorting by Euclidean distance $S$ is a set of points on a plane. A random point $x \notin S$ is given on the same plane. The task is to sort all $y \in S$ by Euclidean distance between $x$ and $y$.

A no-brain approach is to calculate distances between $x$ and $y$ for all $y \in S$ and then sort them using any fast algorithm.

Is there any way to store or preprocess $S$ so the sorting process becomes faster?

Solution 1: Find the $\Theta(n^2)$ perpendicular bisectors between pairs of points, and construct the arrangement of these lines. The arrangement has $\Theta(n^4)$ cells, within which the sorted order is constant. So build a point location data structure for the arrangement, and decorate each cell with the sorted order that is to be returned for points within that cell. The sorted orders between adjacent cells differ only in a single transposition, so you can use a persistent data structure to allow the representations of these sorted orders to share space. Total space is $O(n^4)$ and query time is $O(\log n)$.

Solution 2: Choose a random sample of $\Theta(n)$ of these same perpendicular bisectors, construct their arrangement, and partition each arrangement cell by vertical line segments through each crossing of two sampled lines. The resulting partition has $\Theta(n^2)$ cells, each of which with high probability is crossed by $O(n)$ unsampled bisectors. Decorate each cell of the partition by a valid sorted ordering of the points as viewed from some x within the cell. Total space is $O(n^3)$.

Now, to do a query, locate the query point in the partition, look up the ordering stored with the partition cell, and use the Cartesian tree comparison sorting algorithm of Levcopoulos & Petersson (1989) starting with this stored ordering. The time for this step is proportional to $\sum_i O(1+\log k_i)$ where $k_i$ is the number of points that are out-of-order with point $y_i$. But $\sum k_i$ is $O(n)$ (each unsampled bisector causes at most one out-of-order pair of points), so the query time $\sum_i O(1+\log k_i)$ is also $O(n)$.


Is there a notion of indistinguishability obfuscation for almost equivalent circuits? In the definition of indistinguishability obfuscation (iO), we have a probabilistic algorithm Obs that receives as input a circuit C, such that $i)$ the output Obs(C) is a circuit with the same functionality as C and $ii)$ for any $C_1$ and $C_2$ with the same functionality, we have that Obs($C_1$) is indistinguishable from Obs($C_2$).

Has a similar notion (and candidate construction) for a similar concept where the security holds for $C_1$ and $C_2$ are almost the same (i.e., they agree on all except a negligible fraction of the inputs, and it is computationally hard to find the points where they differ).

I think the notion you're looking for is differing-inputs indistinguishability obfuscation(diO), or originally called extractability iO:
https://eprint.iacr.org/2013/650.pdf

The definition of diO tells us: if there's a non-uniform PPT adversary that can distinguish the obfuscations of two circuits with "almost same" functionalities Obf($C_1$) and Obf($C_2$), then there exists a non-uniform PPT extractor that can extract an input(witness) $x$ where $C_1(x) \neq C_2(x)$.
(the formal definition is on page 11)

If there are only polynomially many inputs where their outputs are different evaluated on $C_1, C_2$, then the standard iO definition also implies diO, using a binary search argument on the input space.

If there are negligible(in ratio) but exponentially many different outputs , then diO is a stronger assumption than standard iO. There are some negative results on the possibility of its existence in certain cases:

https://eprint.iacr.org/2016/162.pdf

https://eprint.iacr.org/2013/860.pdf


Reduction SAT to a problem on a planar graph with as few vertices as possible Let $\phi$ be CNF formula with $n$ variables and $m$ clauses.

I am looking for a reduction is $\phi$ satisfiable to a problem
on a planar graph $G$ with as few vertices as possible.

The majority of reductions I have seen use "crossing gadget",
which replaces edge crossing by a planar graph.

So far the best reference is $|V(G)|=m^2$.

The motivation is that the treewidth of planar graphs
is at most $4.9 \sqrt{|V(G)|}$ and this gives subexponential
complexity for problems exponential in the treewidth like
Independent Set.

You are right that improved reductions from CNF-SAT to any one of various planar graph problems would give improved algorithms for CNF-SAT (via graph algorithms with runtimes exponential in treewidth; such algorithms exist for many graph problems). If you could get $|V(G)| = o(m^2)$ in the reduction you mention, this would imply that the Exponential Time Hypothesis (ETH) is false. This is well-appreciated, yet it has not led to any improvements on running times for CNF-SAT (as far as I know).  For more on how ETH has been used to classify the difficulty of planar (and non-planar) graph problems, see e.g. this survey of Lokshtanov, Marx, and Saurabh.

As for reducing the constant in such reductions, achieving $|V(G)| = c m^2$ for $c$ as small as possible, I don't know how much effort has been devoted to this.


Strongly weight-balanced deterministic skip lists In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are defined as:

  For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants.

They claim:

  Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees,
  deterministic skip lists, and skip lists in the expected sense.

Other papers also claim that deterministic skip lists are strongly weight-balanced, including Concurrent Cache-Oblivious B-Trees and Cache-Oblivious Streaming B-trees.

I can't figure out why deterministic skip lists have this property. The original paper on deterministic skip-lists notes that

  As we see from Fig. 1, there exists a one-to-one correspondence between 1-2 skip lists and 2-3 trees.

It seems to me, however, that 2-3 trees are not strongly weight-balanced, since a node at height $h$ can have anywhere from $2^h$ to $3^h$ descendants.

I have been in contact with one of the authors. He confirmed this was a slip.

As stated above, this does not affect, in any way, any of the results of the paper.


Factoring assuming smoothness of some numbers I have came across a lot of factorization methods and most of them seem to assume smoothness of some numbers.

For example

When $p-1$ is smooth
When $|E(\mathbb{F}_p)|$ is smooth. (Elliptic curve factorization)
Smoothness of prime ideals in Number field sieves.

I want to know whether any other notions are known to be equivalent to factoring like smoothness of $p+1$ or $p^2+1$  ?

See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time polynomial in $\log N$ and $k$ and $B$.  In particular this gives a $(p+1)$-method (see the earlier work of Williams) and $(p^2+1)$ method.

http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf


Exact exponential-time algorithms for 0-1 programs with nonnegative data Are there known algorithms for the following problem that beat the naive algorithm?

Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers.
Output: an optimal solution $x^*$ to $\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}$.

This question is a refined version of my previous question Exact exponential-time algorithms for 0-1 programming.

if the number of non-zero coefficients in $A$ is linear in $n$, there is an algorithm that solves this problem in less than $2^n$ time.

Here's how it works.  We use the standard connection between an optimization problem and its corresponding decision problem.  To test whether there exists a solution $x$ where $Ax\le b$ and $c^T x \ge \alpha$, we will form a decision problem: we will adjoin the constraint $c^T x\ge \alpha$ to the matrix $A$, and test whether there exists any $x$ such that $Ax \le b$ and $-c^T x \le -\alpha$.  In particular, we will form a new matrix $A'$ by taking $A$ and adding an extra row containing $-c^T$, and we will form $b'$ by taking $b$ and adjoining an extra row with $-\alpha$.  We obtain a decision problem: does there exist $x \in \{0,1\}^n$ such that $A' x \le b'$?  The answer to this decision problem tells us whether there exists a solution to the original optimization problem of value $\alpha$ or greater.  Moreover, as explained in the answer to your prior question, this decision problem can be solved in less than $2^n$ time, if the number of non-zero coefficients in $A'$ is linear in $n$ (and thus if the number of non-zero coefficients in $A$ is linear in $n$).  Now we can use binary search on $\alpha$ to solve your optimization problem in less than $2^n$ time.

My thanks to AustinBuchanan and Stefan Schneider for helping to debug an earlier version of this answer.


What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems? JBV suggested I turn some comments into a question, so here goes.

Another question [1] asks about applications of QM computing. One answer [2] was "efficiently simulating quantum mechanics". Apparently this idea dates all the way back to Feynman's early writing on subject; although I dont have a reference. So:

  Question. What is the proof that a quantum computer can efficiently simulate an arbitrary quantum mechanical system?

On one level this seems basic. However, this does not seem to be trivial for following reason: most quantum computing literature seems to reduce to operations on gates acting on two particles or other small subsystems. (Yes, Toffoli gates act on 3 inputs, but anyway are often reduced to two-qubit CNOT gates.)

There is surely no question, due to Turing completeness, that a quantum computer can simulate arbitrary classical or even quantum physics (although maybe there are some naysayers there due to the uncertainty principle etcetera — I  would be curious to hear about that too). But it seems to me that to simulate arbitary quantum physics efficiently one at least needs a way to simulate arbitrary n-way interactions in mostly/nearly 2-way gates.

One could argue that we can build arbitary n-way gates, but the clear evidence after many years of experimental research is that even just 2-way gates are extremely hard to build, and that n-way gates would surely be much harder. (There are some 3-way quantum experiments, e.g. 3 particle bell inequalities, but they are difficult to build.)

[1]
Real world applications of quantum computing (except for security)

[2] https://cstheory.stackexchange.com/a/10241/248

Why do you think simulating quantum physics means that you have to efficiently implement arbitrary quantum $n$-way interactions? If that's your requirement, quantum computers cannot do it efficiently.

You can write down an $n$-way unitary gate which implements an arbitrary $n$-bit-input $n$-bit-output function. This would let us solve an arbitrary problem on $n$ bits in one step. It is common sense that we can't find quantum systems in "real life" that will let us do this.

Of course, in actual quantum physics, quantum dynamics is Hamiltonian and not just unitary, but there are still roughly $2^n$ parameters in an arbitrary $n$-way Hamiltonian, and doing this using 2-qubit gates (which have a constant number of parameters each) will require an exponential number of gates. Furthermore, I am fairly sure that the ability to implement arbitrary $n$-way Hamiltonians would still let you construct arbitrary binary functions on $O(n)$ bits.

So the requirement you pose for quantum computers to efficiently simulate arbitrary $n$-way interactions is much too strict. What you need is that quantum computers can efficiently simulate the $n$-way interactions that actually arise in quantum physics. Quantum computers are able to efficiently simulate $k$-local Hamiltonian dynamics for constant $k$, which may be enough to simulate interactions that arise in real quantum physics.

If you can suggest any $n$-way interactions that arise in quantum physics that  appear difficult for a quantum computer to simulate efficiently, this would be a truly exciting development. However, I don't know of any current suggestions for such interactions.

Whether quantum computers can efficiently simulate quantum field theory is still an open question, but progress is currently being made on it.


Possibility of hierarchy with $UP$ class? I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The reference https://link.springer.com/content/pdf/10.1007%2FBF01184809.pdf gives some classes for which we have oracles with respect to which $UP$ is not low.

Which classes are known to be low with $UP$ oracle ($PSPACE$ is one of them)?
Is there a hierarchy to concoct with $UP$ and $coUP$ analogous to the standard polynomial hierarchy and in particular is there an analog of $PSPACE$?

Problem 2. answered in references

a. https://arxiv.org/pdf/cs/9907033.pdf

b. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=19DD617ABDB31709CA0BEF797C283867?doi=10.1.1.60.9357&rep=rep1&type=pdf.


Formalization of proofs and computational complexity paradox? While reading some articles on formal proofs (see also my previous question on cstheory about the length of ZFC proofs versus human written proofs), I came up with this apparent paradox.

Let $M_{const}$ be a program that given Turing machine $M$ checks if there is a short ZFC proof $\Gamma$ of length $|\Gamma| \leq |M|^2$ that $M$ runs in constant time.

Program M_const( M )
  enumerate all strings S of length  <= |M|^2
    verify if S is a proof of "M in O(1)"
      if it is a valid proof the halt and accept
  if no valid proof is found halt and reject

Now, we can build $M_{paradox}$ that knows its own code (by the recursion theorem) and on input $x$
first simulate $M_{const}( M_{paradox} )$; if it accepts then loop from $1$ to $|x|$
 (so it falls in $O(n)$), otherwise halts (so it falls in $O(1)$).

Program M_paradox( x )
  String M = self_code()  // ok by the recursion theorem
  simulate M_const( M )   // simulate M_const on M_paradox
    if it accepts then for i = 1 to |x| do nothing // -> O(n)
    otherwise halts                                // -> O(1)
  some dummy unused code here  // see below

It is clear (and hopefully provable in ZFC) that:

$M_{const}$ always halts and is correct;
if $M_{const}( M_{paradox} ) = Yes$ then $M_{const} \notin O(1)$ by construction; so we have a contradiction;
so $M_{const}(M_{paradox}) = No $; and we can have:

(a) $M_{paradox} \notin O(1)$ OR
(b) $M_{paradox} \in O(1)$ AND there is not a short proof of it;

but case $(a)$ cannot hold by construction; so ...

$M_{paradox} \in O(1)$
AND there is not a short proof of it;

But steps 1--4 can be formalized in ZFC and (unless I'm missing something, its length depends only linearly on $|M_{paraox}|$) so we can add some dummy code to $M_{paradox}$  until such ZFC proof is shorter than $| M_{paradox}|^2$ (we can use the fact that the runtime of a Turing machine doesn't change if we add unused states, it only affects the self representation); so we get a contradiction with point 5 which says that there is not a short proof of $M_{paradox} \in O(1)$ ???

  Q1. What is the output of $M_{const}( M_{paradox} )$ ?

Update: There were another question Q2 here, but it I decided to post it as a new "Part II" question to avoid confusion.

$\def\mc{M_\mathit{const}}\def\mp{M_\mathit{paradox}}$Let me for the record write up the answer to Q1, so that it doesn’t live only in the comments.

The reasoning given in steps 1–5 in the question is correct in the real world. Thus, $\mc(\mp)$ outputs NO, and $\mp(x)$ halts in constant time, but there is no short enough proof of this in ZFC.

When trying to formalize this argument in ZFC, the problematic step is 2: here, we need to assert, in ZFC itself, the implication

  (1) If ZFC proves ‘$\mp$ halts in constant time’ by a proof of length $\le|\mp|^2$, then $\mp$ halts in constant time.

In general, statements of the form

  (2) If ZFC proves $\phi$, then $\phi$.

are known as instances of the reflection principle for ZFC, and by Löb’s theorem (a generalization of Gödel’s 2nd incompleteness theorem) they are never provable in ZFC itself, except for the trivial case when ZFC already proves $\phi$. Notice that the consistency statement for ZFC is a special case of the reflection principle, for $\phi=\bot$; in general, reflection principles are strictly stronger than consistency.

In our case, $\phi$ is the $\Sigma^0_2$ formula “$\mp$ halts in constant time”, so step 2 apparently makes an appeal to the $\Sigma^0_2$-reflection principle for ZFC, unprovable in ZFC.

However, we have to our disposal an extra restriction that we ignored so far, namely that we have a bound $\le|\mp|^2$ on the length of the purported ZFC-proof of $\phi$. Crucially, at this point, $\mp$ is a fixed explicit Turing machine, hence this bound is a standard integer constant (and likewise, $\phi$ is a fixed sentence). Thus, (1) is actually an instance of the finitistic reflection principle

  (3) If $\phi$ has a ZFC-proof of length $\le s$, then $\phi$.

This is actually provable in ZFC: if $\phi$ does, indeed, have a ZFC-proof of length $\le s$, then we can just take it, and derive (3) by ignoring the premise; if not, then for each string $|w|\le s$, we can “by inspection” produce a ZFC-proof that ‘$w$ is not a ZFC-proof of $\phi$’, and concatenating all these together, we obtain a proof of (3) (specifically, a proof of negation of its premise).

This brute-force proof will have length exponential in $s$, i.e., in our case, $2^{O(|\mp|^2)}$. There are in fact proofs of (3) of length polynomial in $s$ and $|\phi|$: this was proved by Pudlák [1] using efficient partial truth predicates. The improvements in [2] are only stated for consistency statements, but I believe they apply to more general reflection principles as well. Thus, there are ZFC-proofs of (1) of length $O(|\mp|^2)$.

However, this is still not enough to get a contradiction, as it seems any reasonable proof of (3) needs length more than $s$ (though the lower bounds in [1,2] are not quite that strong). Thus, ZFC-proofs of (1) will need length more than $|\mp|^2$. This cannot be fixed by raising the bounds in $\mc$ or by padding $\mp$, as these will just raise the length parameter $s$ in the same way. Thus, there is no paradox.

So, to summarize: ZFC proves that $\mc(\mp)$ outputs NO and that $\mp(x)$ halts in constant time, but the proofs are a little too long.

It is also worth mentioning that nothing in these arguments depends on ZFC specifically. The same reasoning will work for many other theories, for example Peano arithmetic. (Basically, we need a sequential theory axiomatized by finitely many axioms or nice schemata, see Pudlák’s papers for details.)

[1] Pavel Pudlák, On the length of proofs of finitistic consistency statements in first order theories, in: Logic Colloquium ’84 (Paris, Wilkie, Wilmers, eds.), Studies in Logic and the Foundations of Mathematics vol. 120, 1986, pp. 165–196, doi: 10.1016/S0049-237X(08)70462-2.

[2] Pavel Pudlák, Improved bounds to the length of proofs of finitistic consistency statements, in: Logic and Combinatorics (Simpson, ed.), Contemporary Mathematics vol. 65, American Mathematical Society, 1987, pp. 309–331, doi: 10.1090/conm/065.


Is there a name for "physical things out of which one can build a Turing machine"? One of the amazing things about computer science is that the physical implementation is in some sense "irrelevant".
People have successfully built computers out of several different substrates -- relays, vacuum tubes, discrete transistors, etc.
People may soon succeed in building Turing-complete computers out of non-linear optical materials, various biomolecules, and a few other substrates.
In principle, it seems possible to build a billiard-ball computer.

However, the physical substrate is not completely irrelevant.
People have found that certain sets of components -- in particular,
diode-resistor logic --
are "incomplete": no matter how many of them you connect to a power supply and to each other, there are certain very simple things that it cannot do.
(The diode-resistor logic can implement AND, OR, but fails to implement NOT).
Also, certain ways of connecting components -- in particular, single-layer perceptrons -- are "incomplete": there are certain very simple things that they cannot do.
(A single-layer perceptron can implement AND, OR, NOT, but fails to implement XOR).

Is there a less-awkward phrase for "physical things out of which one can build a Turing machine"?
Or for the opposite, "physical things that, no matter how many of them one has, cannot form a Turing machine"?

For a while I used the phrase "functionally complete set" or "universal set of gates" -- or, when speaking to mathematicians, "physical things that can implement a functionally complete set" -- but I've been told that isn't quite correct.
Some sets of components can implement a functionally complete set;
and yet it is not possible to build a Turing-complete machine entirely out of these components.
For example, light bulbs and manually-operated 4-way light switches can implement a functionally complete set (AND, OR, NOT, XOR, etc.);
and yet it is not possible to build a Turing-complete machine entirely out of light switches and light bulbs, since the (electrical or optical) output of one cannot be fed into the (mechanically rotating) input of the next.

related: Is there an official name for a notion of "reusably universal"? and Is there a name for “chips out of which one can build a CPU”?

Physics models reality with theories that define a concept of time-dependent state associated to a system and a time-evolution operator that describes how this state evolves. As soon as you find a physical system that (after some state-space discretization) implements the state space of your Turing machine, and that features interaction terms that implement (maybe after some time discretization) the time evolution according to the state transition table of your Turing machine on its state space, you have found a Turing-complete physical model of your system. Thus you can arguable say, your system "is" Turing-complete.

When looking at quantum computing, you will find discussions of implications physical theories have on the Turing model of computation. For example, physical theories have to be reversible. A property, which is not shared by ordinary Turing machines. Yet there is no loss in generality, as any Turing machine can be simulated by a reversible one, with some overhead that can trade-off time vs. space, etc.


A basic question about bitcoin's anti double spending mechanism Note: much more basic than: Bitcoin and preventing double spending in decentralized digital currencies

I'm trying to understand the concern that bitcoin's chain of blocks technique tries to solve (see http://www.bitcoin.org/bitcoin.pdf). Warning: not a crypto-dude, be tolerant.

I understand that basically we're worried about "double spending". I'm able to grasp this idea when talking about discrete, indivisible coins. E.g. there are only 3 coins in the world, which cant be divided to cents, and we need to track the history of all 3, and to make sure that each payer really had the coin he claimed to have while paying with it.

While I'm able to see how this concept extends to millions of coins, I can't get how does it extend to fractions of coins. How does a "double spending" attack scenario actually looks like? how do the honest nodes scrutinize a nominated new block, after some node proposes it as the new head node? please provide me with some illustrative examples...

The correct answer was given to me here: http://forum.bitcoin.org/index.php?topic=27979.msg352498#msg352498.

The gist: The entire value of the output contributes to the subsequent transaction, so if you wish to transfer smaller amount, you must add an additional output on the second transaction to send the remainder back to yourself.

Note that the accounting is done for transactions outputs and inputs. The block concept is not necessary for the verification process and is only used for technical convenience.


complexity of randomized gossiping The gossiping problem in distributed systems is the following. We have a graph $G$ with $n$ vertices. Each vertex $v$ has a message $m_v$ that must be send to all nodes.

Now, my question is in the context of the ad-hoc network model (we assume that a node does not have any prior knowledge about the topology of the network, its in and out degrees, and the set of its neighbours. In fact the only knowledge of each node is its own identifier and the total number of nodes).

I also assume that all nodes have access to a global clock and work synchronously in discrete time steps called rounds.

The complexity of an algorithm in this context is the number of rounds needed for completion.

I remember that there exists an algorithm that solves the gossiping problem in $O(n \log ^2 n)$ rounds with high probability. But I cannot find the reference anymore, and I am wondering if there are more recent results on that matter.

edit following the judicious comment: at each round a node can transmit the message to all its neighbours and can receive the messages from them. A node will receive a message at a given round if and only if exactly one of its neighbours transmits at that round. Otherwise a collision occurs and none of the messages is received by the node.

I think the reference you are looking for is the paper "Broadcasting algorithms in radio networks with unknown topology" by Czumaj and Rytter.  It seems this paper makes some improvements, but I think it depends on the specifics of the model.


Constant in Komlos conjecture Given $n$ vectors $v_1,\dots,v_n\in\Bbb R^N$ with $\|v_i\|_2^2\leq1$ at every $i\in\{1,\dots,n\}$, Komlos conjecture states that, there is a $c\in\Bbb R$ (independent of $n,N$) such that at some $\epsilon\in\{-1,+1\}^n$, $$\Big\|\sum_{i=1}^n\epsilon_iv_i\Big\|_\infty<c.$$ What is best lower bound known for $c$?

Best upper bound is $c=O(\sqrt{\log n})$.

Is there a set of examples for $c=1+\delta$ for any $\delta>0$ where Komlos conjecture fails?

A simple way of obtaining a lower bound $c\ge\sqrt{2}$ is to consider pairs of vectors $u,v\in\mathbb{R}$. First of all, it makes sense to focus on pairs of unit vectors for which all $\{-1,1\}$-linear combinations are as long as possible (note that this is just an interesting special case, I'm not saying that it is opotimal in any way). This is achieved when $u,v$ are orthogonal, and by checking the possible rotations we find that $u=\frac{1}{\sqrt{2}}(1,1), v=\frac{1}{\sqrt{2}}(1,-1)$ show that $c$ must be at least $\sqrt{2}$.

This example can be generalized to the sets of vectors $V_k=\{2^{-\frac{k}{2}}v_{i,k}\ |\ 0\le i\le k\}\subseteq\mathbb{R}^{2^k}$, where the $j$-th coefficient $(v_{i,k})_j$ of $v_{i,k}$ is $1$ if the $i-th$ binary digit in $j$ is $0$, and $-1$ otherwise.

The $\infty$-norm of any $\{-1,1\}$-linear combination of the vectors in $V_k$ is $(k+1)2^{-\frac{k}{2}}$, which reaches its maximum $\frac{3}{2}$ at $k=2$, with the set of vectors

$V_2=\{\frac{1}{2}(1,1,1,1),\frac{1}{2}(1,1,-1,-1),\frac{1}{2}(1,-1,1,-1)\}$.

There may be better lower bounds, but this is a start.


Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph Quite similar to my previously posted question. This time however, the graph is undirected.

Given

An undirected graph $G$ with no multiple-edges or loops,
A source vertex $s$,
A target vertex $t$,
Maximal path length $l$,

I am looking for $G'$ - A subgraph of $G$ that contains any vertex and any edge in $G$ (and only those), that are part of at least one simple path from $s$ to $t$ with length $\leq l$.

Notes:

I don't need to enumerate the paths.
I'm looking for an efficient algorithm (both time and memory), as I need to execute it over very large graphs (10^8 vertexes, 10^9 edges).

Well, the problem is in $P$ after all.
I'll keep the previous answer as it also works for the directed case (which is NPC, as answered on the other question), and shows it is $FPT$ with respect to $l$.

In the undirected case, it is solvable, deterministically via minimum cost flow (this might not work on the scales you are referring to in the question, but its better than exponential algorithm.

The following procedure will decide whether some edge $e=(u,v)\in E$ should be a part of the output graph. In order to answer the original problem just loop over all edges.

In order to create the flow network, do as follows:

Step 1:
Expand $e$ to have a vertex $x_e$ and replace $e$ with the edges $(u,x_e),$$(x_e,u),(v,x_e),(x_e,v)$  (they are directed as a part of the flow network), set their cost to 0.

Step 2: replace every vertex $t$, except for $x_e$ by two vertices $t^-$ and $t^+$, and add an edge $(t^-,t^+)$. Set the cost of these edges to 1.

Step 3: Replace of every edge $\{a,b\}\in E$ with the edges $(a^+,b^-),(b^+,a^-)$. Set the cost of these edges to 0.

Step 4: Add a new vertex $y_e$ and add the edges $(s,y_e),(t,y_e)$ with cost 0.

Step 5: set all capacities to 1.

Now run the min cost flow algorithm, searching for a flow of value 2 from $x_e$ to $y_e$.

Analysis:

Every 2-valued flow from $x_e$ to $y_e$ is a union of a path $x_e\leadsto s\to y_e$ and a path $x_e\leadsto t\to y_e$.
The paths are disjoint, since for every vertex $t$ there's only 1 capacity in the $(t^-,t^+)$ arc.
The returned paths are the two paths whose sum of distances is minimal, and that's also the cost of the found flow. This allows us to add $e$ to the output graph or delete otherwise.


Heuristics for Optimization Since it's Friday, it's time for a CW question. I'm looking for heuristics that have wide use in optimization problems. To limit the scope to more 'theory-friendly' heuristics, here are the rules (some arbitrary, some not)

It should be a well defined method without numerous parameters, and with a concrete running time (maybe per iteration)
It should have some known theoretical results associated with it (rate of convergence, approximation bounds if any, stationary properties, and so on)
It should have wide applicability and at least one flagship application where it's either the method of choice or one of a few.
it should not be inspired by nature (while this seems like a frivolous objection, I'm trying to exclude genetic algorithms, ant colony optimization and the like).

Answers should ideally be in the following format: here's an example.

Name: Alternating optimizaton

Goal: Minimize a (generally nonconvex) function $f(x,y)$

Conditions: The associated functions $g(x) = \min_y f(x,y)$ and $h(y) = \min_x f(x,y)$ are convex

Algorithm: $i^{\text{th}}$ iteration starts with $x_i, y_i$.

$x_{i+1} \leftarrow \arg \min_x f(x, y_i)$
$y_{i+1} \leftarrow \arg\min_y f(x_{i+1}, y)$

Best known app: $k$-means, iterated closest pair.

Theory: Known results on $k$-means, general sufficient conditions for global optimality of framework

p.s You might find that your answer ends up as a lecture in an algorithms seminar I'm planning :)

Name: iterated reweighted least square

Goal: minimize function of the form $ \sum w(\theta)F(\theta)^2$, $\theta\in R^n$, $F(\theta) \in R^m$, $w(\theta)\in R$

Conditions:  depend on case

Algorithm: obvious - fix weights, solve quadratic problem, recalculate weights

Best known app: geometric median,  M-estimators,$L_p$ norm, compressed sensing

Theory:  proven on-case-to-case basis


Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers? Real computers have limited memory and only a finite number of states.
So they are essentially finite automata.
Why do theoretical computer scientists use the Turing machines
(and other equivalent models) for studying computers?
What is the point of studying these much stronger models with respect to real computers?
Why is the finite automata model not enough?

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata.
Indeed, the main difference between the two models is that with finite automata, we expect to treat data that is bigger than the state space, and Turing Machine are a model for the other way around (state space >> data) by making the state space infinite. This infinity can be perceived as an abstraction of "very big in front of the size of the data". When writing a computer program, you try to save space for efficiency, but you generally assume that you won't be limited by the total amount of space on the computer. That is part of the reason why Turing Machines are a better abstraction of computers than finite automata.


Belief propagation for approximate real 3LIN? In a Science paper from 2002, Mezard, Parisi and Zecchina put forward the belief propagation heuristic for random 3SAT. Experiments indicate that the heuristic works well for ratios of constraints-per-variable for which a satisfying assignment is likely to exist.

My questions are:

(1) What if you consider random 3LIN instead of random 3SAT? (each constraint is a random linear equation over GF(2))

(2) What if you consider random approximate real 3LIN? Is it conceivable that the performance of (an appropriately adapted) belief propagation heuristic would be easier to analyze in this case?

The approximate version, defined in a recent work with Subhash Khot, is as follows: the variables can assume real values and not just binary values. We consider only assignments of norm 1.
Each equation is of the form $c_1 x_1 + c_2 x_2 + c_3 x_3 = 0$, where $c_1,c_2,c_3$ are normally distributed, and $x_1,x_2,x_3$ are chosen uniformly from the set of variables. An equation is satisfied if $|c_1 x_1 + c_2 x_2 + c_3 x_3|\leq \epsilon$, and not just if there is an exact equality.

The intuition is that in the approximate version, changes to the belief (what should be the assignment of a variable) could happen in a continuous/incremental way.

In coding theory, Belief Propagation is heavily used as a good heuristic for decoding (either explicit or randomly generated) LDPC codes in various settings (e.g., for the erasure channel, you want to satisfy all constraints more quickly than Gaussian elimination. For noisy channels, you want to find the "best fit", etc). I think techniques used there are directly relevant to your question. You may want to have a look at the book "Modern Coding Theory" by Urbanke and Richardson for an extensive discussion.


Boolean Functions Where Sensitivity Equals Block Sensitivity Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ is only polynomially larger than $s(f)$. What about the opposite direction? What is known about functions where $s(f) = bs(f)$?
Trivially, constant functions have $0=s(f)=bs(f)$. Also trivially, any function with $s(f) = n$ also has $s(f) = bs(f)$. It is non-trivial but not too hard to show that any monotone function also satisfies this equality. Are there any other nice classes of functions that have $s(f) = bs(f)$? A complete characterization would be ideal. What if we further strengthen the requirements to $s^0(f) = bs^0(f)$ and $s^1(f) = bs^1(f)$?
The motivation for this question is simply to get some intuition for how sensitivity relates to block sensitivity.
Definitions
Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function on $n$-bit words. For $x \in \{0,1\}^n$ and $A \subseteq \{1,\ldots,n\}$, let $x^A$ denote the $n$-bit word obtained from $x$ by flipping the bits specified by $A$. In the case that $A = \{i\}$, we will simply denote this as $x^i$.
We define the sensitivity of $f$ at $x$ as $s(f,x) = \# \{ i | f(x^i) \neq f(x)\}$. In other words, it is the number of bits in $x$ that we can flip in order to flip the output of $f$. We define the sensitivity of $f$ as $s(f) = \text{max}_x s(f,x)$.
We define the block sensitivity of $f$ at $x$ (denoted $bs(f,x)$) as the maximum $k$ such that there are disjoint subsets $B_1, B_2, \ldots, B_k$ of $\{1,2,\ldots, n\}$ such that $f(x^{B_i}) \neq f(x)$. We define the block sensitivity of $f$ as $bs(f) = \text{max}_x bs(f,x)$.
Finally, we define the 0-sensitivity of $f$ as $s^0(f) = \text{max} \{ s(f,x) | f(x) = 0 \}$. We similarly define 1-sensitivity, 0-block sensitivity, and 1-block sensitivity , denoted $s^1(f)$, $bs^0(f)$, and $bs^1(f)$, respectively.

Recently, I proved that s(f) = bs(f) for unate functions and read-once functions over the Boolean operators AND, OR and EXOR, and my paper including the results was accepted to TCS 2014.
(http://dx.doi.org/10.1007/978-3-662-44602-7_9)

You may be attacking this problem. If so, I feel sorry, but I started to attack the problem independently before the question was posted. A preliminary version of my paper was presented at a Japanese domestic meeting in Dec/2013 and the submission deadline was Oct/2013.
(http://www.ieice.org/ken/paper/20131220DBID/eng/)


Minimum weight matching in general graphs with additional input specifying the number of matched edges We know of the minimum weight perfect matching problem in general graphs which can be solved using a primal-dual algorithm. Assume, we have an additional constraint specifying the exact number of edges that the matching can use. In other words, given a graph G=(V,E) with
m=|E| and an integer k, where m and k are different in general, we need to find a matching of minimum weight that uses exactly k edges.

What is known about the problem? Do we have a polynomial time algorithm for the problem?

Add $n-2k$ extra vertices, each connected to all the original vertices with zero-weight edges, and add a large enough number $W$ to each of the original edges to make their weights all positive. Then look for the minimum weight perfect matching.


Can two strings be matched as disjoint subsequences of a string? Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a (non-contiguous) subsequence of $S$, and likewise for $S_2$. But now I ask whether I can have matches $m_1$ and $m_2$ of $S_1$ and $S_2$ as subsequences of $S$ ($m_k$ for $k \in \{1, 2\}$ is a strictly increasing function from $\{1, \ldots, |S_k|\}$ to $\{1, \ldots, |S|\}$ such that, for all $i$, $S_k[i]$ and $S[m_k(i)]$ are the same letter) such that $m_1$ and $m_2$ are disjoint (that is, their images are disjoint). Intuitively, no character of $S$ matches $S_1$ and $S_2$ simultaneously.

Is there a PTIME algorithm to determine this (in the size of the input $S_1, S_2, S$), or can it be shown to be NP-hard? I would suspect it is NP-hard but I cannot see a reduction.

In case it is in PTIME, what about the straightforward generalization, for a constant $k$, where $k$ strings are given as input and I ask for the existence of pairwise disjoint matches of all $k$ strings?

(This problem is a bit related to How hard is unshuffling a string? except the candidate strings can be different, are provided as input, and are not required to cover the entire string $S$.)

Case k=2

Perhaps you can use the following polynomial time dynamic approach:

Keep a table $T_i$ of $(|S_1|+1)(|S_2|+1)$ pairs, in which element $(x,y)=1$ if and only if after scanning $i$ elements of the reference string $S$, $x$ characters of $S_1$ have been found, and $y$ characters of $S_2$ have been found (without overlaps).

Every pair of the table $T_0 (i=0)$ is zero except for the pair $(0,0)=1$.
Copy $T_i$ to $T_{i+1}$ and read the next character $c=S[i+1]$  from $S$; if in $T_i$ there is an entry $(x,y)=1$ such that $S[x+1]=c$ then in $T_{i+1}$ set $(x+1,y)=1$; if in $T_i$ there is an entry $(x',y')=1$ such that $S[y'+1]=c$ then in $T_{i+1}$ set $(x',y'+1)=1$.

At the end of the scan, $S$ contains the merged distinct copies of $S_1$ and $S_2$ if and only if $(|S_1|,|S_2|)=1$.

Simple example:

S  =  a b a a c
S1 =  a a c
S2 =  b a

S    0,0  0,1  0,2 1,0 1,1 1,2 2,0 2,1 2,2 3,0 3,1 3,2
     1    0    0   0   0   0   0   0   0   0   0   0  < T0
a    1    0    0   1   0   0   0   0   0   0   0   0  < T1
b    1    1    0   1   1   0   0   0   0   0   0   0  < T2
a    1    1    1   1   1   1   1   1   0   0   0   0  < T3
a    1    1    1   1   1   1   1   1   1   0   0   0  < T4
c    1    1    1   1   1   1   1   1   1   1   1  [1] < T5

Case k fixed

The same approach above can be used for any fixed $k >2$ (the table size grows polynomially).

Case k not fixed

If $k$ strings are given as input, and $k$ is NOT FIXED: in that case there is a quick reduction from the 3-PARTITION problem which is strongly NP-complete, so it remains NPC even when the input numbers are represented in unary.

Given a set of $A = \{x_1,x_2,...,x_{3m}\}$ of $3m$ positive integers (that can be specified in unary), and a target sum $B$ we must find $m$ disjoint subsets $A_1,A_2,...,A_m \subseteq A$ of $3$ elements ($|A_i|=3$), and the sum of the elements of each subset must be $B$.

Over alphabet $\{a,b,c\}$, set:

"reference" string $S = a^3 \; b^B\; c^3 \; a^3 \; b^B\; c^3 \; ... a^3 \; b^B\; c^3 \;$ ($a^3 b^B c^3$ repeated $m$ times)
for $i = 1,...,3m$ set string $S_i = a \; b^{x_i} \; c$

Informally: the $a^3$ parts of $S$ force to match $3$ of the $S_i$s (otherwise some $S_i$ will not be included); the $c^3$ parts force to "close" $3$ of the $S_i$s. And the  $b^B$ blocks (there are $m$ of them) must be filled exactly with the $b^{x_i}$ substrings of $3$ distinct $S_i$.

Small example:

3-PARTITION instance: $A = \{ 3,  2, 1, 5, 4, 3\}, B=9, (m=2)$

S  = aaa bbbbbbbbb ccc aaa bbbbbbbbb ccc
S1 = a bbb c
S2 = a bb c
S3 = a b c
S4 = a bbbbb c
S5 = a bbbb c
S6 = a bbb c


Proof relevance vs. proof irrelevance I want to use use Agda to help me write proofs, but I am getting contradictory feedback about the value of proof relevance.
Jacques Carette wrote a Proof-relevant Category Theory in Agda library. But some seem to think (perhaps here, but I was told elsewhere) that proof relevance can be problematic. 1-Category Theory is supposed to be proof irrelevant (and I guess above two categories, this is no longer the case?) I even heard that one may not get the same results if one uses proof relevant category theory.
At the same time I believe the Category Theory in the HoTT book and the implementation in Cubical Agda are proof irrelevant (as the HomSets are Sets, i.e., have only one way of being equal).
When should I be happy to have proof relevance? When should I rather choose a proof irrelevant library or proof assistant? What are the advantages of each? Would proof irrelevance be problematic as I move to two categories?

There are several possible notions of proof relevance. Let us consider three similar situations:

An element of a sum $\Sigma (x : A) . P(x)$ is a pair $(a, p)$ where $a : A$ and $p$ is a proof of $P(a)$.

An element of $\Sigma (x : A) . \|P(x)\|$, where $\|{-}\|$ is propositional truncation, is a pair $(a, q)$ where $a : A$ and $q$ is an equivalence class of proofs of $P(a)$ (where any two proofs of $P(a)$ are considered equivalent).

In set theory, an element of the subset $\{x \in A \mid \phi(x)\}$, where $\phi(x)$ is a logical formula, is just $a \in A$ such that $\phi(a)$ holds.

The first situation is proof relevant because we get full access to the proof $p$, and in particular we may analyze $p$.
The third situation is proof irrelevant because we get access just to $a \in A$ but have no further information as to why $\phi(a)$ holds, just that it does.
The second situation looks like proof irrelevance, but is actually a form of restricted proof relevance: we do not delete the proof of $P(a)$ but just control its uses with truncation. That is, from $q$ we may extract a representative proof $p$ of $P(a)$, so long as the choice of $p$ is irrelevant.
There is a cruicial difference between the third and the second situation, for having restricted access to $p$ is not at all the same as not having access at all. Here is a concrete example. Given $f : \mathbb{N} \to \mathbb{N}$, define
$$
Z(f) = \Sigma(x : \mathbb{N}) . \Pi (y : \mathbb{N}) . \mathrm{Id}(f(x + y), 0)
$$
An element of $Z(f)$ is a pair $(m, p)$ witnessing the fact that $f(n)$ is zero for all $n \geq m$. Given $f$ with this property, we want to define the sum $S(f) = f(0) + f(1) + f(2) + \cdots$, which of course should be a natural number since eventually the terms are all zero. But proof relevance matters:

We may define $S : (\Sigma (f : \mathbb{N} \to \mathbb{N}) . Z(f)) \to \mathbb{N}$ by
$$S(f, (m, p)) = f(0) + \cdots + f(m)$$

We may define $S : (\Sigma (f : \mathbb{N} \to \mathbb{N}) . \|Z(f)\|) \to \mathbb{N}$ by
$$S(f, |(m,p)|) = f(0) + \cdots + f(m),$$
where $|(m,p)|$ is the truncated witness of $Z(f)$. This is a valid definition because using a different representative $(m',p')$ leads to the same value (as we just end up adding fewer or more zeroes).

Imagining that in type theory we had proof irrelevant subset types
$$\frac{\vdash a : A \qquad \vdash p : P(a)}{\vdash a : \{x : A \mid P(x)\}}$$
we cannot define $S : \{f : \mathbb{N} \to \mathbb{N} \mid Z(f)\} \to \mathbb{N}$ because we have no information that would allow us to limit the number of terms $f(0), f(1), f(2), \ldots$ that need to be added. (There are other things we can do, but that is beside the point here.)

As long as one works in type theory, the only truly proof irrelevant judgements are judgemental equalities. We never define subset types, such as the one above, because that ruins many good properties of type theory (although it would be interesting to investigate this direction).
In the old days type theory did not have propositional truncation or any other form of quotienting, and so one was forced to work in a completely proof relevant way all the time. This is unsatisfactory because it fails to capture properly a great deal of mathematical reasoning. People invented setoids to deal with the problem, and later on introduced propositional truncation (and other forms of quotienting).
You ask wheter 1-categories are "proof relevant". Well, everything in type theory is proof relevant, the only question is how do we deal with having too much proof relevance. Concretely, in a 1-category $\mathcal{C}$, equality of morphisms $f, g : A \to B$ should be "irrelevant" in the sense that it never matter how $f$ and $g$ are equal, only that they are. In HoTT this is expressed by requiring that $\mathrm{Id}(f,g)$ have at most one element, which amounts to
$\mathrm{Hom}_\mathcal{C}(A,B)$ being an h-set.
In setoid-based formulations of category theory, one needs to account for this phenomenon in some other way, or else one is secretly doing something other than 1-category theory. But I never liked the setoid approach (or Bishop's notion of sets, for that matter), so I will let someone else explain why and how it all makes sense.


Automated proving that a program doesn't halt If you are a computer and you are given a program $P$ (with no input parameter) that doesn't halt, how would you try proving it doesn't halt ?  (here proving means convincing ourselves that it is true)
I guess most people would say to translate the statement " $P$ doesn't halt " into an arithmetic sentence $\forall n, S(n) \ne 0$ (where $S(n+1) = P(S(n))$ is the $n$-th state of the program) and enumerate the theorems of PA until it proves the sentence.  Or is there a more elegant way ?
Ie. how would you try (and success in) solving the halting problem, except in a few pathological cases  ?
Then I'd like to get some intuition on how to visualize (and solve) those pathological cases arising from undecidable problems (in PA). Is there a way to solve them (except in a $\scriptstyle\text{fewer}$ pathological cases) using a new routine enumerating the theorems of a meta-theory (which one) ?
Finally, is it hard to write the concrete code of all this, will it be readable and useful for teaching and for the intuition ?

Concretely I'm asking if this is the algorithm I'm supposed to think to, in that case can I find the concrete code of it somewhere :

Input : a program $P$ with no arguments. Let $ S(n+1) = P(S(n))$ be its sequence of states.
Compute $S(n),n=1,2,\ldots$. If for some $n ,S(n)=0$ then output "$P$ halts".
In the same time enumerate the parenthesized and annotated sentences of PA, where the annotation indicates which inference rules to apply, thus it is trivial to check if a given sentence is a valid theorem of PA and if it proves $\forall n, S(n+1) = P(S(n)) \land S(n) \ne 0$, in that case output "$P$ doesn't halt".
The other cases ($P$ doesn't halt but PA doesn't prove it) are said pathological.

In contradiction with Gurkenglas' answer, there actually is a community of scientists who work on proving non-termination of programs in various language and formalisms.

An obvious approach would be to check for looping non-termination: for a given program $w$, pick an input $x$ and check to see if the same state is reached twice with the same data.

Non-looping non-termination is obviously more complex, but has been studied, e.g. in Emmes & al Proving Non-Looping Non-Termination Automatically or Endrullis & al Proving Looping and Non-Looping Termination by Finite Automata.


Alternate proofs of Immerman-Szelepcsenyi theorem Immerman and Szelepcsenyi independently proved that $NL=coNL$. Using their technique of inductive counting, Borodin et al proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to Reingold's theorem ($SL=L$), Nisan and Ta-Shma proved $SL=coSL$, using logspace uniform projection reductions. A 1996 paper of Alvarez and Greenlaw states "A proof of $NL=coNL$ using techniques similar to Nisan and Ta-Shma's has not been achieved although such a proof would be very interesting". I am wondering if such a proof is found in the last 14 years. Are there any other alternate proofs of $NL=coNL$ ?

Since we don't seem to have any answers, can I make a comment?

Suppose we are given $n$ bits, $X=x_1,\cdots,x_n$ and we have to complement each bit to get $\neg x_1,\cdots, \neg x_n.$ The only constraint is that the circuit that does so should be monotone. We obviously need some additional information to do this and here is one such.

Suppose $k$ is the number of ones in the input and somehow we have this as advice. Then it is easy to see that $\neg x_i = Th^{n-1}_{k}(X-x_i)$ (i.e., on all inputs except $x_i$). Of course, the construction is monotone.

With this construction, the motivation for inductive counting is clear (at least to me). It is worth asking what other advice would work? I don't know of any other. But this may hold the key to your question.


Chomsky Schützenberger enumeration theorem In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is $\mathbb N$-algebraic, if the grammar is unambigious. In some other books the formulation is given, that the structure describing function $$f_L(x)=\sum_{n \in \mathbb N}l_nx^n$$ is algebraic over $\mathbb Q$ iff the grammar is unambigious, where $l_n = \vert \Sigma^n \cap L \vert$.
I understand that by replacing every terminal by the same terminal in the system of equations associated with a grammar $G$ it is possible, to obtain the structure describing function, but I couldn't find a proof anywhere,(and don't know how I could construct one)  that then the (analytical) power series $f_L(x)$ is not transcendental.

There is a proof in the book of Kuich & Salomaa, Semirings, Automata, Languages and another one in the paper of Panholzer, "Gröbner Bases and the Defining Polynomial of a Context-free Grammar Generating Function", J. of Automata, Languages and Combinatorics 10 (2005), 79–97.   I wish there were a simple and clear proof of the result.


Visualizing Unique Games How would you design a picture to illustrate the unique games conjecture?

This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be produced.

Example of the kind of illustrations produced in the past are at

http://www.ams.org/meetings/lectures/current-events-bulletin

and if you click on the 2006 edition you can see the picture that Madhu Sudan used to illustrate his talk on PCP.

I have thought about using the gadget reducing unique games to max cut, or the Khot-Vishnoi graph for reasonably small size. A good suggestion I received was to draw the label-extended graph of a nearly-satisfiable instance of unique games, and highlight in a different color the vertices corresponding to an optimal solution.

Other suggestions?

If I were going to illustrate unique games, I'd do something with a label-extended graph (similar to the suggestion you mentioned).

But specifically, I'd contrast the original constraint graph with the label-extended one. For instance, label edges in the constraint graph with the corresponding equation out of:

$x_1 - x_2 = 0\mod 3$

$x_2 - x_3 = 0\mod 3$

$x_3 - x_1 = 1\mod 3$

Then there will be a (hopefully visually appealing) "twist" between the $x_1$ and $x_3$ vertex clouds in the label-extended graph.


Complexity of finding vectors with optimal projection? Input: a set $T$ of vectors $v_i=(x_i,y_i,z_i)$. Where $x_i,y_i,z_i$ are integers.

Output: a subset of vectors $v_1,v_2,...,v_n$ with vector addition $m=\sum v_i$ such that the projection of $m$ on each axis is maximized. (maximize the absolute value of the minimum projection along any axis)

  Is this problem efficiently solvable or is it NP-hard?

I'm not aware of results related to the 2D case.

The problem is NP-Hard and the reduction is from partition.

So, assume you are given an instance of partition $S=${$x_1,\ldots,x_n$}. Let $t = (\sum_{i=1}^n x_i) / 2$. The question is whether there is a subset of $S$ such that its sum is $t$.

To this end, let $v_0 = (0, 2t, t)$ be a special vector. For every number $x_i$, create the vector

$v_i = (x_i, -x_i, 0)$,

for $i=1,\ldots, n$. Now, the claim is that there is a subset of the vectors with sum $\geq (t, t, t)$ (in absolute value) if and only if there is a subset of $S$ that add up to $t$.

So, consider a subset $X \subseteq S$, with $\alpha = \sum_{x\in X}$. We have that the corresponding sum of vectors (together with the special vector $v_0$) is

$(\alpha, 2t -\alpha, t)$.

Clearly, this vector is maximized when $\alpha=t$, as required.

Note, that you must include the special vector $v_0$ - otherwise the third coordinate would be zero in the sum of vectors.

QED

Note, that the problem is solvable in polynomial time if the numbers are polynomially small, doing dynamic programming (like the one used for solving subset sum if the numbers are small).

2d

If you set the special vector to be $(8t, 10t)$ then the above reduction would work verbatim in two dimensions. (The constant $8$ here is somewhat arbitrary...)


If the set of factors of an infinite word $\xi$ is regular, is this property stable under "shift's" of $\xi$? Let $\xi$ be an infinite binary sequence, and denote by $T(\xi)$ the set of all factors (infixes) of $\xi$. Also if $w$ is some finite prefix of $\xi$, denote by $\xi/w$ the unique $\eta$ such that $w \cdot \eta = \xi$, i.e. the tail of $\xi$ after deleting the prefix $w$. Is it possible that for $\xi$ we have two prefixes $u,v$ of $\xi$ such that
$T(\xi/u)$ is regular, but $T(\xi/v)$ is not regular?

Closely related to this question is, if $w \in X^*$ and $\xi$ is an infinite sequence, is $T(w\cdot \xi)$ regular if $T(\xi)$ is regular, and if $w$ is a prefix, does $T(\xi)$ regular imply that $T(\xi/w)$ is regular?

EDIT: I guess I have a proof that if $T(\xi)$ is regular, then $T(\xi/w)$ is regular too, but this is somewhat contrary to what Yuval Filmus wrote, so I would be grateful if someone would point out to me what might be wrong with my proof??

Okay, we introduce the notation $L / v := \{ u : vu \in L \}$ for $L \subseteq X^*$, the so called (right) quotient or derivative of $L$. First note that if $v$ is a prefix of $\xi$ then
$$
 T(\xi/v) = T(T(\xi)/v).
$$

  Proof: If $w \in T(\xi/v)$ then we have $vxw\eta = \xi$ for some $x \in X^*$. So $vxw \in T(\xi)$ or $xw \in T(\xi) / v$, which shows $w \in T(T(\xi)/v)$. For the other inclusion let $w \in T(T(\xi)/v))$, then $xwy \in T(\xi)/v$ for some $x,y \in X^*$, and by definition $vxwy \in T(\xi)$. If $vxwy$ is a prefix of $\xi$, then $xwy$ is a prefix of $\xi/v$ and we have $xwy \in T(\xi)/v$ and hence $w \in T(\xi)/v$. If $vxwy$
  is not a prefix of $\xi$, then the part $xwy$ must occur in $\xi/v$, as it begins behind the $|v|$-th position in $\xi$, hence $xwy \in T(\xi)/v$ and so $w \in T(\xi)/v$.

Okay, now the proof that $T(\xi)$ regular implies $T(\xi/w)$ is regular.

  Proof: I use that if $L$ is regular, then its set of factors $T(L)$ is also regular (I guess this is true). Then if $T(\xi)$ is regular, then $T(\xi)/w$ is regular if $w$ is a prefix of $\xi$ as regular languages are closed under quotients (this could be found in many textbooks). Taken together
  $$
 T(\xi/w) = T(T(\xi)/w)
$$
  is regular, as it is the set of factors of the regular language $T(\xi)/w$. QED

Let $A = \{0,1\}$ be a binary alphabet and let $L = A^* -\{0,1\}^*00\{0,1\}^* = (01,1)^*(\varepsilon + 0)$. I denote by $F(w)$ the set of factors of a word $w$ and by $P(w)$ the set of its prefixes.

Let $w$ be an infinite word such that $F(1w) = L$ and $P(1w)$ is nonregular. Then $F(001w) = L \cup 00P(1w)$. Since $L$ is regular and do not intersect $00P(1w)$, $F(001w)$ is not regular. You can use Yuval's approach to give an explicit construction: take an enumeration $u_0, u_1, ...$ of $L$ and consider a word $1w = 1u_01^2u_1 \dotsm 1^nu_n \dotsm$.


Largest set allowing one-step unstructured quantum search What is the largest set admitting a deterministic quantum search algorithm, for a single marked element, that operates with only a single call to the oracle?

The question is interesting since Grover's algorithm, which for unstructured search on an $N$-element set requires $O(\sqrt{N})$ calls to the oracle, can in fact search a 4-element set using only a single call.

In general, it is interesting to ask for the minimum number of calls to a quantum oracle required to deterministically search an unstructured set of size $N$ for a single marked element.

Note that Grover's algorithm is optimal up to a constant factor in the limit of large $N$, although of course that does not mean it is optimal for any given finite set.

Perhaps a more appropriate for your question: Dong Pyo Chi and Jinsoo Kim showed that for any "Grover-like" algorithm, in which we may change the phase of the diffusion operator and the oracle gate from $-1$ to possibly independent and arbitrary complex phases, a marked element can be found with a single query if and only if there are at least $N/4$ marked items. Here is a link to their article.

Note that the case $t=N/4$ was discovered earlier by Brassard, Boyer, Hoyer and Tapp.


Can boolean algebra be expressed in simply typed lambda caclulus? Boolean algebra can be expressed in untyped lambda calculus in (for example) this way.

true  = \t. \f. t;
false = \t. \f. t;
not   = \x. x false true;
and   = \x. \y. x y false;
or    = \x. \y. x true y;

Also boolean algebra can be encoded in System F in this way:

CBool = All X.X -> X -> X;
true  = \X. \t:X. \f:X. t;
false = \X. \t:X. \f:X. f;
not   = \x:CBool. x [CBool] false true;
and   = \x:CBool. \y:CBool. x [CBool] y false;
or    = \x:CBool. \y:CBool. x [CBool] true y;

Is there a way to express boolean algebra in simply typed lambda calculus? I assume that answer is NO. (For example, Predecessor and lists are not representable in simply typed lambda-calculus.) If the answer is NO indeed, is there a simple intuitive explanation, why it is impossible to encode booleans in simply typed lambda calculus?

UPDATE: We assume that there are base types.

UPDATE: The negative answer with explanation was found here (Comment "Here's a proof sketch to show that simply-typed lambda calculus with products and infinitely many base types does not have booleans.") This is what I was looking for.

The OP wrote above that the question is answered by a post on @AndrejBauer's blog.


Competing against an optimal weighted majority in experts algorithm In the experts problem, $n$ experts give you binary predictions on a daily basis, and you have to predict whether it's going to rain tomorrow.

That is, at day $t$, you know the past predictions of the experts, the actual weather for days $1,2,\ldots t$, and the predictions for tomorrows, and have to predict whether it will rain the next day.

In the classic Weighted Majority algorithm, the algorithm makes $O(\log n + m)$ mistakes, where $m$ is the number of mistakes of the best expert.

To me, this seems like an extremely weak promise, as it does not allow any benefit from combining predictions of several experts.

Assume that each outcome is $\{\pm 1\}$, prediction of expert $i$ on day $t$ is $p_{i,t}$, and the outcome of day $t$ is $o_t$. We can define an ``optimal weighted majority'' adversary as an optimal weight function $w\in\Delta([n])$, such that the decision made by the adversary on day $t$ is defined as $sign(w\cdot p_t)$, i.e. the weighted majority of the predictions, with respect to the vector $w$. Using this notation, the previous adversary (best expert) could only pick unit vectors.

We can then define the optimal error for days $1,2,\ldots T$ as:
$$E = \frac{1}{2}\min_{w\in\Delta([n])} \sum_{t=1}^T|sign(w\cdot p_t)-o_t|$$

  How would you minimize the regret, compared to $E$?

To see that this is a much more powerful adversary, consider the case of $3$ experts and $3$ days in which the outcome was always $1$.
If $p_1=(1,1,-1), p_2 = (1,-1,1), p_3=(-1,1,1)$, then each expert had a mistake, but a weighted majority vector of $(1/3,1/3,1/3)$ had none.

If you don't mind randomization, then standard online learning algorithms in the "online convex optimization framework" give you essentially what you ask for, in expectation. The reason is that these algorithms are required to output a distribution $w \in \Delta([n])$ on experts at each time step, suffering an expected loss equal to the expectation of picking an expert from this distribution. And they have low expected regret compared to the best distribution on experts, i.e. $O(\sqrt{\ln n / T})$.

For example, you can take the classic multiplicative weights algorithm, which is just weighted majority but picking an expert to follow with probability proportional to its "weight". This is mentioned in Arora's survey (Theorem 6): https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf


Standard format for representing large graphs I am aware of the "famous" DIMACS graph format (which frankly looks a little clunky to me - "c" for a comment line ?) and the METIS file format.

While it's not particularly hard to invent my own graph format, it's nice to follow something accepted so that reuse of code for generating examples and testing algorithms is easier.

  Is there a standard accepted format for representing graphs for use
  with testing graph algorithms ?

I do not think there's a single standard format. igraph library (http://igraph.sourceforge.net/) could be of use, however, as it supports reading/writing of number of different graph formats.


What are good references on understanding online learning? Specifically, I'm asking for resources to learn about machine learning systems that can update their respective belief networks (or equivalent) during operation. I've even run across a few, though I failed to bookmark them.

As you might imagine, it's a rather challenging topic to search for on the internet.

Most online learning algorithms come from at least one out of these lineages:

the perceptron

State of the art perceptrons are the passive-aggressive algorithm, the structured perceptron, and their many varieties.
The winnow

The winnow has been reformulated as exponentiated gradient methods, and can be applied to structured problems as well. There are also varieties that deal directly with L1 regularization (to guarantee sparsity), such as SMIDAS.
Stochastic gradient descent

Stochastic gradient descent is when you apply online optimization to a possibly batch problem. State of the art algorithms are Leon Bottou's LaSVM, Pegasos, and many neural network algorithms can be easily trained in this setting. See the theano tutorial for many examples. Maybe online EM fits here.
particle filtering

This is also known as rao-blackwellized inference, and it allows you to update a graphical/probabilistic model as more data arrives. Some good examples are online topic models and the NIPS tutorial on SMC.

There are also some broader issues with online learning, like online-to-batch conversion, budget techniques for online learning with kernels (like this paper, this paper, and this paper), many different flavors of generalization bounds, sparsity concerns (and also the SMIDAS paper I cited above), hashing to save memory, and many other issues.


Existence of solution for a system of multi-variate polynomial equations and in-equations Formally, I have 2 finite sets of polynomials :

$P = \{p_1, p_2, p_3, ...p_m\}$ and $Q = \{q_1, q_2, q_3, ...q_n\}$, where for $1 \leq i \leq m$, and $1 \leq j \leq n$, I have $p_i, q_j \in \mathbb{C}[x_1, x_2, \ldots x_k]$ (that is these are multivariate polynomials that can admit roots with possibly complex values for each of the variables) [although the coefficients can be assumed to be over $\mathbb{Z}$ or $\mathbb{Q}$]

What are the most efficient (having running time polynomial in the number of variables, and number of polynomials, but not necessarily the degree) algorithms to check for existence of a solution $\bar{u} = (u_1, \ldots, u_k) \in \mathbb{C}^k$ such that $p_i(u_1, \ldots, u_k) = 0$, and $q_j(u_1, \ldots, u_k)\neq 0$, for all $1 \leq i \leq m$, and $1 \leq j \leq n$.

P.S: For the specific problem I am looking into, the degree (maximum sum of powers of variables in any term) does not exceed 2.That is the polynomials, are in some sense, sparse.

Remark

The set of all such points in $\mathbb{C}^k$ is sometimes referred to as constructible sets, and I understand that an efficient algorithm for calculating GCD of multi-variate polynomials immediately yields an efficient algorithm for solving the above problem. I tried to do a (somewhat extensive) survey for relevant literature, but could not really find efficient algorithms (that run in time polynomial in the number of variables, and the number of polynomials).
Are there any efficient randomized algorithms ?

The question seems to be based on false premises, so let me try to deconfuse it.

Solvability of systems of polynomial equations with integer coefficients is NP-hard over any fixed field (or integral domain). For instance, it is straightforward to reduce the satisfiability of a 3-CNF $\phi(x_1,\dots,x_k)$ to the solvability of a polynomial system including $\{x_i^2-x_i:i=1,\dots,k\}$ and a bunch of polynomials translating each 3-clause.
Solvability of general polynomial systems with integer (or rational) coefficients is polynomially reducible to solvability of systems of multilinear degree-$2$ polynomials with coefficients in $\{-1,0,1\}$ and at most $3$ nonzero monomials each. To see this, express each polynomial by an arithmetical circuit (aka straightline program) using operations $+$, $\cdot$, variables, and constants $0,1,-1$. Introduce a new variable for each node in the circuit, and take the set of polynomials describing the value of each node in terms of its inputs.
The multivariate polynomial ring $K[x_1,\dots,x_k]$ (for a field $K$) is indeed a GCD domain, but for $k\ge2$ it is not a Bézout domain, hence the gcd’s do not behave the way you think they do. For example, the polynomials $x_1$ and $x_2$ have a common root $(0,0)$, even though $\gcd(x_1,x_2)=1$.

Thus, your problem is NP-hard, and as such it has no known polynomial-time algorithm (deterministic or randomized). Under plausible assumptions, it even has no subexponential-time randomized algorithm.

Furthermore:

Over a field, inequations can be replaced by equations: instead of $q(x_1,\dots,x_k)\ne0$, use $q(x_1,\dots,x_k)y=1$, where $y$ is a fresh variable.
Solvability of systems of polynomial equations (hence also inequations, by above) in $\mathbb C$ can be ckecked in PSPACE, due to Canny [1]. This is the best known unconditional result, but:
Assuming the Riemann hypothesis for Dedekind $\zeta$ functions, solvability of polynomial systems in $\mathbb C$ can be checked in the class AM, due to Koiran [2]. Moreover, we can derandomize AM to NP under plausible Nisan–Widgerson-style complexity assumptions, thus assuming both, the problem becomes NP-complete.

[1] John Canny, Some algebraic and geometric computations in PSPACE, Proc. 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 460–467.

[2] Pascal Koiran, Hilbert’s Nullstellensatz is in the Polynomial Hierarchy, Journal of Complexity 12 (1996), no. 4, pp. 273–286.


Knowing if there are two solutions to the subset sum problem I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are at least two or more solutions.
My thought is that potentially it is FNP, because the Another Solution Problem (ASP) for Subset Sum appears to be FNP (by reduction from 3SAT), but ASP assumes that at least one solution was already found. Is there a way to say something about the hardness of finding two solutions without prefacing that one was already found?

Your (self) answer is ok, but you can also build a reduction in which there is no "trivial" solution.
Start from $X = \{ x_{1}, \ldots, x_{n} \}, x_i > 0$ with target sum $K$ and build:
$X' = \{  8 * x_{1}, \ldots, 8 * x_{n} \} \cup \{ 1, 1, 2 \}$ and target sum $K' = 8*K + 2$
In this case in order to solve the new problem $\langle X', K' \rangle$ you are "forced to solve" the original one, and there are at least two solutions to $\langle X', K' \rangle$ if there is a solution to $\langle X, K \rangle$.


Examples of reversible computations Irreversible computations can be intuitive. For example, it is easy to understand roles of AND, OR, NOT gates and design a system without any intermediate, compilable layer. The gates can be directly used as they conform to human's thinking.

I have read a paper where it was stated that it is obviously correct way to code irreversibly, and compile to reversible form (can't find the paper now).

I am wondering if there exists a reversible model, that is as easy to understand as AND, OR, NOT model. The model should be therefore "direct" use of reversibility. So no compilation. But also: no models of form: $f(a) \rightarrow (a,f(a))$ (ie. models created by taking irreversible function $f$ and making it reversible by keeping copy of its input).

The paper you mention is probably one of Paul Vitányi's, possibly Time, Space, and Energy in Reversible Computing.

However, not everyone takes the viewpoint that simulation of irreversible computations is the main point. There is some research into what reversible computing can do in addition to such simulations, the beginnings of which is in Bennett's seminal paper Logical Reversibility of Computation on reversible Turing machines. See this paper for an elaboration of these ideas.

In terms of reversible logic circuits, there has been significant effort from the quantum computing community to build non-trivial circuits for arithmetic, e.g. Quantum networks for elementary arithmetic operations, some of which are purely classical, i.e., reversible. These implement a reversible variant of, say, addition, where one of the operands is conserved, but they do not rely on "irreversible thinking", do not use a history, and display a significant amount of ingenuity in their design.


Testing/Identifying a Topological Sorting You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the best algorithm that could identify the graphs among $G_1, G_2, ..., G_n$ that have $(v_1,v_2,...,v_m)$ as a topological sort? Could someone test whether $(v_1,v_2,...,v_m)$ is a topological sort of a DAG $G$ over $V$ in sub-linear time?

This can be done in nearly linear time.

Let the permutation be $\pi = (v_1,\dots,v_m)$, and let $k = k(\pi)$ be the number of steps needed to check a single edge $(u,v)$ against $\pi$.
It is then enough to check that each of the $M_i$ edges of $G_i$ is compatible with $\pi$, which can be done in $O(kM_i)$ time, or $O(k\sum M_i)$ overall.

By preprocessing $\pi$ one can reduce $k$ down to two lookups in an array containing $m$ entries each of $\log\, m$ size, and a comparison between two $(\log\ m)$-bit entries in the array; the array element $a[w]$ contains the index of $w$ in $\pi$ considered as an ordered list.  This means that $k = O(\log\, m)$ yielding $O((\log\, m)\sum M_i)$ time overall for the upper bound.

As @mjqxxxx points out, every edge of every graph may be relevant.  This creates a lower bound of $\Omega(K\sum M_i)$ steps, where $K$ is the least amount of work that needs to be done for every graph edge; it is possible that some approaches can amortize the cost so that $K = o(\log\, m)$.  This is still going to be $\Omega(\sum M_i)$ at best, so there is not much of a gap left.


The relationship between degree of vertex and size of dominating set I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has degree $\ge n^k \,(k< 1)$, is it possible to bound the size of dominating set, i.e $O(n^k)$? Could anyone point me out any materials/papers/books related to this problem?

If all vertices have degree at least $d$ then there is always a dominating set of size $\frac{n \ln n}{d} + 1$. Pick a random set $S$ of size $\frac{n \ln n}{d}$. For a particular vertex $v$, the probability that $v$ is not dominated by $S$ is upper bounded by $(1 - \frac{d}{n})^{\frac{n\ln n}{d}} \leq e^{-\ln n} = \frac{1}{n}$. Introduce an indicator variable for every vertex that is $1$ if it is not dominated by $S$ and $0$ otherwise. The number of undominated vertices is the sum of indicator variables, so the expected number of undominated vertices is at most $n \cdot \frac{1}{n} = 1$. Hence there exists a set of size $\frac{n \ln n}{d}$ that leaves at most one vertex undominated, add this vertex to the dominating set.

For your question it means that if all vertices have degree at least $n^k$ then there is a dominating set of size $n^{1-k}\log n + 1$. Would be nice to see if one can get rid of the $\log n$ or not.


Minimum graph cut with constraints Given an undirected acyclic raph $G = \{V,E\}$, with each edge $e$ having weight $c_e$in the range $[-\infty, +\infty] $, I want to compute a partition of the graph into $N$ disjoint sets $G_i, i=1,...,N$ by removing certain edges such that the overall sum of the remaining edge weights across all $N$ sets is minimized. In addition, I would like to set constraints that would force certain pairs of vertices to be in disjoint sets.

Formally speaking, if each set $G_i$ has $M$ edges $e_j, \hspace{2pt}j=1,...,M$, then:

$$min \sum_i^N\sum_j^Me_j$$

and $\mathbb{P}$ is the set of constraints which disallows certain pairs of nodes $v_k$ and $v_l$ from being assigned to the same set:
$$v_k \in G_k,v_l \in G_l \hspace{2pt} \land \hspace{2pt} k \neq l, \hspace{3pt}\forall (k,l) \in \mathbb{P}$$

I've searched around for this, and most minimum cut algorithms only seem to offer bipartite splits. I also looked into s-t cut algorithms, but in my case rather than having a single source and sink I have multiple such pairs that I want to keep in disjoint sets.

Additional Information I'm trying to model segments of walking trajectories as graph nodes. The edge weights denote the dissimilarity score between two trajectory segments (conversely, if I use the similarity score then I require the maximum cut). The constraints will be used to ensure that two trajectory segments that overlap in time must never be assigned to the same set.

The problem that you describe is NP-hard even on stars as we can reduce Multicut in Trees to its decision version (where we have a cost bound). In Multicut in Trees the input is a tree $G=(V,E)$, a set $S\subseteq {V\choose 2}$ of vertex pairs, and an integer $k$ and one asks whether one can separate all vertex pairs of $S$ by removing at most $k$ edges. The reduction to your problem is to keep $G$ and $S$ as they are, set $N$ to $k+1$ and set the cost bound for accepting a solution to $+\infty$. Then the Multicut instance is a yes-instance if and only if the constructed instance is a yes-instance.

Note that this reduction does not specify how to define the edge weights. In other words, even testing whether there is a feasible solution, that is, any partition with $N$ parts is NP-hard.


On Bipartite planar graph (again) Given $n$ vertices of color $1$ and m vertices of color $2$, what is the maximal number of edges that can join them on the constraints - $(a)$ no edge joins has the same color ends and $(b)$ no two edges intersect when drawn on a plane (a planar graph)?

Also given such $n$, $m$ how many such graphs can be generated so that no vertex is isolated and how many maximal non-equivalent maximal graphs are possible?

Are these standard questions that have been studied anywhere?

$n = m$ is the case I am looking for a lead.

If $\min(m,n)=1$, the maximum number of edges in a planar bipartite graph with $m$ vertices on one side of the bipartition and $n$ on the other side is $m+n-1$ (just connect them in a star). Otherwise, the maximum number is $2(m+n)-4$.

The upper bound (any bipartite planar graph with $V$ vertices has at most $2V-4$ edges) follows by combining Euler's formula $V-E+F=2$ with the observation that all faces have at least four edges, and each edge belongs to at most two faces, so $E\ge 2F$. Use this inequality to eliminate $F$ from Euler's formula and you get $E\le 2V-4$.

For the lower bound, choose two vertices from the side with $m$ vertices and form a complete bipartite graph $K_{2,n}$ with $2n$ edges. Then, choose one of the quadrilateral faces of this graph and place the remaining $m-2$ vertices into it, connecting each one to both of the vertices of the other color within the same face, adding $2(m-2)$ more edges.

As for the number of distinct maximal planar bipartite graphs on this many vertices, I don't know, but it's certainly some kind of exponential.


Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense of HOW the two scale as you increase entropy? Is this a silly question because I'm missing some piece of the puzzle?

This is my (somewhat unorthodox) answer to the comparison between Huffman. Huffman and arithmetic codings. A Huffman code is only optimal if the frequency of the letters in the input alphabet are $2^{-k}$, for an integer $k$. Otherwise, there are internal nodes in the coding tree whose children have different weights. As a result, the output bit stream does not have an entropy of 1 bin/output bit.

One solution is to combine the input letters into groups and enlarge the alphabet. For example, instead of coding a byte stream (as is usually done), you can combine two bytes into a word and use a larger coding tree for the combined alphabet. The problem is that the size of the tree (e.g. instead of $2^8$ entries, now you have to deal with $2^{16}$ entries). And this is just the beginning.

One may view the arithmetic coding as taking this idea to the extreme. Instead of combining two input letters, here we combine all of them. Of course, now the coding tree is huge and cannot be explicitly built. The details of arithmetic coding deals with generating and traversing a virtual Huffman tree for this combined alphabet.


Difference between NP-Hard and NP-Complete Can someone please summarize the exact difference between NP-Complete and NP-Hard problems in simple language? Wiki and my standard books aren't exactly helping.

A NP-complete problem is an NP-hard problem which is in NP.


Formula size lower bounds for AC0 functions Question:

  What is the best known formula size lower bound for an explicit function in AC0? Is there an explicit function with an $\Omega(n^2)$ lower bound?

Background:

Like most lower bounds, formula size lower bounds are hard to come by. I am interested in formula size lower bounds over the standard universal gate set {AND, OR, NOT}.

The best known formula size lower bound for an explicit function over this gate set is $\Omega(n^{3-o(1)})$ for a function defined by Andreev. This bound was shown by Håstad, improving Andreev's lower bound of $\Omega(n^{2.5-o(1)})$.
Another explicit lower bound is Khrapchenko's $\Omega(n^2)$ lower bound for the parity function.

However, these two functions are not in AC0. I'm wondering if we know an explicit function in AC0 with a quadratic (or better) lower bound. The best bound I am aware of is the $\Omega(n^2/\log n)$ lower bound for the Element Distinctness function, as shown by Nechiporuk. Note that the element distinctness function is in AC0, so I'm looking for a lower bound for an explicit AC0 function that is better than $\Omega(n^2/\log n)$, preferably $\Omega(n^2)$.

Further reading:

An excellent resource on the topic is "Boolean Function Complexity: Advances and Frontiers" by Stasys Jukna. A draft of the book is available for free on his website.

A nice question! Khrapchenko can definitely not give quadratic lower bounds for $AC^0$ functions. His lower bound is in fact at least square of average sensitivity. And all functions in $AC^0$ have poly-logarithmic average sensitivity. Subbotovskaya-Andreev can apparently also not give such a function because the argument they use (random restriction results in much smaller formulas) is exactly the reason forcing large $AC^0$ circuit size; Hastad's Switching Lemma (am not quite sure, just an intuition). The only hope is Nechiporuk. But his argument cannot give more than $n^2/\log n$, by information theoretic reasons. So, can it be that everything in $AC^0$ has formulas of quadratic (or even smaller) size? I don't believe in it, but couldn't quickly find a counterexample.

Actually, the Allender-Koucky phenomenon arises also in other context - in graph complexity. Say that a circuit of $2n$ variables represents a bipartite $n\times n$ graph $G$ on vertices $V=\{1,\ldots,2n\}$ if for every input vector $a$ with exactly two 1s is, say, positions $i$ and $j$ ($i\leq n$, $j>n$) the circuit accepts $a$ iff vertices $i$ and $j$ are adjacent in $G$. Problem: exhibit an explicit graph $G$ requiring at least $n^{\epsilon}$ gates to be represented by a monotone $\Sigma_3$-circuit. Seems like an innocent question (since most graphs require about $n^{1/2}$ gates. But any such graph would give us a boolean function of $2m=2\log n$ variables requiring non-monotone log-depth circuits of superlinear size (by results of Valiant). Thus, even proving $n^{\epsilon}$ lower bounds for depth-3 circuits may be a challenge.


Counting subsets of given set with certain properties Consider the following problem: Given is a multiset of positive integers, $S$, and an integer $k$.
Count submulisets of $S$ of size $k$, $\{s_1,\dotsc,s_k\} \subseteq S$,
such that when the $s_i$ are ordered increasingly, $s_i \geq i$.

Can this problem be done in polynomial time (polynomial in size of $S$)?

Background: This is a very special case of counting independent subsets of a graph, (which is hard), but I suspect this special case might be solvable via some clever dynamic programming.

If $S = \{2,2\}$ and $k=1$, the answer is $2$, the following dynamic program works.

Let $S = \{a_1,a_2,...,a_{|S|}\}$ where $a_i \leq a_{i+1}$. Consider the function $DP(i,n)$ as the number of satisfying subsets ending with element $i$ of length $n$. A satisfying set is a set $T = \{s_1,s_2,...,s_{k'}\}$ with the property $i \leq s_i \leq s_{i+1}$.

Hence, $DP(i,n) = 0$ if $a_i \leq n$, $1$ if $n = 1$. Otherwise, $DP(i,n) = \sum_{j=1}^{i-1} DP(j,n-1)$. The answer will then be $\sum_{j=1}^{|S|} DP(j,k)$.

If indeed for the case  $S = \{2,2\}$ and $k=1$, the answer is $1$. A small modification to the above recurrence is possible. Consider a representation of a multiset $S$ in the form $\{(a_1,b_1),(a_2,b_2),...,(a_n, b_n)\}$ where $a_i < a_{i+1}$ and $b_i$ is the number of copies of $a_i$ in $S$.