Find shortest prefix to generate original string by overlapping Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed).

For example, if $S = atgatgatatgat$, I want to find $P = atgat$; $P$ is the smallest prefix of $S$ that can be concatenated (in this case three times, starting at indices $\{0,3,8\}$ of $S$, where the first and second copies overlap but the second and third copies do not overlap) to equal $S$.

Obviously, there is an $\mathcal{O}(n^2)$ algorithm by checking each prefix of $S$, but a colleague mentioned it might be possible to do it in $\mathcal{O}(n \log n)$. I'm thinking of using suffix arrays for different prefixes of $S$ but haven't quite been able to proceed from there.

You are asking about "quasiperiodicity".   This is a well-studied topic and a google scholar search will turn up many papers about it.  For example, there is an $O(n (\log n)^2)$ algorithm
here and an $O(n \log n)$ algorithm here.


A promise problem to decide whether two given pure quantum states are close or far apart Consider this problem in quantum cryptography:

We have two pure states $\phi_1,\phi_2$ as input and constants $0 \leq \alpha <\beta \leq 1 $, where "Yes instances" are those for which $$\left|\left<\phi_1,\phi_2\right>\right| \leq \alpha$$ and "No instances" are those for which $$\left|\left<\phi_1,\phi_2\right>\right|\geq \beta$$

I need to devise a quantum circuit that accepts "Yes instances" with probability at least $p$, and "No instances" with at most probability $q$ for some $q<p$.

How can I do this? Is there a reference in which this problem is solved?

Thanks in advance.

A standard tool is the swap test, which receives two unentangled pure states |φ1⟩ and |φ2⟩ and answers “equal” with probability (1+|⟨φ1|φ2⟩|2)/2 and “not equal” with probability (1−|⟨φ1|φ2⟩|2)/2.  See [BCWW01] (Figure 1 shows the circuit).

[BCWW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  Physical Review Letters, 87, article 167902, Sept. 2001.  DOI: 10.1103/PhysRevLett.87.167902.  A preprint version: arXiv:quant-ph/0102001v1.


Complexity of finding semi-ordered Eulerian tours in a 4-regular graph I'm trying to figure out the time-complexity of the problem I describe below, which I call the semi-ordered Eulerian tour problem or the SOET problem. Either finding an efficient algorithm for this problem or proving that this is actually in NP-hard would settle this question for me. Below I describe the problem, give two examples of instances to the problem and explain what I have realized so far. To be precise, my questions are:

What is the time-complexity of this problem?
Is this problem NP-hard?
If it exists, what is an algorithm that solves this problem in polynomial time in terms of both $n$ and $k$? (see below)

The SOET problem

Given a 4-regular graph $G=(V,E)$, i.e. a graph where each vertex have degree 4, the problem is to find a semi-ordered Eulerian tour (defined below). Note that the graph is not assumed to be simple, so multi-edges and self-loops are allowed.

Definition (semi-ordered Eulerian tour):
Let $S\subseteq V$ be a subset of the vertices in $G$ and $s=s_1s_2\dots s_k$ be a permutation of $S$. The Eulerian tour $U$ is a semi-ordered Eulerian tour with respect to $S$ if, $U=As_1Bs_2\dots s_kXs_1Ys_2\dots s_kZ$ for some $s$ and where $A,B\dots,X,Y,\dots,Z$ are words with letters in $V\setminus S$. That is, $U$ traverses $s$ in some order once and then again in the same order. To be clear, which specific $s$ that satisfies this is unimportant.

Note that since $G$ is 4-regular an Eulerian tour always exists and furthermore it will pass each vertex exactly twice.

Examples

Here I give two examples of 4-regular graphs. The first one, G_1, there is a SOET with respect to $\{a,b,c,d\}$, since there is a Eulerian tour $U=abcdaebced$. In the second example, G_2, there is none.

Current status

I have realized that this problem is at least fixed-parameter tractable in terms of $k$, i.e. there is an algorithm with time-complexity $\mathcal{O}(f(k)p(n))$, where $k=|S|$, $n=|V|$ and $p$ is some polynomial. This can be seen by mapping the problem to $k!k^3$ edge-disjoint paths problems (DPP) where you try to find paths between pairs of vertices in $S$. This has to be done for all permutations of the vertices in $S$, the reason for the factor $k!$ in the number of DPP:s. Furthermore each vertex has to be split into two vertices and connected by edges in one out of three ways (vertically, horizontally or diagonally), to actually give a Eulerian tour. This are in total another $3^k$ DPP:s. Note that this does not necessarily exclude the possibility of an algorithm which is also polynomial in $k$.

Note regarding duplicate:

I have also asked the same question on MathOverflow but after two weeks of no response I thought that this might be the better place for this question.

The SOET problem is NP-Complete as we show in the following paper:

Axel Dahlberg, Jonas Helsen, Stephanie Wehner, How to transform graph states using single-qubit operations: computational complexity and algorithms,
 CoRR abs/1805.05306 (2018).

See Corollary 3.4.1


Why not include private randomness in internal communication information definition? I am using https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf as a reference.

This isn't exactly a research question but I can't find a good place to ask it.

Suppose we have $f:X\times Y \to Z$, $u$ a distribution on $X\times Y$, and $\delta >0$.

Now consider communication protocols that allow both public and private randomness- this means a distribution (the public randomness) on a set of computation trees, each node of which has a player's name, and two edges outgoing marked by $0,1$, and the node gets as info the private randomness of that player; the leafs have no player's name, and instead just contain the output of the protocol (an element of $Z$).

If $\prod$ is a protocol computing $f$ with at most $\delta$ error (the probabiliy space is over both inputs, public and private randomness), we let abuse of notation use $\prod$ as a random variable of a string of what they players said in addition to the public randomness (to clarify, it's a pair ($R,T$) where $R$ is the public random and $T$ the transcript). We can define its external information complexity to be $I_{u,\delta}(X,Y;\prod)$.

We also define the internal information complexity to be

$I(X;\prod|Y)+I(Y;\prod|X)$, intuitively the first summand should be what player $B$ (who got $Y$) learns about $X$, and similiarly for the second.

What confuses me is shouldn't we also condition on the private randomness here?

I.e $I(X;\prod|Y,PR(Y))+I(Y;\prod|X,PR(X))$

I agree that the definition you suggest is more natural. However, this definition is equivalent to the definition without the private randomness, so I assume they omit the private randomness just to have a shorter notation.

To see the equivalence, observe that
\begin{eqnarray}
I(X; \Pi | Y, PR(Y) ) &=& I(X; \Pi, PR(Y) | Y ) - I(X; PR(Y) | Y ) \\
& = & I(X; \Pi, PR(Y) | Y ) \\
& = & I(X; \Pi | Y ) + I(X; PR(Y) | Y, \Pi ) \\
& = & I(X; \Pi | Y )
\end{eqnarray}
Here, the first and third equalities follow from the chain rule, the second equality follows since $X$ and $PR(Y)$ are independent even conditioned on $Y$, and the fourth equality follows $X$ and $PR(Y)$ are independent even conditioned on $Y$ and $\Pi$.

The last independence takes a bit of effort to verify, but it basically follows from the rectangle property of protocols (and one also needs to note that conditioning on $Y$ severs the possible dependence of $X$ and $PR(Y)$ given $\Pi$). A bit more specifically, observe that conditioned $\Pi$ and $Y$, the set of values of $X$ and $PR(Y)$ that are consistent with $\Pi$ and $Y$ form a rectangle. Since $X$ and $PR(Y)$ started as independent variables, conditioning them on being in this rectangle preserves their independence.


Are there any implementations of a graph crossing algorithm? This is much more focused version of this question:

Are there good implementations for easy subclasses of NP-hard graph problems

Computing the graph-crossing number $cr(G)$ for a simple graph is known to be NP-complete. A quick literature review shows some suggested algorithms for computing if $cr(G)<k$. Are they any active implementations available?

Already checked: SAGE, CGAL_Boost, networkx, graph_tool

A slow brute-force implementation of the graph crossing number
was added to Sage in

Sage Trac ticket 24216: Add crossing number of a graph

which was closed 2018-01-05, and merged in Sage 8.2.beta3.


On the paper "Quantum Computing Hamiltonian cycles" The paper Quantum Computing Hamiltonian cycles claims:

An algorithm for quantum computing Hamiltonian cycles of simple,
cubic, bipartite graphs is discussed. It is shown that it is possible to
evolve a quantum computer into an entanglement of states which map
onto the set of all possible paths initiating from a chosen vertex, and
furthermore to subsequently project out all states not corresponding to
Hamiltonian cycles.

The algorithm requires polynomial in $n$ qubits and gives
example with a quantum "gadget".
According to graphclasses
on bipartite ∩ maximum degree 3 graphs hamiltonian cycle is NP-complete.
cstheory claims

Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem

Since cubic planar bipartite graphs are subset of cubic bipartite
graphs, hamiltonicity of cubic bipartite graphs must be NP-hard too.
Doesn't the above arguments show that quantum computer can solve
NP-complete problem, including SAT, which appears to be open problem?
Can the paper be extended to other subclasses of graphs for which
hamiltonicity is NP-hard?
Bugs me the date of the paper is 29th February 1995 and this date
doesn't exist, since odd year can't be leap year.

I emailed the author.
He replied "yes that paper is wrong!".
He has lost the passwords to remove it from the web.


Simulating nondeterministic space-bounded computation using randomness Let's suppose that a language $L \in$ NSPACE($f(n)$) where $f(n)$ is $O(\log n)$. And now let's suppose that I have a probabilistic Turing machine. Can this machine run in $O(f(n))$ space and answer yes when $x \in L$ with $\Pr(yes) > 1/2$ and answer no when $x \not\in L$ with $\Pr(no) = 1$? Let's suppose I dont care about time as long as the machine halts.

My comment was incorrect, and in fact the answer to your question is YES. From Wikipedia:

  Suppose C is the complexity class of
  problems solvable in logarithmithic
  space with probabilistic Turing
  machines that never accept incorrectly
  but are allowed to reject incorrectly
  less than 1/3 of the time; this is
  called one-sided error. The constant
  1/3 is arbitrary; any x with 0 ≤ x <
  1/2 would suffice.

  It turns out that C = NL. Notice that
  C, unlike its deterministic
  counterpart L, is not limited to
  polynomial time, because although it
  has a polynomial number of
  configurations it can use randomness
  to escape an infinite loop. If we do
  limit it to polynomial time, we get
  the class RL, which is contained in
  but not known or believed to equal NL.


Constraint terminology If we want to pick a solution $S$ from a collection of items $C$ to maximize some function $f(S)$.

The constraint that we pick at most $k$ item, i.e., $|S| \leq k$, is called  the cardinality constraint.

If the items in $C$ belongs to different groups and we are allowed to picked at most $k_i$ items from group $i$, what is the right terminology for this constraint? I think some paper used to call it the group cardinality constraint but I'm not sure if it's still the popular terminology.

To be clear that I understand the context, I'm going to first reproduce you situation worded differently.

  Consider a sequence of sets, $C_i$, and a target function, $f$. Let $\cup C_i=C$. We wish to find a subset $S\subseteq C$ that maximizes $f(S)$ under the constraint that $\forall i, |S\cap C_i|<k_i$ and $|S|<k$.

I would agree with the commenter that this should be referred to as a cardinality constraint or a collection of cardinality constraints. I might also call it a "structural constraint," but I would specifically avoid calling it a "group carnality constraint" as "group" already has a meaning. In general, I would advocate for avoiding referring to a collection as a "group," "set," or "class" unless your object actually satisfies the required axioms. "Collection" is a good, general word that doesn't have a mathematical meaning.

If you don't want to use the term "carnality constraint" you can always introduce a term to refer to this specific restriction in your context. This can be helpful because it allows you to highlight the context-sensitive meaning of the constraint in a way that a more general term doesn't. For example, I have a paper with a constraint of this form that I refer to as an "isolation condition" because, when $S$ satisfies it, $S$ is isolated from the structure of the rest of the graph in a relevant way. This gives me a simple and intuitive way to refer to the condition, while simultaneously telling the reader what is important about the condition every time it comes up.


Intermediate problems between L and NL It is well-known that directed st-connectivity is $NL$-complete. Reingold's breakthrough result showed that undirected st-connectivity is in $L$. Planar directed st-connectivity is known to be in $UL \cap coUL$. Cho and Huynh defined a parametrized knapsack problem and exhibited a hierarchy of problems between $L$ and $NL$.

I am looking for more problems that are intermediate between $L$ and $NL$ i.e., problems that are :

known to be in $NL$ but not known (or unlikely) to be $NL$-complete and
known to be $L$-hard but not known to be in $L$.

The RL-complete problem of reachability in directed graphs with polynomial mixing-time (shown by Reingold, Trevisan, and Vadhan in Pseudorandom walks on regular digraphs and the RL vs. L problem) is in $\log^{3/2}(n)$ space (see $\text{BPHSPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$ by Saks and Zhou), which is strictly between L and Savitch's bound on NL of $O(\log^2 n)$ space.


Are edge-vertex graphs of polytopes (decent) expanders? This question is inspired by the polynomial Hirsch conjecture (PHC). Given a $n$-facet polytope $P$ in $\mathbb R^d$, is the spectral gap of its edge-vertex graph (call it $G$) lower bounded by $\Omega(1/\mathrm{poly}(n))$? Note that the cycle graph on $n$ vertices shows that, even for $d=2$, the spectral gap could be as small as $O(1/\mathrm{poly}(n))$; so the conjectured bound--if true--would be almost tight.

A yes answer would imply the PHC. In fact, it would also imply that linear programs can be solved efficiently by just a random walk on the polytope vertices, and this algorithm is not even paying much attention to the objective function! This seems too good to be true.

So, what is the status of this problem: open (like PHC), or false? If false, are there simple counterexamples?

Note: I just realized about the usual complications involved in defining expanders: $G$ need not be regular or bipartite. I hope that both of these technical issues can be overcome using standard ways, and that, in particular, they do not make my question trivial. (Please correct me if I am wrong!)

For 0/1-polytopes (all vertex coordinates are 0 or 1), this is not known to be true.  There is a conjecture by Mihail and Vazirani that the edge expansion of the graph of a 0/1-polytope is at least one.  More information is described in a paper by Volker Kaibel.

I should note two things.  (1) For 0/1-polytopes, the Hirsch conjecture is true.  (2) When performing a random walk on the vertices of a polytope, we need to take care of possible degeneracy.  One vertex can correspond to a lot of bases, and so the walk can stay at the same vertex if we perform a random walk over the bases.  If we want to perform a random walk over the vertices, we need to have a procedure that gives a random adjacent vertex.


Hardness of Subgraph isomorphism problem for sparse pattern graph Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ time assuming ETH. The easiest way to see this is to consider $G$ to be a clique and recall that $k$-clique problem requires $n^{\theta(k)}$ under ETH [1].

On the positive side, if $G$ is a path, a tree or a collection of small identical graphs we know how to solve Subgraph isomorphism in $f(|G|) |H|^{O(1)}$ time [2,3]. All these graphs are sparse, however I'm unaware of a general algorithm that runs in time $f(|G|) |H|^{O(1)}$, for all sparse graphs $G$.

My question is: do we know any conditional lower bounds for Subgraph isomorphism for sparse pattern graphs?

[1]Chen, Jianer, et al. "Tight lower bounds for certain parameterized NP-hard problems." Information and Computation 201.2 (2005): 216-231.

[2]Koutis, Ioannis, and Ryan Williams. "Limits and applications of group algebras for parameterized problems." International Colloquium on Automata, Languages, and Programming. Springer Berlin Heidelberg, 2009.

[3]Fellows, Mike, et al. "Finding k disjoint triangles in an arbitrary graph." International Workshop on Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2004.

It is $W[1]$-hard even when $G$ has maximum degree $3$, but $FPT$ if $G$ has constant treewidth (all the above examples have constant treewidth). See the paper Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask) by Marx and Pilipczuk.

Indeed, it follows from an earlier paper of Marx: Can You Beat Treewidth? Theory of Computing 6(1): 85-112 (2010) that a $f(k)n^{o(k/\log k)}$
time algorithm would violate the ETH. Here $n$ is the number of vertices in $H$ and $k$ is the number of vertices in $G$. This holds even when $G$ has max degree $3$ (but the degree of $H$ is unbounded).


PAC algorithms for APX-Hard problems Do there exist polynomial time algorithms that admit Probably Approximately Correct (PAC) bounds for APX-Hard problems? That is, does there exist a problem $P$ that is APX-Hard, such that for every $\epsilon, \delta > 0$, we have an algorithm that runs in polynomial time in $n$ that gives a $1 + \epsilon$ approximation to it with probability $1 - \delta$. Note that the randomness is not dependent on the instance of $P$ given, but some randomness of the algorithm.

If you had an approximation algorithm for an APX-hard problem which for any $\epsilon, \delta >0$ runs in polynomial time and approximates the problem within a factor of $1+\epsilon$ with probability $1-\delta$, then $\mathsf{NP} \subseteq \mathsf{BPP}$.

The reasoning is very similar to Chandra's answer to another question. APX-hardness for a problem $P$ implies that there is a PTAS reduction from instances of MaxSAT to instances of $P$: for every $\epsilon$, approximating Max3SAT to within a factor of $1+\epsilon$ is polynomial-time reducible to approximating $P$ to within a factor of $1 + c(\epsilon)$. By the PCP theorem, there is a constant $\epsilon_0$ such that the promise problem of distinguishing between satisfiable 3SAT instances and instances where at most a $1-\epsilon_0$ fraction of the constraints can be satisfied is NP-hard (in fact $\epsilon_0$ can be taken arbitrarily close to $1/8$, which is tight). Call this NP-hard promise problem $\text{Gap3SAT}(1, 1-\epsilon_0)$. The PTAS reduction from Max3SAT to $P$ with small enough $\epsilon$ (i.e. $\epsilon < \frac{\epsilon_0}{1-\epsilon_0}$), together with the algorithm with "PAC guarantees", give a BPP algorithm for $\text{Gap3SAT}(1, 1-\epsilon_0)$, which implies a BPP algorithm for any problem in NP.


Necessary and sufficient number of comparisons by every element to fully sort a set of n elements? Given $n$ distinct elements.

Is there a sorting algorithm which ensures that every element is compared atmost $\lg n$ time?

Or is there a higher lower bound?

Note that in a sorting network, the number of times an element is compared is bounded by the depth of the network. There are several simple sorting networks of depth $O((\log n)^2)$. The AKS network has a depth of $O(\log n)$ with a huge constant (according to Wikipedia).


Presenting work-in-progress (slides now available) Presentation now given. Slides available below.

Presenting work-in-progress is something we all should do in order to obtain early feedback and to help crystallize our ideas. Unfortunately, many graduate students need help getting over this hurdle of presenting early research, even if it is only to their own research group. I will be giving a talk about presenting work-in-progress to our graduate students, and I'd like to get some input on what sort of advice I should give them to help them be more willing to share their work.

What tips can you offer on presenting work-in-progress?
How should the presented deal with the fact that the ideas are not entirely clear in his/her head?

I'm not so concerned about the work being stolen, as presentation will occur locally. I'd like to know how to get students to present such work and how they best can do it.

The students' work is generally of a formal nature, rather than describing systems, so I hope that this question is relevant here. If you feel that this is out of scope please do say so.

Resulting Presentation.

Here is the outcome. I am very grateful for your input, which you can see was useful.

It sounds from your question (the use of the word 'willing') that one deterrent is the unwillingness of students to present. Since it's in your research group, I'm assuming that being scooped is not something they need to worry about :). So the real reason is that they feel afraid: of seeming clueless, of not knowing the answer and having someone else find it in 5 minutes after they start presenting, or of people deeming their ideas to be uninteresting.

In other words, the imposter syndrome.

One of the most important transitions a grad student has to go through is the point when they realize that they can actually play in the research world, and make contributions of their own. This often comes when their first paper gets published, but can also happen the first time they talk to a "senior" researcher and realize they know more than that person about their topic of interest, or even the first time they prove a brand new result.

One advice for you might be to give such talks of your own, where you show "how the sausage is made" and show how ill-formed your own initial ideas might be. That gives them a model to work with. At the very least, you can give them examples of the winding path a research project takes.

A second advice you can give them is to remember that most likely no one knows as much about their problem as they do. They may not internalize this just yet, but repeated reminders might help :)

When they actually give the talk, Sylvain's advice is very good: however I don't think the 1/3 rule applies here since in your research group there are probably no outside experts and probably no generic audience. But I'll mention a line I heard yesterday in the context of journalism, but which applies very well for talks by inexperienced people:

  Don't overestimate the audience
  knowledge, and don't underestimate
  their intelligence.

In other words, provide all the background they need, and more. But don't prove teeny little lemmas from scratch.


How hard is recognizing a permutation that is a square for the shift product? This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation problem (How hard is reconstructing a permutation from its differences sequence?) which turned out to be NP-complete. Here, I propose another computational problem which I highly suspect that it is NP-complete.

The shift of a permutation $\pi(i)$ of numbers $1, 2, \ldots n$ is defined as $\sigma(i)$= $\pi(i+k \mod n)$ for some fixed $k$,  $1 \le k \lt n$. The shift product of a permutation $\pi$ is defined as $ \pi(i+k \mod n) \circ \pi(i)$. We say that a permutation $\pi$ is a square for the shift product if there is a permutation $\tau$ such that $\pi$ is the shift product of $\tau$ (i.e. $\pi(i)=  \tau(i+k \mod n) \circ \tau(i)$).

I did not find a notion of shift product for permutations in the literature.

Formally,

Square Permuation

Instance: A permutation $\pi$ of $1, 2, \ldots n$

Question: Is permutation $\pi$ a square for the shift product?

  Is there an efficient algorithm to determine whether a given permutation $\pi$ is a square for the shift product of some permutation $\tau$, or is it NP-complete?

The problem appears to be hard even when the shift amount $k=1$.

This was posted on mathOverflow.

It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&2&\ldots&n\\ (k+1)\bmod n&(k+2)\bmod n&\ldots&(k+n)\bmod n\end{matrix}  \right)$$ be the shift permutation. Then the shift of $\tau$ is just $\sigma = \tau \circ \rho_k$, and the shift product of $\tau$ is $\tau \circ \rho_k \circ \tau$. But $$\pi = \tau \circ \rho_k \circ \tau \iff \rho_k \circ \pi = (\rho_k \circ \tau)^2$$

Given $\pi$ you can find $\rho_k \circ \pi$ in linear time, and then you just need to see whether it has a square root, which can also be done in linear time.


When is hypertree width more useful than generalized hypertree width? In analysis of CSPs, there are three width notions that are analogous to treewidth: hypertree width (hw), generalized hypertree width (ghw) and fractional hypertree width (fhw). Moreover the inequalities $\text{fhw} \le \text{ghw} \le \text{hw}$ are known. The only motivation for hw instead of ghw that I have seen is that there is an XP algorithm for computing hw, but not for computing ghw. Is there any other motivation for hw instead of ghw? More concretely:

What algorithmic results there are that work when a hypertree decomposition of the smallest width is given, but not when a generalized hypertreewidth decomposition of the smallest width is given?

Every XP/FPT algorithm parametrized by htw also gives an XP/FPT algorithm parametrized by ghtw (provided that the decomposition is given in the input)  since there is a linear relation between ghw and hw [1]: $\mathsf{hw} \leq 3\mathsf{ghw}+1$. So basically, you can see hw as a easier to compute constant approximation of ghw.

I am not aware however of problems that are XP when parametrized by hw but not by fhw.

Side note however: if you are only interested in problems when the input is a CSP (with positive encodings) / Database of bounded (f)hw, then an XP algorithm for htw will often give you an XP algorithm for fhw.

Indeed, if the algorithm is XP for hw, then it is polynomial on $\alpha$-acyclic hypergraphs, that is, hypergraphs of hw $1$. Now, if you perform the join of the guards inside each bag of the (fractional / generalized) hw decomposition then you get a new CSP / Databases that is $\alpha$-acyclic. Moreover, each new relation is of XP size in the original DB/CSP. Now if you can rewrite your problem on this new database, this directly give you an XP algorithm for fhw.

[1] I. Adler, G. Gottlob, and M. Grohe.  Hypertree width and related hy-pergraph invariants.European  Journal  of  Combinatorics, 28(8):2167– 2181, 2007.  24


Euclidean-squared max-cut in low dimensions Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that is at least $\frac 2 3$ of the total weight? If not, which constant should replace the $\frac 2 3$?

The worst example I'm able to find is 3 points on an equilateral triangle, which achieves the $\frac 2 3$. Note that a random split would produce $\frac 1 2$, but it seems intuitively obvious that in low dimensions, one can cluster better than randomly.

What happens for max-k-cut for k > 2? How about a dimension d > 2? Is there a framework to answer such questions? I know about Cheeger's inequalities, but those apply to sparsest cut (not max-cut) and only work for regular graphs.

(Question is inspired by the problem of clustering light sources in computer graphics to minimize variance).

The constant does tend to 1/2 as the dimension increases. In d dimensions, you can have d+1 points at distance one from each other, so the the sum of distance-squared is ${d+1 \choose 2}$ and the maximum cut is at most $(d+1)^2/4$, which is a $\frac 12 \cdot \frac {d+1}{d}$ fraction of the total weight


Are there known to exist functions with the following direct-sum property? This question can be asked either in the framework of circuit complexity of Boolean circuits, or in the framework of algebraic complexity theory, or probably in lots of other settings.  It is easy to show, by counting arguments, that there exist Boolean functions on N inputs that require exponentially many gates (though of course we don't have any explicit examples).  Suppose I wish to evaluate the same function M times, for some integer M, on M distinct sets of inputs, so that the total number of inputs is MN.  That is, we just want to evaluate $f(x_{1,1},...,x_{1,N}), f(x_{2,1},...,x_{2,N}),...,f(x_{M,1},...,x_{M,N})$ for the same function $f$ at each time.

The question is: is it known that there exists a sequence of functions $f$ (one function for each N) such that, for any N, for any M, the total number of gates required is at least equal to M times an exponential function of N?  The simple counting argument does not seem to work since we want this result to hold for all M.  One can come up with simple analogues of this question in algebraic complexity theory and other areas.

Well, that is false: it is possible to evaluate M copies of ANY f using only O(N(M+2^N)) gates which can be much less than M*exp(N) (in fact, you get linear amortized complexity for exponential M).  I don't remember a reference, but I think that it can go something like the following:

First add 2^N fictitious inputs which are just constants 0...2^N-1 and now denote the i'th N-bit input by xi (so for i<=2^N we have xi=i, and for 2^N < i <=2^N+M we have the original inputs).  Now we create a triplet for each of the M+2^N inputs: (i,xi,fi) where fi is f(i) for the first 2^N inputs (a constant that is hardwired into the circuit) and fi="*" otherwise.  Now we sort the triplets (i,xi,fi) according to the key xi, and let the j'th triplet be (i_j,x_j,f_j) from this we compute a triplet (i_j,x_j,g_j) by letting g_j be f_j if f_j is not a "*" and let g_j be g_(j-1) otherwise.  Now sort the new triplets back according to the key i_j, and you got the correct answers at the correct places.


Complexity class for some group and graph homomorphism problems Given two groups $G_1$ and $G_2$ what is the complexity class in which the following problem belongs?

$$\mathsf{Is }|Hom(G_1,G_2)|>0$$

Given two graphs $H_1$ and $H_2$ what is the complexity class in which the following problem belongs (Answered by Ricky Demer in comment)?

$$\mathsf{Is }|Hom(H_1,H_2)|>0$$

(As I mentioned in a comment,) The graph problem is NP-complete, even when H2 is a triangle.

By putting 3 isolated vertices into H1, one gets a modified instance such that if the

original instance had no graph homomorphisms then the modified instance also has no

graph homomorphisms else the modified instance has more than 6 graph homomorphisms.

Taking the group problem literally, it is in DTIME(1), since it's decided by the algorithm ACCEPT.

On the other hand, let ∃NZH be the result of instead interpreting the "0" from the

group problem as "the cardinality of the singleton whose element is the zero morphism".

By Reingold's result, ∃NZH is in  GC$\hspace{-0.02 in}\big(\hspace{-0.04 in}\lceil \hspace{-0.02 in}$log2(|G1|)$\hspace{-0.02 in}\rceil \hspace{-0.06 in}\cdot \hspace{-0.06 in}\lceil \hspace{-0.02 in}$log2(|G2|)$\hspace{-0.02 in}\rceil$,logspace$\hspace{-0.03 in}\big)$ ,  since that class

gives the verifier two-way read access to the alleged proof.  Furthermore (still using Reingold), logspace machines can compute such non-zero homomorphisms given 2-way read access to

such witnesses.  Additionally, by this answer's bound on the number of non-isomorphic groups

(which I don't know how to prove), the negation of ∃NZH is in

GC$\hspace{-0.02 in}\big(\hspace{-0.03 in}\big[\hspace{-0.04 in}\lceil$log2(|G1|)$\hspace{-0.03 in}\rceil^{\hspace{-0.02 in}2}\hspace{-0.05 in}+\hspace{-0.06 in}\lceil$log2(|G2|)$\hspace{-0.03 in}\rceil^{\hspace{-0.02 in}2}$ ordinary bits$\hspace{-0.02 in}\big]\hspace{-0.03 in}$+[1 pointer to the advice string]

,logspace$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}n^{O\left(\hspace{-0.02 in}(\hspace{.02 in}\log(n))^{\hspace{.02 in}2}\hspace{-0.02 in}\right)}$.

(The pointer is to where the advice string gives [an ordered pair of reference groups with no non-zero homomorphisms] such that each input group is isomorphic to the corresponding reference group.)

I'm not aware of any evidence for there being $\big[\hspace{-0.02 in}$a set S of ordered pairs $\langle \hspace{-0.02 in}$m,n$\hspace{-0.02 in}\rangle$

with min(m,n) not bounded above$\hspace{-0.02 in}\big]$ such that the complement of the language

$\: \big\{\hspace{-0.05 in}\langle \hspace{-0.02 in}$m,n,G1,G2$\rangle$  :  $\langle \hspace{-0.02 in}$m,n$\hspace{-0.02 in}\rangle \hspace{-0.03 in}\in$ S  and  and  |G1| < m  and  |G2| < n

     and  G1 and G2 are both 2-groups  and  $\langle \hspace{-0.02 in}$G1,G2$\rangle \hspace{-0.03 in}\in$ ∃NZH $\hspace{-0.08 in}\big\}$

is in  GC$\hspace{-0.03 in}\big(\hspace{-0.03 in}o\hspace{-0.02 in}\big(\hspace{-0.03 in}$(log(m+n))3$\hspace{-0.03 in}\big)\hspace{-0.02 in}$,DTIME$\hspace{-0.03 in}\big(\hspace{-0.03 in}$2o(log(m)$\cdot$log(n))$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$2^$\big(\hspace{-0.04 in}$(m+n)o(1)$\hspace{-0.02 in}\big)$

or in  NTIME$\hspace{-0.03 in}\big(\hspace{-0.03 in}$2o(log(m)$\cdot$log(n))$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}n^{o\hspace{-0.02 in}\left(\hspace{-0.02 in}(\hspace{.02 in}\log(m+n))^{\hspace{.02 in}2}\hspace{-0.02 in}\right)}$ ,

where all five little-os are as min(m,n) increases without bound.

However, I certainly suspect that the negation of ∃NZH is already in those two classes,

i.e., without needing to bring S into the picture or assume that the groups are 2-groups.


Is there a standard format for Dependent QBF? I know there is a standard input format DIMACS for a formula is in conjunctive normal form (CNF) and QDIMACS for quantified Boolean formulas. Is there a similar standard format for the Dependent-QBF (DQBF)?

There is a standard format proposed. At QBFEVAL’18 there is a DQBF-track, which uses DQDIMACS from a paper by Föhlich et al on IDQ.


Complexity of computing the average distance of a graph Let $\rm{ad}(G)$ be the average distance of a connected graph $G.$

One way to compute $\rm{ad}(G)$ is by summing up the elements of $D(G),$ the distance matrix of $G$ and scaling the sum appropriately.

If the output graph is a tree then it is known that the average distance can be computed in linear time (See B.Mohar, T.Pisanski  - How to compute the Wiener index of a graph). There appears to be fast algorithms for graphs with bounded tree width as well.

An interesting question therefore is, whether it helps to know $D(G).$ In other words

  Is it possible to compute $\rm{ad}(G)$ in sub-quadratic time?

What I am interested in knowing is if there is a theoretical lower bound as to why this would not be possible.

Computing ad(G) in $O(n^{2-\delta})$ time for constant $\delta>0$ even in graphs with $\tilde{O}(n)$ edges and $n$ vertices would imply that the Strong Exponential Time Hypothesis (SETH) is false. (SETH was defined by Impagliazzo, Paturi and Zane'01 and implies that CNF-SAT on $n$ variables does not have $O(2^{(1-\varepsilon)n})$ time algorithms.)

To prove this, note that we recently proved in (Fast approximation algorithms for the diameter and radius of sparse graphs, Liam Roditty, V. Vassilevska Williams. STOC'13.) that if one can distinguish between graphs of diameter 2 and 3 in subquadratic time, then SETH is false.
The proof goes via a reduction from CNF-SAT.
The same reduction can be used to show that computing ad(G) in subquadratic time shows that SETH is false, as the average distance in the graphs in the reduction would be $2-M/{N\choose 2}$ (where $N$ and $M$ are the number of nodes and edges in the reduction instance) if the CNF-SAT instance is not satisfiable, and more than that if there is a satisfying assignment.


Understanding bounded-diameter decomposition of graphs for PTAS While trying to understand Baker's approach (also explained in this article by Eppstein) to designing PTAS's for planar graphs, I came across a difficulty.

The idea is, given an integer $k$, decompose the graph into subgraphs of tree-width bounded by $O(k)$ (which for planar graphs happens if $diameter = O(k)$), then solve the problem on the subgraphs in polynomial-time, and finally glue the solutions together to get a polynomial-time $(1 + O(1/k))$-approx.

The decomposition method described in the part $8$ of the article, amounts to, as far as I understood, pick any vertex, get a BFS tree from that vertex, and remove every $k$-th level of the tree (potentially starting at level $0 \leq i < k$, but I do not think it matters for this part).

The author then argues that the obtained subgraphs (consisting each of at most $k-1$ levels of the BFS tree), have bounded diameter (i.e. depending only on $k$).

This is the part I do not understand. For instance, what happens if some layer of the tree is a long path ? How is the diameter of a subgraph containing this layer bounded ?

Thank you for any help,

Lucas

Actually, the obtained subgraphs may not have bounded diameter, but they still have bounded tree-width. In order to see this, take one such subgraph $H$, and build $H'$ by adding a new vertex $u$ that is connected to each of the top-level vertices of $H$ (remember that $H$ was obtained as $k-1$ consecutive layers of a BFS tree). Then clearly $diam(H') \leq 2k$ since any vertex in $H'$ is at distance less than $k$ of $u$. We then know that $tw(H') = O(diam(H')) = O(k)$. Finally, $H$ is a minor of $H'$ so $tw(H) \leq tw(H')$, hence $tw(H) = O(k)$.


Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known Given a $k>0$ and a graph $G(V,E)$ with known independence number $\sqrt{|V|}\leq\alpha(G)\leq\alpha\sqrt{|V|}$ and chromatic number $\frac1\beta\sqrt{|V|}\leq\chi(G)\leq\sqrt{|V|}$ for some fixed $\alpha,\beta\geq2$ and given an optimum vertex coloring is it $\mathsf{NP}$-complete to decide if clique number $\omega(G)>k$?

The NP-hardness proof for CLIQUE in the book by Garey and Johnson shows that the following problem is NP-complete:

  Instance: An integer $k$; a $k$-partite graph $G=(V,E)$
  Question: Does $G$ contain a $k$-clique?

Here is a construction that shows NP-completeness of your problem variant:

Let $G$ and $k$ be as in the proof in Garey and Johnson
Let $H_1$ be a graph on $k+2$ vertices: The $k-3$ vertices $v_1,\ldots,v_{k-3}$ induce a clique, and the five vertices $u_1,\ldots,u_5$ induce an odd cycle $C_5$. Every $u_i$ is connected to every $v_j$.
It is easy to see that $\omega(H_1)=k-1$ and $\chi(H_1)=k$.
Let $H_2$ be an independent set on $2|V|+2k^2$ vertices.
Create a graph $G'$ by taking the disjoint union of $G$, $H_1$ and $H_2$, and by adding all the edges between $H_2$ on the one side and $G\cup H_2$ on the other side.

It can be verified that:

$\alpha(G')=2|V|+2k^2$. (Take all vertices in $H_2$.)
$\chi(G')=k+1$. (Note that $G\cup H_2$ is $k$-colorable, and that $H_1$ adds one more color.)
$\omega(G')=\max\{\omega(G),k-1\}+1$. (Note that $\omega(G\cup H_2)=\max\{\omega(G),k-1\}$, and that $H_1$ adds one more vertex to this.)

Hence the knowledge of $\omega(G')$ would allow us to decide whether $\omega(G)=k$.


Mechanization of Mathematics Its been a while since I took my theory course, but I recall that Hilberts Decision problem was shown to be false.

  By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.

From Wikipedia.

But In my AI course, we learned of an algorithm to prove or disprove new statements using the axioms known as Resolution by refutation. Simply take the a negation of the statement you want to prove, and use the axioms to show it either leads to an empty clause (true) or non-empty clause (false).

So my question is: What am I missing from these two seemingly contradictory statements? On one hand the literature states there exists no algorithm to determine if a statement is provable from the axioms, and on the other hand, I am presented with an algorithm that proves (or disproves) a statement from the axioms. What am I confused or incorrect about here?

You're missing what resolution refutation works for -- namely, just propositional logic.

For example, try using that algorithm on "There exist integers x, y, z such that x3 + y3 + z3 = 33."

There are sets of axioms for which the set of theorems is decidable -- the real closed field axioms are the most important example of that, and they in fact also allow quantifier elimination.

There are sets of axioms for which the set of theorems is not decidable -- by undecidability of Diophantine equations, all Σ1-sound extensions of Robinson arithmetic are examples of that.


Understanding non-equivalence of proof lengths according to proof systems Here, in section 4.3, Fortnow says:

But to prove P != NP we would need to show that tautologies
cannot have short proofs in an arbitrary proof system.

I am trying to understand the logic leading to this conclusion. Do I get it right when I say:

Haken showed that under a Frege proof system, solving the pigeonhole principle for $m=n+1$ is intractable.
However, with an extended Frege a proof system based on cutting planes, solving the pigeonhole principle for $m=n+1$ is always achievable in polynomial time.
Therefore, if one proves intractability of say k-SAT in a proof system, it does not imply that solving k-SAT would be intractable in another proof system.

Is that right? Else, what am I missing?

I believe everything you said is correct. I note that your point #3 could hold regardless of points #1 and #2 - points #1 and #2 are just a concrete example of where this has provably happened.


Do past time LTL and future time LTL have the same expressiveness? I would like to ask if anybody is aware of a paper comparing the expressiveness of past time LTL and that of (future time) LTL.

The quick summary is that LTL with only past and no future modalities defines properties expressed over finite-words and these are the star-free subset of the regular languages. Standard LTL when extended with past-time modalities does not have more logical expressive power than LTL with only future modalities but properties can be defined in an exponentially succinct manner.

For a more detailed answer, there are at least three logics one can consider in answering your question and at least three different notions of expressiveness.

Standard Linear Temporal Logic (LTL), which has the standard modalities next and until and is interpreted over traces that have a finite history and an infinite future.
Past-time Linear Temporal Logic (ptLTL), which has the modalities "previously" instead of "next" and "since" instead of until and is interpreted over finite traces, or at some point in an infinite trace but refers to the history of the trace.
Temporal logic with past and future modalities (sometimes abbreviated to TL), which has the modalities of LTL and ptLTL and is interpreted either over infinite traces or over finite and infinite traces.

The three notions of expressiveness are to ask (i) what languages (of finite or infinite words) each logic can define, (ii) what first-order structures these logics define, and (iii) what the complexity of defining a given language (or first-order structure) in each logic is. A more refined vocabulary for comparing expressiveness is provided by the notion of hierarchies, which are briefly mentioned at the bottom.

First-Order Structures definable by temporal languages

Kamp in 1968 studied an until modality that is slightly different from the notion commonly used in computer science today. I will write it as $\mathit{Until}_+$ for because a formula $p ~Until_+~ q$ is true at time instant i if $q$ is true at some $j > i$ and if $p$ holds at all $i < j' < j$. Note that the orders are strict. The temporal-dual is the modality $Since_+$. Kamp compared temporal logics to the Monadic First-Order Logic of Order (MLO, sometimes MFLO or FMLO). MLO formulae contain unary predicate symbols and a relation $<$ and are interpreted over linear orders.

Kamp's theorem shows that a logic with only $Until_+$ and $Since_+$ modalities is expressively equivalent to MLO when both logics are interpreted over the naturals or over the non-negative reals. In fact, Kamp's theorem applies to a family of structures called Dedekind-complete chains (which notably does not include the non-negative rationals). Stavi's theorem shows that a temporal logic with standard since and until and a special since and until modality is expressively-equivalent to the first-order monadic logic of order over every linear order. The notion of expressiveness in these results is "definability of first-order structures".

Gabbay, Pnueli, Shelah and Stavi considered a family of MLO formulae called future formulae, which intuitively only refer to future points in time. They showed that on a family of models called discrete, complete orders, which includes the naturals, future MLO formulae have the same expressive power as temporal logic with the $Until_+$ modality, a next and previously modality. So these results relate certain temporal and first-order logics on certain structures.

Relating languages to first-order logic, McNaughton and Papert showed that first-order definable languages are star-free and regular, which in conjunction with Kamp's theorem shows that all the logics above only define subsets of regular languages. Adding the next and previous modalities does not change what you can define and a proof that the third logic above still defines only the star-free regular languages is due to Zuck and Pnueli, I believe.

Comparative expressive power of temporal languages

Kamp was also one of the first to study how the properties one can express changes with the modalities in a temporal logic.  He showed that the $Until_+$ modality cannot be expressed in a logic with the Eventually, Next and more modalities. This difference in expressive power led him to study the $Until_+$ and $Since_+$ modalities.

Gabbay, Pnueli, Shelah and Stavi proved what is called a separation theorem. They showed that a formula that involves $Until_+$ and $Since_+$ can be written as a Boolean combination of formulae that involve either only $Until_+$ or only $Since_+$. (The story goes that when Kamp heard of a form of this separation theorem from Gabbay, he went out and bought Gabbay a cake.) This paper and separation result is sometimes cited as the reason for not including past modalities in temporal logics. It follows from their results that for a formula with $Until_+$ and $Since_+$, there exists a formula involving only $Until_+$ such that at time instant $0$, either both are true or both or false. It follows from this result that a temporal logic with the standard $Next$, $Until$, $Since$ and $Prev$ modalities, when interpreted over time indexed by the natural numbers (the standard semantics in computer science) has the same expressive power as LTL with only $Next$ and $Until$.

Unfortunately the only algorithm known to compute the separation above non-elementary complexity. Moreover, not every temporal logic has the separation property. In particular, if you only have an eventually and previously modality, separation does not hold. Lichtenstein, Pnueli and Zuck did show that every formula in LTL with past modalities is equivalent to a formula with the form below.

  $\bigvee_1^n (GF~\varphi_i) \land (FG~\psi_i)$, where $\varphi_i$ and $\psi_i$ do not contain standard $Until$ or $X$.

Complexity

In terms of complexity, it is known that temporal logic with past-time modalities is exponentially more succinct than LTL with only future-time modalities. Nonetheless, a result of Sistla and Clarke (1985) shows that the model checking problem for both is in PSpace. The actual complexity issues are a bit more complicated because one can ask for lower-bounds for expressiveness in both logics involved in a comparison. I recommend consulting the references below for more on this.

Vince Bárány's temporal logic course has all the reading material in one place.
Temporal Logic with Past is Exponentially More Succinct, Laroussinie, Markey, and Schnoebelen has recent results on a logic with a now modality and a forgettable notion of past.
The Glory of the Past, by Lichtenstein, Pnueli and Zuck is the definite starting point for reading on complexity differences between LTL with and without past-time modalities.
Lenore Zuck's PhD thesis is a good place to read about background on past and future modalities, in particular Chapters 2 and 3. Chapter 5 has the main results on expressiveness of the logic with past and regular languages.
Propositional temporal logics: decidability and completeness, Lichtenstein and Pnueli, 2000. Studies decidability and completeness of LTL with past and future modalities and has surveys the history of these logics.
Separation - past, present and future, Hodkinson and Reynolds, is a survey of many different logics using the notions of until and since from Kamp, and which discusses these issues from the perspective of the separation theorem.
Expressive Power of Temporal Logics, Rabivonich, 2002 discusses several other notions for comparing expressiveness such as dot-depth, quantifier alternation and basis for a temporal logic.
Efficient Monitoring of Safety Properties, Havelund and Rosu studies an application of ptLTL, and is a place to find a definition of the logic.
The Rise and Fall of LTL by Vardi is a talk that covers most of this and much more from a high level.
Specification in CTL+Past for Verification in CTL, Laroussinie and Schnoebelen, 2000, will answer the questions you haven't yet asked about what happens if you have past-time modalities in a branching-time logic.


Edit distance in sublinear space What is the best known complexity for computing the exact edit distance between two strings of the same length using working space which is sublinear in the size of the input?  I assume the input is stored in some read-only format. Is this a previously studied problem?

To make the question a little more specific, how about $\Theta(\sqrt{n})$ space where $n$ is the length of each input string.

Edit. Following the answer of David Eppstein, it seems a good question is simply if the edit distance can be found in polynomial time and $\Theta(\sqrt{n})$ space. Any lower bounds would also be interesting.

Just to get things going, rather than trying to close out this problem: there is an obvious nondeterministic algorithm using logarithmically many bits of space (search for a single path through the dynamic programming matrix) so by Savitch's theorem there is a deterministic algorithm with space $O(\log^2 n)$. Its time must be of the form $n^{O(\log n)}$, quasi-polynomial rather than exponential.

There are some space lower bounds for edit distance in http://arxiv.org/abs/1106.4412 but I don't think they match your version of the problem.


Lower bound on pebbling numbers Out of curiosity, I tried finding the original paper showing that there are graphs that require $n/\log n$ pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (Which you can access here: http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/p332-hopcroft.pdf).

Sadly, this result is cited as “personal communication,” and any other lower bounds I could find use the different definition of pebbling in graph theory. Does anyone know where I could find a construction of a graph requiring $n/\log n$ pebbles?

A full proof (based on superconcentrators) can be found in chapter 24 "The pebble game" of the book

  Uwe Schöning and Randall Pruim:
  Gems of Theoretical Computer Science
  Springer, 1998

  ISBN 978-3-642-64352-1
  https://link.springer.com/book/10.1007%2F978-3-642-60322-8


Definition of Planar 3-SAT What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?

There's a nice compilation of definitions of related NP-complete planar satisfiability problems at http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf

One of them, planar monotone 3-sat, allows you to split each terminal into positive and negative, with the terminals placed along a line with the positive part on one side of the line and the negative part on the other side of the line. The clauses have only positive or only negative terminals and are placed on the positive or negative side of the line respectively.


Approximation algorithms for problems in P One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for several reasons. Off the top of my head, an approximation algorithm may run with a much lower complexity (or even a much smaller constant), might use less space or might be much better parallelizable.

Also, schemes that provide time/accuracy tradeoffs (FPTAS's and PTAS's) might be very attractive for problems in P with lower bounds that are unacceptable on large inputs.

Three questions: is there anything that I'm missing that makes this obviously a bad idea? Is there research going on in developing a theory of these algorithms? If not, at least, is anyone familiar with individual examples of such algorithms?

As Jukka points out, computational geometry is a rich source of problems that can be solved in polynomial time, but we wish to get fast approximations. The classic "ideal" result is an "LTAS" (linear time approximation scheme) whose running time would be of the form $O(n + \text{poly}(1/\epsilon))$ - usually these are obtained by extracting a constant (poly($1/\epsilon$)) sized kernel from the data, and running an expensive algorithm on that kernel, with a guarantee that an exact solution on the kernel is an approximate solution on the entire input.

There are a number of tricks, reductions and principles, and Sariel Har-Peled's new book is full of these. I don't think there's a rich complexity theory as such.


What is an algorithm to find a minimum vertex cover on a bipartite graph with weighted vertices? I know that for an unweighted bipartite graph, I can find the minimum vertex cover by first finding the maximum matching and turning it into a vertex cover using König's Theorem. Is there a modification one could use if the nodes are weighted?

The weighted vertex cover problem can be formulated as an Integer Program (see http://en.wikipedia.org/wiki/Vertex_cover). When the input graph is bipartite, the constraint matrix of this IP is totally unimodular. Hence this IP can be solved in polynomial time.

For more details of total unimodular matrices and the corresponding algorithms, see the excellent (three volume) book by Alexander Schrijver.


Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G You are given two graphs G and H , and want to know if H is a subgraph of G.

You know that H has a max vertex degree K (constant integer).

What can you say about the complexity of this?

I know that
Isomorphism of Graphs of Bounded Valence Can Be tested in Polynomial Time - Luks 1982,
that's the best I currently have...

If H is the cycle on |G| vertices (and is of maximum degree 2), then this is the Hamiltonian cycle problem. Seems like your problem is NP-hard.


What are the pros and cons for type cases in dependent type theories? Pattern matching on $\cal U$ is allowed in XTT and Idris2 (for unerased types), and that implies the injectivity of type constructors (that's just my intuition, though -- I also wonder how do I prove that?).
I wonder how this feature work in the underlying model of type theories and how do they affect programming in dependent type systems. It seems that $\cal U$ will then become an inductive type, and formation rules are turned into introduction rules...

The basic idea is clearest when you think about things in terms of Tarski-style universes. There, you have a data type of codes, and an interpretation function which maps codes to types. In this case, it is obvious that you can discriminate on type codes, even though this is a much more questionable operation on types. For example, $\mathbb{N} \to 0$ and $\mathbb{R} \to 0$ are equal as sets, which means that injectivity of type constructors is obviously false — $\mathbb{R} \neq \mathbb{N}$!
-- A Tarski-style universe in Agda
—-
-- Declarations.
data TypeCode : Set
El : TypeCode → Set

-- Definitions.
data TypeCode where
  nat : TypeCode
  pi  : (a : TypeCode) (b : El a → TypeCode) → TypeCode

El nat      = Nat
El (pi a b) = (x : El a) → El (b x)

A definition very similar to this Agda code is pretty typical when building PER models of type theory — the main difference is just that everything is valued in PERs.
Distinguishing type codes and types is not “normal mathematics", which is a strike against it, but on the other hand, the stricter, more decidable, equality on type codes can make various forms of automation easier to implement.
Which is better? It’s unclear! As Edwin Brady says, we don’t know how to do dependent types wrong yet.


Type of induction principle for fixpoint types To the Calculus of Constructions we could add a general fixpoint type constructor (accepting inconsistencies or assuming F is a Functor):

Fix : (* -> *) -> *
in  : ∀F. F (Fix F) -> Fix F
out : ∀F. Fix F -> F (Fix F)

We can then write down the type of case discrimination and folding:

case : ∀F T. (F (Fix F) -> T) -> Fix F -> T
fold : ∀F T. (F T -> T) -> Fix F -> T

But what is the type of induction (if there is one)? I've gotten this far:

ind : ∀F T (P : Fix F -> *). (∀(h : Fix F). P h -> P ???) -> (x : Fix F) -> P x

Assuming the rest is correct, what should be in the place of ????
Alternatively, what is the type of dependent case discrimination?

To answer my own question, the paper Generic derivation of induction for impredicative encodings in Cedille shows a type for induction on a fixpoint type. It can look like:

ind : ∀F T (P : Fix F -> *). ((h : F (Σ (Fix F) P)) -> P (in (map fst h))) -> (x : Fix F) -> P x

With Σ being the dependent product and map the functor map of F.


Random Deterministic Automata I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)$, gets a probability of $p^{|E|}\cdot (1-p)^{{{{|V|}\choose{2}}} - |E|}$. In particular, $G(n, \frac{1}{2})$ is the uniform distribution over simple undirected graphs of size $n$.

Now, given a finite alphabet $\Sigma$ and a natural number $n$. Do we have a random process that generates a deterministic automaton $A$ with:

$A$ has $n$ reachable states.
$A$ is defined over $\Sigma$.
$A$ has the same probability as any other deterministic automaton of size $n$ over $\Sigma$.

In words, do we have a way to generate a uniform distribution $D(\Sigma, n,\frac{1}{2})$ over deterministic automata?

I would be happy if you can direct me to a relevant reference.

The question is a bit ill-posed, since you did not specify that equivalent automata should be counted as a single object. Without that restriction (or the reachability one), the set of all $n$-state DFAs over a binary alphabet and with starting state $s=1$ has exactly $n^{2n}2^n$ elements, and it is trivial to sample from this set uniformly, as indicated in the link in my comment,
https://dl.acm.org/citation.cfm?id=3064434

Now the linked paper gives sharp bounds on the expected size of the minimal equivalent DFA, when the original one is drawn from the naive uniform distribution. For binary alphabets, this quantity is concentrated about $0.7968n$. That suggests that if you naively sample DFAs on $n/0.7968$ states and then minimize them, you'll get automata with roughly $n$ reachable states. Of course, no claim is being made about this sampling procedure being uniform. See, however, references in the linked paper -- especially
https://dl.acm.org/citation.cfm?id=782472
and
http://www.sciencedirect.com/science/article/pii/S0304397507002861?via%3Dihub
-- the latter seems most relevant to your question.


Hardness of approximation assuming the existence of one-way functions This question is inspired by a question posed by Shiva Kintali, Hardness of approximation assuming NP != coNP
. Multiplication of two prime numbers of equal size is strong candidate for one-way function. We know the $P \ne NP$ does not imply the existence of one-way functions.

  Are there any hardness of approximation results assuming the existence of one-way functions?

Ideally, assuming $P \neq NP$ would not be sufficient to prove such hardness of approximation result and we must assume that existence of one-way functions to prove such hardness of approximation result.

The problem of learning in the PAC model is really just a problem of combinatorial optimization: with a large enough sample size, finding a function $f \in C$ which has low prediction error is equivalent to finding a function $f \in C$ which best classifies some finite sample from the distribution.

In this area, there are plenty of hardness of approximation results that depend on the existence of one-way functions. For example,
"Cryptographic Hardness of Distribution Specific Learning" -- Kharitonov, http://portal.acm.org/citation.cfm?id=167197

"Cryptographic limitations on learning Boolean formulae and finite automata" -- Kearns, http://portal.acm.org/citation.cfm?id=174647&dl=GUIDE,

and many more recent results.


Meet of integer partitions An integer partition of $n$, $A$, is a multiset of positive integers such that $\sum_{a \in A} a= n$. We say that $B \leq A$, if there exists a map $\phi: |B| \to |A|$, such that for $a \in A$, we have $\sum_{b| \phi(b) = a} b = a$.

Given two integer partitions of $n$, $A$, $B$, I was wondering how hard is it to find the smallest $C$ satisfying both $C \leq A$, $C \leq B$. (by smallest, I mean minimizing $|C|$)

Are any polynomial time algorithms known for this problem?

Considering very simple approximations, I know that $|C| \leq n-\min_{X \in \{A,B\}} \sum_{x \in X} \left\lfloor \frac{x}{2}\right\rfloor$. I got this by considering splitting each $x$ into 2's and 1's. More generally we could say:

$$ |C| \leq n -\max_{k} \left((k-1)\min_{X\in\{A,B\}} \sum_{x\in X}\left\lfloor\frac{x}{k}\right\rfloor\right)$$

The problem is strongly NP-complete.

Reduction from 3-partition, a strongly NP-complete problem. The multiset $S$, $|S| = 3m$, $\sum_{x \in S} x = n$ can be partitioned into tuples of size three of equal sum if and only if $A \leq B$ where $A = S$ and $B$ is $m$ duplicates of $\frac{n}{m}$. If $A \leq B$, we can have $C = A$. If $A \not\leq B$, we must have $|C| > |A|$, hence a 3-partition exists if and only if a set $C$ of size $|A|$ exists.

As for approximations, a trivial 2-approximation exists, since $\max(|A|, |B|) \leq |C| \leq |A| + |B|$. Construction: Build $C$ by always taking smallest integer in either of $A$ or $B$, then remove it from that set, and subtract it from an arbitrary integer in the other set. The value $|C| + |A| + |B|$ can only decrease over the course of the algorithm. This also shows that the problem is in NP.


Which is the limit of lossless compression data? (if there exists such a limit) Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression.

So far, the only source I could find on this topic was the Wikipedia:

  Lossless compression of digitized data
  such as video, digitized film, and
  audio preserves all the information,
  but can rarely do much better than 1:2
  compression because of the intrinsic
  entropy of the data.

Unfortunately, Wikipedia's article doesn't contain a reference or citation to support this claim. I'm not a data-compression expert, so I'd appreciate any information you can provide on this subject, or if you could point me to a more reliable source than Wikipedia.

I am not sure if anyone has yet explained why the magical number seems to be exactly 1:2 and not, for example, 1:1.1 or 1:20.

One reason is that in many typical cases almost half of the digitised data is noise, and noise (by definition) cannot be compressed.

I did a very simple experiment:

I took a grey card. To a human eye, it looks like a plain, neutral piece of grey cardboard. In particular, there is no information.
And then I took a normal scanner – exactly the kind of device that people might use to digitise their photos.
I scanned the grey card. (Actually, I scanned the grey card together with a postcard. The postcard was there for sanity-checking so that I could make sure the scanner software does not do anything strange, such as automatically add contrast when it sees the featureless grey card.)
I cropped a 1000x1000 pixel part of the grey card, and converted it to greyscale (8 bits per pixel).

What we have now should be a fairly good example of what happens when you study a featureless part of a scanned black & white photo, for example, clear sky. In principle, there should be exactly nothing to see.

However, with a larger magnification, it actually looks like this:

There is no clearly visible pattern, but it does not have a uniform grey colour. Part of it is most likely caused by the imperfections of the grey card, but I would assume that most of it is simply noise produced by the scanner (thermal noise in the sensor cell, amplifier, A/D converter, etc.). Looks pretty much like Gaussian noise; here is the histogram (in logarithmic scale):

Now if we assume that each pixel has its shade picked i.i.d. from this distribution, how much entropy do we have? My Python script told me that we have as much as 3.3 bits of entropy per pixel. And that's a lot of noise.

If this really was the case, it would imply that no matter which compression algorithm we use, the 1000x1000 pixel bitmap would be compressed, in the best case, into a 412500-byte file. And what happens in practice: I got a 432018-byte PNG file, pretty close.

If we over-generalise slightly, it seems that no matter which black & white photos I scan with this scanner, I will get the sum of the following:

"useful" information (if any),
noise, approx. 3 bits per pixel.

Now even if your compression algorithm squeezes the useful information into << 1 bits per pixel, you will still have as much as 3 bits per pixel of incompressible noise. And the uncompressed version is 8 bits per pixel. So the compression ratio will be in the ballpark of 1:2, no matter what you do.

Another example, with an attempt to find over-idealised conditions:

A modern DSLR camera, using the lowest sensitivity setting (least noise).
An out-of-focus shot of a grey card (even if there was some visible information in the grey card, it would be blurred away).
Conversion of the RAW file into a 8-bit greyscale image, without adding any contrast. I used typical settings in a commercial RAW converter. The converter tries to reduce noise by default. Moreover, we are saving the end result as an 8-bit file – we are, in essence, throwing away the lowest-order bits of the raw sensor readings!

And what was the end result? It looks much better than what I got from the scanner; the noise is less pronounced, and there is exactly nothing to be seen. Nevertheless, the Gaussian noise is there:

And the entropy? 2.7 bits per pixel. File size in practice? 344923 bytes for 1M pixels. In a truly best-case scenario, with some cheating, we pushed the compression ratio to 1:3.

Of course all of this has exactly nothing to do with TCS research, but I think it is good to keep in mind what really limits the compression of real-world digitised data. Advances in the design of fancier compression algorithms and raw CPU power is not going to help; if you want to save all the noise losslessly, you cannot do much better than 1:2.


Is predicting (in the limit) computable sequences as hard as the halting problem? Question:
Is predicting (as defined below) computable sequences as hard as the halting problem?

Elaboration:
"Predict" means successfully predict, which means make only finitely many errors on the task of trying to predict the n-th bit of the sequence given access to the previous n-1 bits (starting from the first bit and going through the entire infinite computable sequence).

There's a simple diagonalization argument (due to Legg 2006) that for any Turing machine predictor p, there's a computable sequence on which it makes infinitely many errors. (Construct a sequence that has as its nth term the opposite of what p predicts given the previous n-1 terms in the sequence.) So there is no computable predictor that predicts every computable sequence. A halting oracle would allow construction of such a predictor. But can you show that having such a predictor allows you to solve the halting problem?

More elaboration

Definition (Legg)
A predictor p is a Turing machine that tries to predict the n-th bit of a sequence S given access to the previous n-1 bits. If the prediction fails to match the n-th bit of the sequence, we call this a mistake. We will say that p predicts S if p only makes finitely many mistakes on S. In other words, p predicts S if there is some number M in the sequence s.t. for every m>M, p correctly predicts the m-th bit of S given access to the first m-1 bits.

Formally, we could define a predictor machine as having three tapes. The sequence is entered as input bit-by-bit on one tape, the predictions for the next bit are made on a second tape (the machine can only move right across this tape), and then there is a work tape on which the machine can move in both directions.

Simple results
By the above definition, there's a predictor that predicts all the rational numbers. (Use the standard zig-zag enumeration of the rationals. Start by predicting the 1st rational in the list, if there's a mistake, move to the next rational.). By a similar argument, there's a predictor s.t. given access to N, is able to predict all sequences of Kolomogorov complexity less than or equal to N. (Run all the N-bit machines in parallel and take the prediction of the machine that halts first. You can only make finitely many errors).

Citation
Shane Legg 2006
http://www.vetta.org/documents/IDSIA-12-06-1.pdf
(not the author of this post)

Actually this is easier than solving the halting problem.

Let $f:\mathbb N\rightarrow\mathbb N$ be a function that dominates all computable functions, i.e., for all total computable functions $g:\mathbb N\rightarrow\mathbb N$, we have that for all but finitely many $n$, $g(n)\le f(n)$. It is a standard fact that there exist such functions that have strictly lower Turing degree than the halting problem, see e.g. Soare's book Recursively Enumerable Sets and Degrees. These are called the high Turing degrees.

Let $\varphi_e$, $e\in\mathbb N$ be a standard list of the partial computable functions from $\mathbb N$ to $\{0,1\}$.

Now, using $f$ we construct a predictor $p$.

$p(a_0,\ldots,a_{k-1})$ is chosen as some number $a_{k}\in \{0,1\}$ so as to make the sequence $a_0,\ldots,a_k$ agree with $\varphi_t(0),\ldots,\varphi_t(k)$ for the minimal possible $t\le k$. Since we cannot wait for possibly hanging computations to halt, we only monitor the computations until stage $f(k)$ ($f(k)$ many computations steps). If there is no such $t$ we just set $a_{k}$ arbitrarily (say $=0$).

Now suppose $q$ is minimal such that $\varphi_q$ computes the computable sequence that is actually observed. Then we will for all but finitely many $k$ use $t=q$ and hence choose the correct $a_{k}$, because $f$ dominates the running time function for $\varphi_q$, namely $s(n)=$ the least stage where $\varphi_q(n)$ has halted.


What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution? What are the problems with the best known approximation ratio achieved by an algorithm returning a uniformly random solution?

I know one such example for permutation flow shop problem $F|perm|C_{max}$: in the paper "Tight Bounds for Permutation Flow Shop Scheduling" Viswanath Nagarajan and Maxim Sviridenko proved that random sequence of jobs have guarantee $2\sqrt{min\{m,n\}}$ ($m$-number of machines and $n$ - number of jobs) which is the best known currently.

For constraint satisfaction problems, the property of having no better approximation algorithm than random assignment is known as approximation resistance.

This is has been studied by several works in the last few years, with some results based on $P\neq NP$ and other more general results based on the unique games conjecture. A good source for this is Per Austrin's thesis.


Constructing integer sets in which a certain equation has no solution Given some linear equation, e.g., $$x+2y=3z+4u+5w,$$ I would like to construct a set $S$ of $n$ positive integers so that equation has no solution in $S$.

Two questions:

1) How big must the integers in $S$ be? That is, how large is $\max_{a \in S} a$? Can $S$ be chosen in such a way that this latter quantity is  $O(n \log^k n)$ for some $k$?

2) How long does it take to construct (either deterministically or with randomization) a set $S$ of $n$ positive integers where a fixed linear equation has no solution, and such that the largest number $\max_{a \in S} a$ has (approximately) minimal size?

Consider an equation
$$\tag{E}a_1x_1+\dots+a_kx_k=0.$$
Let $s=\sum_ia_i$ be the sum of its coefficients.

If $s=0$, the equation (E) has solutions in every nonempty set $S$, hence you are out of luck.

If $s\ne0$, let $p$ be the smallest prime not dividing $s$. Note that $p=O(\log |s|)$. Then (E) has no solution such that $x_i\equiv1\pmod p$ for all $i=1,\dots,k$, hence the set
$$S=\{1,p+1,\dots,(n-1)p+1\}$$
works, with maximum $(n-1)p+1$. For a fixed equation (E), this is $O(n)$, and the set can be computed as easily as it gets.


Complexity of multi-linear polynomial computing Boolean function Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual,
let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest
Boolean circuit computing $f$.

As we know that every Boolean function
can be computed by polynomials in $\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$.
Let $P(f)$ be the size of the smallest arithmetic circuit(over
$\mathbb{F}_{2}$) which computes
a polynomial $P_{f}$ such that $P_{f}$ computes the same function
as $f$ on $\mathbb{F}_{2}^{n}$(correspondingly $\{0,1\}^{n}$).

It is known that $P(f)\leq\textrm{poly}(C(f))$ and $C(f)\leq\textrm{poly}(P(f))$.

We also know that there is a unique multi-linear polynomial $M_f\in\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$ such that $M_{f}$ computes the same function as $f$ on $\mathbb{F}_{2}^{n}$(correspondingly
$\{0,1\}^{n}$). Let $M(f)$ be the size of the smallest arithmetic circuit(over
$\mathbb{F}_{2}$) computing $M_{f}$.

It is clear that $C(f)\leq\textrm{poly}(M(f))$.
How about other direction?

  Can we bound $M(f)$ polynomially in terms of $C(f)$?

Anything is known about this or something related?

If I understand your question correctly, the answer is no (independently from the field, assuming $\mathsf{VP}\neq\mathsf{VNP}$).


Is BPP vs. P a real problem after we know BPP lies in P/poly? We know (for now about 40 years, thank  Adleman, Bennet and Gill) that the inclusion BPP $\subseteq$ P/poly, and an even stronger BPP/poly $\subseteq$ P/poly hold.
The "/poly" means that we work non-uniformly (a separate circuit for each input length $n$), while P without this "/poly" means we have one Turing machine for all possible input lengths $n$, even longer than, say, $n$ = the number of seconds to the next "Big Bang".

Question 1: What new would a proof (or disproof) of BPP = P contribute to our knowledge after we know BPP $\subseteq$ P/poly?

Under "new" I mean any really surprising consequences, like collapse/separation of other complexity classes. Compare this with consequences the
proof/disproof of NP $\subseteq$ P/poly would deliver.

[ADDED 08.10.2017]: One really surprising consequence
of BPP $\not\subseteq$ P would be that, as shown by Impagliazzo and Wigderson,  all(!) problems in
E = DTIME$[2^{O(n)}]$ would have circuits of size $2^{o(n)}$.
Thanks to Ryan for recalling this result.

Question 2: Why we cannot prove  BPP = P
 along similar lines as the proof of BPP/poly $\subseteq$ P/poly?

One "obvious" obstacle is finite vs. infinite domain issue: boolean circuits work over finite domains, whereas Turing machines
work over entire set $\{0,1\}^*$ of $0$-$1$ strings of any length. So, to derandomize probabilistic boolean circuits, it
is enough to take the majority of independent copies of a probabilistic circuit, and to apply Chernoff's inequality, together with the union bound. Of course, over infinite domains, this simple majority rule won't work.

But is this (infinite domain) a real "obstacle"?
By using results from statistical learning theory (VC dimension), we already can prove that  BPP/poly $\subseteq$ P/poly
holds also for circuits working over infinite domains, like arithmetic circuits (working over all real numbers); see e.g. this paper of Cucker at al.
When using a similar approach, all we would need is to show that the VC dimension of poly-time Turing machines  cannot be too large. Has anybody seen any attempts to make this latter step?

NOTE [added 07.10.2017]:  In the context of derandomization, the VC dimension of a class $F$
of functions $f:X\to Y$ is defined as the maximum number $v$ for which
there are functions $f_1,\ldots,f_v$ in $F$ such that for every $S\subseteq\{1,\ldots,v\}$ there is a point $(x,y)\in X\times Y$ with
$f_i(x)=y$ iff $i\in S$. I.e. we shatter not the sets of points via functions but rather sets of functions via points. (The two resulting definitions of the VC dimension are related, but exponentially.)

The results (known as uniform convergence in probability)
then imply the following: if for each input $x\in X$, a randomly picked function $\mathbf{f}\in F$ (under some probability distribution on $F$)
satisfies $\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$
for a constant $c>0$,
then $f(x)$ can be computed on all inputs $x\in X$ as a majority of some $m=O(v)$ (fixed) functions from $F$.  See, e.g. Corollary 2 in Haussler's paper.
[For this to hold, there are some mild measurability conditions on $F$.]

For example, if $F$ is the set of all polynomials $f:\mathbb{R}^n\to\mathbb{R}$ computable by arithmetic circuits of size $\leq s$, then all polynomials in $F$ have degree at most $D=2^s$.
By using known upper bounds on the number of zero-patterns of polynomials (see, e.g. this paper),
one can show that the VC dimension of $F$ is $O(n\log D)=O(ns)$. This implies the inclusion BPP/poly $\subseteq$ P/poly for
arithmetic circuits.

Not sure how much of an answer this is, I'm just indulging in some rumination.

Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the result would be the big breakthrough more so than the conclusion itself.

For Question 2 I want to share some background and a thought. Pretty much all the techniques and ideas we have for BPP=P, as far as I'm aware, go via "derandomization": Given any probabilistic polytime Turing Machine, construct a PRG to feed it a bunch of deterministically chosen bits instead of random ones, such that its behavior is very similar to its behavior on truly random bits. So with good enough pseudorandom generators, we get BPP=P. (Goldreich's "World of BPP=P" gives evidence that any proof of BPP=P must equate to this.)

This is pretty much along the lines of BPP $\subseteq$ P/poly, except there, the PRG is the advice string which is produced by magic. Perhaps the best answer to your Question 2 is that in P we have no magic and must come up with the advice string ourselves. Derandomization is also the idea behind the 2004 result SL=L, using tools like expander graphs.

Now consider what such a proof would imply for just one particular algorithm, the Miller-Rabin primality test. It would show the existence of some deterministic generator that picks out a sequence of integers to feed to the Miller-Rabin primality test such that, if and only if all the integers passed, then the original number was prime.

As I understand it (though I am no expert), the question of whether such a list exists and how small the numbers in it can be (in particular if it sufficices to check all the numbers below some bound) seems quite a deep question in number theory and is closely related to proving forms of the generalized Riemann Hypothesis. See this question. I don't think there's a formal implication here, but it doesn't seem like something we expect to get next week as an accidental miniature corollary of a much more general PRG construction.


Multi Head universal Turing machine It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" multi head Turing machine?

If we have a fixed number of tapes then yes we can simulate them without the logarithmic overhead. E.g simulation of two-tape (and in general $k$-tape) TMs on a two-tape machine can be done without the logarithmic factor increase.

If we want to simulate an arbitrary constant number of tapes then AFAIK we don't know any such simulation.

See these questions and the references there:

Justification of log f in DTIME hierarchy theorem

Universal simulation of Turing machines


Proving properties of Random Graphs I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas.

Consider the random graph model $G_{n,p}$ where its a random graph on n vertices and each edge is selected with probability $p$. I want to prove that a certain property $P$ is satisfied by graphs in this model with high probability ($\rightarrow 1$ as $n \rightarrow \infty$). I know/can prove the following two facts

Conditioned on the event that the graph obtained from the sample is regular, the probability of the property being satisfied is very high (something like $1 - 1/n^c$)
Given any graph G and any other graph G' that can be obtained by removing edges from G. If G satisfies the property then so does G'.

Can the above two statements be enough to make a general statement about the probability of the satisfaction of the property in $G_{n,p}$

Any references would be very helpful?

It doesn't sound hopeful in general.

For example, let $P$ be the statement "all vertices have degree 0 or 1". Let $p=1/n$ and $n$ even. Then conditioned on the event of being regular, with high probability the graph is 0-regular or 1-regular, so $P$ holds with high probability. Also $P$ is preserved by removing edges. But it is certainly not the case that $P$ holds with high probability under $G_{n,p}$.

Even in other situations (say, fixed $p$ as $n\to\infty$), I would expect that there are events $P$ of the form "maximum degree less than $d$" which satisfy your 1. and 2. but don't hold w.h.p. for $G_{n,p}$.

So something more than just the two properties you wrote down will be needed....


Is there a notion of computability on sets other than the natural numbers? Is there a notion of computability on sets other than the natural numbers?  For the sake of argument, let's say on sets $S$ that biject with $\mathbb{N}$.
It's tempting to say "yes, they are those functions of the form $g \circ f \circ g^{-1}$ where $g$ is any bijection $\mathbb{N} \to S$ and $f$ is any computable function $\mathbb{N} \to \mathbb{N}$".  I'm cautious of this definition for two reasons.

It privileges $\mathbb{N}$ over other countable sets.  Why is $\mathbb{N}$ special when it comes to defining computability?  I'd like a "coordinate free" definition of computability without reference to any privileged set in the same way I might like a "coordinate free" definition of a linear algebra concept without reference to any privileged basis.

It raises questions about the choice of $g$.  I suspect it may be possible to find contradictions by particularly pathological choices of $S$ and $g$.  For example if I choose $S = \mathbb{N}$ and $g$ some non-computable bijection is it really the case that $g \circ f \circ g^{-1}$ is computable for all computable $f$?
It's tempting to require in the definition that $g$ be computable but unfortunately that's begging the question.

Is there some general way of describing computability on countable sets other than $\mathbb{N}$?

This question is not research-level, but since it is receiving answers, I would like to offer an answer that may actually clear things up a bit, and provide references.

There is an entire area of theoretical computer science which studies computability in analysis, algebra and topology. Of central importance is the notion of computability for real numbers. In fact Turing's original paper on Turing machines starts with the following sentence:

  The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.

Sometimes it pays to go back to the source.

There are several ways to set up computability on general sets, of which one of the most general ones is realizability theory. The idea of realizability theory goes back to Kleene's paper On the Interpretation of Intuitionistic Number Theory from 1945, but has since been generalized and developed into a mini-branch of computability, with a good mix of category theory, see for instance Jaap van Oosten's book "Realizability: an introduction to its categorical side" (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).

Let me describe the idea of realizability very briefly, and discuss your "coordinate free" requirement later. Start with a model of computation, such as Turing machines, the $\lambda$-calculus, a programming language, or any other partial combinatory algebra (you can even take certain topological spaces to be "models of computation", this stuff is general). For concreteness, let us consider Turing machines. We code Turing machines by natural numbers, but note that I could have taken some other model of computation, so you should not assume that the use of $\mathbb{N}$ is in any way essential here. (Other possibilities include: the powerset of natural numbers, infinite sequences of natural numbers, the syntax of the untyped $\lambda$-calculus, certain categories of games, etc.)

A computability structure on a set $X$ is given by a relation $\Vdash_X$ between $\mathbb{N}$ and $X$, called the realizability relation, such that for every $x \in X$ there $n \in \mathbb{N}$ such that $n \Vdash_X x$. We call such structures assemblies. This definition directly corresponds to the intuitive idea that some piece of data $n$ respresents, or realizes, an element $x \in X$. (For instance, certain sequences of bits represent finite lists of pairs of strings of characters.)

Given two assemblies $(X, {\Vdash_X})$ and $(Y, {\Vdash_Y})$, a map $f : X \to Y$ is realized (or "computable") if there is a Turing machine $T$, such that, whenever $n \Vdash_X x$ then $T(n)$ terminates and $T(n) \Vdash_Y f(x)$. Again, this is a direct transliteration of what it means informally to "program" an abstract function $f$: the corresponding Turing machine does to representing data whatever $f$ does to the corresponding elements.

Assemblies may be extended to a realizability topos. A topos is a model of higher-order intuitionistic mathematics. This tells us that every realizability topos (there is one for each model of computation) contains lots of interesting objects. For instance, it contains an object of real numbers, which thus gives us computability on reals. But it also contains many other objects, such as Hilbert spaces, Banach spaces, spaces of smooth maps, etc. You asked for some other computable structure, but you got something much better: entire mathematical worlds of computability.

Since category theory and toposes can be scary and require some amount of technical proficiency in computability theory, category theory, and logic, we could also work in just one concrete topos, but we express everything in concrete non-abstract ways. A particularly good world of computation arises from Kleene's function realizability, and goes under the name of computable analysis.

Let me comment on the "coordinate free" requirement:

Switching between models of computation gives different kinds of computable worlds. This is a bit like switching between different fields giving different kinds of linear algebra.
A set $X$ may be equipped with many computability structures $\Vdash_X$, just like a set of vectors has many bases. However, while all bases are equivalent, not all computability structures on $X$ are computably equivalent.
If we work concretely with computability structures $(X, {\Vdash_X})$, that is a bit like working with matrices in linear algebra. It can be very useful, but is not abstract.
To work in a "coordinate-free" fashion, we work in a realizability topos and harness the power of category theory (yes, it's a cliché but it works).
We can even work in a "world-free" fashion: develop mathematics in intuitionistic logic, and then interpret the results in realizability toposes.


Combinatorial embedding of a graph Here : http://www.planarity.org/Klein_elementary_graph_theory.pdf (in chapter embeddings) is given definition of combinatorial embedding of a planar graph. (with definition of faces and so on) Though it could be easily used for any graph, they define planar graph as the graph, for which Euler formula holds (assuming that graph is connected). It pretty much understandable that for every plane graph the definition of faces in combinatorial embedding is similar to the definition of faces in topological embedding. (assuming that graph is connected. Otherwise in combinatorial embedding we'll have infinite face for every connected component)

The question is: if for some connected graph it's combinatorial embedding satisfies Euler formula, does this mean that this graph is planar in topological sense (it has plane embedding, i.e. it's plane graph)?

This is really less about graph per se and more about topology. A combinatorial embedding defines a 2-manifold, a topological space in which every point has a neighborhood homeomorphic to a 2-dimensional open disk: the embedding allows a face to be defined, and we can define a topological space by choosing a disk for each face and gluing them together along the graph edges. A well known theorem in topology (called the classification of 2-manifolds) tells us exactly which 2-manifolds are possible, and they are all distinguishable from each other either by whether they are orientable or whether they have the same Euler characteristic (or both) — see http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdf for some reasonable lecture notes on this subject, that include the proof you're asking for. There are no other 2-manifolds in this classification that have the same Euler characteristic as the sphere, so if you calculate the Euler characteristic and find that it matches the formula for a sphere, you know your embedding must be onto a sphere.

Finding an embedding with actual geometric coordinates in the plane, once you have a planar combinatorial embedding, is not entirely trivial but can be done e.g. using the theory of Schnyder woods. I have some lecture notes on this at http://www.ics.uci.edu/~eppstein/gina/schnyder/ for instance.


Active learning for inferring a convex optimization formulation I was wondering if anybody knows of any relevant references on the general topic of active learning for gradually inferring/updating a convex opt. formulation.
As a specific example, I am thinking of a system where a learner can query an oracle the validity of the current best solution to incrementally learn constraints or coefficients of an LP cost function.
Update
I am interested in problems and methods where we don't have access to the full definition of the problem (e.g. in LP the constraints that define the polytope, or the cost coefficients are unknown). Yet we may be able to iteratively solve the problem by iteratively asking a sequence of questions to an oracle until the last query confirms we have reached an optimal solution (an optimal vertex in LP)

Those are some very technical terms to be throwing around and although I'm familiar with some of the literature from either side, I don't think that I've ever seen them used together. What is the distinction between using a convex program and an LP? They are significantly different, and you refer to both in your question. What you are mentioning sounds really similar to cutting plane or column generation methods in optimization, so perhaps you want to check those out and see if any active learning approaches have been used. In most cutting plane methods, there is usually an efficient (but ad hoc) way to search for violated constraints, usually found by an optimization subproblem; that could be considered similar to active learning but I'm not sure how a canonical active learning approach would look different.


What is the difference between proofs and programs (or between propositions and types)? Given that the Curry-Howard Correspondence is so widely spread/extended, is there any difference between proofs and programs (or between propositions and types)? Can we really identify them?

The programming languages people use day to day don't fit so well into the Curry-Howard correspondence, because their type systems are too weak. To say something interesting using Curry-Howard for imperative programs, one needs to have a more sophisticated type system. The book Adapting Proofs-as-programs pushes this angle with the aim of synthesising imperative programs. With dependent types becoming more and more popular, certainly in research functional languages (Agda, Epigram), the distinction is becoming blurrier. Of course you can do program synthesis/extraction within the Coq theorem prover (and presumably others), which is of course based on Curry-Howard.

The Curry-Howard correspondence can also be used in situations where the proofs do not so clearly correspond to programs (or they are not programs anyone will ever run). One example of this is in Proof-carrying authorization. The propositions correspond to statements about who is authorized to do what. Proofs provide the required evidence that a proposition holds, thus an authorization request is permitted. In order to encode the proofs, proof terms are introduced (via Curry-Howard). Proof terms are sent between parties as representations of proofs of the validity of authorization requests, but they are not considered programs.


Bent and hyper-bent functions Is the AND logic function considered to be a bent function? If it is, how could one make a hyper-bent funtion using logic gates? Thank you (two questions in one: very efficient :) )

Answered by Claude Carlet in a private email. The AND function is bent as long as it has only two variables.


Quick encoding of balanced vectors It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. Is it possible to define such $F$ so that given $x$ we can compute $F(x)$  efficiently ?

Thanks.

Let's consider $n$-bit strings $x$. Definitions:

$f(x,i)$ = bit string $x$ with last $i$ bits complemented.
$b(x)$ = "imbalance" of $x$: number of 1s in $x$ $-$ number of 0s in $x$.

Now fix a string $x$. Consider the function $g(i) = b(f(x,i))$. Observations:

$g(0) = b(x)$.
$g(n) = -g(0)$.
$|g(i) - g(i+1)| = 2$ for all $i$. We either remove one 0 and add one 1 or vice versa.

Now it follows that there exists an $i$ such that $-1 \le g(i) \le +1$.

Hence we can construct an $(n+O(\log n))$-bit string $y$ as follows: concatenate $f(x,i)$ and the binary encoding of the index $i$. The absolute value of the imbalance of $y$ is $O(\log n)$. Moreover, we can recover $x$ given $y$; the mapping is bijection.

Finally, you can add $O(\log n)$ dummy bits that reduce the imbalance of $y$ from $O(\log n)$ to $0$.