Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete? Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say that the problem P is NP-hard?

Yes, and you'd be right.    2^(2^(i+1)) = 2^((2^i)*(2^1)) = 2^((2^i)*2) = (2^(2^i))^2 ,  so just

pad the input n-vertex instance of vertex cover with 2^(2^(ceil(log2(log2(n))))) isolated vertices.

For all positive integers c, a similar thing will apply when 2^(2^i) gets replaced with 2^(2^(c*i)).

However, under plausible assumptions, that's tight:

Let S be the set of functions from {0,1,2,3,...} to itself that are in ω(1), consider any functions

f and g in S, and let Q be the result of replacing 2^(2^i) with 2^(2^(f(i))) before applying

your sparse embedding.  If Q is NP-hard even under polynomial-time Turing reductions,

then    NP $\subset$ r.o.$\hspace{-0.04 in}\big(\hspace{-0.05 in}$DTIME(2^(n^(o(1))))/g$\hspace{-0.04 in}\big)$ ,  where maxL(n) is an upper-bound

on the length of each of the reduction's oracle queries for n-bit inputs

and the advice can be any function h in S such that

max  (  {0,1,2,3,...,maxL(n)-1,maxL(n)}  ∩  Range(i $\mapsto$ 2^(2^(f(i))))  )    is r.o. at most n^(1/(h(n))).

Furthermore, if there is a function j in S such that  f(n)+j(n) ≤ f(n+1)  holds for all sufficiently large n, then the set of input-lengths on which the algorithm errs can be covered by a collection of

polynomial-length integer intervals such that the gaps between them have length n^(ω(1)),

and if additionally j is computable 2^(n^(o(1)))) time when n is the input itself, not the input's length,

then the advice can be removed.  (without losing the interval-cover property I just mentioned)


Algorithms for graph generation given parameters I guess there may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g. clustering coefficient, average path length, degree distribution, etc). I am new to this field, and some google search didn't find me a thorough review of the literature.

My question concerns a specific case: I want to generate a few undirected regular graphs (i.e. each node of each graph has the same number of edges) with different clustering coefficients and average path lengths. More generally, while fixing a degree distribution, generate graphs by varying clustering coefficient and average path length.

I wonder what are the well-known algorithms for doing this (or links to relevant literature reviews would be great too!), and what are the recommended software for generating such graphs?

This question was posted more than 8 years ago, and much progress was done since then. However, many questions remain open, even very natural ones like sampling a random graph with prescribed clustering coefficient. Also, sampling simple graphs (no loop, no multi-edge) with prescribed degree sequence made much progress but remains difficult.
I would like to give a pointer to a quite comprehensive and recent survey on many aspects of these questions, which I think may be of interest to most readers of this post:
Recent Advances in Scalable Network Generation by
Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders, Christian Schulz, 2020
For the specific problem of graphs with prescribed degree sequence, I recommend:

Configuring Random Graph Models with Fixed Degree Sequences by
Bailey K. Fosdick, Daniel B. Larremore, Joel Nishimura, Johan Ugander, 2016
Fast uniform generation of random graphs with given degree sequences by
Andrii Arman, Pu Gao, Nicholas Wormald, 2020

but this is a very partial list, of course.
The last reference has a dedicated discussion of the regular case.


Do good PCPs for NP give us good PCPs for the entire polynomial hierarchy? The PCP Theorem states that every decision problem in NP has probabilistically checkable proofs (or equivalently, that there exists a complete and quasi-sound proof system for theorems in NP using constant query complexity and logarithmically many random bits).

The “folk wisdom” surrounding the PCP Theorem (ignoring for a moment PCP’s importance to the theory of approximation) is that this means proofs written up in strict mathematical language can be checked efficiently to any desired degree of accuracy without the requirement of reading the entire proof (or much of the proof at all).

I am not able to quite see this. Consider the second-order extension to propositional logic with unrestricted use of quantifiers (which I am told is already weaker than ZFC, but I am no logician). We can already start to express theorems which are not accessible to NP by alternating quantifiers.

My question is whether there is a simple, known way of ‘unrolling’ quantifiers in higher order propositional statements so that PCPs for theorems in NP apply equally well to any level of PH. It could be that this cannot be done – that unrolling a quantifier costs, in the worst case, some a constant part of the soundness or correctness of our proof system.

The truth of a statement is different from it having a (short) proof in a proof system. The language is expressive but it doesn't mean that all valid statements in the language have short proofs in the system.

The theorem doesn't say that you can check the truth of a statement or even the correctness of an arbitrary long proof or of arbitrary theorems. It is for proofs of membership in an $\mathsf{NP}$ set, which by definition have polynomial size proofs (certificates) of membership. The theorem only says that you don't need to read the full (polynomial size) proof of membership in an $\mathsf{NP}$ set to decide its correctness.

One implication of the theorem is applying it to the set of theorems in an arbitrary language which have short (i.e. an arbitrary polynomial) proofs in an efficient proof system (i.e. it is decidable in polynomial time if a given string is a proof of a given statement). For example, theorems of ZFC which have proofs of size $n^{100}$ where $n$ is the size of the formula. If the proof system is sound then you can probabilistically verify the correctness of the theorems which have short proofs with reading a small part of their proofs. I think this is the intend meaning of the informal statement "proofs written up in strict mathematical language can be checked efficiently to any desired degree of accuracy without the requirement of reading the entire proof".


Dimensionality reduction in machine learning This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?).

Dimensionality reduction refers to a collection of techniques that input data and return a lower-dimensional version, with some distortion. PCA and Johnson-Lindenstrauss are the most common examples.

From an algorithmic perspective, the tradeoff is clear: lower dimensionality yields faster runtimes and reduced storage space, but compromises precision. I call this the dimension-distortion tradeoff.

From a statistical/information-theoretic perspective, the situation seems less clear. It is commonly believed that dimensionality reduction (PCA in particular) has a denoising effect and thus should actually improve the performance. On the other hand, dimensionality reduction does discard information, which might cause the performance to degrade. Thus, one must address the statistical question: is the information I'm discarding noise or potentially useful (and even if useful, might the benefits of lower dimension still outweigh the losses)?

There appear to be very few formal analyses of the statistical benefits of dimensionality reduction. One that I'm aware of is in our
ALT'13
 paper (with Gottlieb and Krauthgramer). The setting there is fairly general -- metric spaces.

Are there other formal analyses of the statistical benefits of dimensionality reduction? Perhaps other tradeoffs besides those mentioned above?

Information Geometry is a rigorous framework which combines statistical inference, information theory and differential geometry.

Several open problems in statistics (and geometry) have found a new formulation and solution.
Specificaly the concept of dual connections and dualy-flat spaces. It has been shown that various statistical inference methods (e.g maximum likelihood, EM algorithm etc.) can be formulated in terms of dualy-flat spaces in a statistical manifold (reference "Methods of Information Geometry", Amari, Nagaoka). The new formulation allows a unified view of previously un-related methods and algorithms.

The problem of dimensionality reduction and PCA has been formulated information-geometricaly as follows (with emphasis on information):

"Information-Geometric Dimensionality Reduction"
"An Information Geometric Framework for Dimensionality Reduction"
"The e-PCA and m-PCA: Dimension Reduction of Parameters by Information Geometry"


Is there significance to the ratio of the time it takes to locate a problem's solution over the time it takes to verify the solution? I believe I have found a problem, the solution to which can be verified in 0 time (the solution can only be located in non-zero time, however).  As a result, the ratio of the time required to locate a solution to the problem over the time required to verify its solution is infinite.  I was wondering if this ratio generally has significance in computer science.

There certainly is significance -- and there is a lot that is known about the subject.
If you are willing to make reasonable assumptions, such as the security of cryptographic primitive, then it is straightforward to achieve such a ratio: any secure encryption scheme will provide one example.  Encrypting takes polynomial time if you know the key, while recovering the key if you don't know it takes super-polynomial time (assuming the encryption scheme is secure), so their ratio tends to 0 as the security parameter goes to infinity.
If you want to avoid making any unproven assumptions, then I believe it is an open problem to find such a problem.  In particular, it is an open problem to prove that give an explicit example of a function on $n$ bits such that it takes a circuit of size more than $5n$ to compute the circuit.  See e.g., Is there a better than linear lower bound for factoring and discrete log?.  This corresponds to a constant (strictly greater than zero) ratio.  So, I don't think it is known how to exhibit a problem such that it provably has a ratio that goes to zero in the limit.


What is the state complexity of the copy language? Let a number $n$ be given.  Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$.

In words, $L_n$ is the set of copy strings of length $2n$.

Consider the following state complexity function $s$ such that $s(n)$ is the number of states in the smallest Pushdown Automata that recognizes $L_n$.

Question: Can you formally prove any meaningful lower bound for $s(n)$?

My Conjecture: $s(n) = 2^{\Theta(n)}$.

Known Upperbound: $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$.

Rules:

(1) The stack alphabet must be binary.

(2) The input tape is one-way and can't stop on any input character.

The technique described by Yuval:

Do there exists polynomial size CFG that describe this finite language?

(
you may also read:
Lower bounds on the size of CFGs for specific finite languages
)

allows to show very easily an exponential lower bound for CFGs.
Let $G$ a grammar in Chomsky Normal Form for $L_n$.
For every word $w\in \{0,1\}^n$ there exists at least one non-terminal $A(w)$ accepting a subword $s(w)$ of $ww$ having length between $n/2$ and $n$. Let $p(w)$ be a position in $ww$ where this subword occurs. There are at least $n/2$ bits common to all words $w,w'$ such that $A(w)=A(w')$ and $p(w)=p(w')$. Consequently, there can be at most $2^{n/2}$ words that have the same $A(w)$ and $p(w)$. Hence there are at least $2^{\Theta(n)}$ non-terminals.

Furthermore, the PDA can be converted into a CFG in CNF, of polynomial size so this also gives the $2^{\Theta(n)}$ bound on the state complexity of $L_n$.


Is Eulerian Path (or Eulerian Cycle) definable in Monadic Second Order Logic? Does there exist a monadic second order logic formula which is satisfied by a graph if and only if it has an Eulerian path (or Eulerian cycle).

I am looking for properties of graphs which are polynomial time testable but cannot be defined in MSO. I am more inclined to examples of properties from standard textbooks as it is meant for a CS (engineering) crowd and not a CS theory crowd.

Parity cannot be expressed in MSOL (see for instance http://www.cs.technion.ac.il/~janos/COURSES/236331-15/Lec-1.pdf), but connectedness Yes. Using instead $C_2$MSOL, one can express the existence of an eulerian cycle by using the equivalent characterisation : connected and every vertex has degree even.


Fewest number of gates for Multiplication What is the best result for the number of gates in a circuit multiplying two n-bit integers?

The obvious method generates $\theta(n^2)$ gates. There are better approaches with $\theta(n\log n \log\log n)$ and $\theta(n\log n2^{\log^*(n)})$ gates.

I could not find any Boolean circuit family which can handle multiplication with $n\log n$ gates. I wonder if such a family of circuits exists.

Below is a detailed 2008 survey that covers top theoretical algorithms for multiplication, including the ones discussed in the comments to your question (including the Schönhage–Strassen algorithm and the $O(n\log n \, 2^{\log^* n})$ Fuerer algorithm, see page 335 of survey). However, implementation is a different matter and some of these algorithms may not be considered practical; the survey does not cover practical implementations. Although the survey includes algorithms for polynomials, power series, real numbers, and 2-adic numbers, integers are a special case of these (see Figure 1 on page 336).

Fast Multiplication And Its Applications, Bernstein (Algorithmic Number Theory / MSRI Publications / Volume 44, 2008)


Lower bound of the time complexity of heap building A lower bound of the needed number of comparision to build a heap is given by GASTON H. GONNET and J. IAN MUNRO as following

  THEOREM 4. $1.3644... n + O(lg n)$ comparisons are necessary, not only in the worst
  case, but also on the average to create a heap on n elements.

  Proof - A reasonably straightforward enumeration shows that there are $H(n)=
n !/\prod t_i$ valid heaps on a set on n numbers where $t_i$ is the size of the heap rooted at
  node $i$. A lower bound on the average number of comparisons required to permit one
  of $n!$ possible input sequences to one of these orders is $$\lg(n!/H(n))=\sum \lg t_i.$$

I understand how the number of valid heap is calculated. But I don't know information theory so I can't see how the last equation is the lower bound. Is there any theorem or book I can check to see how this works?

It is essentially using decision tree model to obtain the lower-bound. There are $n!/H(n)$ leafs in the decision tree, it is a binary tree, therefore the height of the tree is at least $\lg (n!/H(n))$.


Minimum Spanning tree on a complete "random" graph Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)$ is an exponential distribution.

Problem

What is the distribution of weight of the minimum spanning tree of the above graph?

Note : If $ X_1 \sim exp(\lambda_1)$ and $X_2 \sim exp(\lambda_2)$, then $min(X_1, X_2) \sim exp(\lambda_1+\lambda_2)$

Let's consider a general model in which $L_n(\mu)$ is the (random) length of an MST on $K_n$, where the weight of each edge is sampled independently from a probability distribution $\mu$. When $\mu$ is uniform on $[0,1]$, Frieze showed that $\lim_{n \to \infty} \mathbb{E}[L_n(\mu)] = \sum_{k\ge1}{\frac{1}{k^3}} = \zeta(3)$. Steele showed that for a $\mu$ with CDF $F$ which is differentiable from the right at $0$, this same limit is $\zeta(3)/F'(0)$. In particular, for $\mu$ an exponential distribution with parameter $1$, the expectation is once again $\zeta(3)$ in the limit.

It follows from general results that $L_n(\mu)$ is tightly concentrated around the mean. For example, in his survey McDiarmid shows how to use Talagrand's inequality to prove that, in the case of $\mu$ uniform on $[0,1]$, for any $t$ there exists a $\delta(t)$ such that $\Pr[|L_n(\mu) - \zeta(3)| > t] < e^{-\delta(t) n}$. I am fairly certain that the argument extends to the case of an exponential random variable.

Central limit theorems are also available. Janson proved that $\sqrt{n}(L_n(\mu) - \zeta(3))$ converges in distribution to a Gaussian with mean $0$ and constant variance. (The constant was computed exactly by Wastlund.) This is again shown for uniform $\mu$, but I think it should extend to exponential.

BTW, Steele's result is basically a reduction to the uniform case. Say $\mu$ has a continuous CDF $F$. Then, if $X$ is distributed according to $\mu$, $F(X)$ is uniform on $(0,1)$, and, moreover, $F$ is a monotone function. So, if you apply $F$ to the random weights of your graph, you don't change the MST, and you change the weights to be uniform. The other key observation is that all weights in the MST will be fairly small, so you only really care about the behavior of $F$ close to $0$.


Applications of duality We have recently covered linear programming and I am comfortable with the weak and strong duality theorems.  However, I don't understand what the applications of duality are that are specific to TCS.  Mike Spivey's blog post gives some interesting examples of some nice properties of duality but I was wondering if there are algorithmic advances, for example,  that come from understanding duality or anything more CS related.

Yup. Everything follows from duality. (I am only half joking).
A partial list:

Boosting

The Hard-Core Lemma

Online Learning

The ability to actually solve LPs efficiently

A large fraction of approximation algorithms results.

Much more

To develop algorithms, you often need a constructive or algorithmic version of the duality theorem (which is essentially equivalent to Von-Neumman's min-max theorem in game theory -- the applications in game theory are also huge). This is essentially what the multiplicative weights algorithm is. See Arora/Hazan/Kale for the best survey on this topic: http://www.satyenkale.com/papers/mw-survey.pdf


Intersection of two deterministic parity automata Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the transition function $\delta_i : Q_i \times \Sigma \rightarrow Q_i$, the initial state $q_{0i}$ in $Q_i$, and the coloring function $c_i : Q_i \rightarrow \mathbb{N}$, with $i \in\{0,1\}$.

How is the intersection of two deterministic parity automata formally defined? In particular, how are the coloring functions combined?

The following paper:
http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf
shows that the intersection (and union) of deterministic parity automata may involve an exponential blowup.

Thus, you cannot do much better than converting to nondeterministic Buchi automata, and taking the intersection there (and determinizing back to parity).


Necessary condition for a graph to be Non-Hamiltonian Let us denote the edges incident on vertices of valence 2 as "required" as these edges has to be covered by a Hamiltonian circuit, if one exists on that (undirected) graph. Given a graph on which a proper subset of the "required" edges along with two edges incident on a vertex of valency $\geq 3$ form a cycle, can anything related to the Hamiltonicity of the graph be claimed? A few basic rules for the existence of Hamiltonian Cycles is listed here: http://www.mit.edu/~miforbes/ham_cycle.pdf  Can rule (4) be extended in any way to answer this query?

Asking whether a graph is non-Hamiltonian is CoNP-Complete so it is doubtful that such an algorithm exists.

If you are satisfied with a heuristic that provides a certificates of non-Hamiltonicity, see Bondy and Murty's book (page 53) for a sufficient, but not necessary, condition for non-Hamiltonicity:  If $G$ is Hamiltonian then, for every nonempty subset, $S$, of $V$:

$$ \omega(G - S) \le |S| $$

Where $\omega(G - S)$ is the number of connected components left in $G$ after removing the vertices in $S$.  A simple counterexample for the converse is the peterson graph: It passes the above test but is not Hamiltonian.


What language feature allows programs to manipulate themselves? I am busy researching different languages just for some theoretical knowledge and came across programs that manipulate themselves. What language feature is used for this?


Complexity of counting integer roots of multivariate polynomials in a polyhedron? Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials  in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total degree fixed and we only look at integer roots in a bounded polyhedron?

The decision version of this problem is obviously in $\mathsf{NP}$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $x \in [0, \gamma]$ such that $x^2 \cong \alpha \mod \beta$ (the input here is the triple $(\alpha,\beta,\gamma)$) is NP-complete, which is only one variable and degree 2. I haven't checked the details in a while, but I'm pretty sure their reduction is parsimonious; if so, the counting version you ask about will be $\mathsf{\# P}$-complete as well.


Maximal classes for which largest independent set can be found in polynomial time? The ISGCI lists over 1100 classes of graphs.  For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes.  I would like to compile a list of maximal IS-easy classes.  These classes together form the boundary of (known) tractability for this problem.

Since one can just add a finite number of graphs to any infinite IS-easy class without affecting tractability, some restrictions are in order.  Let's restrict the classes to those that are hereditary (closed under taking of induced subgraphs, or equivalently, defined by a set of excluded induced subgraphs).  Moreover, let's consider only those families that are X-free for a set X with a small description.  There might are also be infinite ascending chains of tractable classes (such as $(P,\text{star}_{1,2,k})$-free and the classes described by David Eppstein below), but let's restrict attention to classes that have actually been proved to be IS-easy.

Here are the ones I know of:

perfect graphs
$(P,\text{star}_{1,2,5})$-free
$(K_{3,3}-e, P_5)$-free
co-Meyniel
nearly bipartite
chair-free
($P_5$,cricket)-free
$(P_5,K_{n,n})$-free (for any fixed $n$)
$(P_5, X_{82}, X_{83})$-free

  Are other such maximal classes known?

Edit: See also a related question asked by Yaroslav Bulatov dealing with classes defined by excluded minors what is easy for minor-excluded graphs? and see Global properties of hereditary classes? for a more general question I asked previously about hereditary classes.

As Jukka Suomela points out in comments, the minor-excluded case is also interesting (and would make an interesting question), but this is not the focus here.

To avoid David's example, a maximal class should also be definable as the X-free graphs, where not every graph in X has an independent vertex.

Classes given in answers below:

apple-free (suggested by Standa Živný)
($P_5$,house)-free (suggested by David Eppstein)
($K_2 \cup$ claw)-free (suggested by David Eppstein)

Added 2013-10-09: the recent result by Lokshtanov, Vatshelle and Villanger, mentioned by Martin Vatshelle in an answer, supersedes some of the previously known maximal classes.

In particular, $P_5$-free being IS-easy subsumes ($P_5$,cricket)-free,
($P_5$,$K_{n,n}$)-free,
($P_5$,$X_{82}$,$X_{83}$)-free, and
($P_5$,house)-free
all being IS-easy.

This means that all the hereditary graph classes defined by a single forbidden induced subgraph with up to five vertices can now be definitively classified as IS-easy or not IS-easy.

Unfortunately the proof that $P_5$-free graphs form an IS-easy class does not seem to work for $P_6$-free graphs, so the next frontier is to classify all the hereditary graph classes defined by a single six-vertex graph.

I remain especially interested in IS-easy classes of the form $X$-free for some collection $X$ of graphs with infinitely many isomorphism classes, yet where $Y$-free is not IS-easy for any $Y \subset X$.

An interesting paper to look at might be:

A. Brandstadt, V. V. Lozin, R. Mosca: Independent Sets of Maximum Weight in Apple-Free Graphs, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. doi:10.1137/090750822

The infinite class of apples is defined as cycles C_k, k>=5, each with a stalk.

You don't mention whether your notion of IS-easiness includes the weighted IS problem. Chair-free graphs (aka fork-free graphs) are known to be IS-easy:

V. E. Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics 135 (1-3) (2004) 3–16. doi:10.1016/S0166-218X(02)00290-1

The tractability of the weighted case is a non-trivial extension, see:

V. V. Lozin, M. Milanic: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi:10.1016/j.jda.2008.04.001

Are there any other (interesting) classes where the weighted IS problem is significantly more difficult/intractable/open than the unweighted case?


Simple Bisimulation algorithm Is there a simple algorithm to calculate the maximal bisimulation relation of a graph/two graphs?
With simple i mean very easy implementation, complexity is not that important for us in this stage.

The coarsest bisimulation has a well known greatest fixed point characterisation. This greatest fixed point characterisation gives you a simple algorithm to calculate bisimulation quotients. There are quite a few immediate improvements you can make to this algorithm. A reference that contains most of these details is Joost Pieter Katoen's lecture on bisimulation minimization. If you need more detail, I suggest looking at the book

  Principles of Model Checking, Christel Baier and Joost-Pieter Katoen.


Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm EDIT: I'm sorry if this question belongs more to cs.SE, I've had a dilemma about where to put it. Please let me know if it's inappropriate.

I'm currently implementing the Vertex Cover problem solving algorithm by aforementioned Authors (Paper: PDF).

I'm having a bit of trouble understanding the inner workings of the Struction operation.

The general idea is as follows:

$v_0$ is a vertex in $G=(V,E)$ (original graph) with a set of neighbours: $\{v_1, v_2, ..., v_p\}$. $G\prime$ is obtained by applying struction to $v_0$ in $G$.
Remove vertices $\{v_0, v_1, ..., v_p\}$ and introduce a vertex $v_{ij}$ for each $(v_{i}, v_{j}) \notin E $ in $G$, where $0 \lt i \lt j \leq p$.
Add an edge $(v_{ir}, v_{js})$ if $i=j$ and $(v_r, v_s) \in E$ in $G$.
Add an edge $(v_{ir}, v_{js})$ if $i \neq j$.
$\forall_{u \in \setminus \{v_0, v_1, ..., v_p\}}$ add the edge $(v_{ij}, u)$ if $(v_i,u) \in E$ or $(v_j,u) \in E$.

My main issue occurs when applying struction to $v_1$ in the following graph.

(It's the same one as in the paper, only the numbering is different.)

After creating the supplementary vertices for anti-edges within the removed set, I'm ending up with $v_{24}$ and $v_{34}$.

At this point, I find the notation of $v_{ir}$ and $v_{js}$ extremely misleading- up to the point of not being able to grasp the intricacies.

So far (using simplistic logic as a substitution for what is written in the paper) I have been able to understand that in step 4, we search for edges adjacent to each of the vertices comprising each of the supplementary vertices added in step 2 and connect them appropriately, ending up with the following:

($v_{24}$ is 10, $v_{34}$ is 11.)

But how should I understand in 'semi-human' terms what is going on in step 3, when $i=j$?

I get that when two supplementary vertices are connected to common neighbors, they should be inter-connected as well, e.g. $v_{24}$ and $v_{34}$ are both connected to ${v_8}$ and $v_{9}$.

Is that a correct assumption?

How can I picture the relationship between $i$, $j$, $r$ and $s$ (especially in the context of $v_{ir}$, $v_{js}$)?

I can imagine implementing it in a separate pass of a loop over the supplementary vertices - but the paper clearly indicates that it's feasible to do step 3 and step 4 in one pass.

Would anybody be so kind to break this down a little bit for me?

I'll try to track myself what I have been able to establish so far as an empirically working solution.

  Remove vertices {v0,v1,...,vp} and introduce a vertex vij for each (vi,vj)∉E in G, where 0

It is practical to have a function $lookup(x)$ for the supplementary vertices at your disposal, such that $lookup(i) = \{ v_{ij}| j: (v_i, v_j) \notin E\}$.

  Add an edge (vir,vjs) if i=j and (vr,vs)∈E in G.

In practice, each new supplementary vertex $v_{ij}$  in $G\prime=(V\prime, E\prime)$ must be connected to every supplementary vertex $v_{rs} \in lookup(i) \cup lookup(j)$ such that $r \neq i \land s \neq j$.

  Add an edge (vir,vjs) if i≠j.

This is the more straightforward case- for each supplementary vertex $v_{ij}$, and every edge $e_1=(v_i, v_r), e_2=(v_j, v_r); e_1,e_2 \in E$, create edge $e\prime=(v_{ij}, v_r); e\prime \in E\prime$.
∀u∈∖{v0,v1,...,vp} add the edge (vij,u) if (vi,u)∈E or (vj,u)∈E.

Result:

Still, any review of the correctness of my musings or guidance as to how to interpret and adhere to the original paper better is much appreciated!


An upper bound over the number of bipolar orientations for a regular graph Given a $k$-regular graph $G$, the number of acyclic orientations $Acy(G)$ is $\chi(-1)$ where $\chi$ is the chromatic polynomial of $G$. How many bipolar orientations does $G$ have?

Is there an upper bound for it? I assume it should be exponentially lower than $Acy(G)$ but didn't succeed in finding a known result connecting these two numbers.

It is not always lower than the number of acyclic orientations by any factor, let alone an exponential one. In particular, in a complete graph, there are $n!$ acyclic orientations, all of which are bipolar.


How much larger than the relaxation time can the mixing time be? The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer.

Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite state space. The relaxation time $t_{\mathrm{rel}}$ is the reciprocal of the absolute spectral gap. The $\epsilon$-mixing time $t_{\mathrm{mix}}(\epsilon)$ is the shortest time in which, regardless of any initialization, the state becomes $\epsilon$-close to the stationary distribution in the total variation sense. The two are related as:

  Levin-Peres-Wilmer (Theorem 12.3, 12.4)
  $$(t_{\mathrm{rel}}-1)\log\frac{1}{2\epsilon}\leq t_{\mathrm{mix}}(\epsilon)\leq t_{\mathrm{rel}}\log\frac{1}{\epsilon\min_x\pi(x)}~,$$
  where $\min_x\pi(x)$ is the smallest atom of the stationary distribution.

If the Markov chain is a random walk on a 3-regular expander graph, then $t_{\mathrm{rel}}$ is a constant, but $t_{\mathrm{mix}} = \Theta(\log n)$ if the graph has $n$ vertices. Thus, the upper bound here better describes the behavior of the mixing time relative to the relaxation time, since $\pi(x) = \frac 1n$ for all $x.$

My question is: How large can the ratio $\frac{t_{\mathrm{mix}}(1/8)}{t_{\mathrm{rel}}}$ be? From above theorem, it is at most $\log\frac{8}{\min_x\pi(x)},$ but can it indeed be as large as this when $\min_x \pi(x)$ may be very very tiny? I conjecture that

$$\frac{t_{\mathrm{mix}}(1/8)}{t_{\mathrm{rel}}}\leq O(\log n)~.$$

Any proofs or counterexamples?

This paper shows that $t_{\mathrm{mix}} = O(kt_{\mathrm{rel}}\log t_{\mathrm{rel}})$ for all Markov chains and that $t_{\mathrm{mix}} = O(kt_{\mathrm{rel}})$ for reversible chains. The conjecture in the question is false since it's shown that $t_{\mathrm{mix}}$ can be as large as $kt_{\mathrm{rel}}.$

http://arxiv.org/abs/1310.8021


Average-case tautologies/contradictions, beyond the random k-CNF model It is well known that random $ k $-CNF formulas over $ n $ variables with $ cn $ clauses are unsatisfiable (i.e. they are contradictions) with high probability, for sufficiently large constant $ c $. Thus, random $ k $-CNF formulas (for $ c $ large enough) constitute a natural distribution over unsatisfiable Boolean formulas (or dually, over tautologies, i.e. negations of contradictions). This distribution has been studied extensively.

My question is the following: are there any other established distributions over propositional tautologies or contradictions, that can be considered as capturing the "average-case" of tautologies or unsatisfiable formulas? Have these distributions been intensively studied?

Paul Beame has two papers (with various coauthors) where the resolution complexity of certain distributions of random formulas are studied. These formulas arise by expressing properties, such as k-colorability or having independent sets of size k, of random graphs from the usual distribution $G(n,p)$. Here are the links:

Paul Beame, Russell Impagliazzo, and Ashish Sabharwal. The resolution complexity of independent sets and vertex covers in random graphs. Computational Complexity, 16(3):245-297, 2007.

Paul Beame, Joe Culberson, David Mitchell, and Cristopher Moore. The resolution complexity of random graph k-colorability. Discrete Applied Mathematics, 153:25-47, 2005.


Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality? If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave.  Clearly in the worst case you cannot upper bound $\textbf{E}[f(x)]$ in terms of $f(\textbf{E}[x])$ for a convex $f$, but is there a bound that goes in this direction if $f$ is convex but "not too convex"?  Is there some standard bound that  gives conditions on a convex function $f$ (and possibly the distribution as well, if necessary) that would allow you to conclude that $\textbf{E}[f(x)] \le \varphi(f)f(\textbf{E}[x])$, where $\varphi(f)$ is some function of the curvature/degree of convexity of $f$?  Something akin to a Lipschitz condition, perhaps?

EDIT: original version missed an absolute value.  sorry!!

Hi Ian.  I will briefly outline two sample inequalities, one using a Lipschitz bound, the other using a bound on the second derivative, and then discuss some difficulties in this problem.  Although I'm being redundant, since an approach using one derivative explains what happens with more derivatives (via Taylor), it turns out that the second derivative version is quite nice.

First, with a Lipschitz bound: simply re-work the standard Jensen inequality.  The same trick applies: compute the Taylor expansion at the expected value.

Specifically, Let $X$ have corresponding measure $\mu$, and set $m := \textrm E(x)$.
If $f$ has Lipschitz constant $L$, then by Taylor's theorem

$$
f(x) = f(m) + f'(z)(x-m) \leq f(m) + L|x-m|,
$$

where $z \in [m, x]$ (note that $x\leq m$ and $x> m$ are possible). Using this and re-working the Jensen proof (I am paranoid and checked that the standard one is indeed on wikipedia),

\begin{align}
\operatorname{E}(f(X)) & =
\int f(x) \, d\mu(x)
\leq f(m) \int d\mu(x) + L\int |x-m| \, d\mu(x) \\[6pt]
& = f(\operatorname{E}(X)) + L \operatorname{E} (|X-\operatorname{E}(X)|).
\end{align}

Now, suppose $|f''(x)| \leq \lambda$.  In this case,

\begin{align}
f(x) & = f(m) + f'(m)(x-m) + f''(z) \frac{(x-m)^2} 2 \\[6pt]
& \leq f(m) + f'(m)(x-m) + \lambda \frac{(x-m)^2} 2,
\end{align}

and so

\begin{align}
\operatorname{E}(f(X))
& \leq f(m) + f'(m)(\operatorname{E}(X) - m) + \frac {\lambda \operatorname{E}((X-m)^2)}{2} \\[6pt]
& = f(\operatorname{E}(X)) + \frac {\lambda \operatorname{Var}(X)}2.
\end{align}

I'd like to briefly mention a few things.  Sorry if they are obvious.

One is that, you can't merely say "wlog $\operatorname{E}(X) = 0$" by shifting the distribution, because you are changing the relationship between $f$ and $\mu$.

Next is that the bound must depend on the distribution in some way.  To see this, imagine that $X \sim \textrm{Gaussian}(0, \sigma^2)$ and $f(x) = x^2$.  Whatever the value of $\sigma$, you still get $f(\operatorname{E}(X)) = f(0) = 0$.  On the other hand, $\operatorname{E}(f(X)) = \operatorname{E}(X^2) = \sigma^2$.  Thus, by changing $\sigma$, you can make the gap between the two quantities arbitrary!  Intuitively, more mass is pushed away from the mean, and thus, for any strictly convex function, $\operatorname{E} (f(X))$ will increase.

Lastly, I don't see how to get a multiplicative bound like you suggest.  Everything I have used in this post is standard: Taylor's theorem and derivative bounds are bread&butter in statistics bounds, and they automatically give additive, not multiplicative errors.

I will think about it though, and post something.  Vague intuition is it will need very strenous conditions on both the function and the distribution, and that the additive bound is actually at the heart of it.


Can you assign a type to any term of the λEA-calculus? The untyped language of System-F and similar is the λ-calculus. That language has terms that can't be typed on System-F, λx.(x x) λx.(x x) being the most obvious example. The λEA-calculus, as described here, and its variants, has an interesting property that all stratified terms of the untyped language are total and strongly normalizing. That raises 2 questions:

Does that mean that, for all terms of λEA, there is a valid type derivation?
Is this a common phenomena, i.e., are there other systems with this same characteristic, or is it something particular of linear logic based proof languages?

For question 1, the answer is no, and is no for almost any type discipline (except certain intersection types): the fact that a term is (strongly or weakly) normalizable does not imply in general that it is typable.  Typability implies termination, not the other way around.

The specific case of of $\lambda EA$, however, brings up another issue which may be the object of confusion, so let me discuss it.  Let us start with a counter-example for your question 1: the term
$$[M]_{\lambda x.N=y,z}$$
is not typable. This is because the construct $[M]_{P=y,z}$ represents contraction of variables $y$ and $z$ in $M$ (i.e., $y$ and $z$ are morally equated in $M$ and $P$ is "plugged in" on them), so for such a term to be typable $P$ must have type $!A$, i.e., it must be duplicable. Now, in my example, $P$ is an abstraction and can never receive type $!A$ (its type will always have the form $B\multimap C$).

There are many more examples like this in $\lambda EA$.  Intuitively, typability ensures more than termination: it also avoids "clashes", i.e., a term may stop its reduction because it "gets stuck".  Typically, this happens when a destructor of a certain form meets a constructor of a different form (e.g., a head::tail pattern that is matched, i don't know, against a binary tree).  For example, in the above case, the constructor matching the destructor $[M]_{P=y,z}$ is $!(-)$, not $\lambda$, i.e., if $P$ ever reduces to something with a constructor at the root, one expects $P=!(N)[\ldots]$, not $P=\lambda x.N$.

In truth, typability is orthogonal to termination. There may be a misunderstanding about this because, in the context of the pure $\lambda$-calculus, which is the one used for showcasing type disciplines to a beginner, there are no "clashes" (there is only one constructor and one destructor), so clash-avoidance is completely hidden and only termination shows up.  But as soon as one spices things up a bit, adding more constructors and destructors, the distinction between termination and clash-avoidance arises, and types are seen to actually ensure the latter more than the former (for instance, PCF is a typed language which does not terminate, as is every real-world functional programming language).  Mor precisely, types always ensure clash-avoidance and might, in many cases of interest, also ensure termination.

Regarding your question 2, I am guessing that by "same characteristic" you mean the fact that the untyped calculus terminates?  In this case, it may not be very common for the programming languages one considers in practice, but it is not very hard to come up with examples, which must not necessarily have anything to do with linearity (for instance: consider any programming language with no gotos and having a distiction between "for" and "while" loops; eliminate while loops; the language you obtain terminates, whether you have types or not). The interest of $\lambda EA$ is not that it terminates but that it does so with an interesting complexity bound (elementary).


Reasons to believe $P \ne NP \cap coNP$ (or not) It seems that many people believe that $P \ne NP \cap coNP$, in part because they believe that factoring is not polytime solvable. (Shiva Kintali has listed a few other candidate problems here).

On the other hand, Grötschel, Lovász, and Schrijver have written that "many people believe that $P=NP\cap coNP$." This quote can be found in Geometric Algorithms and Combinatorial Optimization, and Schrijver makes similar statements in Combinatorial Optimization: Polyhedra and Efficiency. This picture makes it clear where Jack Edmonds stands on the issue.

What evidence supports a belief in $P\ne NP\cap coNP$? Or to support $P=NP\cap coNP$?

Theorem 3.1 of One-Way Permutations and Self-Witnessing Languages C. Homan and M. Thakur, Journal of Computer and System Sciences, 67(3):608-622, November 2003. [ as .pdf ] states that $P≠UP∩coUP$ if and only if ("worst-case") one-way permutations exist. Theorem 3.2 recalls 10 further hypotheses that have been shown to be equivalent to $P≠UP∩coUP$.

Also, we have strong reason to conjecture that $UP \ne NP$. Therefore, the above theorem and the conjecture result in a strong reason to believe that $P \ne NP ∩ coNP$.

Disclaimer: I moved Mohammad Al-Turkistany's edit of my answer to this community wiki answer. He believes that it perfectly answers the question since the existence of one-way permutations is widely believed. I myself haven't yet sufficiently understood the difference between "worst-case" and "average-case" one-way functions to claim that it really answers the question.


Computational hardness of "real" computer programs I have often heard it said that you cannot write a program to catch bugs in a web browser, or word-processor, or operating system, because of Rice's Theorem: any semantical property for a Turing-complete language is undecidable.

However, I am not sure to what extent this applies to real-world program likes operating systems. Do these types of programs need the full strength of Turing completeness? Are there simpler models of computation (such as PR) in which these applications could be written? If so, to what extent does this allow decidability of program correctness?

You certainly can write programs which catch bugs -- there is a large and active community of people who write programs to do exactly that. However, what Rice's theorem prevents you from doing is to write bug-catchers which are both sound and complete (i.e., catch all bugs of a certain class with no false positives).

That said, naive restrictions on the model of computation don't actually help you very much in improving the practicality of program analysis. The reason is that you can get programs which do "almost the same thing" by turning while loops

while P do
   C

into for-loops with a big iteration constant:

for i = 0 to BIGNUM do
  if P then
    C
  else
    break

Now this program does not even need the full strength of primitive recursive (since the for-loop can be macro-expanded into a huge nested if-then-else statement), but in most practical cases it will behave just the same as before. Note that it does help decidability in theory -- the program is total, so you can answer questions by running the program and seeing what happens. This is not  what we actually want, which is to get answers faster than running the program -- the artificial termination introduced doesn't actually help program analysis in practice, since bugs occur because of errors in the real program logic, and we haven't touched that at all.

Furthermore, adding abstraction facilities to a programming language can radically worsen the complexity of the analysis problem, while making it easier to verify programs in practice. For example, proving termination of the simply-typed lambda calculus with natural numbers requires induction up to $\epsilon_0$, but by adding type polymorphism you get System F, whose termination proof as strong as the consistency of second-order arithmetic. Yet, in practice programs written in F are much easier to verify, because the modularity properties of second-order quantification make writing structured programs and correctness proofs much easier.


Finding vertex separator such that the induced subgraph has minimal number of edges My problem is related to edge and vertex cuts with a little twist.
Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that the induced subgraph $G[S]$ has minimal number of edges.
Consider the following graph:

The red edges are the minimal edge cut. The blue vertices are the minimal vertex cut. The green vertices are a vertex cut such that the induced subgraph has the least number of edges. I try to find the green cut. In fact, the number of vertices is not required to be minimal as long as the number of edges in $G[S]$ are minimal.
Is there an algorithm in $P$ to solve this problem? Do you have an idea how to approach the problem?

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is known NP-complete [C. deFigueiredo, S. Klein, "NP-completeness of multipartite cutset testing", Congr. Numer. 119 (1996)
217–222, as cited by Guantao Chen and Xingxing Yu, "A note on fragile graphs", Discrete Math. 2002, https://doi.org/10.1016/S0012-365X(01)00226-6]. So your problem is hard even in the special case of zero edges.


Best Upper Bounds on SAT In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."

I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time complexity of the most efficient SAT solver?

In particular, is it conceivable to find a sub-exponential (yet super-polynomial) algorithm for SAT?

There are two kinds of "best" SAT solvers, one for theory, one for practice.
Theory

Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, "Improved Randomized Algorithms for 3-SAT", ISAAC 2010.

randomized $O(1.32113^n)$ for 3SAT.

Timon Hertli, Robin A. Moser, Dominik Scheder, "Improving PPSZ for 3-SAT using Critical Variables", 2011.

randomized $O(1.321^n)$ for 3SAT.

Konstantin Kutzkov, Dominik Scheder, "Using CSP To Improve Deterministic 3-SAT", 2010.

deterministic $O(1.439^n)$ for 3SAT.

Practice
Check SAT conference for competition results for each year.


Space requirements for solving True Quantified Boolean Formulas problem I came across this section on the wikipedia page for the TQBF solving problem, and just can't wrap my head about the fact that the space requirement is linear. Moreover, it does not provide any reference.

For a given QBF
$$Q_1x_1Q_2x_2...Q_nx_n\phi(x_1,x_2,...,x_n)$$

for each quantifier, the algorithm presented evaluates

$$ A = Q_2x_2...Q_nx_n\phi(0,x_2,...,x_n)$$
$$B = Q_2x_2...Q_nx_n\phi(1,x_2,...,x_n)$$

and returns $A\wedge B$ for $Q_1 = \forall$ and $A\lor B$ for $Q_1 = \exists$. The way I work it out the space should be $O(2^n)$ instead of $O(n + \log(n)) = O(n)$. When I solve a QBF on paper, I realize it is not exponential, so something must be terribly wrong with my analysis.

At each step, the new $A$ and $B$ have one quantifier less, but there are twice as many expressions. I assumed that would build up as
$$ 1: n$$
$$ 2 : (n-1) + (n-1) $$
$$ 3 : (n-2) + (n-2) + (n-2) + (n-2) $$
$$ \ldots $$
$$ k : 2^k (n-k) $$

which goes all the way up to $2^{n-1}$ before decreasing to zero. Can anyone provide a pointer on what I am doing wrong, or even better a good reference?

Thanks

The main difference between time and space is that you can reuse space that is not needed anymore.

If you return from the recursive call that evaluates $A$, you can reuse the space used by this computation to compute the value of $B$.  Because of this you only need to store one branch of the decision tree of the original QBF formula in memory, which gives you a linear space requirement.

This fact is explained quite well in standard introductory text books on Complexity Theory.  You can have a look into Sipser's Introduction to the Theory of Computation, for example. On page 332 (3rd edition) he explains the space requirement for SAT, of which QBF is a generalization.


Real number $p$ such that a $p$-coin makes the undecidable decidable This is an exercice from Arora & Barak, Chapter 7 :

  Describe a real number $p$ such that given a random coin that comes up
  "heads" with probability $p$, a Turing machine can decide an undecidable
  language in polynomial time.

This follows a discussion about the fact that if $p$ is efficiently computable, then it's no better than a $1/2$-coin.  But if $p$ can be anything, we get new powers.  I guess in this case the way to do is to recover the bits of $p$, but I can't think of a deterministic way to do so.

EDIT : based on comments, this question doesn't seem clear.  I'll rephrase it like this, based on my interpretation of 'decide' (if I'm wrong, please let me know):

  Describe a real number $p$ such that given a random coin that comes up
  "heads" with probability $p$, there exists an undecidable language $L$ and a Turing machine $M$ such that $M$ runs in polynomial time, and on input $x$, $M$ outputs $1$ if and only if $x \in L$.

Note that stated like this $M$ makes zero error.

I was also wondering how to solve this problem. Although the comments seem to suggest that the poster of the question has already solved the problem, I will write up a solution regardless in case anyone else is curious.

Some credit goes to Sidhanth Mohanty. He showed me this question because he was also interested in the solution, and he provided some crucial insights.

As discussed in the comments, we are considering probabilistic Turing machines, so we need only output the correct answer with probability, say, at least $2/3$.

Idea: Let $L$ be some undecidable language. Maybe we can encode the answers in the binary expansion of $p$. Establish a reasonable bijection $f \colon \mathbb{N} \to \{0,1\}^*$ and make the $i$-th bit in the binary expansion $p$ one if $f(i) \in L$ and zero if $f(i) \not\in L$. Now we hope to recover the binary expansion of $p$ by flipping the coin $t$ times, counting the number of heads $s$, and computing $s/t$.

Issue 1: This won't be polynomial time. Given some input $x \in \{0,1\}^*$, the index $f^{-1}(x)$ will be exponential in $|x|$, and determining the $f^{-1}(x)$-th bit of $p$ with high enough probability will take too long.

Fix: We get to choose what $L$ is, so we can make the elements in $L$ large in length.

Issue 2: At first it might seem like in order to determine the $i$-th bit of $p$, it's enough to read off the $i$-th bit of the binary expansion of $s/t$, hoping that $\vert s/t - p \vert < 2^{-i}$. However, this is not enough to guarantee that the $i$-th bit of $s/t$ is equal to the $i$-th bit of $p$. Suppose that $p$ is $0.1_2$ and that you're trying to determine the third bit of $p$. If $s/t$ is less than $p$ by any positive amount, which would occur roughly half the time, the third bit of $s/t$ could be a 1 rather than a 0. 1 Of course, we cannot actually have $p = 0.1_2$ since we’re assuming that $p$ is uncomputable by construction, but if $p$ were close to $0.1_2$ or any other value with a binary expansion that terminates, we would have a similar issue.

Fix: Note that if the $(j+1)$-th bit of $p$ is different from the $(j+2)$-th bit of $p$, then if we have $\vert s/t - p \vert < 2^{-(j+2)}$, the $i$-th bit of $s/t$ is indeed equal to the $i$-th bit of $p$ for all $1 \leq i \leq j$. This suggests that we can fix the issue by redefining $p$ to make lots of adjacent bits different in its binary expansion.

1Also, in this case, you would also have the issue that you couldn't distinguish $0.1_2$ and $0.0\overline{1}_2$.

Clean writeup:

Define $f\colon \mathbb{N} \to \{0, 1\}^*$ with $f(n)$ being $n$ written in binary with the leading $1$ removed. Let $H$ be your favorite undecidable language, e.g. let
$$
  H = \{x \in \{0,1\}^* : \text{ $x$ describes a Turing machine that halts on the empty string}\}.
$$
Then let $L$ be the undecidable language
$$
  L = \{1^{4^k} : f(k) \in H\}.
$$
Denote the binary expansion of $p$ as $0.p_1p_2p_3p_4p_5\ldots$. For every $i \in \mathbb{N}$, we choose
$$
  (p_{2i-1}, p_{2i}) =
  \begin{cases}
    (1, 0) & \text{if } f(i) \in H \\
    (0, 1) & \text{if } f(i) \not\in H.
  \end{cases}
$$

Our TM for deciding $L$ does the following on input $x \in \{0,1\}^*$:

If $x$ is not of the form $1^{4^k}$ for some $k \in \mathbb{N}$, reject. Otherwise, compute $k$.
Flip the coin $t = \lceil 3\cdot4^{2k+2}\ln(6)) \rceil$ times, counting the number of heads $s$.
Compute the $(2k-1)$-th bit of the binary expansion of $s/t$. Accept if it is one and reject if it is zero.

The runtime is $O(t) = O\left(\vert x \vert ^ 2 \right)$, which is polynomial time.

To prove correctness, note that $p_{2k-1}$ is one iff $1^{4^k} \in L$. Hence it is enough to prove that the $(2k-1)$-th bit of $s/t$ is equal to $p_{2k-1}$ with probability at least $2/3$. Since $p_{2k+1} \not= p_{2k+2}$, if $\lvert s/t - p \rvert < 2^{-2k-2}$, then for all $i \leq k$ we have that the $i$-th bit of $s/t$ is equal to $p_i$. In particular, if $\lvert s/t - p \rvert < 2^{-2k-2}$, then the algorithm outputs the correct answer.

The Chernoff bound in corollary 5 of this set of notes tells us that for any $\delta \in (0,1)$, we have
$$
  \operatorname{Pr}\left[\left\vert \frac{s}{t} - p \right\vert \geq \delta p \right] \leq 2\exp\left(-pt\delta^2/3\right).
$$
Setting $\delta$ to be $1/(2^{2k+2}p)$, we get
$$
\begin{align*}
  \operatorname{Pr}\left[\left\vert \frac{s}{t} - p \right\vert \geq \frac{1}{2^{2k+2}} \right]
  &\leq 2\exp\left(-\frac{t}{3 \cdot 4^{2k+2} p}\right) \\
  &\leq 2\exp\left(-\frac{3\cdot4^{2k+2}\ln(6)}{3 \cdot 4^{2k+2} p}\right) \\
  &= 2\exp\left(-\ln(6)/p\right) \\
  &< 2\exp\left(-\ln(6)\right) \\
  &= 1/3.
\end{align*}
$$
Thus $\operatorname{Pr}\left[\lvert s/t - p \rvert < 2^{-2k-2}\right] > 2/3$, so our algorithm is correct with probability at least $2/3$.


Tight examples for approximating the feedback vertex set problem There are several 2-approximation algorithms for the UNWEIGHTED feedback vertex set problem (FVS), which are summarized in [4]. Note that the reduction from vertex cover to FVS is approximation-preserving. Assuming Unique Game Conjecture, we cannot expect better algorithms. The question is:

Is there an unweighted graph on which some of the algorithm really reaches ratio 2?

[1] contains such a tight instance for weighted FVS.

Vineet Bafna and Piotr Berman and Toshihiro Fujito,
http://doi.org/10.1137/S0895480196305124;
Ann Becker and Dan
Geiger, http://doi.org/10.1016/0004-3702(95)00004-6;
Toshihiro
Fujito, http://doi.org/10.1016/0020-0190(96)00094-4;
Fabián A.
Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson,
http://doi.org/10.1016/S0167-6377(98)00021-2.

I think you can make the classical local ratio algorithm by Bafna et al. give a $2-o(1)$ approximation on the following family of graphs:

Take $G_n$ to be a $K_{n,n}$ (the complete bipertite graph with $n$ vertices on each side), and then delete a single edge.
The following shows that the algorithm might output all of the "blue" vertices ($2n-4$ in number) as the FVS approximation, while there's a much smaller FVS for $G_n$.

(notice there's no edge between the teal vertices).

The optimal FVS is contains $n-1$ vertices (take all of the vertices on the right, except the top one).

Now there are no semi-disjoint cycles, and the vertices degrees are as follows:

Blue / Purple vertices - degree $n$.
Teal vertices - degree $n-1$.

This means that the all of the blue/purple vertices will be inserted first into the stack at arbitrary order (the teal vertices enters the stack at the end and are the first to be deleted from $F$).

Assuming that the purple vertices will pushed after (and popped before) the blue ones, they will be removed from $F$ which will be updated to contain all of the blue vertices.

From this point on, no other vertex can be deleted from $F$ (otherwise there will be a cycle using the teal/purpule vertices), and the resulting $FVS$ has size $2n-4$.

This gives us a $\frac{2n-4}{n-1}=2-o(1)$ approximation ratio, hence showing the analysis is tight even for the unweighted case.


kmeans++ for arbitrary metric spaces and general potential function I was reading this popular paper "k-means++: The Advantages of Careful Seeding". It appeared in SODA 2007. Since this technique is the most popular clustering technique, I am hoping that my question can be answered.

I found two versions of the paper (which I find contradictory):

http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf
https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf

I have a problem with section 5 ("Generalization") of the paper. The section describes a generalization of the kmeans++ algorithm for an arbitrary metric space with a general potential function $ \Phi^{[\ell]} \equiv \sum_{x \in \mathcal{X}} min_{c \in \mathcal{C}} \| x-c\|^{\ell}$, where $||x-c||$ denotes the distance in any metric space, $\mathcal{X}$ is the data-set, and $\mathcal{C}$ is the center set of size $k$.

Consider Lemma 5.3, of the first version. It says that
-"For a cluster $A$, if we choose a point $p$ uniformly at random, then the expected cost of the cluster(with $p$ as a center) is at most $4 \cdot OPT(A)$".
Before stating this lemma, they explicitly say that this result is independent of the value of $\ell$.

However, a contradictory result is mentioned in lemma 5.1 of the second version, which says that
"For a cluster $A$, if we choose a point $p$ uniformly at random, then the expected cost of the cluster(with $p$ as a center) is at most $2^{\ell} \cdot OPT(A)$"

So far, I agree with the second version of the paper. However, it is possible that the first version came later with corrections. If the first version result is also correct, how to prove this result?

Note: Both these versions are highly cited and appear at the top in the google search. So I doubt if they are incorrect. Also, none of the versions mention anything about the corrections made in the paper.

Here's an example that suggests that the stronger claim in the earlier version (Lemma 5.3) is false.  I've only given a cursory look at the papers, so please check this carefully to make sure I am understanding correctly, thanks.

Consider a cluster $X$ consisting of a rooted star: a root $r$ and $n-1$ nodes $v_1,v_2,\ldots, v_{n-1}$ such that $d(r, v_i) = 1$ for each $i$, and $d(v_i, v_j) = 2$ for each $i, j$ with $i\ne j$.

$OPT$ takes the center to be $r$, at cost $\sum_{i=1}^{n-1} 1^\ell = n-1$.

But suppose the center $c$ is chosen at random. Then with probability $1-1/n$ the center is one of the $v_i$'s (not the root), and then the cost is $1+\sum_{j\ne i} 2^\ell \ge (n-1)2^\ell$.  So the expected cost is at least $(1-1/n) 2^\ell \,OPT$.

BTW, the published version of the manuscript appears to be here:

https://dl.acm.org/doi/abs/10.5555/1283383.1283494


Finding a cutting plane that splits a polyhedron evenly Say we have a polyhedron in standard form:

\begin{equation*}
\begin{array}{rl}
\mathbf{A}\mathbf{x} = \mathbf{b} \\\\
\mathbf{x} \ge 0
\end{array}
\end{equation*}

Are there any known methods for finding a hyperplane $\mathbf{d} \mathbf{x} +d_0= 0$ that splits the polyhedron in a way that the number of vertices on each side of the hyperplane is approximately the same?  (i.e. an algorithm that minimizes the absolute difference of vertex cardinalities on the two sides of the split).

Also, are there any known results regarding the complexity of this problem?

Addendum: Restricting the types of cuts:

Here is a variation of the original problem with the hope that it is easier to solve than the original one:

Is there a way to efficiently compute or estimate for which coordinate $i$ a hyperplane of the form $d_ix_i + d_0 = 0$ would yield the lowest absolute difference of vertex cardinalities on both sides of the split? By efficient I mean anything more efficient than the exhaustive enumeration of vertex cardinalities for all  possible such splits.

Note: After a few days of little progress, I posted this question at MathOverflow too.

I can't remember the analytic way to do this!

But this a classical problem for Genetic Programming! If you are familiar with it you can use a normalized vectors in the center of the polyhedron that describes the cutting plane.

So your population is a set of [x,y,z,...] normalized vectors and as fitting function you use the difference between the 2 split volumes!

So, if the difference tends to zero more "fit" is your vector/plane!


Completeness of the extension of first order logic with least fixed point order operator Is there any result about the extension of first order logic with least fixed point operator, being complete (as logic in general on infinite structures too) or not? In other words does the Goedel completeness theorem of first order logic extent to such FO-LFP logic ?

FO-LFP is neither complete (its valid sentences cannot be described by a recursively presented proof system) nor compact (there is an unsatisfiable set of sentences all of whose finite subsets are satisfiable). The basic argument is given in Denis’s answer so I won’t repeat it here, but let me instead point out that as a general principle due to Per Lindström, when extending first-order logic, some important property has to give way.

The setup is that we consider logics given by a satisfaction predicate $M\models\phi$ between ordinary first-order models, and an abstract set of sentences, that satisfy a handful of natural technical conditions.

The first Lindström’s theorem states that no proper extension of FO can simultaneously satisfy

(Löwenheim–Skolem) If a sentence has a model, it has an at most countable model.
(Compacteness) If $T$ is a set of sentences such that every finite subset of $T$ has a model, then $T$ has a model.

The second Lindström’s theorem states that no proper extension of FO with effectively presented syntax can satisfy

The Löwenheim–Skolem property as above.
(Completeness) The set of valid sentences can be described by an effectively axiomatized proof system (i.e., it is recursively enumerable).

For example, FO+TC has the Löwenheim–Skolem property (as it is a fragment of $L_{\omega_1,\omega}$), hence it can be neither complete nor compact, and a fortiori the same applies to all extensions of FO+TC such as fixed-point logics. (This is of course easy to show directly.)


Complexity of finding automorphism group of code What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code?
Is there better bound on complexity if structure of code is known for eg. Reed Muller codes, goppa codes, quasi-cyclic codes, hadamard etc?

Here is reminder for definition of aut group for code generated by Generator matrix G

$aut({G})= (A,P) :AGP=G$

By taking direct sum of codes (given their two generator matrices $G_1, G_2$, consider the block matrix $G_1 \oplus G_2 = \begin{bmatrix} G_1 & 0 \\ 0 & G_2 \end{bmatrix}$), finding the automorphism group is at least as hard as testing isomorphism of codes (also called code equivalence). The current best upper bound for testing equivalence of linear codes is $2^{O(n)}$ (see Babai-Codenotti-G-Qiao, SODA '11), and this algorithm can in fact give you generators for the automorphism group.

(For the above reduction I'm assuming that each code is indecomposable in the sense that neither code is itself a nontrivial direct sum, but I think this is true of (a) most/all codes people ever study and (b) most codes, ie a random code.)


Are there knot theoretic formulations of NP complete problems? Are there NP complete(or even NP-hard, or NP) problems that have good topological properties to study. Do NP problems have knot theoretic formulations? We know about #$P$ results about the Jones polynomial. Graph problems(embeddings?), specifically colourings of graphs can be seen to have nice knot theoretic properties. It is an open ended question, and any references for this topic appreciated.

You can take a look to:

Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac, and Aleksandar Chakarov. 2009. Tricolorable torus knots are NP-complete. In Proceedings of the 47th Annual Southeast Regional Conference (ACM-SE 47). ACM, New York, NY, USA, , Article 42 , 6 pages.

Abstract: This work presents a method for associating a class of constraint satisfaction problems to a three-dimensional knot. Given a knot, one can build a knot quandle, which is generally an infinite free algebra. The desired collection of problems is derived from the set of invariant relations over the knot quandle, applying theory that relates finite algebras to constraint satisfaction problems. This allows us to develop notions of tractable and NP-complete quandles and knots. In particular, we show that all tricolorable torus knots and all but at most 2 non-trivial knots with 10 or fewer crossings are NP-complete.

and also to its seminal report:

P. Golbus, R. W. McGrail, M. Merling, K. Ober, M. Sharac, and J. Wood. The class of constraint satisfaction problems over a knot. Technical Report number
BARD-CMSC-2008-01, Bard College, 2008.


Quicksort: compute the expected number of comparisons as a function of $M$ and $t$ I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at least discussion?

Problem description (see link for more context):

  Let $C_n$ be the number of comparisons made by quicksort to sort
  a random permutation of $\{1,\ldots,n\}$, when using the median of a
  sample of size $2t+1$ to perform the partitions and the recursive
  calls stop at subfiles of size $M\ge 2t+1$.  Both $M$ are $t$ are constants.
  Compute the expected value of $C_n$ [as a function of] $M$ and $t$.

I got a reply from the problem author, wanted to post the info here for reference:

Apparently the problem was solved by Pascal Hennequin in his PhD thesis. Chern and Hwang discuss the solution in Transitional behaviors of the average cost of quicksort with median-of-(2t+1).

I also found that googling quicksort "2t+1" yields the above paper :).


What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$? In [1] it is stated that

  "It remains an open question as to whether every function in $\#P$ has $TC^0$ circuits (although it is at least known that not all $\#P$ functions have DLogTime-uniform $TC^0$ circuits)."

$TC^0$ circuits generated by DLogTime functions does not contain $\#P$.
We don't know if $TC^0$ circuits generated by arbitrary functions does not contain $\#P$.

Is there anything known about the cases in between these two?
E.g. is it known if $TC^0$ circuits generated by $L$ does not contain $\#P$?

[1] Agarwal, Allender, and Datta, "On $TC^0$, $AC^0$, and Arithmetic Circuits"

This is an (interesting) open problem, as far as I know. Rahul Santhanam and I explicitly mention the problem of proving Permanent is not in LOGSPACE-uniform TC0 in our CCC'13 paper (On Medium-Uniformity and Circuit Lower Bounds).


Derive logitboost using the logistic loss function An additive model constructed using the exponential loss function

$$L(y, f (x)) = \exp(−yf (x))$$

gives   Adaboost. How can we derive the corresponding additive model (known as logitboost) using the logistic loss function

$$L(y, f (x)) = \log(1 + \exp(−yf (x)))$$

What steps I should take to do the above proof?

Originally, Logitboost was derived by Friedman, Hastie, and Tibshirani (paper) -- their algorithm internally used a numerical procedure, via Newtons method to solve a regression problem.

Later, Collins, Schapire, and Singer (paper) found an equivalent formulation, with a single-line modification from AdaBoost, setting
$$D(i) \propto \frac{1}{1+e^{y_i f_{t-1}(x_i)}}.$$

Schapire has a nice summary of boosting here, which also discusses Logitboost.


Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials? Arora and Barak define NP-completeness as the following:

"We say that a language $A \subseteq \{0, 1\}^∗$
is polynomial-time Karp reducible to a language
$B \subseteq \{0, 1\}^∗$
denoted by
$A \leq_p B$ if there is a polynomial-time computable function $f : \{0, 1\}^∗ \rightarrow \{0, 1\}^*$
such
that for every $x \in \{0, 1\}^∗$, $x \in A$ if and only if $f(x) \in B$.
We say that B is NP-hard if A $\leq_p$ B for every $A \in NP$. We say that B is
NP-complete if B is NP-hard and $B \in NP$."

However, something about this is not clear to me: if B is NP-hard, does that mean for all languages $L\in NP$, there is a single fixed polynomial $q$ such that the associated function $f$ is computable in time $q(n)$? Or does it mean for each language $L\in NP$, the function $f$ is computable in time $q_L$, where $q_L$ is a polynomial depending on the language. These polynomials $q_L$ can be arbitrarily large.

The latter. The former is impossible for NP-complete languages by the nondeterministic time hierarchy theorem: assume for contradiction that $B$ is a language computable in nondeterministic time $p(n)$ such that every NP language reduces to it in time $q(n)$. Then
$$\mathrm{NP}\subseteq\mathrm{NTIME}(q(n)+p(q(n)))
\subsetneq\mathrm{NTIME}((q(n)+p(q(n)))n)\subseteq\mathrm{NP},$$
a contradiction.

You asked more generally about NP-hard languages. Consider the language $B\in\mathrm{NEXP}$ defined as
$$B=\{M\#w:\text{$M$ is a clocked poly-time NTM and $M$ accepts $w$}\}.$$
It is clear that any NP-language $A$ reduces to $B$ in time $n+c_A$ for some constant $c_A$, namely $c_A=1+|M_A|$ where $M_A$ is a fixed NTM accepting $A$.

But in fact, every $A\in\mathrm{NP}$ reduces to $B$ in time $3n+c$ for some constant $c$ independent of $A$. The reduction function reads up to the first $c_A$ letters of the input, storing them in its state. If the input has length $\le c_A$, the reduction directly finds the result in a lookup table, and outputs one of two fixed inputs that make $B$ accept or reject as appropriate. Otherwise, it outputs the description of $M_A$, copies the first $c_A$ input letters from the internal state to the output, and proceeds to copy the rest of the input. The running time is thus bounded by
$$\begin{cases}n+c,&n\le c_A,\\c_A+2c_A+(n-c_A)\le3n,&n>c_A\end{cases}$$
for some absolute constant $c$ independent of $A$.


Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed? I'm wondering which is the approximation class of Minimum 0-1 Integer Programming if only non-negative integers are used. That is:

minimize $c^T \cdot x$,
with $x\in \{0,1\}^n$ and $c\in (\mathbb{Z}^*)^n$,
subject to $Ax \geq b$, where $A\in (\mathbb{Z}^*)^{m * n}$ and $b\in (\mathbb{Z}^*)^m$.

where $c^T$ is the transpose of vector $c$ and $\mathbb{Z}^*$ is the set of non-negative integers. Alternatively, $\mathbb{Z}^*$ could be replaced by the set of non-negative rationals, and we could force $b=(1,...,1)$ (it would be the same problem up to normalization).

If negative integers were allowed in $A$ and $b$, then this problem would be Minimum 0-1 Integer Programming, which is NPO-complete.

If $x$ were a vector of integers, rather than a vector of bits, then it would be Cover Integer Program (CIP), which can be approximated logarithmically according to "Improved approximations of packing and covering problems" by A. Srinivasan (1995).

There are many other known related problems with different variations, e.g. all elements in $A$ must be bits, $\geq$ is $\leq$ and min is max, there is a single inequation (i.e. $m = 1$), etc. I had some hope when I found this: https://www.nada.kth.se/~viggo/wwwcompendium/node199.html#7105, comments section, last sentence. However, $A$ is a matrix of bits in that work.

It is trivial to build an S-reduction from Minimum Set Cover, so at least it is Log-APX-hard. But at a first glance it looks too "simple" for Poly-APX- or Exp-APX-hardness, I don't know... Has this problem ever been studied?

EDIT: In the last two weeks I have developed an approximation to the problem (not based on linear programming) and, if my maths are right, it is logarithmic. Since it looks like this variant of  Minimum 0-1 Integer Programming has not been studied yet in the literature, it could be publishable (?). I promise I'll get back here and report it, as soon as some reviewers check out its correctness (also if it's wrong, so that nobody else wastes his time trying the same!). (And, of course, if this problem has already been tackled in the literature, I would really appreciate it if you let me know!!)

EDIT2: As Chandra's answer says below, Kolloiopoulos and Young gave a logarithmic approximation to a generalization of this problem. They define $x$ as a vector of non-negative integers but, simultaneously, include constraints of the form $x \leq d$. By setting $d=(1,...,1)$, $x$ must be a vector of bits.

Kolloiopoulos and Young give an $O(\log m)$ approximation for general covering integer programs. See the paper below.
http://www.sciencedirect.com/science/article/pii/S0022000005000656


Sampling satisfiable 3-SAT formulas Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned on the formula being satisfiable:

Q1: Can this be achieved efficiently by a classical computer (with random bits)?

Q2: Can this be achieved efficiently by a quantum computer?

I am also interested in the following two variants:

V2: You sample all the formulas w.r.t. a probability distribution that gives satisfiable formulas twice the weight of unsatisfiable formulas.

V3: you sample where the weight is the number of satisfying assignments (Here we care only about Q2).

Update: Colins' answer demonstrates a simple algorithm for V3. (I was wrong in assuming that this is classically difficult.) Let me mention another variant
of all the three questions:

You specify in advance $m$ clauses and you need to sample random satisfiable subsets of the input clauses.

There is a simple algorithm for V3.
I'll use the convention that there are $(2n)^3$ possible clauses,
so $2^{8n^3}$ formulas.
(This is just for simplicity - if you don't want all $8n^3$ clauses to be considered valid, it wouldn't affect the following argument.)

Pick a random assignment from $\{0,1\}^n$.
For each of the $7n^3$ possible clauses that are true on this assignment,
include the clause with probability $1/2$.
Each formula $\phi$ will appear with probability proportional to
its number of satisfying assignments.
The $m$-clause variant is similar: pick a set of size $m$
out of the $7n^3$ clauses.


Are there nice generalizations of SPQR trees to k-connected components for k>3? I'm curious how one should best understand the connections between the k-connected components when $G$ has minimum cuts of size $k>3$, or perhaps approximate minimum cuts produced by Karger's algorithm.  SPQR trees answer this question for 2-connected graphs.  And obviously 1-connected graphs are simply a tree of their 2-connected components.

For edge connectivity rather than vertex connectivity, there's always the Gomory–Hu tree.


A small C-like language that turing machines can simulate I am looking for a small language that helps 'convince' students that turing machines are a sufficiently general computing model. That is, a language that looks like the languages they are used to, but is also easy to simulate on a turing machine.

Papadimitriou uses RAM machines for this job, but I fear that comparing something strange (as a turing machine) to another strange thing (basically, an assembly language) would be too unconvincing for many students.

Any suggestions would be most welcome (specially if they came with some recommended literature)

If your students have done any functional programming, the nicest approach I know is to start with the untyped lambda calculus, and then use the bracket abstraction theorem to translate it into SKI combinators. Then, you can use the $smn$ and $utm$ theorems to show that Turing machines form a partial combinatory algebra, and so can interpret the SKI combinators.

I doubt this is the simplest possible approach, but I like how it rests  on some of the most fundamental theorems in computability (which you may well wish to cover for other reasons).

It appears that Andrej Bauer answered a similar question on Mathoverflow a few months back.
If you are set on a C-like language, your path will be a lot rougher, since they have a rather complicated semantics -- you'll need to

Show that Turing machines can simulate a stack and a heap at the same time, and
Show how variables can be implemented with a stack, and
Show that procedure calls can be implemented with a stack.

This is much of the contents of a compilers class, honestly.


Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$ Let $G=(V,E)$ be graph. Recall that a  cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in E \mid a \in A, b \in B\} = E \cap (A \times B)$. Finally, let $E = E_1 \cup E_2$ be a given partitioning of the edges.

Question. What is an efficient way to generate a cut $(A,B)$ of $G$ such that $|E_1(A,B)| > |E_2(A,B)|$ ?

Note. I'm fine with randomized algorithms. Also, in case one has the choice, I'd prefer a cut with minimal $|E(A,B)|$.

Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT.
Proof. Call the given problem Positive Discrepancy Cut (PDC).  Define weighted PDC to be the generalization where the input is a graph $G=(V,E)$ with polynomially bounded (possibly negative) integer edge weights, and the goal is to determine whether there is a positive-weight cut.  To prove the theorem we prove two lemmas:
Lemma 1. Weighted PDC reduces in polynomial time to (unweighted) PDC.
Lemma 2. MAX-CUT reduces in polynomial time to Weighted PDC.
Proof of Lemma 1. Given an $n$-vertex instance $G=(V,E)$ of weighted PDC with weights in $[-M, M]$, where $M$ is polynomial in $|G|$, the reduction outputs the graph $G'$ obtained from $G$ as follows.  Replace each vertex $v$ in $G$ by a clique $C_v$ of $|E|+1$ vertices, with all edges white.  For each edge $(u, v)$ of weight $w$ in $G$, add $|w|$ edges between $C_u$ and $C_v$, making them white if $w<0$ and red if $w>0$.  Given any positive-weight cut $(A, B)$ in $G$, the corresponding cut in $G'$ is $(A', B')$ where $A'= \bigcup_{v\in A} C_v$ and $B'=\bigcup_{v\in B} C_v$.  The number of red edges minus white edges crossing $(A', B')$ is the weight of the cut $(A, B)$.  So, if $G$ has a positive-weight cut, then $G'$ has a cut with more red than white edges.  Conversely, suppose $G'$ has a cut with more red than white edges.  The total number of red edges in $G'$ is at most $|E|M$, so each clique $C_v$ must be entirely contained in one side of the cut or the other.  So the cut corresponds to a cut in $G$ that has positive weight.  This proves Lemma 1. $~~\Box$
Proof of Lemma 2.  Given a MAX-CUT instance $(G=(V,E), k)$, the reduction outputs the instance $G'$ of Weighted PDC defined as follows.  Obtain $G'$ from $G$ by giving every edge in $G$ weight 1, then adding two vertex $a$ and $b$, each with edges to all other vertices.  Give each edge from $a$ or $b$ to a vertex in $G$ weight $-M$ where $M=|E|+1$.  Give the edge $(a, b)$ weight $M|V|-k+1$.  This completes the reduction.
Suppose there is a cut $(A, B)$ in $G$ with at least $k$ edges.  Then the cut $(A', B')$ in $G'$ where $A'=A \cup \{a\}$ and $B'=B\cup\{b\}$ has weight at least $k-|V|M + M|V|-k+1 = 1$.  Conversely, suppose there is a positive-weight cut $(A', B')$ in $G'$.  Vertices $a$ and $b$ cannot be on the same side of the cut, because if they are, the edge $(a, b)$ is not cut, while at least one edge out of $a$ or $b$ is cut, contributing $-M=-|E|-1$ to the cut weight, and each of the remaining edges (in $E$) contributes at most 1.  So $a$ and $b$ are on different sides of the cut $(A', B')$.  WLOG assume $a\in A'$ and $b\in B'$.  Then (accounting for the edges out of $a$ and $b$) the cut $(A, B)$ in $G$ where $A=A'\setminus \{a\}$ and $B=B'\setminus \{b\}$ must have at least $k$ edges.  So the reduction is correct. $~~\Box$
This reduction is similar to one by Peter Shor in this answer to a question about approximating MAX-CUT with negative edge weights.


Finite One-Way Permutation with Infinite Domain Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s functionality. (As in Kolmogorov complexity.) See explanations below.

For instance, the NOT function is one such permutation:

function NOT(x)
    Let y = x
    For i=1 to |x|
        Flip the ith bit of y
    return y

$\pi_k(\cdot)$, defined below, is another case:

function pi_k(x)
    return x + k (mod 2^|x|)

My question is about a special class of permutations, called one-way permutations. Informally speaking, these are permutations which are easy to compute, but hard to invert (for a $\rm{BPP}$ machine). The mere existence of one-way permutations is a long-standing open problem in cryptography and complexity theory, yet in the remainder,  we will assume that they exist.

As an example of a conjectured one-way permutation, one can consider the RSA: Let $n = pq$ be a Blum integer, and let $e = 65537$.
The one-way permutation is defined by:
$\pi_n(x) = x^e \bmod n$.

Note that RSA is defined over the finite domain $\mathbb{Z}_n$. In fact, to obtain an infinite domain permutation, one has to consider a family of RSA permutations
$\{\pi_n\}_{n\in D}$, where $D$ is an infinite set of Blum integers. Note that $D$ is the description of the family, and by definition, it is infinite.

My question is (assuming the existence of one-way permutations):

  Does there exist finite-description one-way permutations over an infinite domain?

The answer may vary: It can be positive, negative, or open (either likely to be positive, or likely to be negative).

Background

The question arose when I was reading an ASIACRYPT 2009 paper. There, the author implicitly (and in the context of some proof) assumed that such one-way permutations exist.

I'll be happy if this is indeed the case, though I couldn't find a proof.

The paper On constructing 1-1 One-Way Functions, by Goldreich, Levin and Nisan shows how to construct length preserving 1-1 functions with infinite domains and finite description. The hardness of inverting the functions is based on popular assumptions, such as hardness of inverting RSA or finding Discrete Logarithms.

Their construction is a twist of the straightforward idea of converting a family, $\{f_i\}_i$, of one-way functions into a single one-way function by setting $f(r,s) = f_i(x)$ where $r$ is the randomness used to pick the index $i$ and $s$ is the randomness used to select the input $x$ (given the index $i$).

The problem with the above idea is that $f(r,s)$ is not necessarily 1-1. They amend this problem by slightly modifying $f(r,s)$ and arguing that, under certain conditions on the family $\{f_i\}_i$, the new construction is indeed 1-1. They then go on to show that these conditions are satisfies by the RSA/Discrete-log based functions.


Smallest representatives of a quotient by an equivalence relation Background

Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for a regular language $L$ such that $|Q|=n$, and let $\equiv_L$ be the relation given by $$x\equiv_Ly\text{ iff for all $u$: }xu\in L\Leftrightarrow yu\in L.$$ It is known we can identify the states of $\mathcal{A}$ with the elements of the quotient $\Sigma^*/\equiv_L$. Moreover, since $\equiv_L$ can be characterized by $$x\equiv_Ly\text{ iff }\hat\delta(q_0,x)=\hat\delta(q_0,y),$$ we know we can choose elements $w_1,\ldots,w_n\in\Sigma^*$ such that $$Q=\big\{[w_i]_{\equiv_L}: i\in\{1,\ldots,n\}\big\},$$ and $|w_i|\leq n$ for all $i$, that is, we can choose representatives for $\Sigma^*/\equiv_L$ of length at most $n$.

This is useful because, given the minimal DFA $\mathcal{A}$ (whose states might be given in an abstract way, not necessarily with elements of $\Sigma^*/\equiv_L$), we can obtain a set of representatives of $\Sigma^*/\equiv_L$ by running $\mathcal{A}$ with all inputs of length at most $n$ and marking the states that have already been reached with a flag. Whenever an unmarked state is reached with a string $w$, we flag the state and add $w$ to the list of representatives. This might not be the most elegant or efficient algorithm, but thanks to the upper bound we can be sure it finished and it computes what we want.

Question

Is there a general method of estimating a minimal length of representatives of an equivalence relation? I'm assuming, of course, that the universe consists of elements of finite length (e.g. $\Sigma^*$).

In particular, I'm looking for a similar upper bound for the relation $\sim_L$ given by $$x\sim_Ly\text{ iff for all $u,v$: }uxv\in L\Leftrightarrow uyv\in L,$$ which can be characterized by $$x\sim_Ly\text{ iff for all $q\in Q$: }\hat\delta(q,x)=\hat\delta(q,y),$$ where the automaton is minimal.

Thanks in advance for your guidance.

Update: to be a bit more precise, what I want is an upper bound $M$ for the smallest representative of a class, so I can do an algorithm of the form: ``check all the words of length at most $M$...'' and be sure that all classes are covered by some representative at least once.

It seems to me that your question is too general to answer.  Let me focus on the case of ∼L.  Then here is an example which shows a lower bound; namely, the length of a representative can be at least $e^{(1-o(1))\sqrt{n \ln n}}$, where n is the number of states of the minimum DFA.

We will actually show a lower bound on the length of a representative with respect to the right-equivalence relation RL on strings defined as: x RL y if and only if for all strings u, ux∈L ⇔ uy∈L.  Because equivalence relation RL is coarser than ∼L, any complete set of representatives with respect to ∼L must contain a complete set of representatives with respect to RL, and therefore a lower bound shown for RL applies also to ∼L.

Number-theoretic preparations.  Let pK be the Kth prime number.  We write the sum of the first K primes as Σ(K).  We also write the product of the primes that are less than or equal to N as N# (the primorial of N).  Then the following facts are known:

pK ∼ K ln K (from the prime number theorem).
Σ(K) ∼ K2 ln K (see the MathWorld article on prime sums).
ln(N#) ∼ N (see the MathWorld article on Chebyshev functions).

By combining these facts, we obtain that $\lim_{K\to\infty}\frac{\ln(p_K \#)}{\sqrt{\Sigma(K) \ln \Sigma(K)}} = 1$, and therefore $p_K \# = e^{(1-o(1))\sqrt{\Sigma(K) \ln \Sigma(K)}}$.

(I think that this final statement is a standard fact in the number theory, but I do not know a good reference for it.  See a related discussion in comments to this post.)

Construction and analysis.  For k∈ℕ, construct a DFA Mk on the alphabet {0, 1} as follows.  Let K=2k.  First, there is a complete binary tree of depth k rooted at the initial state.  Label the K leaves of this binary tree as q1, …, qK.  At each qi, we add a cycle of length pi, labeling each edge of the cycle with both 0 and 1 (that is, once you reach state qi, only the length of the rest of the string matters).  Mark the K states q1, …, qK as accepting states.

If x RL y, then we have that |x|≡|y| (mod pi) for every i≤K by prepending the binary notation of i−1 and some string of an appropriate length to both x and y.  This means that any complete set of representatives with respect to the relation RL contains at least one string with length at least pK#−1.

The number of the states in DFA Mk is K−1+∑i=1K pi = Σ(K)+K−1.  If we denote this number as n, then n ∼ Σ(K), and the length of at least one representative must be at least $p_K \# - 1 = e^{(1-o(1))\sqrt{n \ln n}}$.


Lack of atomic propositions in the Calculus of Constructions from ATTAPL textbook I am working through the Dependent Types chapter from Advanced Topics in Types and Programming Languages (ATTAPL) by Benjamin Pierce et al. I am confused with the calculus presented Fig 2-7 (Calculus of Constructions) that extends $\lambda LF$ to support Prop type. I have multiple questions.

Can a Prop term be $\beta$-reduced at all? The rule (BETA-ALL) on the next page suggests that only the body of a Prop can be reduced. That is, in the term forall x:T.t, only t is reduced.
There are no atomic propositions like True, False. So how can one build a term of type Prop (and Prf p). Any simple example suffices.
I am not sure I understand the type equivalence rule QT-ALL in Fig 2-7.
The encoding of nat (and zero later on) is confusing. For the sake of readability I am writing it down here.

nat = all a:Prop.all z:Prf a.all s:Prf a ->Prf a. a

What is the meaning? Specifically, what is a - any Prop? Why are proofs of z (zero) and s (succ) required?

I think these are lot of questions. I would appreciate answers to any of these questions.

EDIT: I was suggested to move this to cs.stackexchange.com. However, the question is about the meta-theory of Coq and I thought cstheory is an appropriate forum. But if multiple users suggest moving this, I can do that.

I have no thoughts on whether this is on-topic for TCS and if need be I can repost my answer elsewhere. But I think the question is a good opportunity to demonstrate how to think about the CoC pending some consensus to move it.

The rule BETA-ALL, which says we can beta-reduce terms underneath the all binder (but not the type of the argument), is not part of the typing or equivalence rules of $\mathsf{CC}$. Pierce is extending his definition of $\beta$-reduction first seen in Section 2.3 (section "Strong Normalization"), which itself is defined "As an auxiliary device for the soundness and completeness of algorithmic typechecking." Specifically the fact that this reduction is strongly normalizing can be used to show that typechecking halts.
Pierce mentions on page 51 that "We may use type and term variables declared in a fixed initial context to simulate the built-in types and operators of a programming language."

Also see Figure 2-1 (First-order dependent types), in which one of the context formation rules (labelled "term variable binding") is that if $\Gamma$ is a well-formed context and $T$ is a well-formed type, we can pick a variable name $x$ and and then $\Gamma, x :: T$ is a well-formed context. (It seems to be implicit that $x$ should be a fresh name, i.e. does not conflict with the rest of $\Gamma$, and that $T$ is well-formed in context $\Gamma$.).

Now combine this with rule of Figure 2-7 which states that $T ::= \ldots \mathsf{Prop}\ldots$, meaning $\mathsf{Prop}$ is a type. Therefore we can add $\mathsf{True} :: \mathsf{Prop}$ to the context. Likewise with $\mathsf{False}$.

To add a proof of $\mathsf{True}$, use rule K-App to deduce that $\mathsf{Prf} \:\mathsf{True}$ has kind $\ast$, i.e. is a type, and apply term variable binding again to add some proof $\mathsf{Unit} :: \mathsf{Prf} \,\mathsf{True}$ to the context.
When introducing $\mathsf{Prop}$, we also introduce this new binder called forall, which seems reasonable. Now we have to give this a semantics---how do we prove some forall x, P? The rule merely states that a proof of forall x, P is the same thing as offering "a proof of $P$ for every $x$" where the latter is defined as a dependent product (something our system already had). In a sense, the rules just say "by using the operator $\mathsf{Prf}$, $\mathsf{Prop}$ acts like $\ast$."

Perhaps you're wondering why this is interesting. We know that a proposition $p:\mathsf{Prop}$ can be coerced to a type $\mathsf{Prf} p : \ast$, and the equivalence says the binder forall acts like a dependent product, so what is gained?. But notice that by using T-ALL and QT-ALL, $\mathsf{Prop}$ can effectively play the role of $T$ when forming the dependent product, so we can quantify over $\mathsf{Prop}$ and still have a $\mathsf{Prop}$. This is the "impredicativity"  Pierce refers to, and it makes the system drastically more expressive. If we tried to get rid of the coercion just take $\mathsf{Prop} \equiv \ast$, we would have $\ast : \ast$, which is known to be inconsistent by a theorem of Girard.
To exhibit a natural number per Pierce's definition, you must be able to satisfy this criterion: If I give you any type $a$, term $z : a$, and successor function $s : a \to a$, you must be able to offer me some term of type $a$. Since you don't know the type $a$ in advance, the only thing you can do is apply $s$ to $z$ some number of times, and that is effectively the same thing as having a natural number. Pierce is showing that $\mathsf{CC}$ is expressive enough to type Church's encoding of the natural numbers , which is good because that encoding becomes impossible when you move from untyped lambda calculus to STLC. See these course notes. See also the Wikipedia page on System F for more information---System F is less expressive than $\mathsf{CC}$ but still good enough to play this game.


Is the model in which a protocol is proven secure more important than type of hardness from which the algorithm gains its strength Question: If I prove a protocol secure in the plain model (i.e., without any prerequisites or setup before running the protocol, setups like a common reference string distributed among all parties) using nonstandard hardness assumptions (like bilinear oracle Diffie-Hellman) has any advantage over a protocol which uses a setup before running but its hardness relies on a standard hardness assumption (like discrete logarithm)?
  If there is a tradeoff, can you point me how to maintain this tradeoff?

I must note that the nonstandard hardness does not give you enough measure to compare the complexity of the protocol using it with other protocols.

Let me rephrase the question:

  Which one is preferred?

  Proving a protocol secure in the standard model, based on non-standard assumptions
  Proving a protocol secure in non-standard models (like CRS), based on standard assumptions.

The short answer is: It depends!

Details follow.

Assume that you can prove a protocol secure in the CRS model using standard assumptions. In addition, assume that you can implement the CRS model in the standard model without significant overhead, and using only standard assumptions. Then, the second approach is preferable. (Here, "significant" depends on the application.)

On the other hand, assume that you cannot implement the CRS model in the standard model easily ,i.e. either the overhead is too high, or the protocol setting is that you cannot implement the CRS without resorting to non-standard assumptions (For instance: You don't have access to some trusted 3rd party, etc.) In such cases, it seems that the first approach is preferable.

Side note: I must add that both approaches are highly valuable in theory, regardless of the real-world application.