What are some example problems for integer programming that are *not binary* I'm interested in NP-hard problems that have a "nice" integer-programming formulation (quadratic or linear, with quadratic or linear constraints) that is not binary.

Of course it is always possible to replace integer-valued variables with a set of binary variables, but that's okay; I'm still interested in optimization problems whose "natural" formulation would be as an integer problem with more-than-binary integers.

Classical examples that come up when searching for integer programming are Set Cover and Max Cut, but those have a very straight-forward binary formulation... any pointers?

EDIT: Let me clarify natural through an example. Let's say we have some integer optimization problem where variables $x_i$ refer to how many units of product $i$ a factory should produce. This would be naturally formulated with integers other than 0 and 1. On the other hand, a knapsack combinatorial optimization problem would have an integer formulation where $x_i = 0, 1$ indicating whether or not item $i$ is chosen.

EDIT:
In the integer programming literature, binary does not refer to the overall representation of integers. It refers to the additional constraint that all variables be either 0 or 1, instead of arbitrary integers.

Here are a few examples:

(Most Common) Cutting Stock Problem - determine patterns for which to cut boards in order to meet demand.
(Kinda same problem) - Knapsack with general integer variables - used for column generation in the cutting stock problem
Problems with modular constraints:  $x \equiv 3 \pmod 5$ can be written as $x + 5y = 3$, $y \in \mathbb{Z}$.  Most commonly seen in cyclic train schedules - https://www.sciencedirect.com/science/article/abs/pii/S0360835213001782
Generalized Vehicle Routing Problems - http://orel.uca.es/pdfs/ORP3_3_ClaudiaBode.pdf
B-matchings - https://arxiv.org/pdf/math/0607088.pdf
Bin Packing with a constant number of item types (theoretical application) https://arxiv.org/abs/1307.5108
Lattice point counting in polyhedra - https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf
Lattice vector problems - Closest Vector Problem (CVP) and Shortest Vector Problem (SVP) are technically unconstrained convex quadratic (general) integer programming problems. These are important problems in computer science. https://en.wikipedia.org/wiki/Lattice_problem
This also goes under the name of "integer least squares regression" since it is also just solving a quadratic regression problem with an integer constraint
https://stanford.edu/~boyd/papers/pdf/int_quad_cuts.pdf
"The integer least squares problem captures the essence of the phase ambiguity estimation problem arising in the global positioning systems (GPS) [HB98]."

I would, however, like to figure out upper bounds for integer variables used in practice.  Something still on my mind.  For instance, can we assume that all integer variable used in practice are upper bounded by 1000? 10,000?  How can we use this information?  It is true that often it can be advantageous when solving to convert integer variables into binary variables, but this is not always the case.


Strongly normalizing type theory beyond induction-recursion Are there known type theories in the literature, which have strong normalization proofs and their proof-theoretical strength goes beyond strength of type theories with induction-recursion?

Yes. System F is probably the simplest example. As far as I know, you can’t prove normalisation for it in a dependent type theory with induction-recursion — you need at least impredicative prop to do so.


Some good reading on polygon algorithms What are some good resources (books, articles, sites) about polygon intersection and union algorithms?

I found this book to cover the topics well

Computational Geometry in C
by Joseph O'Rourke


Finding common label sequences in a directed acyclic graph I have a directed acyclic graph with ~250k nodes, each node has one of about 100 symbols as label. Letting a word be the sequence of n symbols that corresponds to a path containing n nodes in the graph, how can I find the most common words? What known algorithms should I study?

An interesting extension is to let edges also have one of about 100 symbols (the set of edge symbols does not intersect the set of node symbols) as label, redefining a word to be the sequence of length n+(n-1) symbols that corresponds to a path containing n nodes and n-1 edges.

Reading tips and wikipedia links are appreciated as well as more elaborate answers.

Can't you just use the graph to build a trie, and then have the counts of all words.  (You would have to augment the trie slightly.)  It's a simple step from there to sort the words by number of occurrences, although the most common word will trivially be the single label that appears the most in your DAG.  (It gets more interesting if you look at most common words of a given length...)


Embedding a graph as a collection of interior-disjoint tetrahedra Define a mesh in 3D as a connected collection of tetrahedra with disjoint interiors (so tetrahedra share only k-faces, $k \le 2$). Given an arbitrary graph, is there an efficient procedure to test if it can be embedded as a mesh ?

Here, an embedding is a mapping of vertices of the graph to points in $R^3$ and edges to straight lines such that edges only intersect at vertices, and faces only intersect at edges, and no two faces intersect in their interior.

In Hardness of embedding simplicial complexes in $\mathbb{R}^d$ it is stated that $\mbox{EMBED}_{3\rightarrow3}$ is at least as hard as recognizing a 3-sphere, which is known to be in NP, but not known to be in P. They continue to say that for all we know, the problem may be undecidable.

EDIT: Update. Actually, my answer applies to PL embeddings. For linear embeddings the problem is known to be in PSPACE. I don't know if anything else is known.


Bounds on the size of the smallest NFA for L_k-distinct Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal:

$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$$

This language is finite and therefore regular.  Specifically, if $\left|\Sigma\right|=n$, then $\left|L_{k-distinct}\right| = \binom{n}{k} k!$.

What is the smallest non-deterministic finite automaton that accepts this language?

I currently have the following loose upper and lower bounds:

The smallest NFA I can construct has $4^{k(1+o(1))}\cdot polylog(n)$ states.
The following lemma implies a lower bound of $2^k$ states:

  Let $L ⊆ Σ^*$ be a regular language.  Suppose there are $n$ pairs $P = \{ (x_i, w_i) \mid 1 ≤ i ≤ n \}$ such that $x_i\cdot w_j \in L$ if and only if $i=j$.  Then any NFA accepting L has at least n states.

Another (trivial) lower bound is $log$$n\choose k$, which is the log of the size of the smallest DFA for the language.

I am also interested in NFAs that accept only a fixed fraction ($0<\epsilon<1$) of $L_{k-distinct}$, if the size of the automaton is smaller than $\epsilon\cdot 4^{k(1+o(1))}\cdot polylog (n)$.

Edit: I've just started a bounty that had a mistake in the text.

I meant we may assume $k=polylog(n)$ while I wrote $k=O(log(n))$.

Edit2:

The bounty is going to end soon, so if anyone is interested in what is perhaps an easier way to earn it, consider the following language:

$L_{(r,k)-distinct} :=\{w : w$ contains $k$ distinct symbols and no symbol appear more than $r$ times$\}$.

(i.e. $L_{(1,k)-distinct} = L_{k-distinct}$).

A similar construction as the one in the comments gives $O(e^k\cdot 2^{k\cdot log(1+r)}\cdot poly(n))$ sized automaton for $L_{(r,k)-distinct}$.

Can this be improved? What's the best lower bound we can show for this language?

This is not an answer but a method which I believe would leave to an improved lower bound. Let us cut the problem after $a$ letters are read. Denote the family of $a$ element sets of $[n]$ by $\mathcal A$ and the family of $b=k-a$ element sets of $[n]$ by $\mathcal B$. Denote the states that can be reach after reading the elements of $A$ (in any order) by $S_A$ and the states from which an accepting state can be reached after reading the elements of $B$ (in any order) by $T_B$. We need that $S_A\cap T_B\ne \emptyset$ if and only if $A\cap B=\emptyset$. This already gives a lower bound for the required number of states and I think it could give something non-trivial.

This problem essentially asks for a lower bound on the number of the vertices of a hypergraph whose line graph is (partially) known. Similar problems were studied e.g., by Bollobas and there are several known proof methods that can be useful.

Update 2014.03.24: In fact if the above hypergraph can be realized on $s$ vertices, then we also get a non-deterministic communication complexity protocol of length $\log s$ for set disjointness with inputs sets of size $a$ and $b$ (in fact the two problems are equivalent). The bottleneck is of course when $a=b=k/2$, for this I could only find the following in Eyal and Noam's book: $N^1(DISJ_a)\le \log \big(2^k \log_e {n\choose a}\big)$ proved by the standard probabilistic argument. Unfortunately I could not (yet) find good enough lower bounds on this problem but assuming the above is sharp, it would give a lower bound $\Omega(2^k\log n)$ unifying the two lower bounds you have mentioned.


largest language class for which inclusion is decidable am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable.

am also interested in the same question for what were once called "GSMs", generalized sequential machines, or maybe more modernly, FSM "transducers", where if $f(x)$ is the transducer, $C \subset f(C)$, $C$ in the class.

(of course, the problem is also equivalent to determining whether the intersection of a complement is empty.)

[simply asking for the "largest known" language is a literature related question. however some kind of proof that there exists a "largest class" I believe is an open question. although, there might be a straightfwd argument of nonexistence via diagonalization...?]

unfortunately wikipedia does not have some of this basic info for major language classes. wonder if there is any table, paper, or reference esp online.

there is a nice table of decidability & undecidability of basic language questions in [1] but its quite dated at this point.

[1] Hopcroft/Ullman, Intro to Automata Theory, Languages & Computation, 1979

Converted from comment: language inclusion is decidable for very simple deterministic pushdown automata ("On the Inclusion Problem for Very Simple Deterministic Pushdown Automata (1999)" by E. Makinen, 1999)
and a restricted version of timed finite state machine ("On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap" by J. Ouaknine and J. Worrell, 2004).


Subgraph of G whose maximum degree and minimum degree are of the same order Consider a graph $G$ with max degree $\Delta_G$, min degree $\delta_G$ and average degree $d_G$.

Is it possible to obtain a subgraph of $G$, say $G'$, such that  $\Delta_{G'} = c_1d_{G}$, $\delta_{G'} = c_2d_{G}$ , where $c_1,c_2$ are constants

EDIT 1: Also the size of the resultant subgraph $G'$ must be constant times the size of original graph $G$.

My attempt :

Let $X$ be the random variable which denotes the degree of any randomly chosen vertex. Therefore, $d_G = E[X]$. Using markovs's inequality, we have

$$P(X > 3E[X]) < \frac{1}{3} $$
 and
$$P(X < \frac{E[X]}{3}) = P(\frac{1}{X} > \frac{3}{E[X]}) < \frac{E[\frac{1}{X}]*E[X]}{3} < \frac{1}{3}$$

Using union bound, we have

$$P(\frac{E[X]}{3} < X < 3E[X]) > 1/3$$.

Using the above equation, we can show that there exist $|V|/3$ vertices in $G$ whose degree is between $d_G/3$ and $3d_G$.

Does the graph obtained by the above $|V|/3$ vertices solve the problem? If not, can we modify the technique to obtain a solution?

Thanks in advance!

If you want to find an induced subgraph of "sufficient size" i.e not of constant size, then this is not possible. Consider the star $K_{1, n}$, which has average degree $2-1/n$.  Take any subset of the vertices.

if the subset contains the central node, then the max degree equals the size of the subset. If this subset is more than a constant size, then it violates your condition.
if the subset does not contain the central node then the max degree is zero, which again violates your condition.


Clique-width expressions with logarithmic depth When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree decomposition where the tree is binary and its height is $O(\log n)$. This can be achieved while keeping the width of the decomposition at most $3w$. (See e.g. "Parallel algorithms with optimal speedup for bounded treewidth", by Bodlaender and Hagerup). So, logarithmic depth is a property of a tree decomposition which we can get almost for free.

My question is if there exists a similar result for clique-width, or perhaps a counter-example. In other words, given a clique-width expression for $G$ using $k$ labels, does there always exist a clique-width expression of height $O(\log n)$ for $G$, that uses at most $f(k)$ labels? Here, the height is defined naturally as the height of the parse tree of the clique-width expression.

If a statement similar to the above is not known, is there an example of an $n$-vertex graph $G$ with small clique-width $k$, such that the only way to construct $G$ with $f(k)$ labels is to use an expression with large depth?

After a while I found an answer in the literature, so I'm posting it here in case it is useful to someone else.

It is in fact possible to re-balance clique-width expressions so that they have logarithmic depth. The result is given in the paper "Graph operations characterizing rank-width and balanced graph expressions" by Courcelle and Kanté, WG '08. I quote Theorem 4.4 from the paper:

"Every graph of clique-width or NLC-width $k$ is the value of a 3-balanced
clique-width expression of clique-width or NLC-width at most $k \times 2^{k+1}$"

The catch here is that the number of labels blows up exponentially in the balancing. It seems that for clique-width no better result is currently known. The same paper gives a similar result with only a constant blow-up for rankwidth, but this doesn't help, since the difference between clique-width and rankwidth can be exponential in the worst case.


Verified type checkers Most of the work on programming language metatheory mechanization focus on the declarative properties of the languages (e.g., type soundness), but fail to address the algorithmic side, i.e. the type checking (or reconstruction) algorithm.

As far as I know, the only works that verified the algorithmic properties of type systems are the early papers on the mechanization of Algorithm W (Naraschewski & Nipkow 1999, Urban & Nipkow 2009), and Jacques Garrigue's certified type checker for a representative subset of OCaml (2014).

Are there any other work on formally verifying the completeness, soundness & other algorithmic properties (e.g., decidability) of type checking (or type inference) algorithms?

Here are some results of a simple Google search:

Certification of a Type Inference Tool for ML: Damas–Milner within Coq by Catherine Dubois and Valérie Ménissier-Morain
Formalization of a Polymorphic Subtyping Algorithm by Jinxu Zhao, Bruno C. d. S. Oliveira, and Tom Schrijvers
type-inference formalization in Coq, based on A Rewriting Semantics for Type Inference


Is it possible to prove that a game(ex. chess or othello...) will eventually halt at some point. Is it possible to prove that a game(ex. chess or othello...) is solvable and will eventually halt at some point. I wonder as the halting problem is undecidable, will it be possible to prove that a particular game will end after a finite number of moves

You can make games that will halt and those that won't.  Othello will always halt because it cannot continue for more than 60 moves based on the rules.  Chess ends only because there are rules to prevent infinite-move games (repetition rule, 50-move rule, etc).  You can certainly construct games that never end... a silly example is "whoever names the highest integer wins".

Then there are games that lead to a paradox when you try and ask if they will end or not.  A famous example is the game called CHOICE.  The first move of CHOICE is to choose a game that does eventually end.  The 2nd move of CHOICE is to play the first move of the chosen game, etc.

Now we ask, "does CHOICE end or not?"  If you say it does, then the first move of CHOICE could be to choose CHOICE, and continuing this way leads to a never-ending game.  So suppose we say CHOICE does not end, thereby disqualifying it as a possibility for the first move.  Then clearly it DOES end.


Solving Superstring Exactly What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?

UPD:
$O^*(\cdot)$ suppresses polynomial factors.

The shortest superstring problem is a problem whose answer is the shortest string which contains each string from a given set of strings.
The question is about optimization extension of a famous NP-hard problem Shortest Superstring(Garey and Johnson, p.228).

I've studied the problem and I found some results.
Shortest Common Superstring (SCS) can be solved in time $2^n$ with only polynomial space(Kohn, Gottlieb, Kohn; Karp; Bax, Franklin).

The best known approximation is $2\frac{11}{30}$ (Paluch).

The best known approximation of compression is $3\over4$ (Paluch).

If SCS can be approximated by a factor $\alpha$ over the binary alphabet, then it can be approximated by a factor $\alpha$ over any alphabet (Vassilevska-Williams).

SCS cannot be approximated with a ratio better than $1.0029$ unless P=NP (Karpinski, Schmied).

Maximal Compression cannot be approximated with a ratio better than $1.0048$ unless P=NP (Karpinski, Schmied).

I would be grateful for any additions and suggestions.


Are bins with more black than white balls negatively 1-correlated? Suppose we throw $m_b$ black balls and $m_w$ white balls independently and
uniformly at random in $n$ bins.
Let
$\left\{ B_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$,
$\left\{ W_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$
be the number of black and white balls that end up in bin $i$, respectively.

Let
$\left\{ M_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$
be the binary random variables such that
$$
    \Pr(M_{i} = 1 \,|\, B_i>W_i ) = 1,\\
    \Pr(M_{i} = 1 \,|\, B_i=W_i ) = 1/2,\\
    \Pr(M_{i} = 1 \,|\, B_i<W_i ) = 0.
$$
In other words, $M_{i}$ indicates whether bin $i$ contains more
black balls than white balls (breaking ties u.a.r.).

In
Randomized Distributed Edge Coloring via an Extension of the
Chernoff--Hoeffding Bounds by
Alessandro Panconesi and Aravind Srinivasan, it is shown that the
Chernoff bound holds for dependent binary random variables such that
for each $I \subseteq \left\{ 1, \cdots, n \right\}$
$$
    \Pr \left( \bigwedge_{i \in I} X_{i} = 1 \right)
    \leq \prod_{i \in I} \Pr \left( X_{i} = 1 \right)
$$
They call the latter property negative 1-correlation.

My question is: are the r.v. $M_{i}$ negatively one correlated?

This is very intuitive, but I couldn't figure out any proof. All my attempts end up dealing with the explicit joint probability distribution of the $B_i$ and $W_i$, at which point I'm stuck...

A good reference is Concentration of Measure for the Analysis of Randomized Algorithms, by Dubhashi and Panconesi.  This is not a standalone proof but shows how you could use the results therein to prove your desired inequality.

We say a set of random variables $X_i, i \in [n]$ are negatively associated if for all disjoint subsets $I,J \subset [n]$, and all nondecreasing functions $f$ and $g$,
$$
\mathbb{E}[f(X_i, i \in I)g(X_j, j \in J)] \leq \mathbb{E}[f(X_i, i \in I)]\mathbb{E}[g(X_j, j \in J)].
$$

By the proof of proposition 3.1 of D&P, the variables $\{B_1, \dots, B_n\}$ and $\{W_1, \dots, W_n\}$ are negatively associated.  By the disjoint monotone aggregation property of negatively associated variables, (p.35 of D&P), $-W_1, \dots, -W_n$ are also negatively associated, and the random variables $B_i-W_j$, over all choices of $i,j$ are as well.  In particular, the set of variables $B_i - W_i$, for any subset $I \subset [n]$ are negatively associated.

Then, per exercise 3.1, or just by applying the above inequality recursively with $f=g=1$,
$$
\mathbb{E}[ \prod_{i \in I}M_i ] \leq \prod_{i\in I}\mathbb{E}[ M_i],
$$
from which your inequality follows.


Unary languages in $AC^0$? Barrington, Immerman, and Straubing state

  circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in $\text{AC}^0$)

I'd appreciate clarification of this statement; it seems to imply that $\text{AC}^0$ contains even undecidable languages.

Could someone please point out my error, or explain what the authors might mean?

Barrington, D.A.M., Immerman, N., and Straubing, H., On Uniformity within $NC^1$, JCSS 41 274–306, 1990.  doi: 10.1016/0022-0000(90)90022-D

Note the beginning of the sentence you quoted.  It says

  In their non-uniform versions these circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in AC0).

The nonuniform version of AC0 is defined as the class of problems which are decided by a (not necessarily uniform) family of boolean circuits of polynomial size and constant depth with unbounded fan-in.  Since there is no uniformity condition, you can use completely different circuits for different lengths, implying that you can decide any unary languages (including undecidable ones).  This is the motivation of the uniformity condition.  For detail, see Proposition 11.2 of Computational Complexity by Papadimitriou.


Space efficient "industrial" unbalanced expanders I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-expander if for any $S \subset A$ of size at most $k$, the number of distinct neighbors of $S$ in $B$ is at least $(1-\epsilon)d|S|$. It is known that the probabilistic method yields such a graph with $d=O(\log (n/k)/\epsilon)$ and $m=O(k \log(n/k)/\epsilon^2)$. However, one needs $O(n d)$ space to store such a graph. Also one also needs to access this storage when doing anything with the graph, which can cost as well. Ideally, one would like an explicit construction. However, as far as I know, known constructions achieve parameters that are still somewhat far from the above (at least provably so).

My question: are there any other constructions, possibly non-explicit, which achieve bounds "closer" to the ones above, yet use "significantly less" than $O(nd)$ space ?

I am looking for answers in any of these three categories: (a) theorems (b) conjectures (c) observations and "war-stories" such as "we did this and it kind of seemed to work (sort of)". I.e., "industrial" expanders are OK. I prefer (a) over (b) and (b) over (c), but beggars cannot be choosers :)

Here is an example of a construction of type (c). Take $d$ random linear hash functions $h_i: [n] \to [m]$ (mod $m$), and connect each vertex $i$ to $h_1(i) \ldots h_d(i)$. Me and my student did some experiments on it, and it seemed to work "fine". Are there any theorems or conjectures about this or related constructions ?

Thanks!

Eickmeyer and Grohe (2010) prove that your candidate construction can be made explicit: take $d$ somewhat linearly independent linear hash functions $h_1,\dots,h_d$ and connect left vertices $v$ with right vertices $h_1(v),\dots,h_d(v)$. Eickmeyer and Grohe show that this construction gives $(k,\epsilon)$-expanders with left degree $d=k(t-1)/(2\epsilon)$, whenever $t$ is an integer, the left vertex set has size $n=q^t$, the right vertex set has size $m=dq$, and $q>d$ is a prime power. The hash functions $h_1,\dots,h_d$ are chosen in such a way that any $t$ of them are linearly independent.


Communication complexity problems with linear distance Are there any known (non-trivial) randomized communication complexity lower bounds for natural gap problems in which the 1-inputs are linearly far from the 0-inputs? That is, partial functions $f:\{0,1\}^{2n} \to \{0,1,*\}$ such that the Hamming distance between every $(x,y) \in f^{-1}(1)$ and $(x',y') \in f^{-1}(0)$ is linear -- and that $f$ requires randomized protocols to communicate (say) $\Omega(\sqrt{n})$ bits?

(For instance, the Gap-Hamming-Distance problem has $2\sqrt{n}$ distance, whereas I'm looking for $\Omega(n)$ distance; where $GHD(x,y) = 1$ if $HD(x,y) \ge n/2 + \sqrt{n}$ and $GHD(x,y) = 1$ if $HD(x,y) \le n/2 - \sqrt{n}$.)

Edit: As pointed out by Igor, any communication complexity predicate can be made into a problem with linear-distance by requiring the inputs to be encoded by a good code. What interests me though, is whether there exist problems in the literature, in which the linear-distance occurs in a natural way (as the distance in the Gap-Hamming-Distance problem).

Let $C:\{0,1\}^{n} \to \{0,1\}^{2n}$ be an error correcting code with linear distance. Let $g: \{0,1\}^{n} \times \{0,1\}^{n} \to \{0,1\}$ be a function whose randomized communication complexity is large (say, $\Omega(\sqrt{n})$ or $\Omega(n))$.

Define $f: \{0,1\}^{2n} \times \{0,1\}^{2n} \to \{0,1,*\}$ to be the partial function that on codewords of $C$ outputs $f(x,y) = g(C^{-1}(x),C^{-1}(y))$, and it outputs $*$ if at least one of $x,y$ is not in $C$.

Clearly, the communication complexity of $f$ is equal to the communication complexity of $g$, and $f$ satisfies the property that for every two different inputs on which $f$ outputs 0 or 1, the distance between them is linear.


Number of subsets on a set with partial order Given a set $S$ with strict partial order $<$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a<b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are downward-closed?

Are there algorithms that can solve the problem in time polynomial in $|S|$?

See three closely related questions Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits? and Is counting maximal cliques in an incomparability graph #P-complete? and https://mathoverflow.net/questions/49515/on-the-number-of-antichains-of-a-poset

They are all on antichains rather than downward-closed sets but downward-closed sets correspond one-for-one with the antichains of their maximal elements.

I believe both of the cstheory questions have answers with references that also answer your question: no, the problem is #P-complete.


Is the feasible region of this SDP polyhedral? We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral?

We believe this to be true since the 'circular' portion of the cone of semidefinite matrices is due to the extreme rank-$1$ matrices. Any 'curved' boundary of the feasible region must occur from an infinite number of extreme rays.

As a consequence, can we claim that this SDP can be solved exactly in polynomial time just like linear programs which too have a polyhedral feasible region?

No, even if there is a finite number of feasible rank-1 matrices, the feasible region of an SDP does not have to be polyhedral.

A spectrahedron you see all the time in applications is $S_n = \{X: X \succeq 0, X_{11} = \ldots = X_{nn} = 1\}$, i.e. the set of Gram matrices of $n$ unit vectors. This is, for example, the feasible region for the Goemans-Williamson SDP relaxation for MaxCut. There can be no more than $2^n$ rank-1 matrices in $S_n$, because $xx^T \in S_n$ implies $x_i^2 = 1$ for all $i$, and therefore $x \in \{-1, 1\}^n$.

Now let's look at $S_3$. Write

$$
X = \left(
\begin{array}{ccc}
1 & x & y\\
x & 1 & z\\
y & z & 1
\end{array}
\right)
$$

By Sylvester's criterion, $X \succeq 0$ if and only if all principal minors are non-negative. This gives the following inequalities:
$$
\begin{align}
 x^2, y^2, z^2 &\leq 1\\
x^2 + y^2 + z^2 &\leq 1 + 2xyz
\end{align}
$$
The first three inequalities come from writing the 2-by-2 minors, and the last comes from writing the determinant of $X$.

It's now easy to see this set is not polyhedral. For example, let the set $T$ be the projection of $S_3$ onto the free variables $x, y, z$, and consider $U = T \cap \{(x, y, z): z = 0\}$. Polyhedral sets remain polyhedral after orthogonal projection and intersection with halfspaces, so if $S_3$ is polyhedral, then $U$ is as well. But $U = \{(x, y, 0): x^2 + y^2 \leq 1\}$ is a disc.

In fact there is also a direct geometric argument that $U$ is a disc. If $X$ is the Gram matrix of the vectors $u, v, w$, then setting $z = 0$ means $v \perp w$, and $(x, y)$ are the coordinates of the projection of $u$ onto the plane spanned by $v$ and $w$, expressed in the orthonormal basis given by $v$ and $w$. Since $u$ can be any unit vector, $(x,y)$ can be any vector of length at most $1$.

For illustration, here is the set $T$:

And here you can see that $U$ is a disc:


How to find the set of edges for the directed graph associated with a partial order? I have a set $S$, and a partial order relation $\preceq$ defined on $S$. The way this partial order is given to me is through a function $f:S\times S \to \{true, false\}$,  where $f(a,b) = true$ if and only if $a\preceq b$. Given this setup, I can construct a directed graph $D = (S, E)$, where $E= \{(a,b) \in S\times S | f(a,b) = true\}$. I can find all the elements of $E$ in  time $|S|^2/2$ by examining all the possibilities. I am looking for an algorithm that can take advantage of the properties of partial order (in particular, transitivity), to reduce the expected time to find all the elements of $E$ to a linear order function of $|S|$.

As Yury already mentioned, the output size can be too large to hope for subquadratic time, when measured as a function of the input size $n$. But even when the output size is small, very little can be done. In particular, suppose that the input is a partial order with a single comparable pair, chosen uniformly at random among all such partial orders. Then the output size is $O(1)$ but nevertheless it takes $\Omega(n^2)$ queries to find the comparable pair. This is true regardless of whether you're considering only deterministic algorithms or whether you're doing expected case analysis of randomized algorithms.


Proof and computational complexity I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong relation between proof and computational complexity?
I'm asking this as a reference request.

Maybe the keyword you are looking for is "Implicit Complexity". It is more general than Curry-Howard correspondence, but several lines of research investigate along the axis you are interested in. You can check for instance the publications of Patrick Baillot for many references and pointers.
For a little self-promotion, here are for instance two recent papers [KPP1,KPP2] characterizing via the Curry-Howard correspondence on certain cyclic proofs the following complexity classes, depending on the logical rules incorporated or not in the cyclic proof system:

Regular languages (no contraction, no cut) [KPP1]
DLogSpace (contraction, no cut) [KPP1]
Primitive recursive functions (cut, no contraction) [KPP2]
Gödel's System T (cut, contraction) [KPP2]

[KPP1] Cyclic Proofs and Jumping Automata. Kuperberg, Pinault, Pous, FSTTCS 2019
[KPP2] Cyclic Proofs, System T and the power of Contraction. Kuperberg, Pinault, Pous, POPL 2021


The probability by which Bloom filters preserves the order relation given a similarity measure on sets A Bloom filter is a data structure for probabilistic set-membership. When adding an item to the set, $k$ bits (whose indices are determined by $k$ different hash functions) are set to 1. To check if an item is a member of the set, those $k$ bits are checked to be equal to 1. Deletions are no supported and there is a probability of false positives.

Bloom filters are usually used make digests of big sets. In our case they are used to represent a set of items a certain user are interested in. Our clustering algorithm uses the similarity between the sets of two users (Cosine Similarity usually). However for the cryptographic version, we use the similarity between the corresponding Bloom filters of the sets instead.

  What I am seeking as whether there is
  any references regarding the
  conditional probability that the
  similarity between two Bloom filters
  will tell us something about the
  similarity between the corresponding
  sets, and to which degree Bloom
  filters preserve the order relation on
  Cosine Similarity (or other similarity
  measures).

I have been doing some work on that, and it gets pretty deep, lots of combinatorics and multi-set coefficients. I've posted a related question here. I tried to search for papers studying these properties as well and I did not manage to find something of much use.

This is not a direct answer to your question,  but it's related. The probability you want is precisely what is provided by min-wise hashing schemes. In particular, a min-wise hash takes a set and produces a single element, with the property that the probability of the two elements being identical is precisely the Jaccard similarity between the sets (intersection/union).


Membership problem for certain class of unrestricted grammars Consider an arbitrary context-free grammar $G$ over the alphabet $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$. To the productions of this grammar,  add two fixed non-context-free productions $P$: $\overline{0} 0 \rightarrow  \epsilon$  and $\overline{1} 1 \rightarrow  \epsilon$. Call the resulting grammar $G^P$ standing for "$G$ augmented with the productions $P$".

Is it possible to give an algorithm which takes a grammar $G^P$ and a  string $s$ over $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$ and decides whether $s \in \mathcal{L}(G^ P)$?

This class of grammars is undecidable. Here is a rough idea about how to use it to emulate Turing machines.

At each point, the current partially expanded word would look like

$$[\mbox{tape to the left}][\mbox{head}][\mbox{tape to the right}]$$

Here:

$[\mbox{tape to the left}]$, after applying $P$, only contains characters $\overline0$ and $\overline1$.
$[\mbox{tape to the right}]$, after applying $P$, only contains characters $0$ and $1$.
$[\mbox{head}]$ is a single nonterminal, which encodes both the head state and the character at the head position.

Suppose that the head is in state $S$, and the character under the head is $i\in\{0,1\}$. Then the head is represented by nonterminal $S_i$. If it needs to transition to state $T$, replace the current character with $j$, and move to the left, there are two transitions $S_i\rightarrow0T_0j$ and $S_i\rightarrow1T_1j$. If it needs to move to the right instead, there are two transitions $S_i\rightarrow\overline jT_0\overline0$ and $S_i\rightarrow\overline jT_1\overline 1$. In some sense, the head has to "guess" the character in the direction it is moving to by producing the matching character. If the guess is wrong, the invariant on $[\mbox{tape to the left}]$ or $[\mbox{tape to the right}]$ would be violated, and it would never recover.

When the machine halts, the head should "consume" its tape on both sides by "guessing" and producing matching characters. After that, it should produce empty word. As a result, empty word would be a member of such grammar if and only if the corresponding Turing machine halts.


Proof of a unique homomorphism from an initial object What is the proof that there is only one homomorphism from an initial object to another object?

As far as I remember (and my copy of Pierce's Basic Category Theory for Computer Scientists confirms this), the initial object is defined as an object with exactly one arrow to each object in the category.


Oracle comparing $EXP$ with $UP$ Heller (Theorem 6) gave an oracle relative to which $NP=EXP$, and Homer & Selman gave an oracle relative to which $P=UP$ and $\Sigma_2^P=EXP$.
Beigel, Buhrman, Fortnow (freely available author's version) gave an oracle in which $P=\oplus P$ and $NP=EXP$ holds.

Is there an oracle that gives $P\neq UP=coUP=NP=coNP=\oplus P=EXP$?

Is there an oracle that gives $P=UP=coUP\neq NP=coNP=\oplus P=EXP$?

Or is it known $UP\neq EXP$ unconditionally?

$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ relative to any oracle, this should resolve 1. (I say "should" because I haven't checked all the details...)

*UP-generic oracles are discussed, for example, by Fenner-Fortnow-Kurtz-Li (author's freely available version) and also (shameless self plug) a quick tutorial in Section 5.1 here (author's free version)


Determining the distribution of results of a simple algorithm Setting
Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$:

Pick an integer $k \in N$, uniformly at random.
Pick a subset of $k$ elements from $N$, uniformly at random.

After picking $s$ such sets, we repeatedly (until exhaustion) mark each number that is in a set whose other numbers are all marked.
Example
For example, if $N=\{1,2,3,4,5\}$ and $s=3$, we might pick the sets $s_0=\{1,3,5\}$, $s_1=\{1,4\}$ and $s_2=\{4\}$.  In the marking phase, we'd first mark $4$ (because in $s_2$ all 0 other elements are marked), then we'll mark $1$ (from set s_1), and we'll be done.
More generally, if $s=1$, then we know that $\frac{1}{N}$ fraction of times, we will have marked exactly one element with this process, and $\frac{N-1}{N}$ fraction of times we will mark no elements.
Question
Can anyone provide a closed-form expression for the distribution of the number of marked elements after this procedure for arbitrary $s$?
P.S.  I am purposefully leaving out the motivation or reference for this algorithm so as not to bias answers.  Those who recognize the motivation are kindly asked not to mention it, unless it specifically helps with the solution.

I suspect you won't get a closed form solution for the distribution you're looking for. Think of the seemingly easier problem where $k$ is always chosen to be exactly $2$, and where you get the set $\{1\}$ "for free". This problem is just like asking for a closed-form distribution of the cardinality of the connected component in the Erdos-Renyi graph $G(n,s)$ that contains a specific vertex $v_1$. I'm pretty sure that there's no known closed-form description of this distribution, and that in fact the lower order terms are poorly understood, especially around the critical value $s \sim n \log n$.


Adherence of languages and the Dyck language Let $L \subseteq X^*$ and $X = \{a,b\}$ be a language of finite words, denote by $A(u)$ the prefixes of some word (finite or infinite), then the adherence $\mbox{Adh}(L)$ is defined to be the set of infinite words such that
$$
 \mbox{Adh}(L) = \{ \xi \in X^{\omega} : A(\xi) \subseteq A(L) \}
$$
i.e. the set of infinite words all of whose prefixes are prefixes of some words from $L$. Also
write $u \le v$ if $u$ is a prefix of $v$. Define the Dyck language as
$$
 D = \{ v \in X^* : |v|_a = |v|_b \mbox{ and } \forall w \le v : |w|_a \ge |w|_b \}.
$$
Examples of words from $D$ are: $ab, abaabb, aabbab$. Then it is claimed that
$$
 \mbox{Adh}(D) = \{ \xi \in X^{\omega} : \forall v < \xi : |v|_a \ge |v|_b \}.
$$
Note that if this holds then $aaba^{\omega}$ should be in $\mbox{Adh}(D)$. I wanted to proof that claim, therefore I use the property of Adh:
$$
 \mbox{Adh}(L^*) = L^* \cdot Adh(L) \cup L^{\omega}.
$$
And define a "strict" Dyck-language $D_s := \{ a^nb^n : n \ge 0 \}$, then $D = (D_s)^*$.
It is
$$
 \mbox{Adh}(D_s) = \{ a^{\omega} \}
$$
because $A(D_s) = \{ \varepsilon, a, ab, aa, aab, aabb, \ldots \} = \{ a^i b^j : i \ge j \}$ and just the subset $a^*$ fulfills the property that there exists an infinite word $\xi$ with $A(\xi) = a^*$, for $a^ib^j$ with $j > 0, i \ge j$ just has a finite number of completions $w$ such that $a^ib^jw \in A(D_s)$ (namely by $w = \varepsilon, b, bb, \ldots, b^{i-j}$) and so could not be the set of prefixes of some infinite word (the set $A(\xi)$ for infinite $\xi$ has two properties, 1) it is infinite and 2) the words could be lineary ordered according to the prefix relation, by 2) it is enough to look at some $a^ib^j$ and see of what words from $A(D_s)$ it is a prefix of).

Now using the property it is
$$
 \mbox{Adh}(D) = \mbox{Adh}(D_s^*) = D_s^* \cdot Adh(D_s) \cup D_s^{\omega} = D_s^* a^{\omega} \cup D_s^{\omega}.
$$
But the word $aaba^{\omega}$ is not an element of this language, contradicting the first claim? Might the claim be false, or is there some flaw with my proof, I don't see it, maybe you can help?

PS: The claim (unproved) as well as the properties of the Adh-Operator is from the famous and often cited paper Adherences of Languages, which introduces those notions, so I think the claim is correct.

For each $n \geq 0$, the word $aaba^nb^{n+1}$ is in $D$, therefore $aaba^\omega$ is in $Adh(D)$.


what advantage does heapsort has over smoothsort? Wikipedia states that the advantages of smoothsort over heapsort is that at times it comes closer to O(n) time.

Now I was wondering what advantage does heapsort has over smoothsort?

Or to rephrase this question, is smoothsort always a better choice than heapsort (even if the input is not already sorted to any degree) ?

Having just done some reading up on the two algorithms, it would appear that heapsort has no implicit O advantage over smoothsort. This kind of makes sense when you think that smoothsort is just a special kind of heapsort, using a special kind of heap.

Where heapsort does have is an advantage is that it is easier to understand, and much better documented. There are very few publicly available implementations of smoothsort, and very little literature on them, however there is a lot of literature on heapsort.

Indeed, the only real accessible literature is this write-up by Keith Schwarz. It is also the basis of the wikipedia article.


Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them? It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them.
However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most one push or pop in each move?

To be more specific, call a PDA real-time if the machine can see the currently read letter and the top of the stack, then based on this, it either needs to delete the top element of the stack (pop), or push one element onto the stack (push), or leave the stack as it is. In either case, it has to move to the next letter.

  Is there a CFL that no real-time PDA can recognize?

Related: Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

Crossposted: https://cs.stackexchange.com/questions/114995/pdas-without-%ce%bb-steps-or-popping-more-than-one-from-stack

In the standard $\epsilon$-free PDA definition the transition function is:

$\sigma : Q \times \Sigma \times \Gamma \to Q \times \Gamma^*$

$(q_i, a, A, q_j, \alpha) \in \sigma$ means that the PDA on state $q_i$, with head on input $a$ and $A \in \Gamma$ on top of the stack, enters state $q_j$ and replace $A$ with $\alpha \in \Gamma^*$

According to this definition, if $|\alpha| \leq 1$ there is no way to increase the stack and the resulting automata is a DFA.

But letting $|\alpha| \leq 2$ is enough to recognize all CFLs; and this is a direct consequence of the following theorem:

Theorem [D.J. Rosenkrantz. Matrix equations and normal forms for context-free grammars] Given a proper context-free grammar $G$, an equivalent context free grammar in quadratic Greibach normal form can effectively be constructed from $G$

A grammar $G$ in quadratic Greibach normal form if every right side of the rules is in the form $A V^*,\; |V| \leq 2$ ($A$ is the terminal alphabet, $V$ is the set of non-terminals):

$X \to a\, B C$ or
$X \to a\, B$ or
$X \to a$

$B, C \in V$

***ADDENDUM

This is an idea to prove that even with the constraint required by domotorp in the question (at each step 1 POP or 1 PUSH or NO CHANGES ) we can recognize all CFLs.

The above theorem says that a PDA $P$ that can "look" at the top symbol $X$ of the stack and according to it and the current input symbol can (i) POP it, (ii) REPLACE it with $B$ or (iii) REPLACE it with $B$ and PUSH $C$ is as powerful as a PDA.

In order to build an equivalent $P'$, we expand the set of non-terminals $\Gamma$ of $P$ to $\Gamma' = \Gamma \times (\Gamma \cup \{ = \})$; we also expand the set of states $Q$ to $Q' = Q \times (\Gamma \cup \{*\})$

The double symbols in each "register" $r$ of the stack are used to store both the symbol at $r$ (left element) and to "override" the symbol at $r-1$ (right element):

      <A,B>  in P' is equivalent in P to  A
      <C,.>                               B
      ....                               ....

      <A,=>  in P' is equivalent in P to  A
      <C,.>                               C
      ....                               ....

If $P'$ is in state $\langle q_j,*\rangle$ it means that the "logic" top of the stack symbol that it should use is effectively the top of the stack; if it is in state $\langle q_j, A \rangle$ then the "logic" top of the stack is $A$ (and the real top should be ignored).

So the replace (ii) operation of $P$ can simply be stored in the internal state of $P'$:

$q_i, a, A \to q_j, B$ becomes

$\langle q_i, * \rangle, a, \langle A,\cdot\rangle \to \langle q_j, B \rangle, \langle A,\cdot\rangle$
$\langle q_i, A \rangle, a, \langle \cdot,\cdot\rangle \to \langle q_j,  B \rangle, \langle \cdot,\cdot\rangle $

As soon as $P$ needs to PUSH $BC$ (iii), it can store $B$ in the right part of the pushed symbol (the "override" part):

$q_i, a, A \to q_j, BC$ becomes

$\langle q_i, * \rangle, a, \langle A,\cdot\rangle \to \langle q_j, * \rangle, \langle A,\cdot\rangle \langle C,B\rangle$
$\langle q_i, A \rangle, a, \langle \cdot,\cdot\rangle \to \langle q_j, * \rangle, \langle \cdot,\cdot\rangle \langle C,B\rangle $

The $P$ POP operation (i) can be simulated popping the current top and if it "overrides" the previous element, store it in the state:

$q_i, a, A \to q_j, \epsilon$ becomes

$\langle q_i, * \rangle, a, \langle A,= \rangle \to \langle q_j, * \rangle, \epsilon$
$\langle q_i, * \rangle, a, \langle A,B \rangle \to \langle q_j, B \rangle, \epsilon$
$\langle q_i, A \rangle, a, \langle \cdot,= \rangle \to \langle q_j, * \rangle, \epsilon$
$\langle q_i, A \rangle, a, \langle \cdot,B \rangle \to \langle q_j, B \rangle, \epsilon$

***ADDENDUM 2

The above proof could be highly simplified, because:

the PDA derived from the quadratic Greibach Normal form needs only one state (provided that the acceptance condition is the empty stack at the end of the input);
$P'$ could simply store the TOP of the stack in its internal state (there is no need to use $\Gamma' = \Gamma \times Gamma$

as soon as I have some free time I'll update the answer.


Can the "mutual independence" condition in the Lovász local lemma be weakened? The Lovász local lemma, as stated in Corollary 5.1.2 here, is given as follows.

  Lemma. Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is mutually independent of all but at most $d$ of the $A_j$'s. Then if $ep(d+1) \leq 1$, the probability that none of the $A_i$'s occur is positive.

I have a few questions about the assumptions needed for the above lemma. Looking at the proof given in the Wikipedia article here, it appears that one does not require each $A_i$ to be mutually independent of all but at most $d$ of the $A_j$'s. Instead, all one requires is that$$\text{Prob}\left(A_i \mid \bigwedge_{j \in S} \overline{B_j} \right) = \text{Prob}(A_i),$$where $S = \{1, \ldots, k\} - \Gamma(A_i)$, where $\Gamma(A_i)$ is the dependency locus of $A_i$. I think that the above condition appears to be considerably weaker than mutual independence; indeed, mutual independence means that
$$\text{Prob}\left(A_i \wedge \bigwedge_{j \in S} \overline{B_j}\right) = \text{Prob}(A_i) \cdot \prod_{j \in S} \text{Prob}(\overline{B_j}).$$

Am I right to say that mutual independence is not required?

Also, is there a reason why the constant $e$ in the statement of the Lovász local lemma is optimal? Several sources seem to agree on this. It seems somewhat arbitrary to me, and I feel like a smaller constant can be achieved by being more careful in the proof.

Thanks in advance!

The Lopsided Lovasz Local Lemma relaxes the mutual independence condition to negative dependence. We assume we have events $A_1, \ldots, A_n$, with a lopsidependency graph $G$ defined on $[n]$ s.t. for every event $A_i$ and every $S \subseteq [n] \setminus \Gamma^+(i)$,
$$
\Pr\left(A_i \mid \bigwedge_{j \in S}{\bar{A_j}}\right) \le \Pr(A_i).
$$
As you (sort of) suggest, the classical inductive proof of LLL works fine with the lopsidependency graph in place of the depdendency graph. This answers your question because the negative dependence condition is only weaker than the equality you wrote. See these notes by Vondrak for some applications.

The tightness of the constant $e$ (in the limit) was shown by Shearer, who characterized the smallest probabilities that guarantee a local lemma-type statement for any given dependency graph. There are fascinating connections with statistical mechanics, covered in a paper of Scott and Sokal.


How to calculate the cost of factoring a large integer? I would like to know how much it would cost to factor a large integer. The cost can be given computer operations, time to process it or even monetary value. I know there are people that factored 200 bit RSA keys, but Wikipedia doesn't say how long it would take in modern CPUs.

-- Background --

I am designing a virtual roulette game where the ball is spun (the number is chosen) before the player bets. As a proof of that but I show the player the product of two primes, one of them is used as the random number seed.

I would like to know what is the minimum suitable size for this number such as the cost of factoring it will be greater than the maximum prize I offer.

To turn the question around, one could equivalently ask: "How large must my prime be in order to be secure until year X against the resource plausibly available to a potent (e.g. government-funded) attacker?" This question is being regularly reassessed in various studies yielding recommended key lengths for crypto systems. A regularly updated web page summarizing these reports can be found here.


Complexity of counting all connected subgraphs Let G be a connected graph.

  What is the complexity of counting all connected subgraphs if G is of the following types?

  G is general.
  G is planar.
  G is bipartite.

I don't care about any structures or ..., just need to count all the connected subgraphs!
I'm also interested in the complexity of counting all connected subgraphs with exactly k nodes in G.

Pointers to papers and books are also welcomed!

Welsh states that the problem #P-complete even in the most restricted case (counting the number of connected subgraphs of a planar bipartite graph). See the bottom of page 305 in Welsh, Dominic (1997), "Approximate Counting", Surveys in Combinatorics, Bailey, R. A., ed., Cambridge University Press, pp. 287–324.

In context, though, I wonder whether he really means connected spanning subgraphs. And that leads me to wonder which version of the problem you want: connected spanning subgraphs, connected subgraphs that need not be spanning, or connected induced subgraphs?


Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem? Possible Duplicate:
  Implications of unprovability of $P\neq NP$

I shortly came across Gödels incompleteness theorem again and I wondered, since so much time has been spent on trying to answer whether $P = NP$, do we know that such a proof exists? Maybe $P = NP$ is a theorem that can't be answered with the kind of math we are currently working with. Do you know evidence or even a proof that Gödels incompleteness theorem does not apply to whether $P = NP$?

Note that Gödel's Incompleteness Theorems are the following statements:

Any formal system which can be used to express arithmetic is either incomplete (there are statements which are neither provable nor disprovable) or inconsistent.
Any formal system which can be used to prove a statement equivalent to  its own consistency, is in fact inconsistent.

But assuming, for instance, that ZF set theory (or an essentially equivalent  foundation for mathematical subjects such as computer science) is consistent, we don't need Gödel's Theorems anymore to tell us that there are statements which are neither provable nor disprovable from our foundations: interesting specific examples, such as the Axiom of Choice have already been demonstrated. So even without Gödel's Theorem, it is certainly concievable that a statement such as "P = NP" is indepdendent of set theory.

For this question, Scott Aaronson has written a very accessible article on the subject, which also goes over the basics of formal logic, what it could mean to have a model of set theory which included an axiom which is equivalent to asserting its own inconsistency, and the subject of logical independence results in general.


Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions? Background

It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.

Although some natural problems are known to exist, many of them are in someway equivalent to simulating Turing machines or the lower bound result is heavily dependent on the machine model.

See this question for more details: Problem in deterministic time $n^p$ and not lower

Question

Does there exist $k \geq 2$ such that there exist problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not computationally hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

Update: As pointed out by @NealYoung in the comments, when $k=2$, no such problems exist.  Also, for the computational model, let's go with multitape Turing machine.

Why does it matter?

I suspect that if the answer is false (meaning that no such problems exist), then all polynomial time problems have non-uniform nearly linear size circuits.

Let me try to explain.

Let $k \geq 2$ be given.

Suppose for a minute that every problem in $DTIME(n^k) - DTIME(n^{k-1})$ is hard for $DTIME(n^{k-1})$ under nearly linear time reductions.

Next, consider a problem $X$ that is complete for $DTIME(2^{k \cdot n})$ (such as the problem of simulating a $2^{k \cdot n}$-time bounded Turing machine on an input).  By the time hierarchy theorem, this problem cannot be solved in much less than $2^{k \cdot n}$ time.

Then, convert this problem $X$ from binary inputs to unary inputs to get a problem $X'$.  We have that $X' \in DTIME(n^k) - DTIME(n^{k-1})$.  By the assumption, it follows that $X'$ is hard for $DTIME(n^{k-1})$ under nearly linear time reductions.

Finally, we can build small non-uniform circuits for $X'$ because there are so few possible unary input strings.  Also, we can build a small circuit for any nearly linear time reduction.  Combining these together, we get small circuits for all problems in $DTIME(n^{k-1})$.

Maybe we can get a contradiction based on some known circuit lower bounds?  Or, there could even be relativized results that come into play.  Any thoughts are greatly appreciated.  Thank you!

The answer to the question is yes, assuming that (for all large $k$) $k$-SUM is not in $\text{DTIME}(n^{o(k)})$.
It also follows (by a result of Patrascu and Williams) that the answer is yes assuming the ETH holds.
The proof reuses the classical technique from the classical proof that, if any unary language is NP-hard, then P=NP.
Definitions

The question: Does there exist $k \geq 2$ such that there exist problems in $\text{DTIME}(n^k) - \text{DTIME}(n^{k-1})$ that are not computationally hard for $\text{DTIME}(n^{k-1})$ under nearly linear-time reductions?

The $k$-SUM problem: Given $n$ integers, are there $k$ of them that sum to zero?

ETH (the Exponential Time Hypothesis): 3-SAT is not in $\text{DTIME}(2^{o(n)})$.

Result
Theorem 1. Assume that (for all $k$), $k$-SUM is not in $\text{DTIME}(n^{o(k)})$.  Then the answer to the question is yes.
Proof. We show the contrapositive.  Assume that the answer to the question is no.  As observed in the post, this implies that, for all sufficiently large $k$, there is a unary language that is hard for $\text{DTIME}(n^k)$ under nearly linear-time reductions.  To complete the proof we show the following:
Lemma 1. Assume that, for some $c\ge 1$, for all sufficiently large $k$, there is a unary language that is hard for $\text{DTIME}(n^k)$ under $O(n^c)$-time reductions.  Then, for all $k$, $k$-SUM is in $\text{DTIME}(n^{2c+1}) \subseteq \text{DTIME}(n^{o(k)})$.
Proof. Fix such a $c\ge 1$ and an arbitrarily large $k$. Let $L\subseteq 1^*$ be the unary language that is hard for $\text{DTIME}(n^{k+1})$ under $O(n^c)$-time reductions.
Define the following generalization of $k$-SUM, called $k$-SUM'.  The input consists of $n$ integers, a target $t$, and a budget $d\le k$.  The question is whether any $d$ of the given integers sum to $t$.
To prove the lemma, we describe an $n^{O(c)}$-time algorithm for $k$-SUM' (which clearly generalizes $k$-SUM).
As $k$-SUM' is easily in $\text{DTIME}(n^{k+1})$, by definition of $L$ there is an $O(n^c)$-time reduction, say $f$, from $k$-SUM' to the unary language $L$.
We use the classical technique from the proof that, if there is an NP-hard unary language, then P=NP.  Namely, consider the following dynamic-programming algorithm for $k$-SUM' (presented here in recursive memoized form):

input: $k$-SUM' instance $I=((x_1, x_2, \ldots, x_n), t, d)$

if $n=0$ or $d=0$, return 'true' if $t=0$ and 'false' otherwise  (base case)

compute the reduction $f(I) \in 1^*$ (the time this takes and $|f(I)|$ are both $O(n^c)$)

if we've previously computed the answer for an instance $I'$ with $f(I')=f(I)$, return the same answer for $I$.  otherwise:

let $I_0$ be the $k$-SUM' instance $((x_1, x_2, \ldots, x_{n-1}), t, d)$

let $I_1$ be the $k$-SUM' instance $((x_1, x_2, \ldots, x_{n-1}), t-x_n, d-1)$

recursively compute the answers for $I_0$ and $I_1$

the answer for $I$ is 'true' iff the answer to $I_0$ is 'true' or the answer to $I_1$ is 'true'

memoize the answer for $I$ in the lookup table, under index $f(I)$

return the answer for $I$

The algorithm is correct by standard dynamic-programming reasoning along with the observation that any two $k$-SUM' instances that reduce to the same element of $L$ must have the same answer.
How much time does it take?
For each subproblem (not counting the recursive calls) the time is dominated by the the time to compute $f(I)$, which is $O(n^c)$.
Each subproblem $I'$ that arises in the recursion has size $O(n)$, so $f(I')$ is of the form $1^m$ for $m = O(n^c)$.  Thus, the number of "distinct subproblems" (whose answers are not already cached when they arise) is $O(n^{c+1})$ (we get an extra factor of $n$ because if a subproblem $I$ has an ancestor $I'$ with $f(I)=f(I')$, the answer for $f(I')$ won't be cached when $I$ is encountered).  It follows that the recursion tree has $O(n^{c+1})$ nodes, and the total time is $O(n^{2c+1})$.  $~~~\Box$


Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope? I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ .

Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph of $P$?
(Polynomial in the dimension, the number of equations, and the representation of $b$. I can assume that the number of equations is polynomial in the dimension.)

Update: I think I was able to show that this is NP-hard, see my answer that explains the argument. (And by $NP$-hard, I mean that an polynomial time algorithm would prove $RP = NP$... not sure what the correct terminology is here.)

Update 2: There is a 2 line proof of $NP$-hardness (given the right combinatorial polytope) and I was able to find it an article by Khachiyan. See answer for description and link. :-D

An equivalent problem:

In the comments Peter Shor pointed out that that this question is equivalent to the question of whether we can uniformly sample from the vertices of a given polytope. (I think the equivalence goes like this: In one direction, we can go from a polytope $P$ with a vertex $v$ to the vertex figure at $v$, $P/v$, and sampling the vertices of $P/v$ is equivalent to sampling the neighbors of $v$ on $P$. In the other direction, we can go from a polytope $P$ to a polytope $Q$ of one higher dimension by adding a cone with apex $v$ and base $P$. Then sampling the neighbors of $v$ in $Q$ is equivalent to sampling the vertices of $P$.)

This formulation of the question has been asked before: https://mathoverflow.net/questions/319930/sampling-uniformly-from-the-vertices-of-a-polytope

Edit 2: Embarrassingly, there is a two line proof of the $NP$-hardness, if one starts with the right polytope.

First, recall the circulation polytope of a graph on the bottom of page 4 of Generating all vertices of a polyhedron is hard.

It's vertices are in bijective correspondence with the directed simple cycles. Therefore, they are hard to sample or count by JVV Proposition 5.1. :-D

Equipped with these keywords, I was able to find the hardness of sampling result as theorem 1 of Transversal Hypergraphs and Families of Polyhedral Cones by Khachiyan.

Edit: I wrote up the argument below, and it appears correct. However, there is a much simpler argument, which I'll outline here:

a) By Analysis of backtrack algorithms for listing all vertices and all faces
of a convex polyhedron (Fukuda et al.) it is strongly NP-hard to solve the following problem on polytopes:

Input: A polytope $Ax = b , x \geq 0$ in $\mathbb{R}^n$ a subset $S \subseteq n$

Output: Whether there is a vertex $v$ of $P$ that is nonzero on each of the coordinates in $S$.

b) Given this, one can make the following construction: introduce new variables $y_{ik}$ for $i \in S$ and $k = 1, \ldots, d$, and introduce the inequality $0 \leq y_{ik} \leq x_i$. Call the resulting polytope $P_{S,d}$. The point of this construction is to introduce a hypercube above each vertex, of dimension $d |supp(x) \cap S|$.

c) One can check that the vertices of this polytope all lie above the vertices of the old polytope, and that the number of vertices over a vertex is $2^{d | supp(x) \cap S|}$, where $supp$ is the function that sends a vertex to the coordinates where it is nonzero.

d) By a usual chain of bigons type argument it follows that by taking $d$ sufficiently large, a uniform sample from the vertices of $P_{S,d}$ would (with high probability) give a sample from the vertices maximizing the size of their intersection with $S$.

There appear to be various extensions of this. I will update with a link when the writing is done.

(The old argument used to be here -- it is in the edit history. I've removed it because it's very long and will interfere with finding the correct answer to the question.)


A matrix rank problem over finite fields: Is that a known problem? The following problem is simple to state, but seems quite complicated to solve to me. Any hint or reference to related work is appreciated.

Let $A \odot B$ denote elementwise multiplication of matrices $A$ and $B$.
Let $M|\mathbf w$, where $M$ is a matrix and $\mathbf w$ is a subset of the column indices, denote the matrix formed by selecting columns $\mathbf w$ from $M$.

Problem:

  Input: A binary matrix $B=\left[b_{ij} \right]_{m \times n}$, $b_{ij} \in \{0, 1\}$ and a collection $\{ \mathbf{w}_i \subset \{1,\cdots, n\} | i=1,\cdots,k \}$ of column indices.

  Output: Find a matrix $A=\left[ a_{ij} \right]_{m \times n}$, $a_{ij} \in \mathrm{GF}(p^q)$ such that for each $\mathbf{w}_i$, $i=1,\cdots, k$, rank of $(A \odot B)|\mathbf{w}_i$ is $|\mathbf{w}_i|$ or print IMPOSSIBLE if no such matrix exists.

Informally, the problem is that given an $m\times n$ matrix in which some of the elements are fixed to 0, assign values from a finite field to other elements such that the rank of some specific subsets of the columns is maximized.

Observations:

You can assume that $w=\max_i |\mathbf w_i|$ is a constant.
You can assume that $p^q$ is much larger than $3knw$.
If $\mathbf w_i$'s are disjoint, one can simply solve the problem by solving the problem for each $\mathbf w_i$ separately.
If $\mathbf w_i \subset \mathbf w_j$ for some $i \neq j$, $\mathbf w_i$ can be removed from the collection and the problem does not change.
From #3 and #4, the only difficult case of the problem is when $\mathbf w_i$'s intersect, but do not overlap completely (i.e. one is the subset of another).

Edit:

As "mobius dumpling" noted in his answer, with random assignment from the finite field to the matrix $A$, $(A\odot B)|\mathbf w_i$ has full rank with a constant probability $s$ for each $i=1,...,k$. The problem is that the probability that all $(A\odot B)|\mathbf w_i$ have full rank is $s^k$, which is not a constant. Should I use a more complicated method (such as inclusion/exclusion method) to compute the total probability?
A necessary condition for the problem is: for all $i$: for each $j\in \mathbf w_i$, there is a distinct row $k$ such that $b_{kj}=1$. This can be checked in polynomial time.
Having a full rank matrix $A \odot B$ as the result is neither a necessary nor a sufficient condition. The necessary part is apparent since in many cases, the answer is not a full rank matrix. For the case $m < n$, it is not also sufficient.

When $p^q>3k$, then there is an easy randomized algorithm for this problem (with error probability zero and polynomial expected running time). The algorithm prints "IMPOSSIBLE" if there is $i$ such that $B|w_i$ has more than $n-|w_i|$ rows that consist entirely of zeroes. Otherwise, the algorithm prints "POSSIBLE". It then chooses uniformly random matrices $A$ until it finds one that satisfies the requirements. Below I'll prove that a random matrix $A$ satisfies these requirements with at least constant probability.

If the algorithm printed "IMPOSSIBLE" then it is easy to see that indeed there is no $A$ that satisfies the requirements. Now, consider the case that the algorithm printed "POSSIBLE".

A known result states that a random matrix over a field of size $|F|$ is full-rank with probability $\ge 1-2/|F|$. To see this consider the columns one by one, and compute the size of the linear subspace that they have to "dodge". Work from the last column to the first. You get that the chance that the matrix is full rank is $(1-1/|F|)\cdot(1-1/|F|^2)\cdot\ldots$. In fact, the same proof can be seen to work even if some of the entries are fixed to zero, as long as no entire row is fixed to zero. QED.


Does existence of a total $\mathsf{NP}$ search problem not solvable in polytime imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$? It easy to see that if $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ then there are total $\mathsf{NP}$ search problems which cannot be solved in polynomial time (create a total search problem by having both the witnesses for membership and the witnesses for nonmembership).

Is the converse also true, i.e.

  Does existence of a total $\mathsf{NP}$ search problem not solvable in polynomial time imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?

For total UP the answer is yes, because the question "Is the i'th bit of the solution 1?" is in $NP \cap co-NP$.


DC uniform circuit and parity-P This is a question from the lecture about Toda's theorem:

http://www.cs.princeton.edu/courses/archive/spring01/cs522/lecnotes/lec8.ps

The lecture uses theorem 1 and theorem 2 but not include proof. My question is how to proof?

Theorem 2:

$L \in \oplus P$ iff $L$ can be computed by a DC uniform circuit $\{D_n\}$ that

use $AND$, $OR$, $NOT$, $XOR$ gates.

has size $2^{n^{O(1)}}$ and constant depth

$XOR$ gates can have unbounded (exponential) fanin, but $AND$, $OR$ gates have fanin at most $n^{O(1)}$

$NOT$ gates can appear anywhere in the circuit.

This question may not be a research level question, but I really want to know the answer. If someone can give me a detailed reference, I will appreciate that.

The circuit characterization are by Kannan, Venkateswaran, Vinay, and Yao given in the paper:

A Circuit-Based Proof of Toda′s Theorem


Phase transition in counting feasible solutions to knapsack problems? Imagine that you have a normalized knapsack constraint with $n$ items and weights
$w_1,...,w_n$ satisfying $\sum_{i=1}^n w_i = 1$. I'm trying to understand the behavior of the function

$$Z(c) = \#| S \subset \{1,...,n\} : \sum_{i \in S} w_i \leq c|.$$

Clearly if $c = 0$, then $Z(c) = 0$, and if $c = 1$ then $Z(c) = 2^n$. Are there any results on phase transition behavior for $Z(c)$ when the $w_i$ are drawn randomly?

I'm aware there are results, for example, for counting the number of solutions to constraint satisfiability problems, but I haven't seen similar results for a counting the feasible solutions to a knpasack constraint.

I don't have a reference for you, just a minor remark that is too large for a comment.

We assume $w$ is chosen as follows.  Choose r.v. $x\in[0,1]^n$ uniformly at random (i.e., each $x_i$ is i.i.d. uniformly in $[0,1]$), then set $w_i = x_i/X$, where $X=\sum_j x_j$.  Then with high probability, almost all sets $S$ will have $\sum_{i\in S} w_i \sim 1/2$:

Lemma 1. Let r.v. $w$ be chosen as above.  With probability $1-e^{-n/6}$, for all $\epsilon\in[0,1]$, among the subsets $S\subseteq\{1,\ldots,n\}$, the fraction satisfying $$\textstyle\Big|1/2 - \sum_{i\in S} w_i\Big| \ge \epsilon$$ is at most $2 e^{-n\epsilon^2/4}$.

Proof. For any $x$, and $X=\sum_{i=1}^n x_i$ as described above,
note that $E[X] = n/2$, so by a standard Chernoff bound the probability of the event $X\le n/4$ is at most $e^{-n^2/6}$.
So, with probability at least $1-e^{-n^2/6}$, $X\ge n/4$.

Now fix any $x$ and $w$ with $X\ge n/4$, and fix $\epsilon>0$.  To complete the proof we bound the fraction of subsets $S$ such that $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$.

This fraction equals the probability that $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$ for a random subset $S\subseteq \{1,\ldots,n\}$.

Because $w=x/X$, the condition $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$
is equivalent to $|X/2 - \sum_{i\in S} x_i| \ge \epsilon X$.

Note that $E_S[\sum_{i \in S} x_i] = X/2$,
so by a standard Chernoff bound
$$\Pr_S\big[|X/2 - \textstyle\sum_{i\in S} x_i| \ge \epsilon X\big] \le 2\exp(-X\epsilon^2) \le 2\exp(-n\epsilon^2/4).$$
(The last step uses $X\ge n/4$.) $~~\Box$

We don't have to choose $w$ randomly to get the bound.
Any $w$ with $\max_i w_i = O(1/n)\sum_i w_i$ will do.

Note that the result implies a sharp threshold in the following sense:
for any $c > 1/2$, almost all sets $S$ will satisfy the given knapsack inequality $\sum_{i\in S} x_i \le c$.
For any $c < 1/2$, almost none will.


Hard problems for bounded vertex cover We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?

$(k,r)$-center is another (arguably natural) problem that is $W[1]$-hard parameterized by vertex cover. (See a recent preprint by Katsikarelis, me, and Paschos here - sorry about the self-promotion!). The problem here is to select $k$ vertices (centers) so that all other vertices are at distance at most $r$ from the closest center. This generalizes $k$-Dominating Set (which corresponds to $r=1$). More strongly, the problem is $W[1]$-hard parameterized by vertex cover and $k$.

The catch with our reduction is that we need to produce an edge-weighted graph, i.e. we need the edges to have different lengths. We can replace weighted edges with paths, but then this only proves W-hardness when the problem is parameterized by feedback vertex set. Indeed, if all edges have uniform weights then the problem is FPT parameterized by vertex cover.

This example reinforces Daniel's point (which I agree with) that it would be surprising to find a problem that is W-hard by vertex cover, without having some additional input given besides the graph.


Complexity of blind sort? We all know that the minimal complexity of a comparison-based sorting algorithm is $\Omega(n \log n)$ comparisons. I'm trying to do a blind sort, i.e. given a number $n$ output a circuit (with boolean, arithmetic and "comparison" gates) that sorts a list of $n$ items.

Precomputing all ${n \choose 2}$ comparisons and then doing arithmetic on the resulting bits gets me an $\Theta(n^3)$ algorithm, however by some crazy "pointer arithmetic" I think I can get a $\Theta(n^2)$ version.

Is there a known lower bound for comparison-based sorting circuits along similar lines to the $n \log n$ one for comparison-based sorting algorithm? Might it even be possible to blind sort in $n \log n$ time?

Goodrich's "Randomized Shellsort: A Simple Oblivious Sorting Algorithm" has a discussion of data-oblivious sorting. Sorting networks are data-oblivious, but impractical in general, as I understand it.


Model of MLTT with $\eta$ rule where function extensionality fails Consider intensional Martin-Löf type theory with judgmental $\eta$ rule for dependent product types. Is there a model of it where function extensionality fails?

The simplest one that I know about is the $\text{Set}$-based polynomial model ("container" model). Here, every context is interpreted as a family of sets, i.e. a $Q : \text{Set}$ together with an $A : Q \to \text{Set}$. We can view this as a set of questions together with sets of possible answers for each question, or a request-response protocol with at most two messages sent. Certain game semantics generalize this to arbitrary number of interactions in a protocol.
A morphism between $(Q, A)$ and $(Q', A')$ is a function $f : Q \to Q'$ with $g : (q : Q) \to A'\,(f q) \to A\,q$. So this is not a usual morphism of families, because we map answers in the backwards direction. Again, this can be viewed with the game/protocol intuition, as a synchronous translation between two protocols. The translator gets $q : Q$ from the "domain" agent, computes $f\,q$ and feeds it to the "codomain" agent, then receives an answer in $A'\,(f\,q)$ and translates it back.
Roughly speaking, most of the polynomial model of MLTT works by taking a plain $\text{Set}$ model and the opposite of a simply-typed "fibered" $\text{Set}$ model, and gluing them together. We need to take opposites of type constructions because of the flipping of mapping directions in answers. So when modeling the answer components, products become coproducts, the unit type becomes the empty type, and so on.
Function types and $\Pi$ types are an exception to this scheme, where there is non-trivial interaction between the question and answer components of the model.
See this for the simply typed case. See Pi.agda from this for a formalization of the dependent $\Pi$ case, or this for the same in a more general setting with heavier abstractions.
Regarding the failure of function extensionality: semantic $\Pi$ inhabitants can be viewed as bidirectional functions with forwards and backwards mapping components. However, the function application always projects out and applies the forwards component. Hence, if we have $(a : A) \to f\,a = g\,a$, this only expresses that $f$ and $g$ have the same forwards action, and does not say anything about the backwards actions. So $f = g$ generally does not follow.


Are there published algorithms for on-line creation of AVL trees from ordered streams? Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time.  More specifically this is possible using only O(log n) additional storage, and only O(log n)-time after then end-of-stream is discovered.  The technique involves pennants and the 1-2 binary representation of n.

The technique needs to be modified for AVL trees, and I haven't seen referneces to an on-line algorithm for creating AVL trees.  Does anyone know of such a published algorithm?

If I understand your question correctly and the elements arrive in sorted order, I believe the usual bottom-up AVL tree insertion algorithm meets your criteria. In particular, insert-only AVL trees have $O(1)$ amortized (and $O(\lg n)$ worst-case) update time. Simply maintain a pointer to the last element of the tree and perform each insertion at that location.


Best algorithm for calculating lists of neighbours Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted from nearest fo farthest.

Which is the fastest parallel algorithm for this purpose?

PS: I also crossposted this in math exchange and SO

This is the well-studied problem of Nearest Neighbour Search.  There is not one 'best solution' to the problem---you'll want to choose trade offs based on the input and requirements.

Do you need the creation of the data structure to be parallel?  Or just the queries?  Depending on how many thousands of points you're talking about, if your set of points is static it might not be impractical to do something naive like:

For each point $x$, construct a list of all other points, sorted by distance from $x$.

This can be done in $O(n^2\log n)$ time and $O(n^2)$ space, which is not that bad if you only need to run it once for a set of several thousand points.  It will give you constant or logarithmic query time for pretty much anything you'd want to do.

If you need something smarter that requires less space or less time, I'd recommend reading the Wikipedia article on Nearest Neighbour Search and perhaps refining your question, telling us

how many times you'll need to build the structure from scratch
whether or not it needs to be dynamic
what exactly needs to be parallelized
whether your 'cutoff value' for Euclidean distance is fixed, or will vary from query to query
if possible, a tighter estimate on the number of points.  When somebody says 'thousands' sometimes they mean 3,000 and sometimes they mean 300,000.


Formal semantics of OCaml in Coq The semantics of a large subset of OCaml, called OCamllight,  was formalized in HOL by Owens several years ago. More recently, a type theoretical semantics of a smaller subset of OCaml was implemented in Nuprl by Kreitz, Hayden and Hickey.

Is there any similar development in Coq?

Have you seen Arthur Charguéraud's PhD thesis, Characteristic Formulae for Mechanized Program Verification?

Rather than building the type system and small-step semantics as inductive relations, he gives a technique for converting Caml programs into characteristic formulas. This are basically a generalization of predicate transformer semantics to support a very large subset of Ocaml -- notably, including unsafe casts like Obj.magic. To quote from his thesis:

  I have focused on a subset of the OCaml programming lan-
  guage, which is a sequential, call-by-value, high-level programming language. The
  current implementation of CFML supports the core λ-calculus, including higher-
  order functions, recursion, mutual recursion and polymorphic recursion. It supports
  tuples, data constructors, pattern matching, reference cells, records and arrays. I
  provide an additional Caml library that adds support for null pointers and strong
  updates.

It's a very appealing approach if you want to prove a particular Caml program correct (less so if you are interested in its metatheory, though).


Partition into interval graphs Suppose there is a graph $G=(V,E)$. I want to test if $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs.

I know about the NP-completeness of determining interval numbers but the above problem is different.
Now, in the literature I found this work by A. Gyárfás and D. West on multitrack interval graphs but I'm not sure if it is relevant to above problem.

Any citation to existing literature on the above or similar problem would be helpful. Also please let me know if there is a formal name for the above problem.

I think, your problem is NP-complete. It is a special case of a theorem
by Farrugia,
stating that it is NP-hard to test if the vertex set a graph can be partitioned into
two subsets $V_1,$ and $V_2$ such that $G(V_1)$ belongs to the graph class $\mathcal{P}$ and
$G(V_2)$ belongs to the graph class $\mathcal{Q}$, provided $\mathcal{P}$ and $\mathcal{Q}$
are closed under taking vertex-disjoint unions and talking induced subgraphs, and at least
one of $\mathcal{P}$ and $\mathcal{Q}$ is non-trivial (meaning not all graphs in the class are
edgeless).


Graph labelling where vertices with a common neighbour get different labels Is the following notion of graph labeling (let me call it special labeling) ever studied in the literature?
A special labelling of a (simple undirected) graph $G$ is a function $f:V(G)\to\mathbb{N}$ such that $f(u)\neq f(v)$ whenever $u$ and $v$ have a common neighbour (i.e., $N(u)\cap N(v)\neq \emptyset$).
The closest I  could find in the literature is strong subcoloring introduced in [1]. A strong subcoloring of $G$ is a function $f:V(G)\to\mathbb{N}$ such that $f(u)\neq f(v)$ whenever $d(u,v)=2$ (i.e. distance between $u$ and $v$ in $G$ is two). The difference between the two notions is that special labelling does not allow two adjacent vertices to have the same label if they have a common neighbour. Both notions are the same for triangle-free graphs.
Reference
[1] Shalu, M. A.; Vijayakumar, S.; Yamini, S. Devi; Sandhya, T. P., On the algorithmic aspects of strong subcoloring, J. Comb. Optim. 35, No. 4, 1312-1329 (2018). ZBL1400.90266.

`Special labelling' is not exactly $L(0,1)$-coloring, but is very close. In $L(0,1)$-coloring, neighboring vertices can get the same colour even if they have a common neighbor. Speciall labelling do not allow this. Special labelling is already studied in the literature under the name injective coloring.

An injective colouring of a graph $G$ is a colouring $c$ of the vertices
of $G$ that assigns different colours to any pair of vertices that have a
common neighbour.

There are a number of papers on injective coloring. The main graph classes studied are planar graphs [1,2,3], chordal graphs [4], regular graphs [5], and sparse graphs [6]
References
[1] Bu, Yuehua; Qi, Chentao; Zhu, Junlei; Xu, Ting, Injective coloring of planar graphs,  ZBL07300884.
[2] Lužar, Borut; Škrekovski, Riste; Tancer, Martin, Injective colorings of planar graphs with few colors, Discrete Math. 309, No. 18, 5636-5649 (2009). ZBL1209.05093.
[3] Bu, Yuehua; Wang, Chao; Yang, Sheng, List injective coloring of planar graphs.,  ZBL06986943.
[4] Hell, Pavol; Raspaud, André; Stacho, Juraj, On injective colourings of chordal graphs, Laber, Eduardo Sany (ed.) et al., LATIN 2008 Berlin: Springer (ISBN 978-3-540-78772-3/pbk). LNCS 4957, 520-530 (2008). ZBL1136.68463.
[5] Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique, On the injective chromatic number of graphs, Discrete Math. 256, No. 1-2, 179-192 (2002). ZBL1007.05046.
[6] Cranston, Daniel W.; Kim, Seog-Jin; Yu, Gexin, Injective colorings of sparse graphs, Discrete Math. 310, No. 21, 2965-2973 (2010). ZBL1209.05075.


Bidirectional A*: is an update of the distance estimation feasible while searching? The A* algorithm is some kind of an enhanced Dijkstra. Keep in mind that I want an optimal algorithm here and A* is optimal if the heuristic does not overestimate the distance to the goal.

The bidirectional case of A* is not as simple as the bidirectional Dijkstra as the finish condition is a bit tricky, of course you can manage to implement it if you work with "consistent potential functions" (see paper reference below).

Now to my question: when implementing a special distance estimate for A* (landmarks/ALT) this works also in the bidirectional case. In some papers they say one can change the active set of landmarks while the search is going on. This makes sense as the estimates will get better and still only a subset is involved for the estimate.

But will changing/improving the distance estimate while the search is going influence the optimality?

Unintuitive things can follow from this, e.g. a distance update to a node lowers the distance from source to this node but could increase the distance from this node to the goal due to the better distance estimate but I'm unsure if this violates the 'consistent potential' definition and could result in suboptimal paths. (E.g. in my latest trial to implement this I sometimes get suboptimal results but this could be also other bugs.)

The paper "Computing Point-to-Point Shortest Paths from External Memory" says I can do so but I'm unsure if I misunderstood something:

  6.1 Restarting. As we shall see below, we sometimes need to change the way lower bounds are calculated in the middle of an ALT computation,
  e.g., by replacing the current potential functions p f and p r by
  another consistent pair.

I think I have found the answer in the paper and it is indeed not just a replacement of the potentials:

  Now, if we want to replace p_f and p_r (forward and reverse potential) , all we need to do is change
  the keys of the labeled vertices for the two searches appropriately
  and update the priority queues containing these vertices. This takes
  time proportional to the number of labeled vertices at this point.


Small circuits for circuit evaluation problem Let $\mathsf{CircuitEval}_{s, n}$ be the function which maps an $s$-gate circuit $C$ on $n$ bits and an $n$-bit string $x$ to $C(x)$. Assume that circuits are encoded as an acyclic sequence of assignments $k := g(i, j)$ where $i, j, k$ are wire labels.

I know this is a bit of a funny question, but what is the best known upper bound on the circuit complexity of this problem? There is an $O((s + n)^2)$ single-tape TM computing this function, and so by the Fischer-Pippenger simulation, size $O((s + n)^2 \log(s + n))$ should suffice. The quadratic comes from having to seek back and forth. Is it possible to do better? Is it possible to do in size $O(s + n)$?

I have learned from talking to Ryan Williams (who deserves the credit for my being able to post this answer) that it is known from Paul and Pippenger that Circuit Eval can be decided by a quasilinear time multitape TM and also that there are reductions from multitape TMs to circuits which give only a quasilinear size blowup. That is, Circuit Eval has circuits of size $(n+s)\log^{O(1)}(n+s)$, as per your formulation.

There is a proof of this here on page 6 (see Theorem 3.1 (Folklore)).


What should a proof of correctness for a typechecker actually be proving? I've been programming for several years, but am very unfamiliar with theoretical CS. I've recently been trying to study programming languages, and as part of that, type checking and inference.

My question is, if I try to write a type inference and checking program for a programming language, and I wish to prove that my typechecker works, what exactly is the proof I'm looking for?

In plain language, I want my type checker to be able to identify any errors in a piece of code that might occur at runtime. If I were to use something like Coq to try proving that my implementation is correct, what exactly will this "proof of correctness" be trying to show?

That's a good question! It asks what we expect from types in a typed language.

First note that we can type any programing language with the unitype: just pick a letter, say U, and say that every program has type U. This isn't terribly useful, but it makes a point.

There are many ways to understand types, but from a programmer's point of view the following I think is useful. Think of a type as a specification or a guarantee. To say that $e$ has type $A$ is to say that "we guarantee/expect/demand that $e$ satisfy the property encoded by $A$". Often $A$ is something simple like int, in which case the property is simply "it's an integer".

There is no end to how expressive your types can be. In principle they could be any kind of logical statements, they could use category theory and whatnot, etc. For example, dependent types will let you express things like "this function maps lists to list such that the output is a sorted input". You can go further, at the moment I am listening to a talk on "concurrent separation logics" which allows you to speak about how concurrent programs work with shared state. Fancy stuff.

The art of types in programming language design is one of balancing expressivity and simplicity:

more expressive types allow us to explain in more detail (to ourselves and to the compiler) what is supposed to be going on
simpler types are easier to understand and can be automated more easily in the compiler. (People come up with types which essentially require a proof assistant and user's input to do type checking.)

Simplicity is not to be underestimated, as not every programmer has a PhD in theory of programming languages.

So let us come back to your question: how do you know that your type system is good? Well, prove theorems that show your types to be balanced. There will be two kinds of theorems:

Theorems which say that your types are useful. Knowing that a program has a type should imply some guarantees, for instance that the program won't get stuck (that would be a Safety theorem). Another family of theorems would connect the types to semantic models so that we can start using real math to prove things about our programs (those would be Adequacy theorems, and many others). The unitype above is bad because it has not such useful theorems.
Theorems which say that your types are simple. A basic one would be that it is decidable whether a given expression has a given type. Another simplicity feature is to give an algorithm for inferring a type. Other theorems about simplicity would be: that an expression has at most one type, or that an expression has a principal type (i.e., the "best" one among all types that it has).

It is difficult to be more specific because types are a very general mechanism. But I hope you see what you should shoot for. Like most aspects of programming language design, there is no absolute measure of success. Instead, there is a space of design posibilities, and the important thing is to understand where in the space you are, or want to be.


Can a result of (any) hash algorithm contain the hash result itself? Suppose you have a file of 240 lines. Any lines, any content.
You then calculate the hash of that file, let's say MD5, and the result is something in the following structure:

f8dbe310c1f61066d766071b07503ce8

Now, you take this hexadecimal digest, and add it to the file as line 241.

Rehashing the file (with additional hash line) will result with a new hash value obiously.

My questoin is whether it is even theoretically possible for a hash value to contain itself, meaning, can there be a file, with some content that its hashed value is identical to a string already presented in the file (e.g. line 241 in this example)

For the first question, about the last line, it surely depends on the hash function. For example, suppose each line is a single bit (0 or 1). If the hash function is the xor of the bits, then the answer is yes -- take 240 lines with total parity 0. But the answer is no if the hash function is defined by
$$f(x_1, x_2, \ldots, c_n) = \neg (x_n \oplus f(x_1, \ldots, x_{n-1})),$$
with $f()=0$, where $\oplus$ is xor.

For the second question (about any line), I think @Yonatan's point in his comment was that if the hash function has finitely many possible outputs (as e.g. MD5 does), then, for a file that already contains every possible hash output (one per line), no matter what the hash outputs it will be in the file already.


Is the maximum independent set in cubic planar graphs NP-complete? In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation from vertex cover and for vertex cover (I suppose in cubic planar graphs) they cite the paper of Garey, Johnson and Stockmeyer 1976.

When I looked at their DBLP entry, there is a single paper that matches the description of the mentioned paper:

Some Simplified NP-complete Graph Problems.

Having checked the paper, the reduction for vertex cover in graphs of maximum degree 3 is for general graphs, not planar graphs. For planar graphs, they only have a reduction that shows hardness on planar graphs of maximum degree 6, not 3 (already the gadget has vertices of degree 6).

I'm wondering if I'm missing something here since there are consequent papers building upon the aforementioned comment of the book.

A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper.

  Bojan Mohar:
  "Face Covers and the Genus Problem for Apex Graphs"
  Journal of Combinatorial Theory, Series B 82, 102-117 (2001)


An efficient Beta-Equivalence algorithm? Is there an efficient algorithm to determine if two terms are beta-equivalent? I'm specifically curious about simply-typed-lambda-calculus, so you can assume both terms are strongly normalizing.
I know a simple algorithm:

Compute the beta normal form for each term.
Confirm that the two BNFs are alpha-equivalent.

But it is possible for BNFs to be exponentially larger than the original Term. Is it possible check the equivalence of Terms S and T in O(|S| + |T|) time?

The answer is no.  An old theorem of Statman states that $\beta$-equivalence in the simply-typed $\lambda$-calculus is not elementary recursive, that is, no algorithm whose running time is bounded by $2^{\vdots^{2^{|S|+|T|}}}$ for a tower of exponentials of fixed height may decide whether two simply-typed terms $S$ and $T$ are $\beta$-equivalent.
The original statement is from
Richard Statman.  The typed $\lambda$-calculus is not elementary recursive.  Theoret. Comput. Sci. 9:73-81, 1979.
A simpler proof may be found in this paper by Harry Mairson.
Edit: as observed by Martin Berger, Mairson proves that $\beta\eta$-equivalence is not elementary recursive, whereas Statman's result (and the OP's question) concerns $\beta$-equivalence, without $\eta$.  However, as pointed out by xavierm02, Mairson's result implies Statman's.  Let me fill in the details for those who are not familiar with $\eta$-long forms.
The $\eta$-long form $\eta(x^A)$ of a variable $x^A$ is defined by induction on $A$: observe that $A=A_1\to\cdots\to A_n\to\alpha$ for some $n\in\mathbb N$, some types $A_1,\ldots,A_n$ (smaller than $A$) and some atom $\alpha$, and let
$$\eta(x^A) :=  \lambda y_1^{A_1}\ldots\lambda y_n^{A_n}.x\eta(y_1^{A_1})\cdots\eta(y_n^{A_n}),$$
where the $\eta(y_i^{A_i})$ are given inductively.
The $\eta$-long form $\eta(M)$ of a simply-typed $\lambda$-term $M$ is defined by replacing every occurrence of variable $x^A$ of $M$ (free or bound) with $\eta(x^A)$.  (NB: through Curry-Howard, this corresponds to taking a sequent calculus proof and expanding it so that it has only atomic axioms).
Observe that:

$\eta$-long forms are stable under substitution, and therefore under $\beta$-reduction;
two $\eta$-long $\beta$-normal forms are $\beta\eta$-equivalent iff they are equal (up to $\alpha$-renaming, of course);
computing the $\eta$-long form of a simply-typed $\lambda$-term is elementary recursive (if you don't keep the size of type annotations, the $\eta$-long form of a term may be exponentially bigger, but that is not a problem).

That Mairson's result implies Statman's is a consequence of the following:
Claim.  Let $M,N$ be two simply-typed $\lambda$-terms.  Then, $M\simeq_{\beta\eta}N$ iff $\eta(M)\simeq_\beta\eta(N)$.
In fact, via point (3) above, an elementary recursive algorithm for deciding $\beta$-equivalence immediately gives an elementary recursive algorithm for deciding $\beta\eta$-equivalence (the one pointed out by xavierm02).
Let us prove the claim.  The right-to-left implication is trivial.  Conversely, suppose that $M\simeq_{\beta\eta} N$. This obviously implies $\eta(M)\simeq_{\beta\eta}\eta(N)$. Let $P$ and $Q$ be the $\beta$-normal forms of $\eta(M)$ and $\eta(N)$, respectively. By point (1) above, both $P$ and $Q$ are $\eta$-long (because $\eta(M)$ and $\eta(N)$ are). But of course we still have $P\simeq_{\beta\eta} Q$, so by point (2) $P=Q$, which proves $\eta(M)\simeq_\beta\eta(N)$ (they have the same $\beta$-normal form).


Advice on good research practices After reading Daniel Apon's question, I started thinking that it might be useful (especially to junior researchers and graduate students like me) to ask a broader and more general question so we can learn from the experience of more senior researchers.

So here is the question:

  What practices have you found most useful in your research?

I don't want to restrict it to any particular type of advice, so any advice on research practice is welcome.

One thing I found useful is to allocate time and designate a space for doing specific research activities.

When I was at Princeton U, I loved sitting at the Engineering library that is well lit, bright and spacious, to read and to think of new ideas. When I verified my 139 pages paper, I used to do it in a room in the biology library at Weizmann that had no computers and no other people, only a desk, chairs and a window to an inner garden. When I go over introductions or notes, I like doing it in coffee shops.

There are several reasons why I found this to be a good practice for me:

(1) Just pondering about a good environment for me for an activity fills me with anticipation for this activity, or at least somewhat prepares me for it.

(2) The fact that I decide to do something specific at this time, and I have the space I need for doing that, induces simplicity, clarity and good order.

(3) Knowing what I like, what I care about, and also what distracts me and what is not good for me, I create environments that make it is easier for me to do what I need to do.