Is counting the words in a finite regular language #P-complete? Almost the exact same question was asked here, but nobody proved or cited its #P-completeness! I found this question because I proved it is #P-complete (proof below), and the proof was trivial, but I couldn't find it anywhere on the web or in the discussion on that question! (One person commented "I suspect it is #P-complete".) So either my proof is wrong, which you can judge for yourself, or the result is novel, which I would think is highly unlikely. Which is it?

Proof:

Consider the set of regular expressions formed by the union and concatenation of symbols from $(\Sigma\cup{.})$, where $\Sigma$ is an alphabet and $.$ is a symbol for any $l\in\Sigma$. I will show that #SAT reduces in $O(mn)$ time to counting the number of strings that satisfy such a regex, where $m$ is the number of clauses and $n$ is the number of variables in the given formula $\varphi$.

The reduction is very simple. First, reduce #SAT to #UNSAT by noting that if $\varphi$ has $n$ variables, then $\#\text{SAT}(\varphi) = 2^n - \#\text{UNSAT}(\varphi)$. So now we have to count the number of falsifying assignments of the variables of $\varphi$.

To falsify $\varphi$, it suffices to falsify just one clause. We therefore want to find
$$\left|\bigcup \limits_{C\in\varphi}F(C)\right|$$
where $F(C)$ is the set of assignments of literals that falsify $C$.

We thus write a regex representing the language of falsifying assignments for each clause. Using $\Sigma = \{0,1\}$, and letting $r_i$ be the $i^{th}$ symbol of a regex $r$, the regex for the language of assignments that falsify a clause $C$ is
$$
r_i = \begin{cases}
         0 & \text{if } x_i\in C \\
         1 & \text{if } \overline{x_i}\in C \\
         . & \text{otherwise}
      \end{cases}
$$

We then take the union of the regexes for each clause $C\in\varphi$. For example, if $\varphi = (x_1\vee \overline{x_2}\vee x_3) \wedge (x_1\vee x_3\vee \overline{x_4})\wedge (\overline{x_1}\vee \overline{x_4})$ we would have $r = $010.|0.01|1..1, where | denotes union.

The construction yields a union of $m$ strings, each of $n$ symbols. Thus the reduction takes $O(mn)$ time and the size of the regex-counting instance is polynomial in the size of the formula. Further, any regular expression that uses only concatenation, dot, and union represents a finite regular language (specifically, there is no Kleene star). So since we can solve #SAT by counting strings that satisfy such a regex, we can say that counting the words in a finite language is #P-complete.

See this paper:
Counting the size of regular sequences of given length is #P-complete:
S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting
and random generation of strings in regular languages.
In ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 551–557, 1995.


Practical Data-oblivious Compaction? Compaction is a particularly weak form of sorting. The problem can be phrased as follows:

Given an array $A$ of $N$ cells, with at most $R$ of the cells distinguished (say by a bit), produce an array $D$ of at most size $O(R)$ containing all of the marked cells

Compaction is said to be:

Tight: If the output array $D$ is of size exactly $R$
Order-preserving: If the relative ordering of marked elements of $A$ is the same as the relative ordering of elements of $D$ (i.e. if the compaction is "stable" in the sense of sorting)
Data-oblivious: If the algorithm which computes the compaction has access patterns independent of the data

One can construct tight, order-preserving, data-oblivious compaction from a sorting network. You have to use non-standard comparison function which:

Sets all marked elements as greater than unmarked elements
Within comparisons between marked elements (resp. unmarked elements), breaks ties by the element's initial ordering in the array.

But such a function is easy to specify, and can be computed in $O(\log N)$ time.
This means that one can construct tight, order-preserving, data-oblivious compaction from the AKS sorting network (giving an $O(N(\log N)^2)$ algorithm) or from a more practical sorting network like Batcher Odd-Even Mergesort (giving an $O(N(\log N)^3)$ algorithm).
Anyone who has worked for sorting networks before has heard that there are the asymptotically optimal algorithms (namely the AKS sorting network and ZigZag Sort, both using $O(N\log N)$ comparisons), and the practically efficient algorithms (Batcher's mentioned above is one example, but there are many which are $O(N(\log N)^2)$ comparisons).
I'm essentially curious if there is something similar for compaction --- I have seen papers such as this which give oblivious tight compaction in $O(N)$ time <1>.
This paper's improvement is lowering the implied constant from $2^{228}$ to ~$9000$. I imagine that for al "reasonably-sized arrays" it is still more efficient to pair Batcher's sorting network with the aforementioned non-standard comparison function.
So has been research done into practically-efficient compaction algorithms? While I eventually want something which is tight, order-preserving, and data-oblivious, the most important keyword by far is "data-oblivious". I'm willing to tolerate a negligible (meaning $N^{-\omega(1)}$) probability of failure, as long as it has "good constants".
Moreover the data to be compacted is "random" in a strong sense. In particular, each element of the array is marked/not marked according to the result of an i.i.d. $\mathsf{Bern}(1/2)$.
<1> The linked algorithm has a negligible probability of failure, which is fine for my purposes.

It looks like there are some known lower bounds (see page two of Sorting Short Keys in Circuits of Size $o(n\log n)$). The relevant section is copied below:

More specifically, Lin, Shi, and Xie [LSX19] showed that any stable compaction circuit that treats the payload as indivisible must have at least $\Omega(n \log n)$ selector gates — here the indivisibility assumptions requires that the circuit only move the payload around through selector gates but not perform boolean computation on the encoding of the payload.  The indivisibility restriction in Lin et al.’s lower bound [LSX19] can be removed if one assumes the Li-Li network coding conjecture [LL04] — this is implied by Afshani et al. [AFKL19]’s recent work$^2$.

Given that this is the case, it seems like the best thing to do is to use sorting networks. There seem to be a few new ones which may be competitive (see for example this), but I can't say anything definitive.


Will Martin-Löf Type Theory lead to a greater ability to write provably correct code? This post refers to the Curry-Howard isomorphism and the Martin-Löf Type Theory.

The post makes the claim of a future 'unification' between the the describing language of math, and the operation based language of computer programming.

My questions are:

Will these ideas lead to a better ability (through languages) to write provably correct code?
Have the full implications of MLTT been discovered on a theoretical level?
Does this post describe anything could couldn't already do in COQ or Agda?

I don't think your question is particularly well posed. It mostly asks for opinions. Here are mine:

Yes.
I do not know what you mean, but the answer is probably "there is more MLTT theory to be done, although we do know a lot".
You cannot do all of homotopy type theory in Coq and Agda. This is an active area of research.


Difference lists in functional programming The question What's new in purely functional data structures since Okasaki?, and jbapple's epic answer, mentioned using difference lists in functional programming (as opposed to logic programming), which is something I've recently been interested in. This led me to find the difference list implementation for Haskell. I have two questions (forgive/correct me if I should make them two different questions on the StackExchange).

The simple question is, is anyone aware of academic consideration of difference lists in functional programming and/or implementations besides the one in the Haskell library? jbapple's answer didn't give a citation for difference lists (difference lists in logic programming exist in the lore and in a couple of sources which I have Around Here Somewhere (TM)). Before finding the Haskell implementation I wasn't aware that the idea had leaped from logic to functional programming. Granted, the Haskell difference lists are something of a natural use of higher-order functions and work quite differently from the ones in logic programming, but the interface is certainly similar.

The more interesting (and far fuzzier-headed) thing I wanted to ask about is whether the claimed asymptotic upper bound for the aforementioned Haskell difference list library seems correct/plausible. My confusion may be because I am missing something about obvious about complexity reasoning with laziness, but the claimed bounds only make sense to me if substitution over a large data structure (or closure formation, or variable lookup, or something) always takes constant time. Or is the "catch" simply that there's no bound on the running time for "head" and "tail" precisely because those operations may have to plow through an arbitrary pile of deferred computations/substitutions?

Yes, the bounds depend on the assumption that function composition takes constant time.
Basically, if you have a join list:

datatype 'a join = Nil | Cons of 'a * 'a join | Join of 'a join * 'a join

It's obvious that concatenation is constant time, and that it's $O(n)$ to turn this into a cons-list. If you think about the usual representation of closures, you can see that this is basically the same pointer representation as the usual representation of datatypes. (Alternatively, you can view this type as a defunctionalized difference-list.)


Runtime of Tucker's algorithm for generating a Eulerian circuit What is the time complexity of Tucker's algorithm for generating a Eulerian circuit?
The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an arbitrary 2-regular detachment of the graph and then generates a Eulerian circuit.

I couldn't find any reference that says, for example, how the algorithm constructs an arbitrary 2-regular detachment of the graph, what data structures it uses, what the time complexity is, and so on. Any ideas?

A version of Tucker's algorithm was used in B. Awerbuch, A. Israeli, and Y. Shiloach, Finding Euler Circuits in Logarithmic Parallel Time, STOC 1984, to find Euler tours efficiently in parallel, and similar ideas can be used to make the algorithm run sequentially in linear time.

Suppose you have a connected graph $G$ in which all vertices have even degree, and start by pairing off edges at each vertex. This forms a collection of cycles that together cover the graph, and Tucker's algorithm works by joining the cycles together one at a time.

To make this repeated joining process efficient, first run a connected components algorithm (e.g. DFS) to find which edges belong to which cycles. Make a bipartite multigraph $H$, where the vertices on one side of the bipartition correspond one-for-one with the vertices of $G$, the vertices on the other side of the bipartition correspond with the cycles you've constructed, and the edges of $H$ correspond to incidences between cycles and vertices in $G$. Construct a spanning tree $T$ of $H$ (e.g. DFS again), rooted at one of the cycle vertices.

Now, for each cycle $C$ that is not the root of $T$, join $C$ to its grandparent in $T$ (by swapping the edge pairing at the common vertex of the two cycles, represented by the parent of $C$), in constant time per join.

The same technique also works for directed graphs (and that's the version that Awerbuch et al use for their main presentation); in that case, the only difference is that you want equally many incoming and outgoing edges at each vertex, and the edge-pairing at each vertex must pair incoming edges with outgoing edges.


Searching nodes in semi-splay tree If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations.

My course also says that if you search for a node and the node is not in the semi-splay tree, you still have to perform semi-play on the search path in the tree.
But isn't that basically pushing nodes to the root that aren't actually have been searched for?

So my question would be : why do you still have to perform semi-splay even if the node you search for is not in the tree?

To complete the search process for an element $x$ that is not in the tree, you have to go all the way to a leaf node to confirm that $x$ is not in the tree.  If you repeatedly search for such an element $x$, you have to splay on an unsuccessful search, otherwise the query time for $x$ could indefinitely remain as bad as $\Theta(n)$, even in an amortized sense.


Algorithm to "scale" an array in place Problem: transform an array $A$ of $n$ natural numbers (of $t$-bits) into an array $B$, which is a permutation of $\{1, ..., n\}$ with the property that, whenever $B[i] \leq B[j]$ holds, $A[i] \leq A[j]$ holds. Call this operation "scaling".

For instance:

A = 7 7 2 5 9
B = 3 4 1 2 5
B = 4 3 1 2 5 -- a second "non stable" possibility

Assuming $n$ can be represented in $t$ bits, is there a way of scaling an array in place?

The time and space complexity should be as close to $O(n)$ and $O(1)$ as possible, with a $O(\log n)$ factor being probably acceptable.

A. Maus, IPS, sorting by transforming an array into its own sorting
permutation with almost no space overhead, solves a related problem; but it seems that the method approaches standard bucket sorting, requiring $O(n)$ space, as $\log_2 n$ approaches $t$.

Correct me if I'm wrong, but given this is possible with O(n) time, then you can build the sorted array in O(n) time, too:

for(i=0; i<n; i++) {
 C[P[i]] = A[i];
}

If so, there's no way this can be done in O(n), since sorting is O(n.log(n)) at least.
When you take that into account, there are many O(n.log(n)) sorting algorithms, that can be easily fitted for your purpose and you can implement it this way:

B = array(1..n);
sort(B, cmp_func);

where cmp_func(int a, int b) compares A[a] and A[b] instead of a and b.

Sorry for my lame pseudocode, but I think it's understandable.


Is there research on algorithmic design patterns? From what I've seen in the majority of algorithms publications, the focus of research is mainly towards improving the solutions to algorithmic problems in terms of efficiency or optimality in the case of approximation algorithms. My interest and hence my question is towards the generalization rather than improvement of algorithms, that is finding common ideas,techniques,optimization tricks that underlie the design or analysis process of algorithms and data structures. Examples of such patterns would be: lazy propagation in data structures, sqrt decomposition, incremental (sweep like) algorithms, smaller to larger merging (as in union by rank)...etc.

I am aware that these techniques would be explained when used in a specific instance of an algorithm, but the focus would still be on the algorithm rather than the design technique.

I appreciate if someone can provide guidance on where to look for such research and whether design techniques are valid as a research point.

There are many general techniques and meta-theorems. Unlike software engineering, in TCS we don't want to repeat things similar to what the others did, we want to create something new or solve an unsolved problem, so it's not as easy as using lazy propagation in software development. Here I provide some examples but it's surely way far from the complete list.

Parametrised complexity: kernelization, iterative compression, bidimentionality, ...
Approximation algorithms: randomised rounding, scaling, ...
In graph theory, based on structural hierarchies of graphs like bounded tree width graphs/excluded minor graphs/ bounded expansion graphs / nowhere dens graphs, there are different tools (like decompositions) and meta theorems (like Courcelle theorem).


Determinism and pi-calculus Milner embedded $\lambda$-calculus into $\pi$-calculus, showing that the $\pi$-calculus is capable of Turing-complete, deterministic calculation. Since parallel compositions of processes in the $\pi$-calculus typically have several possible non-confluent reductions, so one can use the $\pi$-calculus to model non-deterministic concurrency.

Type systems are used to prove certain desirable behaviour of programs. For example, simply typed lambda terms always terminate to a lambda abstraction value (the calculus is strongly normalising). So it's just natural to wonder whether we can find a good type system for $\pi$-calculus such that some of its processes correspond to deterministic computations.

Is there a type system for the $\pi$-calculus probably with types for processes such that processes under certain types are always confluent? Even more, could there be certain types such that their values are processes coming from lambda expressions, e.g. encoded in one of Milner's encodings?

There are plenty such typing systems.

Most work is based on the linear/affine typing system introduced
in (1) and generalised in (2). Here are the main works on this subject.
In (3) the typing system ensures a precise match with PCF (int its call-by-name variant -- changing to call-by-value is easy).
In (4) the typing system gives a precise interpretation of the
simply typed λ-calculus. (5) does the same thing for System F, (6) does the same for the λμ-calculus.

The typing systems in  (3, 4, 5, 6) are precise in the sense that the inhabitants of translations of λ-calculus types
"are processes coming from lambda expressions", at least up to $\simeq$ (weak typed bisimulation). More precisely, if $\alpha$ is a type in the λ-calculus, and $\Gamma = x_1 : \beta_1, ..., x_n : \beta_n$ is a corresponding typing environment, then the processes $P$ that are typable
as

$$
   \vdash P \triangleright x_1 : \overline{\langle\beta_1\rangle}, ..., x_n : \overline{\langle\beta_n\rangle}, u : (\langle\alpha\rangle)^{\uparrow}
$$

are (up to $\simeq$) the translations of λ-terms $M$ with

$$
   \Gamma \vdash M : \alpha
$$

(Here $\langle \alpha \rangle$ is the translation of a λ-type $\alpha$ into π-types, and
$\overline{\tau}$ the dualisation of the π-type $\tau$.) The translations
are fully abstract in the sense that

$$
M =_{\beta\eta} N
\quad\text{iff}\quad
\langle M \rangle_u \simeq \langle N \rangle_u
$$
(Here $\langle M \rangle_u$ is the translation of $M$, located at $u$.) So the embedding is as precise as one can hope for. (NB, I'm skating over some details above, for ease of presentation.)  Note  that the systems in (3, 4, 5, 6) are closely related -- indeed they are in some sense the same system, although this viewpoint has not yet been published.

If you want a brief summary of how those typing systems ensure confluence, then it is this: they ensure that there is always at most one active output (i.e. an output not under a prefix). This is brutal/syntactic.

Session types (7, 8) can also be used for this purpose, but the
correspondence is not that precise, in parts because session
types are not as constraining as the types deriving
from (1). See (9) as an example where sessions are used to model
effects (such as state) in PCF.

Davide Sangiorgi and others have also worked on this problem,
see (10) for a summary.

Aside: as the question correctly guesses, λ-calculus can be seen as an especially well-behaved form of message passing, a viewpoint  put forward 1976 in Carl Hewitt's pioneering work (11) in the  actors tradition. The typing systems above essentially constrain π-calculus so only this well-behaved  message passing is typable. Coincidentally, Milner invented the π-calculus in parts to give a formal model of actors. In hindsight, as (12) explains nicely, there is a small mismatch between actors and π-calculi.

K. Honda, V. Vasconcelos, N. Yoshida: Secure Information Flow
as Typed Process Behaviour.
K. Honda, N. Yoshida, A uniform type structure for secure information flow.
M. Berger, K. Honda, N. Yoshida: Sequentiality and the Pi-Calculus
N. Yoshida, K. Honda, M. Berger: Strong Normalisation in the Pi-Calculus
M. Berger, K. Honda, N. Yoshida: Genericity and the Pi-Calculus
K. Honda, N. Yoshida, M. Berger: Control in the Pi-Calculus
K. Takeuchi, K. Honda, M. Kubo, An Interaction-based Language and its Typing System.
K. Honda, V. T. Vasconcelos, M. Kubo, Language Primitives and Type Disciplines for Structured Communication-based Programming.
D. Orchard, N. Yoshida, Effects as sessions, sessions as effects.
D. Sangiorgi, D. Walker:  The π-Calculus: A Theory of Mobile Processes
C. Hewitt, Viewing Control Structures as Patterns of Passing Messages.
S. Fowler, S. Lindley, P. Wadler, Mixing Metaphors: Actors as Channels and Channels as Actors.


can some one use a polynomial one-to-many reduction for NP-comp problems? For proving a decision problem is NP-com, there are diffrent methods of reductions as parsimonious, like karp-reduction, or many-to-one reductions!
What about one-to-many map? is it possible to set a polynomial one-to-many reduction from NP-comp decision problem 'A' to a decision problem 'B' which we are looking for it's complexity?

I think what you are looking for is the notion of polynomial-time Turing reduction, denoted $\leq_{T}^{p}$ (also called Cook reduction, since this was the notion of reduction Cook used in the paper in which he defined NP-completeness; poly-time many-one reductions are called "Karp" or "Karp-Levin" for a similar reason), or polynomial-time truth-table reductions, denoted $\leq_{tt}^{p}$.

For any notion of reduction, you get a notion of NP-completeness: e.g. a problem is "NP-complete under $\leq_{T}^{p}$ reductions" if it is in NP and every problem in NP $\leq_{T}^{p}$-reduces to it.  The different notions of completeness are a priori distinct; however, even if they are distinct, showing that a problem is NP-complete under Cook reductions is still good evidence of its intractability.

Terminologically, when people say "NP-complete" without further specifying, they usually mean NP-complete under many-one reductions.

Lutz and Mayordomo showed that if NP does not have measure 0 in EXP,  there are problems that are NP-complete under $\leq_{T}^{p}$-reductions that are not NP-complete under $\leq_{m}^{p}$-reductions. The Lutz and Mayordomo paper has lots of other references, but one result that should be mentioned is that (under no assumptions), there are problems that are  $\leq_{T}^{p}$-complete for $NE$ that are not $\leq_{m}^{p}$-complete for $NE$ [1,2].

Truth-table reductions can be viewed either as a multi-query version of many-one reductions (in a sense they are "many-many") or as non-adaptive Turing reductions, or as Turing reductions in which all the queries are made in parallel.  The idea is that the reducing machine looks at the input, decides all the queries it's going to make without asking any of them, then asks all of them and gets answers from the oracle, then decides its answer without making further queries.

[1] H. Buhrman, S. Homer and L. Torenvliet, Completeness for nondeterministic complexity classes, Math. Systems Theory 24 (1991) 179-200.

[2] O. Watanabe, On the Structure of Intractable Complexity Classes, PhD thesis, Tokyo Institute of Technology, 1987.


Finite state transducer with infinitary outputs or without emphasis on acceptance? 1)  Is there a notion of (deterministic) finite state transducer (FST) that allows the possibility of producing an infinite stream of output symbols?  In other words, one where the transduction relation is a subset of $\Sigma^* \times \Gamma^\omega$ (as opposed to $\Sigma^* \times \Gamma^*$)?

For example, the definition of an FST given on Wikipedia involves a transition relation $\delta \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times (\Gamma \cup \{\epsilon\}) \times Q$, which might first seem to permit infinite streams of output.  However, the transduction relation is defined inductively (basically, the reflexive-transitive closure of $\delta$), thereby ruling out infinitary outputs.

2)  Relatedly, the definitions of FSTs that I've seen include a subset $F \subseteq Q$ of accepting states.  Is there a name for the class of (deterministic) FSTs in which $F = Q$, i.e., in which all input strings are accepted and the emphasis is placed on the output?

Any references that you can point me to would be greatly appreciated!

There are several relevant references on the subject. I just indicate a few of them. I suggest you to browse the references of these articles to get more.

Early references include the work of Françoise Gire.

[1] F. Gire, "Relations rationnelles infinitaires", Thèse de 3ème cycle, Paris VII, 1981.

[2] F. Gire, Une Extension aux Mots Infinis de la Notion de Transduction Rationnelle, 6th GI Conf., Lect. Notes in Comp. Sci., Volume 145, 1983, p. 123-139.

[3] F. Gire, M. Nivat, Relations rationnelles infinitaires. [Infinitary rational relations] Calcolo 21 (1984), no. 2, 91--125.

Interesting results can be found in

[4] Latteux, M.; Timmerman, E. Rational $\omega$-transductions. Mathematical foundations of computer science (Banská Bystrica, 1990), 407--415, Lecture Notes in Comput. Sci., 452, Springer, Berlin, 1990.

Section 4.3 of [5] is also a very good reference.

[5] L. Staiger, ω-Languages, Vol 3, Chapter 6 of the Handbook of Formal languages edited by G. Rozenberg and A. Salomaa, (1997) 339-387. Springer-Verlag, Berlin.

Finally, here is a more recent paper, where you will find other relevant references.

[6] Finkel, Olivier. On the accepting power of 2-tape Büchi automata. STACS 2006, 301--312, Lecture Notes in Comput. Sci., 3884, Springer, Berlin, (2006).


Is there an accepted name for Ross Quinlan's adaptation of the ID3 decision algorithm to use a Pearson's chi-squared test for independence? In Ross Quinlan's seminal paper Induction of Decision Trees, Quinlan summarizes the current state of machine learning in 1985 and loudly introduces the ID3 decision algorithm in the context of its peers in the field. However, he also states this halfway into the paper:

  An alternative method based on the chi-square test for stochastic independence has been found to be more useful.

And further in:

  Hart notes, however, that the chi-square test is valid only when the expected values of $p' i$ and $n'i$ are uniformly larger than four. This condition could be violated by a set C of objects either when C is small or when few objects in C have a particular value of some attribute, and it is not clear how such sets would be handled. No empirical results with this approach are yet available.

The name for this modification of the algorithm is not given, though. Is there an accepted name for this modification of ID3 (which is usually dependent on Shannon entropy to perform branching)? It seems like something that should be obvious (eg, ID3.1.x), but I cannot find a formal source.

I've also taken the liberty of perusing and studying the meta links within the FAQ of this fine site, and this didn't seem to fall into any of the bins for obviousness or non-research level, nor did it appear to be a good fit for other StackExchange sites. It is, however, a simple question that I could not find the answer to in any of the common sources.

This is directly pertinent to my research: I'm compiling another optimization that bridges the gap between generalized Shannon mutual information and Pearson's chi-squared test for independence in the context of TDIDT, then applying it to multivariate characteristics in cancer data as an alternative to random forests. As such, working definitions for my terms are greatly useful, insofar as they might lead to further papers I am not familiar with.

Unfortunately, I'm not able to get into detail of the ID3 paper you cited.

I read the Quinlan's book about C4.5 and I don't remember any quote about Chi-square splitting procedure. However, it exists a decision trees induction process that uses Chi-squares as splitting procedure, it is CHAID: http://en.wikipedia.org/wiki/CHAID.

By the way, do you really need a Chi-square splitting procedure? Good permances of C4.5 are well known, and it uses Information Gain as splitting criterion. Moreover, classical Data Mining books (such as Introduction to Data Mining by Tan et al.) state that better performances can be achieved with different pruning techniques rather than different splitting criteria.

If you really want a Chi-square splitting procedure I would suggest to use CHAID or modify the Java implementation of C4.5 in WEKA.


Testing isomorphism of asymmetric graphs While reading the question Examples where the uniqueness of the solution makes it easier to find, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) problem is in $P$.

But what happens if we assume that both $G_1$ and $G_2$ are asymmetric (i.e. both have only the trivial (identity) automorphism) ? Does the problem become easier (polynomial time)?

Note: the problem cannot be harder than Graph Automorphism ($GA$), because there is a quick reduction: just use $GA$ on $G_1 \cup G_2$, if the answer is yes then the two graphs are isomorphic (see also Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. 401-411).

Upon request of Marzio De Biasi I'm converting my comment into an answer.

A graph is asymmetric (some authors refer to it as rigid) if it has a unique automorphism, i.e., the identity. As pointed out by Chad Brewbacker, most graphs are asymmetric. However the following two questions are open:

1) Is isomorphism of asymmetric graphs in P?

2) Can isomorphism of general graphs be reduced to isomorphism of asymmetric graphs?

Question 1) has received a lot of attention in quantum computing due to the fact that the isomorphism of asymetric graphs can be reduced to the nonabelian hidden subgroup problem  and to the non abelian hidden shift problem. However the results are negative, showing that one needs to prepare at least $\Omega(n\log n)$ hidden subgroup states or hidden shift states to have enough information to solve the isomorphism problem.


Is it decidable whether the output length of a transducer is bounded by the input length? The transducers considered here are those Wikipedia calls finite state transducers.  The behavior of a transducer $T$, that is, the relation it computes, is written $[T]$: a word $y$ is an output for $x$ iff $x[T]y$.

Question: Is the following problem decidable:

  Given: A transducer $T$ and a regular language $L$
  Decide: Does it hold that $\forall x \in L$, $\forall y$ a word, $x[T]y$ implies that $|y| \leq |x|$?

I'm looking for nontrivial analysis/solvable subcases, reduction to known problems and/or related refs. (right now not even sure it is decidable in general...?)

Motivation: this problem was inspired by analysis/inquiry into automated theorem proving of number theoretic problems in general and a highly-studied one, Collatz conjecture, in particular.

The other contributor deleted his answer, maybe to let me extend my above comment, so here it is.

Let $T$ be a possibly nondeterministic transducer, and $L$ be a regular language.  Modify $T$ into a transducer $T'$ that checks that its input is in $L$ (by, e.g., changing the state set into the Cartesian product of the state sets of  $T$ and $L$, and modifying the transition function so that the $L$ part of the states is properly updated, while retaining the behavior of $T$.)

A branch of $T'$ is a sequence $\rho_1 C_1\rho_2 C_2 \cdots \rho_n C_n \rho_{n+1}$ such that $\rho_1\rho_2 \cdots \rho_{n+1}$ is an accepting simple path in $T'$, and each $C_i$ is a strongly connected component of $T'$ the states of which include the destination of $\rho_i$ (and the origin of $\rho_{i+1}$).  The branch is tame if:

The input length of the path $\rho_1\rho_2\cdots\rho_{n+1}$ is greater than or equal to its output length;
For any $i$, any simple cycle in $C_i$, the input length of the cycle is greater than or equal to its output length.

Fact: $\big[$ For any $x, y$, $x[T']y$ implies $|y| \leq |x|$ $\big]$ iff all branches are tame.

The proof is rather immediate.  The latter property being decidable (as the number of branches is bounded, and the number of simple cycles too), this shows that the problem of the question is decidable.


What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid? A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like,

A  0  0  0

0  0  0  0

0  0  C  D

What are some effective heuristics that could be applied to find them - and particularly, techniques to trim/discard paths along the way?

Edit: Just to clarify, the edges are formed when elements are connected horizontally and vertically, but not diagonally. The problem also states that any element that is marked 0 can be used to form a path, but non 0 elements are "obstacles" that need to be avoided.

A-0-0-0
      |
0-0-0-0
|
0-0-C D

could be one path, for instance. Another may be,

A 0-0-0
| |   |
0 0 0-0
| | |
0-0 C D

I don't see an easy way of counting without enumerating. You can easily visit all hamiltonian paths with an exaustive depth-first search with backtracking. You can actually cheat a bit, and realize that, if N is the number of hamiltonian paths that start by going to the right, the total number of hamiltonian paths is 2N (due to the symmetry if the grid).  This does not extend all the way (for some vertices not all paths will lead to the same number of cycles, but you can upper bound the number of hamiltonian paths easily with a similar argument (with the bonus that you can solve parts of it exactly to improve your bound with symmetry arguments). This is the strategy I'd choose.

But if you don't want this, some generic heuristics:

You can also easily upper bound the number of hamiltonian paths as |E| choose |V|-1 (where |E| is the number of edges and |V| the number of vertices in the graph), which can be a lot better for a sparse graph than |V|! (the naive bound that assumes that the graph is complete).
An easy way to improve this bound is by trimming known-bad combinations, by not considering twice edges from the same vertex. So you'd get something like prod_v(deg_v-1) (which should still upper bound the number of hamiltonian paths, since you're now counting cycles more than once, I think).


Complexity of computing generalised determinants. (P - #P transition) Computing the determinant of a matrix can be done in polynomial time, while computing the permanent is known to be #P-hard. Let $A$ be an $n \times n$ matrix. Define a generalised determinant function as follows,

$$ Det_ \theta (A) = \sum_ {\mu \in S_n} e^{i \theta ~ sign(\mu)} A_{1,\mu (1)} \ldots A_ {n , \mu(n)}$$.

$S_n$ is the symmetric group on $n$ elements. It can be readily seen that  $Det_0 (A) = Perm(A)$ and $Det_{\pi/2}(A) = i Det(A)$.

For what value of $\theta$ does the computation of $Det_\theta{A}$ cease to be #P-hard?
For what value of $\theta$ does $Det_\theta{A}$ become poly time computable?
As $\theta$ varies how does the complexity of computation of $Det_\theta{A}$ change in general?

ps - Some physics- Prima facie $Det_\theta{A}$ looks like the analogue of Slater determinant corresponding to Anyon wavefunctions.

I extend my comment in an answer.

By rewriting $e^{i \cdot sgn(\mu)\theta} = \cos(sgn(\mu)\theta)+i\sin(sgn(\mu)\theta) = \cos(\theta)+i \cdot sgn(\mu)\sin(\theta)$ we have: $Det_\theta(A) = \cos(\theta)Perm(A)+i\sin(\theta)Det(A)$. Thus, if $\cos(\theta) \neq 0$, we have $Perm(A) = (Det_\theta(A)-i\sin(\theta)Det(A))/\cos(\theta)$, meaning that $Det_\theta$ is $\#P$-hard (and $VNP$-complete over $\mathbb{C}$).

Several generalizations of the determinant have been studied however. Peter Bürgisser studies the complexity of immanants in his Habilitationschrift "Completeness and Reduction in Algebraic Complexity Theory" (http://math-www.uni-paderborn.de/agpb/work/habil.ps). Nicolas de Rugy-Altherre studied the complexity of one of them, the Fermionant, and proves other $VNP$-completeness results for such functions in "Determinant versus Permanent: salvation via generalization? The algebraic complexity of the Fermionant and the Immanant", https://arxiv.org/abs/1309.2156.

Hyperdeterminants (https://en.wikipedia.org/wiki/Hyperdeterminant) is a generalization of determinants to tensors. See "New algorithms for linear k-matroid intersection and matroid k-parity problems" by A. Barvinok for identities and algorithms on hyperdeterminants.


Are there any intersections between Theory A and Theory B? In the following two questions Origins and applications of Theory A vs Theory B? and Solid applications of category theory in TCS?, many people shared their knowledge and opinions about the division of those two areas in theoretical CS.

I am a student in mathematics with experience in both graph theory and category theory, crucial mathematical knowledge for theory A and B, respectively, and I am seeking to learn more and probably even do some serious research in theoretical CS. I am interested in whether there are any intersections between theory A and B, and if so, are there any people who have done some work in the intersections or at least are there any references in this topic?

One cool example of work that straddles things that are typically considered theory A and things typically considered theory B are the lower bounds on the running time of the simplex algorithm with randomized pivoting rules, due to Friedmann, Hansen, and Zwick. The lower bounds rely on lower bounds for policy iteration algorithms for parity games, which are a tool used in formal verification and automata theory.


Complexity of unbalanced bipartite isomorphism For $i=1,2$, let $G_i=(A_i\cup B_i,E_i)$ be an undirected bipartite
graph with bipartition $A_i$ and $B_i$, where $|A_1|=|A_2|=a$ and
$|B_1|=|B_2|=b$ with $a\le b$.

  Question. Is the problem of deciding isomorphism between
  such graphs solvable in $O(b^k 2^a)$ time, for some constant $k>0$?

Note that Babai's result yields a $2^{(\log(a+b))^c}$ time
algorithm for some constant $c>1$.
For the cases with $a=O(\log b)$, a solution to my question would
yield a polynomial time complexity.

If you are willing to relax the 2 to some other constant, then yes: this can be solved in $O(c^a)$ time for some absolute constant $c$. You can view this problem as isomorphism of hypergraphs, where the vertices in $A_i$ are the vertices of your hypergraph, and the vertices in $B_i$ are hyperedges. Luks (STOC '99) showed how to solve hypergraph isomorphism for hypregraphs on $a$ vertices in $O(c^a)$ time for some absolute constant $c$.


Split or merge Binary Search Trees in O(log n) We need to have an efficient operation of merging or splitting two binary search trees $S_1$ and $S_2$. There are given the following.

The element with the largest value in $S_1$ is smaller than the element with the smallest value in $S_2$. Abusing the notation $S_1 < S_2$.

We define as merge operation the operation which requires the two trees $S_1$ and $S_2$ and produces a valid binary search tree $S$ containing all of their elements.

Similarly, $S$ is split in two binary search trees $S_1$ and $S_2$ given an element $k$ for which (abusing the terminology again) $S_1 \le k < S_2$.

The best solution I have come up with in order to convince myself that this is possible, is by using splay trees. To merge we put the smallest element of $S_2$ as the root of the new tree with $S_1$ as the left subtree and $S_2$ as the right subtree (alternative we use the largest element of $S_1$ if it smaller). Amortized time $O(\log n)$. Similarly, we split by searching for the element $k$... Amortized time $O(\log n)$ again.

Is there anything better?

(Sorry for the lack of imagination in my question, this is my first post here.)

Treaps support both operations in $O( \log n)$ time with high probability. The trick is to give the splitting element $0$ priority making it the root, splitting the trees, and then reverting its priority to the original value. Merging is done similarly.


Chromatic number of G+v where G is a cograph Cograph is a well-know graph that does not have induced $P_4$. My questions are about determining the chromatic number of graphs in the class cograph+v.

Notations:

Denote by $\chi(G)$ the chromatic number of a graph $G$.
Let $V(G)$ denote the vertices of $G$. For any vertex $v\in V(G)$, denote by $N(v)$ the neighbors of $v$ and $N[v]=N(v)+v$ the closed neighborhood of $v$. Let $A\subseteq V(G)$, denote by $\langle A \rangle_{G}$ be the induced subgraph of $A$ of $G$.
Let $G$ be an undirected simple graph, and $H=G+v$ be a graph such that $G=H-v$, i.e., $G$ is the graph obtained by deleting $v$ from $H$. This type of notation is introduced in the paper Parameterized complexity of vertex colouring. For a graph class $\mathcal{F}$, let $\mathcal{F}+kv$ denote the graphs which can be built by adding at most $k$ vertices to a graph in $\mathcal{F}$.

Question 1:
Is the following statement true?

$\chi(G+v)=\chi(G)+1$ if and only if $\chi(\langle N(v) \rangle)=\chi(G)$, where $G$ is a cograph.

The "if" direction is easy, because $\chi(G+v) \le \chi(G)+1 $ and $\chi(\langle N[v] \rangle) = \chi(\langle N(v) \rangle) + 1$.
For general simple graph $G$, the "only if" direction is not true. For example, let $G$ be a $P_4$ (path of 4 vertices) and $G+v$ be a $C_5$ (cycle of 5 vertices).

Question 2:
If the proposition in question 1 is false. Is it easy to determine $\chi(G+v)$, where $G$ is a cograph.

Update: Jim showed than cograph+v is a subset of the class of perfect graph. Also he actually proved another more general theorem.

For any perfect graph $G$, $\chi(G)=\chi(G-v)+1$ if and only if $\chi(\langle N(v)\rangle) = \chi(G-v)$.

I think Artem is on the right track with perfection:

As cographs are $P_4$-free, cograph+v is $C_5$-free (and $C_{2k+1}$-free and $\overline{C}_{2k+1}$-free, $k>1$) and so they are perfect graphs.

This means the only thing that is pushing the chromatic number up is clique size. So if $\chi(G+v) = \chi(G) + 1$, it is because v has increased the maximum clique size, which means that $N(v)$ must have had a clique of size $\chi(G)$ and so $\langle N(v)\rangle_G$ had the same chromatic number as $G$.

So it seems the statement in question 1 is true.

But even without it, since cograph+v can't have any large induced cycles, it is contained in the set of weakly chordal graphs. A graph $G$ is a weakly chordal graph if for every cycle of length at least 5 in $G$ and $\overline{G}$, there is a chord. Weakly chordal graphs are a subset of perfect graphs and there are various efficient algorithms for a number of optimization problems on weakly chordal graphs, such as colouring.


What is the role of the Bicolored Calculus of Constructions? So, I'm reading a bit about elaboration, particularly, algorithms based on the Bicolored Calculus of Construction, and I'm a bit confused. I don't understand what exactly the purpose of the $CC^{bi}$ is. It seems to be identical to $CC$ except there is a distinction between implicit and explicit arguments for functions. In particular, I don't see how it allows you to write $(id\; 0)$ instead of $(id\; \mathbb{N}\; 0)$. If we assume a system for global definitions, then,

$id : (\Pi A\; |\; \mathsf{Type}\; . (\Pi x : A\; . A))$

and

$id = (\lambda A\; |\; \mathsf{Type}\; . (\lambda x : A . x))$.

Do the rules really allow for $(id\; 0)$? Of course the syntax does, but I don't see it in the typing relation. Am I missing something? Am I understanding the role of $CC^{bi}$ incorrectly?

Also, isn't the property of confluence lost? I guess my problem is that I'm reading about elaboration without having read much about $CC^{bi}$ before this. What's a good paper that introduces it and it alone?

Edit: To be more specific, I am asking how $(id\; 0)$ is accepted in place of $(id\; \mathbb{N}\; 0)$ when the rules for both explicit and implicit $\Pi$ application are identical modulo sytnax. I see no difference between $:$ and $|$ the rules for both seem the same.

Edit: I am not talking about the Implicit Calculus of Constructions, which is a different theory and has different rules for explicit $\Pi$'s (application vs. generation.)

Edit: Okay, I think I'm starting to understand this but I won't answer this question until I'm sure. Basically $(id\; 0)$ does not type check and in fact it is just elaborated to $(id\; \mathbb{N}\; 0)$ right before type checking or done as a secondary responsbility of the type checking algorithm. Essentially these implicit calculi are intended to be interface (user-end) languages which are elaborated into the usual (explicit) calculi or at least the explicit fragment of the implicit calculi before the terms are type checked. If that is the case, then I think I see the big picture. Can someone please confirm this?

In The Implicit Calculus of Constructions
Extending Pure Type Systems with
an Intersection Type Binder and Subtyping, Alexandre Miquel introduces the basic concepts for the Implicit Calculus of Constructions, which I believe is synonymous with the Bicolored Calculus of Constructions.

The point is (among other things) to have a calculus without the clutter of explicit type annotations everywhere. Type inference is (very likely to be) undecidable though.

In this calculus, if we take $id=\lambda x. x$, then you can derive
$$ \vdash id\colon \forall X\colon Type. X\rightarrow X$$
by simply using the explicit product and the implicit product rules in succession. Then the instantiation rule for the implicit product allows
$$ \vdash id\colon Nat\rightarrow Nat $$
and so
$$ \vdash id\ 0 \colon Nat$$
The system admits subject reduction and confluence, even on untyped terms (which in fact fails for calculi with abstraction annotations). All this can be found in Alexandre's thesis, which is sadly in French. Not sure I have a better reference for these results though I'm afraid.


Strongly NP-complete variants of subset sum or partition problem Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA problem is NP-complete.

Also, Factoring decision problem has sub-exponential time algorithm and it is not believed to be NP-complete. Meanwhile, a variant of factoring problem is NP-complete.

Subset-sum and partition problems are weakly NP-complete problems since they have pseudo-polynomial time algorithms. I am interested in their variants that are strongly NP-complete.

  Are there known variants of subset-sum or partition problem that are strongly NP-complete?

P.S. I am not interested in 3-partition problem.

It's like cheating, but if you change the representation of the numbers in the input then the problem becomes strongly NPC:

SUBSET SUM OF FACTORIZED SEMIPRIMES "SUBSUMS"

Input: A list of $N+1$ integers: $q_0$ and $A = \{q_1, ..., q_N\}$ each one represented as a (sub)sum of factorized (semiprime) integers; i.e. $q_i$ is given as $p_{i,1} 2^{a_{i,1}} + ... + p_{i,m_i} 2^{a_{i,m_i}}$ where $p_{i,j} \geq 3$ is a prime and $a_{i,j}$ is its "shift" exponent (in other words the input is the list of integers $p_{1,1}, a_{1,1}, p_{1,2}, a_{1,2},  ..., p_{2,1}, a_{2,1}, p_{2,2}, a_{2,2}, ...$)

Output: Does there exist a subset of $A' \subseteq A$  such that $\sum_{q \in A'} q = q_0 $?

Easy reduction from the strongly NPC problem $X3C$.


What classes of mathematical programs can be solved exactly or approximately, in polynomial time? I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The continuous optimization community seems to claim that all convex programs can be solved efficiently, but I believe their definition of "efficient" does not coincide with the TCS definition.

This question has been bothering me a lot in the last few years, and I can not seem to find a clear answer to it. I hope you could help me settle this once and for all: Which classes of MPs can be solved exactly in polynomial time, and by which means; and what is known about approximating the optimal solution of MPs that we can not solve exactly in polynomial time?

Below, I give an incomplete answer to this question that is also possibly incorrect at some places, so I hope you could verify and correct me at the points where I'm wrong. It also states some questions that I cannot answer.

We all know that linear programming can be solved exactly in polynomial time, by running the ellipsoid method or an interior point method, and subsequently running some rounding procedure. Linear programming can even be solved in time polynomial in the number of variables when facing a family of LPs with any super large amount of linear constraints, as long as one can provide a "separation oracle" for it: an algoritm that, given a point, either determines whether that point is feasible or outputs a hyperplane that separates the point from the polyhedron of feasible points. Similarly, linear programming in time polynomial in the number of constraints when facing a family of LPs with any super large amount of variables, if one provides a separation algorithm for the duals of these LPs.

The ellipsoid method is also able to solve quadratic programs in polynomial time, in case the matrix in the objective function is positive (semi?)definite. I suspect that, by using the separation oracle trick, we can in some cases also do this if we are dealing with an incredible number of constraints. Is that true?

Lately semidefinite programming (SDP) has gained a lot of popularity in the TCS community. One can solve them up to arbitrary precision by using interior point methods, or the ellipsoid method. I think, SDPs cannot be solved exactly due to the problem that square roots can not be computed exactly. (?) Would it then be correct if I say there is an FPTAS for SDP? I have not seen that stated anywhere, so that's probably not right. But why?

We can solve LPs exactly and SDPs up to arbitrary precision. What about other classes of conic programs? Can we solve second-order cone programs up to arbitrary precision, using the ellipsoid method? I don't know.

On which classes of MPs can we use the ellipsoid method? What properties does such an MP need to satisfy such that an answer can be given up to arbitrary precision, and what additional properties do we need in order to be able to obtain an exact solution in polynomial time? Same questions for interior point methods.

Oh, and finally, what is it that causes continuous optimizers to say that convex programs can be solved efficiently? Is it true that an arbitrary-precision answer to a convex program can be found in polynomial time? I believe not, so in what aspects does their definition of "efficient" differ from ours?

Any contribution is appreciated! Thanks in advance.

I can answer this part:

  Would it then be correct if I say there is an FPTAS for SDP?  I have not seen that stated anywhere, so that's probably not right.  But why?

The statement is correct, but we do not often see it because a stronger statement holds and is more important than this weaker statement.

An FPTAS is a polynomial-time algorithm which, given a problem and an accuracy parameter 1k, outputs a (1+1/k)-approximate solution.

But for SDP, the ellipsoid method and the interior-point method provide polynomial-time algorithms which, given a problem and an accuracy parameter 1k, output a (1+2−k)-approximate solution.  Note that the approximation factor is much better than what is required for an FPTAS.


Is there a linear time algorithm for integer multiplication verification? There is a quadratic randomized algorithm for matrix product verification.
Is there a similar trick to 'verify given three integers $n,a,b$ if $n=ab$ holds?' in $O(\log n)$ time?

There is a linear time randomized algorithm, that is of complexity $O(\log n)$: Cf M. Kaminski, A note on probabilistically verifying integer and polynomial products, J. ACM 36(1), pp. 142–149, Jan. 1989.
The basic idea: Instead of checking $n = ab$ modulo $p$ for some random prime number $p$, check it modulo $2^i-1$ for some integer $i$. The reduction modulo $2^i-1$ is fast (faster than modulo a prime $p$) since only additions are required. And if you take $i = O(\log^{1-\epsilon} n)$, the computation of $(a\bmod 2^i-1)(b\bmod 2^i-1)$ can be done in (sub)linear time. Kaminski proves that if $n\neq ab$, $n\not\equiv ab\bmod 2^i-1$ with high probability.


Set of functions computable in polynomial time I write paper and I want to distinguish between the class of decision problems which can be decided in polynomial time and the class functions which can be computed in polynomial time.
The first is just written as $\mathrm{P}$ or $\mathrm{PTIME}$, right? Can the latter be denoted as $m^{\mathcal{O}(1)}$ or is this a confusing definition?

The notation $m^{O(1)}$  just denotes the set of functions of polynomial growth rate, so that would be indeed confusing. The class of functions computable in polynomial time is usually denoted $\mathsf{FP}$.


Is the following optimization problem NP-hard? Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight $w_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:

$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$
$$\text{s.t.} x_{ij}+x_{ik} \le 1 $$
$$x_{ij}+x_{jk} \le 1 $$

Note this problem is not the Maximum Weighted  Matching problem as edges that share the same end point are allowed.

The new version of the problem is indeed NP-hard.

Reduction from set cover: Subsets are $S_1, S_2, ..., S_m$ and the universe is $U = \{ a_1, a_2, ..., a_n \}$. Construct a node-weighted directed graph $(N,S,c)$ as follows:

Nodes are $N = \{ a_1, a_2, ..., a_n, S_1, S_2, ..., S_m, S'_1, S'_2, ..., S'_m \}$.
Edges are: $(a_j,S_i)$ iff $a_j \in S_i$, and $(S_i,S'_i)$ for all $i$.
Weights are: $w(a_j) = M$ for all $j$, and $w(S_i) = 1$ and $w(S'_i) = 0$ for all $i$.

Now if there is a set cover $X$ of size at most $k$, we can get the benefit of at least $nM + m - k$ as follows:

For each $a_j$ pick one set $S_i \in X$ in the cover with $a_j \in S_i$, and choose the edge $(a_j,S_i)$; we get the benefit of $M$ from $a_j$.
For each $S_i \notin X$ we choose the edge $(S_i, S'_i)$; we get the benefit of $1$ from $S_i$.

Conversely, if we can get the benefit of at least $nM + m - k$, then we have at most $k$ nodes in $\{S_1, S_2, ..., S_m\}$ and all of the nodes in $U$ must have outgoing edges; this gives a set cover of size at most $k$.


#P-complete problems are at least as hard as NP-complete problems I just read

J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)

and one of the first sentences is

  Valiant defines the notion of the #P-complete class (...) and shows that problems in this class are at least as hard as NP-complete problems.

My first problem is that is seems weird to directly compare the complexity of counting and decision problems. But more importantly: There are quite easy decision problems, whose counting variant is #P-complete, for example satisfiability of boolean formulas in DNF. This can also be read on Wikipedia:

http://en.wikipedia.org/wiki/Sharp-P-complete

So is the statement, that a #P-complete problem is at least as hard as a NP-complete problem simply wrong or am I getting something wrong?

It's not at all weird to compare the complexity of counting and decision problems: reductions allow you to do that very naturally. You can use reductions to compare any kind of problem: decision, counting, approximate counting, optimization, function problems, ... All of this follows from the intuitive notion that a reduction from A to B means "If I could solve B, I could also solve A at roughly the same cost."

The existence of easy decision problems whose counting version is hard is a red herring. Counting matchings is the hard problem: if you could do that, you could solve any NP problem by reduction. Detecting matchings is easy: you can do that but it doesn't (seem to) help you to solve NP-complete problems.


Is there any work done on developing difference-calculus of Turing Machines (or simpler Formal Languages) I am attempting to develop some notions of a difference-calculus between a notional Ideal Turing Machine conceived by a developer (e.g. whatever is intended by a software developer), call it $M_I$, and the Machines that represent the software which actually gets designed and implemented, say $M_\alpha$ and $M_\beta$, respectively.

Specifically, my interest is in examining limitations (due to Rice's Theorem for instance) in automated detection of errors in software programs between the Language processed by the ideal machine, and the language processed by the developed/implemented Machines.

Any reference to prior work that works with some notions of exploring differences between two specified Turing Machines, or barring that a lower level Formal Language would be extremely helpful and appreciated; because i'd rather cite than write :-).

As it turns out, there is some fascinating work done in this direction.

In particular, in 2003, Michael Howard, Jon Pincus, and Jeannette M. Wing's Measuring Relative Attack Surfaces in proceedings of Workshop on Advanced Developments in Software and Systems Security, Taipei, December 2003.

Further work by the same authors over the years is quite interesting ... For anyone who found my question of interest you can check their work out at http://www.cs.cmu.edu/~pratyus/as.html ... And if you find them interesting, i hope that you will find my work interesting too :)


Transposition of any characters in Damerau–Levenshtein edit distance computation Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters?

Maybe some heuristic would help?

update

I will identify the application.

I have two sequences of characters. An "Old" one and a "New" one. I need to compute editorial prescription (is it a correct English term?) as a series of actions that could be applied to an "Old" sequence to make it equal to a "New" one.

There are not more than 10-20 characters in a sequence in most cases, thus O(n) is not so important.

The important part is... characters in that "Old" sequence have some metadata assigned to each other. That's why transposition is more welcome than remove/insert when it's possible.

My goal is to make an "Old" sequence equal to a "New" one preserving that metadata as much as possible.

Thanks for updating the question - here goes an answer tailored to your application:

Since we are dealing with realatively small instances we could define an optimal algorithm based on a backtracking branch and bound schema (Presentation on B&B - easy, Something more thorough with common application) by constructing a "path" of permutations with following assuptions:

We want to promote swaps to preserve metadata - cost = 1
We want to penilize other operations but allow them if nessesary - cost = 2
Dissalow "stupid" moves ex. Inserting a letter that's not in the target sequence
Innitial Upper Bound = Levensthein (plain version not the Damerau extension) x 2 (because of the costs)
Lower Bound current path cost + how many letters (disregard positions) do not match in current and target sequences Example:
i have ABCCDD
i want CCWGZDD

the cost added to current path is (1 (W) + 1 (G) + 1 (Z) + 2 (D)) = 5
(probably there is room for a better Lower Bound but it's usually non-trivial to come up with one)

Each time you get to target sequence and path cost is lower than Upper Bound - update it and backtrack.
Each time your Lower Bound exeeds Upper Bound - backtrack

Please google backtracking algorithms and branch and bound for more information. Should you like the solution but have no idea how to go about implementing it please let me know (PW) I'll try to cook-up some pseudocode for you.

The algorithm in worst case is exponential but on real istances should perform very well.


(Cryptographic) problems solvable in a polynomial number of arithmetic steps In the paper from Adi Shamir [1] from 1979 he shows, that factoring can be done in a polynomial number of arithmetic steps. This fact was restated, and thus came to my attention, in the recent paper of Borwein and Hobart [2] in the context of straight line programs (SLP).

Since I was rather surprised to read this, I have the following question: Are there any other cryptographic problems or maybe also other relevant problems, that can be solved in a polynomial number of steps with a SLP and that are currently not known to be solvable efficiently on a "normal" classical computer?

[1] Adi Shamir, Factoring Numbers in $O(\log n)$ arithmetic steps. Information Processing Letters 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, The Extraordinary Power of Division in Straight Line Programs,
The American Mathematical Monthly Vol. 119, No. 7 (August‒September 2012), pp. 584-592

I did not read the paper as well but the abstract seems to say that an exponenial number of bit operations are required.

Chebyshev's work on congruences and its reformulation in the AKS algorithm show that prime generation is in P. Therefore trial division yields non-trivial factors. In that case, for some number N, you can expect a density of primes of 1/ln(N).

Furthermore, you can have a look at Turing's 1937 PhD thesis on the subject.


Quantum matrix multiplication? It doesn't seem like this is known - but are there any interesting lower bounds on the complexity of matrix multiplication in the quantum computing model?  Do we have any intuition that we can beat the complexity of the Coppersmith-Winograd algorithm using quantum computers?

In arXiv:quant-ph/0409035v2 Buhrman and Spalek present a quantum algorithm beating the Coppersmith-Winograd algorithm in cases where the output matrix has few nonzero entries.

Update: There is also a slightly improved quantum algorithm by Dörn and Thierauf.

Update: There is an improved quantum algorithm by Le Gall beating Burhman and Spalek in general.


What is the complexity of rectangle packing when rotations are allowed? In the rectangle packing problem, one is given a set of rectangles $\{r_1,\dots,r_n\}$ and bounding rectangle $R$.  The task is to find a placement of  $r_1,\ldots,r_n$ inside $R$ such that none of the $n$ rectangles overlap.
Generally, the orientation of each rectangle $r_i$ is fixed.  That is, the rectangles cannot be rotated.  In this case, the problem is known to be NP-complete (see, e.g., Korp 2003).

What is the complexity of the rectangle packing problem if rectangles can be rotated by $90$ degrees?

Intuitively, allowing rotations should only make the problem harder since one should first choose an orientation for each rectangle, and then solve the no-rotation packing problem.  But the NP-hardness proof of the no-rotation case is a reduction from bin-packing and seems to critically depend on the fixed orientation of each rectangle in order to construct the bins.
I have not been able to find a corresponding NP-hardness proof for the case in which rotations are allowed.

We can reduce the no-rotations packing problem to the rotations-allowed packing problem as follows.  Take any instance $(R, r_1, r_2, \dots, r_n)$ of the no-rotation problem.  Vertically scale the entire instance by twice the ratio of the smallest width of any rectangle $r_i$ divided by the height of the container rectangle $R$.  (This ratio has a polynomial number of bits, so the transformation can be executed in polynomial time.)  Each scaled rectangle $r'\!\!_i$ fits inside the scaled container $R'$ only in its original orientation, so allowing rotations adds no new solutions.


Easy decision problem, hard search problem Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete).

What are some other examples of problems where the decision version is easy but the search version is relatively difficult (compared the the decision version)?

I would be particularly interested in problems where the decision version is non-trival (unlike the case with Nash equilibrium).

Given an integer, does it have a non-trivial factor? -> Non-trivially in P.

Given an integer, find a non-trivial factor, if there is one -> Not known to be in FP.


Bob's Sale (reordering of pairs with constraints to minimize sum of products) I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well.

Someone has already asked a question related to this problem here - Minimum weight subforest of given cardinality - but as far as I understand it doesn't help me with my problem. The highest-rated answer on StackOverflow is also worth looking at.

Here's the verbatim copy of my StackOverflow question. It's probably inadequately formulated for this site (heck, I feel inadequately uneducated just asking it here), so feel free to edit it:

Note: this is an abstract rewording of a real-life problem regarding ordering records in a SWF file. A solution will help me improve an open-source application.

Bob has a store, and wants to do a sale. His store carries a number of products, and he has a certain integer quantity of units of each product in stock. He also has a number of shelf-mounted price labels (as many as the number of products), with the prices already printed on them. He can place any price label on any product (unitary price for one item for his entire stock of that product), however some products have an additional restriction - any such product may not be cheaper than a certain other product.

You must find how to arrange the price labels, such that the total cost of all of Bob's wares is as low as possible. The total cost is the sum of each product's assigned price label multiplied by the quantity of that product in stock.

Given:

N – the number of products and price labels
Si, 0≤i<N – the quantity in stock of product with index i (integer)
Pj, 0≤j<N – the price on price label with index j (integer)
K – the number of additional constraint pairs
Ak, Bk, 0≤k<K – product indices for the additional constraint

Any product index may appear at most once in B. Thus, the graph formed by this adjacency list is actually a set of directed trees.

The program must find:

Mi, 0≤i<N – mapping from product index to price label index (PMi is price of product i)

To satisfy the conditions:

PMAk ≤ PMBk, for 0≤k<K
Σ(Si × PMi) for 0≤i<N is minimal

Note that if not for the first condition, the solution would be simply sorting labels by price and products by quantity, and matching both directly.

Typical values for input will be N,K<10000. In the real-life problem, there are only several distinct price tags (1,2,3,4).

Here's one example of why most simple solutions (including topological sort) won't work:

You have 10 items with the quantities 1 through 10, and 10 price labels with the prices $\$$1 through $\$$10. There is one condition: the item with the quantity 10 must not be cheaper than the item with the quantity 1.

The optimal solution is:

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

with a total cost of $\$$249. If you place the 1,10 pair near either extreme, the total cost will be higher.

This is a follow-up on Gero's answer.  The idea is to modify his construction to show strong NP-hardness.

Instead of choosing $t_i=(2b+1)^i$, chose $t_i=i$.  Now, you have to modify the argument that a solution with prize $P=2b\sum_{1\leq i \leq k} t_i$ implies that there exists a 3-partition.

Take an arbitrary shelf order.  Do the accounting in the following way: distribute $w_i-1$ units of quantity of the root-product to its leaf-products.  Then every product has quantity 2.  By definition of the constraints, this does not shift to a higher price.
After this shifting, the price will be exactly $P$.
If the shifting moved some quantity to a lower prize, the original prize was strictly larger than $P$.

Hence, it is only possible to achieve the claimed prize, if all leaf-products have the same prize as their root-product, which means that there exists a 3-partition.

Citing the result from a SWAT 2010 paper this argument shows that even with unary encoding of the numbers and $k$ different price tags, a running time of $f(k)\cdot n^{O(1)}$ would violate "standard complexity assumptions".
This makes the hinted at dynamic programming with a running time of $n^{O(k)}$ look not so bad.

Also cross-posted to the original stack-overflow question.


Generalizations of Brzozowski's method of derivatives of regular expressions to grammars? Brzozowski's method of derivatives is a very pretty technique for building deterministic automata from regular expressions in a nicely algebraic way. I've worked out some cute generalizations of this technique to handle some larger classes of grammars, but the algorithms are straightforward enough that it seems quite possible that they've been discovered before. But Googling references to descendants of this technique doesn't seem to turn up much. Anyone know of anything?

You might be interested in this paper:

  Yacc is Dead by Matthew Might and David Darais, 2010

  We present two novel approaches to
  parsing context-free languages. The
  first approach is based on an
  extension of Brzozowski's derivative
  from regular expressions to
  context-free grammars. The second
  approach is based on a generalization
  of the derivative to parser
  combinators. The payoff of these
  techniques is a small (less than 250
  lines of code), easy-to-implement
  parsing library capable of parsing
  arbitrary context-free grammars into
  lazy parse forests. Implementations
  for both Scala and Haskell are
  provided. Preliminary experiments with
  S-Expressions parsed millions of
  tokens per second, which suggests this
  technique is efficient enough for use
  in practice.

Also of potential interest:

Yacc is Not Dead, review of this paper by Russ Cox, of re2 fame.
Yacc is dead: An update, reply from Matt Might.
Functional Pearl: Parsing with Derivatives by Matthew Might, David Darais and Daniel Spiewak - an updated version of the "Yacc is Dead" paper, presented at ICFP 2011 in Tokyo.


Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT Stated briefly, my question is: is Karp's original proof reducing SAT to 3SAT  unnecessarily elaborate?  The details are as follows.

In his 1972 paper Reducibility Among Combinatorial Problems, Karp proved that SAT reduces to 3SAT by stating:

  Replace a clause $\sigma_1 \cup \sigma_2
 \cup \ldots \cup \sigma_m$, where the
   $\sigma_i$ are literals and $m>3$, by
   $$
   (\sigma_1 \cup \sigma_2 \cup u_1)
   (\sigma_3 \cup \ldots \cup \sigma_m \cup \bar{u}_1) (\bar{\sigma}_3 \cup u_1) \ldots (\bar{\sigma}_m \cup u_1),
 $$
   where $u_1$ is a new variable. Repeat this
   transformation until no clause has more than
   three literals.

It seems to me that the final $m-2$ clauses (i.e. the clauses containing two literals) here are unnecessary. So, the construction is correct as written but it is more elaborate than necessary. Without the 2-literal clauses,  we obtain the construction usually given in undergraduate textbooks.   Is this correct, or am I missing something obvious?   I feel extremely unsure of myself suggesting that anything done by Karp could be expressed more elegantly.

The conjunction of the first two clauses, $(\sigma_1\cup\sigma_2\cup u_1)(\sigma_3\cup\ldots\cup\sigma_m\cup\bar{u}_1)$ is equisatisfiable to the original clause, as can be easily checked (any valuation satisfying one of the $\sigma_i$ also satisfies one of the two new clauses, and can be extended to $u_1$ as needed to satisfy the other; any valuation satisfying both new clauses has to satisfy some $\sigma_i$, since it cannot satisfy both $u_1$ and $\bar{u}_1$.)

The additional clauses ensure that $u_1$ is in fact equivalent to $\sigma_3\cup\ldots\cup\sigma_m$, but as far as I can see, Karp does not actually use this. He credits Cook's 1971 paper for this particular reduction, but the version found there (actually for DNF tautologies rather than CNF satisfiability) does not feature these extra constraints.


$FNP$ ,$ \#P$,$\oplus P$ classes I was trying to understand these classes but always got confused ... the questions are :

What is the relation between $FNP$ and $\#P$ , in particular is it an open question ?

What is the relation of $\oplus P$ and $NP$ ? is this question open ?

What about the relationship between $PH$ and $P^{FNP}$ ? is this question open ?

1)$\bf FNP$ is contained in $\bf FPH$, which is called the "functional polynomial hierarchy", where every function in $\bf FPH$  is polynomial time 1-Turing reduciable to some function in $\bf \#P$.
2)We know from the Valiant Vazirani theorem that $\bf NP$ $\subseteq$ $\bf RP^{PromiseUP}$. We also know that $\bf UP$ $\subseteq$ $\bf \oplus P$. Therefore, we have $\bf NP$ $\subseteq$ $\bf RP^{\bf \oplus P}$.


Why do non-proper types have no terms? I'm attending a course on Type Theory. The textbook is 'Types and Programming Languages' by Prof. Benjamin C. Pierce.

In Chapter 29, Prof. Pierce introduces 'type operator', which can generate another type with an input type. For example, 'Pair' can be a type operator which accepts any two types $X$ and $Y$ to form a type $Pair\; X\; Y$.

However, the 'type operator' itself is a type - a special type which is different from 'proper type' such as $Nat$ and $Nat \rightarrow Nat$. It seems that all 'proper types' have terms of it. For example, $Nat \rightarrow Nat$ has at least $(\lambda x : Nat. x)$. But type operator like $Pair$ does not have any term of it.

Prof. Pierce doesn't explain why $Pair$ has no term. Why 'non-proper' types can be called a 'type' when it does not correspond to any collection of programming language terms?

The best way to understand this is to have a second level of "types above types" which we then call kinds. Kinds can be formed by the following rules:

Type is a kind.
If K and L are kinds then so is K → L.

Kinds have elements:

The elements of Type are types, such as nat, bool, nat → nat, nat × nat, etc.
The elements of K → L are functions which map elements of K to elements of L.

For instance, Pair is an element of Type → Type → Type. It is a "kind-level" function which maps types A and B to type A × B. Another example is List which is an element of Type → Type and it maps a type A to the type List A of lists of As.

A very fancy kind is (Type → Type) → Type which takes a function on types and returns a type. An example of this is "recursive type definition". To see this, consider the most general form of a recursive type definition:

type t = Φ(t)

For instance, we could define lists of numbers like this (using OCaml notation):

type natlist = Nil | Cons of nat * natlist

This is a special case of the general recursive type definition if we take

Φ(a) = Nil | Cons of nat * a

We could actually define an operator rectype and then write

type t = rectype Φ

to define the type t which is equal to Φ(t). Now it takes a moment's thought that rectype is of kind  (Type → Type) → Type. (At this point, if you have never seen this before, you should be having a minor epiphany.)

In Haskell Type is written as * so sometimes Haskell tells you that something has type * → *. This means that the thing is a type-level function taking types to types. In Ocaml there are kinds under the hood but they are never shown to the user (well, kind of since they get exposed through module types).

Professor Pierce of course knows all these things much better than I do, but most likely at this point in the course he does not want to burden you with another layer of $\lambda$-calculus on top of $\lambda$-calculus. A quick and dirty solution is to just put all the kinds together in one big messy pile and call them "improper types". The trouble with such things is that the smart students will get confused (and rightfully so).


Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$? Chaitin's incompleteness theorem states for any formal system $F$ (which satisfies various criteria), there is a $L$ such that for any $s$ the statement $$K(s) \ge L_F$$ is unprovable in that formal system. My question is, do we know what that constant is for ZFC. (Note that, like all questions involving Kolmogorov complexity, the specific value depends on the description language, but only up to an additive constant. If you want a specific language, you can use Binary combinatory logic, but once you find a $L_{ZFC}$ in one language, its trivial to find it in another.)

Note: I am not asking for the minimum $L_{ZFC}$, just any $L_{ZFC}$. In other words, I'm looking for an upper bound on the minimum $L_{ZFC}$.

(Note: This answer works for most any consistient theory, not just $ZFC$.)

We will define a machine $p$ based on the universal algorithm. $p$ does a search, looking for a string that represents a proof of a statement of the form "not ($p$ halts and outputs $n$)" (note that this requires quining, since it is self-referential), for some numeral $n$, such that the proof is valid in ZFC. When it finds such a proof, it outputs $n$.

Lemma: For any numeral $n$, if ZFC is consistient, ZFC does not prove the statement "not ($p$ halts and outputs $n$)".

Assume to the contrary that for some $n$, ZFC proves "not ($p$ halts and outputs $n$)". Then $p$ will find this proof, output $n$, and halt. Moreover, since $p$ must halt in a finite amount of time, we can construct a step by step proof of this in ZFC. That is, we can prove "$p$ halts and outputs $n$" in ZFC. This is a contradiction in ZFC, but ZFC is consistient by assumption. Therefore ZFC does not prove the statement "not ($p$ halts and outputs $n$)" for any numeral $n$.

Now, formalize $p$ into a program $\rho$. Let $$L_\text{ZFC} = |\rho|+1$$ Suppose that $ZFC$ proves for some $s$ that $K(s) \ge L_\text{ZFC} \gt |\rho|$. This implies that the machine that $\rho$ encodes, $p$, does not output $s$. But by the lemma, ZFC can not prove this! Therefore, there is no $s$ such that ZFC proves $$K(s) \ge L_\text{ZFC}$$

Now all that needs to be done is to actually create $\rho$ in some programming language, but we will leave that as an exercise to the programmer.


Decidability of type inference and type checking in MLTT In Martin-Löf's An Intuitionistic Theory of Types: Predicative Part it is proved that type checking $a \colon A$ is decidable subject to $a$ being typeable in the first place, by proving a normalization theorem for closed typeable terms.
On the other hand, I've seen it written in multiple places (Wikipedia, Nördstrom etc.) that type-checking in (intensional) MLTT is decidable; are they implicitly restricting to typeable terms?
Is anything known about the decidability of type inference or type checking in intensional MLTT if we do not restrict to the typeable terms?
For instance, perhaps there is a decision process that recognizes untypeable terms, say by normalizing to a form that doesn't correspond to any of the constructors, or by showing that there is no non-periodic sequence of reductions for any untypeable term.

I haven't been able to find very much in the literature.

Certainly the decision problem

  Given a (pre-)term $a$ Is there a type $A$ such that $\vdash a :A$ is derivable in MLTT?

Sometimes written $\vdash a\ :\ ?$ (and called the type inference problem) is decidable, which is to say it doesn't matter whether $a$ is well-typed or not to get an answer. Indeed, all proof checkers based on MLTT implement some version of this decision algorithm!

Obviously, the problem in a non-empty context ($\Gamma\vdash a\ :\ ?$) is decidable as well, usually you need to solve the latter to solve the former.

This should answer questions 1 and 2. The algorithm does not involve normalizing $a$, which in general would be bad news, since it is undecidable whether an untyped term normalizes to anything. However the type checking algorithm does involve normalizing types, which are by construction well-typed themselves.

As a result, normalization of well-typed terms is a necessary condition for the type inference problem to be decidable.

You might want to check Nordström, Petersson and Smith for an introduction.

I'm not aware of any generic description of a type inference algorithm for normalizing type theories, though Pollack gives a pretty good overview (though the state of the art has improved) in Typechecking in Pure Type Systems.


What is known about computing distinct count range queries? Let $U=\{1,\ldots, u\}$ be a universe of elements for some $u\in \mathbb N$.
Given some $n\in\mathbb N$, we are interested in computing some function $f:U^{\le n}\to\mathbb R$ over range queries.

In the Range Query problem we get an integer array $A[1,\ldots,n]\in U^n$ and wish to compute queries that takes as input parameters $1\le i\le j\le n$ and return $f(A[i,\ldots,j])$.

Consider the function $f$ that returns the number of distinct elements in the queried range.

The goal is to preprocess the input array $A$ and create a small summary that allows efficient computation of these distinct queries.

  What is the best known algorithm for the problem? (given a memory bound $m$, what is the minimal query time that is required).

.

  If we allow approximation of the number of distinct elements, can we get faster queries?

EDIT: I have found a related problem discussed in stackoverflow. The answer there shows a $O(n\log n\log u)$ bits algorithm that answers queries in $O(\log n)$ time.

Is this optimal?

Can we get better time/space bounds if we allow approximation?

A sketch data structure is an approximation of a set of elements. Sketches vary in what they store -- some store just hashes, some store elements from the set (a sample), and some store floating-point numbers.

This solution uses the sketch data structure from "A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection", by Cohen et al. It stores $k$ hash values.

Let $I = 2nk/m$. Let $F[t] = \{A[1], A[2], \dots , A[tI]\}$ and $B[t] = \{A[n], A[n-1], \dots, A[n-tI]\}$.  Store the sketches for $F[1],  F[2], \dots, F[m/2k]$ and $B[1],  B[2], \dots, B[m/2k]$. That is a total of $m/k$ sketches, each of size $k$, using a total of $m$ words of space.

Let $r(x)$ denote the value of $x$ rounded to the nearest integer. To estimate the carnality of $\{A[i], \dots, A[j]\}$, estimate the cardinality of $F[r(j/I)] \bigcap B[r((n-i)/I)]$. The Cohen et al. paper describes how to do this in $\text{poly}(k)$ time. The variance of the estimate is a long formula in Corollary 2, combined with the error induced by only using $m/k$ samples, which is at most $4nk/m$.


Question on subtyping of handlers in "An Effect System for Algebraic Effects and Handlers" I had a question on subtyping in the paper "An Effect System for Algebraic Effects and Handlers". I was wondering why there isn't a subtyping rule for adding effects on both sides of a handler type, something like this:

$$
\frac{
}{
T!A \;\Rightarrow\; R!B \;\leqslant\; T!(A \cup C) \;\Rightarrow \;R!(B \cup C)
}
$$

This would be useful when apply a variable with a handler type to a computation with more effects than the handler type has in its left side.

You can add effects to both sides of a handler type using the typing rule for handlers, but that won't work for variables. For example when the handler is an argument to a function.

I'm surprised we don't get this question more often, for Andrej and I have considered adding this rule for quite some time and believed to have proven its correctness. But in the end, it turned out to be false, at least in a call-by-value setting (I have heard it plays out nicer in call-by-push-value).

Consider the state handler, described on top of page 24 of the same paper, which takes a stateful computation of type $B$ on state $A$ and transforms it into a pure function from $A$ to $B$. Its type is $$B!\{\mathtt{lookup},\mathtt{update}\} \Rightarrow (A \to B ! \emptyset) ! \emptyset$$ Note the two empty sets on the right hand side. The first states that the resulting function is pure, the second one that there no effects occur when producing this function.

Now assume that we apply the handler to a computation that may call some other effects $\Delta$ besides $\mathtt{lookup}$ and $\mathtt{update}$. Applying the suggested rule, you would get the type $$B!(\{\mathtt{lookup},\mathtt{update}\} \cup \Delta) \Rightarrow (A \to B ! \emptyset) ! \Delta$$
but in fact, the correct type is
$$B!(\{\mathtt{lookup},\mathtt{update}\} \cup \Delta) \Rightarrow (A \to B ! \Delta) ! \Delta$$
as the unhandled effects $\Delta$ may occur before producing the function or after calling it.


Overlapping BFS Layers in Dominating Set with Baker's Technique (I'm not sure if this is an appropriate question for TCS.SE, but I'm not sure what is more appropriate).

When using Baker's Technique to find an approximation to the minimum dominating set of a planar graph, why must we overlap 2 BFS layers in every partition? I understand that for vertex cover each partition needs to overlap 1 layer to handle cases where an edge in the overlapped layer can only be covered by another vertex in the layer.

However, to my knowledge, vertex cover is just a reduction of dominating set, and any vertex cover is also a dominating set. Why do we need to overlap 2 layers for dominating set?

Of course, links to papers are great too--I just haven't found anything explaining the reason yet.

EDIT: David has a great answer below. There's also a paper describing the issue (with pictures) and a correction to Baker's original algorithm for Dominating Set here: http://www.mdpi.com/1999-4893/6/1/43 (PDF link)

In a single layer of the partition, consisting of the vertices at distance $d$ to $d+k$ from the root, the vertices at distance $d+1$ through $d+k-1$ can be dominated the same way as they are in the whole graph, but you have no control of the size of the dominating sets of the vertices at distances $d$ or $d+k$, on the boundary of the layer: in the original graph, those vertices could be dominated by a small number of vertices in a different layer that aren't there when you restrict to that layer. So the solution is to find a system of layers with the property that the subsets of vertices at distance $d+1$ through $d+k-1$ within each layer form a partition of the whole graph, and then within each layer to only try to dominate that subset. To do this, you need to overlap the layers by two levels.


Consequences of #P = FP Which would be the consequences of #P = FP?

I'm interested in both practical and theoretical consequences.

From a practical point of view, I'm particularly interested in consequences on Artificial Intelligence.

Pointers to papers or books are more than welcome.

Please do not say that #P = FP implies P = NP, I already know that. Also, please do not say "there will be no practical consequences if the algorithm runs in time $\Omega(n^{\alpha})$, where $\alpha$ is the number of electrons in the Universe": permit me to assume that, if a deterministic polynomial time algorithm for a #P-complete problem exists, its running time will be "clement" ($O(n^2)$, for example).

Here are a few theoretical consequences of the equality FP=#P, although they have nothing to do with artificial intelligence.  The assumption FP=#P is equivalent to P=PP, so let me use the latter notation.

If P=PP, then we have P=BQP: quantum polynomial-time computation can be simulated by classical, deterministic polynomial-time computation.  This is a direct consequence of BQP⊆PP [ADH97, FR98] (and of an earlier result BQP⊆PPP [BV97]).  On top of my knowledge, P=BQP is not known to follow from the assumption P=NP.  This situation is different from the case of randomized computation (BPP): since BPP⊆NPNP [Lau83], the equality P=BPP follows from P=NP.

Another consequence of P=PP is that the Blum-Shub-Smale model of computation over the reals with rational constants is equvalent to Turing machines in a certain sense.  More precisely, P=PP implies P=BP(Pℝ0); that is, if a language L⊆{0,1}* is decidable by a constant-free program over the reals in polynomial time, then L is decidable by a polynomial-time Turing machine.  (Here “BP” stands for “Boolean part” and has nothing to do with BPP.)  This follows from BP(Pℝ0)⊆CH [ABKM09].  See the paper for definitions.  An important problem in BP(Pℝ0) is the square-root sum problem and friends (e.g. “Given an integer k and a finite set of integer-coordinate points on the plane, is there a spanning tree of total length at most k?”) [Tiw92].

Similarly to the second argument, the problem of computing a specific bit in xy when positive integers x and y are given in binary will be in P if P=PP.

References

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen.  On the complexity of numerical analysis.  SIAM Journal on Computing, 38(5):1987–2006, Jan. 2009.  http://dx.doi.org/10.1137/070697926

[ADH97] Leonard M. Adleman, Jonathan DeMarrais and Ming-Deh A. Huang.  Quantum computability.  SIAM Journal on Computing, 26(5):1524–1540, Oct. 1997.  http://dx.doi.org/10.1137/S0097539795293639

[BV97] Ethan Bernstein and Umesh Vazirani.  Quantum complexity theory.  SIAM Journal on Computing, 26(5):1411–1473, Oct. 1997.  http://dx.doi.org/10.1137/S0097539796300921

[FR98] Lance Fortnow and John Rogers.  Complexity limitations on quantum computation.  Journal of Computer and System Sciences, 59(2):240–252, Oct. 1999.  http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Clemens Lautemann.  BPP and the polynomial time hierarchy.  Information Processing Letters, 17(4):215–217, Nov. 1983.  http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Prasoon Tiwari.  A problem that is easier to solve on the unit-cost algebraic RAM.  Journal of Complexity, 8(4):393–397, Dec. 1992.  http://dx.doi.org/10.1016/0885-064X(92)90003-T


Escaping references in Eff and resources In the paper "Programming with Algebraic Effects and Handlers" there is the issue where references (dynamic instances of a state effect, defined using algebraic effects) can propagate outside the scope of the handler. I assume the problem here is that calling an operation on the reference would result in an "unhandled operation" run-time error. "Resources" are introduced to remedy this problem, they seem like implicit handlers around the whole program.

What I was wondering is, if one had an effect system that tracked called operations then would references propagating outside the handler scope still be a problem? The unhandled operations called on the reference would be known statically in the effect system and so these problems can be ruled out, run-time errors of this kind wouldn't appear.

Resources would still be useful to reduce verbosity and to fully emulate ML-style references, but they would no longer be needed to avoid run-time errors if one had a sufficient effect system. Am I right in thinking this?

The problem "Does a reference escape its scope?" is undecidable. An effect system can only overapproximate the answer to the question, so there will necessarily by tricky situations in which the compiler will claim that a reference might be escaping its scope, but it really won't. However, this is unlikely to be a real problem. After all, if a sophisticated compiler can't tell whether a reference is escaping its scope, how can we expect humans to do it?

Note that there are uses of references where we want them to escape scope. Here are some such cases:

A function memo which takes another function f and returns its memoized form. Typically memo creates a local reference in which it stores the cache.
A self-optimizing data structure such as a self-balancing tree uses local references in the background, so that it can modify itself. Such structures are often referentially transparent, i.e., the optimizaiton has no observable effect other than better efficiency.
It is unrealistic to expect that nobody will ever implement any stateful data structures. These need to use state, and they must be allowed to escape the scope in which they were created, or else the structure of the entire program becomes a hostage to correct scoping of handlers.

A similar issue arises regarding instances of effects. A realistic programming language must allow dynamic creation of new effect instances. Some situations which require this are:

opening any number of files or communication channels: each is an instance of an effect, and we cannot tell at compile-time how many we need,
creating a list of references, where do not know ahead of time how many will be created.

Multicore OCaml simulates instances with first-class modules. To my mind that is a hack, as they're using the genericity of modules to simulate generation of fresh names, and as far as I can tell, it's difficult to write a handler that captures all instances of a given effect.

Let me also say that resources are not a hack. They are inspired by comodels by Plotkin and Powers. I find it a pity that the people who're doing effects largely ignore resources. They think it's possible to write programs without local references. That's just denial for the sake of theoretical simplicity.


Reading up on $BQP = BPP^{BQNC}$ What should I read to understand this problem?

  The power of small-depth quantum
  circuits. Is $BQP = BPP^{BQNC}$? In other
  words, can the "quantum" part of any
  quantum algorithm be compressed to
  polylog(n) depth, provided we're
  willing to do polynomial-time
  classical postprocessing? (This is
  known to be true for Shor's
  algorithm.) If so, building a
  general-purpose quantum computer would
  be much easier than is generally
  believed! Incidentally, it's not hard
  to give an oracle separation between
  $BQP$ and $BPP^{BQNC}$, but the question is
  whether there's any concrete function
  "instantiating" such an oracle. --Scott Aaronson
  http://www.scottaaronson.com/writings/qchallenge.html

This was conjectured by R. Jozsa in Section 8 of arXiv:quant-ph/0508124. If you are already familiar with quantum computing and quantum complexity theory, you can start by reading that section.

An important reading is arXiv:quant-ph/0006004, where Cleve and Watrous show that Shor's algorithm is in that class.


3-coloring graph zero-knowledge proof I was researching about zero-knowledge proofs and in this link http://web.mit.edu/~ezyang/Public/graph/svg.html I've seen the exercise question:

Currently, you can only select adjacent pairs of nodes to check. Would the proof still be zero knowledge if you could pick arbitrary pairs of nodes to check?

I think it would still be "zero knowledge" because it shouldn't leak information to verifier, but there won't be a proof if you select non-adjacent pairs since the reveal phase doesn't prove anything. Is this a trick question?

Yes, it would still be zero knowledge. However, it wouldn't be a proof of anything, since whether the colors matched or not, you still know nothing about whether the graph is actually 3-colored or not. It's not a trick question -- just a bad one.