Computing volume of high-dimensional convex polyhedra I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-dimensional space with parameters bounded roughly as follows: $d \le 50$  and $n \le 1000$. Note, that there is no guarantee on the number of faces.

Jeff Erickson's page has a link to a program Vinci-1.0.5, which has a hard limit of 255 faces. This is a limitation of the implementation, the algorithm itself can probably handle more faces in reasonable time.

I couldn't find any implementations of the Markov chains based method for estimation, although I guess they will be even less efficient.

Is there any software, that can handle the range of parameters described above or some moderate relaxation of it? I would be very grateful for any other references as well.

You can try and use qhull http://www.qhull.org/ - it can compute the volume of the convex hull of the vertices. However, a priori I do not see any reason for it to perform reasonably for your range of numbers. If qhull does not work, you can try CGAL/GALIA. In the worst case, you can try and impelement one of the random walk algorithms you mentioned - they should not be too hard to implement in this case, but the constants involved might be very large...


One-Way Permutations without Trapdoor In Short: Assuming one-way permutations exist, can we construct one that has no trapdoor?
More info:
A one-way permutation is a permutation $\pi$ which is easy to compute, but hard to invert (see the one-way-function tag wiki for a more formal definition). We usually consider families of one-way permutation, $\pi = \{\pi_n\}_{n \in \mathbb{N}}$, where each $\pi_n$ is a one-way permutation, acting on a finite domain $D_n$. A trapdoor one-way permutation is defined as above, except that there exists a trapdoor set $\{t_n\}_{n \in \mathbb{N}}$ and an poly-time inverting algorithm $I$, such that for all $n$, $|t_n| \le {\rm poly}(n)$, and $I$ can invert $\pi_n$ provided that it is given $t_n$.
I know one-way permutations which are generated so that it is infeasible to find the trapdoor (yet the trapdoor exists). An example, based on RSA-assumption, is given here. The question is,

Do there exist (families of) one-way permutations which do not have a trapdoor (set)?

Edit: (More Formalization)
Assume there exists some one-way permutation $\pi$ with (infinite) domain $D \subseteq \{0,1\}^*$. That is, there exists a probabilistic polynomial-time algorithm $\mathcal{D}$ (which, on input $1^n$, induces some distribution over $D_n=\\{0,1\\}^n \cap D$), such that
for any polynomial-time adversary $\mathcal{A}$, any $c>0$, and all sufficiently large integer $n$:
$\Pr[x \leftarrow \mathcal{D}(1^n) \colon \quad \mathcal{A}(\pi(x))=x]<n^{-c}$
(The probability is taken over the internal coin tosses of $\mathcal{D}$ and $\mathcal{A}$.)
The question, is whether we can construct a one-way permutation $\pi'$, for which there exists a probabilistic polynomial-time algorithm $\mathcal{D}'$ such that for any poly-size family of circuits $\mathcal{A}'=\{\mathcal{A}'_n\}_{n \in \mathbb{N}}$, any $c>0$, and all sufficiently large integer $n$:
$\Pr[x \leftarrow \mathcal{D}'(1^n) \colon \quad \mathcal{A}'_n(\pi'(x))=x]<n^{-c}$
(The probability is taken over the internal coin tosses of $\mathcal{D}'$, since $\mathcal{A}'$ is deterministic.)

I don't know about constructions from general assumptions, but you can get a plausible candidate for a "one-way permutation without a trapdoor" by using discrete log modulo a prime $p$.  That is, let $g$ be a primitive root modulo $p$, and define $\pi(x) = g^x\!\mod p$.  Then $\pi$ is a permutation on the integers between $1$ and $p-1$, and it is generally assumed to be one-way.  For the "no trapdoor" part, I suppose you need to define exactly what that means, but as far as I know, we don't have any way to set things up to enable inversion.  (If we did, then it'd have all sorts of cool (positive) applications in cryptography!)


Questions about Farhi's pre-Adiabatic paper I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation.

I guess I understand most of the math and physics but I am struggling with the intuitions used throughout the paper. Here are my questions.

Introduction of $|r\rangle$ on page 3:
I understand that $|r\rangle$ and $|w\rangle$ are orthonormal. But I don't see why the authors introduced this state.

Use of Norm in equation 17 on page 4:
The equation is as follows.
$$\sum_w |||\Psi_w, t\rangle - |\Psi, t\rangle||^2 \ge N \varepsilon$$
There are more than one kind of norms. What kind of norm are we talking about here? Why? What is the physical significance of this quantity in this context?

Everything interesting happens in this paper happens within the 2D subspace generated by the two vectors $|s\rangle$ and $|w\rangle$. The vector $|r\rangle$ is a vector from this subspace orthogonal to $|w\rangle$, giving us the basis $|w\rangle, |r\rangle$, where the analysis will be very simple (using 2x2 matrices).

The norm in the second question is simply $|||a\rangle||^2 = \langle a | a \rangle $. The meaning of individual terms in the sum is: "Does the result of our (Hamiltonian) algorithm actually get away from the (useless) state we would get without applying the oracle at all?" If this term is small for many different instances (different $w$'s), the algorithm doesn't work, as it would likely give the same (wrong) answer for these instances. Thus, if the sum over all of the $w$'s were small, it would tell us that the algorithm fails. If it is large, it doesn't immediately mean it works, however, having the sum large is a necessary condition for a successful algorithm.


How fast can we find and disconnect roots in a forest? Consider a forest of rooted trees. The problem is to support two operations:

disconnect(v): if v is the root of some tree in the forest, remove all edges of v;
findroot(v): find root of the tree containing node v.

Are there known worst-case lower bounds for such operations? In particular, is it possible to support both operations in $O(1)$ worst-case time?

Note that this problem is equivalent to the following version of marked ancestor problem:

mark(v): mark node v of the rooted tree, if its direct parent already marked or if v is the root;
firstmarked(v): return nearest marked ancestor of v.

There is a known lower bound trade-off if we allow mark(v) to mark any node:

  We present a new lower bound for the marked ancestor problem in the cell probe model with word size b between the update time $t_u$ and the query time $t_q$, $$t_q = \Omega(\frac{\log n}{\log(t_u b \log n)})$$

  BRICS RS-98-7 Alstrup et al.: Marked Ancestor Problems

For a reasonable word size $b$, this trade-off implies that it is impossible to support both operations within $O(1)$ worst-case time.

Alstrup et al. prove the same trade-off for various related problems. However I couldn't find any assertions about my version: their proof technique seems to rely on arbitrary gaps between marked nodes.

The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. Their solution is based on Euler tour of the tree with union-split-find structure (and fast LCA for trees with unbounded degree).

The same paper states that it is an open problem whether this bound is tight.

[1] D. Breslauer and G. F. Italiano. Near real-time suffix tree construction via the fringe marked ancestor problem. Selected papers from the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011) https://www.sciencedirect.com/science/article/pii/S1570866712001062#br0230


Efficiently finding the minimum number of transpositions needed to sort a list I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are.

For example, the list [1, 1, 2, 0] requires 2 transpositions:

[1, 1, 2, 0] // Start
[1, 1, 0, 2] // Swap index 2 and 3
[0, 1, 1, 2] // Swap index 0 and 2

The list [0, 1, 0, 0] requires 1 transposition:

[0, 1, 0, 0] // Start
[0, 0, 0, 1] // Swap index 1 and 3

The list [2, 2, 2, 2] requires 0 transpositions because it is already sorted.

Some meta information:
1) The list may have repeated elements, so simply using the Cayley distance between the sort and the identity permutation will not work.
2) This Math Overflow question is related.

Unfortunately, the problem is NP-hard in general, according to Amir, Hartman, Kapah, Levy and Porat (see http://epubs.siam.org/doi/abs/10.1137/080712969), even if each symbol appears at most three times. I didn't find a mention of a constant factor approximation algorithm, or of something reasonably fast to tackle the problem. Are there any additional restrictions you can think of in your case?

EDIT: the authors also give a 3/2-approximation algorithm, but I don't know if it's good enough for your purposes.


Complexity of computing a densest minor Consider the following problem.
Input: An undirected graph $G=(V,E)$.
Output: A graph $H$ which is a minor of $G$ with the highest edge density among all minors of $G$, i.e., with the highest ratio $|E(H)|/|V(H)|$.

Has this problem been studied? Is it solvable in polynomial time or is it NP-hard? What if we consider restricted graph classes like classes with excluded minors?

If we ask for the densest subgraph instead, the problem is solvable in polynomial time. If we add an additional parameter $k$ and ask for the densest subgraph with $k$ vertices, the problem is NP-complete (this is an easy reduction from $k$-clique).

Ok, since there's still nothing here in the way of an answer, let me at least make a couple of simple observations:

For graphs of bounded treewidth it should be possible to find a densest minor (or even a minor with specified numbers of edges and vertices) by the usual sort of dynamic program on the tree decomposition, where each state of the dynamic program keeps track of the number of edges and vertices in the part of the minor living in a subtree of the decomposition, the subset of vertices in the bag of the decomposition that participate in the minor, the equivalences between vertices in this subset caused by the minor contractions in the whole graph, and a refinement of this equivalence relation caused by the contractions in the part of the minor living in the subtree.

If so, it would follow that, when the density is below three, it should be possible to find the densest minor in polynomial time (with a constant factor that depends on how close to three the density is). For, the graphs whose densest minor has density $\le 3-\epsilon$ have planar forbidden minors and therefore bounded treewidth.


References on model checking and pi calculi I'm a mathematician and it looks like I need to learn about these topics. What would be good references that go into the technical details of the following topics?

(s)pi calculus

model checking

I'm not really interested in applying these tools, but in their actual mathematical constructions, since it looks like they might contain ideas that I'm looking for.

For the $\pi$-calculus, the following texts should be of interest. [1] is a relatively gentle introduction while [2] summarises the state of the art about 10 years ago. A lot  of progress has been made since, but that's not yet written up in a textbook. The original papers [3] are also quite readable but contain much detail that may overwhelm a novice (or may be instructive, since it's usually omitted in later accounts). Milner has written a little tutorial [4]. Finally, if you have not encountered process theory, the original CCS book [5] might be a good place to do so. It deals with CCS, a predecessor to the $\pi$ calculus, and key technical ideas in the theory of $\pi$-calculus like bisimulation are explained in a simpler setting.

Regarding the spi-calculus, I suggest to look at the original paper [6], but note that the spi-calculus has largely been superseded by the applied pi-calculus [7]. The applied pi-calculus is widely used in modelling cryptographic protocols. [8] is a tutorial of applied pi.

Communicating and Mobile Systems: The $\pi$ Calculus, by R. Milner.
The $\pi$-Calculus: A Theory of Mobile Processes, by D. Sangiorgi and D. Walker.
A Calculus of Mobile Processes, Part 1 and Part 2, by R. Milner, J. Parrow and D. Walker.
The Polyadic pi-Calculus: A Tutorial, by R. Milner.
Communication and Concurrency, by R. Milner.
A Calculus for Cryptographic Protocols The Spi Calculus, by M. Abadi and A. Gordon.
Mobile values, new names, and secure communication, by M. Abadi and C. Fournet.
Applied pi calculus, by M. Ryan and B. Smyth.

If you spell out the ideas you are looking for, maybe we can give you more focussed reading recommendations.


Fast algorithm for scoring a sequence Let us define:

$U = \left\{ u_j \right\}, 1 \leq j \leq N = 2^{L}$, the set of all different binary sequences of length $L$.
$V = \left\{ v_i \right\}, 1 \leq i \leq M = \binom{L}{k}2^{k}$, the set of all different gapped binary sequences with $k$ known bits and $L-k$ gaps.

We have a score function $f : V \rightarrow R$, that associates a real number $c_i$ to any of $v_i$'s; i.e. $c_i = f(v_i)$.

Given any pair of $u_j$ and $v_i$, we can count the number of mismatches, by counting the known bits of $v_i$ that are different in $u_j$.  For example given $L=7, k=4$:

$\text{diff}(\text{"0001100"}, \text{"01...01"}) = 2$,

because the second bit and the last bit are different (gaps can match to any value).

We have a weight associated to the number of mismatches. In general, the number of mismatches can be any number between $0$ and $k$. so we have $k+1$ such weights given by $\left \{ w[0],w[1],\ldots,w[k] \right \}$.

For a given sequence $S$ of $T$ bits, $S = s_0s_1 \ldots s_{T-1}$, we define the total score as the weighted sum of all the $c_i$'s for all the the contiguous $L$-bits subsequences of $S$ weighted by their distance:

$g(S)=\sum_{j=0}^{T-L}\sum_{i=1}^{M} c_i \times w[\text{diff}(v_i, s_js_{j+1} \ldots s_{j+L-1})]$.

the obvious algorithm is as follows:

g:=0;
for j:=0 to T-L
  for i:=0 to M
    g:=g+c[i]*calcDif(S,j,i)

where calcDif() takes $O(L)$ to count number of mismatches. so the overall time would be in the order of $T*M*L$.

What is a better approach to calculate the total score more efficiently? Typical values are: $L=20, k=10, T=2000$?

The problem can be solved at least in $O(M \cdot T \log T)$ which is theoretically better, but may be slower than $O(M\cdot T\cdot L)$ in practice if $L$ is comparable to $\log T$.

Let's show how to find a score of each $v_i$ independently in $O(T \log T)$. For any (possibly gapped) string $W = w_0 w_1 \ldots w_{n-1}$ define two polynomials $zeros_W(x)$ and $ones_W(x)$ as follows:

$$ zeros_W(x) = \sum_{i=0}^{n-1} [w_i = ''0'']x^i$$
$$ ones_W(x) = \sum_{i=0}^{n-1} [w_i = ''1'']x^i$$

where $[P]$ is Iverson notation.

For example, $zeros_{01...01}(x) = 1 + x^5$, $ones_{01...01}(x) = x + x^6$, $zeros_{0001100}(x) = 1+x+x^2+x^5+x^6$ and $ones_{0001100}(x) = x^3 + x^4$.

Then compute coefficients of the following polynomial $$c(x) = zeros_S(x) \cdot ones_{rev(v_i)}(x) + ones_{S}(x) \cdot zeros_{rev(v_i)}(x) = \sum_{j}c_j x^j$$ where $rev(W) = w_{n-1} \ldots w_1 w_0$ is just reversed $W$. It's easy to see that $c_{L-1+k}$ will be equals exactly to the difference between $s_k s_{k+1} \ldots s_{k+L-1}$ and $v_i$. For example, for $S=''0100''$ and $v_i = ''10''$ $c(x)$ will be equal to $(1+x^2+x^3)\cdot x + x \cdot 1 = 2x + x^3 + x^4$ which gives us all interesting differences (2, 0, 1) so we can calculate score in linear time. Thus the problem is reduced to polynomial multiplication, which can be done in $O(T \log T)$ using FFT.

The possible disadvantage of such approach is that FFT has essential constant hidden in its big-O, so using $O(T^{1.585})$ Karatsuba multiplication or something similar may work better in practice for not very large $T$.


PHOAS with extrinsic typing? Parameterized Higher Order Abstract Syntax (PHOAS) is a representation of syntax trees that allows the host language's binding to be used to represent binding in the language being modelled, while fulfilling the strict positivity requirements that most dependently typed languages impose . This is done by modelling the type of variables as a type parameter: $term : (V : Set) \to Set$.

The original PHOAS paper describes a way to model System F using intrinsic typing: the syntax tree of a term is indexed by its type, so only well typed terms can be constructed.

The problem I have is that, I would like to use PHOAS to model a dependently typed calculus. Having terms and types be in the same syntactic category means that (as far as I can see) the extrinsic approach is not feasible: we can't have $term\ (V : Set) :  term \to Set$.

I'm wondering if there has been any work done on using PHOAS to model extrinsically typed languages: that is, where our syntax allows ill-typed terms to be formed, and we have a separately defined relation between telescopes, terms and types, i.e. traditional $\Gamma \vdash t : T$ typing rules.

In particular, I'm unsure how to model a term whose free variables all come from the given telescope. PHOAS uses $Term_0 = \forall V . term\ V$ to model closed terms, and $Term_1 = \forall V . (V \to term\ V)$ to model terms with one open variable. How can I generalize this to arbitrary telescopes? Should my typing rules refer to $term$s or $Terms$?

The standard well-formed-related predicate can be relatively easily extended to handle untyped PHOAS.  The main subtlety is how to handle reduction at the type level.  Here's a start of a two-place relation for well-typed in Coq:

Require Import Coq.Lists.List.
Reserved Infix "@" (left associativity, at level 11).
Local Open Scope list_scope.

Inductive expr {var : Set} : Set :=
| Var (v : var)
| U : expr
| Pi (s : expr) (d : var -> expr)
| Abs (tx : expr) (f : var -> expr)
| App (f x : expr).
Declare Scope expr_scope.
Delimit Scope expr_scope with expr.
Infix "@" := App : expr_scope.

Inductive wf {var1 var2} : list ((@expr var1 (* t1 *)) * var1 * (@expr var2) (* t2 *) * var2) -> @expr var1 (* t1 *) -> @expr var1 -> @expr var2 (* t2 *) -> @expr var2 -> Prop :=
| wf_Var {G t1 v1 t2 v2} : List.In (t1, v1, t2, v2) G -> wf G t1 (Var v1) t2 (Var v2)
| wf_U {G} : wf G U U U U
| wf_Pi {G s1 s2 d1 d2}
  : wf G U s1 U s2
    -> (forall v1 v2,
           wf ((s1, v1, s2, v2) :: G)
              U (d1 v1) U (d2 v2))
    -> wf G U (Pi s1 d1) U (Pi s2 d2)
| wf_Abs {G s1 s2 d1 d2 f1 f2}
  : wf G U s1 U s2
    -> (forall v1 v2,
           wf ((s1, v1, s2, v2) :: G)
              (d1 v1) (f1 v1) (d2 v2) (f2 v2))
    -> wf G (Pi s1 d1) (Abs s1 f1) (Pi s2 d2) (Abs s2 f2)
| wf_App {G s1 d1 s2 d2 f1 x1 f2 x2}
  : wf G (Pi s1 d1) f1 (Pi s2 d2) f2
    -> wf G s1 x1 s2 x2
    -> wf G (App (Abs s1 d1) x1) (App f1 x1) (App (Abs s2 d2) x2) (App f2 x2)
| wf_App_nd {G s1 d1 s2 d2 f1 x1 f2 x2}
  : wf G (Pi s1 (fun _ => d1)) f1 (Pi s2 (fun _ => d2)) f2
    -> wf G s1 x1 s2 x2
    -> wf G d1 (App f1 x1) d2 (App f2 x2).


Almost regular subhypergraph of hypergraph with large minimal degree I am interested in knowing whether the following conjecture is true or not:

For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$.
Let $\mathcal{S}$ be a finite family of sets of size at least $M$ in which each element appear at most $d$ times.
There exists a set $X$ such that $\delta M \leq |S \cap X| \leq M$ for all $S \in \mathcal{S}$.

We can also formulate this in terms of hypergraphs:

For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$.
Let $H$ be a $d$-uniform hypergraph in which each vertex has degree at least $M$. There is a subhypergraph $H'$ of $H$, obtained by only deleting hyperedges, in which the degree of each vertex is between $\delta M$ and $M$.

(If we want to make the statements completely equivalent, we should ask all hyperedges to have uniformity at most $d$ rather than exactly $d$.)
The question has the flavor of Hall's matching theorem and of Beck-Fiala, but so far I was unable to prove the conjecture using these tools. Perhaps I am missing some simple argument, or perhaps there is a simple counterexample.

Unfortunately the conjecture is wrong (for $d \geq 2$). Here is a counterexample for $d=2$.

Suppose that the conjecture (in its graphical formulation) held for some $c,M_0 > 0$. Consider a complete bipartite graph in which the left side has $M^2$ vertices and the right side has $M$ vertices. Thus the left degrees are $M$ and the right degrees are $M^2$. In order to create a subgraph in which all right degrees are at most $M$, we need to remove at least $M(M^2-M)$ edges. On the other hand, any subgraph in which all left degrees are at least $cM$ must have at most $(1-c)M^3$ edges removed. This means that $M^3 (1-1/M) \leq (1-c)M^3$, which is false for large enough $M$.


NP-hardness of a Set Cover specialization Is the following problem NP-hard?

Given a set of $N$ real numbers (targets) $x_1,\dotsc,x_N$ and a "trident" defined by two distances $a$, $b$ from the center of the trident, what is the minimum number $K$ of positions $p_1,\dotsc,p_K$ of the trident to cover all targets, i.e.
$$ \bigcup_{k=1}^K \{p_k-a,p_k,p_k+b\} \supseteq \{x_1,\dotsc,x_N\}.$$

Obviously, this is a special case of the set cover problem: Considering all sets $\{p_k-a,p_k,p_k+b\}$, with $p_k\in\{x_n+t\mid n\in\{1,\dotsc,N\}, t\in\{a,0,-b\}\}$ representing all "relevant" potential positions, we look for the minimum number of sets covering the universe $\{x_1,\dotsc,x_N\}$. Equivalently, we can represent the problem as a bipartite graph of position and target nodes and consider the hitting set problem.

Note that the problem is not NP-hard if the trident loses one of its "jags": Then each target can be covered from 2 positions and each position covers at most 2 targets, so the corresponding bipartite graph of potential positions and targets is a union of paths. In each path it is easy to determine a minimal hitting set (namely, the inner position nodes).

But is the trident case NP-hard?

Overview

This problem is NP-hard; more precisely, the associated decision problem (in which we ask whether a target number of tridents $k$ can cover all of the given $x_i$s) is NP-hard. We will refer to this decision problem as the Numerical Trident Cover Problem.

To prove that the Numerical Trident Cover Problem is NP-hard, we introduce the following intermediate problem, which we will call the Grid Triangle Cover Problem:

Input: A finite set $S \subset \mathbb{Z}^+ \times \mathbb{Z}^+$ of integer coordinate pairs and an integer value $k$.

Output: Yes or no, with an output of yes if and only if there exists a set $T \subset \mathbb{Z} \times \mathbb{Z}$ with $|T| \le k$ such that $S \subseteq \bigcup_{(x,y) \in T} \{(x, y), (x, y+1), (x+1, y)\}$

Thinking about this problem graphically, we are given a subset of the integer lattice and asked to cover every point in this subset with $k$ side-length-$(1, 1, \sqrt{2})$ right triangles in a particular orientation (in particular these triangles must have vertices of the form $(x, y)$, $(x, y+1)$, and $(x+1, y)$). We are asked to say yes if and only if this is possible.

To show that Numerical Trident Cover is NP-hard, we provide two reductions: a reduction from Planar 3SAT to Grid Triangle Cover and a reduction from Grid Triangle Cover to Numerical Trident Cover. Together, these compose into a reduction from the NP-hard problem Planar 3SAT to the Numerical Trident Cover problem, implying that Numerical Trident Cover is NP-hard.

Note that since we are using real numbers in the Numerical Trident Cover Problem, the issue of encoding and input size should come up. We avoid this problem by always using numbers of the form $p + q\sqrt{2}$ in our Numerical Trident Cover instances, allowing for an efficient encoding simply by encoding $p + q\sqrt{2}$ as $(p, q)$. In fact, the problem is still hard even if the numbers are further restricted to be integers, though that reduction requires a bit more work, and is therefore omitted here.

Reduction 1: From Grid Triangle Cover to Numerical Trident Cover.

Suppose we are given an instance of the Grid Triangle Cover problem consisting of a set $S \subseteq \mathbb{Z}^+ \times \mathbb{Z}^+$ and a number $k$.

Then we construct an instance of Numerical Trident Cover (consisting of a list of real numbers $x_1, ..., x_N$, a pair $a, b$, and a target number of tridents $k'$) as follows.

Let the elements of $S$ be $s_1 = (p_1, q_1), s_2 = (p_2, q_2), ..., s_{|S|} = (p_{|S|}, q_{|S|})$. For each $i$ from $1$ to $N = |S|$ let $x_i = -p_i + q_i \sqrt{2}$. Let $a = 1$ and $b = \sqrt{2}$. Finally, let $k' = k$. This is the output instance of Numerical Trident Cover.

This reduction is clearly a polynomial time operation, so the only thing left to show is that the reduction is answer preserving.

To do this, consider the "reasonable" places to put the tridents. The only places where we can put a trident so that it hits at least one $x_i$ are locations of the form $x_i$, $x_i + a$, or $x_i - b$. For each of the $x_i$s, these three values are all of the form $-v_a + v_b \sqrt{2}$ for some integers $v_a$ and $v_b$. Thus we can restrict our attention to numbers of the form $-v_a + v_b \sqrt{2}$. Define the bijection $f$ between the set of all $p + q \sqrt{2}$ and the set of all pairs of integers according to the rule $f(-v_a + v_b\sqrt{2}) = (v_a, v_b)$. Note that $f$ maps $x_i$ to $s_i$.

Also note that if a trident is located at $-p + q\sqrt{2}$ then its three prongs are located at $-(p+1) + q\sqrt{2}$, $-p + q\sqrt{2}$, and $-p + (q+1)\sqrt{2}$. In other words, the image of the three prongs under $f$ consists of points $(p,q)$, $(p+1, q)$, and $(p, q+1)$. The image of a trident under $f$ is exactly a triangle of the form we are using to cover the values in $S$. Similarly, every properly oriented triangle maps to a trident under $f^{-1}$. In fact, the triangles and tridents are in exact bijection under $f$.

Since $f$ is bijective, it is clearly the case that some set of tridents covers $\{x_1, ..., x_{|S|}\}$ if and only if the images of those tridents under $f$ cover $S = \{s_1, ..., s_{|S|}\} = \{f(x_1), ..., f(x_{|S|})\}$. Then since the image of a trident under $f$ is a side-length-$(1,1\sqrt{2})$ triangle in the proper orientation, we can conclude that we can cover the $x_i$s with $k$ tridents if and only if we can cover the set $S$ with $k$ side-length-$(1,1\sqrt{2})$ triangles in the proper orientation. We conclude that the reduction is answer preserving.

Reduction 2: From Planar 3SAT to Grid Triangle Cover.

For this reduction, we are given a 3SAT instance in the form of a planar bipartite graph. The vertices in one part correspond to variables, and the vertices of the other part, each of degree 3, correspond to clauses. Each edge is labeled as positive or negative, indicating which way the variable is included into the clause (positively or negatively).

Then we can construct a Grid Triangle Cover instance $(S, k)$. We can construct $S$ out of variable gadgets, clause gadgets, and wire gadgets. After describing these gadgets and their desired behaviors, we will be able to describe how $k$ is computed.

First we describe a wire. A wire consists of a sequence of an odd number of points (in the integer lattice) where the first and last are called terminals such that every consecutive pair can be covered by a triangle without the triangle hitting any other point in the wire. As an example consider the following wire:

xoo       x
   o       o
   o ooo   o
   o o  oooo
    oo

The point of a wire is that it can be satisfied using a minimum number of covering triangles in two ways. In particular, if $p$ is the number of non-terminal points in the wire ("o"s in the above example) then $\frac{p+1}{2}$ triangles are necessary and those triangles will, in addition to covering the non-terminal points, cover exactly one of the two terminals.

Here we show the two ways to cover the example from above (where two points are labeled the same number if they are covered by the same triangle):

x11       9
   2       9
   2 556   8
   3 4  6778
    34

or

112       x
   2       9
   3 566   9
   3 5  7788
    44

One concern is that we might wish to connect two terminals with a wire but be unable to do so because any "wire" between those two terminals would have even length. However, that is not the case: we can always choose a route for a wire to make that wire have odd length (and therefore be a valid wire). Replacing any horizontal segment of wire of length 6 with the following length 7 wire segment can fix the parity of the wire length:

oo  oo
  ooo

Next we introduce a clause gadget. A clause simply connects one of the terminals of three wires in such a way that if one of the wires is satisfied so that the shared terminal is covered, then the triangle covering that shared terminal does not cover any points from the other wires:

      o
      o
      o
   ooox
       ooo

In order for the shared terminal to be covered, at least one of the three wires must be satisfies in such a way that the triangles satisfying the wire do not cover the wires' non-shared terminal.

Finally, we introduce the variable gadget. The variable gadget is a large wire-like loop (of even length) with terminals optionally occurring to the side every three rows as follows:

oo
o o
o ox
o o
o o
o ox
o o
o o
o ox
o o
o o
o ox
o o
 oo

The variable can grow vertically to accommodate the necessary number of terminals The terminals on rows of even parity correspond to positive occurrences of the variable and those on rows of odd parity correspond to negative occurrences. As with wire, the non-terminal points of the variable gadget can be satisfied using the minimum number of triangles (half the number of points in the loop) in exactly two ways. Those two settings cover either all the positive occurrence terminals or all the negative occurrence terminals of the variable gadget.

Putting it all together is pretty obvious: we build the bipartite graph using variable gadgets, clause gadgets (shared terminals) and wires connecting the terminals. The total number of triangles necessary to cover the non-terminal points of the wires and variables is then the target number of triangles.

Clearly we cannot cover the entire grid with fewer than that triangles. Furthermore, we can be assured that the non-terminal points are each covered since the variables and wires will each be satisfied in one of the two ways described. Thus the only task is to satisfy the terminals.

At each variable, either all the positive or all the negative occurrence terminals will be satisfied by the variable gadget. The other terminals at the gadget have to be satisfied by their attached wires. Then the clause terminals can be satisfied if and only if every clause is attached to at least one wire whose other terminal did not already use up the wire (a wire whose other terminal was satisfied by its attached variable gadget). In other words, the terminals are all satisfied if and only if the assignment of variables according to the settings of the variable gadgets satisfies every clause.

As you can see, the produced Grid Triangle Cover instance is a yes instance if and only if the input Planar 3SAT instance is a yes instance. Since this reduction is also polynomial time (all of the gadgets require space polynomial in the size of the input instance), we conclude that we have a valid reduction.


W[1]-hard problems with FPT time approximation algorithms I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are:

R1. W[1]-hard.

R2. Admit a (preferably constant) approximation algorithm in FPT time.

The problem I'm familiar with is counting the number of simple paths of length $k$ in a graph. It is known to be #W[1]-hard, but admits a $(1+\epsilon)$-approximation in FPT time (for any constant $\epsilon$).

Also interesting would be problems that satisfy R1 and R2, and also:

R3. There exists $\epsilon>0$ such that the problem is not $(1+\epsilon)$ approximable in FPT time (unless W[1]=FPT).

  What other problems satisfy R1 and R2, and possibly R3?

In the Directed Odd Cycle Transversal problem the input is a graph $G$ and the task is to find a smallest set $S$ of vertices such that $G-S$ has no (directed) cycles of odd length. In the parameterized version we are also given an integer $k$ and asked whether a solution of size at most $k$ exists.

In this paper we prove that (R1) the problem is W$[1]$-hard, (R2) that it admits a factor 2 approximation algorithm in time $2^{k^{O(1)}}n^{O(1)}$, and that (R3’) assuming a hypothesis somewhat stronger than $FPT \neq W[1]$ that there exists an $\epsilon > 0$ such that the problem does not admit a $(1+\epsilon)$ approximation algorithm in time $f(k)n^{O(1)}$.


Bounded computation and incompleteness Is there a complete theory T over a logical language L such that bounded computation may be encoded in it? Computational questions can be framed as arithmetical ones by interpreting them over natural numbers. Let $\phi$ be a first order statement which states that $P \neq NP$ in the language of arithmetic. Then either $\phi$ belongs to Th(N) or its negation does (i.e.) it contains the answer to the P vs NP problem.

However, since Th(N) is not RE, I would like to know if computation (in particular, bounded computation) can be interpreted over some alternate structure with nicer properties (i.e. whose theory is decidable). Note that if a theory is complete, then it cannot be RE-complete (i.e.) deciding whether any $\phi$ belongs to the theory is not RE-complete, it is either recursive or RE-hard.

The context is Razborov's paper on "Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic" in which he shows that the bounded arithmetic theory $S_2^2(\alpha)$ cannot prove polynomial circuit lower bounds for SAT assuming Strong Pseudo Random Generators (SPRGs) exist. Here the statement "SAT does not have poly size circuits" can be written as a bounded sentence when interpreted over the naturals.

I want to understand if the presence of a total order is required for the interpretation of computation inside a structure. Suppose I take graphs with the minor ordering (which is a WQO), is it possible to interpret computation inside this? My only point of reference is the undecidability of First order satisfiability by reduction from the Halting Problem. In this case, we do not seem to require a successor function, just the idea of a "future" configuration with certain properties. I understand that this setting is different from interpretation inside a structure. I want to understand this difference.

It depends on what you mean by "encode computation". There are many papers on the topic, a good starting reference is "Metamathematics of First Order Logic" by Petr Hajek and Pavel Pudlak. Pavel defined what is called sequential theory for theories where you can encode strings (I don't see if being a computation or not means much).

P vs. NP can be studied for other structures, first order logic with order is sufficient to phrase the question whether every $\Sigma^b_1$ formula is equivalent to a quantifier-free one (and you can enrich the language to contain all operations that you want to assume to be efficient). The strings case is old (I will add reference later). It is also studied over real numbers (in the context of BSS model).

The question can be studied over structures without order, see the work on algebraic complexity like Valiant's VP vs. VNP and also GCT (for complex numbers and other fields).


Sources of open problems? I'm wondering if there are some known sources of open TCS problems? I'm a junior studying math/CS and would like to know of some accessible problems that I could start thinking about!

Thanks so much!

Here's a partial list of collections of open problems in TCS, broadly construed. Note that a collection of "major open problems" exists already on this site: http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/251#251.

In Computer Science (Wikipedia): https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science
Sublinear time algorithms: http://sublinear.info/index.php?title=Main_Page
Analysis of Boolean Functions: http://lanl.arxiv.org/abs/1204.6447
Computational geometry: http://cs.smith.edu/~orourke/TOPP/
Exact algorithms: http://faculty.cs.tamu.edu/chen/courses/cpsc669/2011/notes/ww1.pdf
Formal languages, etc.: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html
Parameterized complexity: http://fpt.wikidot.com/open-problems
Topological graph theory: http://www.cems.uvm.edu/~darchdea/problems/problems.html
Embeddings of finite metric spaces: http://kam.mff.cuni.cz/~matousek/metrop.ps
Lambda calculus, proof theory, semantics, and programming languages: http://tlca.di.unito.it/opltlca/
Perfect graphs: http://www.aimath.org/WWN/perfectgraph/
Real analysis in computer science: https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf
Fine-grained complexity: http://duch.mimuw.edu.pl/~malcin/opl.pdf
Communication complexity: https://sublinear.info/index.php?title=Workshops:Banff_2017
Erdős problems: http://www.math.ucsd.edu/~erdosproblems/All.html


Sufficient conditions for the regularity of a context-free language It would be nice to collect a list of conditions that imply that a context-free language L
is regular, i.e. conditions of the form:
"if a given CFG/PDA has property P, then its languages is regular"

The property P does not have to characterize
the CFGs generating regular languages. Furthermore, P does not have to be decidable, and P should "somehow depend" on the language being
context-free ("the syntactic monoid of L is finite",
"L is decidable in space o(log log n)" and so on, are not what I am looking for).

Every unary context-free language is regular.
(e.g. a direct consequence of Parikh's theorem)
If every iterative/pumping pair of a context-free language L is
degenerated, then L is regular, i.e. L is regular if, for all words x,u,y,v,z it satisfies:
$$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$This was proved by Ehrenfeucht, Rozenberg, "Strong iterative pairs and the regularity of context-free languages", 1983. See
"Context-free languages" by Berstel and Boasson for an exposition.
If a context-free language is commutative and linear, then it is regular.
(Ehrenfeucht, Haussler, Rozenberg, "On regularity of Context-free Languages",  1983)


Is unbounded quantum fanout operation experimentally feasible? It is known that the "unbounded quantum fanout operation" is very powerful: (See, for example, Hoyer et al. : http://theoryofcomputing.org/articles/v001a005/v001a005.pdf).

In particular, it is known that many operations that cannot be done in constant depth classical circuits can be done in constant depth quantum cicuits that include the quantum fan-out operation.

However, I can't seem to find any discussion as to whether "constant depth" fanout is possible physically.

In classical computation, it seems fairly reasonable to consider "fan-out" to be an operation that does not add to the "depth" of a circuit: such a computational model models the latency of actual physical circuits of reasonable size.

For a fair comparison, unbounded quantum fanout would need to be achievable using some kind of experiment with a latency that scales as a constant with the size of the fanout (if it scales even logarithmically, then that kind of defeats the whole advantage of the quantum fanout operation).

Is there any experimental evidence to suggest whether such constant-latency quantum fanout unitary operations are feasible?

There are two way to see your question :

Is unbounded fanout a reasonable approximation for realistic (quantum) circuits ?
Is there a realistic quantum architecture which is effectively equivalent to the quantum circuit with unbounded fan-out ?

Peter Shor essentially suggested the formulation 1. in his comment above, and I’ll let experimentalists answer this question.

The question 2. seems strange, but I bring it forward because its answer is positive : In a 2009 paper (arXiv:0909.4673, paywalled version), Dan Browne, Elham Kashefi, and Simon Perdrix showed that Measurement Based Quantum Computing (MBQC), is equivalent up to a classical side-processing of logarithmic depth, to the quantum circuit model augmented with unbounded fanout gates.

They basically recall that the unbounded parity gate is a Clifford gate and can be therefore be expressed as a measurement pattern of constant depth (arXiv,paywalled PRA) and show that a fanout gate is nothing else than a parity gate “sandwiched” between two layers of Hadamard gates, and can therefore be simulated in constant depth.

Therefore, your question

  Is there any experimental evidence to suggest whether such constant-latency quantum fanout unitary operations are feasible?

is equivalent to

  Is there any experimental evidence to suggest whether Measurent Based Quantum Computing is feasible?

I personally think the answer to the latter question is “yes”, but the opinions on the feasibility of a given quantum computing architecture tend to be subjective...


Can MONOTONE WSAT be in solved in polynomial time? In the weighted monotone satisfiability problem (MONOTONE WSAT), the input is an n-variable MONOTONE CNF Boolean formula (when there is no a clause with a negated variable) and an integer k, and the problem is to decide whether there exists a satisfying assignment in which at most k of the variables are true. Can MONOTONE WSAT be in solved in polynomial time or is also NP-complete?

This problem is indeed NP-complete.

Actually, the answer for this question is answered in:

https://cs.stackexchange.com/questions/11558/prove-np-completeness-of-deciding-satisfiability-of-monotone-boolean-formula

Therefore, this question is closed and answered...


Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$? If we can prove that  $\mathsf{L}=\mathsf{P}$, does it imply that $\mathsf{NL}=\mathsf{NP}$ ?

I thought it is the case, but I cannot prove it (also for the converse).

No. It is possible that L=P and that P != NP which implies that NL != NP since NL is contained in P.


Logic Programming: Transforming B:-A C:-A to B,C:-A I hope I've come to the right place... it's (probably) a fairly straightforward Logic Programming question.

If I have two clauses of the form:
B:-A C:-A
I can transform these into:
B,C:-A

(Edit: where B,C is a conjunction. I'm doing bottom-up evaluation and it's useful to me to represent multiple clauses with the same body using one clause with a conjunction of the respective heads. This seems trivial, but I'm wondering if there's a name for such a transformation—however, I know that the resulting clause is no longer a Horn clause.)

Does anyone know if this transformation has a name, and if so, can anyone provide a pointer (preferably online) to somewhere that describes it.

Many thanks (from a n00b).

So, this is an instance of the fact that $(A \supset B) \wedge (A \supset C)$ is equivalent to $A \supset (B \wedge C)$. A different type isomorphism, namely that $(B \supset A) \wedge (C \supset A)$ is equivalent to $(B \vee C) \supset A$, looks more like what you wrote down, but that's because in logic programming notation we write B :- A when we mean $A \supset B$. (Note: $\supset$ is "implies," $\wedge$ is "and," and $\vee$ is "or.")

What you're trying to do is related to the binarization transformation, which is discussed in McAllester's "On the complexity analysis of static analyses." There may be a better name for the transformation, but if so, it wasn't known the authors of the paper "A succinct solver for ALFP" (Alternating Least Fixedpoint formulas are a generalization of Horn clauses for bottom-up logic programs such as yours) - in Example 1 on page 4 they discuss a similar transformation and just call it "exploiting the possibility of sharing of pre-conditions."


Minimum path edge-cover or minimum flow with unit capacities and DAGs I have a directed acyclic graph (DAG) such that there can only be at most one edge between any two nodes (ie, only one (i,j) can exist between i and j). I need to find the the smallest set of paths from sources si to sinks ti that cover all the edges (ie, any edge is in at least one path).

The problem should be equivalent to a minimum flow problem, after having introduced a virtual source and a virtual sink and having set l(i,j)=1 for i,j not in {s,t} and l(s,si) = l(ti,t)=0 and c(i,j)=infinite.

There is some literature about that (eg, http://basilo.kaist.ac.kr/mathnet/kms_tex/981523.pdf). However, I'd like to know if there is an algorithm that works better in the specific case. The best I can think of is the blocking flow method (see the paper above), which should be O(|V|*|E|) in my case.

Thanks in advance for any help!

Marco

Eventually, I found an answer myself and I used it to implement this bioinformatics library:

http://bioinformatics.oxfordjournals.org/content/early/2012/05/02/bioinformatics.bts258.abstract

(see the supplementary data for a theoretical analysis on minimum covering path set).


Standard Name for a vertex removal like operation I have an operation that looks a lot like vertex removal, and I'm wondering if there's a standard name for it. Given a graph $G$ we remove a vertex $v$, but instead of removing the edges that were incident on $v$, we "re-route" them by connecting all incoming and outgoing edge pairs. Specifically, if $-$ is normal vertex deletion and we're trying to define $\ominus$, then
$$G \ominus v \equiv G - v + \{ uw | uv \in G \land vw \in G\}.$$
Is there any standard name for this operation?

This operation is called vertex elimination. See for example: "Triangulated Graphs and the Elimination Process", by Rose (1970).
This type of operation is well-studied, among others, in the context of chordal graphs (see Wikipedia entry about perfect elimination orderings). A related problem of finding an optimal ordering for applying this operation is called Minimum Fill-in.


Given a network flow, are there bounds on the change in weight on nodes? Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight around among nodes. This is expressed through a flow $f$ defined on the edges: $f(i,j)$ tells me how much weight I transfer from $i$ to $j$.

The flow cannot create new weight.
The flow must be integer.
$f(i,j)$ is allowed to be larger than $w_i$, but after the entire flow has been applied all the $w_i$ must be non-negative again.

Let $\Delta_i$ be the total change in the weight on node $i$, with the sign convention such that $\Delta_i$ is positive if more tasks leave node $i$ than arrive at $i$. An upper bound on $\Delta_i$ is $w_i$, by virtue of the third condition on the flow. My question now is: Is there also a lower bound?

A naive lower bound for each $\Delta_i$ would be given by the sum of the $\Delta_j$ for all neighbors of $i$, but I wonder if some network- and graph-theory can find better bounds?

If a good lower bound on the $\Delta_i$ is not possible, maybe there is a good \emph{upper} bound on the quantity
$$\sum_{i \in V} \Delta_i^2$$?

I think you're using a confusing sign convention, but I'll stick with it.  It's pretty easy to see that for any connected graph you can have all weight flowing into a single vertex (unless I'm misunderstanding something), so the lower bound you'll get is $$\Delta_i\geq -\sum_{i\in V}w_i.$$

Things won't really be better for bounding the square.  For example, if your graph is a star in which every leaf has $w_i=1$, then $$\sum_{i\in V}\Delta_i^2 = (|V|-1)+(|V|-1)^2.$$

You can't get a neighbourhood restriction, either, because you can take the example of a $k$-ary tree in which every leaf has weight 1 and all the weight goes to the root.

What you can get, however, is the possibly useful bound $$\sum_{i\in V}{|\Delta_i|} \leq 2\sum_{i\in V}w_i.$$

To see this, just note that when charge leaves a vertex you'll count it twice.


Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence I am generally interested in the forcing method used by Baker-Gill-Solovay and Cohen.  I am looking for as many sources as I can get my hands on concerning either the technique itself or its use. Does anyone have suggestions?

For more uses of forcing (via so-called generic oracles) in complexity theory, see The Oracle Builder's Toolkit (freely available from Fortnow's homepage) by Fenner, Fortnow, Kurtz, and Li. They give a general theory of generic oracles, and show its many applications in complexity.

If you're interested in how oracles in complexity are like independence proofs in set theory, you might be interested in the following papers:

Arora, Impagliazzo, Vazirani. Relativizing versus Nonrelativizing Techniques: the Role of Local Checkability.
Impagliazzo, Kabanets, Kolokolova. An Axiomatic Approach to Algebrization. (full version freely available from Kabanets's homepage)

For the uses of forcing in set theory, see the book Set Theory (Set Theory on Amazon) by Jech, especially Parts II and III of the book (not to be confused with "Introduction to Set Theory" by Hrbáček and Jech).


An intuitive/informal proof for LP Duality? What would be a good informal/intuitive proof for 'hitting the point home' about LP duality? How best to show that the minimized objective function is indeed the minimum with an intuitive way of understanding the bound?

The way I was taught Duality only led to one understanding which I am sure is shared by a LOT of people I know: For every corresponding minimization problem there is an equivalent maximization problem that can be derived by inverting the inequality constraints. Period. This  "conclusion" of duality is what seems to stick but not "why is this so" (i.e. how/why is there a bound on the optimal solution).

Is there a way of playing with the inequalities just to 'show' the lower/upper bound on the optimum which could be a motivation for the proof?

I've gone through Chvatal's book as well as a few others but found nothing that could be understood by absolute noobs to LP. The closest that I got was from Vazirani's book on algorithms, where he talks about 'multiplying the inequalities with some magic numbers that show the bound' - I'm not sure how to reproduce the effect for an arbitrary LP.

Per OP's wish, here's the math.SE answer I link to in my comment above.

Maybe it's worthwhile to talk through where the dual comes from on an example problem.  This will take a while, but hopefully the dual won't seem so mysterious when we're done.

Suppose with have a primal problem as follows.

$$
        Primal =\begin{Bmatrix}
        \max \ \ \ \  5x_1 - 6x_2  \\
        \ \ \  s.t. \ \ \ \ 2x_1 -x_2 = 1\\
        \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\
        \ \ \ \ x_1 \geq 0\\
        \end{Bmatrix}
$$

Now, suppose we want to use the primal's constraints as a way to find an upper bound on the optimal value of the primal.  If we multiply the first constraint by $9$, the second constraint by $1$, and add them together, we get $9(2x_1 - x_2) + 1(x_1 +3 x_2)$ for the left-hand side and $9(1) + 1(9)$ for the right-hand side.  Since the first constraint is an equality and the second is an inequality, this implies $$19x_1 - 6x_2 \leq 18.$$
But since $x_1 \geq 0$, it's also true that $5x_1 \leq 19x_1$, and so $$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$$
Therefore, $18$ is an upper-bound on the optimal value of the primal problem.

Surely we can do better than that, though.  Instead of just guessing $9$ and $1$ as the multipliers, let's let them be variables.  Thus we're looking for multipliers $y_1$ and $y_2$ to force $$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$$

Now, in order for this pair of inequalities to hold, what has to be true about $y_1$ and $y_2$?  Let's take the two inequalities one at a time.

The first inequality: $5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

We have to track the coefficients of the $x_1$ and $x_2$ variables separately.  First, we need the total $x_1$ coefficient on the right-hand side to be at least $5$.  Getting exactly $5$ would be great, but since $x_1 \geq 0$, anything larger than $5$ would also satisfy the inequality for $x_1$.  Mathematically speaking, this means that we need $2y_1 + y_2 \geq 5$.

On the other hand, to ensure the inequality for the $x_2$ variable we need the total $x_2$ coefficient on the right-hand side to be exactly $-6$.  Since $x_2$ could be positive, we can't go lower than $-6$, and since $x_2$ could be negative, we can't go higher than $-6$ (as the negative value for $x_2$ would flip the direction of the inequality).  So for the first inequality to work for the $x_2$ variable, we've got to have $-y_1 + 3y_2 = -6$.

The second inequality: $y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

Here we have to track the $y_1$ and $y_2$ variables separately.  The $y_1$ variables come from the first constraint, which is an equality constraint.  It doesn't matter if $y_1$ is positive or negative, the equality constraint still holds.  Thus $y_1$ is unrestricted in sign.  However, the $y_2$ variable comes from the second constraint, which is a less-than-or-equal to constraint.  If we were to multiply the second constraint by a negative number that would flip its direction and change it to a greater-than-or-equal constraint.  To keep with our goal of upper-bounding the primal objective, we can't let that happen.  So the $y_2$ variable can't be negative.  Thus we must have $y_2 \geq 0$.

Finally, we want to make the right-hand side of the second inequality as small as possible, as we want the tightest upper-bound possible on the primal objective.  So we want to minimize $y_1 + 9y_2$.

Putting all of these restrictions on $y_1$ and $y_2$ together we find that the problem of using the primal's constraints to find the best upper-bound on the optimal primal objective entails solving the following linear program:

$$\begin{align*}
\text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\
\text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\
                   -y_1 + 3y_2& = -6\\
                   y_2 & \geq 0.
\end{align*}$$

And that's the dual.

It's probably worth summarizing the implications of this argument for all possible forms of the primal and dual.  The following table is taken from p. 214 of Introduction to Operations Research, 8th edition, by Hillier and Lieberman.  They refer to this as the SOB method, where SOB stands for Sensible, Odd, or Bizarre, depending on how likely one would find that particular constraint or variable restriction in a maximization or minimization problem.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint


Hardness of finding a graph coloring given the optimal number of colors We know that graph coloring is NP-complete even in some special graph classes. On the other hand if someone tells you the exact value of the chromatic number of the input graph, is this problem remains NP-complete. In other words I am wondering if there are any result for the search version of the coloring problem (possibly on different graph classes).

Knowing the exact value of the chromatic number $\chi$ cannot help by more than a factor of $n$.  Since there are only $n$ possible values of $\chi$, you can 'guess' its value, i.e., run processes $P_1,\dots,P_n$, where $P_i$ runs an algorithm assuming $\chi=i$.  This whole scheme can find an optimum colouring in time at most $n$ times the time that it takes $P_\chi$ to find an optimum colouring.

On the other hand, if you're talking about parameterizing the running time by $\chi$, then it's a much more interesting question.  It's in FPT if you parameterize by $n-\chi$ S. Khot and V. Raman, ‘Parameterized Complexity of Finding Subgraphs with
Hereditary properties’.  If you parameterize by $\chi$ I would assume it's W[1]-hard.


EXP-Complete Problems vs Subexponential Algorithms Does the fact that a problem $A$ is EXP-time complete implies that $A$ is
not in $DTIME(2^{o(n)})$?

I'm aware that by the time hierarchy theorem, $EXP=DTIME(2^{n^{O(1)}})$ is not
included in $E=DTIME(2^{O(n)})$. Nevertheless this does not seem to exclude immediately the existence of sub-exponential time algorithms for every EXP-complete problem $A$, since when reducing an instance $x$ of a problem $B\in EXP$ to an instance y of problem $A$, we may have a polynomial blow up in size. In other words, $|y|=|x|^{O(1)}$.

So my question is whether there exists some argument that rules out, unconditionally, the existence of sub-exponential time algorithms for EXP-complete problems.

Due to popular demand, I’m converting my comment to an answer.

A simple padding argument shows that for every constant $\epsilon>0$, there exist EXP-complete problems in $\mathrm{DTIME}(2^{n^\epsilon})$. Indeed, fix an arbitrary EXP-complete problem $L$, and assume that it is computable in time $2^{n^c}$. Let $d>c/\epsilon$, and consider the problem
$$L'=\left\{0^m\#w:w\in L,m\ge|w|^d\right\}.$$
On the one hand, $L$ is polynomial-time${}^\dagger$ reducible to $L'$ via the function $w\mapsto0^{|w|^d}\#w$, thus $L'$ is EXP-hard.

On the other hand, $L'$ is computable in time $2^{n^\epsilon}$: given an input of size $n$, we first check (in polynomial time) that it is of the form $0^m\#w$ for $m\ge n'^d$, where $n'=|w|$. Then we check if $w\in L$, which takes time $2^{n'^c}\le2^{m^{c/d}}\le2^{m^\epsilon}\le2^{n^\epsilon}$.

${}^\dagger$ Actually, the reduction as given is even uniform $\mathrm{AC}^0$, and it can be made DLogTime if we replace $|w|$ with an upper bound that is a power of two.


Lower bounds on counting functions I have a question about counting problems on arbitrary (not necessarily polynomial time) functions.

Let $F_n = \{f : \{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions with $n$ inputs (again, not necessarily polynomial time).

Consider the operator $\#: F_n \to \mathbb{N}$ that maps $f \in F_n$ to $\#f = |\{x \in \{0,1\}^n : f(x) = 0\}|$

Consider a computational model where evaluating $f$ on an input $x$ can be done in time O(1). Clearly, the operator #f can be computed in time $O(2^n)$ by a brute force algorithm that evaluates $f$  on all inputs, and counts which of these inputs are zeros of $f$.

My question is, is there an exponential lower bound on the running time of #f?

Since you are accessing $f$ in a black box manner, you have to query $f(x)$ at all $2^n$ points. Since otherwise, you can design two functions $f_1$ and $f_2$ that are consistent at all query points yet have different number of zeros.


Status of Impagliazzo's Worlds? In 1995, Russell Impagliazzo proposed five complexity worlds:

1- Algorithmica: $P=NP$ with all the amazing consequences.

2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) but are efficiently solvable in the average-case.

3- Pessiland: There exist average-case $NP$-complete problems but one-way functions do not exist. This implies that we can not generate hard instances of $NP$-complete problem with known solution.

4- Minicrypt: One-way functions exist but public-key cryptographic systems are impossible

5- Cryptomania: Public-key cryptographic systems exist and secure communication is possible.

  Which world is favored by the recent advances in computational complexity? What is the best evidence for the choice?

Russell Impagliazzo, A Personal View of Average-Case Complexity
, 1995

Impagliazzo's Five Worlds,
The Computational Complexity
     blog

About a year ago I co organized a workshop on complexity and cryptography: status of Impagliazzo's worlds, and the slides and videos on web site may be of interest.

The short answer is that not much has changed in the sense that most researchers still believe we live in "Cryptomania" and we still have more or less the same evidence for this, and not much progress on collapsing any of the worlds for one another.

Perhaps the most significant piece of new information is Shor's algorithm that shows that at least if you replace P with BQP, the most commonly used public key cryptosystems are insecure. But, because of Lattice based cryptosystems, the default assumption is that we live in cryptomania even in this case, though perhaps the consensus here is a bit weaker than the classical case. Even in the classical case, there seems to be much more evidence for the existence of one-way functions ("Minicrypt") than the existence of public key encryption ("Cryptomania"). Still, given the effort people have spent in trying to break various public key cryptosystem, there's significant evidence for the latter as well.


Rate of convergence for the Perron–Frobenius theorem The Perron–Frobenius Theorem states the following.

Let $A = (a_{ij})$ be an $n \times n$ irreducible, non-negative matrix ($a_{ij} \geq 0, \forall i,j: 1\leq i,j \leq n$). Then the following statements are true.

$A$ has a real eigenvalue $c \geq 0$ such that $c > |c'|$ for all other eigenvalues $c'$.
There is an eigenvector $v$ with non-negative real components corresponding to the largest
eigenvalue $c: Av = cv, v_i \ge 0, 1 \leq i \leq n$, and $v$ is unique up to multiplication by a constant.
If the largest eigenvalue $c$ is equal to $1$, then for any starting vector $x^{\langle 0\rangle} \neq 0$ with non-negative components, the sequence of vectors $A^k x^{\langle 0\rangle}$ converge to a vector in the direction of $v$ as $k \rightarrow \infty$.

But the theorem does not say how fast the sequence of vectors $A^k x^{\langle 0\rangle}$ will converge. Are there any known results on the rate of convergence? What are some good, polynomial-time algorithms to compute this limiting vector?

See the power method for computing eigenvectors:
http://en.wikipedia.org/wiki/Power_iteration

Convergence is exponential (geometric in the ratio of the top two eigenvalues).


Finding a basis for quantum measurement with maximum distinguishability I wish to find a basis state for the quantum measurement of two states which provides the maximum possible distinguishability. In this example let's say we wish to find the best basis ($|\psi\rangle$) to distinguish between $|0\rangle$ and $|+\rangle$.

My approach was to generalize the quantum states as density matrices:

$\rho_+=|+\rangle\langle+|=\frac{1}{\sqrt{2}}\pmatrix{1\cr1}\frac{1}{\sqrt{2}}\pmatrix{1&1}=\frac{1}{2}\pmatrix{1&1\cr1&1}$

$\rho_0=|0\rangle\langle0|=\pmatrix{1\cr0}\pmatrix{1&0}=\pmatrix{1&0\cr0&0}$

$\rho_{\psi}=\frac{1}{2}\left(I+r_x\pmatrix{0&1\cr1&0}+r_y\pmatrix{0&-i\cr{i}&0}+r_z\pmatrix{1&0\cr0&-1}\right)=\frac{1}{2}\pmatrix{1+r_z&r_x-ir_y\cr{r_x+ir_y}&1-r_z}$

$\left|\vec{r}\right|\le1$

My next step was to maximize the difference in quantum fidelity, which I assume is calculated as:

$\Delta Fidelity=p_\psi\left(|+\rangle\right)-p_\psi\left(|0\rangle\right)=|\langle+|\psi\rangle|^2-|\langle0|\psi\rangle|^2=tr\left(\rho_+\rho_\psi\right)-tr\left(\rho_0\rho_\psi\right)$

$\rho_+\rho_\psi=\frac{1}{2}\pmatrix{1&1\cr1&1}\frac{1}{2}\pmatrix{1+r_z&r_x-ir_y\cr{r_x+ir_y}&1-r_z}=\frac{1}{4}\pmatrix{1+r_x+ir_y+r_z&1+r_x-ir_y-r_z\cr1+r_x+ir_y+r_z&1+r_x-ir_y-r_z}$

$tr\left(\rho_+\rho_\psi\right)=\frac{1}{2}\left(1+r_x\right)$

$\rho_0\rho_\psi=\pmatrix{1&0\cr0&0}\frac{1}{2}\pmatrix{1+r_z&r_x-ir_y\cr{r_x+ir_y}&1-r_z}=\frac{1}{2}\pmatrix{1+r_z&r_x-ir_y\cr0&0}$

$tr\left(\rho_0\rho_\psi\right)=\frac{1}{2}\left(1+r_z\right)$

As far as I can tell, the work so far looks right, since a density matrix with $r_x=1$ and $r_x=r_y=0$ is the density matrix of state $|+\rangle$, same for $|0\rangle$. This next part is where I get stuck. I try to find the basis state which maximizes distinguishably by finding the quantum state which results in the largest difference in fidelity:

$\Delta Fidelity=\frac{1}{2}\left(1+r_x\right)-\frac{1}{2}\left(1+r_z\right)=\frac{1}{2}\left(r_x-r_z\right)$

I know the correct answer here is $|\psi\rangle=\frac{|+\rangle+|0\rangle}{2cos\left(\frac{\pi}{8}\right)}$, which is a quantum state where $r_x=\frac{1}{\sqrt{2}}$ and $r_z=\frac{1}{\sqrt{2}}$. This quantum state has a fidelity of 0.854 with $|+\rangle$ and a fidelity of 0.146 with $|0\rangle$. However, I coudld not have gotten to this answer with $\Delta Fidelity=\frac{1}{2}\left(r_x-r_z\right)$, since that equation would have led me to picking $r_x=1$ and $r_z=0$ (which is $|+\rangle$) as a measurement basis.

I'm wondering what it is I missed here?

I figured out what I missed. $\Delta Fidelity=\frac{1}{2}\left(r_x-r_z\right)$ is indeed correct. However, what I missed was the fact that $r_z$ could be less than 0, since the only requirement is that $\left|\vec{r}\right|\le1$. Therefore, to achieve the maximum value of $\Delta Fidelity$, we set $r_x=\frac{1}{\sqrt{2}}$ and $r_z=-\frac{1}{\sqrt{2}}$. This means the actual correct answer is $|\psi\rangle=\frac{|+\rangle+|1\rangle}{2cos\left(\frac{\pi}{8}\right)}$, because a density matrix with $r_z=-1$ and $r_x=r_y=0$ is the density matrix of the $|1\rangle$ state, and the state $|\psi\rangle$ is a midway state between $|+\rangle$ and $|1\rangle$.

Thus, the general approach I took was correct, but I initially failed at performing mathematical optimization in my head.


Is the traditional analysis of Bloom filters wrong? This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was published in 2010, yet I've seen the traditional analysis of Bloom filters continued to be taught in various algorithms and data structures courses.

Is the traditional analysis of Bloom filters indeed incorrect?

Thanks!

The traditional analysis is fine.  The "traditional" analysis is, if it is explained correctly, an approximation;  it's based on calculating the expected number of cells that are 0/1 when you hash the keys into the filter, and then analyzing as though that was the actual number.  The point is that the number of cells that are 0 (or 1) are tightly concentrated around their expectation, so it's a fine approximation.  This was well known, and can be found, I think, even back in my survey article with Andrei Broder.

This paper says that really the performance of a Bloom filter is a random variable (corresponding to the actual fraction of 0/1 entries), and if you want to calculate that performance exactly for some reason, you need to do the combinatorics.  For smaller filters, you'll see an arguably non-trivial difference.

I've talked with the authors of this paper.  Their analysis is all well and good (though I'd argue that it isn't deep or new);  their motivation that the "traditional analysis is wrong" was, I think, exaggerated.


Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata Let $\mathcal A$ be an automaton, then I define the following $\omega$-language accepted by $\mathcal A$:
$$
 L'(\mathcal A) := \{ \eta \in X^{\omega} : v \sqsubset \eta \mbox{ implies } v \in L(\mathcal A) \}
$$
where $v \sqsubset \eta$ means $v$ is a finite prefix of $\eta$ and $L(\mathcal A)$ denotes the finite (regular) language accepted by $\mathcal A$.

For $k > 0$ denote by $PF_k(\eta)$ the set of all $\omega$ words $\xi$ such that the first $k$ letters of $\eta$ and $\xi$ are the same (they share a common prefix of length $k$) and the infixes (or factors) of length $k$ are the same, i.e. if $F_k(\eta)$ denotes the factors of length $k$ then $PF_k(\eta) = \{ \xi : \eta[0...k] = \xi[0...k], F_k(\eta) = F_k(\xi) \}$.

Now I want to show, if $\eta \in L'(\mathcal A)$, then there exists a $k > 0$ such that $PF_k(\eta) \subseteq L'(A)$. First I thought that this does not hold, so that for every $\eta \in L'(A)$ and $k > 0$ you can find some $\xi \notin L'(A)$ such that $\xi \in PF_k(\eta)$, but didn't succeeded in constructing a counter-example, so I guess it holds but I have no idea how to proof it?

The conjecture does not hold:
Let $L$ be the set of prefixes of $(c^*ac^*b)^*$.
Then $L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$.
Take the word $\eta=(c^1ac^1b)(c^2ac^2b)(c^3ac^3b)\dots \in L'$.
For all $k\in\mathbb N$, we can show that $PF_k(\eta)\not\subseteq L'$, as witnessed by $$u_k=(c^1ac^1b)(c^2ac^2b)\dots (c^kac^kb)c^kb c^\omega.$$
Indeed we have $u_k\in PF_k(\eta)$ but $u_k\notin L'$.


List of (unsolved) complexity problems arising from PL What are some major, open computational complexity problems that arise from programming languages, especially program analysis and compilation? I am looking for problems on the lines of "the time complexity of Hindley-Milner type inference" or "the time complexity of 0CFA" (though both are solved problems).

Pippenger's (1) from 1996 shows that (under some assumptions)  strict (CBV) functional programming languages are asympotically slower than imperative languages.  It is open whether Pippenger's result can be generalised to lazy functional languages, as was pointed out in (2).

Pippenger imposes two simplifying assumptions (on-line computation, and a certain atomicity of input). It is open whether
they can be removed.  Pippenger conjectures that it can be done, but warns: "[s]uch a result [...] seems far beyond the reach of currently available methods in computational complexity theory".

See also Campbell's answer in (3), and  Ben-Amram's notes (4).

 1. N. Pippenger, Pure Versus Impure Lisp.

 2. R. Bird, G. Jones, O. De Moor, More haste, less speed: lazy versus
    eager evaluation.

 3. Stack Overflow, Efficiency of purely functional programming.

 4. A. M. Ben-Amram, Notes on Pippenger's Comparison of Pure and Impure LISP.


Is every recursive language recognized by a mortal Turing machine? We say that a Turing Machine $M$ is mortal if $M$ halts for every starting configuration (in particular, the tape content and initial state can be arbitrary). Is every recursive language recognized by a mortal Turing Machine? (i.e. if there is a TM that accepts $L$, there is also mortal TM that accepts $L$)

Here are two results cited in Charles E. Hughes "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators":

Theorem 3: The class of mortal Turing machines is exactly the class of the constant running time Turing machines.

$ConstT = \{ M \mid \exists s $ s.t. for all initial configurations $C$, $M$ halts in no more than $s$ steps $\}$

So I think that we can derive the following: given a mortal Turing machine $M$, let $M', s$ be the corresponding constant time TM and its running time. The language recognized by $M$ over alphabet $\Sigma = \{0,1\}$ is exactly:

$$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$$

So the class of languages recognized by mortal Turing machines is a proper subset of the class of regular languages. For example you can use  $L = \{(0|1)^*1^*\} $ to fool every constant time TM.

Things get interesting when we try to decide if a Turing machine is mortal because we have to face with arbitrary (finite) initial tape and state.

Theorem 4: the set of mortal Turing machines is recursively enumerable.


How hard is deciding the existence of Red-Blue perfect matching? Two-colorable perfect matching problem is to decide whether a graph has coloring with two colors such that each node has exactly one neighbor the same color as itself. The problem was proven to be NP-complete by Schaefer. It remains NP-complete even for planar cubic graphs.

I am interested in a variant where we want to decide whether input graph has coloring with two colors such each node has exactly one neighbor colored differently from itself. I call this Red-Blue perfect matching problem. I don't know whether this is a known problem.

  How hard is deciding the existence of Red-Blue perfect matching?

As Mikhail noted, the problem was called Perfect Matching Cut in literatures. It was proved to be NP-complete in the following paper (see Theorem 1 on page 5), with a reduction from monotone 1-in-3-SAT:

Pinar Heggernes, Jan Arne Telle. Partitioning Graphs Into Generalized Dominating Sets.


About the small set expansion conjecture Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \vert S\vert \}  }$) The ``small-set expansion conjecture" states that it is NP-Hard to determine if this is below $\epsilon$ or above $1-\epsilon$ for $\epsilon = 1/O(log(\frac{1}{\delta} ) )$

For context one notes that $h(G,\delta = \frac{1}{2})$ is the Cheeger constant which is known to be NP-hard to bound. But there does seem to exist values of $\delta$ (which ones?) for which $\phi(G,\delta)$ can be computed in polynomial time?

Towards understanding the small-set expansion conjecture one seems to prove this statement,

If $W$ is the span of the Laplacian eigenvectors of $G$ such that their eigenvalues are less than some $\lambda \in [0,1]$ and if every $w \in W$ satisfies $\mathbb{E}_i[w_i^4 ] \leq C ( E_i [w_i ^2 ]  )^2$ then for every set $S$ such that $\vert S \vert \leq \delta \vert V \vert$ we have $\phi(S) \geq \lambda(1 - \sqrt{C \delta}  )$

[Reference, Lemma 8 here, http://www.boazbarak.org/sos/files/lec2d.pdf ]

My questions are,

How does the above theorem help understand the conjecture stated at the beginning? What is the relationship between the two?
Why should such vectors $w$ exists as demanded in the theorem? What is the intuition behind looking at such $w$?
What is the intuition behind choosing that specific value of $\epsilon$ as in the statement of the conjecture?

I think the following should answer your questions, even though it's not exactly in the same order.

The original formulation of the small set expansion conjecture states that, analogously to the Unique Games Conjecture, for every $\epsilon >0$ there exists $\delta>0$ so that it is NP-hard to determine whether in a graph $G$ it's the "YES" case where there exists a $\delta$-sized set with expansion less than $\epsilon$ or it's the "NO" case where every $\delta$-sized set has expansion at least $1-\epsilon$. The paper of Raghavendra, Steuerer, and Tulsiani https://www.cs.cornell.edu/~dsteurer/papers/ssereductions.pdf showed that this is equivalent to the case where $\epsilon = O(\log (1/\delta))$ and in fact the case where in the NO case, for every $\delta' \geq \delta$, sets of size $\delta'$ have at least the same expansion as they would in the "$\epsilon$-noisy Gaussian graph" (see the paper for the precise statement).  The reason for the relation $\epsilon = O(\log (1/\delta))$ is because this is the relation between those parameters in the Gaussian noise graph. This result of Raghavendra et al can be thought of as the small-set expansion analog for the paper of Khot, Kindler, Mossell and O'Donnell who showed a similar result for unique games, giving a very precise relation between the parameters $1/\delta$ (which in the unique games setting is known as the alphabet size) and $\epsilon$.

The result you mention discussed in my lecture notes is from Section 8 in my paper with Brandao, Harrow, Kelner, Steurer and Zhou ( https://www.cs.cornell.edu/~dsteurer/papers/hypercontract.pdf ). What we show there, roughly speaking, is that a graph is a small set expander if and only if the span of eigenvectors corresponding to low eigenvalues of its Laplacian does not contain an "analytically sparse" vector.

The intuition is the following: consider the following two extremes:

1) A random vector $w$. In this case, the distribution of entries of $w$ is approximately the Gaussian distribution, and so this satisfies that $\mathbb{E}_i w_i^4 = O(\mathbb{E}_i w_i^2)^2$.

2) A vector $w$ that is the characteristic vector of a set of measure $\delta$ (i.e. it has $1$ in the coordinates belonging to the set, and $0$ in the others). In this case, $\mathbb{E}_i w_i^4 = \delta \gg \delta^2 = (\mathbb{E}_i w_i^2)^2$.

Now, roughly speaking, the subspace $W$ corresponding to eigenvalues smaller than $\epsilon$ of the Laplacian corresponds to set which have expansion at most $\epsilon$ in the graph. So, if there exists a $\delta$-sized set with such expansion then there would be a vector $w$ (namely the projection of the characteristic vector of this set to $W$) with $\mathbb{E}_i w_i^4 \gg (\mathbb{E}_i w_i^2)^2$. The other direction (which is more challenging to prove but turns out to be true) is that if there is a vector $w$ with this property then we can also find a set with $o(1)$ measure with not too good expansion.


List of NP-hard problems, where there is active research in practical heuristics I am looking for list of NP-hard optimization problems, where there is active research in practical heuristic for solving them and there are common benchmarks, which people try to beat.

Examples include:
Phylogenetic tree reconstruction (heuristic for example here)
Travelling salesman (not so active, but LKH is quite well known)

More specifically, I am looking for areas of research, where people really care about resulting cost (like TSP or phylogeny mentioned above).
E.g. finding decision tree is not a thing I am looking for, since very few people care about resulting tree height.

MaxSAT - people actually care about this because SAT solvers are so well-developed that often the best route for your favorite NP optimization problem in practice is to reduce it to MaxSAT and then apply one of the well-known solvers. Check out the SAT competition for benchmarks etc.

Clique-finders get used in computational biology and combinatorics, and the heuristic algorithms are shockingly good, as I recall.

Vast portions of Operations Research is devoted to algorithms, including heuristic ones, for solving cases of integer or mixed-integer linear programming.


Extensional characterization of non-deterministic finite state transductions I recently became aware of the rather appealing characterization of deterministic word-to-word transductions as word functions with bounded variation (see e.g. [1]). This coincides with the set of functions that can be realized by subsequential transducers, which are deterministic finite state transducers with an output function defined on accepting states.

Not every function defined by a non-deterministic FST is subsequential, that is, even if the FST is single-valued, it might not be determinizable. I wondered if there are any extensional characterizations of the set of functions definable by (single-valued) FSTs?

Thanks!

[1] Bruyère, Véronique and Reutenauer, Christophe.  A proof of choffrut's theorem on subsequential functions. Theoretical Computer Science, 1999.

The best reference is probably the book Rational transductions and context-free languages by J. Berstel.

First recall that a function $f$ from $A^*$ to $B^*$ is realized by a transducer (= non-deterministic FST) if and only if it is rational, that is, if the set $\{(u, f(u)) \mid u \in A^* \}$ is a rational subset of $A^* \times B^*$.

You can find several other relevant characterizations of rational functions in Chapter 4 of Berstel's book.

(Eilenberg 1974. See Prop. 4.1 and Corollary 4.3) A function from $A^*$ to $B^*$ is rational if and only if it can be realized by a normalized unambiguous transducer.
(Schützenberger 1976. See theorem 4.5) A function is rational if and only if it admits a semimonomial representation.
(Elgot and Mezei 1965. See Theorem 5.2) A function is rational if and only if it is the composition of a left sequential transduction by a right sequential transducer.

See also A. Arnold and M. Latteux, A new proof of two theorems about rational transductions, Theoret. Comput. Sci. 2 (1979), 261–263.


Hardness of approximating fractional chromatic number on bounded degree graphs Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?

Yes.

If I understood correctly, the proof of Theorem 1.6 in Khot (2001) establishes that it is NP-hard to distinguish between the following two cases, even if we focus on bounded-degree graphs of sufficiently high degree:

There is a $k$-colouring.
The ratio of the number of vertices to the maximum size of an independent set is at least $k^{\log(k)/25}$.

From the perspective of fractional chromatic number these two cases are:

The fractional chromatic number is at most $k$.
The fractional chromatic number is at least $k^{\log(k)/25}$.

Now we must remember that we need sufficiently high degrees (as a function of $k$). But as far as I can see, the proof has, e.g., the following convenient corollary that might already be sufficient for your purposes:

Given any constant $\alpha$, there are constants $\Delta$ and $c$ such that the following problem in NP-hard: given a graph $G$ of maximum degree $\Delta$, decide whether the fractional chromatic number of $G$ is at most $c$ or at least $\alpha c$.

An of course this already implies that there is no PTAS, unless P = NP.


Self-organizing Sequential Search Heuristics I've read the paper by Jon L. Bentley "Amortized analyses of self-organizing sequential search heuristics". It deals with different schemes for improving linear search. (such as after every access to an element move it to front or transpose neighboring elements) And at the end of the paper was a section for those who are interested in practical applications of this techniques.

It says that such techniques has practical applications if you want to do a linear search quicker (obviously, it's true).
But can you give some example of such problem?
If we need to make fast searching , insertion and deletion why don't you use HashTable? I thought the only reason why we use Linked List is that it preserves order and its very easy to implement. Am I right?
But with such heuristics we don't preserve order. But it's still easy to implement...

So for what purposes do we use such heuristics that don't preserves order for list?
Thank you very much!

The self-adjusting linked lists described by Bentley have practical applications in data compression.  For example, bzip2 uses move-to-front encoding (among many other tricks).  See also this paper by Bentley et al.


Place n points in a box as far away from each other as possible Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized.

In other words, I'm looking to put points down in a box as far away from each other as possible.

This seems to be equivalent to packing disks of max radius -- a very well studied problem, at least if your box is a square, see, e.g.,Circle packing in a square. For heuristics see, e.g., http://www.pack-any-shape.com/


Algorithm for K-best NON perfect bipartite matchings I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf

It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best.
However, it only looks at perfect matchings. I'm am especially interested in bipartite matchings.

In particular, for the bipartite graphs, the Theorem 1 p. 161 uses the fact that the matchings are considered perfect.

How can I solve the k-best assignment problem for general bipartite graphs?

After some thinking, I found an answer. If one has a better one I'll accept it.

From a cost matrix of shape $n\times m$ with $n<m$, it is easy to add nodes that will not change anything by giving all their incident edges the same weight $w$, that is adding $(m-n)*m$ edges.


What category are Tagless Final Algebras final In? The Haskell and Scala community have been very enamored recently with what they call tagless final 'pattern' of programming. These are referenced as dual to initial free algebras, so I was wondering what Tagless Final was final of. On ncatlab one only finds talk of final coalgebras, not final algebras.

A few references:

The influential Haskell Typed Tagless Final Interpreters lecture notes
A translation of that article for Scala (Dotty) Revisiting Tagless Final Interpreters
A blog post From Object Algebras to Finally Tagless Interpreters makes the case that Object algebras are equivalent to Tagless Final.
It cites the paper Extensibility for the Masses, practical extensibility with Object Algebras.

The example used by these are clearly Algebras, which in category theory are expressed with endofunctors F as maps of the form F(X) -> X. Coalgebras are dual maps X -> F(X), and represent processes.

The follow up question is more about use of final tagless in programming circles which seems to be more related to final coalgebras.
See the question on stackoverflow here.

Final Algebra semantics was introduced by Mitch Wand in his paper "Final Algebra Semantics and Data Type Extensions", see this freely available tech report: https://www.cs.indiana.edu/ftp/techreports/TR65.pdf .

It does not mean final coalgebra semantics, which is a very different idea. The wrinkle is that the algebra is not final in the same category that the initial algebra is initial, because then the final algebra would just be given by the unit type/terminal object as carrier. Instead, Wand defines a category of adequate extensions of an algebra, which basically say you want the algebras in question to not equate basic values. An example of this is that the signature may contain numbers and you only want to consider algebras where the interpretations of distinct integers are unequal. This rules out the trivial terminal object as carrier because it would equate all numbers. I wrote a blog post about this a while ago in an attempt to understand the same question: http://prl.ccs.neu.edu/blog/2017/09/27/final-algebra-semantics-is-observational-equivalence/ .


Computational complexity in quantitative finance Predicting the stock market is hard! Can TCS make this sentiment more formal?

Recently I have started thinking a little bit about finance, and was wondering how knowledge of TCS could help. Hedge funds and investment firms seems to use algorithmic trading, machine learning, and AI all the time, but TCS results seem to be few. In particular, I only know two papers:

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge, Computational Complexity and Information Asymmetry in Financial Products, 2009.

Philip Z. Maymin, Markets are efficient if and only if P = NP, 2011.

The first paper shows that derivatives can amplify the cost of informational asymmetry (instead of the desired goal of reducing it) for computationally-bounded agents. The second paper challenges the popular belief of efficient markets by showing that market efficiency can be used to solve NP-hard problems.
Are there any books/surveys or seminal papers on related ideas? Especially things related to the difficulty of predicting or approximating markets or trading optimally (or close to optimally) in such markets?
A slightly more meta question: why does there seem to be an abscence of papers on this? Is there no interest, or is that all the interested parties become quants that are hiden behind no-publication agreements?
Related question
Algorithmic lens in the social sciences
What is the Complexity Classification of Portfolio Theory in Financial Economics?

The question you begin with relates to predicting the stock market, but you seem to have broader concerns.  I'll attempt to tackle your meta-question; apologies in advance for my sweeping generalizations.

As far as I can tell, academic computer science is far removed from the actual concerns of hedge funds and people who try to model and predict markets.

The current focus areas in algorithmic game theory are not obviously relevant to finance practitioners.  In particular, worst case results are not seen as useful at all, and average case analysis based on artificial distributions seems largely irrelevant also.  Yet the only way to obtain information about real distributions seems to be to actually engage in the market, updating one's information using a variety of learning techniques.  This creates messy models that change dynamically and are not amenable to most types of analysis.

As an example, there has been a focus in finance on understanding the microstructure of trades.  Market microstructure is an emergent property of the specific low-level market mechanisms that are in place, such as how frequently pending trades are matched, what information traders believe exists in the order book, techniques used to obfuscate that information, the roll-back mechanisms in place, contractual arrangements relating to settling trades, network latency in receiving updates about the current state of the order book, and many other factors.  Market microstructure is a highly reflexive system, so the clean models typical of TCS seem beyond reach.

The market design community is trying to tackle questions like this (for instance see Huang and Stoll and the recent Kirilenko et al. paper on the flash crash), but they do not seem to have much interaction with TCS.

Finance has become increasingly complex as IT has pervaded markets.  This means that most markets now consist of multiple interlocking systems which it may not be possible to meaningfully model separately.  In addition, as markets move closer to continuous trading, I am not sure the TCS lens of computation is currently all that useful in finance; control theory, graphical models, fluid dynamics, and many other areas of applied mathematics seem more directly useful.

TCS methods could well be useful, but one needs to expend effort to understand what happens in finance, to find a place to apply the lever, and to acquire an appropriate mathematical toolkit.  Personally I would like to see more work along the lines of Arora/Barak/Brunnermeier/Ge, which engage with deep questions.  For instance, does adding more degrees of freedom to financial systems lead to good outcomes for the users of these systems?  Or does adding complexity mainly serve to help intermediaries set up asymmetric zero-sum games against the users?  There is probably a neat complexity-based argument waiting to be discovered...

So in a nutshell: you haven't seen much TCS/finance research because it is hard to apply TCS to finance.


Original Hoare Logic termination paper I'm looking for the original paper where Hoare (or someone else I suppose) discusses termination (Total Correctness). Or any other early work on termination for "vanilla" Hoare logic (I suppose by that I mean a HL for a C-like toy language).

I've had a look at Axiomatic basis for Computer Programs (PDF) (which seems to be essentially Hoare logic of the partial correctness flavour) and
A note on the for rule, which mentions proof of a while rule, but can't seem to find the missing link; a paper on termination/the while rule/Total correctness.

You probably want

Manna, Pnueli, Axiomatic Approach to Total Correctness of Programs, 1973