If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo? The homeomorphic embedding relation for trees as I understand it is a well-quasi-order (wqo) on trees when the label of a node determines the number of children of that node, and there are a finite number of such labels. A description of what (I hope) I'm referring to is in section 5.1 of this article.

I want to naively generalize this wqo to trees wherein the labels do not determine the number of children, for the purpose of runtime termination checking with states being said ill-behaved trees.

Assuming that I'm testing the homeomorphic embedding relation $\leq$ according to the rules (if something looks wrong here, then trust the linked the paper and correct me instead):

$l \leq r = \begin{array}\\
c(s_1 \ldots s_n) \leq c(t_1 \ldots t_n) & \text{if} & l = c(s_1 \ldots s_n) \text{ and } r = c(t_1 \ldots t_n) \text{ and } s_1 \leq t_1 \ldots s_1 \leq t_n \\
s \leq c(t_1 \ldots t_n) & \text{if} & l = x(s_1 \ldots s_n) \text{ and } r = c(t_1 \ldots t_n) \text{ and } \exists i.s\leq t_i \\
false && \text{otherwise}
\end{array}$

where $c$ is a label, $x$ is some other label, and $s_i$ and $t_i$ are subtrees (and the $c(\ldots)$ notation is a tree construction with $c$ as the root of a (sub)tree and $\ldots$ that (sub)tree's children).

Would I still have a wqo if I simply said the relation holds if I ever encounter (in the course of checking membership in the relation) a scenario where I'm checking $c(\ldots s_m) \leq c(\ldots t_n)$ and $m \neq n$?

My gut says that I still would have a wqo (the 'dives in' rule should force me to make the arity check and blow the whistle whenever the vanilla homeomorphic embedding would be too lenient on labels-with-inconsistent-children-counts, and catch the case of an infinite sequence of widening trees), but as with any procedural hack on a mathematical relation I feel a bit too dumb to be sure.

Here's a nice property of WQOs:

  If $R$ is a WQO on terms, and $S$ is another transitive relation such that
  $$ R\ \subseteq\ S$$
  Then $S$ is a WQO

Proof: Let $t_1,\ldots, t_n,\ldots$ be an infinite sequence of terms. Because $R$ is a WQO, there are $i, j$ with $i<j$ such that $t_i\ R\ t_j$. But this implies $t_i\ S\ t_j$, so $S$ is a WQO as well.

This (somewhat counter-intuitive) result means you can always make your relation more permissive while preserving the WQO property.


Log-space reduction from Parity-L to CNOT circuits? Question.

In their paper Improved simulation of stabilizer circuits, Aaronson and Gottesman claim that simulating a CNOT circuit is ⊕L-complete (under logspace reductions). It is clear that it is contained in ⊕L; how does the hardness result hold?

Equivalently: is there a logspace reduction from iterated matrix products modulo 2, to iterated products of elementary matrices (the invertible matrices which realize row transformations) mod 2?

Details

A controlled-NOT (or CNOT) operation is a reversible boolean operation, of the form
$$
\mathsf{CNOT}_{\!h,j} (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j\,, \;\ldots\;, x_n)
\;\;=\;\;
(x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j \oplus x_h\,, \;\ldots\;, x_n)
$$
where only the j th  bit is changed, and that bit is changed by adding $x_h$ modulo 2, for any distinct positions h and j. It is not hard to see, if we interpret $\mathbf x = (x_1\,, \;\ldots\;, x_n)$ as a vector over ℤ/2ℤ, that this corresponds to an elementary row transformation modulo 2, which we may represent by a matrix with 1s on the diagonal and a single off-diagonal position. A CNOT circuit is then a matrix product consisting of a product of some elementary matrices of this type.

The paper by Aaronson and Gottesman mentioned above (which, very incidentally to this question, is about a class of quantum circuits which can be simulated in  ⊕L) has a section on computational complexity. Towards the beginning of this section, they describe ⊕L as follows:

  ⊕L [is] the class of all problems that are solvable by a
  nondeterministic logarithmic-space Turing machine, that
  accepts if and only if the total number of accepting paths
  is odd. But there is an alternate deﬁnition that is probably more intuitive to non-computer-scientists. This is
  that ⊕L is the class of problems that reduce to simulating
  a polynomial-size CNOT circuit, i.e. a circuit composed
  entirely of NOT and CNOT gates, acting on the initial
  state |0...0⟩. (It is easy to show that the two deﬁnitions
  are equivalent, but this would require us ﬁrst to explain
  what the usual deﬁnition means!)

The target audience of the article included a substantial number of non-computer-scientists, so the wish to elide is not unreasonable; I'm hoping someone can clarify how this equivalence holds.

Clearly, simulating a product of such matrices can be performed in ⊕L as a special case of evaluating coefficients of iterated matrix products (mod 2), which is a complete problem (under logspace reductions) for ⊕L.
Furthermore, as the CNOT matrices just perform elementary row operations, any invertible matrix can be decomposed as a product of CNOT matrices. However: it is not clear how to me how to decompose even an invertible matrix mod 2 into a product of CNOT matrices by a logspace reduction. (Indeed, as noted by Emil Jeřábek in the comments, Gaussian elimination suffices to compute determinants mod 2, which is a ⊕L-complete problem: so a direct attack by decomposing e.g. invertible matrices as products of elementary matrices seems not to be feasible in logspace unless L = ⊕L.) To say nothing of matrix products which are not invertible. So some cleverer reduction seems to be required.

I hope someone can provide a sketch of this reduction, or a reference (e.g. a text for which this is an exercise, if it is simple).

Let us start with the $\oplus L$-complete problem of counting mod $2$ the number of paths of length $n$ from vertex $s$ to vertex $t$ in a directed graph $G=(V,E)$. We apply a couple of logspace reductions as follows.

Let $G'=(V',E')$ be the graph such that $V'=V\times\{0,\dots,n\}$ and $E'=\{((u,i),(v,i+1):i<n,(u,v)\in E\}\cup\{(w,w):w\in V'\}$ (i.e., we take $n+1$ copies of $G$’s vertices, make edges go from the $i$th copy to the $(i+1)$th copy according to $G$’s edges, and add all self-loops). Then the original problem is equivalent to counting paths of length $n$ from $s'=(s,0)$ to $t'=(t,n)$ in $G'$.

Moreover, $G'$ is acyclic, and we can explicitly define an enumeration $V'=\{w_k:k\le m\}$ such that all edges in $G'$ apart from the self-loops go from $w_k$ to $w_l$ for some $k<l$. Without loss of generality, $w_0=s'$ and $w_m=t'$. Let $M$ be the adjacency matrix of $G'$ wrt the given enumeration. Then $M$ is an upper triangular integer matrix with $1$ on the diagonal, and the number of paths of length $n$ from $s'$ to $t'$ equals the top right element of $M^n$.

It is easy to see that
$$M=\prod_{j=m}^1\prod_{i=0}^{j-1}E_{i,j}(M_{i,j}),$$
where $E_{i,j}(a)$ is the elementary matrix whose only nondiagonal entry is $a$ in row $i$ and column $j$. In this way, we reduced the original problem to computing the top right element of a product of elementary matrices. In the $\oplus L$ case, the computation is modulo $2$, i.e., we consider the matrices over $\mathbb F_2$. (In this case, the elementary matrices can be only $E_{i,j}(0)=I$, which we can ignore, and $E_{i,j}(1)$, which can be simulated by a single CNOT gate, as mentioned in the question.) If we consider them as integer matrices, we get a $\#L$-complete problem, and if we consider them modulo $k$, we get a $\mathrm{Mod}_kL$-complete problem.


First-order multi arity functions in dependent type? (cross posted from Reddit https://www.reddit.com/r/dependent_types/comments/b1ts8b/firstorder_multi_arity_functions_in_dependent_type/?

Take Agda for example, functions of multi arity is "encoded" as functions of one argument returning functions. In the same sense one can "encode" a record type as iterated Sigmas, but Agda has primitive first-order record type.

Then the problem is, in the encoded case, one can talk about functions of multiple arities generally, like function extensionality https://github.com/agda/cubical/blob/master/Cubical/Core/Prelude.agda#L105 . to apply function extensionality to functions of multiple arity, one just iteratively apply it multiple times.

It turns out Sigma type has also some general properties like this: https://github.com/agda/cubical/blob/master/Cubical/Foundations/HLevels.agda#L66 . So if record type is also encoded, then one can use this to a record type of multiple fields, just iterate it multiple times. But in case of Agda one cannot do this, because record type is primitive to Agda.

So is there a dependent type theory that has primitive multi-arity function types?

Also can we extends such a theory so we can talk generally of functions of multiple arity and records of multiple field? One goal is to write down a definition of "isContrRecord" in this new theory.

Any related reference?

I do not understand what you are asking for, as it seems that you are simply asking for record types. The comments are too terse for a normal discussion, so I will offer a solution here, and you tell us what is wrong with it. I will do it by way of an example.

Suppose we are given the following types:
\begin{align*}
& \vdash A \ \mathsf{type} \\
x : A & \vdash B(x) \ \mathsf{type} \\
x : A, y : B(x) & \vdash C(x,y) \ \mathsf{type}
\end{align*}
We would like the type of "binary" dependent functions whose domain is something like $x : A, y : B(x)$ and the codomain is $C(x, y)$.

Let us write
$$
\{ \ell_1 : A_1, \ell_2 : A_2(\ell_1), \ldots, \ell_n : A_n(\ell_1, \ldots, \ell_{n-1})
\}
$$
for a dependent record type with fields $\ell_i$. Observe that this looks a lot like a chunk of a context. Given a term $p$ of the above type, write $p.\ell_i$ for the $i$-th projection.

Without any pattern matching the type of dependent functions from $x : A, y : B(x)$ to $C(x, y)$ can be written as
$$\Pi (p : \{x : A, y : B(x)\}) \,.\, C(p.x, p.y),$$
which is arguably not so nice. But since patterns for record types are irrefutable (they always match), we can also use pattern-matching to write
$$\Pi (\{x = x_0, y = y_0\}) \,.\, C(x_0, y_0).$$
or, if we dare use the same symbol for a field label and the bound variable (OCaml allows this, for instance),
$$\Pi (\{x, y\}) \,.\, C(x, y),$$
For such pattern matching to make sense we need to know ahead of time that the fields $x$ and $y$ have types $A$ and $B(x)$, respectively. In implementations of proof assistants this is typically not a problem as each record type has to be declared before it can be used. Otherwise, we can still write something like
$$\Pi (\{x : A , y : B(x)\}) \,.\, C(x, y)$$
to indicate the missing type information.

Of course, the same sort of ideas apply to $\lambda$-abstraction. Given
$$x : A, y : B(x) \vdash e(x,y) : C(x,y)$$
the term
$$\lambda \{x : A, y : B(x)\} \,.\, e(x,y)$$
will receive the above product type.

In any case, it seems that we can have pattern matching on the records and get precisely what you are asking for. I kindly ask that, in case this is not what you are asking for, you modify your question and provide some concrete examples of what you are looking for.


Has this form of "kind-of-dual" homomorphisms been studied? Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be graphs and let $h:V_2\to V_1$ be a map such that, for every edge $(u_1,v_1)\in E_1$, there is an edge $(u_2,v_2)\in E_2$ such that $h(u_2)=u_1$ and $h(v_2)=v_1$.

This kind of maps has occurred in our recent research in Database Theory. We think that it looks like a natural "dual" to graph homomorphisms, where $h$ would be $V_1\to V_2$ and map each edge of $G_1$ to an edge of $G_2$. However, we could not find it in the literature, but, since we do not have a name for it, maybe we searched in the wrong places.

Some background: in Database Theory, homomorphisms play an important role in the context of the containment problem for conjunctive queries. The "kind-of-dual" form occurs in the context of parallel query evaluation.

In this slightly extended context, testing for existence of such a mapping is NP-complete, and I expect that also for graphs. However, I am not asking for complexity results, but I would be be grateful for pointers to the literature (or even a name, for that matter).

In the case of undirected graphs, there is literature about such morphisms called graph emulators.
They are a refinement of the notion of covering graph.
A covering graph maps the neighbourhood of a vertex $u$ bijectively to the neighbourhood of $h(u)$, while an emulator is only required to do it surjectively, which seems equivalent to your question.

This notion appears in the context of characterizing graphs having planar covers or planar emulators, which yields several open problems, see for instance this paper for a survey.


Secure multiparty computation of number of 1s times number of 0s in a shared string Suppose there are $N>2$ parties $p_j$, each with a bit $b_j\in{\{0,1\}}$. I want to compute the multiplication of number of ones times that of zeros, that is, $R=(\sum{b_j})\times(N-\sum{b_j})$.

The computation should be secure in the sense that no party can learn more than the final result $R$. For example, it's not ok to perform secure sum, because then $\sum{b_j}$ will become known, and the sum is sensitive in my problem. So, is there any existing secure computation protocol that fits the demand?

Edit: The number $N$ in the problem is large, at least over $1000$. So efficient secure multiparty computation is needed. A secure sum protocol could be efficient but generic  SMC like boolean circuits might be too computation intensive. So I need an efficient protocol.

This answer is about feasible solutions based on homomorphic encryption that is NOT fully-homomorphic, as the latter may be extremely inefficient (if there are efficient fully homomorphic cryptosystems that are comparable with those provided below in terms of efficiency, I'd be glad to hear about them).

Since you only need one multiplication then there are solutions that are potentially less expensive than fully homomorphic encryption: [1] and [2]. The latter works on encrypted bit-decompositions of the input so it will need a bit-decomposition protocol like [3] and [6], but the former works on whole values. Just for completeness, the former has been extended to $d$-operand multiplication in [4], even though the OP may not need this. These solutions are non-interactive and should work in the two-party case.

If you have more than two parties and could afford some interaction then [5] provides a "secure multiplication gate" which is potentially more efficient and allows unbounded number of multiplications. It works basically by converting the homomorphically-encrypted values to some sort of secret-sharing, multiplies the result (interactively), then convert it back to homomorphic encryption.

[1] Evaluating 2-DNF Formulas on Ciphertexts

[2] Non-interactive cryptocomputing for NC1

[3] Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation

[4] Additively Homomorphic Encryption with d-Operand Multiplications

[5] Multiparty Computation from Threshold Homomorphic Encryption

[6] Efficient Binary Conversion for Paillier Encrypted Values


Clique problem on fixed graphs As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this case correspond to edges of $K_n$.
It is know (Razborov, Alon-Boppana)
that, for $3\leq k\leq n/2$, this function requires monotone
circuits of size about $n^k$.

But what if we take one fixed graph $G\subseteq K_n$, and consider
the monotone boolean function $CLIQUE(G,k)$, which takes a subset $S\subseteq [n]$ of vertices, and outputs $1$ iff some $k$ vertices in $S$ form a clique in $G$. Variables in this case correspond to vertices of $K_n$, and the function is just the standard clique function but restricted to the spanning subgraphs of one fixed graph $G$.

1. Does there exist $n$-vertex graphs $G$ for which  $CLIQUE(G,k)$ requires monotone
circuits of size larger than $n^{O(\log n)}$? I guess - NO.

2. Is $CLIQUE(G_n,k)$ an NP-hard problem for some sequence of graphs
$(G_n\colon n=1,2\ldots)$? I guess - NO.

Note that if $C_1,\ldots,C_r$ are all maximal cliques in $G$, then  $CLIQUE(G,k)$
can be computed as an OR of $r$ threshold-$k$ functions, the $i$-th of
which tests whether $|S_a\cap C_i|\geq k$. Thus, if $r=poly(n)$, then the entire
circuit is of polynomial size. But what about graphs with an
exponential number of maximal cliques? (A clique is maximal it no
vertex can be added to it.)

It is possible to "embed" $CLIQUE(m,k)$ into $CLIQUE(H,k)$ for a particular
graph $H$ on $n=2^m$ vertices. In particular, Bollobas and Thomason (1981) have shown that,
if $H$ is a Hadamard graph whose vertices
are subsets of $[m]$, and two vertices $u$ and $v$ are adjacent iff $|u\cap v|$ is
even, then $H$ contains an isomorphic copy of every graph $G$ on $m$ vertices.
Can this fact be combined with Razborov´s lower bound (of about $m^k$)
for $CLIQUE(m,k)$ to conclude that  $CLIQUE(H,k)$ requires monotone circuits
of size about $m^k$?  A potential problem here is that, even though the graph $H$ "contains" all $m$-vertex graphs, these graphs are not on the same set of vertices.
And Razborov's argument rquires that positive and negative inputs
($k$-cliques and complements of complete $(k-1)$-partite graphs) are
graphs on the same set of vertices. Moreover, all positive inputs ($k$-cliques)
are just isomorphic copies of one and the same fixed $k$-clique.

3. Any ideas? Has anybody seen such type of problems being considered?
I mean, decision problems for subgraphs of a fixed graph. Or, say,
the SAT problem for sub-CNFs of one fixed
(satisfiable) CNF (obtained by removing some literals)?

Motivation: Problems of this kind are related to the complexity of combinatorial optimization algorithms. But they seem to be interesting in themself.
Why should we seek for algorithms that are efficient on all graphs? In reality, we
are usually interested in the properties of small pieces of one (large) graph
(network of streets in a country, or facebook, or the like).

Remark 1: If the graph $G=(L\cup R,E)$ is bipartite, then the vertex-edge incidence matrix of the inequalities $x_u+x_v\leq 1$ for all $(u,v)\not\in E$ is totally unimodular, and one can solve the clique problem on induced subgraphs of $G$ via linear programming. Thus, for bipartite graphs $G$, $CLIQUE(G,k)$ has a small (albeit  non-monotone) circuit.

Remark 2: An indication, that in the case of bipartite graphs $G$, the answer to Question 1 "should" indeed be NO is that then the following monotone Karchmer-Wigderson game on $G$ needs only $O(\log n)$ bits of communication. Let
$k$ be the largest number of vertices in a complete bipartite subgraph of $G$.
Alice gets a set $A$ of red nodes, Bob a set $B$ of blue nodes such that $|A|+|B|>k$. The goal is to find a non-edge between $A$ and $B$.

We did some research on the problem of proving in tree-like Resolution whether a fixed graph $G$ has a clique of size $k$ (where $k$ is usually small). In particular we discovered that refutations of size $n^{\Omega(k)}$ are needed for a large class of graphs.

You can find the paper Parameterized Complexity of DPLL Search Procedures at this link.


Models of random graphs, for real computer networks I am interested in models of random graphs which are similar to the graphs of real computer networks. I am not sure if the common well-studied $G(n,p)$ model ($n$ vertices, each possible edge is selected with probability $p$) is good for studying real computer networks (is it?).

  what models of random graphs are useful for understanding computer networks araising in practice?

More generally, what other models of finite random graphs (other than those equivalent to the $G(n,p)$ model) have been studied in the literature? (An ideal answer would be a pointer to a survey for studied models of finite random graphs.)

This survey, The structure and function of complex networks by Newman, reviews techniques and models for real complex networks including concepts such as small-world effect, degree distributions, and random graph models. Also, the same author has a nice paper, Random graphs as models of networks, about adaptations of random graphs to model real networks.

References:

1) Random graphs as models of networks, M. E. J. Newman, in Handbook of Graphs and Networks, S. Bornholdt and H. G. Schuster (eds.), Wiley-VCH, Berlin (2003)

2) The structure and function of complex networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003)


What are the major research issues in distributed transactions? Background: Transaction processing has been a traditional research topic in database theory.
Nowadays distributed transactions are popularized by the large-scale distributed storage systems which typically involve data partition (also called sharding) and data replication.

What are the major research issues in distributed transactions?
Are there well-known theories and solutions which need (theoretical) improvement?

Any references are appreciated.

There are many research areas both in the theory and practice of distributed databases.

One of the main practical challenges is that of implementing efficient concurrency control mechanisms for distributed and geo-replicated databases. In order to execute
transactions efficiently, such mechanisms can provide weaker guarantees than serialisability, which requires that transactions appear to be executed sequentially. An alternative to serialisability is that of settling for Snapshot Isolation [1], but this has been proved to scale poorly to geo-replicated and distributed systems.
At the current state of the art, two different variants of Snapshot Isolation (SI) have been defined to deal with concurrency control in geo-replicated systems:
Parallel Snapshot Isolation (PSI) [2], and Non Monotonic Snapshot Isolation (NMSI) [3,4].
As for what it concerns distributed databases (i.e. where data are sharded among different sites), a variant of snapshot isolation
for distributed system has been proposed very recently [5].

Having different notions of isolation levels which provide weaker guarantees than serialisability, another important question is that of writing programs in a way so that executions still appear to be serialisable. A sound criterion for Snapshot Isolation has been devised in [1]. Some people in my group are currently working on devising a reasonable criterion for PSI.

Another relevant question, both from a theoretical and practical point of view, is that of transaction chopping. Basically chopping is a static analysis techniques in which  coarse-grained transactions are broken down into smaller, fine grained transactions. For serialisability, this question has been tackled in [6], and the resulting theory has been applied to give a practical implementation in [7].

From the point of view of theoretical foundations of distributed databases, there has been some proposal to use techniques from the weak memory models community [8] to define formally the behaviour of transactions. In [9] the authors give a formal notion of behaviour for transactions; the same approach have been used in [10] to specify the behaviour of replicated data types.

Recently, I and some colleagues of mine (Alexey Gotsman and  Hongseok Yang) built, starting from the techniques developed in [8,9,10], a theoretical framework for specifying the observable behaviour of consistency levels for geo-replicated databases. We successfully employed the framework to give an axiomatisation of
SI, PSI and NMSI, each of which we have proved to be correct with respect to a simple implementation. We also exploited the resulting theory to devise a
chopping criterion for PSI. These results will hopefully we published in the foreseeable future.

Please do not hesitate to write me if you have other questions.
Hope this helps,

Andrea Cerone.

References:

[1] Fekete et al, Making Snapshot Isolation Serializable (2005)

[2] Sovran et al, Transactional Storage for Geo-replicated Systems (2011)

[3] Arkedani et al, Non-Monotonic Snapshot Isolation: scalable and strong consistency for geo-replicated transactional systems (2013)

[4] Arkedani et al, On the Scalability of Snapshot Isolation (2013)

[5] Binnig et al, Distributed snapshot isolation: global transactions pay globally, local transactions pay locally

[6] Shasha et al, Transaction chopping: algorithms and performance studies (1995)

[7] Zhang et al, Transaction chains: achieving serializability with low latency
in geo-distributed storage systems (2013)

[8] Alglave, A formal hierarchy of weak memory models (2012)

[9] Buckhardt et al, Understanding Eventual Consistency (2013)

[10] Buckhardt et al, Replicated Data Types: Specification, Verification, Optimality (2014)


FPTAS for Number Partition Problem I've been given a task to implement two algorithms (an exact algorithm and fully polynomial approximation scheme) for number partitioning problem. I found out that I can use some modification of heuristic approach (like complete differencing tree method) or just plain brute-force for the former, but I have a lot of trouble with the latter... can anyone point some resources where FPTAS for NPP is discussed or guidelines how to construct one?

Cheers

http://en.wikipedia.org/wiki/Partition_problem mentions two textbooks which cover the subject:

Hans Kellerer; Ulrich Pferschy; David Pisinger (2004), Knapsack problems, Springer, p. 97, ISBN 9783540402862

Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 0-471-92420-2. MR 1086874.


UnambiguousSAT reductions Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other.

Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but with the promise that there is $\leq 1$ solution (that is, it is in $\mathsf{PromiseUP}$). Valiant-Vazirani gives a randomized reduction from SAT to USAT.

For some natural problem $\Pi$, let U$\Pi$ is the corresponding promise problem in $\mathsf{PromiseUP}$, and suppose that $\Pi$ randomly reduces to U$\Pi$.

Is it reasonable to expect reduction from U$\Pi$ to USAT and vice versa? Would that mean $\mathsf{PromiseUP}$ has complete problem?

In general if USAT is in $\mathsf{RP}$ then $\mathsf{NP}=\mathsf{RP}$. Can we get something similar for U$\Pi$ as above?

"Is it reasonable to expect reduction from ..."

unambiguous$\Pi$ to unambiguousSAT  ?

Yes, since SAT is NP-hard under reductions that preserve the number of solutions.

"and vice versa" ?
$\Pi$ is NP-complete and you've assumed that U$\Pi$ "has a randomized reduction from $\Pi$", so there is

a randomized reduction from USAT to U$\Pi$, since there's one from SAT to U$\Pi$.  For most natural problems, if U$\Pi$ is non-trivial then one can find a simple reduction from SAT to $\Pi$ that preserves number of solutions.  In particular, it's reasonable to expect a reduction from USAT to U$\Pi$.  However, I have no clue regarding whether-or-not there's necessarily

a better reduction from USAT to U$\Pi$ (than the one from $\Pi$ to U$\Pi$).

"Would that mean promiseNP has a complete problem?"  Yes, since it follows

from NP having complete languages that promiseNP unconditionally does too.

"In general if" unambiguousSAT "is in RP then NP=RP."

"Can we get something similar for" unambiguous$\Pi$?

Yes, as follows:

By NP-hardness of U$\Pi$ under randomized reductions,  NP $\subseteq$ BPP .    By search-to-decision, probabilistic polynomial-time algorithms can solve all of FNP.  By the definition of FNP,

one can efficiently deterministically check whether-or-not an alleged witness is valid.

Finally, if there are no valid witnesses, then one cannot incorrectly find such a witness.


Runtime of Grover's algorithm What is the time complexity (not query complexity) of Grover's algorithm?  It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration requires use of the reflection operation which in turn takes time $\Omega(\log(N))$ using any standard set of universal gates.

The problem is, I can't find even a single reference which says the time complexity of Grover's algorithm is $\Omega(\log(N) \sqrt{N})$.  Wikipedia, and several other web pages, say $O(\sqrt{N})$ time complexity.  Grover's paper claims $O(\sqrt{N})$ "steps".

Am I missing something?  Perhaps people define the reflection operation to take unit time.  But that doesn't make sense to me because if we can play the game of allowing arbitrary unitaries to take unit time then there would be no difference between query complexity and time complexity.

The question is usually taken to be moot, for the following reason.  Grover's algorithm is a combinatorial search algorithm to find a solution to an arbitrary predicate.   While, yes, $\Theta(\log N)$ is the quantum gate complexity in each stage of the black-box algorithm, the predicate needs to be computed too.  The quantum gate complexity of that is $\Omega(\log N)$, because otherwise it wouldn't read the whole input and you could discard some of the input bits from the search.  On the other hand, an interesting predicate could take a lot more time than that.  Hence, the number of calls to the predicate is taken to be the standard coin, just as it is for the classical analogue of Grover's algorithm, namely random guessing.


Algorithm for detecting closed region on a plane First off, I just want to say that I am not well versed in computational geometry, so if this question has some obvious answer, I apologize.  I tried googling it but I could not find anything.

My question: Given an input of a plane with 1 or more line segments, is there an efficient algorithm for determining if there exists a closed region on this plane?  For example, see the following picture:

benjamindicken.com/closed_region.png

On this plane, there exists one closed region.  I would like the algorithm to return true if a closed region exists, and false if one does not.

At the moment, I only need this algorithm to determine if a closed region exists or not, but I could foresee needing this to return the number of closed regions as well.

Thanks for your help.

Let $S$ be a set of segments with the property that no two segments have an intersection with positive length. The set $S$ bounds a region if and only if the intersection graph of the segments in $S$ has a cycle.


Proving lower bounds by proving upper bounds The recent breakthrough circuit complexity lower-bound result of Ryan Williams provides a proof technique that uses upper-bound result to prove complexity lower-bounds. Suresh Venkat in his answer to this question, Are there any counter-intuitive results in theoretical computer science?, provided two examples of establishing lower-bounds by proving upper-bounds.

  What are the other interesting results for proving complexity lower-bounds that was obtained by proving complexity upper-bounds?
  Is there any upper-bound conjecture that would imply $NP \not\subseteq P/poly$ (or $P \ne NP$)?

One could turn the question around and ask what lower bounds aren't proved by proving an upper bound. Almost all communication complexity lower bounds (and streaming algorithm lower bound and data structure lower bounds that rely on communication complexity arguments) are proved by showing that a communication protocol can be constructively turned into an encoding scheme, with the length of the encoding depending on the communication complexity of the protocol, and the lower bound for the protocol follows from the fact that you cannot encode all n bit messages using n-1 bits or fewer.

The Razborov-Smolensky circuit lower bounds work by showing how to simulate bounded-depth circuits by low-degree polynomials.

A couple of candidates of lower bounds that are not proved with an upper bound could be the time hierarchy theorem (although, to get the tightest bounds, one needs an efficient universal turing machine, which is a non-trivial algorithmic task) and the proof of AC0 lower bounds using the switching lemma (but the cleanest proof of the switching lemma uses a counting/incompressibility/Kolmogorov-complexity)


Selection in a genetic algorithm I have a working genetic algorithm which uses a few genetic operators on pairs of individuals.

These two individuals are selected by fitness-proportional (roulette-wheel) selection, that is, an individual's likelihood of being selected is proportional to its fitness.

The way a pair is selected is simply by selecting a single individual from the population twice. Sometimes, the same chromosome can be selected twice, and then all genetic operators are simply operating on two copies of the same individual.

For example, crossover is meaningless in this case.

My question is, should I take measures to ensure the pair that are selected are not equal?

Or should I mitigate the problem by performing operators on single individuals first (such as mutation), so the pair are more likely to be different when it comes to things like crossover?

Or should I ignore the problem completely, "let nature take its course", and allow an individual to breed with itself?

The usual course is to feign ignorance and let it happen.

However, it is generally bad, so you'd ideally take steps to make it less likely to happen. The brute force solution is of course to simply check for equality and reselect one of the parents if necessary. You can do this, but there's a decent chance that if all you do is throw away the duplicates, the overhead of checking every time may start to limit the returns you get.

Another way to minimize these effects is to use a selection operator that is less biased. Roulette-wheel selection has a very high probability of selecting from only the handful of best individuals in many cases (depends on the particular distribution of fitness values of course). You're probably better off starting off with tournament selection as your default choice. It will give you a wider coverage of the parent pool, which keeps more diversity around for longer. Also, you can tweak the knobs a bit by looking at how you do environment selection (replacing old parents by some combination of old parents and new offspring). The more strongly elitist you are, the faster you'll converge, which you usually want to avoid.

One of the best black-box GAs out there is CHC (Eshelman, 1990) (always be wary of black boxes, but if you're going to treat the method as one, CHC seems to be one of the more effective ones). CHC is worth looking at, partly because it is a pretty good search algorithm, and partly because it provides a window into the types of things you can do to a standard GA to try and exert a bit more control over what it's doing.

CHC takes a very odd approach. It pairs parents completely randomly and without replacement. This means that every parent is selected exactly once (recombination produces two offspring, so each parent is selected as part of one mating pair giving N/2 pairs * 2 offspring/pair = N offspring). Crossover is "HUX" or half-uniform crossover, which produces offspring maximally distant from their parents. Combined, these give a very explorative search. In addition though, it is maximally elitist. Of the N parents and N offspring, the best N of the total are kept. This drives convergence very quickly -- very exploitative. Finally, parents produce no offspring at all if they are closer than a threshold value to one another. The threshold starts at L/4 (L=length of encoding), and is decremented each time zero offspring are produced in a generation. Thus the number of offspring produced in each generation is variable, and this number is used to determine how much the population has converged. At some point, when it has converged sufficiently (when the threshold reaches zero), CHC performs a "cataclysmic mutation" in which all but one individual have 35% of their bits randomly flipped and the process restarts.

Unfortunately the original paper describing CHC is only available in dead-tree form as far as I know. However, you can find a few descriptions online and in other papers that reference it.


Covering string by palindromes Given a string $w=\sigma_1\sigma_2\ldots\sigma_n$, a palindrome cover is a sequence $p_1p_2\cdots p_m$ of words $p_i$ such that $p_1p_2\cdots p_m = w$ and such that each $p_i$ is a palindrome.

How hard is it to find the size minimal palindrome cover? (this seems doable by dynamic programming, but I'm not sure it works).
Does the problem become harder if given as input is also a bound $b$ on each palindrome length?

Consider the simple greedy algorithm, which always takes the longest palindrome which starts at the current location. For example, if $w=1213312$, then it'll output $(121)\cdot(33)\cdot(1)\cdot(2)$, while the optimal cover is $(1)\cdot(213312)$.

Does the greedy algorithm provide 2-approximation for the problem?

This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example:

A subquadratic algorithm for minimum palindrome factorization by Fici et al

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings by Rubinchik and Shur.


if I were to define a new complexity class how should I start? If I wanted to define my own complexity class would you first define it as a set of problems with reductions to those problems? How would one go about doing this?

First you would search around and check e.g. the complexity zoo, because many, many classes are already defined and you don't want to redefine one that is already known by some other name.

The ways I know of are:

Define a complete problem and a notion of reduction; the class consists of all problems so reducible to that problem. This is usually only possible for so-called "syntactic" complexity classes -- see the question "Semantic vs Syntactic Complexity Classes" -- which tend to also have a nice definition in terms of a model of computation. (E.g. $\mathsf{NP}$ can be defined as all languages that are polytime mapping-reducible to $\mathsf{3SAT}$; or as all languages decidable by a polytime nondeterministic TM.)
Define a model of computation and what it means for that model to decide/compute a language/problem; the class consists of all languages/problems for which there exists such a model of computation that decides/computes the language/problem. This works for probabilistic classes like $\mathsf{BPP}$, but also for more exotic models like quantum classes, circuits, interactive protocols, or finite automata for that matter. This is probably the method you'd go for, and for more detail, maybe look at examples of all the above types (e.g. $\mathsf{BPP, BQP, ACC, IP, MA, PCP, REGULAR}$).

Perhaps those more expert than I am can say if there are other major methods that are missing, or expand on these if needed.


Where to find info on (polytime) approximability of various discrete optimization problems? Where to find info on (polytime) approximability of  various discrete optimization problems?
Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of various optimization problems?

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/


Counting words accepted by a regular grammar Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted?  Both "with exactly n letters" and "with at most n letters" are of interest.

Margareta Ackerman has two papers on the related subject of enumerating words accepted by an NFA, but I wasn't able to modify them to count efficiently.

It seems like the restricted nature of regular languages should make counting them relatively easy -- I almost expect a formula more than an algorithm  Unfortunately my searches so far haven't turned up anything, so I must be using the wrong terms.

For a DFA, in which the initial state is state $0$, the number of words of length $k$ that end up in state $i$ is $A^k[0,i]$, where $A$ is the transfer matrix of the DFA (a matrix in which the number in row $i$ and column $j$ is the number of different input symbols that cause a transition from state $i$ to state $j$). So you can count accepting words of length exactly $k$ easily, even when $k$ is moderately large, just by calculating a matrix power and adding the entries corresponding to accepting states.

The same thing works for accepting words of length at most $k$, with a slightly different matrix. Add an extra row and column of the matrix, with a one in the cell that's both in the row and the column, a one in the new row and the column of the initial state, and a zero in all the other cells. The effect of this change to the matrix is to add one more path to the initial state at each power.

This doesn't work for NFAs. I suspect the best thing to do is just convert to a DFA and then apply the matrix powering algorithm.


Efficient flow problem for a complex integer program I have a bunch of marbles each with some weight (they can also have negative weights). I want to pick the nodes such that the weight is maximized. The only rule is that if I pick X1 and X2 I have to pick X1,2 as well. Also if I pick X1,X2,X3 then I have to pick not only X1,2 and X2,3 and X1,3 but also X1,2,3. The other thing is that I cannot pick X1,2 unless I pick both X1 and X2.

It is easily solvable by integer programming but I am wondering if there is any network flow solution that is more efficient?

Some clarification:
for every X1 and X2 there is always a X1,2 marble (but may have 0 or negative weight).

The input is just the list of marbles and their weights [(X1:W1), (X2:W2), (X1,2:W1,2),...]

More Updates
Suresh pointed out that the input size is very large and I agree. In the problem that I am solving I only have 4 layers. I mean I have up to X(i,j,k,l) and everything above it with 5 or more subscripts has a weight 0.

Isn't this problem NP-complete?

Start with a graph $G$. Make $x_i = 1 \ \ \forall i$, where $i$ is a vertex of $G$. Now, for each edge $(i,j)$ of $G$, make $x_{i,j} = -3$. Otherwise, make $x_{i,j}=0$. Give weight 0 to all three- and four-level marbles. To maximize your objective function, you want to pick as many marbles as you can so long as you don't take two marbles connected by an edge. This is the maximum independent set problem, which is NP-complete.


Problems with efficient solution except for a small fraction of inputs The halting problem for Turing machines is perhaps the canonical undecidable
  set. Nevertheless, we prove that there is an algorithm deciding almost
  all instances of it. The halting problem is therefore among the growing collection
  of those exhibiting the “black hole” phenomenon of complexity theory,
  by which the difficulty of an unfeasible or undecidable problem is confined
  to a very small region, a black hole, outside of which the problem is easy.

  [Joel David Hamkins and Alexei Miasnikov, "The halting problem is decidable on a set of asymptotic probability one", 2005]

Can anyone provide references to other “black holes” in complexity theory, or another place where this or related concepts are discussed?

I'm not sure whether this is what you're looking, but the phase transition in random SAT is an example. Let $\rho$ be the ratio of number of clauses to number of variables. Then a random SAT instance with parameter $\rho$ is very likely to be satisfiable if $\rho$ is less than a fixed constant (near 4.2) and is very likely to be unsatisfiable if $\rho$ is a little bit more than this constant. The "black hole" is the phase transition.


Upper and lower bound of binomial summation For $n>1$ and $~0<p \leq 1$,   can we upper and lower bound the following   binomial series in terms of $n$ and $p$ $$\Sigma_{i=\lceil p n \rceil}^n {n \choose i} (p )^i(1-p)^{(n-i)}$$

Let me denote the sum as $S_{n,p}$. It gives the probability that a random sample from the binomial distribution $B(n,p)$ exceeds its expected value.

For $0<p<1$ constant, the central limit theorem tells you that $B(n,p)$ looks like the normal distribution $N(pn,p(1-p)n)$ for large $n$. Since this is symmetric, $S_{n,p}$ will be approximately $1/2$ as noted in usul’s comment.

This can be quantified using the Berry–Esseen theorem: applying it to $n$ indicator random variables with mean $p$, variance $p(1-p)$, and third moment $(p^2+(1-p)^2)p(1-p)\le p(1-p)$, gives

$$\left|S_{n,p}-\tfrac12\right|\le\frac C{\sqrt{p(1-p)n}}$$

for a certain constant $C<1/2$.


Easy problems with hard counting versions Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-SAT and number of topological sortings.

  Are there any other important classes (say examples in lattices, trees, number theory and so on)? Is there a compendium of such problems?

There are many types of problems in $P$ which have $\#P$-hard counting versions.

  Is there a version of a natural problem in $P$ that is more completely understood  or simpler than general bipartite perfect matching (please include details on why simpler such as being provably in the lowest classes of the $NC$-hierarchy and so on) in some other area (such as number theory, lattices) or at least for particular simple bipartite graphs, whose counting version is $\#P$-hard?

Examples from lattices, polytopes, point counting, number theory will be appreciated.

One interesting example from number theory is expressing a positive integer as a sum of four squares.  This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at https://dx.doi.org/10.1002%2Fcpa.3160390713), and if I remember correctly, there is now even a deterministic polynomial-time solution.  But counting the number of such representations would allow you to compute the sum-of-divisors function $\sigma(n)$, which is random polynomial-time equivalent to factoring $n$. So the counting problem is probably hard.


Axioms of Minimum Size Resolution Refutations Let $\phi$ be an unsatisfiable CNF formula and let $\Pi$ be a resolution refutation of $\phi$ of minimum size. Let $\psi$ be the subformula of $\phi$ containing the clauses that actually appear as axioms in $\Pi$. Is there anything interesting that can be said about $\psi$?

Some specific questions:

Is $\psi$ minimally unsatisfable? (i.e., are all proper subsets of $\psi$ satisfiable?)
Are all variables appearing in $\psi$ necessary for unsatisfiability? (i.e., is there an assignment to all but one variable that does not falsify any clauses in $\psi$?)
Is $\psi$ a minimum unsatisfiable core of $\phi$?

All of these properties seem unlikely to hold in general but I cannot think of any counterexamples.

With the caveat that I am posting this quickly in a sleep-deprived state, I think the answer is "no" to all three questions.

Take the pigeonhole principle formulas PHP^m_n for m pigeons and n holes. The miniminal length of a resolution refutation for m = n+1 is exp(Omega(n)) by Haken. However, Buss and Pitassi proved that for m = exp(\sqrt(n log n)) pigeons (or something in that range) there are refutations of length exp(\sqrt(n log n)) (or something in that range). Clearly, then, the shortest resolution refutation in this case is using lots of redundant clauses (from the point of view of minimal unsatisfiability).


possible bridge between group growth theory and complexity theory? RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with complexity theory. (of course there are other deep known links between TCS/ group theory.)

  has anyone seen a link between group growth theory and complexity theory? eg have any complexity class separations been found expressible in this framework, etc?

(eg conceivably there could be an intermediate link via boolean circuits etc.)

Maybe this is along the lines you are looking for: I wrote a blog post here explaining how you can use Gromov's theorem on groups of polynomial growth to show that non-uniform read once automata are no more powerful than linear time Turing machines for deciding word problems of groups.

The basic idea is that groups with non-uniform read once automata necessarily have polynomial growth (i.e., the number of elements with a word of length at most $r$ is $O(r^k)$ for some fixed $k$). By Gromov's theorem, this implies that the group is virtually nilpotent. There is work giving linear time algorithms for the word problems of such groups, so that's that.


BWT: is it possible to predict the next character in a sequence? A very simple questions. Let B be the BWT (Burrows–Wheeler transform) of a string S. My question is, due to  "grouping" of consecutive characters in BWT, is it possible to somehow know the number of equal characters that follow given the first character of its kind (or at least some lower bound on the number of such characters). So let say B=...caaaaabaccccccacc... then, is it possible to know that after the first a there will be at least 2 consecutive a's or maybe the exact number of a's that follow?

Or alternatively one can pose a complementary question, a flip side of the above question (I write the question in order to better describe the problem):

Is there a better way to find breaks in BWT aside from checking each character and comparing it with the previous one. That is, let say I want to locate "ab" break. I would need to go from left to right and compare second character with the first one and then third with the second and so on until I find out where the pair mismatches. Is there a way to check every second character and come to the same result, because if this is possible then there exist a lower bound on the number of same consecutive characters (which is 2)?

In general, no, but it's difficult to prove a negative given that there might be some data structure equivalent to a BWT that provides the prediction capability.

The L vector in the BWT is simply a list of the input string's characters sorted by their following context, i.e. the suffix that begins immediately after each character.  Its information content is inversely related to how well this following context predicts the character preceding it.

This predicability is present in many types of text and in many models for generating text, but it's easy to fool adversarially if you have some algorithm like you describe in your second paragraph.  For instance, if your algorithm has only read a portion of the input (you don't specify how it operates, so I'm guessing), I believe it's possible to extend a string in such a way as to spoil any context where you think the prediction is 100%.


What was the original intent for the creation of Lambda calculus? I've read that initially Church proposed the $\lambda$-calculus as part of his Postulates of Logic paper (which is a dense read). But Kleene proved his "system" inconsistent after which, Church extracted relevant things for his work on "effective computability" and abandoned his prior work on logic.

So as I understand it, the $\lambda$-system and its notations took form as part of something to do with logic. What was Church initially trying to achieve that he forked off from later? What were the initial reasons for creating $\lambda$-calculus?

He wanted to create a formal system for the foundations of logic and mathematics that was simpler than Russell's type theory and Zermelo's set theory.

The basic idea was to add a constant $\Xi$ to the untyped lambda calculus (or combinatory logic) and interpret $XZ$ as expressing "$Z$ satisfies the predicate $X$" and $\Xi XY$ as expressing "$X\subseteq Y$". With rules expressing these intentions one can then interpret the ${\to}{\forall}$-fragment of intuitionistic predicate logic and unrestricted comprehension, the only problem being that by Curry's paradox, every $X$ is derivable.

See p. 7 of:

Cardone and Hindley, History of Lambda-calculus and Combinatory Logic, 2006:
http://www.users.waitrose.com/~hindley/SomePapers_PDFs/2006CarHin,HistlamRp.pdf

As well as the introduction to:

Barendregt, Bunder and Dekkers, Systems of Illative Combinatory Logic Complete for First-Order Propositional and Predicate Calculus, JSL 58-3 (1993):
http://ftp.cs.ru.nl/CompMath.Found/ICL1.ps


A probabilistic set with no false positives? So, Bloom filters are pretty cool -- they are sets that support membership checking with no false negatives, but a small chance of a false positive. Recently though, I've been wanting a "Bloom filter" that guarantees the opposite: no false positives, but potentially false negatives.

My motivation is simple: given a huge stream of items to process (with duplicates), we'd like to avoid processing items we've seen before. It doesn't hurt to process a duplicate, it is just a waste of time. Yet, if we neglected to process an element, it would be catastrophic. With a "reverse Bloom filter", one could store the items seen with little space overhead, and avoid processing duplicates with high probability by testing for membership in the set.

Yet I can't seem to find anything of the sort. The closest I've found are "retouched Bloom filters", which allow one to trade selected false positives for a higher false negative rate. I don't know how well their data structure performs when one wants to remove all false positives, however.

Anyone seen anything like this? :)

One answer is to use a big hash table and when it fills up start replacing elements in it rather than finding (nonexistent) empty slots elsewhere for them. You don't get the nice fixed-rate of false answers that you do with Bloom filters, but it's better than nothing. I believe this is standard e.g. in chess software for keeping track of positions that have already been searched.


Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075).

The authors give a characterization of strong approximation resistance which I don't completely understand.

Given a measure $\Lambda$ in $R^{k + {k \choose 2}}$, (the coordinates of a point in this space are written $x_1, x_2, ..., x_k, x_{(1,2)}, ... x_{(i,j)}, ... , x_{(k-1, k)}$) and some subset $S \subset [k]$,  they define $\Lambda_S$ as the measure projected onto the coordinates of $S$.

I can think of two such interpretations for $\Lambda_S$. First fix $k=4$ so that $\Lambda$ is in $R^{10}$. Our coordinates are $1, 2, 3, 4, (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$. Fix $S = \{1, 2, 3\}$.

Interpretation 1: Under one interpretation, the measure $\Lambda_S$ should be projected using the coordinates $1$ and $2$ and $3$ only.

Interpretation 2: Under the other interpretation we should also include the "pair" coordinates so we should project using $1$, $2$, $3$, $(1,2)$, $(1,3)$, $(2,3)$.

I'm thinking that the second interpretation is the correct one. This is because the definition is reformulated in terms of matrices in definition 2.11 on page 19. In this formulation, we have a measure $\zeta$ on a subspace of matrices in $R^{(k+1)\times(k+1)}$ analogous to the measure $\Lambda$, but given $S$, projection measure $\zeta_S$ is defined by taking the submatrix formed by restricting to rows and columns whose indices are in $S$. But in this formulation, the entry $i,j$ of the matrix corresponds to the coordinate $x_{(i,j)}$.

Am I correct? Or is there some way to reconcile the first interpretation with the matrix analogue?

Section 1 of the paper, in which the first definition appears, is introductory. The formal development starts at Section 2. The part of the paper starting at Section 2 is completely self-contained. Therefore, if there is any mismatch between a definition in Section 1 and a definition elsewhere, the latter is the correct one.

In theoretical computer science, papers are published in conferences. Conference reviewers cannot be expected to read 50-page strong manuscripts, and so the argument has to be described in an elaborate introduction. This is why there is so much technical content in Section 1. The development there is simplified and more leisurely to facilitate reading. The authoritative part of the paper is Section 2 and forward.


Do graphs with large number of paths contain large chain minor? Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.

Note that the number of paths between two endpoints of a $k$-chain is $2^k.$

Question: Let $G$ be a simple graph on n nodes and let $s$ and $t$ be two nodes of $G.$ Suppose that number of (simple) paths from s to t in $G$ is at least $n^k.$ Then, is it possible to obtain a $\Omega(k)$-chain from $G$ with ($s$ and $t$ as endpoints) by a sequence of deletion and contraction of edges?

If the answer is positive then the second part of question is whether there is an efficient algorithm to obtain such a large chain.

I would be equally happy with $\sqrt k$-chain or $k^\alpha$ for any $\alpha >0.$

I would appreciate any partial answer or any intuition on whether such a conjecture should hold.

I had posted this on math overflow few days back. Someone suggested to post it here as well.

https://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor

Seems this is a FPT algorithm for a fixed $k$. First of all we can just consider a block which contains $s,t$. If we have a $k\times k$ grid minor which contains $s,t$ then we can find the corresponding chain. As otherwise, as Chekuri et al. shown, the graph has tree width at most $O(k^{1/\delta})$ where $\delta > 0$ is some constant. So we can compute the tree decomposition of graph then check whether that chain exists or not. I'm not sure if with usual dynamic programming on graphs of bounded tree width is possible to find the chain. Also if is not bounded tree width, their algorithm can find the corresponding grid in polynomial time.

P.S: Note that I didn't use the fact that there are $n^k$ s-t paths, may be by some trick inside this fact is possible to obtain better algorithm.


Find all nearby points in a set, for each element of the set Given a finite set $S$ of points in $\mathbb R^p$ and a number $\rho$, my collaborators and I want to find, for each $s\in S$, the other points in $S$ that are within $\rho$ of $s$. Of course there's the obvious $O(|S|^2)$ algorithm, and we also came up with something (roughly, sort in each dimensions, then for each dimension and for each element of $S$ mark nearby points in some sparse matrices, and then combine the sparse matrices) that has better running time under certain assumptions, but not in the worst case.

I feel that this must be a standard problem, but I haven't been able to find references. I was wondering if someone here knows what I should search for or can suggest a good reference to start from?

Thanks in advance!

I think what you are looking for is the Fixed-radius near neighbors problem.


Triangular Mesh Reordering - Huddling Triangles I am given a 3D model represented by its outside surface as a triangular mesh (hollow inside). The model is mostly 2-manifold, so that each triangle edge is shared by exactly 2 triangles. This, naturally, means that every triangle has exactly 3 neighbors (except at non-manifold bare edges, but we can ignore this case for now).
The mesh is represented as an array of triangles. Assume that I know the indices of each triangle's neighbors.

Is there an algorithm for reordering the triangles such that most triangles are very close to all 3 their neighbors in this 1D ordering?

I suspect this is an NP complete problem, but I wonder if there are approximation algorithms.

Here's what I found but all seem unsatisfactory:

Space-filling Hilbert-like curves (e.g. for triangular grids).
Even if I could generate such a curve for arbitrary topology (non-regular) meshes, these do not preserve or minimize overall locality:

  Both the Hilbert curve and its discrete approximations are useful because they give a mapping between 1D and 2D space that fairly well preserves locality. If (x,y) are the coordinates of a point within the unit square, and d is the distance along the curve when it reaches that point, then points that have nearby d values will also have nearby (x,y) values. The converse can't always be true. There will sometimes be points where the (x,y) coordinates are close but their d values are far apart.

What is guaranteed, is that close points on the 1D curve will tend to be close in 2D space, but the converse is not true (i.e. close points in 2D space will not necessarily be close on the 1D curve) and that is what I want .

Adjacency Matrix Bandwidth Reduction
Another approach I considered was creating the adjacency matrix for the triangle neighborhood graph where each node in the graph is a triangle and there is an edge between each pair of neighboring triangles.
The adjacency matrix is symmetric very sparse since each node has (at most) 3 neighbors.

I'd like an algorithm to reorder the columns and rows of the matrix such that most of the sparse entries are as close to the diagonal as possible. This is called matrix bandwidth reduction, and is an NP-complete problem, but it has several well known algorithms such as the reverse Cuthill–McKee algorithm (RCM). This algorithm and its variants are essentially variants of the breadth-first-search algorithm.

However, IIUC, in my case the graph is mostly locally planar, so the algorithm will essentially generate a spiral of interleaved triangles from and around the start node. This spiral will cause each triangle to get farther and farther away from at least 1 but sometimes all 3 of its immediate neighbors by a distance that is proportional to the circumference of the spiral at that point.

I prefer fewer long non-local hops to many shorter non-local hops.

Am I missing anything? Is there another approach I could take?

There appears to be a solution used by game programmers that both optimizes graphics hardware cache utilization and facilitates mesh connectivity compression. It is Tom Forsyth's Linear-Speed Vertex Cache Optimisation described here: https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html

The algorithm uses a heuristic based on modeling the GPU vertex cache to produce a sequence of triangles with high locality and vertex reuse. The pattern produced is reportedly not unlike the Hilbert curve. The algorithm has linear time complexity.

The master thesis "Efficient Triangle Reordering for Improved Vertex Cache Utilisation in Realtime Rendering" (http://www.martin.st/thesis/) contains a C++ implementation and also seems to describe an improved algorithm.


A special class of languages: “circular” languages. Is it known? Define the following class of "circular" languages over a finite alphabet Sigma. Actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, that's a different class of languages.

A language L is circular iff for all words $w$ in $\Sigma^*$, we have:

$w$ belongs to L if and only if for all integers $k > 0$, $w^k$ belongs to L.

Is this class of languages known? I am interested in the circular languages which are also regular and in particular in:

a name for them, if they are already known
decidability of the problem, given an automaton (in particular: a
DFA), whether the accepted language obeys to the above definition

In the first part, we show an exponential algorithm for deciding circularity. In the second part, we show that this the problem is coNP-hard. In the third part, we show that every circular language is a union of languages of the form $r^+$ (here $r$ could be the empty regexp); the union is not necessarily disjoint. In the fourth part, we exhibit a circular language which cannot be written as a disjoint sum $\sum r_i^+$.

Edit: Incorporated some corrections following Mark's comments. In particular, my earlier claims that circularity is coNP-complete or NP-hard are corrected.

Edit: Corrected normal form from $\sum r_i^*$ to $\sum r_i^+$. Exhibited an "inherently ambiguous" language.

Continuing Peter Taylor's comment, here's how to decide (extremely inefficiently) whether a language is circular given its DFA. Construct a new DFA whose states are $n$-tuples of the old states. This new DFA runs $n$ copies of the old DFA in parallel.

If the language is not circular then there is a word $w$ such that if we run it through the DFA repeatedly, starting with the initial state $s_0$, then we get states $s_1,\ldots,s_n$ such that $s_1$ is accepting but one of the other ones is not accepting (if all of them are accepting then then the sequence $s_0,\ldots,s_n$ must cycle so that $w^*$ is always in the language). In other words, we have a path from $s_0,\ldots,s_{n-1}$ to $s_1,\ldots,s_n$ where $s_1$ is accepting but one of the others is not accepting. Conversely, if the language is circular then that cannot happen.

So we've reduced the problem to a simple directed reachability test (just check all possible "bad" $n$-tuples).

The problem of circularity is coNP-hard. Suppose we're given a 3SAT instance with $n$ variables $\vec{x}$ and $m$ clauses $C_1,\ldots,C_m$. We can assume that $n = m$ (add dummy variables) and that $n$ is prime (otherwise find a prime between $n$ and $2n$ using AKS primality testing, and add dummy variables and clauses).

Consider the following language: "the input is not of the form $\vec{x}_1 \cdots \vec{x}_n$ where $\vec{x}_i$ is a satisfying assignment for $C_i$". It is easy to construct an $O(n^2)$ DFA for this language. If the language is not circular then there is a word $w$ in the language, some power of which is not in the language. Since the only words not in the language have length $n^2$, $w$ must be of length $1$ or $n$. If it is of length $1$, consider $w^n$ instead (it is still in the language), so that $w$ is in the language and $w^n$ is not in the language. The fact that $w^n$ is not in the language means that $w$ is a satisfying assignment.

Conversely, any satisfying assignment translates to a word proving the non-circularity of the language: the satisfying assignment $w$ belongs to the language but $w^n$ does not. Thus the language is circular iff the 3SAT instance is unsatisfiable.

In this part, we discuss a normal form for circular languages. Consider some DFA for a circular language $L$. A sequence $C = C_0,\ldots$ is real if $C_0 = s$ (the initial state), all other states are accepting, and $C_i = C_j$ implies $C_{i+1} = C_{j+1}$. Thus every real sequence is eventually periodic, and there are only finitely many real sequences (since the DFA has finitely many states).

We say that a word behaves according to $C$ if the word takes the DFA from state $c_i$ to state $c_{i+1}$, for all $i$. The set of all such words $E(C)$ is regular (the argument is similar to the first part of this answer). Note that $E(C)$ is a subset of $L$.

Given a real sequence $C$, define $C^k$ to be the sequence $C^k(t) = C(kt)$. The sequence $C^k$ is also real. Since there are only finitely many different sequences $C^k$, the language $D(C)$ which is the union of all $E(C^k)$ is also regular.

We claim that $D(C)$ has the property that if $x,y \in D(C)$ then $xy \in D(C)$. Indeed, suppose that $x \in C^k$ and $y \in C^l$. Then $xy \in C^{k+l}$. Thus $D(C) = D(C)^+$ can be written in the form $r^+$ for some regular expression $r$.

Every word $w$ in the language corresponds to some real sequence $C$, i.e. there exists a real sequence $C$ that $w$ behaves according to. Thus $L$ is the union of $D(C)$ over all real sequence $C$. Therefore every circular language has a representation of the form $\sum r_i^+$. Conversely, every such language is circular (trivially).

Consider the circular language $L$ of all words over $a,b$ that contain either an even number or $a$'s or an even number of $b$'s (or both). We show that it cannot be written as a disjoint sum $\sum r_i^+$; by "disjoint" we mean that $r_i^+ \cap r_j^+ = \varnothing$.

Let $N_i$ be the size of the some DFA for $r_i^+$, and $N > \max N_i$ be some odd integer. Consider $x = a^N b^{N!}$. Since $x \in L$, $x \in r_i^+$ for some $i$. By the pumping lemma, we can pump a prefix of $x$ of length at most $N$. Thus $r_i^+$ generates $z = a^{N!} b^{N!}$. Similarly, $y = a^{N!} b^N$ is generated by some $r_j^+$, which also generates $z$. Note that $i \neq j$ since $xy \notin L$. Thus the representation cannot be disjoint.


Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)? Is there a relation between  BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you're given a circuit for the function.

The paper:

https://eccc.weizmann.ac.il/report/2017/109/

shows that certain counterexamples to BBH would refute a non-uniform version of ETH (Circuit SAT has $2^{o(n)}$ size circuits). They conjecture something like that "non-uniform ETH for Circuit SAT <=> BBH is true".

Note in the other direction, if SETH is false for circuits, this would refute some version of BBH: we cannot possibly solve SAT for black boxes in $o(2^n)$ time.


Terminology about computation and Finite algebra I am looking for the name of something that may have one.

A finite algebra $\mathcal{A} = (E, \{f_1, f_2, \ldots, f_k\})$ is a non-empty set $E$ together with some functions $f_i$ from $E^{r_i} \to E$ where $r_i$ is a fixed integer (arity).

An $n$-term is a term on $n$ variables $x_1, \ldots, x_n$ over a finite algebra $\mathcal A$. A term is defined as usual by induction:

Any element of $E$ and the variables $x_1,\ldots, x_n$ are terms
If $t_1, \ldots, t_{r_i}$ are terms, then $f_i(t_1,\ldots, t_{r_i})$ is also a term.

An $n$-term $t$ computes a function $[t]\colon E^n \to E$ in an obvious way.

Terminology question: How do we call finite algebras such that for every function $f\colon E^n\to E$, there exists a term $t$ such that $[t] = f$?

Famous example:
 $$(\{0, 1\}, \{\land, \lor, \lnot\})$$

Famous co-example:
 $$(\{0, 1\}, \{\land, \lor\})$$

Such algebras are called functionally complete. Also, what you call terms are actually called polynomials. In standard terminology, term operations have a more restricted definition that allows variables and the basic operations $f_i$, but not constants from $E$. Algebras that satisfy the stronger condition that every operation is represented by this kind of a term are called primal. See e.g. Burris&Sankappanavar, A Course in Universal Algebra.


Partially Ordered CFG I'm looking for work about partially ordered context-free grammars. I've found one paper, which seems to simplify the problem too much (in addition to some technical mistakes, as far as I can tell). It defines the language of a  pom-CFG by reduction to a normal context-free grammar, which excludes some (otherwise) possible words from the language, I think.

Thus I'm looking for other work.

What I mean by partially ordered CFG

The production rules don't produce linear strings of symbols but partially ordered (multi) sets of symbols. Thus the "words" of the generated language are also partially ordered multi-sets of symbols. For example this:

  b-c
 /   \
a     d-a
 \   /
  a--

The possible linearizations of this partially ordered word are aabcda, abacda, abcada.

The described concept is known as graph grammars and dates back into the 1970ies. Searching for this yields a sufficient amount of references. The terms "Graph Transformation" and "Graph Rewriting" are also used. See e.g. Wikipedia on Graph Rewriting.


Why is Proof Checker required in Proof Carrying Code In the classical PLDI'98 paper by Necula, "The design and implementation of a certifying compiler", the high-level verifier uses:

VCGen to generate verification conditions (safety predicates)
First-order logic theorem prover to prove the conditions
LF proof checker to check the proof from step (2)

I am a bit confused by step (3). Why is it required at all? Will just (1) and (2) not suffice? Why don't we just trust the proof generated by a theorem prover?

The purpose of the proof checker is to minimise the trusted computing base.

By having a proof checker, neither the compiler nor the theorem prover need to be correct. The paper makes this point on Page 3:

Neither the compiler nor the prover need to be correct in order to be guaranteed to
detect incorrect compiler output. This is a significant advantage since the VCGen and
the  proof checker are significantly simpler than the compiler and the prover.

A proof checker is just a couple of lines of code, and can be hand-inspected for correctness. In contrast, an automated prover that performs well is extremely complex and unlikely to be correct, although with well-tested and widely used provers, the mistakes will be in edge cases that might not be easy to trigger.
Have a look at the 30k LOC C code that make up Lingeling, a state-of-the-art SAT solver to see just how complicated automated theorem provers can be. Without a proof checker, you'd have to prove correct that theorem prover. This is beyond whaty we can economically do in 2015.


Lower bounds on Gaussian complexity Define the Gaussian complexity of an $n \times n$ matrix to be the minimal number of elementary row and column operations required to bring the matrix into upper-triangular form. This is a quantity between $0$ and $n^2$ (via Gaussian elemination). The notion makes sense over any field.

This problem certainly seems very basic and it must have been studied. Surprisingly, I don't know of any references. So, I'll be happy with any reference there is. But, of course, the main question is:

Are there any non-trivial explicit lower bounds known?

By nontrivial I mean superlinear. Just to be clear: Over finite fields a counting argument shows that a random matrix has complexity order n^2 (a similar claim should be true over infinite fields). Hence, what we're looking for is an explicit family of matrices, e.g., Hadmard matrices. This is the same as with Boolean circuit complexity where we know that a random function has high complexity, but we're looking for explicit functions with this property.

This appears to be a very hard problem, related to a more widely-studied one.

Suppose we consider a square invertible matrix A, and define c(A) as the minimal number of elementary row operations needed to reduce A to the identity matrix.  This complexity measure is larger than the one Moritz suggests, so proving superlinear bounds for it can only be easier.

Now, row operations are reversible.  It follows that c(A) can be equivalently defined as the minimum number of row operations needed to produce A, starting from the identity matrix.

Notice that producing A in such a fashion gives rise to an arithmetic circuit to compute the map taking x to Ax.  The fanin of each gate is 2, and the number of non-input gates corresponds to the number of row operations.

There isn't any obvious reduction in the reverse direction (from circuits to row-op sequences).  Still, we can characterize c(A) in terms of the arithmetic circuit complexity of Ax in a restricted circuit model: I claim that c(A) is equal to one-half the minimum number of edges in an arithmetic circuit for A, of fanin at most 2 and width n, where we don't charge for edges leading into gates of fanin 1.
(I'm using the usual notion of circuit width here.)  This can be shown using the simple idea sketched before.

Now here's the connection to well-studied problems: it's been a famous open problem for over 30 years to exhibit an explicit linear map Ax (over any finite field) which requires a superlinear number of gates in a fanin-2 circuit.  The classic reference is Valiant, "Graph-theoretic arguments in low-level complexity", and a recent FTTCS survey by Lokam is also helpful.

In studying c(A), we are imposing an additional width restriction, but since our restriction is so weak (width n) I don't anticipate the problem becoming much easier.  But hey--I'd love to be proved wrong.


Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is semicomputable if the probability it assigns to a given string can be computed to arbitratry precision from above or below by a Turing machine. If it can be computed from above and below, it's computable. (formal description here)

Now, I prefer to think of the space of distributions that can be sampled by a probabilistic Turing machine (PTM). That is the distributions $p$ for which a PTM with no input outputs the string $x$ with probability $p(x)$.

I have a (rough) proof that the two classes of distributions the class of lower semicomputable semimeasures and the class of semimeasures samplable by PTM are equivalent: every lower semicomputable semimeasure can be sampled by a PTM and vice versa. However, this seems like the sort of thing that has been worked out ages ago, and is well known to everybody. Can anybody help me with a reference that asserts and proves this equivalence?

edited after @domothorp's comments

This answer is not a reference but rather to make some of the notions precise in your question. First, semicomputable does stand for what you say but I think there is a big difference between upper and lower semicomputable - in case of the former I have no clue how you would sample.

Second, do you have a measure or a semimeasure? In a semimeasure the sum of the probabilities is at most 1, so I again do not know how you would sample, as there is no full distribution (of course you can say that you normalize by dividing the sum of the probabilities but that might not be computable, you could never know when to give up a computational path).

Finally, if you have a lower semicomputable measure, then it is in fact equivalent to have a PTM that can sample with this distribution (although we must allow the sampling to run for arbitrarily long, as long as it stops eventually).

I think the best reference on the topic is Ming Li and Paul Vitányi: An Introduction to Kolmogorov Complexity and Its Applications. For another available online see chapter 6.2 of László Lovász: Complexity of Algorithms at http://www.cs.elte.hu/~dom/complexitynew.pdf


Can recursion be replaced with a finite set of higher-order functions? I am wondering if there is some proof that all recursive algorithms can be rewritten to use some known set of higher-order functions instead of recursion. I'm talking about functions like fold, map, filter, etc.

If recursion can always be replaced, I'm also interested in knowing whether there is some mechanical translation, or if it's something that can't be automated.

Apologies if this question is ill-formed. I'm no PLT expert.

You may replace recursion with computation of fixed points, so all you need is a fixed-point operator

fix : (a -> a) -> a

which satisfies

fix f = f (fix f)

Then, given a recursive definition of f : a -> b,

f = Φ(f)

we may define f as

f = fix (λg.Φ(g))

Here fix has type ((a -> b) -> (a -> b)) -> (a -> b).

You may consider this to be cheating, but the question is not really research-level precisely because the connection between recursion and fixed points is a basic piece of knowledge. I am guessing that maybe you did not know about the connection.


hardness of constant approximation of largest matching set We say that $H$ is a matching graph if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more.

Given a graph $G=(V,E)$ a subset $U\subseteq V$ is called a matching set if the sub graph that is induced by $U$ is a matching graph.

Prove that approximating the problem of finding the largest matching set is $NP-Hard$ for any constant factor.

I tried reducing to it from the $IS$ problem. I know that it is $NP-Hard$ to approximate $IS$ for any constant factor. I thought of this reduction, given a graph $G=(V,E)$:

$1)$ Find $k=\max\limits_{\ v\in V} deg(v)$.

$2)$ Construct $k$ graphs exactly like $G$: $G_1(V_1,E_1),\dots,G_k(V_k,E_k)$. those graphs are exactly like $G$ but the vertices are signed by the index and so does the edges.

$3)$ Return $H=(\cup_{i} V_i,\cup E_i)$.

I wanted to say that:

If $m$ is the size of the maximal $IS$ in $G$, the size of the largest matching set in $H$ is: $k\ \cdot m$.

I failed doing so. Can someone help?

Check out

  Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai:
  "Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses"
  Link:  https://arxiv.org/abs/1308.2617


Computing sum of sparse polynomials squared in O(n log n) time? Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n>m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient algorithm for computing the polynomial:

$$\sum_i p_i(x)^2$$

Since this polynomial has degree at most $2n$, both input and output size is $O(n)$. In the case $m=1$ we can compute the result using FFT in time $O(n \log n)$. Can this be done for any $m<n$? If it makes any difference, I'm interested in the special case where coefficients are 0 and 1, and the computation should be done over the integers.

Update. I realized that a fast solution for the above would imply advances in fast matrix multiplication. In particular, if $p_k(x)=\sum_{i=1}^n a_{ik} x^i + \sum_{j=1}^n b_{kj} x^{nj}$ then we can read off $a_{ik} b_{kj}$ as the coefficient of $x^{i+nj}$ in $p_k(x)^2$. Thus, computing $p_k(x)^2$ corresponds to computing an outer product of two vectors, and computing the sum $\sum_k p_k(x)^2$ corresponds to computing a matrix product. If there is a solution using time $f(n,m)$ to computing $\sum_k p_k(x)^2$ then we can multiply two $n$-by-$n$ matrices in time $f(n^2,n)$, which means that $f(n,m)=O(n\log n)$ for $m\leq n$ would require a major breakthrough. But $f(n,m)=n^{\omega/2}$, where $\omega$ is the current exponent of matrix multiplication, might be possible. Ideas, anyone?

Squaring a polynomial with $x_i$ nonzero coefficients takes time $O(x_i^2)$ using ordinary term-by-term multiplication, so this should be preferred to the FFT for those polynomials where $x_i < \sqrt{n \log n}$.  If $\sum_i x_i = n$, then the number of polynomials with $x_i$ greater than $\sqrt{n \log n}$ is $O(\sqrt{n / \log n})$, and these will take time $O(n^{3/2}({\log n})^{1/2})$ to square and combine (as will the remaining polynomials).  This is an improvement over the obvious $O(m n \log n)$ bound when $m$ is $\Theta(\sqrt{n / \log n})$.


What is the Volume of Information? This question was asked to Jeannette Wing after her PCAST presentation on computer science.

  “From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge question for the theoretical computer science community since I think it begs the question “What is information?”)

Beyond "What is information?" one should also figure out what "volume" means in this context? Perhaps maximum density of information is a better measure.

Lance, there is in fact a theorem which gives bounds on this. The Margolus-Levitin theorem bounds the rate of computation in terms of energy density. There is a nice trick which can then be played: If the local energy density exceeds a certain limit, a black hole will form causing an event horizon which will essentially prevent you from getting an answer by causally disconnecting that region of space-time from the rest of the universe. Seth Lloyd has a nice paper using this trick to estimate the computational power of the universe (Phys. Rev. Lett. 88, 237901 (2002), arXiv).

You can of course use similar reasoning on any finite region of space-time.


Formalized configuration of Subset sum problem Worst-case ? Is there a formal proof of the worst-case configuration of the subset sum problem?

In other words - is there a set proven to be the hardest to find a subset equals to 0 from?

thanks

No, there isn't. If there was such a particular instance of subset sum problem that would be "the hardest" we could solve it by brute-force, and then hard-code it (and its answer) into our program solving subset sum problem. Then our algorithm, given an instance to solve, would first check whether the input matches that hard instance, and if so, it would simply output its answer in O(1) time - and thus, the instance wouldn't be hard anymore.

In general, hardness lies in the problems (which we can see as infinite sets of instances), and not in particular instances (or even some finite sets of instances), and searching for explicit instances of the problem that are "the hardest" doesn't make much sense. You could restate the question to ask about some "hard" family of instances - i.e., such families that our problem remains NP-hard when limited only to these instances. You could probably get one example of such families by looking at the details in the reduction showing that SUBSET-SUM in NP-hard.

Answer to the comment: Generally, this kind of questions is too elemental for this site - I would really advise you to read some good intro to complexity theory, or at least to do a DFS on wikipedia starting from this article: http://en.wikipedia.org/wiki/NP-complete
I think you will find all your answers there. Then, if you're interested specifically in the SUBSET-SUM problem, you could look into the reduction showing its NP-hardness - you will see there arbitrary instances of SAT (or some other NP-hard problem) being mapped into some particular instances of SUBSET-SUM (the set of these "hard" instances will probably be smaller than the set of all instances, but still infinite and "dense"). And yes, if you can solve the SUBSET-SUM problem restricted to this set of instances, you will prove that P=NP.


Efficiently computable variants of Kolmogorov complexity Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:

It corresponds to an intuition of giving strings with patters or structure a lower complexity than strings without.
It allows us to define conditional complexity $K(x|y)$, or even better $K(x|O)$ for some oracle $O$.
It is sub-additive $K(x,y) \leq K(x) + K(y)$.

However it has an awful downside: returning $K(x)$ given $x$ is undecidable.
I have wondered if there is a variant of Kolmogorov complexity $K'(x)$ using a restricted model of computation (either by using weaker languages than TMs, or using resourced bounded TM) that preserves features (1) and (2) (feature (3) is a bonus, but not a must) while being efficiently computable?
The motivation for this question is for use in simulation studies of various toy-models of evolution. Thus an answer that has been used as a 'rough approximation' for Kolmogorov complexity in numeric work before is preferred. However, the goal isn't to go completely experimental, so a relatively simple/clean description language/model-of-computation for $K'$ is preferred, so that it might be possible to prove some reasonable theorems about how drastically $K'$ differs from $K$ and on what kind of strings.
Relates questions
Kolmogorov complexity with weak description languages
Is there a sensible notion of an approximation algorithm for an undecidable problem?

Gzip.  Cilibrasi and Vitanyi have a really nice article where they use gzip as an approximation of Kolmogorov complexity to do clustering. Clustering by Compression


Inferring simplest method to convert bit array 1 to bit array 2 Consider the set of all bit arrays of length n. Now consider the set of all 1-to-1 functions that map from this set to this set.

Now select a single function out of the latter set. Is there any algorithm to find a "minimal" method of implementing this function? Assume that we only have access to fundamental bit array operators such as AND OR XOR NOT and left and right bitshifts.

In case you're wondering, the reason I want this is because I'm writing an algorithm to convert from z-curve ordering of bits to hilbert-curve ordering of bits. My current method is to make a lookup table, but I bet there's a better option.

As a simple example, let's say I have a truth table that looks like this:

00 -> 10
01 -> 01
10 -> 00
11 -> 11

Then I should be able to infer that, given an input bit string input, the output bit string output is (in java syntax)

output = ((~input) << 1) ^ input

Here's the proof in this case:

00 -> 11 -> 10 -> 10
01 -> 10 -> 00 -> 01
10 -> 01 -> 10 -> 00
11 -> 00 -> 00 -> 11

There is clearly an algorithm, since the finite search space can be explored using brute force.  This takes a long time...

Instead of considering $f \colon \{0,1\}^n \to \{0,1\}^n$, one can look at the Boolean function $f' \colon \{0,1\}^{2n} \to \{0,1\}$ defined by $f'(xy) = 1$ iff $f(x) = y$.

No polynomial-time algorithm is known to find a minimum-size circuit for a Boolean function, which is known as the Minimum Circuit Size Problem (MCSP).  However, MCSP is in NP.

If MCSP were in P, then one could factor in average time $2^{n^\epsilon}$ time (for any $\epsilon > 0$) numbers that are products of two primes, each of which is congruent to 3 modulo 4.  These numbers are quite hard to factor in practice, so this would be quite surprising.

On the other hand, if the MCSP is NP-complete, then this would imply strong circuit lower bounds for the class E = DTIME($2^{O(n)}$), which we don't currently know how to do.

Valentine Kabanets and Jin-Yi Cai, Circuit Minimization Problem, STOC 2000, 73–79. doi:10.1145/335305.335314 (preprint)

So no polynomial-time algorithms seem likely for your problem, unless you can exploit special features of the functions you are interested in.


Algorithms for printing the digits of pi, minimizing the time spent between digits What is the smallest function $t(n)$ such that there exists an algorithm which prints the binary digits of $\pi$, with the time spent between printing digit $n - 1$ and digit $n$ being $O(t(n))$?

Since the $n$th bit of $\pi$ can be computed in $O(n \log^3 n)$ time by itself, we can trivially take $t(n)$ to be $n \log^3 n$. But we can hope that $t(n)$ can be much smaller, since we get to "reuse" all of the computations which gave us the previous bits. In fact, I don't see how to rule out $t(n) = 1$.

Also, what is the name of this "mode" of computation, where we are listing out the terms of an infinite sequence? It's a little like streaming, but backward...

($M(n)$ is "the time required to perform precision
$n$
multiplication.") $\:$ By page 10 of this paper,

a precision-$n$ approximation to $\pi$ can be computed in time $\;\; O\Big(\hspace{-0.04 in}M(n)\hspace{-0.02 in}\cdot \hspace{-0.02 in}\log(n)\hspace{-0.04 in}\Big) \;\;\;$.

By the very end of this paper, one can find a rational number $c$ such that for all $n$,

the first $n$ bits of $\pi$ are the first $n$ bits of every precision-$\hspace{-0.03 in}\lfloor (19.9\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)\hspace{-0.04 in}+\hspace{-0.04 in}c\rfloor$ approximation

of $\pi$, so the first $n$ bits of $\pi$ can be computed in time $\;\;\; O\Big(\hspace{-0.04 in}M(n) \cdot \hspace{-0.02 in}\log(n)\hspace{-0.04 in}\Big) \:\:\:\:$.

Thus, if $\Theta$$(M(n)\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n))$ has a time-constructible function, one can print $\pi$ "with the time

spent between printing digit" $n\hspace{-0.04 in}-\hspace{-0.05 in}1$ "and digit $n$ being" $\;\; O\Big(\hspace{-0.05 in}\big(\hspace{-0.02 in}M(n)\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n)\hspace{-0.02 in}\big)\big/n\hspace{-0.04 in}\Big) \;\;$, $\;\;$ as follows:

(Recall that the 0th and 1th bits of $\pi$ are both "1".) $\;\;\;$ Set $\: i = 0  \:$ and $\: t_{curr} =1 \:$ and output "1", then run the following loop forever. $\;\;\;$ Compute [the first $2^{\hspace{.02 in}i+2}$ bits of $\pi$] and $\big[\hspace{-0.02 in}$an integer

$t_{next}$ in $\Theta \hspace{-0.04 in}\left(\hspace{-0.02 in}M\hspace{-0.04 in}\left(\hspace{-0.02 in}2^i\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.05 in}i\hspace{-0.02 in}\right)$ such that $t_{next}$ is an upper bound on the time it will take to compute

$t_{next}$ and those bits of $\pi \big]$. $\:$ At the start of those computations, output the $2^i\hspace{-0.03 in}$-th bit of $\pi$.

Interleaved with those computations, output a bit of $\pi$ approximately $t_{curr}\hspace{-0.03 in}\big/\hspace{-0.02 in}2^i$ steps after outputting the previous bit of $\pi$. $\:$ At the end of those computations, output the rest of the first $2^{\hspace{.02 in}i+1}$ bits of $\pi$, then increment $i$, set $\: t_{curr} = t_{next} \:$, $\:$ and go back to the beginning of this loop.

With the fastest known integer multiplication algorithm,

that would achieve $\;\;\; t\hspace{.02 in}(n) \: = \: (\log(n))^{\hspace{.02 in}2}\hspace{-0.05 in}\cdot 8$$\hspace{.02 in}\log^{\hspace{-.02 in}*}$$(n)$$\;\;\;$.

To avoid that general trick, one should probably impose a sublinear space bound.


Is analogy between database and probability concepts legitimate? In Relational Databases: Tutorial for Statisticians Joe R. Hill casts probability view onto database theory. In Table 1 the author summarized the parallels between the two disciplines, describing relation structure together with three relational algebra operations in probabilistic terms.

I seek clarification on 2 items:

What probability distribution corresponds to empty relation? An intermediate step in Dr.Hill's paper is indicator function -- which is standard trick of thinking about relations in functional terms. My understanding is that the author generalizes {0,1} valued indicator function to probability distribution. There, the 1 valued tuples are assigned not vanishing discrete probabilities (assuming discrete domain), while all the tuples not belonging to relation inherit their 0 indicator function value as probability. My objection is that this would work for nonempty sets of tuples only.
Missing from the parallels is Relational Algebra union operation -- what probability concept is it analogous to? If we take average, then it would fail to honor associativity law.

Edit: Resolved confusion with transformation constraint. Consider a relation

x y
---
1 a
2 a
3 b

honoring FD x->y. One can match it with joint distribution like this

\ |  1   2   3  |
--+-------------+----
a | 1/4 1/4  0  | 1/2
b |  0   0  1/2 | 1/2
--+-------------+----
  | 1/4 1/4 1/2 |  1

Still the analogy is weak: there is well known interpretation of Functional dependencies in terms of entropy.

I would expect that the empty relation corresponds to the always-zero probability distribution.  Disjoint union corresponds to addition of probability distributions.  However, standard union would be more complicated.  I don't really know if there is some way to encode the standard union for probability distributions.  (I have heard people say that probability distributions form a boolean algebra.  So there must be some operation that serves as the union.)


Cite a conference contribution as conference paper of book chapter Let's say you submit a paper to a TCS conference and it is accepted. Then you go there and give a talk. When you put this information in your CV;

do you write it as two items in different sections; first in conferences and second the published paper or just as one single thing?
if the paper is published in some sort of a book (book of abstracts, LNCS, etc) with ISBN, will you cite it as conference paper or as book chapter?

Thanks

Converting/extending a comment to an answer:

I keep a list of talks/posters on my website. I do this to include links to slides, photos and video recordings. When I was applying for grad school I had them in my CV, too. I have the impression that it might have helped. However, once you have a lot of talks it becomes too much info. On some senior researchers' CVs I've seen very compact talk lists: they include their invited or conference talks as acronyms/university names and lists of years. For example, if they regularly present at STOC they might write "STOC 2003,2004,2007". I think this is mostly to show that they are involved with the community and go places regularly.
As Dave mentioned, it is usually standard to cite the paper as a conference. I think the exception is when conferences publish their proceedings, or selected papers, as a special issue of a journal. The only time this happened to me, I had to go through an extra layer of review (first conference, then the journal) for one paper, so I think is appropriate to cite those as journal papers.
A lot of time papers are first published in conferences, and then a year (or more!) later a longer version appears in a journal. The convention is to cite this as a journal paper with a note after: "preliminary version appeared in Conference X 2008".