texts:
I'm more of a quantum optics guy than a quantum info guy, and deal mainly in master equations. I'm interested in operator-sum form, and I'd like to derive the errors in this form for a small quantum system that I'm simulating.

The catch: The quantum system is driven by an external (classical) field modelled with a sinusoidal function, and the damping rates are low, so I can't make a rotating wave approximation to eliminate this time dependence. Given that I must solve the master equation numerically by integration, and the result of each integration at time $t$ is not sufficient information to figure out these errors, and I need to do some work to recover the superoperator matrix that has operated on a vectorised density matrix. i.e. I feed the master equation a vectorised density matrix with a single entry of 1 and the rest zero, and build the matrix like that for a particular time $\tau$. Am I on the right track here (sanity check)? More explicitly, if $\mathrm{vec}(\rho_{ij,t=\tau})$ is the vectorised (so it's a column vector) form of a density matrix with a single entry of 1 in position $i,j$, at $t=0$ that has been evolved to time $\tau$, then a matrix to take the vector form of the density matrix from $t=0$ to $t=\tau$ is given as $\mathbf{M}=\sum_{i,j}\mathrm{vec}(\rho_{ij,t=0})\mathrm{vec}(\rho_{ij,t=\tau})^\dagger$.

The question: Given this superoperator $\mathbf{M}$ that does $\mathbf{M}\,\mathrm{vec}(\rho_0)=\mathrm{vec}(\rho_\tau)$, how can I get Krauss operators for the operator-sum equivalent of $\mathbf{M}$ that are in a useful form? i.e. the system in question is a qubit or a qutrit and another qubit or qutrit. I'd like to be able to do the operator sum in the form of tensor products of spin matrices on each channel if possible.

Side question: Is $\mathbf{M}$ a Choi matrix?

Final note: I awarded the acceptance to Pinja, as I used the paper Pinja suggested. I have provided an answer myself below that fills in the details.


texts: Testing/Identifying a Topological Sorting

texts: You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the best algorithm that could identify the graphs among $G_1, G_2, ..., G_n$ that have $(v_1,v_2,...,v_m)$ as a topological sort? Could someone test whether $(v_1,v_2,...,v_m)$ is a topological sort of a DAG $G$ over $V$ in sub-linear time?


texts: Proof of Correctness of Bottleneck Dijkstra Algorithm

texts:
I am working on a bottleneck multicast tree for which I am using bottleneck Dijkstra algorithm.

My question is 1) bottleneck Dijkstra has the same correctness as that of (simple) Dijkstra or not ?

2) if yes then how and if no then how?

Will be happy to see your responses. Thank you


texts: Bin packing approximation with different bin sizes

texts:
Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size?

More formally, there are $n$ bins of size $b_i$ for $i=1,\dotsc,n$, and $m$ objects, each of size $o_j$ for $j=1,\dotsc,m$.

Is there a solution that can pack all of these items into the bins?


texts: I have a very large directed graph (1M nodes) I am wondering what is the best algorithm for finding the longest (most number of nodes) cycle in the graph?


texts: Can relativization technique be applied to natural NP-complete languages?

texts:
Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is hard if there is no efficient algorithm that solves the problem (with high probability) on instances sampled from D.

Holenstein and Kunzler [2]asked the following question:
Question: Does $NP\nsubseteq BPP$ imply that there exists a hard problem in $distNP$?

Impagliazzo [3] showed that any proof that gives a positive answer to the above question must use non-relativizing techniques. More precisely, it is shown that there exists an oracle $O$ such that $NP^O\nsubseteq BPP^O$, and there is no hard problem in $distNP^O$.

My question: Does there exists $X\subset NP$ such that there exists an oracle $O$ such that $X^O\nsubseteq BPP^O$, and there is no hard problem in $distX^O$? More specifically, how about if $X$ is a natural NP-complete problem which is can be represented by paddable language (i.e. we can encode arbitrary additional information, without changing the membership of the instance in the language.)?


texts:
Consider the following min-max problem

Given a graph $G=(V,E)$ and an integer $k \geq 0$, delete at most $k$ nodes in $G$ to maximize the size of the minimum dominating set in the residual graph.

The NP-hardness of the problem can be shown by setting $k=0$. Can we somehow easily get the hardness of approximation results from the hardness of the Dominating Set problem? In general, for min-max problems, can we do the same thing?


texts:
Let us suppose that I have defined a new convenient form of the Turing machine for processing of some specific sort of commonly used structures.

This form of TM contains some specific features related to the considered structures and specific rules of its instruction applying.

Obviously any TM of my form can be transformed to the conventional classical Turing Machine (and vice-versa), as my structures can be represented as flat strings. But my form is more convenient to deal with this structures and I have implemented visualisation software which emulates this process.

My question is: is any sense of publishing a paper describing this type of machine or it is just multiplying entities beyond necessity?


texts:
Problem

I do not understand why larger $p$ will give a larger covering number.

Since when $p\geq q$, the corresponding hypercube is also larger (by $\| x \| _ { q } \leq n ^ { ( 1 / q - 1 / p ) } \| x \| _ { p }$ when $p > q>0$) and thus should give smaller covering set. Covering number is essentially the minimum cardinality of covering set, so it seems that larger $p$ should give smaller covering number?


texts: Is it possible to convert any tree to a B-tree or an R-tree?

texts:
I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an arbitrary number of directed edges linking it to other nodes (i.e. children, parent and different grammatical relations such as subject_of, complement_of, etc.). Note that all these features are absolutely necessary to accurately represent the syntactical structure of a sentence.

Now, given such an initial tree with a totally unconstrained structure, I want to know if it is possible to convert that tree into a form that is more search-efficient (i.e. so that search involves less recursion). The only operation I really need to support is finding nodes with an arbitrary combination of type, id, value, and/or feature(s). I also need to be able to match a node back to the original tree if other operations are necessary. What is of primary importance is read-time and query efficiency.

From what I understand, B-trees and R-trees are generally search efficient. From Wikipedia, "like B-trees, this makes R-trees suitable for large data sets and databases, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory." This is exactly the situation I am in right now. However, I have very limited knowledge of the different types of trees and how they convert to another.

So, I am wondering if it is possible in theory to convert any N-ary tree (i.e. in my case, a completely unconstrained tree with an arbitrary number of children, edges and features for each node) into a B-tree or an R-tree to make it more search efficient? How would one go about doing this?


texts:
How would you design a picture to illustrate the unique games conjecture?

This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be produced.

Example of the kind of illustrations produced in the past are at

http://www.ams.org/meetings/lectures/current-events-bulletin

and if you click on the 2006 edition you can see the picture that Madhu Sudan used to illustrate his talk on PCP.

I have thought about using the gadget reducing unique games to max cut, or the Khot-Vishnoi graph for reasonably small size. A good suggestion I received was to draw the label-extended graph of a nearly-satisfiable instance of unique games, and highlight in a different color the vertices corresponding to an optimal solution.

Other suggestions?


texts:
Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem:

Is the top-right entry of $M^n$ positive?

Note that the obvious approach of iterated squaring (or any other explicit calculation) requires us to potentially handle integers of doubly exponential magnitude, i.e., having exponentially many bits. However the problem is easily seen to be in Allender et al.'s "PosSLP" class ("On the Complexity of Numerical Analysis", SIAM J. Comput. 38(5)), and therefore in the fourth level of the counting hierarchy.

1) Is it possible to place this matrix powering problem in a lower complexity class?

2) If not, could it conceivably be PosSLP-hard?

3) I am especially interested in the matrix powering problem for low-dimensional matrices, i.e. up to and including 6x6 matrices. Might the complexity be lower for such matrices?


texts: Is there a programming language where any arbitrary recursive function can be fused?

texts:
Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend this problem, such as Stream Fusion, which allow the combination of list consuming/producing functions. Those techniques require specialised, specific algorithms and only work for a restricted set of recursive functions.

My question is: what determines which recursive functions can, and which recursive functions can not be fused that way? Is there a programming system with well-behaved recursion where any arbitrary function could be fused this way?


texts: In what sense are coroutines dual to (sub)routines?

texts: The name coroutine suggests that in some sense they should be dual to (sub)routines. Is there a real mathematical duality? I'm hoping for something like "in category theory subroutines are X and coroutines are Y, where X is dual to Y".


texts: Best book on Simplex Method implementation?

texts:
I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in exponential time. I've also heard that naive implementation can loop for some kind of data.

Is there a book/paper/source which explains nuances of practical implementation of SM?

Thanks in advance.


texts: Alternative proofs of Savitch's theorem?

texts:
Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one?

By the usual one I mean the proof based on recursively querying whether there is a midpoint.

Whether a proof is different is subjective, but hopefully not too subjective for this forum.

What I Learned:

A superficially different argument first shows graph reachability is in log-space uniform $AC^1$, by building a circuit calculating $G^{|G|}$ via repeating squaring, and then providing a depth first algorithm that shows that log-space uniform $AC^1$ is in $L^2$. (Reference: https://cs.stackexchange.com/a/90950/66344). I think the essential idea is the same.
This paper offers a different formalization of Savitch's theorem as a game:  https://link.springer.com/chapter/10.1007/978-3-642-11512-7_2 The intuition is nice, but the essential idea is the same.
It seems that no improvements on Savitch's theorem are known ( https://rjlipton.wordpress.com/2009/04/05/savitchs-theorem/ ), but this is not the same question.


texts:
I want to start learning about Network Coding:

http://en.wikipedia.org/wiki/Network_coding

Do you know any good survey (e.g. from IEEE Surveys and Tutorials) on the above subjects. I found some university courses on google but I'd like some recommendations from people who already read and know a good source.

Thanks
Vasilis


texts: Dynamic 2-dimensional orthogonal range reporting in external memory and linear space

texts:
Orthogonal 2-dimensional range reporting is the problem of storing a set of values from $U \times V$, where $U$ and $V$ are totally ordered universes, subject to queries of the form "Return all stored points in the four-sided box $[a,b] \times [c,d]$", where $a,b \in U$ and $c,d \in V$ are parameters of the query.

Nekrich, in "Orthogonal range searching in linear and almost-linear space
", summarizes the best known results for linear space:

$$
\begin{array}{|l|l|l|}
\hline \text{Reference} & \text{Query Time} & \text{Modification Time} \\
\hline \text{Kreveld and Overmars} & O(\sqrt{n \lg n} + k) & O(\lg n)\\
\hline \text{Chazelle} & O((k+1)\lg^2 n) & O(\lg^2 n)\\
\hline \text{Nekrich} & O(\lg n + k \lg^\varepsilon n) & O(\lg^{3+\varepsilon} n) \\
\hline
\end{array}
$$

Kreveld and Overmars, "Divided K-d trees"
Chazelle, "A functional approach to data structures and its use in multidimensional searching"
Nekrich, "Orthogonal range searching in linear and almost-linear space
"

What are the best known extensions of these in external memory? The result from Arge et al.'s "On two-dimensional indexability and optimal range search indexing" uses superlinear space. The only generalizations I know have bounds

$$
\begin{array}{|l|l|l|}
\hline \text{Reference} & \text{Query Time} & \text{Modification Time} \\
\hline \text{Kanth and Singh} & O(\sqrt{n/B} + k/B) & O(\lg_B n)\\
\hline \text{Procopiuc et al.} & O(\sqrt{n/B} + k/B) & O\left(\frac{1}{B} \left( \lg_{M/B} \frac{n}{B}\right) \left(\lg \frac{n}{M}\right)\right)\\
\hline
\end{array}
$$

Kanth and Singh, "Optimal dynamic range searching in non-replicating index structures"
Procopiuc et al., "Bkd-tree: A Dynamic Scalable kd-tree"


texts: Different algorithms for longest increasing subsequence

texts:
The longest increasing subsequence problem has a simple and elegant $O(n \log n)$ time solution via patience sorting.

Such a basic and well-studied problem, however, should have a number of different solutions, just as sorting does.

Are there other distinct $O(n \log n)$ time algorithms for this problem?


texts: How far has computer science moved past Knuth's TAoCP, if at all?

texts:
The seminal book The Art of Computer Programming got its start in 1968. I have been finding references to it in many literature reviews, apparently there are many problems for which a review by Knuth done in the 1970s has remained state-of-the-art up until today. It is amazing to me that so many of the theoretical developments of the time have survived decades of the obsolescence cycles that have eliminated all of their original implementations.

What fraction of the content of TAoCP have been eclipsed by later research? If an algorithm is found in TAoCP, what are the odds that a better one is out there in today's literature?


texts: I want to make a first SAT solver. I know the SAT competition and the SAT conference, and there are just so many papers on this subject. I'm a starter, an overwhelmed starter. Where should I begin? Eventually I want to push the state-of-the-art. I want some expert advice on how to start, so that I won't be wasting my time on the non-essentials too early. Many thanks.


texts:
Tarjan described a procedure for decomposing a graph using clique separators in "Decomposition by clique separators", RE Tarjan - Discrete mathematics, 1985 - Elsevier.

He also proposed different divide-and-conquer algorithms for various graph problems such as maximum clique, minimum coloring and maximum independent set. An atom is a subgraph of a graph that does not contain a separator. If one can solve the problem efficiently in the atoms (local solutions) then Tarjan describes in the same paper how to extend these local solutions to a global solution. Therefore characterization of the atoms is very important. For example an atom of a chordal graph is a clique and the atoms of an edge intersection graphs of paths in a tree are exactly line graphs of a multigraph.

I am wondering the characterization of atoms for other graph classes like for example disk graphs or AT-free graphs.


texts: Coloring where all colors are present in closed neighborhood of every vertex

texts:
I am interested in (proper) vertex colorings of graphs with the following condition:
for every vertex $v$ in the graph, all colors should be present in the closed neighborhood of $v$.
Is this studied in the literature? The closest I found is $r$-dynamic $k$-coloring. For $k$-regular graphs, a ($k-1$)-dynamic $k$-coloring satisfies the above condition. But, I am also interested in a coloring that use less than $k$ colors and satisfies the above condition. Currently, I am more interested in such coloring of regular graphs.
If there is a paper dealing with ($k-1$)-dynamic $k$-colorings of $k$-regular graphs, I would like to read it (I saw a result on ($k+1$)-dynamic $k$-colorings in a paper).
Thank you.
Related Colouring Variants:-

$r$-dynamic $k$-coloring (also called $r$-hued $k$-coloring)
An $r$-dynamic $k$-coloring of $G$ is a (proper) $k$-coloring of $G$ such that every vertex $v$ in $G$ has neighbors in at least $\min\{deg(v),r\}$ different color classes.
b-coloring
A b-coloring is a (proper) coloring such that every color class $V_i$ contains a vertex $u_i$ which has neighbors in all other color classes.
In the coloring variant I am looking for, every vertex has neighbors in all other color classes.

Definition:-
For a vertex $v$ of $G$, the closed neighborhood of $G$, denoted by $N[v]$, is $v$ together with its set of neighbors.
i.e., $N[v]=\{v\}\cup\{u : uv\in E(G)\}$.


texts: Induction over a transitive relation in Coq

texts:
I have the current problem when using induction with Coq:

I have states ST, which are pairs (A,B), where A are Addresses (nat) and B are Memories (A parameter)

Open Scope type_scope.

Definition Address := nat.
Parameter Memory : Set.

Definition State := ( Address *  Memory ).

and a reflexive and transitive relation between states:
    ST ==> ST',
which builds on a relation that performs the 'single step' between states:
    ST --> ST'

Reserved Notation "S '-->' S'" (at level 50, left associativity).
Inductive eval : State -> State -> Prop :=
| eval_step : forall (a a' : nat) (m m' : Memory),
  a' > a ->
  (a, m) --> (a', m')

where "S '-->' S'" := (eval S S') : type_scope.

Reserved Notation "S '==>' S'" (at level 50, left associativity).
Inductive eval_trans : State -> State -> Prop :=
| refl : forall (t : State),
  t ==> t

| trans : forall (t t' ti : State),
  t --> ti ->
  ti ==> t'->
  t ==> t'

where "S '==>' S'" := (eval_trans S S') : type_scope.

When performing induction on an hypothesis of the form
    ST ==> ST',
I should get two cases to prove.

When I introduce the various parts of a state among the hypotheses and then induce over a ST==>ST' hypothesis,
CoQ forgets the biding between a state and its component.
E.g. if ST is A,B and I have A,B among the hypotheses, induction here will forget the binding between ST and A,B.
This is a known problem (https://stackoverflow.com/questions/4519692/keeping-information-when-using-induction), that can be circumvented with a "remember A,B as ST".

However, in the transitive case, the "remember" does some wrong things, as the single step becomes
    ST --> ST'
    ST' ==> ST''
(and an inductive hypothesis of the form, if ST' = A,B , having already ST = A,B, then ST ==> ST')
The single step is performed between the same state, which should not be the case.

If I drop the "remember", the transitive case works fine, as expected,
    ST --> ST'
    ST' ==> ST''
but, alas, the state ST is a generic state and not A,B.

Lemma some_lemma :
  forall (a a' : Address) (m m' : Memory),
    (a, m) ==> (a', m') ->
    (a, m) ==> (S a', m').
Proof.
intros a a' m m' H.
induction H.
(*base case*) admit.
(*inductive case*) admit.
(*in both cases I lost that t = (a,m), but the IH is right*)
Admitted.

Lemma some_lemma_v2 :
  forall (a a' : Address) (m m' : Memory),
    (a, m) ==> (a', m') ->
    (a, m) ==> (S a', m').
Proof.
intros a a' m m' H.
remember (a,m) as t.
induction H.
(*base case*) admit.
(*inductive case*)
(* I have that t = (a,m) and the IH sais that if ti =(a,m) then have some ==>,
but ti is the state t reaches after 1 step (H)*)
Admitted.

Any help is greatly appreciated.
I have created this example by shortening the case I am working on, I believe all the important details to be present.

thank you, and sorry in case I have missed some answer being out there in the net, but I couldn't find anything useful.


texts: What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?

texts:
I am trying to find a distribution over $n$ random vectors, say $x_1,\ldots, x_n$, on the $k$-dimensional unit sphere (where $n > k$) that minimizes $\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$ subject to the constraint $\mathbb{E}[x_i^Tx_j]=0$.

I tried some distributions and almost all them have variance $1/k$. For example, both the distribution in which each coordinate of each $x_i$ is independently and uniformly chosen from $\left\{-1/\sqrt{k}, 1/\sqrt{k}\right\}$ and the distribution in which each $x_i$ is an independent uniform vector on the $k$-dimensional unit sphere have variance $1/k$.

Is $1/k$ the minimum variance among all distributions?


texts:
Often, when we take part in TCS conferences, we notice some little details that we wish the conference organisers would have taken care of. And when we are organising conferences, we have already forgotten it.

Hence the question: Which small steps we could easily take to improve TCS conferences?

Hopefully, this question could become a resource that we could double-check whenever we are organising conferences, to make sure that we do not repeat the same mistakes again and again...

I am here interested in relatively small and inexpensive details – something that conference organisers could have easily done if only they had thought about it in time. For example, it might be a useful piece of information that could be put on the conference web page well in advance; a five-dollar gadget that may save the day; something to consider when choosing the restaurant for the banquet; the best timing of the coffee breaks; or your ideal design of the conference badges.

We can cover here all aspects of conference arrangements (including paper submissions, program committees, reviews, local arrangements, etc.).

This is a community wiki question. Please post one idea per answer, and please vote other answers up or down depending on how important they are in your opinion.


texts: Spectrum of a variety: a possible connection btw ordinals and structures?

texts:
Consider a variety of algebras $\mathbb{V} = \mathbb{V}(\sigma,\tau)$ which consists of the set of algebras defined over a fixed signature $\sigma$ and satisfying a set of identities $\tau$. We may then define its ordered version $\mathbb{V}_{or}(\sigma,\tau)$ cas the set of algebras admitting a total order $\leq$ compatible with $\sigma$. By this I mean that:

(*) for each $f : X^n \rightarrow X$ in $\sigma$, for each tuples $t,t' \in X^n$, if $t_i \leq t'_i$ for every $i \in [n]$ then $f(t) \leq f(t')$.

Given such an ordered algebra $A$, we may define its order type $ot(A)$ as the maximum order type of a well-founded order $\leq' \subseteq \leq$ without accumulation points. We may then define the spectrum of the variety $\mathbb{V}$ as the set of ordinals obtainable in that way.

Is this notion known in universal algebra, and if so, which varieties have a known spectra?

An easy case seems to be the variety of ordered fields: for instance, the field of reals $\mathbb{R}$ would have order type $\omega$, and the field of rational fractions $\mathbb{R}(x)$ would have order type $\omega^{\omega}$. So is the following true:

Conjecture: the spectrum of the ordered fields consists of the ordinals closed under addition and multiplication?

(NOTE: I added the requirement that $\leq'$ has no accumulation points, as otherwise any countable ordinal would be embeddable in $\mathbb{R}$. The precise meaning is relative to $\leq$: if $S$ is the set of elements of $\leq'$, we ask that for every $x \in S$, there is an interval $I$ of $\leq$ properly containing $x$ s.t. $I \cap S = \{x\}$.)


texts: Is this a weaker or stronger form of the halting problem

texts:
Halting problem: There is no decider for $L =\{\langle M,w\rangle ~|~ M$ halts on $w \}$
This problem: For any $H$ which can decide some infinite subsets of $L$, then I can always, constructively find $\langle M,w\rangle$ such that $H(\langle M,w\rangle)$ is incorrect.
Here the infinite subset part is supposed to be like heuristics. Primitively checking for infinite loops and things. If someone comes up with a program which can mostly determine halting, I should always be able to come up with an adversarial case in which it fails.
Halting implies these adversarial cases exist, but can I find them at all? Can I find them efficiently?


texts:
The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s.

Are these areas still active in terms of research for parallel algorithms? Are there newer more sophisticated models for parallel computation? Are general models still in vogue, or are researchers trying to specialize with GPGPU or Cloud based computation coming in fashion?


texts:
I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea is we have ally locations and enemy locations. We want to visit all allies while encountering few enemies. I thought of this when reading some papers in combinatorial optimization, but this is not my area of expertise. So, I don't know if I am searching the correct words.
The graph theoretic formulation is that we have an edge weighted graph $G = (V,E)$ which is bicolored so $V = A \cup B$ (note the coloring need not be proper, i.e. $G$ doesn't have to be bipartite). We are given an integer $k$ and want to find a minimum weight cycle (or alternatively path) which contains all vertices in $A$ and at most $k$ vertices in $B$.
Has this problem been studied somewhere? Does it have a name or fit inside a known generalized TSP? Or maybe there is some reduction to known version of TSP?
When $k=0$ we can delete vertices in $B$ along with all edges incident to them and we have the usual TSP.


texts: Massive online collaboration for solving open problem in theoretical computer science

texts:
In Polymath projects a large group work on an open problem.

What kind of problems seem to work best in this framework?
Are there any good candidates for a polymath project in theoretical computer science?
Are there any obstacles that make Polymath projects less likely to succeed in theoretical computer science in comparison to other areas of mathematics?


texts: Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles

texts:
Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles.

Question: Is there some constant $k$ so that the $k$-HamiltonianCycles problem is $NP$-complete on the class of planar $4$ connected graphs? In particular, what about $k = 3$? If not, what about $k = 4$?

Motivation: It is well known that $1$-HamiltonianCycles is $NP$-complete on the class of planar $3$-connected graphs. On the other hand, all planar $4$-connected graphs have a Hamiltonian cycle, by Tutte.

Additionally, it is known that a $4$-connected planar graph $G$ is "Hamiltonian Connected." That is, given any two vertices, $x$ and $y$, there is a Hamiltonian $xy$-path in $G$. This implies that a $4$-connected planar graph always has at least $2$ Hamiltonian cycles. Given one cycle, say $C$, let $e$ be an edge not in $C$. If $\gamma$ is the Hamiltonian path between the endpoints of $e$, we can extend it to a Hamiltonian cycle containing $e$.

If the $4$ connected planar graph $G = (V,E)$ has at least one vertex of degree $\geq 5$, then by $4 |V| > \sum_{v \in V} deg(v) = 2|E|$, $|E| > 2|V|$. This implies that there is an edge not in the union of any two Hamiltonian cycles of $G$, so that one is guaranteed a third Hamiltonian cycle by the same argument as in the previous paragraph. Since a planar graph has at most $3n - 6$ edges, one cannot repeat this to guarantee the existence of a fourth Hamiltonian cycle.

I don't know if there is an argument guaranteeing that all $4$-connected planar graphs have at least $3$ Hamiltonian cycles, or if there is a different kind of argument guaranteeing that all $4$-connected planar graphs have at least $4$ Hamiltonian cycles. I am wondering if these problems, or similar ones, are $NP$-complete.

This question is similar, but not the same: https://mathoverflow.net/questions/233476/what-is-the-complexity-of-finding-a-third-hamilton-cycle-in-cubic-graph


texts: Number of points on the interior of the convex hull of a random subset

texts:
This question is in regards to the following problem:

  Suppose you are given a set $S$ of $n$ points in the plane. Let $R$ be a random subset of $S$ of size $r$ with all subsets of size $r$ equally likely. What is the expected number of points of $S$ that lie on the interior of the convex hull or $R$? I.e. What is $E[|S\cap \operatorname{int}(\mathcal{CH}(R))|]$?

I have been looking in Clarkson and Shor's Applications of Random Sampling in Computational Geometry, II, Mulmuley's chapter in the handbook of computational geometry, and related papers. As far as I understand it, these methods all apply to bounding the number of points of $S$ outside the convex hull, but do so by finding the expected sums of the sizes of conflict lists. For instance, the conflict list of an edge in the problem above is the number of points in $S$ that are beyond it, and the sum of the sizes of all conflict lists is $O(n)$. But because the same point may appear in $O(n)$ conflict lists itself, this doesn't seem to say anything about the number of points on the interior.

Any help in understanding the problem, or useful references is appreciated. Unfortunately, I have a sneaking suspicion that the answer is obvious, but find myself a bit stuck. Thanks.


texts: Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree

texts:
A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how many assignments (i.e., functions from the variables to $\{0, 1\}$) make $\Phi$ true. As this problem is #P-hard, I study it for restricted classes of DNF formulae.

The hypergraph of a DNF formula has as vertices the variables, and has one hyperedge per clause which contains precisely the variables of the clause. The requirement that I impose is that the hypergraph of the input DNF is a hypertree: in other words there is a tree $T$ on the variables such that each clause is a connected subtree of $T$.

Is anything known about the complexity of #SAT for monotone DNF formulae obeying this restriction? Is it still #P-hard, or does it become PTIME?

Depending on whether this is hard or not, I am also curious about other possible restrictions on the hypergraph, e.g., alpha-acyclicity, beta-acyclicity, or the strenghtening of the hypertree condition where each clause must be a connected path of the tree $T$ (I do not know a name for these hypergraphs).

Some remarks on the problem. I think it is the case that, if the size of the clauses is bounded by a constant, the problem can be solved in PTIME by writing an OBDD for the formula following $T$. However, if there is no bound on clause size, this approach doesn't seem to work, but on the other hand the constrained structure imposed by $T$ does not make it easy to encode arbitrary counting problems, so I don't know how to show hardness.

I am aware of works that study the complexity of #SAT under various constraints on the input formulae, such as this one for beta-acyclicity, but the definition here is for hypergraphs on an input CNF formula, and I didn't find anything relevant about DNF inputs.


texts: Designing a Transport network path suggestion tool

texts:
I am working on a suggestion system to passengers on transits to take.
The thing is we are formulating stations on a transport network (eg. bus transport) as nodes and route between spatially adjacent stations as edges. The
weights on edges being the time it takes to reach between stations.

We are in search of route, a person should take if he/she desires
to go from node A to node B. I am aware that I can use the shortest path
problem to find a shortest route. But the complication is that the
shortest route may not be the fastest route to the destination. This is because
on the shortest route one of the leg of the journey has very low bus frequency and thus may take longer.

Let me elaborate it further. What I mean is that say A--C--B is the shortest route  but the frequency of buses is hourly. But A--D--B is another route which
is longer that A--C--B but has more frequency say once in 10 minutes.
Thus in this case A--C--B is the desired route. It is quite clear that the standard shortest path may not give the desired result.

Can you suggest a solution to this problem? I was thinking may be
detect all unique cycles involving node A & B. And compute actually required
time (taking into account bus frequencies) on that route. But I am not
sure how to go about this.


texts:
Background

Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If there is no $2^{n^{o(1)}}$ factoring algorithm then this this is optimal [2]. Of course, on a quantum computer we know how to factor, so this lower bound does not help. Further, the optimal classical algorithm uses the Fourier spectrum of the function thus screaming "quantumize me!"

[1] N. Linial, Y. Mansour, and N. Nisan. [1993] "Constant depth circuits, Fourier transform, and learnability", Journal of the ACM 40(3):607-620.

[2] M. Kharitonov. [1993] "Cryptographic hardness of distribution-specific learning", Proceedings of ACM STOC'93, pp. 372-381.

In fact, 6 years ago, Scott Aaronson put the learnability of $AC^0$ as one of his Ten Semi-Grand Challanges for Quantum Computing Theory.

Question

My question is three-fold:

1) Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions?

2) Has there been any progress on the learnability of $AC^0$ in particular? (or the slightly more ambitious $TC^0$)

3) In regards to the learnability of $TC^0$, Aaronson comments: "then quantum computers would have an enormous advantage over classical computers in learning close-to-optimal weights for neural networks." Can somebody provide a reference on how weight updating for neural nets and $TC^0$ circuits relate? (apart from the fact that threshold gates look like sigmoid neurons) (This question was asked and answered already)


texts: What's the point of $\eta$-conversion in lambda calculus?

texts:
I think I'm not understanding it, but $\eta$-conversion looks to me as a $\beta$-conversion that does nothing, a special case of $\beta$-conversion where the result is just the term in the lambda abstraction because there is nothing to do, kind of a pointless $\beta$-conversion.

So maybe $\eta$-conversion is something really deep and different from this, but, if it is, I don't get it, and I hope you can help me with it.

(Thank you and sorry, I know this is part of the very basics in lambda calculus)


texts: What is/are the lower bounds for finding a something akin to complex residue?

texts:
Given a function $\sum_{i=-N}^N{c_i x^i}$:

$f(x) \equiv \sum_{i=-N}^N{c_i x^i}$ where $c_i$ is an integer; $0 \le c_i \le a$ for some $a$.

The constant $c_0$ is desired, and we start with only $f(x)$ and $N$.  $N$ is $\Theta(2^{b})$ for some $b$.

  Can you clarify?

First, we start with a closed form of a function.  The function itself is similar to a generating function, so that the function description is usually more concise than a list of all of its coefficients, yet it describes all of the coefficients.  Some examples are

$\frac{1-x^{100}}{1-x} = 1 + x + x^2 + ... + x^{99}$

$\frac{ 1 - (n+1)x^n + nx^{n+1} }{ (x-1)^2 } = 1 + 2x + 3x^2 + ... + (n+1)x^n$

The problem seems to be that this coefficient is in the middle of a list of positive and negative coefficients.  In the two examples above, the coefficient c_0 can be easily extracted.  However, this is not so when there are negative coefficients.  For example, take the functions above and divide by x^m to get a function that contains some negative coefficients.

  What is known about the general form of $f(x)$?

The function $f(x)$ is a rational function:

$f(x) = P(x)/Q(x)$

where $P(x)$ and $Q(x)$ are polynomials.

Here's a little insight into how $f(x)$ is calculated.
I use a standard rational function:

$g(x) = (x^s(x^t-1)) / ((x-1)(x^u+1))$

I then multiply $g(x)$ by $g(y)$, and $g(y)$ is of the same form of $g(x)$, but in another variable.  I then possibly subtract this from a function of one coefficients:

$h(xy) = (1-(x y)^v) / (1-x y)$

I then use another variable function similar to $g(x)$, say $g(z)$, and multiply again.  Possibly subtract again.  Repeat this until the function I want is constructed.  Then reassign variables like so (to either positive or negative exponents):

$y \mapsto \displaystyle x^{\pm 2^N}$

$z \mapsto \displaystyle (x^{\pm 2^N})*(x^{\pm 2^N})$

and so on.  This is how the function is created, without going into detail.

  How fast can this computation be performed?

So far, I've seen that Bruno Salvy's webpage hosts a "gfun" package that solves this in O(N).

I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better.  I imagine that a bounds related to the length of the function description may be possible...


texts: Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons

texts:
I have a set of $n$ convex polytopes of the form

$$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$

where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\mathcal{L}_k, \mathcal{L}_j)$$ there is a point of intersection other than the trivial solution $\beta = 0$. Additionally, I know that $C_i$ is such that each entry of $\beta$ must be greater than or equal to zero. What I want to know is whether this implies that there exists a nontrivial point of intersection of all $n$ polytopes, or if there is some counterexample?

Thanks!


texts: On status of Valiant's $NC^2=P^{\#P}$ provability program?

texts:
In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back.

What is the rationale (at least then) behind his $NC^2=P^{\#P}$ program (Valiant is a reputed researcher) which most researchers believe is false?
Is his program for proving $NC^2=P^{\#P}$ taken seriously and if so what is the status of his program?
Is this talk available any where?

I am aware of holographic alorithms. But typically  an inventor invents something because he believes in some vision and not the other way.


texts: Use of physical environment to obtain useful results

texts:
I dare to ask a broad layman question expecting a layman simple answer. I'm no scientist in any field.

Question: Does the following concept make sense or does it exist and actually being used? > Given some initial (digital) data, it would in some cases be possible AND more efficient to cast these "outside" of the digital computer (most probably in a form of some wave), letting it be altered through specifically fitted physical environment and receiving them back as digital data in order to solve some problem/obtain useful result rather than processing those initial data digitally by the software function. Time spent on creation of this "physical filter" (most likely not solid, e.g. magnetic field) should most probably be added to the overall processing time consumption for it to make sense. Also: it would be expected not to use this method to obtain very exact answers to exact problems, but rather to draw some useful data from some complex initial data. The filter would probably not be static, but could change according to required setup.

An illustrative example bellow (not actually feasible)

problem: Is value of x higher than any of the values in given very large set?

software solution: function iterating through each value in set and comparing value of x to it. When none is larger or equal when the cycle ends, x is higher than all, otherwise x is not larger than all and cycle can break early.

solution using physical filter: filter has the form of opaque columns of height that represent values in given set. Value of x is outputted in a form of a light ray at corresponding height "through" the filter. When no column is higher or equal, light is received by the sensor on other side.

  When not considering the time required to construct such filter, the solution to the problem using the filter should be much faster than software solution, no?

Hope the question is not too stupid or too irrelevant to this stack.


texts: Most significant bit of integer multiplication and binary decision diagrams

texts:
Let $x$ and $y$ two binary numbers with $n$ bits and $z = x \cdot y\ $ the binary number (length $2n$) of the product of $x$ and $y$. We want to compute the most siginifcant bit $z_{2n-1}$ of the product $z = z_{2n-1} \ldots z_0$.

In order to analyse the complexity of this function in the model of binary decision diagrams (in particular read-once branching programs) I try to look for some equivalent expressions for the case $z_{2n-1} = 1$. The first obvious thing is $z_{2n-1} = 1 \Leftrightarrow x \cdot y \geq 2^{2n-1}$ (here $x$ and $y$ are the corresponding integers to the binary numbers). I want to get an intuition what happens if I set some input bits constant. E.g. if I set the most significant input bit from $x$ and $y$ to 0 I get the constant 0 function. But bits with lower significance haven't such an influence on the result.

Are there any other equivalent expressions for the case $z_{2n-1} = 1$ which help more to see what happens if I fix some input bits? Are there any refined methods to compute the product of two binary numbers which can help? Or do you have some other approach to this problem?


texts: Generalizing linear interpolation to posets

texts:
Assume that I have an array $A$ of $n$ numerical values where some are known and some are unknown (with $A[0]$ and $A[n-1]$ assumed to be known). If I want to estimate an unknown value $A[i]$, a reasonable way is to perform linear interpolation: find the largest $j < i$ such that $A[j]$ is known, find the smallest $k > i$ such that $A[k]$ is known, and do a weighted average $A[j] := {k-i \over k-j}A[k] + {i-j \over k-j}A[j]$. In particular, this ensures that the following property (*) holds:

$$\text{if } A[j] \leq A[k] \text{ then } A[j] \leq A[i] \leq A[k]$$

Now, you can see an array as a totally ordered structure, and wonder about what would happen in the case of a partial order. Assume that I have a DAG $G = (V, E)$ of $n$ nodes where every node $v \in V$ has a numerical value $\mu(v)$ where some values are known and some are unknown (with the values of the roots and leaves assumed to be known). If I want to estimate some unknown $\mu(v)$, it seems that I should interpolate it out of the values of the closest ancestors and descendents of $v$ whose values are known. The question is: what should we do, exactly? Is there a generalization of linear interpolation in this setting?

[Here is a possible choice: for every couple $(u, w)$ of ancestors and descendents of $v$, perform linear interpolation along all the possible chains between $u$, $v$ and $w$ to get a value for $v$, and average all the values over all chains and ancestor-descendent pairs to get your final estimate. Is this the correct way to do things? Can this estimation be computed more efficiently than with this definition? (i.e., could we do it in linear time in the size of the neighborhood of $v$ under consideration, rather than in a quadratic way?). Do we still have some variant of property (*)? (note that, even if you assume monotonicity, i.e. for each ancestor-descendent couple $(u, w)$ you assume $\mu(u) \leq \mu(w)$, then the estimation $\mu(v)$ obtained by the previous process may still violate monotonicity, i.e. $\mu(v) > \mu(u)$ for some ancestor $u$ of $v$)]


texts:
Given an algebraic variaties of  n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?

And if there is, what is the computational complexity of the algorithm?


texts: Can constant ambiguity reduce the state complexity of a regular languages?

texts:
We say that NFA $M$ is Constantly Ambiguous if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths.

If automaton $M$ is constantly ambiguous for $k=1$, then $M$ is called Unambiguous FA (UFA).

Let $L$ be a regular language.

Can some constantly ambiguous automaton $M_c$ for $L$ be smaller than the smallest UFA that accepts $L$? How much smaller could it be?

Can Finitely ambiguous automaton be exponentially smaller than the smallest CFA for the same language?

It is known that there are Finitely ambiguous automatons (there exists $k$, such that every word is accepted by up to $k$ paths) which are exponentially smaller than the smallest UFA for the same language, but I haven't seen something about constant ambiguity.

Also, here's a related question I've posted here a few months ago.

EDIT:

Domotorp's answer shows that $CFA$ is polynomially reducible to $UFA$, but doesn't address the question of whether we can gain that polynomial space reduction by $CFA$s.

So the new question becomes: How much smaller (linearly/quadratically/etc.) can a $CFA$ be compared to the minimal $UFA$? for the same language?


texts: The quad-edge data structure (Delaunay/Voronoi)

texts:
2 questions for the computational geometers or algebraists:

I am just beginning to dive into computational geometry and I am loving it =)

I am attempting to read the famous article by Guibas and Stolfi called "Primitives for the manipulation of general subdivisions and the computation of Voronoi Diagrams" in order to implement a Delaunay triangulation algorithm. I am tempted to skip all the theoretical stuff and just read the description of their quad-edge data structure to save time. However, I think it may be worth it to understand all the math in the article if the structure is widely used, or just because it may be beautiful.

The math is a little to dense for me. I'm not completely ignorant on topology, but the description of their edge algebra requires knowledge of abstract algebra that I don't have.

My two questions are: What other applications of the quad-edge structure are there besides computing Delaunay/Voronoi? It seems like an extremely powerful tool.

The second question; What is an abstract algebra? It would be great if you could give me a reference to an introduction to abstract algebra, just enough so I can understand the section on their edge algebra.

Thank you!


texts: Digital steganography re-encoding resistance

texts: I'm curious to know if any papers exist on the ability of steganographically-altered image data to retain its integrity after it has been re-encoded into a different format (e.g., from PNG to JPEG). Is this an inherent trait in good steganography implementations, or is this an issue that needs to be treated separately?


texts: The only algorithm I have seen to compute a stable matching is the one by Gale an Shapley. Is there any other algorithm to compute a stable matching?


texts: Is the decidability of a language decidable?

texts:
Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language?

Comments + answer say trivially the answer is yes; however, I'm wondering here would it be possible without the use of excluded middle to construct such a machine.


texts: Seeking for a game for modelling a problem using game thoery

texts:
I have a problem which I want to formulate it as a game, using game theory. In this problem there is several agents, we can consider the agents as the employees of different offices, these agents have some information about the clients and these information are updates and increases over time. the problem is persuading the agents to present their information to a central office over time. the problem have a continous nature. I am seeking for a game to model this problem using game theory. May you please tell me which kind of games is sufficient for this problem?

Best Regards


texts: What's a good news source for Computer Science?

texts: If I want to be aware of the lastest discoveries in the Computer Science area, what's a good source of information? (preferable online)


texts: Canonisation of boolean matrices under row and column permutations

texts:
Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows:

$A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, Q\in\{0,1\}^{m\times m}$, so that $B=QAP$

In other words two matrices are equivalent, if they are equal up to permutation of rows and columns.

A canonisation function for $\sim$ is any function $N$ on the set of all boolean matrices with $N(A)\in \{0,1\}^{m\times n}$ for all $m,n\geq 1$ and $A\in \{0,1\}^{m\times n}$ with the following two properties:

$N(A)\sim A$ for every $A$
$A\sim B \Leftrightarrow N(A)=N(B)$ for all $A,B\in\{0,1\}^{m\times n}$

Now i want to find a canonisation function for $\sim$ that is most efficiently computable.
One possible canonisation function is the function $\mathrm{MaxLex}$ which maps every matrix $A$ to the lexicographically largest $B$ that is equivalent to $A$.

For this i first define a linear order on bitvectors as follows:
For $b,c\in\{0,1\}^k$

$b<_{llex} c$ iff: the number of ones in $c$ is larger than in $b$ or ($b$ and $c$ have the same number of ones and $b(i)>c(i)$ for the first index $i$ with $b(i)\neq c(i)$)

Then a lexicographic order $<_{lex}$ on matrices of equal dimension is defined as follows:

$A<_{lex}B$ iff $w_A<_{llex}w_B$

where
$w_X=X(1,-)X(2,-)\ldots X(m,-)\in\{0,1\}^{mn}$ denotes the bit vector that results from the concatenation of the rows $X(i,-)$ of $X$.

Then $\mathrm{MaxLex}(A):=\max_{<_{lex}} \{ B : A\sim B\}$

I have found a simple recursive algorithm that computes $\mathrm{MaxLex}$, which has however a worst case runtime of $\mathcal{O}(m!)$.

Now my questions are:

Is there a more efficient algorithm that computes $\mathrm{MaxLex}$ than my $\mathcal{O}(m!)$ algorithm?
Is there a polynomial time algorithm that computes  $\mathrm{MaxLex}$
Is there a canonisation function for $\sim$ that is computable in polynomial time?
Is anything known about the computational complexity of this problem?

I am thankful for any tips, pointers or comments. I have already googled this problem but couldn't find anything. The only thing i found which resembles this is the decision problem of whether a boolean matrix is equivalent to a triangle matrix, which according to this posting is in NP, but not known to be NP-hard nor in P.


texts:
I want to know if the decidability of equality of two decidable proofs of the same proposition can be proved without any additional axioms in Calculus of Inductive Constructions.

Specifically, I want to know if this is true without any additional axioms in Coq.

$$\forall P: \texttt{Prop}, P \vee \neg P \Rightarrow
(\forall p_1 : P, \forall p_2: P, \{p_1 = p_2\} \vee \{p_1 \neq p_2\})
$$

Thanks!

Edited to correct the error:
Edit 2 to make Prop more explicit


texts:
In 1996, a long-standing open problem was solved by a computer; namely, that Robbins algebra and Boolean algebra are the same. The proof was found by an automated theorem prover.

Moreover, the known proof of Four color theorem contains computer-generated components.

The aim of this question is to list proofs that are (completely or partially) found by computer (whether the only known proof or the one discovered for the first time).


texts: Deciding whether a context-free language is regular

texts:
Does anyone know whether the following decision problem is decidable:

Given a context-free language $L$, is $L$ regular?

Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone know an algorithm that takes as input a context-free grammar $G$ and outputs an equivalent regular grammar $G'$, i.e. $L(G) = L(G')$, if $L(G)$ is regular?


texts:
During research, I hit a set theoretic claim that I could neither proof nor disproof.

Let $S_1,S_2,S_3$ be three set systems over the same finite universe $U$ such that

$S_1,S_2,S_3$ are closed w.r.t. $\cap$ and $\cup$ and

for each pair $u,v \in U$, there are two disjoint sets $X \in S_i, Y \in S_j$, $i,j \in \{1,2,3\}$, $i \neq j$, such that $u \in X$ and $v \in Y$.

Then, there is a partition of $U$ into at most three sets, each from a different set system.


texts: Completeness of realizability semantics for higher-order type theory

texts:
In this answer I mention a paper by Geuvers in which he describes a class of models for a type theory $\lambda P_2$ which is a sub-system of the CoC and roughly corresponds to 2nd order predicate logic.

He goes on to describe a class of realizability models, which are based on Weakly Extensional Combinatory Algebras (WECAs). In a couple of lines, the model involves a WECA $\cal A$ and a set ${\cal P}\subset {\mathscr P}({\cal A})$, closed under arbitrary intersections and closed under the realizability product:
$$\prod_{t\in X}F(t):= \{a\in{\cal A}\mid \forall t\in X,\ a\cdot t\in F(t)\} $$
where $F:X\rightarrow {\cal A}$ is an arbitrary function. One can then define the interpretation $[\![\_]\!]$ from types in $\lambda P_2$ to elements of $\cal P$:

$$[\![\alpha]\!]_{\xi\rho}:= \xi(\alpha)$$
$$[\![\Pi\alpha.\tau]\!]_{\xi\rho}:=\bigcap_{A\in{\cal P}}[\![\tau]\!]_{\xi[\alpha:=A]\rho} $$
$$[\![\Pi x:\sigma.\tau]\!]_{\xi\rho}:= \prod_{a\in[\![\sigma]\!]}[\![\tau]\!]_{\xi\rho[x:=a]}$$
$$[\![P\ t]\!]_{\xi\rho}:= [\![P]\!]_{\xi\rho}((\!|t|\!)_{\xi\rho})$$
$$[\![\lambda x:\sigma. P]\!]_{\xi\rho}:= a\in[\![\sigma]\!] \mapsto [\![P]\!]_{\xi\rho[x:=a]}$$

Where $\xi$ and $\rho$ are appropriate valuations, and $(\!|\_|\!)$ is the interpretation of terms into elements of the WECA $\cal A$. I'm omitting a fair number of details, e.g. the interpretation is actually over type constructors and not only types.

My question is pretty straightforward: is this class of models complete for $\lambda P_2$? Is the "obvious" generalization complete for CoC? For CIC? Are there any references for this?

The interpretation of the "large" product is restricted to be intersections, which may make it too weak a notion of models to be complete, but the choice of WECAs seems to make it a powerful notion of models.

In Pitts' paper Polymorphism is Set-Theoretic, Constructively, it is shown that every model of system $F$ can be embedded in a topos, and so a rather general notion of topos models is indeed complete for system $F$.

So my follow up questions are:
Do these topos models generalize the class of realizability models described above? Does the theorem generalize to $\lambda P_2$? I suspect the answer is yes, but I'd kind of like to see the details worked out.

Edit: I've asked both Herman and Andrew for insights, and they were kind enough to both reply. I'll summarize their response.

Herman notes that there is completeness for 2nd order predicate logic, in which it is crucial to allow subsets of the full powerset for the interpretation of 2nd order quantifiers. It is an open question about whether $\lambda P_2$ is conservative over 2nd order predicate logic, and this seems to be a related question. He also refers to Geuvers - Extending Models of Second Order Predicate Logic to Models of Second Order Dependent Type Theory, CSL 1996.

Andrew notes that the completeness results involving topos models seem very close to the syntax as opposed to the set theoretic ones, and so is skeptical that the results can be extended to this setting without significant effort (he is agnostic about the result itself though!).


texts: Finding the size $k$ subset in a metric space that maximizes the min distance between elements

texts:
I have a metric space $(X,d)$ and I'd like to find a subset of size k of far away elements.

We can cast this as the following optimization problem $\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, i,j \in S} d(i,j))$

For the case $k = 2$, there is a well known 2-approximation, which picks an arbitrary point and finds the point that is furthest from it. There is a natural extension of this idea, which at the $m$th stage, picks the point that maximizes the min distance to each of the $m-1$ previously chosen points. This uses $O(k^2|X|)$ time.

Questions:

This seems like a natural enough problem that it's been studied -- what are the keywords to this problem?
Does this greedy extension work well? What are some other heuristics to try?
For fixed $k$, is there a constant factor approximation with query size $O(|X|)$? Can one obtain a decent approximation in better than $O(k^2|X|^k)$ time?

Similar objective functions, such as $\prod_{i \not = j, i,j \in S} d(i,j) $, are also interesting.


texts:
The concept of hysteresis seems well suited to describe and distinguish finite automata:

  "Hysteresis is the dependence of the state of a system on its history." (Wikipedia, Hysteresis)

  "[The state of a finite state machine] is determined by its history.
  (Minsky, Computation)

What I am looking for is a definition of hysteresis strength $H$ of finite automata distinguishing finite automata with a stronger dependence on history from those with a weaker one.

------------------ edited -----------------------

Thanks to domotorp's hint, I found that the Nerode index is a good such measure: finite automata (equivalent to finite regular expressions) have a finite Nerode index, and the smaller the Nerode index is, the less "memory" (or hysteresis strength) the automaton has.

But: The Nerode index is defined rather abstractly, as the number of equivalence classes of a language with respect to the Nerode equivalence relation.

What I would like to know:

  How is the Nerode index related to the structure/complexity/size of a regular expression?
  How is the Nerode index related to the structure/complexity/size of an equivalent state diagram?

Is there more to say than:

The lesser complex the regular expression describing an automaton is, the
smaller its Nerode index is.
The Nerode index is correlated to the number of (accessible) states.


texts: Derandomization of Polynomial Identity Testing

texts:
There are some theorems that state $P = BPP$ if some condition is satisfied. For example, a theorem of Impagliazzo and Wigderson states tha $P=BPP$ unless $DTIME(2^{O(n)})$ has sub-exponential circuits for infinitely many input lengths.

Hence there is a polynomial time deterministic algorithm thet solves the Polynomial Identity Testing problem, that works correctly if this condition ($DTIME (2^{O(n)})$ does not have sub-exponential circuits) is satisfied.

Can one state this algorithm explicitly?


texts: Converting a pictorial representation of a directed graph to a adjacency matrix

texts:
I am not sure if there is a better forum to ask this question, so I will try here.

Consider an image, say in .jpeg format, representing a directed graph, with nodes. Is there an algorithm, be it a machine learning/image processing/computer vision algorithm, that can read and process this image, and generate a potential adjacency matrix representation of this graph? What if the graph isn't planar, i.e. edges can intersect.

The graph itself could be unshaded circles representing nodes, with an arrow representing an edge from one node to another.

Obviously, as it is a supervised learning problem, some training data needs to be provided, but if this can be done, how would I go about doing it? If someone can point me to research in this problem, I'd appreciate it, as my search seems to have been to no avail.


texts: Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

texts:
As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given the time of day, because it's not relevant is it?
I have always thought of the C-T thesis as a statement, specifically a statement in theoretical computer science. A statement that reads, "There exists no computation model capable of recognising languages that a Turing Machine cannot". Even that is a bit messy for me. Is there a formal definition for a computation model? Finite alphabet, finite states, what exactly are we talking about here?
Whether provable or not is another story, but it's a statement that evaluates to some logical value or another. Some people say that the C-T is a statement, some actually say it's not. I have no authority in this, so I'm left as confused as ever.
And if it's not a statement, then great! It's not a problem anymore. At least from the mathematical side of things.
I have a couple of what I think are misconceptions. I've taken a look at the Chomsky Hierarchy of grammars, and at the very top lie all the so called Unrestricted Grammars which have been proven to be equally expressive as Turing Machines, apparently. Now I don't even know the formal definition for expressivity, all I have is an intuitive understanding. CFGs are more "expressive" than DFAs and CSGs are more "expressive" than CFGs etc etc, because they can recognise all the languages the prior construction can and more. Is this actually the commonly accepted definition?
Now Unrestricted Grammars specifically, allow production rules of the form $\alpha \to \beta$ where $\alpha$ is any non-empty string and $\beta$ is any string. Hence, unrestricted. How on earth could a computational model compete with something that is literally unrestricted? It makes me think of the C-T thesis as trivial, "of course" it's true.
This left me even more confused: What would it mean to disprove Church-Turing thesis?
The accepted answer to this question starts off with:

The Church-Turing thesis has been proved for all practical purposes.

Why is practicality suddenly worth anything in theoretical computer science?
Are there like two interpretations or more of the C-T thesis, one for "practical purposes" and one for "mathematics"?


texts: The number of integral points in a polytope

texts:
Suppose we define a polytope with
$$
\mathbf{Ax} \leq  \mathbf{b}
$$
What is the best way to find/approximate the number of the integral points in the polytope?
Update: how hard is the complexity of this problem?

Update: dimension of the space is $n$ and is a variable in the problem.


texts:
Let $A$ be an $n \times n$-matrix, and let $1 \leq k \leq n$. Which algorithms do exist, or what is know about the complexity of computing determinants of all $k \times k$-minors?

The naive algorithm has complexity $\Theta( {n \choose k}^2 k! )$. If we apply Gaussian elemination for each minor $\Theta( {n \choose k}^2 k^3 )$. Of course, there is a dynamic programming approach, too, but I am not firm enough to compute its complexity.

I am also interested whether there is a lower bound actually known.


texts: Landauer's principle internals - how it works

texts:
I attached a picture, where the energy dissipation (entropy increase) on information erasure is explained. Is the explanation correct?

"RESTORE TO ONE" - is it correct to identify the operation as "information erasure"? It looks like a negation, not like "information erasure".
I would say that the erasurement would be performed, when the "ball" (the black dot near "0" in the picture) would be returned to the meta-stable point between 0 and 1.
Maybe the intention of the author was to show, that "negation" has "erasurement" embedded in it? Then, he states that "computing depends on information erasure" - this statement is too strong? - we have reversible computation that do not erase information, correct?
The picture and point 2. (above) seem to be a very good metaphore of Landauer's principle. Does it match Landauer's principle closely, or maybe even perfectly - or is it just a picture to help only conceptually understand the principle?

(PS. A better title is welcomed..)


texts: Complement of Multi-colored Clique with an extra condition

texts:
In the problem Multi-colored clique, we ask for a $k$-clique of the input graph $G$ where $G$ is guaranteed to be $k$-colorable. In the complement problem Independent Set given Clique Partition, we ask for a $k$-independent set of the input graph which admits a $k$-clique partition.
Independent Set given Clique Partition with Simple Modules
Instance: A graph $G$, a +ve integer $k$, a partition of vertex set of $G$ into cliques $V_1,V_2,\dots,V_k$
$\qquad \quad\,$ such that for every pair of colors $i$ and $j$, $V_i\cup V_j$ induce a clique plus isolated vertices
$\qquad \quad\,$ (that is, if $x\in V_i$ has a neighbor in $V_j$, and $y\in V_j$ has a neighbor in $V_i$,
$\qquad \quad\,$ then $x$ and $y$ are neighbors).
Question: Is there an indepedent set of size $k$ in $G\,?$
(NB: "clique plus isolated vertices" refer to the disjoint union of a clique and a set of isolated vertices)
Is this problem NP-hard?  (or even W[1]-hard?)
I have a feeling that it is indeed NP-hard, but I am unable to prove it.
Or, is this problem in P?
If it is in P, an interesting combinatorial problem will also be in P.
Is this or any related problem (other than MultiColoredClique) studied in the literature? Is the condition ''each color pair induce biclique+isolated vertices'', or something similar considered in a study?
Note: I asked the following question first: Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices. But, my actual interest is in the problem described above.


texts: Are there any schools with researchers interested in cellular automata?

texts:
I have been working on an independant project focusing on cellular automata and was wondering if this might be something that I could continue on in graduate school somewhere. I've seen some mathematics departments with symbolic dynamics as well as a few CS departments with researchers interested in CA. The list is small though. If anyone knows which departments to look at and/or any specific faculty/programs to look at then I would greatly appreciate it.

Also, my project is sort of taking on a "mathematical" flavor and I was wondering if it would be better to look into mathematics over computer science departments, or is it generally pretty easy to do this type of thing in either.


texts:
The oracles that are used in relativized collapses or separations of complexity classes rarely represent $natural$ algorithmic problems. They are typically constructed "artificially" with techniques like diagonalization, for the sole purpose of achieving the relativized collapse or separation. A notable exception is that for any ${\bf PSPACE}$-complete set $L$ it holds that ${\bf P}^L={\bf NP}^L$. This indeed leads to "natural relativized worlds," since there are  ${\bf PSPACE}$-complete languages that correspond to  natural algorithmic tasks. Generally, I am looking for such examples, where the oracle represents a natural problem. (And, of course, it is not trivially implied by the above example).

In particular, is there any such known "natural relativized world" in which ${\bf P}$ and ${\bf NP}$ are separated?

$Note:$ A random oracle here does not count as natural, because it does not represent a natural algorithmic problem. It rather represents that a statement holds for almost all oracles, regardless to their "naturality."


texts: Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the Vertices

texts:
Consider the standard minimum-cost flow problem presented here. I would like to add an additional set of constraints on the total incoming/outgoing flow for each vertex (excluding the source $s$ and the target $t$) as follows:
$$\sum\limits_{w \in V } {f({v_i},w) = \sum\limits_{w \in V} {f(w,{v_i}) = } {r_i}} ,\forall {v_i} \in V - \{ s,t\},$$
where $r_i$ is called vertex $v_i$ flow requirement (is there a standard term for it?). Please note that this problem is single-commodity and it is different from the multi-commodity flow problem.

Moreover, consider that all the capacities, costs, flows, and requirements are non-negative integers. Is there a well-known algorithm to solve this problem in polynomial time? If this is an NP-Complete problem, what's the fastest known algorithm and the approximation method to solve it?


texts: What is the proof that visibility graphs can be used to compute the shortest path?

texts:
I am trying to understand what the proof is that constructing a visibility graph and searching on can give you the shortest path between two points, avoiding a set of convex polygons. I am trying justify that using the visibility graph algorithm on spherical polygons transformed with the Gnomonic Projection to a linear plane will result in the shortest path, using great circle distance, between two points on the sphere's circle. To do so, I need to understand what assumptions the visibility graph needs to be valid, so I can see if those are still true for this mapping.

On page 612 of Discrete and Computation Geometry, Mitchell states:

  It is easy to show that an locally optimal s-t path must on the
  visibility graph VG(P)

Referring to the fact that a shortest path between two points, navigating around polygonal obstacles, can be found by creating a visibility graph and then searching that visibility graph using an algorithm like A*.

He however, does not explicitly state how we know that this path is in the visibility graph.

The paper most people cite for the original Visibility Graph algorithm is "An Algorithm for Planning Collision-Free Paths
Among Polyhedral Obstacle" from 1979, stating:

  The shortest collision-free path from S to G on the plane is the
  shortest path in the VGRAPH from the node corresponding to S to that
  corresponding to G when the euclidean metric is used on the links. We
  will call this method for finding collision-free paths for a point by
  finding the shortest path in a visibility graph the VGRAPH algorithm.
  This method was used for navigating SHAKEY [8], an early robot
  vehicle, and is also described in some detail in Ignat'yev [5].

They however, again fail to say how they know this is true. The SHAKEY paper also does not mention any proof.

Now in Chapter 15 of Computational Geometry: Algorithms and Applications, titled "Visibility Graphs Finding the Shortest Route", they give this proof for why they shortest path should consist entirely of endpoints of the obstacles, implying that it will be in the visibility graph:

  Lemma 15.1 Any shortest path between pstart and pgoal among a set S of
  disjoint polygonal obstacles is a polygonal path whose inner vertices
  are vertices of S.

  Proof. Suppose for a contradiction that a shortest
  path τ is not polygonal. Since the obstacles are polygonal, this means
  there is a point p on τ that lies in the interior of the free space
  with the property that no line segment containing p is contained in τ.
  Since p is in the interior of the free space, there is a disc of
  positive radius centered at p that is completely contained in the free
  space. But then the part of τ inside the disc, which is not a straight
  line segment, can be shortened by replacing it with the segment
  connecting the point where it enters the disc to the point where it
  leaves the disc. This contradicts the optimality of τ, since any
  shortest path must be locally shortest, that is, any subpath
  connecting points q and r on the path must be the shortest path from q
  to r. Now consider a vertex v of τ. It cannot lie in the interior of
  the free space: then there would be a disc centered at p that is
  completely in the free space, and we could replace the subpath of τ
  inside the disc— which turns at v—by a straight line segment which is
  shorter. Similarly, v cannot lie in the relative interior of an
  obstacle edge: then there would be a disc centered at v such that half
  of the disc is contained in the free space, which again implies that
  we can replace the subpath inside the disc with a straight line
  segment. The only possibility left is that v is an obstacle vertex.

They however, don't give a citation for this proof. Is there a previous version of this proof, or is this the original?

Are there other ways to writing this proof?


texts:
I need a reference for CTL* logic (preferably easy to understand).

I have gathered some disperse information regarding temporal and CTL logic but I need a more orderly coverage. A chapter of the multi-agent systems book I read depends on this subject and I am stuck.


texts:
Is it possible to type a variable-argument function?

EDIT: like those defined in Scheme.


texts: Is it possible to type Ackermann function with (stratified variant of) System F?

texts:
I was surprised to find no open-source implementation of Ackermann function in pure System F as an illustrative example. I finally managed to implement it myself in Haskell using Church encoding:

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE ImpredicativeTypes #-}

type Nat = forall a . (a -> a) -> (a -> a)

succ :: Nat -> Nat
succ n = \s z -> n s (s z)

c0 :: Nat
c1 :: Nat

c0 = \_s z -> z
c1 = succ c0

exp :: Nat -> Nat -> Nat
exp = \n m -> n m

tetr :: Nat -> Nat -> Nat
tetr k n = n @Nat (\x -> x k) c1

iter :: (Nat -> Nat) -> (Nat -> Nat)
iter f n = (n @Nat) f c1

ack :: Nat -> Nat -> Nat
ack = \m -> (m @(Nat -> Nat)) iter succ

You can notice a variant of tetration on the way.

Can Ackermann function (and tetration) be defined as a pure lambda term without inductive types in a predicative system?

For instance in Agda with level polymorphism?

If not, what other type-theory tools apart from inductive types, can help us define non-primitive-recursive functions?


texts: What is the largest gap between rank and approximate rank?

texts: We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication complexity. The largest gap between deterministic communication complexity and randomized communication complexity is exponential. So what about the gap between rank and approximate rank of a boolean matrix?


texts: Problem conditions to use Laplacian solvers

texts:
I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense.
Suppose that we want to solve Ax=b, where matrix A is not a Laplacian matrix. Under what condition on A and b, we can solve Ax=b using Laplacian solvers?
P.S. Introducing a good reference will be helpful too.


texts: "Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

texts:
Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you find it worthy of archiving.

The paper appears to be my first interesting result ... ever. I'm totally new to archiving/publishing. And, relative to others, I am rather green in the logical disciplines. I produced this paper on my own; I am not studying at any institution.

If you do find it worthy of arXiv.org, and if you do have endorser privileges for Computer Science, would you be willing to endorse me? My account name is "JakeT".

I am hoping that others will find this interesting. I do.


texts: Viola's Reduction of 3XOR to listing triangles

texts:
Apparently this was due to Pătraşcu, but in this report on the ECCC server, Viola states that 3XOR can be reduced to listing triangles.

  Assume that given a graph in adjacency list format, with $m$ edges, $z$ triangles, $O(m)$ nodes, one can list $\min\{z,m\}$ triangles in time $m^{(4/3)-\varepsilon}$ for $\epsilon>0$ constant. Then one can solve 3XOR on a set of size $n$ in time $n^{2-\epsilon'}$ with error $1\%$ for a constant $\epsilon'>0.$

My question is the reverse. If one were to have an efficient algorithm for 3XOR, what could one say about efficiently listing triangles?


texts:
In a recent thread on the Agda mailing list, the
question of $\eta$ laws popped up, in which Peter Hancock made thought-provoking remark.

My understanding is that $\eta$ laws come with negative
types, ie. connectives which introduction rules are invertible. To disable $\eta$ for functions, Hank suggests using a custom-made eliminator, funsplit, instead of the usual application rule. I would like to understand Hank's remark in terms of polarities.

For example, there are two presentations $\Sigma$-types. There is the
traditional Martin-Löf split eliminator, in a positive style:

$$
\begin{array}{l}
\Gamma \vdash f : (a : A)(b : B\: a) \to C (a , b) \\
\Gamma \vdash p : \Sigma a : A. B \\
\hline \\
\Gamma \vdash \mathrm{split}\: f\: p : C\: p
\end{array}
$$

And there is the negative version:

$$
\begin{array}{l}
\Gamma \vdash p : \Sigma a : A. B \\
\hline \\
\Gamma \vdash \pi_0\: p : A
\end{array}
\qquad
\begin{array}{l}
\Gamma \vdash p : \Sigma a : A. B \\
\hline \\
\Gamma \vdash \pi_1\: p : B[\pi_0\: p / a]
\end{array}
$$

This latter presentation makes it easy to obtain $\eta$ for pairs,
ie. $(\pi_0 p , \pi_1 p) == p$ for any pair $p$ (where == stands for the definitional equality). In terms of provability, this difference does not matter: intuitionistically, you can implement projections with split, or the
other way around.

Now, $\Pi$-types are usually (and uncontroversially, I believe) taken negatively:

$$
\begin{array}{l}
\Gamma \vdash f : \Pi a : A. B \\
\Gamma \vdash s : A \\
\hline \\
\Gamma \vdash f s : B[s / a]
\end{array}
$$

Which gives us $\eta$ for functions: $\lambda x. f x == f$.

However, in that mail, Hank recalls
the funsplit eliminator (Programming in ML type theory, [http://www.cse.chalmers.se/research/group/logic/book/], p.56). It is
described in the logical framework by:

$$
\begin{array}{l}
f \in \Pi(A, B) \\
C(v)\: Set [v \in \Pi(A, B)] \\
d(y) \in C(\lambda(y)) [y(x) \in B(x) [x \in A]] \\
\hline \\
\mathrm{funsplit}(f, d) \in C(f)
\end{array}
$$

Interestingly, Nordstrom et al. motivate this definition by saying that
"[this] alternative non-canonical form is based on the principle of
structural induction". There is a strong smell of positivity to this statement: functions would be 'defined' by their constructor, $\lambda$.

However, I cannot quite nail down a satisfactory presentation of that
rule in natural deduction (or, even better, sequent calculus). The
(ab)use of the logical framework to introduce $y$ seems crucial here.

So, is funsplit a positive presentation of $\Pi$-types? Do we also have something similar in the
(non dependent) sequent calculus? What would it look like?

How common/curious is that for the proof theorists in the field?


texts:
Probably the most common application of linear types in PL is to use them to give languages which control aliasing (i.e., a linear value has a single pointer to it, more or less).

But there's a slight mismatch between this usage and typical denotational models of linear logic. IIRC, Benton showed that if a Cartesian closed category has a strong commutative monad, then its category of algebras will be symmetric monoidal closed (ie, a model of linear logic). But this theorem doesn't apply to the alias-control usage, since the state monad is not commutative. And indeed, in the past few years Simpson and his coworkers have given calculi for general strong monads, which are not term calculi for linear logic.

So my question is, what is the denotational semantics of linear languages with state? Is there a non-degenerate (ie, tensor is not a Cartesian product) symmetric monoidal closed category in which allocation, reading, and linear update can be modeled?


texts: Do algorithms for solving parity games ignore other possible strategies for player V after finding one?

texts: Solving parity games (from a "start" node) relies on the existence of a history-free winning strategy for player 0 (V) or 1 (R). Whether there is more than one such strategy is probably never discovered, is it? Are there algorithms to keep searching even after discovering one appropriate strategy, i.e. searching for more than one (say all possible) strategies?


texts: Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)?

texts:
In online-setting, we usually allow exponential time to think and come up with a strategy. On the other hand, in offline-setting, we might care about solving a particular problem optimally, or as good as possible, in polynomial time.

Therefore, there is a chance that for some problems, we can actually come up with a strategy that gives us a competitive ratio that is better than best offline-approximation.

These problems could be crucial to study to obtain some insight understanding on online algorithms. Please let me know if you know of some examples.

Thanks.


texts: Applications of association schemes to complexity theory and other TCS

texts:
An association scheme is defined as a pair $(V, R_0,R_1, \ldots,R_{n+1})$ of a set $V$ and relations $R_i$ on $V$ such that

$(x,y) \in R_i$ implies $(y,x) \in R_i$ for all $x, y \in V$.

$R_0 = \{ (x,x) \mid x \in V \}$

If $(x,y) \in R_k$, the number of $z \in V$ such that $(x,z) \in R_i$ and $(y,z) \in R_j$ is a constant $c_{ijk}$ depending on $i$, $j$ and $k$, but not on the choice of $x$ or $y$.

An example of the application of the theory of association schemes to complexity theory is the following result of Evdomikov from 1994:

Under the Generalized Riemann Hypothesis, the irreducible factors of a degree $n$ polynomial over an explicitly given finite field of order $q$ can be found in time $(n^{\log n} \log q)^{O(1)}$.

So... question(s):

Are there other, more recent applications of association schemes to complexity theory, or other TCS?
What is the current state of the art in factoring algorithms of polynomials over finite fields?

Thanks in advance.  I'll be offline for a day or two, I'm afraid.  If there are issues with this question, I'll address them within 72 hours.


texts: Throwing Balls into Bins, estimate a lowerbound of its probability

texts:
This is not a homework, though it looks like. Any reference is welcome. :-)

Scenario: There are $n$ different balls and $n$ different bins (labled from 1 to $n$, from left to right). Each ball is thrown independently and uniformly into bins. Let $f(i)$ be the number of balls in the $i$~th bin. Let $E_i$ denote the following event.

  For each $j\le i$, $\sum_{k\le j}{f(k)} \le j-1$

That is, the first $j$ bins (the most left $j$ bins) contains less than $j$ balls, for each $j\le i$.

Question: Estimate $\sum_{i<n}{Pr(E_i)}$, in terms of $n$? When $n$ goes infinity. A lowerbound is preferred. I do not think an easily calculated formula exisit.

Example: $\lim\limits_{n\to\infty}{Pr(E_1)}=\lim\limits_{n\to\infty}{(\frac{n-1}{n})^n}=\frac{1}{e}$.  Note $Pr(E_n)=0$.

My guess: I guess $\sum_{i<n}{Pr(E_i)}=\ln n$, when $n$ goes infinity. I considered the first $\ln n$ items in the summation.


texts: Unique Identifier Creation and Invalidation

texts:
A colleague of mine recently interviewed for a software engineering job, and he was given a problem regarding unique identifier creation and testing for validation.

So, the problem is: if a generated  unique-identifier, let's say an order id provided online by an ecommerce site, is provided to a customer, and when the customer attempts to lookup the order, they have inadvertently transposed two characters, how to quickly test that the id is invalid, and how to create an id such that the transposition of two characters does not represent another valid id.

I want to know what class of problem is this (not in the complexity sense but categorically) and what are general methods that attempt to solve it. Looking for variations on the theme of unique identifier and invalidation on google has not produced interesting results. I am hoping someone here might lead me in the right direction to learn more about this kind of problem.

I hope I have found the right forum for posing the question, and apologies if I have not.


texts:
Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or things like that.

The only problem that comes to my mind is the DFA-INTERSECTION-NONEMPTINESS for unary automata. Given $k$ deterministic automata, this problem is to decide if they accept some common word. In this generality the problem is PSPACE-complete, but for unary automata it is NP-complete.

But beside from that, no other decision problem from the realm of finite automata theory come to my mind. So do you know any?


texts: The curve used in Parvaresh-Vardy decoding

texts:
Consider the Parvaresh-Vardy list decoder.

As I understand it, the idea is to decide on a curve over an extension field of the form $(f,f^h mod E, f^{h^2} mod E,\dots)$ and then evaluate each of these field elements (interpreted as univariate polynomials over a base field) on all the elements of the base field.
This was so that on interpolating to get a multivariate polynomial $Q(x,y_1,y_2,\dots)$, we have a root fining step comprising simply solving for the points lying on $Q=0$ and the curve.

An important consideration here was that $Q$ (the curve) not be identically zero as a polynomial, or that the curve not lie on the hypersurface defined by $Q=0$. This is ensured by taking $Q$ of smallest degree and not divisible by $E$, and by taking the exponent h to be large enough. Basically we adjust degrees of $Q$ and the curve to ensure that the curve does not lie on the surface.

My question is this:
Is there any significance to the choice of the Parvaresh Vardy curve as defined, beyond this degree requirement to ensure the curve isn't contained in the hyperplane?
For instance, could we choose the curve to be simpler, say of the form $(f,f^2 mod E, f^3 mod E,\dots)$? In this case, lets say we take $Q$ to be linear in the $y_i$'s (as used in linear-algebraic list-decoding of folded codes, say) so that the function applied on the curve , $Q(f,f^2,f^3,f^4,\dots)$, cannot be identically zero.

Everywhere it is mentioned that the tuple of functions is "carefully chosen" to ensure the method goes through, but I am unable to see what exactly is the motivation for this particular choice of curve.
This method is also used in the expander construction of Guruswami-Umans-Vadhan. Also, in a subsequent paper by Ta-Shma-Umans, another curve is used, but that curve too is similar to the Parvaresh-Vardy curve, but using linear combinations of the functions used in the former.


texts: Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem?

texts:
Possible Duplicate:
  Implications of unprovability of $P\neq NP$

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


texts:
Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion.

Is it possible to use a Decision problem in Knot Theory such as Knot recognition and make it into a proof of work function? Also has anyone done this before? Also, when we have this Proof of Work function will it be more useful than what is being currently computed?


texts: About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube

texts:
Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$ variable polynomial $\sum_{(i,j)\in E} \frac{ (x_i - x_j)^2 }{4}$ over the hypercube $\{ -1, 1\}^n$.

Is Max-CUT really special or is there always a reduction from a target NP-complete question to Max-CUT so that the optimization version of the target question can also be written as trying to optimize some polynomial over the hypercube? Do we know how to systematically get these special reductions or do they provably not exist or its just that we still don't know?

At some level all NP-complete questions are "equivalent" (sure they have variously different approximation hardness properties!) but it seems intuitively a bit unobvious that the optimization versions of each of them can't be written in this form though one of them can trivially be!

Is it possible that the different approximation hardness behaviour of the different NP-complete problems is somehow related to this issue of their optimization versions not having an uniform representation as polynomials (one for each) to be optimized over the hypercube?


texts: Questions about Farhi's pre-Adiabatic paper

texts:
I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation.

I guess I understand most of the math and physics but I am struggling with the intuitions used throughout the paper. Here are my questions.

Introduction of $|r\rangle$ on page 3:
I understand that $|r\rangle$ and $|w\rangle$ are orthonormal. But I don't see why the authors introduced this state.

Use of Norm in equation 17 on page 4:
The equation is as follows.
$$\sum_w |||\Psi_w, t\rangle - |\Psi, t\rangle||^2 \ge N \varepsilon$$
There are more than one kind of norms. What kind of norm are we talking about here? Why? What is the physical significance of this quantity in this context?


texts: Theories which characterize classes of computational complexity

texts:
When reading the paper "An applicative theory for FPH" you can encounter the following passage:

Considering theories which characterize classes of computational complexity, there are three different approaches:

in one, the functions which can be defined within the theory are “automatically” within a certain complexity class. In such an account, the syntax has to be restricted to guarantee that one stays in the appropriate class. This results, in general, in the problem that certain definitions of functions do not work any longer, even if the function is in the complexity class under consideration.
In a second account, the underlying logic is restricted.
In the third account, one does not restrict the syntax, allowing, in general, to write down “function terms” for arbitrary (partial recursive) functions, nor the logic, but only for those function terms which belong to the complexity class under consideration, one can prove that they have a certain characteristic property, usually, the property that they are “provably total”. While the function terms, according to the underlying syntactical framework, may
have a straightforward computational character, i.e., as $\lambda$ terms, the logic which is used to prove the characteristic property may well be classical.

My question concerns references which can be as an introduction to the three above-mentioned approaches. In this passage we see just characterizations for approaches, but do these have any generally accepted names?


texts: The Cost of an Equivalence Query for DFA

texts:
Inspired by this question, I am curious about the following:

  What is the worst-case complexity of checking whether a given DFA accepts the same
  language as a given regular expression?

Is this known?  The hope would be that this problem is in P -- that there is an algorithm polynomial in the size of both.


texts: Is there any known result on the maximum degree of faces in regular-and-planar graphs ? In particular, is anything known about maximum degree of the faces in a 4-regular planar graph? By degree of a face I mean the number of edges forming it.


texts: Encoding an infinitely looping process with state in the pi-calculus

texts:
Suppose I have a process that informally does this

int count = 0
forever do
    receive x on some channel c;
    count += x;
    output count on some channel d;

(here ";" means sequential composition -- so P ; Q means do P, and then do Q)

I know how to implement the sequential composition in the pi-calculus -- that was answered in another question here. I also think I know how to model a state variable like count in the pi-calculus.

But what I can't seem to encode in the pi-calculus is the infinite loop. To do that I would either need recursive process definitions, or use replication somehow. But I can't work out the correct way to use replication here -- because I can't work out what process I am replicating (since the use of state means the process being replicated is different every time).

Any help would be great.

thanks
graham


texts: Which subproblems of 3SAT are still NP complete?

texts:
The $\mathsf{NP}$-complete problems satisfy the property that if any of them is in $\mathsf{P}$, then all other $\mathsf{NP}$-complete problems are in $\mathsf{P}$.
The problem $3$-SAT is $\mathsf{NP}$-complete, as much as every $k$-SAT with $k\geq 3$.
(On the other hand, $2$-SAT is known to be in $\mathsf{P}$).

Obviously, the problem $3$-SAT can be seen as a subset of $k$-SAT for $k\geq 3$ and, in general, all of them are a subclass of SAT.

However my question goes in the opposite direction: which are some smaller subclasses of $3$-SAT that are still $\mathsf{NP}$-complete?

I am interested in studying the $\mathsf{P} = \mathsf{NP}$ conjecture by looking just into smaller class of $3$-SAT problems that are still acceptable.


texts: Expansion of the union of two expander graphs

texts:
Suppose that $G$ and $H$ are both expander graphs on the same node set $V$ with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$.
Let $G\cup H$ be the graph on $V$ with the smallest set of edges such that both, $G$ and $H$, are subgraphs of $G \cup H$.

What can be said about the expansion of graph $G \cup H$? In particular, is the spectral gap of $G \cup H$ at least as large as the minimum of the spectral gaps of $G$ and $H$?
Is the case where $G$ and $H$ both have constant node degree any different?

This is certainly true for the edge expansion of $G \cup H$, since it can only increase by adding edges.
I know that spectral expansion and edge expansion are related by the Cheeger inequality, but using this route we only get a bound on the spectral expansion of $G \cup H$ that is worse than the one given by $\lambda_G$ and $\lambda_H$.


texts: Succinct Representation and Communication complexity

texts:
Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of $i,j$ is assigned in the input wires, the hardness of P-complete  , NP-complete problems is amplified to EXP complete and NEXP-complete problems respectively .

My question is about relationship between communication complexity  and succinct representation.

For example, can Alice and Bob that have $A,B \subseteq \{1,...,n\}$ compute the disjointedness function with $O(\log n)$ bits to construct the following protocol ?
 However, disjointedness has a lower bound  $\Omega (n)$. The answer of this question must be $NO$. Why ?

Protocol:

1.Alice make a succinct representation of her input $A$ : this circuit output  $1$ iff $i\in A$ for given index of $i \in \{1,...,n\}$.

2.Bob gets $A$ from the succinct circuit by executing brute force evaluation of all assignments, and check whether $A \cap B =\emptyset$

Thank you for Igor's answer.Additional questions are:

What are examples of $nice$ $structures$ you mention ?(Why arbitrary undirected graphs,  boolean circuits, or formulae have $nice$ $structures$ in the sence of your answer ? Why  messages Alice sent do not have ? If $A,B\subseteq \{1,...,{n \choose 2}\}$ then can we consider their inputs as undirected graphs ?)


texts:
There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete problems in subexponential time of form $2^{n^{\delta_2}}$ where $\delta_2\in(0,1)$?

I am particularly interested in what is known about hard to polynomial time approximable problems such as Independence number and Clique number in subexponential time? Note that ETH only prohibits exact computation in such a time frame. Say Independence number is $\alpha(G)=2^{r(n)n}$ on a graph with vertex count $|V|=2^{s(n)n}$ for some $0<r(n)<s(n)$. Is an $2^{(r(n)n)^{\delta_1}}$-factor approximation scheme possible for Independence number in time $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$ where $0<\delta_1<1$ and $0<\delta_2<1$ are some fixed positive reals?

That is for every $\delta_1\in(0,1)$ is there a $\delta_2\in (0,1)$ such that $\alpha(G)$ can be approximated within $2^{\log_2^{\delta_1}(\alpha(G))}=2^{(r(n)n)^{\delta_1}}$ factor in time $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$?


texts: What's the difference between an invariant and an "inductive" invariant?

texts:
I would like to understand this with an example. Also, are there other kinds of invariants related to these?

Thanks!