texts:
One method for proving a protocol secure is through simulation-based models. This simulator uses ideal/real paradigm in which a protocol is secure in the real model if it is proven secure in an ideal model using a trusted third party (you can refer to the Canetti's UC framework to realize what is the power and use of this simulator, although use of this simulator dates back to 80s). This simulator is often given polynomial power to simulate the ideal world and if an external entity (observer) cannot distinguish between a real run and a simulated run with probability at most half plus negligible, we say that the protocol is secure or following UC terminology for realizing a functionality, the protocol securely realizes the functionality. It is good to mention that the simulator is also simulating the attacker, so the power of the simulator is essentially power of the attacker. There is often times that the simulator has superpolynomial power.

  Question: Does superpolynomial simulator has any advantage over a polynomial simulator? I need a good article on cons and pros of such a simulator.

A good article in which the author have used a polynomial simulator is Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions of Canetti.


texts:
Assuming that $P \ne NP$
how surprising would it be if a weaker form of $P = NP$ holds?

For example consider the following weaker forms of $P = NP$:

$NP \subseteq DTime(2^{O(n^\varepsilon)})$ for some $\varepsilon < 1$.
$NP \subseteq DTime(2^{cn})$ for some constant $c < 1$.
$NP \not\subseteq DTime(2^{O(n^\varepsilon)})$ for any $\varepsilon < 1$, but
there is an efficient algorithm
that solves all (or say 99% of) instances that come up in practice.
E.g. there is some efficiently computable set of inputs and
an efficient algorithm that solves the promise problem on that set.
The set contains all "real-world" instances of the problem.
$NP \not\subseteq DTime(2^{O(n^\epsilon)})$ for any $\epsilon < 1$, but
there is an efficient probabilistic algorithms
that is correct with probability $p$ (where $p < 1$).

5-8. 1-4 above with a quantum computer.

How surprising would any of these statements be to theoreticians
compared to $P = NP$?


texts: Explain Gurvits's tensor-rank interpretation of Deolalikar's paper

texts:
[Note: I believe this question in no way hinges on the correctness or incorrectness of Deolalikar's paper.]

On Scott Aaronson's blog Shtetl Optimized, in the discussion about Deolalikar's recent attempt on P vs NP, Leonid Gurvits made the following comment:

  I tried to understand/reformulate the approach, and here
  is my, perhaps very minimalist, attempt: the discrete probabilistic distributions in the paper can be viewed
  as tensors, or very special multilinear polynomials.
  The assumptions “P=NP” somehow gives a (polynomial?)
  upper bound on the tensor rank. And finally, using
  known probabilistic results, he gets nonmatching
  (exponential?) lower bound on the same rank. If I am right, then this approah is a very clever, in a good sense
  elementary, way to push the previous algebraic-geometric approaches.

Despite the suspected/known flaws in Deolalikar's proof, I'm curious:

  In what way can the distributions discussed in Deolalikar's paper be considered as tensors, and how do the statements of his results (regardless of their correctness) translate into statements about tensor-rank?


texts: Are there any known implementations for quantum computing constructs?

texts:
Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the Church-Turing thesis).

What are the most significant experiments that have been conducted to demonstrate quantum-computing theory (such as qubits and teleportation)?


texts: Linear Programing with Rounding for the Fire Station Problem

texts:
Consider the following fire  station problem: The input is a positive
integer k and a complete undirected graph $G = (V,E)$ with distances on the edges. The distances form a
metric: $d(v, v) = 0$, $d(u, v) = d(v, u) ≥ 0$, and $d(u, w) ≤ d(u, v) + d(v, w)$. The output is a subset $S\subset V$ with $|S| \leq k$ such that cost $\sum_{v\in V} \min _{u\in S} d(v,u)$ is minimized. Let $O^*$ be the optimal value of the cost, is it possible to construct a linear program with rounding that runs in polynomial time and approximately solve the problem such that the cost is no more than $(1+\epsilon) O^*$?


texts: Small kernel (i.e. proof-verifier) for Agda?

texts:
Proof-assistants usually include a lot of machinery that assists in the creation of proofs. The creation process may be unsound without risking the soundness of the proof-assistant if the alleged proof that was created is later verified by a sound proof-verifier. The smaller this verifier is, the less likely it is to be unsound due to coding or reasoning errors. The term small kernel was coined to refer to such a verifier in Barendregt and Geuvers (the idea apparently goes back to De Bruijn).

I have found literature mentioning this concept in relation to Coq and HOL Light (among others), but not to Agda, hence the question:

  How close is Agda to having a small kernel? How does it compare to other proof-assistants such as Coq and HOL Light?

Geuvers, H., Proof assistants: history, ideas and future, Sādhanā 34, No. 1, 3-25 (2009). ZBL1192.68629.

Barendregt, Henk; Geuvers, Herman, Proof-assistants using dependent type systems, Robinson, Alan (ed.) et al., Handbook of automated reasoning. In 2 vols. Amsterdam: North-Holland/ Elsevier; 0-444-50812-0 (vol. 2); 0-444-50813-9 (set)). 1149-1238 (2001). ZBL1005.03011.

Adams, Mark, Proof auditing formalised mathematics,  ZBL07106502.


texts:
I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented.

I'm new to the subject of "Derandomization," and as such, I wanted to know which reference to start from?

I prefer one that discusses literature and history, as well as the technical details.


texts: Max and Min Equations with Linear Programing

texts:
I am given constants $c_{i,j}$ as inputs.  I want to find values for the variables $x_i$ that satisfy a system of equations, where each equation either takes the form

$$x_i = \max\{x_j + c_{i,j} : j \ne i\}$$

or the form

$$x_i = \min\{x_j + c_{i,j} : j \ne i\}.$$

Is there an efficient algorithm to test this system of equations for feasibility, and if feasible, find a solution?  Can this be solved using linear programming somehow?


texts: What is computational complexity of calculating the Variance-Covariance Matrix?

texts:
I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector decomposition is causing the largest performance hit, I am wondering how much of that hit is caused by the Covariance Matrix computation.

The asymptotic running time I estimate it to use is $O(N\cdot n^2)$ using a naive algorithm, because it has to take the means of all the data of size $N$ and then has to do it for every dimension (where $n$ is the number of dimensions) in a nested iteration, and thus producing a $n^2$ size matrix.

Is my assumption correct, or if not what is the asymptotic complexity?


texts: Provable gaps between decision tree complexity and "true" complexity

texts:
The title is a little misleading: but hopefully the question isn't:

Grønlund and Pettie's new result showing that 3SUM has only $O(n^{3/2})$ decision tree complexity got me wondering:

  Is there a simple example of a problem with a decision tree complexity of $O(f)$ but that admits a lower bound (in a more detailed model) of $\omega(f)$ ?

In other words, how should the result on 3SUM change our view of the possibility of getting a significantly lower than $n^2$ upper bound on the complexity of the problem ?


texts: Decidability of membership in the fixed point of a rational relation

texts:
Given a finite alphabet $\Sigma$, a non-deterministic finite-state transducer representing rational a relation $T \subseteq \wp(\Sigma^* \times \Sigma^*)$, a finite state machine representing a regular language $L \subseteq \Sigma^*$, and a word $w \in \Sigma^*$. Let $T(L)$ denote the image of $T$ over $L$, i.e., $\left\{ w' \in \Sigma^* \mid \exists w \in L. (w,w') \in T\right\}$. Let $\mu$ and $\nu$ respectively represent the least and greatest fixed point operators.

Is it decidable whether $w \in \mu Z. L \cup T(Z)$?
Is it decidable whether $w \in \nu Z. L \cap T(Z)$?
If questions 1 or 2 are answered in the negative, does this change in the special case where $T$ is expressible as a finite union of deterministic transducers, i.e., $\mid T\left(\left\{w\right\}\right)\mid$ is finite for all $w$?
Are these results different when dealing with ranked trees rather than words, i.e., $\Sigma$ is a ranked alphabet, $L$ a tree-regular language, and $w$ a ranked tree over $\Sigma$?


texts:
Assume that we want to sort a list $S$ of $n$ real numbers.
Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly.
How much advantage can we gain using this black box?

For example, can we sort the numbers with only $O(\sqrt n)$ calls to the black box?
The best algorithm that I have found uses $n$ calls to the black box.
But I haven't been able to improve it further.
Here is my algorithm which is similar to merge-sort:

First partition the list $S$ into $\sqrt n$ lists $s_1, s_2, ..., s_{\sqrt n}$ with approximately $\sqrt n$ size.
Then use $\sqrt n$ calls to the black box to sort these lists.
Finally, merge the sorted lists using the black box as follows:

Put the smallest elements of the lists in a new list $L$,
then call the black box to sort it.
The number in $L[1]$ (first and smallest element of $L$) will be
the smallest number in $S$.
We can put it in the first place of the output list.
Assuming the element has been chosen from $s_j$,
we replace $L[1]$ with the second smallest element of sort list $s_j$,
and again run the black box on it to compute the second smallest member of $S$.
We continue till all the elements are sorted. The total number of black box calls for this part will be $n - \sqrt n$. Therefore overall the total number of calls will be $n$.

On the other hand, it looks like we should be able to obtain a lower-bound using the lower-bound on the number comparisons needed for sorting as follows:
We can implement the black box using $\sqrt n \lg \sqrt n = \frac{1}{2} \sqrt n \lg n$ comparisons.
If we can solve the problem with $o(\sqrt n)$ calls to the black box and merging in linear-time we can sort $n$ real numbers with $o(n \lg n)$ comparisons which is impossible.

I guess we could prove that $\Omega(n)$ is a lower-bound for the number of calls to the black box, since lots of comparisons using in the black box would be shared and therefore are recounted in our argument.

UPDATE: As the the other posts suggest, an $\sqrt n \lg n$ is also achievable.


texts: Best way to represent NP-Hardness result for decision problem with two decision parameters

texts:
What is the best way to represent a NP-Hardness result for a decision problem with two decision parameters? Suppose we have a problem $P$ which asks to minimize two parameters $x$ and $y$ and we show that given a constant $x$ deciding whether $y \leq k$ is NP-Hard and given a constant $y$, deciding whether $x \leq k$ is NP-Hard.

What is the best way of stating this result? $P$ is NP-Hard to solve? Or should the statement be more specific? Furthermore, for such two parameter decision problems, what should be proven if we want to obtain an NP-Hardness result? A result of the type I proved or a result that proves it is NP-Hard to decide if $x + y \leq k$ etc.


texts: Different definitions of grammar complexity

texts: It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L_0 \supseteq L$), production complexity (minimal possible $|P|$ for grammar $(N, \Sigma, P, S)$ generating $L$)... What are other kinds of grammar complexity studied in literature? How these complexities depend on each other?


texts: Time complexity for a variant of edit distance

texts:
This question is about the following variant of edit distance.  Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter x for a letter y only costs 1 the first time.  Any further substitutions of x for y cost 0.
As simple examples:
A = apppple
B = attttle

cost 1 (not 4) to transform A into B. This is because we change p for a t four times but we only charge for the first one.
A = apxpxple
B = atxyxtle

cost 2 (not 3) as the p to t substitution only costs 1 even though we do it twice.
A = apppple
B = altttte

cost 2. p -> l give allllle and then l -> t gives altttte.
If we assume the total length of the input is n, what is the best time complexity?
I suspect the problem is NP-hard so I am not expecting a poly time solution.
Question previously asked at https://codegolf.stackexchange.com/questions/215148/edit-distance-where-a-substitution-only-costs-the-first-time


texts: A dynamic data structure to list triangles

texts:
Consider an undirected graph with $n$ nodes.  Is there an efficient data structure that supports the following operations?

Insert an edge into the graph
Delete an edge from the graph
Given a query edge $(i,j)$, list all the triangles that include that edge. There can be $n$ of these in the worst case but ideally this operation would be sublinear if the number of triangles to be reported is.


texts:
I have a vague memory of a series of papers working to reduce the constant factor in the number of comparisons for deterministic linear time median finding, using increasingly elaborate (but interesting!) techniques to do so.

In particular, I remember one of the papers using the term "green forests" for a data structure storing information from previous comparisons (in an attempt to reuse them and avoid future comparisons).

Does this ring any bells?  "median finding green forests" turns out to be a terrible search term.


texts: converse relationship between the cut rule and the identity axiom

texts:
On page 30 of "Proofs and Types" by Girard, Taylor, and Lafont, it is claimed that that the identity axiom for sequent calculus:

C ├ C

has a converse relation with the cut rule:

$$\frac{\vec{A} \vdash C,\vec{B}  \qquad \vec{A'},C \vdash \vec{B'}}
      {\vec{A},\vec{A'} \vdash \vec{B},\vec{B'}}$$

The explanation it gives is that the in the identity axiom, C on the left is stronger than C on the right. With the cut rule, it claims, C on the right is stronger than C on the left. While the claim about the identity axiom seems to follow from basic notions of sequents, I do not understand the claim about the cut rule. Could someone explain this?


texts: Relationship between two graph optimization problems

texts:
Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph:

P1. Find a largest induced subgraph of the input graph with property $Q$, or detect if no such subgraph exists. (Largest = maximum number of vertices.)

P2. Partition the vertices of the input graph, such that the number of partition classes is minimum, and each class induces a subgraph with property $Q$, or detect if no such partition exists.

Several choices of $Q$ lead to classical problems, for example:

$Q(G)$="$G$ is an independent set." Then P1 is the max independent set problem, P2 is minimum coloring. Both are NP-hard.
$Q(G)$="$G$ is a clique." Then P1 is the max clique problem, P2 is minimum clique cover. Both are NP-hard.
$Q(G)$="$G$ is Hamiltonian." Then P1 looks for a largest circle, P2 looks for a minimum partition into Hamiltonian subgraphs. Both are NP-hard.
$Q(G)$="$G$ is connected." Then P1 looks for the largest connected component, while P2 looks for the number of connected components. Both are solvable in polynomial time.
$Q(G)$="$G$ has a perfect matching." Then P1 looks for a maximum matching, if the input graph has at least one edge, otherwise there is no subgraph with the property. The solution for P2 is the trivial partition with one class if the input graph has a perfect matching, or otherwise there is no feasible partition. Both cases are solvable in polynomial time.

Question: is there any (preferably natural) choice for the property $Q$, which makes one of the problems P1,P2 NP-hard, while the other is solvable in polynomial time?


texts: I'm interested in linear 2-state cellular automata (with local rules only) that could compute the majority function. Say the state of a cell is either 0 or 1. Is it possible to have a cellular automaton that sets all cells to 1 if the majority of initial states is 1 and sets all cells to 0 if the majority of initial states is 0? The cellular automaton could be synchronous or asynchronous. I tend to believe that the answer is negative (mainly because of rule locality). Any literature on this problem? I also believe that one could approximate it in the sense that one could devise a cellular automaton that fails only on a small fraction of its inputs (purely experimental at this point).


texts: Confusion about reduction counting vertex covers to counting cycle covers

texts:
This confuses me.

One easy case of counting is when the
decision problem is in $P$ and there are no solutions.

A lecture show that the problem of counting the number of perfect matchings in a bipartite graph (equivalently, counting the number of cycle covers in a directed graph) is $\#P$ -complete.

They give reduction from counting vertex covers of size $k$
to counting cycle covers in a digraph using gadgets.

Theorem 27.1 The number of good cycle covers in $H$ is $(k!)^2$ times the number of vertex covers of $G$ of size $k$.

Using gadget they leave only the "good" cycles.

My understanding of the lecture is that $G$ doesn't have
vertex cover of size $k$ iff the transformed digraph $G'$
doesn't have cycle cover. Checking if $G'$ has cycle cover
can be done in polynomial
time, implying $P=NP$ since we can transform the decision
problem to finding solution.

  What am I misunderstanding?

The permanent of the adjacency matrix of digraph
counts cycle covers and is $\#P$-complete.

The decision problem "Is the permanent of (0,1) matrix zero"
is in P since finding cycle cover is in $P$.

$P \ne NP$ implies there is no reduction of counting
$NP$-complete problems to counting $(0,1)$-permanent which maps $0 \mapsto 0$.

Edit Related MO question

Added

Markus Bläser points out that bad cycle are still "there",
but the sum of their weights vanishes.

Appears to me the weight of bad cycle in
a widget is zero.

From page 148 (11 of the pdf):

  The full adjacency matrix B with submatrices A corresponding to these
  four-node widgets counts 1 for each good cycle cover in H and 0 for each bad
  cycle cover

Another question:

  Wouldn't maximum weight cycle cover contain only the good cycles,
  corresponding to a $k$ vertex cover in the original graph?

In CC every vertex must be in exactly one cycle.


texts:
The origin of life problem is the wide-ranging inquiry into the mechanisms underpinning the emergence of life, where one definition of life is "a self-sustained chemical system capable of undergoing Darwinian evolution" [1].

In one model - the "RNA world" hypothesis [2] - a sea of self-replicating RNA molecules are the precursors to cellular organisms. The mechanism behind the emergence of RNA from the prebiotic chemicals found on earth's surface is an open problem. However, in a series of groundbreaking results, the Sutherland Group at the University of Manchester described a plausible mechanism that combines prebiotic feedstock molecules to yield 2 of the 4 nucleotide types (ribocytidine, ribouridine) found in RNA [3].

From a computational complexity perspective, what can be said in general about the difficulty of reverse-engineering the remaining nucleotides found in RNA? That is, the problem of determining if a desired organic molecule is "reachable" using basic chemical reactions from the set of less-complex molecules thought to be abundant on the earth's surface. Are there any phase transition conditions which would make it easier or harder to reverse engineer a molecule, similar to the phase transitions found in satisfiability problems [4]?

The problem is related to retrosynthetic analysis (for which Elias James Corey received the Nobel Prize in chemistry in 1990) and computer-assisted organic synthesis, however when considering the origins of life, we tend to think of a primitive environment where the available building blocks and plausible pathways leading to good yields are constrained compared to a modern wetlab.

Another approach is the metabolism first model, where cyclical chemical reactions based on small molecules evolve to develop increasingly complex structures.

The generalized, abstract problem of determining reachable outcomes given a set of starting materials and allowable reactions is undecidable when the number of steps is unconstrained and NP-hard when bounded [5]. This observation however does not say how difficult the organic chemistry we actually see in our world is.

In general, basic organic chemistry is not Turing-complete because termination is decidable [6]. However, stochastic chemistry [7] can approximate Turing machines to arbitrary precision [8]. Arbitrary protein structure prediction (protein folding) is known to be NP-complete [9].

There are some machine learning methods for assessing whether or not a particular target compound or drug is likely to be synthesizable [10]. Does this approach say anything about RNA/DNA?

The problem of RNA formation may be completely tractable even if the more general problem of organic synthesis is intractable. This would mirror the situation in physics. Deducing the dynamical equations governing an arbitrary physical system is NP-hard [11], however the physics we encounter in our world is much easier to analyze and appears to be tractable (what has also been called "the unreasonable effectiveness of mathematics in the natural sciences" [12]).

[1] http://originlife.org/
[2] http://en.wikipedia.org/wiki/RNA_world_hypothesis
[3] http://www.nature.com/nature/journal/v459/n7244/full/nature08013.html
[4] http://www.cs.ubc.ca/~kevinlb/papers/2012-PredictingSatisfiability.pdf
[5] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9276&rep=rep1&type=pdf
[6] http://dna.caltech.edu/Papers/sCRN_computation_2008.pdf
[7] http://demonstrations.wolfram.com/DeterministicVersusStochasticChemicalKinetics/
[8] http://lucacardelli.name/Talks/2009-05-08%20Biochemistry%20%28Warsaw%29.pdf
[9] http://www.bentribelhorn.com/files/cs524.pdf
[10] http://www.dtc.umn.edu/publications/reports/2010_02.pdf
[11] http://arxiv.org/pdf/1005.0005.pdf
[12] http://www.dartmouth.edu/~matc/MathDrama/reading/Wigner.html


texts: What is the largest complexity class that a non-Turing complete proof assitant, like Coq, can achieve?

texts: Given that all functions in Coq will terminate, it cannot cover the entire $RE$. So what is the class it can achieve? Is it $R$?


texts:
A deterministic automaton $\mathcal A = (X, Q, q_0, F, \delta)$ is called $k$-local  for $k > 0$ if for every $w \in X^k$ the set $\{ \delta(q,w) : q \in Q \}$ contains at most one element. Intuitively that means if a word $w$ of length $k$ leads to a state, then this state is unique, or said differently from an arbitrary word of length $> k$ the last $k$ symbols determine the state it leads to.

Now if an automaton is $k$-local, then it need not be $k'$-local for some $k' < k$, but it has to be $k'$-local for $k' > k$ cause the last symbols of some word $|w| > k$ determine the state, if any, uniquely.

Now I try to connect the number of states and the $k$-localness of an automaton. I conjecture:

  Lemma: Let $\mathcal A = (X,Q,q_0,F,\delta)$ be $k$-local, if $|Q| < k$ then the automaton is also $|Q|$-local.

But I failed to proof, any suggestions or ideas?

I hope by this Lemma to derive something about the number of states of an automaton which is not $k$-local for all $k \le N$ given a fixed $N > 0$, but $k$-local for some $k > N$.


texts: For which problems in P is it easier to verify the result than to find it?

texts:
For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) exponential time.

In P, however, the solution can also be found in polynomial time, so it does not seem obvious when is the verification  faster than finding the solution.  In fact, different problems seem to behave differently from this point of view. Some examples:

3SUM: given $n$ input numbers, find 3 among them that sum to 0. As far as I know, the fastest known algorithm runs in  $O(n^{2-o(1)})$ time, and this order is conjectured optimal. On the other hand, the verification of a solution is much faster, since all we need to do is just to check that the 3 found numbers indeed sum to 0.
All-Pairs Shortest Paths:  given a graph with edge weights, compute its shortest path distance matrix. Once such a matrix is given, can it  be checked faster that it is indeed the correct distance matrix, than re-computing it? My guess is that the answer is perhaps yes, but it is certainly less obvious than for 3SUM.
Linear Programming. If a claimed optimal solution is given, checking it is  easier than re-computing it, when auxiliary information is also given (an optimal dual solution). On the other hand, if only the primal solution is available, it is not clear if one can check it faster, than actually solving the LP.

Question: what is known about this subject? That is, when is it easier to verify a solution for a problem in P, than finding the solution?


texts: Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

texts:
Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice that there is no $O(\cdot)$ around $f(n) + 1$.

Is it true that $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

Using the linear speed-up theorem, we can prove $\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$, but can we reach $n$?

It seems that the language of palindromes is in $\mathsf{DTIME}(n)$; for related topics, see Lipton's blog post about string algorithms


texts: Completeness of Constraint Typing (type inference) question regarding $\sigma'$

texts:
The theorem of completeness of type inference states the following:

Suppose $\Gamma \vdash t:S| _{\mathcal{X}}C$,

In other words, I have some term "t"
whose type is "S" under the assumptions in Gamma,
assuming the constraints "C" is met.
The "x" denotes that we assign the typed variable "x" to this inference.

And sigma is a mapping of type variables to types.

If:

$\sigma(\Gamma)\vdash \sigma(t) : T$, and

When assume a mapping that Gamma has some t whose type is "T".  When we apply
sigma to that Gamma, our assumptions are still valid

$dom(\sigma)\cap\mathcal{X} = \emptyset$

We want the domain of the type mappings to be disjoint from our type variables.

then there is some solution:

$(\sigma', T)= T$ and

The tuple (sigma', T) is equivalent to T

$\sigma'\backslash\mathcal{X}=\sigma$

sigma' set minus type variables will be equal to sigma

What I don't fully understand (and the Pierce book is so very opaque) is why the need for the $\sigma'$ to prove that the program is typeable. What exactly is happening in that transition from $\sigma \rightarrow \sigma'$.

Or am I being as dense as I think, and this theorem is able to simultaneously look at the step rules I have defined for my language and resolve the term to a concrete value.  And Completeness implicitly uses those rules, thus the need for $\sigma'$


texts: Graph planarity testing via adjacency matrix

texts:
I have looked at several efficient graph planarity algorithms which
rely on computing and traversing DFS trees
(that add one vertex/edge/path at a time).

I am looking for graph planarity algorithms based on
the adjacency matrix and operations on it, e.g.
taking the square of the matrix,
computing the eigenvalues of the matrix, etc.


texts: What is the complexity of this path problem?

texts:
Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 2$.

Question: Does there exist an $s-t$ path in $G$, such that the path touches at most $k$ vertices? (A vertex is touched by the path if the vertex  is either on the path, or has a neighbor on the path.)


texts: Suffix tree and searching for longest subword that appears two times and two occurencies are not overlapping

texts:
I'm learning basics of text algorithms, so my question might seem simple.

Let's have word $S$, i want to find longest subword $x$ such that it appears in $S$ two times and those two occurencies are not overlapping.

For example $S=ababab$ and the solution will be $ab$, because any longer subword: $aba$ or $bab$ (or longer) are overlapping.

I came up with one solution: it's using suffix arrays, from that i can calculate LCP (longest common prefix) table and LPF(longest previous factor) table and task is almost done.

Next i tried to solve this task with suffix tree (preferably compressed suffix tree, because uncompressed is almost not used), but i don't really know how to do it.
I'd love to hear some solutions from you. Cheers


texts: $\epsilon$-nets with respect to the cut norm

texts:
The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\right|$.

Define the distance between two matrices $A$ and $B$ to be $d_C(A,B) = ||A-B||_C$

  What is the cardinality of the smallest $\epsilon$-net of the metric space $([0,1]^{n\times n}, d_C)$?

i.e. the size of the smallest subset $S \subset [0,1]^{n\times n}$ such that for all $A \in [0,1]^{n\times n}$, there exists an $A' \in S$ such that $d_C(A, A') \leq \epsilon$.

(EDIT: I forgot to mention, but I am also interested in "non-proper" $\epsilon$-nets, with $S \subset \mathcal{R}_+^{n\times n}$ -- i.e. if the elements of the $\epsilon$-net have entries outside of [0,1], that is also interesting.)

I am interested in both upper bounds and lower bounds.

Note that cut sparsifier techniques imply $\epsilon$-nets for cut metrics, but give something stronger than I need -- they give an $\epsilon$-net for which you can efficiently find an $\epsilon$-close point to any matrix simply by sampling from that matrix. One might imagine that there exist much smaller $\epsilon$-nets for which you cannot simply sample do find an $\epsilon$-close point to an arbitrary matrix.

I initially asked this question here on mathoverflow.


texts: Classes of graphs with superconstant treewidth

texts:
There are several interesting classes of graphs with bounded treewidth. For instance, trees (treewidth 1), series parallel graphs (treewidth 2), outerplanar graphs (treewidth 2), $k$-outerplanar graphs (treewidth O(k)), graphs of branchwidth $k$ (treewidth O(k)),...

Question: Are there examples of interesting classes of graphs whose treewidth is not bounded by a constant, but by a low-growing function?

Are there well known graph classes with treewidth $O(\log\log n)$?
Are there well known graph classes with treewidth $O(\log n)$?

I would also be interested in classes of graphs with treewidth
$O(\log^k n)$ or $O(\log\log...n)$ where the logarithm is repeated a constant number of times.

Obs: Of course it is easy to cook up artificial families of graphs with a given treewidth, like the family of $\;O(\log n)\times n\;$ grids. So I'm primarily looking for family of graphs which have been studied in other branches of graph theory and which happen to have treewidth $O(\log n)$ or $O(\log\log n)$, but non-constant treewidth.


texts: Is the wording of Google's QC Supremacy valid?

texts:
Quantum supremacy using a programmable superconducting processor was published today. Scott Aaronson posted a few weeks ago a post about this paper and it was clear we will see a Nature or Science paper soon.

The abstract’s wording is less extravagant:

  This dramatic increase in speed compared to all known classical
  algorithms is an experimental realization of quantum
  supremacy for this specific computational task...

Isn't supremacy a well-defined concept in complexity theory?
Wouldn't Shor's algorithm be considered a QC supremacy?
How can we define supermacy unless it's provable that there is no classical algorithm to solve the problem faster on "traditional" supercomputer besides brute force?

Note: this is an amazing paper and I am seriously asking to understand if the wording of the paper is acceptable by the QC community.

Related: IBM’s response.


texts: Can neural networks be used to devise algorithms?

texts:
After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I wondered whether

  Can neural networks be trained to solve classic algorithmic problems?

Here I mean that for example the network would get an input graph $G$ with weighted edges, and two vertices $s$ and $t$ specified, and we asked it to find a shortest $st$ path as fast as possible.
Then I guess the neural network would discover and train itself to use Dijkstra or something similar.

On one hand, we know that the computational power of neural networks is $TC^0$.
On the other, I don't know if this is necessarily related to my question.
Even so, for most problems we don't know whether they can be solved in $TC^0$ or not.
Seeing whether a neural network can train itself, might be a good indicator whether there's a fast algorithm or not.
For example, if neural networks can't train themselves to solve SAT fast, then that makes it (even more) likely that $NP\not\subset TC^0$.
I wonder what a neural network would do with GRAPHISOMORPHISM or FACTORIZATION.

Of course, extracting the algorithm is a whole different question.
I suspect experts know how to do that, but discussing it is not the topic of this question.

Added two days later: After seeing the answers, let me specify that if you answer in the negative, then I would like to know

  Why is playing chess easier than Dijkstra or Graphisomorphism?


texts: Context-free Grammar for a Context-free Language Intersecting a Regular Language (get the Maximum Number of Rules)

texts:
It is well known that the intersection of $L \cap R$ of a context-free Language $L$ and a regular Language $R$ is context-free. Each proof I have seen constructs a automaton (a PDA) that accepts $L$ and one (a DFA) that accepts $R$. Than a further automaton (a PDA) is constructed that accepts $L \cap R$. This automaton can be converted to a context-free language.

Is there some literature that gives a proof without constructing automatons and constructs a context-free grammar that generates $L \cap R$ directly?

What I want to know actually: Given a context-free Language $L$ and a regular Language $R$. How many rules at most does a context-free grammar need to generate $L \cap R$?


texts: Reference Request: Submodular Minimization and Monotone Boolean Functions

texts:
Background: In machine learning, we often work with graphical models to represent high dimensional probability density functions.  If we discard the constraint that a density integrates (sums) to 1, we get an unnormalized graph-structured energy function.

Suppose we have such an energy function, $E$, defined on a graph $G = (\mathcal{V}, \mathcal{E})$.  There is one variable $x$ for each vertex of the graph, and there are real-valued unary and pairwise functions, $\theta_i(x_i) : i \in \mathcal{V}$ and $\theta_{ij}(x_i, x_j) : ij \in \mathcal{E}$, respectively.  The full energy is then

$$E(\mathbf{x}) = \sum_{i \in \mathcal{V}} \theta_i(x_i) + \sum_{ij \in \mathcal{E}} \theta_{ij}(x_i, x_j)$$

If all $x \in \mathbf{x}$ are binary, we can think of an $x$ as indicating set membership and with just a small abuse of terminology talk about submodularity.  In this case, an energy function is submodular iff $\theta_{ij}(0, 0) + \theta_{ij}(1, 1) \le \theta_{ij}(0, 1) + \theta_{ij}(1, 0)$.  We are typically interested in finding the configuration that minimizes the energy, $\mathbf{x}^* = \arg \min_{\mathbf{x}} E(\mathbf{x})$.

There seems to be a connection between minimizing a submodular energy function and monotone boolean functions: if we lower the energy of some $\theta_i(x_i=1)$ for any $x_i$ (i.e., increase its preference to be "true"), then the optimal assignment of any variable $x_i^* \in \mathbf{x}^*$ can only change from 0 to 1 ("false" to "true").  If all $\theta_i$ are restricted to be either 0 or 1, then we have $|\mathcal{V}|$ monotone boolean functions:

$$f_i(\mathbf{\theta}) = x_i^*$$

where as above, $\mathbf{x^*} = \arg \min_{\mathbf{x}} E(\mathbf{x})$.

Question: Can we represent all monotone boolean functions using this setup by varying the pairwise terms, $\theta_{ij}$?  What if we allow $E$ to be an arbitrary submodular energy function?  Conversely, can we represent all submodular minimization problems as a set of $|\mathcal{V}|$ monotone boolean functions?

Can you suggest references that will help me towards better understanding these connections?  I'm not a theoretical computer scientist, but I'm trying to understand if there are insights about monotone boolean functions that are not captured by thinking in the submodular minimization terms.


texts: Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

texts:
In their paper (p. 503) Garey and Johnson remark:

  ... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ...

Does anyone know some candidate problems with the properties the mentioned above?

I think the possible answer to this question can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.


texts: Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm

texts:
EDIT: I'm sorry if this question belongs more to cs.SE, I've had a dilemma about where to put it. Please let me know if it's inappropriate.

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

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

The general idea is as follows:

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

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

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

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

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

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

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

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

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

Is that a correct assumption?

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

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

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


texts: Examples of hard instances for Goemans and Williamson algorithm

texts:
I'm interested in the explicit examples of graphs for which application of Goemans and Williamson algorithm for approximating maximum cuts results in 0.878…-approximation factor.

The algorithm to create such instances would be perfect, explicit examples and references are satisfactory.


texts: $NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?

texts:
Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$.

Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, what is the smallest (known) $\mathscr{C}_d$ ?

My thoughts:

I know $\mathscr{C}_3$ consists only of graphs isomorphic to $K_4$, by an Euler's formula argument. So necessarily $d > 4$.

$\mathscr{C}_4$ is already infinite, and the number of isomorphism types of size $\leq k$ grow exponentially fast: once you have a triangle, you can subdivide two of its edges and connect them with an edge. You can also subdivide four sided faces by connecting opposite edges with a new edge. You can then subdivide a triangle into an m level pyramid, and subdivide the levels with vertical lines, which gives $2^m$ choices based on the next subdivision point being 'right' or 'left' of the previous one. So $\mathscr{C}_4$ is (to me) a plausible candidate.

I know the following two closely related theorems:

1) Hamiltonian cycle is NP-complete on the class of cubic, 3-connected simple plane graphs ( $\mathscr{C}_{\infty}$ in my notation): http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf

In addition, they show that they can force the girth to be at least 5. This is opposite from the spirit of my question.

2) Hamiltonian cycle is NP-complete on the class of 3-connected plane graphs with face degree $3$ (i.e. maximal plane graphs): http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf


texts:
I have seen a bunch of results concerning Matrix Completion, PCA, Compressed Sensing where a common theme has been to relax the Rank constraint/objective by replacing it with Nuclear Norm. I was wondering if there is a survey of some sort which collects these results, compares them and presents the basic underlying technique. I havent read the original papers yet so they might be the best reference but the purpose of the question is to know if there are other easier to understand references to get started on this topic with.

Thanks in advance


texts: NP-intermediate problems with efficient quantum solutions

texts:
Peter Shor showed that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) only yields a quadratic improvement over the classical algorithm, hinting that NP-complete problems are still intractable on quantum computers. As Arora and Barak point out, there's also a problem in BQP that is not known to be in NP, leading to the conjecture that the two classes are incomparable.

Is there any knowledge/conjecture as to why these NP-intermediate problems are in BQP, but why SAT (as far as we know) isn't? Do other NP-intermediate problems follow this trend? In particular, is graph isomorphism in BQP? (this one doesn't google well).


texts:
We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v_1,\ldots,v_n$, the cost of the ordering is $\sum_{i=1}^n c(v_i,i)$.

Is finding the minimum cost topological ordering NP-hard?


texts: Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

texts:
This one's hard, so all help really appreciated!

I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it reduces to, similar problems it reminds you of, etc.

The story goes as follows. I own an ice cream truck business with n trucks. There are m stops where I make deliveries. Each location $m_i$ has $p_i$ people waiting for me. After buying their ice cream, everyone leaves (so $p_i$ reduce to zero). $p_i$ increases over time as more people line up to wait for the ice cream trucks. Also, all the truck drivers get commission, so they are competing against each other. All trucks have to be either at a location or moving to the next at any given time.

How can I figure out where to send the trucks next in order to maximize my profit on any given day?

Things to keep in mind:

Two trucks that stop in the same spot at similar times will only get
the profit once, i.e. the people leave after one truck arrives
The trucks take time to get from one location to another
$p_i$ increases over time at each stop, but some stops increase faster
than others, i.e. some locations are near malls (location, location,
location)

I've tried reducing this to a multi-machine scheduling problem, travelling sales person problem, ILP etc., but the main issue is that the $p_i$ at every location (i.e. the distance in the TSP or the job length in the scheduling problem) is constantly changing.

Thanks in advance!


texts: Computational consequences of Friedman's (unprovable) Upper Shift Fixed Point theorem?

texts:
Harvey Friedman showed that there is a neat fixed point result that cannot be proved in ZFC (the usual Zermelo-Frankel set theory with the Axiom of Choice).  Many modern logics are built on fixed point operators, so I was wondering: are there any consequences known of the Upper Shift Fixed Point theorem for theoretical computer science?

  Unprovable Upper Shift Fixed Point Theorem
  For all $R \in \text{SDOI}(Q^k,Q^k)$, some $A = \text{cube}(A,0) \setminus R[A]$ contains $\text{us}(A)$.

The USFP Theorem seems to be a $\Pi^1_1$ statement, so it might be "close enough" to computability (such as checking non-isomorphism of automatic structures), to impact theoretical computer science.

For completeness, here are the definitions from Friedman's MIT talk from November 2009 (see also the draft book on "Boolean Relation Theory").

$Q$ is the set of rational numbers.  $x, y \in Q^k$ are order equivalent if whenever $1 \le i,j \le k$ then $x_i \lt x_j \Leftrightarrow y_i \lt y_j$.  When $x \in Q^k$ then the upper shift of $x$, denoted $\text{us}(x)$, is obtained by adding 1 to every non-negative coordinate of $x$.  A relation $A \subseteq Q^k$ is order invariant if for every order invariant equivalent $x,y \in Q^k$ it holds that $x \in A \Leftrightarrow y \in A$.  A relation $R \subseteq Q^k \times Q^k$ is order invariant if $R$ is order invariant as a subset of $Q^{2k}$, and is strictly dominating if for all $x,y \in Q^k$ whenever $R(x,y)$ then $\max(x) \lt \max(y)$.  Further if $A$ is a subset of $Q^k$ then $R[A]$ denotes $\{ y | \exists x \in A R(x,y)\}$, the upper shift of $A$ is $\text{us}(A) = \{\text{us}(x) | x \in A\}$, and $\text{cube}(A,0)$ denotes the least $B^k$ such that $0 \in B$ and $A$ is contained in $B^k$.  Let $\text{SDOI}(Q^k,Q^k)$ denote the set of all strictly dominating order invariant relations $R \subseteq Q^k \times Q^k$.

Edit: As Dömötör Pálvölgyi points out in comments, taking $k=1$ and $R$ to be the usual ordering on rationals seems to yield a counterexample.  First, the set $A$ cannot be empty, as $R[A]$ is then also empty and $A$ would then have to contain 0 by the cube condition, a contradiction.  If the non-empty set $A$ has an infimum then it cannot contain any rationals greater than this, so it must be a singleton, which contradicts the upper shift condition.  If on the other hand $A$ has no infimum then $R[A] = Q$ so $A$ must be empty, a contradiction.  Any comments on whether there are any hidden non-obvious definitional problems, such as perhaps an implicit nonstandard model of the rationals?

Further edit: The argument above is roughly correct, but is wrong in the application of the upper shift.  This operator only applies to non-negative coordinates, so setting $A$ to be any negative singleton set yields a fixed point, as desired.  In other words, if $m < 0$ then $A = \{m\}$ is a solution, and there are no other solutions.


texts: Consequences of nondeterminism speeding up deterministic computation

texts:
If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e.

  for some function $t \in n^{\omega(1)}$, $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$,

then if follows from the deterministic time hierarchy theorem that
$\mathsf{P} \subsetneq \mathsf{NP}$.

But are there any other interesting consequences nontrivial
(i.e. not a consequence of $\mathsf{P} \subsetneq \mathsf{NP}$)
if nondeterminism can speed up deterministic computations?


texts: Is there a FNP problem that's NP-hard but not FNP-hard?

texts:
For the reductions, choose a class C such that [it's clear what FC means]

and FC is not known to be able to solve the satisfaction search problem,

and assume that FC indeed can't solve that search problem.

With the following definitions of hardness for FNP problems R,

NP-hard   -   The corresponding decision problem is NP-hard (with respect to C reductions).

FNP-hard   -   There is a C reduction f from satisfiability to the corresponding decision problem

and a function g in FC such that for all instances x of the satisfiability problem,

for all strings y, if  f(x) R y  then g(x,y) is a satisfying assignment to x.

is there a FNP problem that's NP-hard but not FNP-hard?


texts: Existence of equilibria in infinite two players zero sum extensive form games with perfect information

texts: I am looking for a study that has examined whether and under which conditions (if any), an infinite and of possibly infinite horizon two person zero sum extensive form game with perfect information and finite discrete action space, has a value. I would appreciate very much any tips.


texts: Scope of active substitutions in the applied $\pi$-calculus

texts:
As I have seen a few questions on calculi floating around, I figure this is the right place to ask. Suppose we have an extended process $P \equiv \nu \tilde{n}.\left( \{M/x\} \mid N \right)$ where $\{M/x\}$ denotes an active substitutions and $M$ and $N$ are some terms.

The question i ask myself is, whether we generally substitute $x$ for $M$ in $N$ if $x \in N$, or whether it depends on if $x \in \tilde{n}$ such that it is bound by $\nu \tilde{n}$. In other words, are processes computing in parallel in scope of active substitutions, and if yes, on what conditions?

Despite skimming through several papers, i did not manage to get a clear cut answer.


texts:
This paper on locally-nameless (Charguéraud, Arthur: The locally nameless representation, Journal of Automated Reasoning (2012): 1-46) describes how to perform beta-reduction by "opening", but it's unclear to me how to normalize under abstractions.
For example how would one normalize the following expression, with the locally-nameless operations:

$\lambda((\lambda\lambda(1 \; 0)) \; 0)$


texts: Extending cographs with product operation

texts:
Let $\mathcal{C}$ be the class of undirected graphs defined inductively as follows:

A single vertex is in $\mathcal{C}$;
If $G\in\mathcal{C}$ then its complement $\overline{G}$ is in $\mathcal{C}$;
If $G,H\in\mathcal{C}$ then their disjoint union $G\oplus H$ is in $\mathcal{C}$;
If $G,H\in\mathcal{C}$ then their tensor product $G\otimes H$ is in $\mathcal{C}$.

This class of graphs appears in linear logic: this is how coherent spaces are defined.
I would like to now if this class have been studied from the point of view of graph theory. Does it have a name? Does it admit other characterizations?
If we restrict the definition to the first three lines we get cographs. But when we add the product operation we can create the 4-nodes path $P_4$, clique-width is then $>2$. But is the clique-width bounded for the whole class?
Thank you in advance for your help.
Update after daniello's answer
It was not clear for me how to generate paths of arbitrary lengths. This can be done by induction as follows, where the induction hypothesis is:
"$\forall n$, there is a graph $G_n$ of $\mathcal{C}$ containing $P_n$ as an induced subgraph"

The paths $P_2$ and $P_3$ are clearly in $\mathcal{C}$. Take $G_2$ and $G_3$ to be respectively $P_2$ and $P_3$.

For $n\geq 4$, we define $G_n$ as the tensor product of $G_{n-1}$ (obtained by IH) with the graph $H_n$ whose set of vertices is $[1,n]$ and which contains an edge between every pair of vertices except between $n$ and $n-3$. The graph $H_n$ is clearly a cograph thus belongs to $\mathcal{C}$. It is not very hard to see that $G_{n-1}\otimes H_n$ contains $P_n$ as an induced subgraph.


texts:
In the classic setting, an automaton for a language $L$ is required to accept all words in $L$ and reject/get stuck on every word in $\Sigma^*\setminus L$.

All of the related concepts are then defined with respect to $\Sigma^*$ as the possible inputs (e.g. $L$'s regularity/CF/state complexity/ etc.).

But we can think of a model where the possible input is some set $I\subseteq \Sigma^*$, and consider $L$'s attributes with respect to $I$.

Formally, an automaton for a language $L$ with respect to possible input set $I$ is required to:

Accept every word $w\in I\cap L$.
Reject every word in $I\setminus L$.

(i.e. its action on $\Sigma^*\setminus I$ could be arbitrary).

If such automaton exists, we say that $L$ is regular with respect to $I$.

  If this model is known, can anyone provide a reference?

An immediate result that if $I$ is finite, every language (including, say, the Halting Problem) becomes regular w.r.t. $I$.

  How can we characterize the requirements from $L$,$I$ such that $L$ is regular with respect to $I$?

Note that this is not the same as $L\cap I$ being regular (e.g. $I\subseteq L$ for some non-regular language $I$).


texts: Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related?

texts:
This is a crosspost of mathoverflow/345282

I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy:
$$\inf_{x\in\mathbb{R}^n}\quad p(x)$$
where $p$ is a polynomial of even degree degree, $d=2\ell$.

The approach of Lasserre, which relies on Putinar's Nullstellensatz, requires to restrict to an archimedean domain, which can be done by adding the constraint $\|x\|^2\leq a$ for a sufficiently large $a$. This approach is described e.g. in Theorem 5.5. of this lecture, and yields the hierarchy:

$$
\begin{align}\tag{$P_r$}
\sup &\quad \lambda\\
s.t. &\quad p(x)-\lambda = q(x) + \sigma(x) (a-\sum_i x_i^2)\\
     &\quad \text{for some SOS polynomials $p$,$\sigma$}\\
     &\quad \text{of degree at most $2(\ell+r)$ and $2(\ell+r-1)$, respectively.}
\end{align}
$$

The approach of Reznick, which is described e.g. in this lecture, and consists in expressing $p(x)-p^*$ as a rational function (the ratio between a SOS polynomial and $(1+\|x\|^2)^r$ for increasing values of $r$):

$$
\begin{align}\tag{$Q_r$}
\sup &\quad \lambda\\
s.t. &\quad (1+\sum_i x_i^2)^r \ (p(x)-\lambda) = q(x)\\
     &\quad \text{for some SOS polynomials $p$ of degree $2(\ell+r).$}
\end{align}
$$

So my question is: Are these two approaches related / equivalent?  Is it known if one approach converges faster than the other one?


texts: Reference request on dynamic flows combined with network coding

texts:
I have read some papers about network coding and dynamic flows (flows over time).

I think I have made comprehensive searches on google, google scholar and IEEE Xplore.
IMHO, the reasons for the difficulty in finding such references are that this topic is new and that there are not many people doing research on this topic.

As Kaveh's comment below, I am going to explain the problem with more detail.
The original network coding theory addresses the maximum flow problem under the circumstances that every node in the network can combine the information it receives, which is the counterpart of the maximum flow problem in the network with coding ability.

The quickest flow (flows over time) addresses the problem how soon a/some commodity/commodities can be transship to some certain nodes, and this model is applicable in, for example, evacuation. Some reference for the flows over time are Quickest flows over time and Multicommodity flows over time.

The problem I am interested in is how to combine the coding ability, as in the network coding theory, to the quickest flow model. Once the network has coding ability, there maybe some promotion in the counterpart of the quickest flow.

Thanks in advance!


texts: Complexity status of the Edge Deletion problem to bounded degree graphs

texts:
I'm interested in the complexity status of the following problem.

Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$.

Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality at most $k$ such that the maximum degree of $G-E' = (V,E \setminus E')$ is at most $d$. No, otherwise.


texts: Is Kolmogorov complexity quasi-surjective?

texts:
For Kolmogorov complexities $\hspace{.02 in}K$ induced by essentially-optimal description languages,

does there exist an integer $c$ such that for all positive integers $n$,

there exists a string $x$ such that $\;\;\; n \: < \: K(x) \: < \: n\hspace{-0.04 in}+\hspace{-0.03 in}c \;\;\;\;$?

Unlike the question I was inspired by, this question's answer is robust against the choice of $\hspace{.02 in}K\hspace{-0.02 in}$, since by definition $L_{\hspace{.03 in}0}$ is an "essentially-optimal description language" if and only if

it is a computable partial function from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*}$ to itself such that for all

computable partial functions $L_{\hspace{.02 in}1}$ from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*}$ to itself, there exists an

integer $c$ and a computable (total) function $\: f : \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*} \to \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*} \:$ such that

for all strings $x$, $\;\;\; \operatorname{length}(\hspace{.05 in}f(x)) \: < \: \operatorname{length}(x)+c \;\;\;$ and $\; L_{\hspace{.03 in}0}\hspace{-0.02 in}(\hspace{.05 in}f(x)) = L_{\hspace{.02 in}1}\hspace{-0.02 in}(x) \:\:$.


texts: Natural Transformations and Parametricity

texts:
In Theorems for Free!, Wadler says that the characterization of parametricity can be re-expressed in terms of lax natural transformations and this will be the subject of a further paper. Which paper is he referring to?

The categorical approach to paramtericty I know uses dinatural transformations as in Functorial Polymorphism by Bainbridge, Freyd, Scedrov and P.J. Scott. What is the connection between lax natural transformation and dinatural transformation formulations of parametricity?


texts: Counting the maximum number of paths of length $n$ that differ in at least $k$ edges

texts:
What is known about the complexity of solving (or approximately solving) the following problem?

INPUT: Graph $G=(V,E)$ and constants $L$ and $K$.

OUTPUT: The maximum size of any set $S$ of simple paths of length $L$ such that every two paths in $S$ differ in at least $K$ edges. I care about the case when $L$ and $K$ are small constants


texts: Alan Turing's Contributions to Computer Science

texts:
Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, undecidability, and the Turing test.  However, his important discoveries are not limited to the ones I listed.

In honor of his 100th Birthday, I thought it would be nice to ask for a more complete list of his important contributions to computer science, in order to have a better appreciation of his work.

So, what are Alan Turing's important/influential contributions to computer science?


texts: Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem.

texts:
Last semester, I took a combinatorial optimization course where the reference book was Combinatorial Optimization by William J. Cook et al. It was very interesting for me to see the relationship between some great algorithms (like disjktra's shortest path algorithm, edmonds' maximum matching algorithm ...) and LP duality.

My question is about a general framework on constructing combinatorial algorithms based on LP duality.

For a given problem what are the necessary and sufficient conditions for the existence of such algorithms. I think duality gap should be the first necessary condition and to have a totally unimodal matrix could be sufficient.

Maybe the answer is written in that book and I should read it again carefully.


texts: Quadratic relationship between nondeterministic and deterministic space?

texts:
Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades.

Suppose we approach the problem from the other end.
For simplicity, assume the Boolean alphabet.
The amount of space used by a TM to decide a computable language is often closely related to the logarithm of the number of states used by the automaton simulating the TM for each regular slice of a language.
This motivates the following question.

Let $D_n$ be the number of syntactically distinct DFAs with $n$ states, and let $N_n$ be the number of distinct NFAs with $n$ states.
It is straightforward to show that $\lg N_n$ is close to $(\lg D_n)^2$.

Further, let $D_n'$ be the number of distinct regular languages that can be recognised by a DFA with $n$ states, and let $N_n'$ be the number recognised by an NFA.

  Is it known whether $\lg N_n'$ is close to $(\lg D_n')^2$?

It is not clear to me how $D_n$ and $D_n'$, or $N_n$ and $N_n'$, are related to each other, or how closely.
If all this relates to a well known question in automata theory then a hint or pointer would be appreciated.
The same question is also relevant for two-way automata, due to the same reasoning, and I am especially interested in this version.


texts:
Is there something known about the class of graphs with the property that all maximal independent sets have the same cardinality and are therefore maximum ISs?

For example, take a set of points in the plane and consider the graph of intersections among all segments between pairs of points in the set. (segments->vertices, intersections->edges). This graph will have the above property, as all maximal ISs correspond to triangulations of the original point set. Are there other categories of graphs known to have this property? Can this property be easily tested?


texts: What are the limitations on formal proofs of Erlang systems?

texts:
Well, today I just got my 15 minutes of fame, but now I think I am wrong on the point about formal proofs on Erlang systems.  The discussion on news.ycombinator.com suggests that Erlang code may or may not lend itself so well to formal reasoning (and it's certainly not pure a pure functional language), although a bit of google-fu turns up a fair number of peer reviewed articles on formal proofs on Erlang systems.

I'd like to get this right.  Can somebody here give a decent, in-depth explanation of the ins and outs of formal proofs on Erlang systems?


texts: What is the shortest description of a universal computational structure that includes a meta-circular evaluator?

texts:
I am wondering whether there is a minimal (or the shortest known) way of specifying a universal computational structure that includes a specification of a meta-circular evaluator within that structure. What are theoretical hurdles we might encounter? Is there something along these lines in the literature?

Update to elaborate a bit what I have in mind: A 1D-cellular automaton implementing the rule 110 has a very short description, but this structure is not immediately homoiconic, in fact it would require a lot of bits to make it homoiconic. Similarily, it takes quite a lot of states to implement a Turing machine in a Turing machine, but perhaps not as many. The Peano axioms are succinct, but Gödelization is complicated. On the other hand, LISP requires a decent amount of description at first, but the elegance of the language by essentially specifying an AST allows to write a LISP interpreter in a fairly short form. There seems to be some information theoretic trade-off. I am not interested in advanced language features like arithmetic, however, it just needs to be universal.


texts: Functional Sparse-Matrix with good performance?

texts:
While writing a Petri Net program, I was faced with a choice about data structures to represent the graph. Adjacency lists (i.e. lists enumerating the arcs into and out of individual places or transitions) are easy to implement, but while I was studying the theory of petri nets, I was taken with the beauty of the matrix-based state-equation approach - which would presumably require me to use sparse matrices.

Which led me to wonder - are there are any implementations of sparse matrices providing fast enumeration in both rows and columns? If not, are there alternatives that would allow me to construct and efficiently traverse a bipartite graph in a functional language such as Erlang?

FWIW - By 'efficiently', in this case, I mean fast at enumerating the arcs incident on a given transition or place. I'd be happier to trade space for time if there are trade-offs to be made. Since the graph will not be modified after construction, it need not be particularly efficient for insertions or updates.

TIA


texts: Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?

texts: If we want a specific example, then how about the Erdos-Renyi random graph?


texts: Lower bound for enumerating k closest pair of points

texts:
Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ pairs of points in increasing order of distance.

The trivial algorithm takes $O(n^2 \log n)$ time but we can do better if we are allowed to build a data structure in a pre-processing phase. It is easy to see that one can build a data structure that takes $O(n \log n)$ time and $O(n \log n)$ space in the following way - we simply sort all of the input points and store the closest candidate for each point in a heap. Then, with $O(\log n)$ delay, I can get an output element. For the point which was popped from the heap, we can add the next closest point using binary search over the input and inserting into the heap (both operations take $O(\log n)$ time). Although this method is better, it still takes $O(n^2 \log n)$ time in total.

Question 1 - My question is whether there is a known lower bound that total enumeration cannot be done in $o(n^2 \log n)$ time. This was listed as an open problem here. I am looking for references that prove a lower bound or a more recent paper that confirms this is still an open problem.

Question 2 - What happens if I replace distance function to $d(x_i, x_j) = x_i + x_j$? Does this make the problem easier and admit $o(n^2 \log n)$ time algorithm?


texts:
In the HoTT book, it is said

  The type of booleans 2 : U is intended to have exactly two elements. It is clear that we could construct this type out of coproduct and unit types as 1 + 1.

I don't see how this works, since it seems to me A + A = A, which would imply 1 + 1 = 1, and 1 != 2. What am I missing?  (Sorry for the brevity; I'm only able to work and read using a mobile device for this week).


texts:
From time to time, I have to read a paper with unclear typesetting. By this, I mean:

very small fonts; sometimes 8pt or smaller.
very bad scan;
Using bitmap fonts instead of vector ones.
too old formatting (usually dating back to 1970s or the beginning of 1980s.)

In these cases, one might prefer to read a more clear version submitted to the authors' home page. Unfortunately, the author version is not always available; and even in that case, they might be very lengthy (the so-called full version of the paper).

In the case of bitmap fonts, I found a good strategy: Find the postscript (PS) version of the paper, and convert the bitmap fonts to their vector counterparts using pkfix or a combination of pkfix-helper + pkfix, whichever applies (read the documentation).

However, I still can't find a workaround for other problems. Specially, small-font papers bother me a lot. My best bet is to use a desk lamp: I don't know why, but magically the words seem  larger under its light!

  How do you read a paper whose typesetting is unclear? Specially, what do you do when the font is too small to read?

PS: Some months ago, I found an application which "splited" a PDF into several segments, so that they were easy to read on an iPhone or the like. (Sorry, I don't recall the name of that app.) However, the output was downgraded to fit the iPhone small screen, and therefore it wasn't apt for computer screen or printer.


texts: Example of where violation of strict positivity condition in inductive types leads to inconsistency

texts: Most dependent typed systems have a strict positivity conditions for inductive types. Does anybody know an example where violation of the condition leads to inconsistency in the system?


texts: How to properly define a zero-knowledge proof system with oracle access

texts:
An $IP$ system $(P,V)$ is zero-knowledge (ZK) for some language $L$ if for every probabilistic polynomial-time verifer $V^*$ there exists a probabilistic polynomial-time algorithm $S$ for every $x\in L$ such that the output distribution of $(P,V^*)(x)$ and $S(x)$ are "close". Close means that the probability distribution of their outputs are either "equal" (perfect ZK), "statistically close" (statistical ZK), or "computationally indistinguishable" (computational ZK).

My question is,

  if we allow the honest-verifier $V$ to have access to oracle $O$, do we have to allow any other cheating-verifier $V^*$ to also have access to $O$? Or, do we just simply consider all cheating-verifiers without access to any oracle?

My main problem is that, intuitively, the complexity classes for ZK might be very different depending on if we allow the cheating-verifiers such oracle access.

I cannot find any reference regarding relativized classes of ZK. If anyone could direct me to any reference I will really appreciate it. I'm aware of the Random Oracle model (RO), where all parties, even malicious ones, have access to a random oracle. But the goals, motivation, and applications of RO are not the ones I'm interested. I'm interested in relativization results in the Baker-Gill-Solovay sense.


texts: How to understand the "Availability" of the CAP theorem?

texts:
As we know, in the CAP theorem, "A" means "Availability". On wikipedia, the explanation of "Availability" is:

  Availability: a guarantee that every request receives a response about
  whether it was successful or failed

However, from the perspective of engineering, there is no ABSOLUTE availability. We can only say that the availability of a system is 5'9'(99.999%), or even 8'9', but we cannot say that the availability of a system is 100%, 100% available system does not exit in reality, even if the system has millions of duplicated nodes, right?

The CAP theorem proves that no system could satisfy the 3 requirements simultaneously. My question is, if a system claims to satisfy both "A" and "P", what is the accurate meaning of this "A"? 6'9' or even higher?


texts: Möbius values of CNF and DNF lattices of a monotone Boolean function

texts:
Let $\phi$ be a monotone Boolean function on a set of variables $\langle k \rangle := \{0,\ldots,k\}$ such that $\phi$ depends on all the variables in $\langle k \rangle$ (that is, for every variable $x \in \langle k \rangle$, there is a valuation $\nu: \langle k \rangle \setminus \{x\} \to \{\top,\bot \}$ such that $\phi(\nu \cup x \mapsto \top) \neq \phi(\nu \cup x \mapsto \bot)$).

Let $F_{\text{cnf}} = C_0 \land \ldots \land C_n$ be the (unique) minimized CNF representing $\phi$, where we see each clause simply as the set of variables that it contains.
For $\mathbf{s} \subseteq \langle n \rangle$, define $d_{\mathbf{s}} := \bigcup\limits_{i \in \mathbf{s}} C_i$. Note that we can have $d_\mathbf{s} = d_\mathbf{s'}$ for $\mathbf{s} \neq \mathbf{s'}$. Further notice that $d_\emptyset = \emptyset$.

We define the CNF lattice $(L_{\text{cnf}},\leq)$ of $\phi$ as the lattice with underlying set $L_\text{cnf} = \{ d_\mathbf{s} \mid \mathbf{s} \subseteq \langle n \rangle \}$, and where $\leq$ is reversed set inclusion (i.e, $d_\mathbf{s} \leq d_\mathbf{s'}$ iff $d_\mathbf{s'} \subseteq d_\mathbf{s}$). The top element $\hat{1}$ of that lattice is then $\emptyset$, while its bottom element $\hat{0}$ is $\langle k \rangle$.

We define similarly the DNF lattice $(L_{\text{dnf}},\leq)$ of $\phi$, where instead of $F_{\text{cnf}}$ we use $F_{\text{dnf}} = D_0 \lor \ldots \lor D_m$, the unique minimized DNF representing $\phi$. Observe that we have again $\emptyset$ as the top element and $\langle k \rangle$ as the bottom element.

Now, let $\mu_\text{cnf}: L_{\text{cnf}} \times L_{\text{cnf}} \to \mathbb{Z}$ be the Möbius function of the CNF lattice of $\phi$ (resp., $\mu_\text{dnf}$ the Möbius function of its DNF lattice). See, for instance, 3.7 of Enumerative Combinatorics for a definition of that function.

Example:
Let $\phi$ be the monotone Boolean function on variables $\langle 4 \rangle$ defined by the CNF $F_\text{cnf} = (3 \lor 4) \land (0 \lor 4) \land (0 \lor 1 \lor 2)$. You can check that its corresponding DNF is $F_\text{dnf} = (0 \land 3) \lor (0 \land 4) \lor (2 \land 4) \lor (1 \land 4)$. The Hasse diagrams of the CNF and DNF lattices of $\phi$, together with the values $\mu(e,\hat{1})$ for each element $e$ of the lattices, are drawn below (where, e.g., "034: 1" means that it is element $e=\{0,3,4\}$ and we have $\mu(e,\hat{1})=1$):

CNF lattice:

DNF lattice:

QUESTION: Is it always the case that $\mu_\text{cnf}(\hat{0},\hat{1})=0$ if and only if $\mu_\text{dnf}(\hat{0},\hat{1})=0$?
I know a proof of this conditionally to FP $\neq$ #P (which is beyond our scope here), but I would like to prove it unconditionally.

What I know:

First, I know that it does no matter if we start from minmized expressions or not, thanks to the crosscut theorem (see Corollary 3.9.4 of Enumerative Combinatorics, for instance);
Second, using the Möbius inversion formula on the lattices to count the number of satisfying valuations $\#\phi$ of $\phi$, I can easily show that $\#\phi$ is even iff $\mu_\text{cnf}(\hat{0},\hat{1})$  and $\mu_\text{dnf}(\hat{0},\hat{1})$ are both even, so that they have the same parity;
Third, I coded a little something to generate all monotone functions that depend on all their variables $\langle k \rangle$, up to $k=5$ (and there are a lot of them!) and tested my question. I found out that in fact I always had $|\mu_\text{cnf}(\hat{0},\hat{1})| = |mu_\text{dnf}(\hat{0},\hat{1})|$. Moreover I have cases where the signs are the same, and cases where they are opposite.


texts: Smoothed analysis of approximation algorithms

texts:
Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for example Heiko Röglin and Berthold Vöcking, Smoothed analysis of integer programming, 2005.
Some of these general results seem to rely on isolation lemmas in order to produce an instance with a unique optimal solution.
Assuming $\mathsf{NP}\ne \mathsf{ZPP}$, this paper rules out the existence of smoothed polynomial time algorithms for $\mathsf{NP}$-hard problems.
Some work has been done on smoothed analysis for approximation algorithm ratios.
There is Rao Raghavendra, Probabilistic and Smoothed Analysis of Approximation Algorithms, 2008 which attempts to give an improved approximation bound for the Christofides algorithm with smoothed analysis. No explicit approximation ratio is given, though.
Is there any reason for why hardness of approximation results should limit the approximation ratios of algorithms that run in smoothed polynomial time? Do the results in Heiko Röglin and Berthold Vöcking's paper also apply for approximation algorithms?


texts: Is there any task where classical computers outperform quantum computers?

texts:
Everybody knows that there are whole classes of problems which quantum computers are able to solve much faster (i.e. with fewer instructions) than classical computers.

Is there any problem for which the reverse is true?


texts: The Optimum Strategy to Find the Best Parking Slot Along a Busy Road

texts:
Imagine that you are going to a shop. In front of the shop there are $N$ number of parking slots. That shop is located at the $k^{th}$ slot.

As you drive along the parking slots, you notice that for $n$ parking slots, $n_{fill}$ of the slots are filled, whereas $n_{empty}$ slots are empty ( naturally, $n=n_{fill}+n_{empty}$ and $n<k$ ).

Base on this information, and the assumption that all slots are equal ( that is, one won't prefer this slot over that slot, or this block of slots over that block of slots), what is the optimum strategy to find the parking space that is the nearest to the shop?


texts: What technique is used to implement type checking for CoC?

texts:
I am studying David Christiansen's tutorial on implementing a dependently typed language, where it says:

Typed normalization by evaluation is far from the only way to implement conversion checking for dependent types. Indeed, normalization by evaluation has a number of characteristics that make it only suitable for certain theories: it η-expands expressions as many times as possible, but η-expansion is not valid for some theories (including Coq’s Calculus of Constructions)

May I have a reference to why η expansion is invalid for CoC? Is there some "moral" by which one can see the rules of CoC and realise that η expansion is invalid?
The rules for implementing CoC in ATAPL Chapter 2 look to my naive eye like NBE (Normalization by Evaluation). The rules for CoC are given as an extension to the equivalence rules of LF, augmented with extra rules that govern how Prf (the encoding mechanism of Pi types) and Prop interact. The rules QA-NABS-1, QA-NABS-2 seem to be implementing η expansion for stuck terms? Why do these rules not describe NBE?
Is there a name for the rules given in ATAPL to implement type checking for CoC? They seem ad-hoc to me, and I don't understand how I would come up with them. I would appreciate a reference to the framework that is used to create the reduction rules for CoC (for clarity, by a framework, I refer to ideas such as NBE or hereditary substitution)

I have included the rules for CoC as given in ATAPL, Chapter 2, for reference:


texts:
Are there any known natural examples of optimization problems for which it is much easier to produce an optimal solution than to evaluate the quality of a given candidate solution?

For the sake of concreteness, we may consider polynomial-time solvable optimization problems of the form: "given x, minimize $f(x, y)$", where $f:\{0,1\}^*\times\{0,1\}^* \to \mathbb{N}$ is, say, #P-hard. Such problems clearly exist (for instance, we could have $f(x, 0) = 0$ for all $x$ even if $f$ is uncomputable), but I am looking for ``natural'' problems exhibiting this phenomenon.


texts: Algorithm for maximum bipartite matching with arriving edges?

texts: Given a bipartite graph with fixed nodes and incrementally arriving edges, is there any efficient algorithm to compute and update the maximum matching?


texts:
So we all know the comparison-tree lower bound of $\lceil\log_2 n!\rceil$ on the worst-case number of comparisons made by a (deterministic) comparison sorting algorithm. It does not apply to randomized comparison sorting (if we measure the expected comparisons for the worst case input). For instance, for $n=4$, the deterministic lower bound is five comparisons, but a randomized algorithm (randomly permute the input and then apply merge sort) does better, having $4\frac{2}{3}$ comparisons in expectation for all inputs.

The $\log_2 n!$ bound without the ceilings does still apply in the randomized case, by an information-theoretic argument, and it can be slightly tightened to
$$k+\frac{2(n!-2^k)}{n!} \text{, where } k=\lfloor\log_2 n!\rfloor.$$
This follows because there is an optimal algorithm that randomly permutes the input and then applies a (deterministic) decision tree, and the best decision tree (if it exists) is one in which all leaves are in two consecutive levels.

What if anything is known about upper bounds for this problem? For all $n>2$, the randomized number of comparisons (in expectation, for the worst-case input, for the best possible algorithm) is always strictly better than the best deterministic algorithm (essentially, because $n!$ is never a power of two). But how much better?


texts: Is there a PSPACE-intermediate language?

texts:
Suppose PH is strictly contained in PSPACE. Is there a problem in PSPACE that is not in PH and not PSPACE-complete?

I encountered a language that is in PSPACE. The question is whether it's in PH. So far I don't have any success in either proving it's in PH or proving it's PSPACE-complete. I wonder if there is a languge that's not in PH and not PSPACE-complete given PH $\ne$ PSPACE.


texts:
I'm starting a research about parallel clustering. I see a ton of articles on this topic, so that I don't know where to start. I'd like to get familiar with classic methods of parallelizing clustering. Are there any "have-to-know" books/papers in this area, that would provide me a good introduction?

I'm interested in shared-nothing architecture, generally something that may be suitable for map-reduce model.


texts: Collection of failed attempts to solve X

texts:
I've been half-jokingly entertaining the idea of trying to blog about "n ways not to solve P vs NP" in the indefinite future, and in my search came across the How not to solve P=NP? question on cs.stackoverflow.

Clearly P vs NP is a great starting point, being the source of so much development in TCS. But this got me wondering if there are other problems where people have consistently published their failures, or just any thoughts on why some things don't work. Surely not in papers, unless a strong negative result came out, but probably in blog format (which is increasingly becoming its own medium for communicating science).

Of course, this doesn't seem very practical (unless you store all your progress in digital or easily-convertible-to-digital format), but maybe the benefits outweigh the costs. So the other natural question is, how useful do you think it would be if we started doing it as a community? How often is a failed attemp one (or several) steps away from a success?


texts: Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications

texts:
Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with excluded minors make heavy use of Robertson and Seymour’s structure theory for graphs with excluded minors, especially when the treewidth is large (small treewidth usually makes problem to be easily solved by dynamic programming) [2].

However, there are some results are trying to avoid using the grid minor theorem. For example, Chekuri and Chuzhoy [3] show a framework for using theorems to bypass the well-known Grid-Minor Theorem of Robertson and Seymour in some applications. In particular, this leads to substantially improved parameters in some Erdos-Posa-type results, and faster running times for algorithms for some fixed parameter tractable problems.

Do you know any other examples of problems with large treewidth avoid using the grid minor theorem?


texts: Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?

texts:
It is well known that if a constraint matrix $A$ is total dual integral or totally unimodular, then this is a sufficient condition of integrality of the polyhedron defined by the system $Ax \leq \beta$ (provided that $\beta$ has integer entries). But it is not a necessary condition.

Thus my question is

  Are there natural examples (from combinatorial optimization) of integral polyhedra such that their underlying constraint matrix is neither TUM nor TDI?


texts:
Has any research been done on paradox-driven computers?

An example of what I mean by "paradox-driven":

Given a computer which can send information back through time, an algorithm to instantly break passwords would be:

crackPassword(){
    String password=recieveFromFuture();
    if (password.checkIfCorrect()){
        sendToPast(password);//no paradox generated, valid password found.
    }else{
        sendToPast(password++);//paradox generated, this "parallel universe" cannot exist.
    }
    return password;
}

Since every parallel universe which does not contain a correct password is impossible, the user will continue on one or more valid "parallel universes".

This allows for the solution of any problem in O(1) time, so long as the answer is easily verified.

To the user this would appear as if the program immediately jumped to a valid password.


texts: Book Recommendations for a General Introduction to (Theoretical) Computer Science

texts:
After perusing the web and cstheory.stackexchange in particular, I've come across many different wonderful resources in Computer Science - from Sipser's "Introduction to the Theory of Computation" to books on Languages or volumes on Cryptography.

However, what I couldn't find was a general introduction to Computer Science, a book that covers some of these topics briefly in distinct chapters. That is to say, a chapter on computational complexity, a chapter on languages, a chapter on logic, a chapter on cryptography, a chapter on algorithms etc, all in one book.

I'm a math major, and whenever I run into things like hash functions or "automata", I have to hit Google and go from there. It'd be nice if I could have a book that could get me reasonably up to speed on many of these foundations and central ideas in (theoretical) computer science without having to read 4 different books about 4 different fields in CS totalling 2000+ pages.

Just to be clear, I'm not really looking for hands-on books on how to write code - this question pertains mostly to the theoretical bases of CS (although I wouldn't mind a chapter on functional programming or "programming concepts"). Also, my preference goes out to a book as opposed to a website or online resource as I travel a lot and usually don't have access to the internet, though I do have the habit of taking a book with me.

In essence, I'm thinking about something equivalent to "University Physics" books (but instead, a fair bit shorter as those tend to be huge tomes of 1400+ pages), or "Mathematical Methods for Scientists" - something like that.


texts: Transform a CNF into an equivalent 3-CNF defined on the same variables

texts:
(I posted this question on CS ten days ago, with no answer since then - so I post it here.)

Any CNF formula can be transform in polynomial time into a 3-CNF formula  by using new variables. It is not always possible if new variables are not allowed (take for instance the single clause formula : $(x_1 \lor x_2 \lor x_3 \lor x_4)$).

Let define the (SAT to 3-SAT) problem : Given $F$, a CNF formula. Is it possible to transform $F$ into an equivalent 3-CNF defined on the same variables as $F$ ? - where "equivalent" means with the same set of models.

What is the complexity of this problem ?


texts: Explaining input-size of integral arguments to undergraduate CS students

texts:
When I teach undergraduate algorithms, the students have no problem accepting that two n-bit numbers can be added in $O(n)$ time, or that modular exponentiation takes $O(n^3)$ time.

But when we get to knapsack and solve it via DP, they are confused.  For example, the conventional approach to knapsack for $N$ items and a $W$-capacity bag  is the straightforward $O(NW)$ DP method.  But I then point out that $W=2^n$ and therefore DP is exponential time.  This invariably causes objections, confusion, and lots of doubt.  I have yet to find a way of explaining this that makes it clear.  Can anyone help?

Oh, and they haven't seen Turing machines, so that's off-limits.


texts: Common terminology used for lower/upper bounds

texts:
Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it were an optimization problem then I would call it the optimal value or the optimal bound. Do you agree?

I am familiar with the term tight lower/upper bound. According to Wikipedia,

  An upper bound is said to be a tight upper bound, a least upper bound, or a supremum if no smaller value is an upper bound. Similarly a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum if no greater value is a lower bound.

This definition does not mention whether the bound is achieved by an infinite family of instances or all instances.
I looked up several books on "combinatorics", "algorithms", "graph theory" and "optimization". I could not find a reference that formally defines what a tight bound is.

According to the book Approximation Algorithms by Vijay V. Vazirani:

  An infinite family of instances of this kind, showing that the analysis of an approximation algorithm is tight, will be referred to as a tight example.

So given a bound (e.g., upper bound), an example is tight if it represents an infinite family of instances achieving the bound. However, this bound may not be the best possible bound that can be found for the problem. What if you have the best possible bound (say optimal bound) for the problem and give a tight example corresponding to it? Although the example is still tight (by definition), it is different from other tight examples since its corresponding bound is optimal. So basically the question is, can we call the bound optimal (as I did!) or there is already a definition for such a bound? I have also heard of the phrase "theoretical lower/upper bound" but have no idea when we should use it!

How do you differentiate the above terminologies (preferably by formal definitions)? Are there any other terminologies that are not mentioned here?


texts: Linear time in-place riffle shuffle algorithm

texts:
Is there a linear time in-place riffle shuffle algorithm? This is the algorithm that some especially dextrous hands are capable of performing: evenly dividing an even-sized input array, and then interleaving the elements of the two halves.

Mathworld has a brief page on riffle shuffle. In particular, I'm interested in the out-shuffle variety which transforms the input array 1 2 3 4 5 6 into 1 4 2 5 3 6. Note that in their definition, the input length is $2n$.

It's straightforward to perform this in linear time if we've got a second array of size $n$ or more handy. First copy the last $n$ elements to the array. Then, assuming 0-based indexing, copy the first $n$ elements from indices $[0,1,2,...,n-1]$ to $[0, 2, 4,...,2n-2]$. Then copy the $n$ elements from the second array back to the input array, mapping indices $[0,1,2,...,n-1]$ to $[1,3,5,...,2n-1]$. (We can do slightly less work than that, because the first and last elements in the input do not move.)

One way of attempting to do this in-place involves the decomposition of the permutation into disjoint cycles, and then rearranging the elements according to each cycle. Again, assuming 0-based indexing, the permutation involved in the 6 element case is
$$
\sigma=\begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\
0 & 2 & 4 & 1 & 3 & 5\end{pmatrix}=\begin{pmatrix}0 \end{pmatrix} \begin{pmatrix}5 \end{pmatrix} \begin{pmatrix}1 & 2 & 4 &3 \end{pmatrix}.
$$

As expected, the first and last elements are fixed points, and if we permute the middle 4 elements we get the expected outcome.

Unfortunately, my understanding of the mathematics of permutations (and their $\LaTeX$) is mostly based on wikipedia, and I don't know if this can be done in linear time. Maybe the permutations involved in this shuffling can be quickly decomposed? Also, we don't even need the complete decomposition. Just determining a single element of each of the disjoint cycles would suffice, since we can reconstruct the cycle from one of its elements. Maybe a completely different approach is required.

Good resources on the related mathematics are just as valuable as an algorithm. Thanks!


texts:
I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me?

In my problem, I have a bipartite graph with N abound 1000 (#vertices on each side) and the Hungarian algorithm takes too much time to be an option for my case.

the weight on edges are real numbers but it's ok to round them to integer numbers
I have a brute-force greedy implementation, however, I am looking for something more sophisticated

Thanks


texts: Find items that are in at least $k$ of $n$ sets

texts:
Consider $n$ sets of values (represented as sorted arrays with no duplicates, and with a known size (ie. the size can be obtained in O(1)). The values can be tested for equality in O(1) time. I want to obtain the set of values that are present in at least $k$ different sets among the $n$.

The obvious algorithm to do this is to go through all the sets, count the number of occurrences of each value, and return those with a count higher than $k$. Yet, in some cases, you can do better: for instance, when $n = k = 2$ and when one set $S_1$ is much smaller than the other set $S_2$, it is more efficient to look at all items of $S_1$ and perform a binary search for each of them in $S_2$: the binary search approach costs $O(|S_1| \log(|S_2|))$ whereas the naive approach costs $O(|S_1| + |S_2|)$ which is worse when $|S_1| << |S_2|$.

With this in mind, in which situations can we do better than the naive algorithm? (If this is a well-known problem, I would be happy to know its usual name and have references.)


texts: Who introduced nondeterministic M-automata, and proved that the finite ones recognize the rational sets over M?

texts:
Let $M$ be a monoid. The family $\operatorname{RAT}(M)$ of rational sets over $M$ is defined inductively:

If $L$ is a finite subset of $M$, then $L\in\operatorname{RAT}(M)$.
If $K,L\in\operatorname{RAT}(M)$, then $K\cup L\in\operatorname{RAT}(M)$ and $KL\in\operatorname{RAT}(M)$.
If $L\in\operatorname{RAT}(M)$, then $L^*\in\operatorname{RAT}(M)$.

A similar definition can be found in "J.-E. Pin, Mathematical Foundations of Automata Theory", and already "S. Eilenberg, Automata, Languages, and Machines" defines rational sets.

A nondeterministic $M$-automaton $\mathcal A = (Q,\delta,I,F)$ consists of a set of states $Q$, a transition relation $\delta\subset Q\times M\times Q$, a set of initial states $I\subset Q$, and a set of final states $F\subset Q$. If $\delta$ is a finte set, then we say that $\mathcal A$ is finite. A run on $\mathcal A$ is a sequence of the form $$r=q_1u_1q_2\dots u_nq_{n+1}$$ with $(q_iu_iq_{i+1})\in\delta$ for all $1\leq i\leq n$. If $q_1\in I$ and $q_{n+1}\in F$, then we say that it accepts $u=u_1\dots u_n$. The set accepted by $\mathcal A$ is defined as $$L(\mathcal A):=\{u\in M|\mathcal A \text{ has a run } r \text{ that accepts }u\}$$

I found this definition in chapter 7 Automatentheorie of the German text book "Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden: Arithmetik, Kryptographie, Automaten und Gruppen”. There we also find the following theorem:

Theorem 7.15 Let $M$ be a monoid and $L\subset M$. Then the following are equivalent:

$L$ is rational, i.e. $L\in\operatorname{RAT}(M)$.
$L$ is accepted by a nondeterministic finite $M$-automaton.
$L$ is accepted by a "spelling" nondeterministic finite $M$-automaton with a single initial state.
$L$ is accpected by a nondeterministic finite $M$-automaton with "rational labels".

I omitted the definitions for "spelling" and "rational labels", because I only want to know who first introduced nondeterministic M-automata, and proved the equivalence of (1) and (2).


texts:
To prove unforgeability of threshold signatures TSig =(TKeyGen, TSign, Verify), it is sufficient to prove that the underlying signature scheme Sig=(KeyGen, Sign, Verify)
is secure and TSig is simulatable.
My question is what's the intuition behind defining the security of threshold blind signatures the same way, and is it applicable for signatures on committed messages.


texts:
I am reading an old paper of M.C. Golumbic about EPT (edge intersection of paths in a tree) graphs. In the paper it is shown that the number of maximal cliques of an EPT graph instance is polynomial. It concludes that if an oracle reports that a graph $G$ is an EPT graph, then  it is possible to find the maximum clique with a standard clique enumeration algorithm.

First of all, what are these standard clique enumeration algorithms? If there are more than one, can we say that if the number of maximal cliques of a graph is polynomial then can we use any of these enumeration algorithms? Or should we derive a special algorithm from a generic algorithm which uses some special structures of the graph class?

Thanks in advance.