texts:
Background: I have multiple point clouds (sets of objects) $\{S_i\}_{i\in\mathbb{N}}$ of variable size and "purity" (meaning that some sets contain very similar objects, some show a high diversity; some sets are large, some are small). Each object is characterized by a $n$-dimensional continuous feature vector $v_j \in \mathbb{R}^n$, each set can therefore be seen as a matrix $M_i \in \mathbb{R}^{|S_i| \times n}$.

I want to classify these point clouds using a binary classifier into "pure" and "diverse".

Idea: I was thinking about covariance. This way every point cloud is represented by its $n \times n$ covariance matrix.

Question: What other features can I use to characterize the individual point clouds? How else can I transform these matrices of different shape to representations of fixed length representations that can be passed on to a classifier?


texts: What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $O(n\log n)$ which supports $O(1)$ query time for planar graphs. Do trees have better complexity?


texts: Is the model in which a protocol is proven secure more important than type of hardness from which the algorithm gains its strength

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

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


texts:
To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$.

For more info, see "Superpolynomial circuits, almost sparse oracles and the exponential hierarchy" by Buhrman and Homer.  Also, for more info on $P/poly$, see https://en.wikipedia.org/wiki/P/poly

I recently started thinking about $NP/poly$.  I can't seem to find much info on this class other than the listing here: NP/poly @ Complexity Zoo

@EmilJeřábek suggested in the comments below that $MA$-$EXP^{NP} \cap coMA$-$EXP^{NP}$ (and further $NEXP^{\Sigma_2^P}$) is known to not be contained in $NP/poly$ by relativizing the arguments for $P/poly$.

  Question

  Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

Note: Question was updated to reflect @EmilJeřábek's comments below.


texts: Vertex Cover applications in the real world

texts:
What applications does the Vertex Cover Problem have in the real world?

Which industry or research projects use actually implemented software that is based on theoretical results for the Vertex Cover problem? In particular, are any of the following theoretical results implemented in used software?

Approximation algorithms for Vertex Cover
Exponential-time algorithms for Vertex Cover
Fixed-parameter tractable algorithms for Vertex Cover
Kernelization algorithms for Vertex Cover


texts:
I'm not sure whether this question should be asked on mathoverflow.com or here, but as it is in the context of computational complexity, I will ask here.

Context

Oded Goldreich states in his book Computational Complexity: A Conceptual Perspective (no advertising intended!) that a search problem is in PC (Polynomial-Time Check) if it fulfills this condition among others:

  There exists a polynomial $p$ s.t. if $(x, y) \in R$ then $|y| \leq p(|x|)$.

Question

If the solution to a search problem is a function, how is the size of the function ($|y|$) determined? I thought, it could be size of the input of that function, but I am not sure.


texts: Graphs in which every minimal separator is an independent set

texts:
Background:
Let $u, v$ be two vertices of an undirected graph $G=(V,E)$.
A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$
belong to different connected components of $G-S$. If no proper
subset of a $u,v$-separator $S$ is a $u,v$-separator then $S$ is
a minimal $u,v$-separator. A vertex set $S\subseteq V$ is a (minimal)
separator if there exist vertices $u, v$ such that $S$ is a (minimal)
$u,v$-separator.

A well-known theorem of G. Dirac states that a graph has no induced
cycles of length at least four (called triangulated or chordal graph)
if and only if every of its minimal separators is a clique.
It is also well-known that triangulated graphs can be recognized
in polynomial time.

My questions: What are graphs in which every minimal separator is an independent set?
Are these graphs studied?  And what is the recognition complexity of
these graphs?
Examples for such graphs include trees and cycles.


texts:
The problem

Given

a (connected) DAG $G(V,E)$ where each node is assigned an (non-negative) integer
weight
an integer k where $0\leq k\leq|V|$

Find a induced subgraph $H$ of $G$ consisting of $k$ vertices such that

if a vertex is in $H$, all of its predecessors are also in $H$ (=closure?)
The sum of the weights for all vertices in $H$ is minimized

Possible algoritms

a trivial algorithm to solve this problem is to loop over all subsets of the vertices with size $k$ and check if the first condition holds. If so check if the sum of weigths is smaller than the current best one found. This algorithm would be $O(V×V!)$. For large graphs this would be extremely slow.

Is there a more efficiënt algorithm?

I have considered an greedy algorithm which builds up by starting with an empty set and adds the smallest weight vertex where the first condition would still hold. This algorithm does not always give the correct result.

Edit: An example

weights: vertex 1:weight 6, 2:4, 3:3, 4:4, 5:1, 6:3, 7:6, 8:7, 9:1, 10:4
connections: 1->3, 2->3, 2->4, 3->5, 3->7, 4->6, 4->8, 5->7, 6->8, 7->9, 8->9, 8->10

for $k=4$ a greedy algorithm will return {1,2,4,6} with total weight 17, whilst {1,2,3,5} has total weight 14.


texts:
What are general guidelines for checking your proofs? I believe this is important for graduate students like me. I already know what we need to do to prove something, but you always have to check everything before you send it out. Even to your own advisor.

I've developed myself some strategies by trial and error, and got a lot of advice from my advisor. But this is always a very tedious work. Normally, when you finish with something, you just want to go on to the next problem, but you still have to stick to the current problem until everything is perfect. Here I present an example of my own list of tricks:

Fill in the details. A lot of mistakes are in places were you write "it is clear that...", "without loss of generality...", etc.
Try some numbers. Try extreme cases, like "what happens when I set $n=1$ or $n=1000$".
Keep a clean notebook. Write every day on it, and compare it with your rough notes. I try to write also in latex, I've found many mistakes this way.

What are the general strategies that you apply for checking your proofs?

The objective of this question is to make it a community-wiki.


texts: How can I randomly generate bounded height spanning trees?

texts:
For a project that I am working on, I should generate random spanning trees with bounded height.

Basically I do the following:
1) Generate a spanning tree
2) Check the feasibility, if feasible keep it.

1) Starting from a minimum spanning tree (Prim's or Kruskal's) I add a non-existing edge and this creates a cycle, I detect this cycle and remove one of the edges of this cycle that gives me a new spanning tree and I continue with this spanning tree by adding a new edge...

2) Suppose there is a special vertex $v_{center}$. For every vertex $v$, the length of the path from $v$ to $V_{center}$ should be less then $\delta$, where $\delta$ is a given parameter.

Is there any better(clever) way of doing this?

P.S. I forgot to specify the other constraint (my mistake): the degree of the vertices should also be bounded.


texts: Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$

texts:
An $n \times n$ Boolean matrix $B$ has Boolean rank $k$ if there exist matrices $L \in \{0,1\}^{n \times k}$ and $R \in \{0,1\}^{k \times n}$, s.t. $B = L \circ R$. Here $\circ$ denotes the Boolean matrix product (i.e. $1+1 = 1$).

  What is the best upper bound we know for $|\{B \in \{0,1\}^{n \times n} : B \text{ has Boolean rank } \leq k\}|$?

An equivalent question in terms of bipartite graphs is as follows:

  How many bipartite graphs $G = (V \cup U, E)$ with $|U| = |V| = n$ which can be covered with at most $k$ bicliques exist?


texts: Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments

texts:
Given a tournament $T$ where $S_1$ and $S_2$ be two acyclic sub-tournament of $T$.

  Is the following problem NP-Complete: Finding a maximum acyclic sub-tournament $S$, which is subset of $S_1 \cup S_2$?

Can the given problem be solved in polynomial time? If not please state the NP-Completeness.

By keeping $S_1$ as such and removing only the vertices from $S_2$, an $S'$ maximal acyclic tournament belonging to $S_1 \cup S_2$ can be obtained in polynomial time. The solution $S'$ thus obtained may not be the same as the maximum acyclic sub-tournament $S$.

The polynomial time algorithm is based on compression step in iterative compression algorithm for feedback vertex set in tournament from the paper

  Fixed-parameter tractability results for feedback set problems in tournaments, Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truss, Journal of Discrete Algorithms 8 (2010) 76–86.

If finding a maximal acyclic sub-tournament $S$ is NP-complete then I have no choice except to find $S'$, so I wish to know whether finding $S$ is NP-complete or not.


texts: About Boolean functions with a high sign-rank

texts:
Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to get some context for this,

Before this paper was there no other function known in the $Th \circ Th$ or $Th \circ Maj = Maj \circ Th$ or in any other $TC^d$ class with such high sign-rank?
What other functions do we know of which have a high sign-rank? I can see it to be known for only a handful of examples like the Minsky-Pappert function, a depth $3$ $AC^0$ generalization of it (in a Razborov-Sherstov paper) and another in a Bun-Thaler paper and Inner-Product-Mod-2. Are there others? (If yes, then can you kindly link to references to their proof?)
The page 4 and 5 of this paper give some intuition about what makes a Boolean function have a sign-rank. It would be great to know if others have more insights to add to this discussion. Are there maybe any "folklore" thumb-rules which help judge if a function has a high sign-rank?


texts: Worst-case computational complexity of solving Diophantine equation

texts:
Manders and Adleman proved that the following decision problem is NP-complete:

  Given integers $a,b,c>0$, does the quadratic equation $ax^2+by-c=0$ have a solution in integers $x,y>0$?

The problem remains NP-complete even if the prime factorization of $b$ is given, and $a=1$. It is equivalent to the following problem: given integers $b,c,d>0$, does there exist an integer $0\le x<d$ such that $x^2\equiv c\pmod b$?

My question is, what is the complexity of the following problem?

  Given integers $b,c>0$, does the equation $x^2-cx+by=0$ have a solution in integers $x,y>0$?

Does the problem become easier if the prime factorization of $b$ is given?

Note that any solution has $x,y$ bounded by $c$, hence the problem is clearly in NP.

The problem is equivalent to: given $b,c>0$, does there exist $0<x<c$ such that $x^2-cx\equiv0\pmod b$? Notice that even if we know the factorization of $b$, the number of solutions of this quadratic equation modulo $b$ is exponential in the number of prime factors of $b$ by the Chinese remainder theorem, hence it is not clear how to check whether some of them falls in the target range. For example, in the case where $b$ is odd and coprime to $c$, an $x$ solves the equation iff $x\equiv0$ or $x\equiv c\pmod{p^e}$ for every prime power $p^e$ that divides $b$.


texts: What podcast should everybody listen to?

texts:
This list was inspired by the lists:

What are the popular science books that inspire TCS?
What Books Should Everyone Read?
What papers should everyone read?
What videos should everybody watch?

I don't know if there are a lot of podcasts about Theoretical Computer Science, but if you have something that is relevant to that list it will be very good.


texts: Compute lowest dimensional polytope from a given set of sign vectors

texts:
Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\mathbf R^d$ so that $\langle v,h_i \rangle \neq 0$ and $t_i = \text{sign}( \langle v,h_i \rangle )$ holds for all $i$. Here, $\langle u,v\rangle$ denotes the inner product and $\text{sign}(x)$ denotes the sign ($+$ or $-$) of the non-zero real number $x$.

Question: What is the fastest known algorithm for the inverse operation? Given a set $t_1,\dots,t_n$ of cell types, we want to compute some set of hyperplanes in as few dimensions as possible, so that its cell types are a superset of $t_1,\dots,t_n$.


texts:
Let us suppose that we want to provide for each inductive type an axiom describing the associated elimination/induction principle. For example, given a definition for the naturals:

inductive nat : Prop ≝
  O : nat
| S : nat → nat.

We may provide for them the following definition of an elimination function:

$\texttt{let rec nat_ind(x) := }\\
\quad\forall Q:nat\to Prop. \\
\quad\forall C_1: (Q\; O). \\
\quad\forall C_2: (\forall x:nat. Q x \to Q (S x).\\
\quad\quad (\texttt{x}\equiv O\Rightarrow C_1) \\
\quad\quad  \vee (\exists y:nat. x\equiv S y \Rightarrow \Big(C_2\; y\; (\texttt{nat_ind(}y\texttt{)}\;Q\;C_1\;C_2)\Big)
$

Can this formulation be trivially extended for each constructor by simply adding a $C_i$ for an additional inductive case? If not, where can I look for a  general definition of the elimination axiom that can be applied to any inductive type expressible ine a CoC/CIC dependent type system extending $\lambda Pw$, from Falsehood to Leibniz Equality? I.e., how does a theorem prover generates the elimination for inductive types?


texts: Converting a bounded knapsack problem to 0/1 knapsack problem

texts:
I originally posted this question at the programmers section of StackExchange (because that section is supposed to deal with data structures and algorithms), but they suggested posting in the math section. Read the FAQ there didn't mention anything about algorithms, but did suggest this section: cs theory. If this should really live in the math section, I'll repost there and delete from here.

Link to the the original question: https://softwareengineering.stackexchange.com/questions/117136/converting-a-bounded-knapsack-problem-to-0-1-knapsack-problem

I ran across a problem where goal was to use dynamic programming (instead of other approaches). There is a distance to be spanned, and a set of cables of different lengths. What is the minimum number of cables needed to span the distance exactly?

To me this looked like a knapsack problem, but since there could be multiples of a particular length, it was a bounded knapsack problem, rather than a 0/1 knapsack problem. (Treat the value of each item to be its weight.) Taking the naive approach (and not caring about the expansion of the search space), the method I used to convert the bounded knapsack problem into a 0/1 knapsack problem, was simply break up the multiples into singles and apply the well-known dynamic programming algorithm. Unfortunately, this leads to sub-optimal results.

For example, given cables: 1 x 10ft, 1 x 7ft, 1 x 6ft, 5 x 3ft, 6 x 2ft, 7 x 1ft

If the target span is 13ft, the DP algorithm picks 7+6 to span the distance. A greedy algorithm would have picked 10+3, but it's a tie for minimum number of cables. The problem arises, when trying to span 15ft. The DP algorithm ended up picking 6+3+3+3 to get 4 cables, while the greedy algorithm correctly picks 10+3+2 for only 3 cables. [I suspect that I just need to tweak my value function, but does the DP algorithm handle value functions that vary depending on what else has been selected? My instincts say no.]

Anyway, doing some light scanning of converting bounded to 0/1, it seems like the well-known approach to convert multiple items to { p, 2p, 4p ... }. My question is how does this conversion work if p+2p+4p does not add up to the number of multiple items. For example: I have 5 3ft cables. I can't very well add { 3, 2x3, 4x3 } because 3+2x3+4x3 > 5x3. Should I add { 3, 4x3 } instead?

[I'm currently trying to grok the "Oregon Trail Knapsack Problem" paper, but it currently looks like the approach used there is not dynamic programming.]


texts:
As far as I understand a large number of clustering problems can be formulated as:

$\underset{\textbf{P}}{ \text{argmin}} \;  \sum_{i,j} f \left(x_i, x_j\right)$

where $\textbf{P}$ is a partitioning of $\mathbf{x}$. In other words, the goal is to find a partitioning that is optimal with respect to a sum of pairwise contributions of the variables within and/or across clusters. Problems such as K-means and correlation clustering can be written in the above form. For example, K-means minimizes the sum-of-squares which is known to be NP-hard.

I am wondering if there is any work on what I informally would call higher-order or clustering, where the functions $f$ measure the affinity of general cliques of variables

$\underset{\textbf{P}}{\text{argmax}}\; \sum_{c_i} f(\mathbf{x}_{c_i})$

for cliques $c_i$ in some set $C$.

Perhaps a more difficult problem is what I would informally call black-box clustering, i.e. problems of the above form where $f$ is unknown (i.e. we don't have access to an algebraic or analytical expression of $f$, but we can query it. I imagine using some sort of direct-search optimization method for solving such problems.

Does anybody know of if these problems have been addressed in the literature? Perhaps they are known by other names?


texts: Given $A\in\Bbb Z^{n\times k}$, $v\in\Bbb Z^n$ and variables $x_1,\dots,x_k$ given as a vector $x$ we know that solving $x\in\Bbb Z^k$ in $Ax\leq v$ is fixed parameter tractable. There is a deterministic algorithm that runs in $O((nk)^{ck})$ time for some $c>0$. What is the space complexity of the algorithm? Does it run in polynomial space?


texts: Any SAT/SMT formulations of the VRP/VRPTW (TSP, Job-Shop-Scheduling)?

texts:
i wonder if they are any approaches formulating a Vehicle-Routing-Problem with Time-Windows (VRPTW) (as a decision problem) as a SAT/SMT instance? (alternative: TSP)

For example:
"Is there a valid solution visiting all customers within their time-windows with n=10 vehicles?"

This decision problem could be useful for a first step minimizing the number of vehicles used.

I don't have any experience with SMT, but i expect it to be necessary if we want to handle coordinates/times as real numbers.

Usually all the TSP/VRP formulations are done in the mixed-integer-programming domain, but i wonder if a sat/smt formulation could be competitive (in terms of solving time in practice) for the decision problem above.

So what do you think:

do you know any references?
do you think a sat/smt approach could be competitive?
anything else you want to mention?

Thanks for all your input.

Sascha

Edit: As i mentioned the TSP as a more common problem in TCS which is related to the VRPTW, i should also mention the Job Shop Scheduling problem, which is the other "partial problem" in the VRPTW. Maybe the researchers in this field tried something with SAT/SMT.


texts: Can a totality checker be used to guarantee a proof on the calculus of constructions + inductive types is correct?

texts:
If we extend the Calculus of Constructions with Fix, we gain a lot of expressivity for barely no added complexity. That includes being able to derive induction, perform large eliminations, prove 0 != 1 and so on. This system is, moreover, very user-friendly and comfortable to program in. Sadly, nothing of that because the resulting system becomes inconsistent. Making it consistent again requires, it seems, a lot of added complexity such as, for example, inductive types, or positive recursion checks + constructor-constrained recursive types + lift.

Suppose, though, that someone gives me a term T of type MyTheorem, programmed in that language (CoC + Fix), and that this term successfully pass through a totality checker. Wouldn't I be able to, then, trust, with absolute certainty, that MyTheorem holds? And, if that is true, doesn't that mean that, as long as that totality checker is used, one can just program on that comfortable language instead of dealing with the added complications of induction types and so on?


texts: Can you identify the sum of two permutations in polynomial time?

texts:
There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question:

Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ numbers such that $\sum_{i=1}^n a_i = n(n+1).$  Decompose it into the sum of two permutations, $\pi$ and $\sigma$, of $1 \dots n$, so that $a_i = \pi_i + \sigma_i\,$.

There are some necessary conditions: if the $a_i$  are sorted so that $a_1 \leq a_2 \leq \ldots \leq a_n\,$, then we must have

$$\sum_{i=1}^k a_i \geq k(k+1).$$

However, these conditions are not sufficient. From the answer to this math.se question I asked, the sequence 5,5,5,9,9,9 cannot be decomposed as the sum of two permutations (one can see this by using the fact that both 1 or 5 can only be paired with 4).

So my question is: what is the complexity of this problem?


texts: How many samples are needed to reconstruct a path?

texts:
Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be multiple shortest paths.

At each iteration, each vertex is randomly colored using $0$ or $1$.
We then get a single bit, that is $1$ with a probability proportional to the number of $1$-vertices along the path.
That is, if $6$ of the vertices along the path were colored with $1$ and $4$ were zero, then the bit will be $1$ w.p. 3/5.

Importantly, we get to know the coloring of every iteration, and the goal path does not change.

  How many samples do we need until we can compute the path with, say, probability 2/3?

A very simplistic approach would be to eliminate all monochromatic paths whose color is different than the given bit (e.g., a $1$-path can be eliminated if we get a $0$-bit). This seems to give a very weak bound.


texts: Separating $DSPACE(f)$ and $DTIME(2^f)$: is there any function computable in time $2^{O(f)}$ but not in space $O(f)$?

texts:
For $f(n)\ge n$,

$$\mathsf{DSPACE}(f(n)) \subseteq \mathsf{DTIME}(2^{O(f(n))}).$$

Is there any function $f$ for which this containment is known to be proper?


texts: Easy problems with hard counting versions

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

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

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

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

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


texts: Techniques for Reversing the Order of Quantiﬁers

texts:
It is well-known that in general, the order of universal and existential quantifiers cannot be reversed. In other words, for a general logical formula $\phi(\cdot,\cdot)$,

$(\forall x)(\exists y) \phi(x,y) \quad \not\Leftrightarrow \quad (\exists y)(\forall x) \phi(x,y)$

On the other hand, we know the right-hand side is more restrictive than the left-hand side; that is, $(\exists y)(\forall x) \phi(x,y) \Rightarrow (\forall x)(\exists y) \phi(x,y)$.

This question focuses on techniques to derive $(\forall x)(\exists y) \phi(x,y) \Rightarrow (\exists y)(\forall x) \phi(x,y)$, whenever it holds for $\phi(\cdot,\cdot)$.

Diagonalization is one such technique. I first see this use of diagonalization in the paper Relativizations of the $\mathcal{P} \overset{?}{=} \mathcal{NP}$ Question (see also the short note by Katz). In that paper, the authors first prove that:

  For any deterministic, polynomial-time oracle machine M, there exists a language B such that $L_B \ne L(M^B)$.

They then reverse the order of the quantifiers (using diagonalization), to prove that:

  There exists a language B such that for all deterministic, poly-time M we have $L_B \ne L(M^B)$.

This technique is used in other papers, such as [CGH] and [AH].

I found another technique in the proof of Theorem 6.3 of [IR]. It uses a combination of measure theory and pigeon-hole principle to reverse the order of quantifiers.

  I want to know what other techniques are used in computer science, to reverse the order of universal and existential quantifiers?


texts:
I've been playing around with resumptions lately, mostly from Abramsky's classic paper Retracing Some Paths in Process Algebra. They are quite slick (basically solutions to the domain equation $R = I \to (O \times R)$), and very reminiscent of Kahn networks.

Of course, this observation is not original to me --- they form a traced monoidal category, and this fact was used by Abramsky and Jagadeesan to give semantics to linear logic. At any rate, note that if you feed a resumption $r$ an input of type $I$, you get an output of type $O$ and an updated resumption $r'$, which is what lets you model the fact that a dataflow node can change as it sees inputs come in.

As a result, it seems like they could give a nice API for building I/O transducers in a higher-order language like ML or Haskell, but I can't seem to find any papers describing such a thing. But they've been around for decades, and Gordon Plotkin invented them, so it's not like they've languished in obscurity. So I was wondering if anyone had seen them put to such use.


texts: What are some career options for someone with a computer scientist master degree?

texts: Other than going fully academic and getting a doctorate/post-doc, or going for a more or less 'standard' job in software development, what are some other career options in the full or semi theoretical C.S field?


texts: Using Kolmogorov complexity as input "size"

texts:
Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$.
Normally in the analysis of algorithms or computational complexity theory, we have some sets
$$I(n) = \{w \in S : |w| = n\}$$
of all inputs of length $n$, and a function $T(w)$ that gives the running time of some solution algorithm $A$ on input $w$.
The worst-case running time sequence for $A$ is then
$$ f_n = \max_{w \in I(n)} T(w). $$

Let us now define the sets
$$ I^K(n) = \{w \in S : K(w) = n \}$$
of all inputs with Kolmogorov complexity $n$, and let us define the sequence
$$ f^K_n = \frac{1}{\left|I^K(n)\right|} \sum_{w \in I^K(n)} T(w). $$
Here $f^K$ is the average running time sequence for $A$, except where the "size" of inputs is their Kolmogorov complexity, not their length.

Are there algorithms for which $f_n$ is asymptotically significantly different from $f^K_n$?  If so, are there problems whose time complexity changes when using this different way of analyzing algorithms?


texts:
The paper "Symbolic Finite State Transducers, Algorithms and Applications" by Bjorner et al (to appear at POPL 2012) describes one type of finite-state, infinite-alphabet automata/transducers by using predicates from any decidable theory as the alphabet. The paper also references quite a few others including:

"Automata and logics for words and trees over an infinite alphabet" by Segoufin,
"Finite memory automata" by Kaminski and Francez, FOCS 1990

I'm wondering whether there's a good survey on different infinite alphabet automata models.


texts: Hardness of approximation by reduction from MAX-E3SAT

texts:
For the MAX-E3SAT define $k=\sum_i^n (g_i-1)$, where $n$ is the number of variables and $g_i=\text{max}(\{\text{occurrences of }x_i, \text{occurrences of }\neg x_i\}), \text{ for each }i=\{1,\ldots,n\}$.
We were able to prove a reduction from MAX-E3SAT to a particular minimization problem $\Pi$, wherein if a $\beta$ fraction of the $m$ clauses are satisfied then the cost of the tour is  $c_1 k + c_2 (1-\beta) m $, where $c_1, c_2 >0$ are constants.
What are the existing results on MAX E3SAT we could use to show inapproximability? The inapproximability depends on the ratio $(1-\beta)m/k$ and we would want the ratio $(1-\beta)m/k$ to be as large as possible to get better results.
I have not specified details of the problem $\Pi$ and the constants as I don't think they are necessary for improving the results. This will help to keep the question minimal and general enough for others to benefit from.
Attempt 1:

Theorem 16.23 [1]: For any positive constant $\delta >0$, $\text{NP}\subseteq \text{PCP}_{1, 7/8 + \delta} \left(O\left(\log n\right), 3\right)$, and the verifier is restricted to use only functions that check the "or" of three bits or their negations.

For any $\delta >0$ no polynomial-time algorithm can distinguish between MAX E3SAT instances in which all clauses are satisfiable, and instances in which a $7/8 +\delta$ fraction of the clauses are satisfiable, unless P=NP

So using this theorem and the reduction we can deduce a gap-preserving reduction of $\left(1, 1+\frac{c_2(1-\beta)m}{c_1k}\right)$. A simple and conservative bound for $k$ is $2m$, assuming all clauses are distinct, all literals in a clause are distinct, and both $x_i$ and $\neg x_i$ don't occur in the same clause. This then gives the result that an $\alpha$-approximation algorithmn for $\Pi$, with $\alpha <  1+\frac{c_2(1-\beta)}{2c_1}$ and $\beta=7/8$, will imply P=NP.
Attempt 2:
I recently looked into [2]. The $(1016-\epsilon )/1015$ inapproximability result for MAX-(3,2B)-SAT seems to be relevant. The structure of the problem can help in bounding $k$ to $3m/4$ (need to verify calculations), as each literal occurs twice. However, this doesn't seem to lead to a better result due to small $(1-\beta)$.
References:
[1] Williamson, David P.; Shmoys, David B., The design of approximation algorithms, Cambridge: Cambridge University Press (ISBN 978-0-521-19527-0/hbk; 978-1-139-06515-3/ebook). xi, 504 p. (2011). ZBL1219.90004.
[2] Berman, Piotr; Karpinski, Marek; Scott, D. Alexander, Approximation Hardness of Short Symmetric Instances of MAX-3SAT (2004).


texts: Should one study undergrad TCS materials before taking grad-level ones? (soft question)

texts:
I am a 1st year PhD student. I got a bachelor's degree in CS but I didn't start learning TCS systematically until this year.
This dumb question came to me when I opened an undergrad complexity lecture watchlist after I forgot it for months, and realized that I had already learned the content from an "advanced" textbook. And I found things covered by the course were learned by myself within a much shorter time. That's perhaps a special case. But I noticed that undergraduate-level courses/materials cover more details and examples about the basic concepts than advanced ones, and I don't know if it's necessary to know such a kind of details.
So my real question starts here: should one skip undergraduate-level TCS courses/materials to save time, or do it step by step to reinforce knowledge?


texts:
My background is in complexity theory/logic (where there is just one process most of the time), and in distributed computing (where there are $n$ processes, and one or more might fail over time).  However, I now want to be able to say something about a process spawning/creating/spinning off another process.  Is there rigor in parallel computing, operating systems, etc., that accounts for this?
Motivation:
I am trying to construct models that abstract out certain features of molecular interactions.  I'd like to say that the set of chemical reactions $S$ is an independent process, and that at a certain time step $t$, it spawns another independent process $S'$.  Intuitively, these things feel like independent processes, because they have no contact with each other after time $t$ - or very little contact, only interchanging "messages."
More formally:

(1) Are there pre-existing CS definitions that capture the notion of one process spawning another independent process?  I am especially interested in being able to demarcate where $S$ stops and $S'$ starts, and why that is "reasonable" to do.
(2) If there is more than one answer to (1), what do you consider the pros and cons to the various definitions?

(Note: I have no idea how to tag this appropriately, and plan to re-tag depending on the answers.)


texts: Is there a short explicit construction of an universal recursive function? All definitions I have seen involve numbering of Turing machines in some way, which is possible yet seems hard and unmanageable to write in a higher-level programming language (like Python, Haskell etc.)


texts: If BQP contains NP, does this mean that P=NP?

texts:
There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that if P=NP then PH collapses to the 0th level.

Based on the above two statements, I would like to ask if BQP contains NP, does this imply that P=NP?

[1] http://www.scottaaronson.com/papers/bqpph.pdf


texts: Can weakly parsimonious counting reductions use the input instance to compute the count?

texts:
Quick version: is there a definitive definition of weakly parsimonious counting reduction for #P?

Longer version: I am doing a gadget based reduction for NPC and would like to use it for #P. The reduction definitely isn't strongly parsimonious and to keep it simpler I'd like to avoid making it so.

Given the number of solutions to the reduced class, I can get a function which gives me the number of solutions to the original, IF I am allowed to put the original instance into the counting translation function. The number of solutions to the original is going to be something like the number of solutions to the translated problem divided by 2^n, where n is the number of variables in the original SAT problem.

Some definitions I've found on the web allow this and some don't, so I want to know if there is an important difference.


texts:
Let $\alpha(C_{n}^{\boxtimes k})$ be independence number of $k$-fold strong product of an $n$-vertex cycle graph $C_{n}$.

$\forall n > 6$, is $\alpha(C_{n}^{\boxtimes (k+r)})^{\frac{1}{k+r}} \geq \alpha(C_{n}^{\boxtimes k})^{\frac{1}{k}}$ for infinitely many positive integer pairs $(k,r)$?


texts: What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

texts:
We know that Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable,so what is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$?

Is it equivalent to Tarski elimination algorithm or lower?


texts: I'm looking into using of the shelf compression algorithm to approximate the Kolmogorov complexity of a document corpus D and the complexity of D+d, where d is an extra document. I've got a strange result where size(compress(D)) > size(compress(D+d)). Is this possible if compress actually calculated (the uncomputable) Kolmogorov complexity of D and D+d?


texts: Any computable transcendental number that is computable in P time but not $O(n)$

texts: Is there any known computable transcendental number such that its $n$th digit is computable in polynomial time, but not in $O(n)$?


texts:
Is there a Turing Machine that can decide whether almost all other Turing Machines halt?

Suppose we have some enumeration  $\mathbb{N} \rightarrow \{M_i\}$ of Turing machines, and some notion of "size" of a set of natural numbers $\| \cdot \|$, and we define:

$$f(i) = \|\{n: M_i \text{ can't decide whether }M_n \text{ halts} \}\|.$$

What characterizations of the minimum value of $f$ exist for different $\| \cdot \|$? For instance, suppose $\| S \|$ is the limsup of the proportion of numbers up to $k$ that are in $S$. Is there an $i$ for which $f(i) = 0$?


texts: Polynomial-time algorithms with huge exponent/constant

texts: Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, where the proven upper bound on the running time is in such a way)?


texts: Prove that finding set of $k$ vertices $S$, such that $G{\setminus}S$ is claw-free is NP-Complete

texts:
The claw in a graph $G(V,E)$ consists of a vertex $v\in V$, and it's three neighbours - $\{x_1,x_2,x_3\}\in V\setminus \{v\}$, if $\{x_1,x_2,x_3\}$ form an independent set in $G$.

The problem asks us to prove that the following problem is NP-complete:

Is there a set of $k$ vertices $S$, such that $G(V\setminus S, E)$ is claw-free?

It is simple to prove that problem is in NP - we can check in polynomial time whether the graph is claw-free after removing $k$ vertices. So now the only thing needed is to find a reduction from some known NP-complete problem to this one. I've been stuck on this problem for 2 weeks - I've thought about reducing VERTEX COVER, but after fiddling with it I think this may be a dead end. I will be grateful for any tips, that would point me in the right direction.


texts: Generalization and instantiation of types in Hindley-Milner type inference

texts:
I’m currently reading Heeren, B., Hage, J., & Swiestra, D. (2002). Generalizing Hindley-Milner Type Inference Algorithms in an attempt to understand Hindley-Milner-style type inference.

I'm struggling with two concepts early in the paper, the first is
generalization of a type. From the article:

  Generalizing a type $\tau$ with respect to a type environment $\Gamma$
  entails the quantification of the type variables that are free in
  $\tau$ but do not occur in $\Gamma$:

  $$generalize(\Gamma,\tau) =_{def}\;\forall\vec{\alpha}.\tau
 \;\;\text{ where } \vec{\alpha} = freevars(\tau)-freevars(\Gamma)$$

  In the literature, generalization is sometimes referred to as
  determining the closure of a type. In fact, these different notations,
  e.g. $\Gamma$($\tau$) in [DM82] and Clos$\Gamma$($\tau$) in [LY98], all express the same.

Another explanation is that generalize “abstracts a type over all type variables which are free in the type but not free in the given type environment.”

However, I fail to see what this accomplishes and when you want to do this, and would be very grateful if someone can point me in the right direction.

Another concept is instantiation, explained in the following manner:

  An instantiation of a type scheme is obtained by the replacement of
  the quantified type variables by fresh type variables:
  $$instantiate(\forall \alpha_1\ldots\alpha_n.\tau =_{def}\; [\alpha_1 := \beta_1,\ldots,\alpha_n := \beta_n]\tau \;\;\text{ where } \beta_1,\ldots,\beta_n \text{ are fresh}$$
  A type
  $\tau_1$ is a generic instance of a type scheme $\sigma = \forall\vec{\alpha}.\tau_2$ if there exists
  a substitution S with S$\beta$ = $\beta$ for all $\beta \in freevars(\sigma)$ such that $\tau_1$ and
  S$\tau_2$ are syntactically equal.

Does this simply mean that you replace all bound type variables with globally unique variables in order to avoid accidental collisions, or is there more to it?


texts: Is there any work done on developing difference-calculus of Turing Machines (or simpler Formal Languages)

texts:
I am attempting to develop some notions of a difference-calculus between a notional Ideal Turing Machine conceived by a developer (e.g. whatever is intended by a software developer), call it $M_I$, and the Machines that represent the software which actually gets designed and implemented, say $M_\alpha$ and $M_\beta$, respectively.

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

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


texts: Name for "uniformly polynomial" subclass of XP?

texts:
Suppose $L$ is a parameterized language with respect to some alphabet $\Sigma$.
The $k$-slice of $L$ is $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$, the set of instances in $L$ which have parameter $k$.
The complexity class $\mathsf{XP}$ contains the parameterized languages $L$ such that $L_k \in P$ for each $k$, possibly with a different algorithm and polynomial running time bound for each $k$.
Each fixed-parameter tractable language is in $\mathsf{XP}$, and there are languages in $\mathsf{XP}$ that are not in $\mathsf{FPT}$; this is Proposition 27.1.1 in the Downey & Fellows 2013 textbook.

However, $\mathsf{XP}$ seems to have nontrivial structure beyond this, since one can stratify this class based on how fast the degree of the bounding polynomial grows with $k$: for $\mathsf{FPT}$ the degree is constant, whereas for $\mathsf{XP}$ it can grow arbitrarily.
Downey & Fellows does not mention anything about the structure of $\mathsf{XP}$ beyond Proposition 27.1.1, and the discussion in the Flum & Grohe 2006 textbook isn't much more detailed.

Following on from my earlier question Limits of variants of Independent Set? is there a name for the subclass $\mathsf{Q}$ of $\mathsf{XP}$ where $L \in \mathsf{Q}$ if there is a polynomial $g_L$ such that every instance $(x,k)$ in $L$ can be decided in at most $|x|^{g_L(k)}$ steps?

In other words, this class $\mathsf{Q}$ allows only up to $|x|^{\text{poly}(k)}$ time instead of $|x|^{g(k)}$ time for some arbitrary function $g$ as for $\mathsf{XP}$.


texts:
I am trying to find problems whose average-case space complexity has been analyzed.

More specifically, I am interested to know if there are any  problems with a proven  space complexity lower bound that is  super-linear, and especially if there are any  with an  average-case analysis (e.g., the bound holds even if the algorithm is allowed to err for a small percentage of times etc. )

Thanks in advance


texts: Is a theoretically secure key exchange possible?

texts:
During a discussion I was wondering if it would be possible to design a theoretically secure key exchange.

In other words: If it is possible to design a key exchange (like Diffie–Hellman) where the communication could not be decrypted by an eavesdropper even if he had a computer with infinite speed and memory.

My question is:

Would this be possible and can this (yes or no) be proven mathematically?

EDIT

After having read some of the answers I want to improve my question a bit:

Is it possible that some sender is sending some information to a receiver over an (insecure) channel not having any common keys nor access to a common source of randomness (or similar) in a way that it is not theoretically possible to "decrypt" the actual information from data transferred over the channel?

After a week of thinking I think I found some proof:

A is some data of the sender (such as a public/private key pair)
B is some data of the receiver
Ds is the data sent by the "sender"
Dr is the data sent by the "receiver"
Fn are mathematical functions
M is the "cleartext message" to be encrypted
The data sent by the "receiver" depends on the data received from the "sender" and from the private data B: Dr = F1(B,Ds)
The data sent by the "sender" depends on the data received from the "receiver", private data and the message: Ds = F2(A,M,Dr)
"Theoretically security" would mean that two different messages M exist which can result in the same data of the set (Dr,Ds); otherwise an attacker could search for all sets (A,B,M) which lead to a given data of (Dr,Ds) - and would know the only possible value of M
Because of Ds = F2(A,M,Dr) this would mean that different values of the set (A,M) must exist that lead to the same Ds (when Dr is given)
This would mean that the receiver (not having any additional information about A but the information contained in Ds) would also not be able to decrypt the message

I'm not sure if this proof is correct.

Can anyone tell me if it is correct?


texts: How many different proofs are there of parity is not in AC0?

texts:
The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part of this question. E.g., if you say there are 4 different proofs in your answer, please explain why these 4 are "different" in your opinion.

I am familiar with two proofs, one based on the switching lemma, and the other based on aprrximation by low-degree polynomials, due to Razborov-Smolensky. I think these proofs are different since they generalise in different ways. E.g., switching lemma proofs give better correlation bounds, while low-degree techniques give lower bounds for $\mathsf{AC}^0$ with mod $p$ gates.


texts:
Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2.

Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time?

Surprisingly, the only reference I find for this problem is this ancient discussion:

http://www.iwriteiam.nl/cutsticks.html

What else is known about the problem? Can we prove the problem to be `in the limbo'?

Update: The cutting-sticks problem has the constraint that each stick is at least $n$ units long. (See the comments and Tsuyoshi's answer for the unconstrained case).


texts: Ed. Witten's new paper and the simulation of a quantum field theory

texts:
Context: Ed. Witten recently wrote a potentially revolutionary paper where he showed that under certain conditions, a Chern-Simons path integral in three
dimensions is equivalent to an N = 4 path integral in four dimensions (this is the standard d=4, N=4 super Yang Mills theory)

Speculation: Witten had shown that the Chern-Simons topological quantum field theory can be solved in terms of Jones polynomials. A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial. (source: Wikipedia and this paper) Now I haven't completed reading Witten's paper and I wouldn't understand much of it anyways. But the idea is that if a quantum computer can simulate a path integral (or a Chern-Simons TQF) and since now Witten has shown in both of them to be dual descriptions in some sense, a quantum computer, atleast theoritically might be able to simulate a QFT. Also by the extension of that, Maldacena proposed that the specific field theory that Witten is using to be dual to type-II B string theory in AdS/CFT so then it may also be possible (only theoritically) to simulate a string theory.

Question: What are the technical constrains that a quantum or classical computer faces while simulating a QFT? Also my speculations only partially complete, could experts suggest a better description? Thanks!

PS. Also thanks to Mitchell Porter who brought up that paper before.


texts:
Consider the following div function written in Coq. It takes in a proof that the divider is non-zero.

Definition div (n d:nat) (pf: ~(d = 0)) := n/d.

Focus on ~(d = 0): Is this a term or a type? My understanding is that this is a term of type Prop. Check gives the same.

Check (forall d:nat, ~(d = 0))
  forall d : nat, d <> 0 : Prop

So, is pf a member of the term ~(d = 0)? This is confusing. Should I now think of ~(d = 0) as a type? Note that I am familiar with dependent types (though not expert) and am being pedantic here.

A term by itself cannot be a type unless pf : ~(d = 0) is a syntactic sugar for something along the lines of pf: Proof ~(d = 0) where Proof is a type of kind $\Pi x:Prop. \star$. That is, it takes a prop term and returns a new type.

What is going on here? I think I am missing the calculus part here.


texts: Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?

texts:
Deutsch's algorithm is a well known quantum computing $f(0) + f(1)\mod{2}$
with only one one evaluation of $f$.
If we replace $+$ with $\cdot$ the problem seems to become rather different. My question is:
does there exist a quantum algorithm computing the value of $f(0)\cdot f(1)$ (or AND if you prefer)
using only one evaluation of $f$. Otherwise: is it known that such an algorithm does not exist?

Update: I have now become aware of procedure that gives correct answer with a probability greater than what any classical procedure is able. The "error" is one-sided in the sense that it always produces the correct answer when $f(0)\wedge f(1)=1$. This leads me to an extended question: does there exist a quentum algorithm (possibly similar to the one mentioned below) with the property that the result is $1$ only if $f(0)\wedge f(1)=1$? Of course the "best case scenario" would be an algorithm that gives correct answer with probability $1$.


texts: Expected values of Kolmogorov complexity in a random sample

texts: Kolmogorov complexity of a string is not computable. However, in a random subset of size $M$ of binary strings of length $n$, how many are expected to have complexity less than some integer $n_{0}$ less than $n$ (as a function of $M$, $n$ and $n_{0}$)?


texts: The cozy neighborhoods of "P" and of "NP-hard"

texts:
Let $X$ be an algorithmic task. (It can be a decision problem or an optimization problem or any other task.) Let us call $X$ "on the polynomial side" if assuming that $X$ is NP-hard is known to imply that the polynomial hieararchy collapses. Let us call $X$ "on the NP-side" if assuming that $X$ admits a polynomial algorithm is known to imply that the polynomial hierarchy collapses.

Of course, every problem in P is on the polynomial side and every problem which is NP-hard is in the NP-side. Also, for example, factoring (or anything in NP intersection coNP) is on the polynomial side. Graph isomorphism is on the polynomial side. QUANTUM-SAMPLING is in the NP-side.

1) I am interested in more examples (as natural as possible) of algoritmic tasks in the polynomial side and (especially) in more examples in the NP side.

2) Naively it looks that the NP side is a sort of a "neighborhood" of the NP-hard problems, and the P-side is a "neighborhood of P".  Is it a correct insight to regard problems in the NP side as "considerably harder" compared to problems in the P side. Or even to regard problems in the NP side as "morally NP-hard?"

3) (This might be obvious but I don't see it) Is there an $X$ on both sides or are there theoretical reasons to believe that such an $X$ is unlikely. Update The answer is YES; see Yuval Filmus' answer below.

(If these "sides" are related to actual complexity classes and if I miss some relevant cc jargon or relevant results please let me know.)

Update: There are by now several very good answers to the question. As noted first by Yuval Filmus and mentioned again the question is not formal and some restriction on the argument showing that X is on the P-side/NP-side is needed. (Otherwise, you can have X to be the task of presenting a proof for 0=1 which is on both sides.) Putting this aside, it may be the case that problems X (genuinly) on the NP-side capture somehow the hardness of SAT, although this may also be the case for some problems on the P-side where the hardness of SAT is weakened (even slightly) in a provable way. Yuval Filmus gave a weakened version of SAT which is on both sides. Andy Drucker gave (in two answers) five interesting examples including a reference to Schöning's Low and High hierarchies, and Scott Aaronson gave further interesting examples, mentioned the question of inverting a one-way function which is close to capture NP hardness and yet on the P-side,  and his answer also discusses the interesting case of QUANTUMSAMPLING. I metioned an old result of this kind by Feige and Lund.


texts: Avoiding overflow in finding a solution to $ax + by = c$

texts:
Can anyone come up with a nice way of computing a solution to the linear diophantine equation $ax + by = c$ where $a,b,c \in \mathbb{Z}$ and $\gcd(a,b) \mid c$, such that all the calculations are carried out without any of the intermediate results exceeding $\max\{|a|, |b|, |c|\}$ in absolute value?

I.e. if $a,b,c$ are 64-bit integers, all the calculations should be done using 64-bit integers only.

The standard method is of course to use Euclidean algorithm to first find a solution to $ax + by = \gcd(a,b)$ and then multiplying $x$ and $y$ by $\frac{c}{\gcd(a,b)}$. The Euclidean algorithm is fine, but this last multiplication might go out of range.


texts: Type theoretic equivalent of isomorphism class

texts:
How one defines the notion of isomorphism class in type theory? For concreteness I will describe what I mean with an example in Coq.

Suppose I have a record ToyRec:

Record ToyRec {Labels : Set} := {
X:Set;
r:X->Labels
}.

And a definition of isomorphisms between two objects of type ToyRec,
stating that two objects T1 and T2 are isomorphic if there exists a
bijection f:T1.(X)->T2.(X) which preserves the label of mapped elements.

Definition Isomorphic{Labels:Set} (T1 T2 : @ToyRec Labels) : Prop :=
exists f:T1.(X)->T2.(X), (forall x1 x2:T1.(X), f x1 <> f x2) /\
                         (forall x2:T2.(X), exists x1:T1.(X), f x1 = f x2) /\
                         (forall x1:T1.(X) T1.(r) x1 = T2.(r) (f x1)).

Now I would like to define a function that takes an object T1 and returns a set
containing all objects that are isomorphic to T1.

g(T1) = {T2 | Isomorphic T1 T2}

So I have some closely related questions:

1) How one does such a thing in type theory, or more specifically, in coq? I know that I might be reasoning too set theoretically here, but what would be the right type theoretic notion of isomorphism class?

2) More basically, how one would define a set (or type) of all elements  satisfying a given property P?

3) Does Voevodsky's univalence axiom helps formalizing this notion?

obs: I posted a similar question in stackoverflow, but I believe that cstheory is more appropriate, since this question is more about type theory than coq syntax.


texts: Confluently Persistent String Data Structure

texts:
I'm looking for a confluentially persistent data structure for a string - so far I'm looking at finger trees. That is, how would I resolve two edits to the same base tree, and would I be able to preserve the undo history? I'm assuming that some mutations would be mutually exclusive, and I'd need to reject one. That is, I'm under the impression that order matters.

Some specifics - I'll have a copy of the tree in each thread - each will be sending updates to a central thread that updates all the others. Each thread will be based on the central thread's tree.


texts: Do graphs with large number of paths contain large chain minor?

texts:
Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.

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

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

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

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

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

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

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


texts: Historical reasons for adoption of Turing Machine as primary model of computation.

texts:
It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-used than other theoretically equivalent (to my knowledge) models, for instance Kleene's μ-Recursion or the Lambda Calculus (I understand that the former didn't appear until later on and the latter wasn't originally designed specifically as a model of computation, but it shows that alternatives have existed from the start).

All I can think of is that the TM model more closely represents the computers we actually have than its alternatives. Is this the only reason?


texts:
Background

The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses).  These running times are generally given in terms of $M$, the size of memory, and $B$, the number of words that can be transferred to memory at one time.  Sometimes $L$ and $Z$ are used for $B$ and $M$ respectively.

For example, sorting requires a cost of $\Theta(N/B\log_{M/B} N/B)$ and naive matrix multiplication requires $\Theta(n^3/B\sqrt{M})$.

This model is used to analyze "cache-oblivious algorithms", which do not have knowledge of $B$ or $M$.  Generally the goal is for the cache-oblivious algorithm to perform optimally in the external memory model; this is not always possible, as in the Permutation problem for example (shown in Brodal, Faderberg 2003).  See this writeup by Erik Demaine for a further explanation of cache-oblivious algorithms, including discussions of sorting and matrix multiplication.

We can see that changing $M$ causes a logarithmic speedup for sorting and a polynomial speedup for matrix multiplication.  (This result is originally from Hong, Kung 1981 and actually predates both cache obliviousness and the formalization of the external memory model).

My question is this:

Is there any case where the speedup is exponential in $M$? The running time would be something like $f(N,B)/2^{O(M)}$. I am particularly interested in a cache-oblivious algorithm or data structure that fits this description but would be happy with a cache-aware algorithm/data structure or even a best-known lower bound.

It is generally assumed in most models that the word size $w = \Omega(\log N)$ if $N$ is the input size and clearly $M > w$.  Then a speedup of $2^M$ gives a polynomial speedup in $N$.  This makes me believe that if the problem I'm looking for exists, it is not polynomial.  (Otherwise we can change the cache size by a constant to obtain a constant number of I/Os, which seems unlikely).


texts: Is signing a message hash a valid replacement for blind signature?

texts:
I didn't understand how the blind signature implementations work. But I devised my own way of doing it:

Alice would compose the message
Alice would calculate the hash of the message
Alice would hand the hash to Bob
Bob would sign it with his private key
Alice would hand the message and the signed hash to Carol
Carol would calculate the actual hash using the message
Carol would decode the signed hash with Bob's public key
Carol would compare the actual hash with the decoded hash

Wouldn't this algorithm replace the blind signature implementation as described in Wikipedia in every case?


texts:
Ownership types and Separation Logic seem to have similar goals, control over ownership and aliasing.  Perhaps, I should also add: the ability to write modular specifications.

What is known about the relationship between ownership types and Separation Logic?


texts:
Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ for this vertex. The game ends when a monochromatic edge is discovered. Let $X(G)$ be the maximal length of the game under optimal play by both players (Alice wants to shorten the game as possible, Bob wants to delay it as possible). For example, $X(K_n) = n$ and $X(C_{2n+1}) = \Theta(\log n)$.

Is this game known?


texts: Balls & Bins: A punishment and reward game

texts:
Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$.  The rules of the game are as follows:

(1) Once a bin has a threshold number of balls $Q$ (the threshold is uniform for all bins), the bin may be capped, and capping is irreversible.  However, one is not obligated to cap the bin once this condition is met.  Capping must be SEQUENTIAL.  One cannot simultaneously cap two bins to avoid e.g. a situation where capping one bin drops the number of balls in the other bin below the threshold $Q$ necessary for capping.

(2) Once a bin is capped, a bin-specific set of "punishments" or "rewards" can be specified for at most $k$ other bins.  For example, we might say that, in capping bin $3$, we need to subtract two balls from bin $1$ and add seven balls to bin $5$.  So to each bin we assign a two $k$-tuples: the first, e.g. {1,5}, with values from the previous example, specifies the bins to be "punished" or "rewarded", and the second, e.g. {-2, 7}, again from the provided examples, species how many balls to add or remove from each of the bins in the first tuple.

(3) Negative values for bin ball counts are permissible, and a bin may initiate (i.e. have some $c_i$ value) $\leq 0$.

(4) We add the constraint that punishments or rewards must be symmetric.  If capping some bin $b_i$ means subtracting one ball from bin $b_j$, it must also be the case that capping bin $b_j$ means subtracting one ball from bin $b_i$.

(5) We add the constraint that the total number of punishments or rewards a bin may receive is at most $k$.  By the symmetry condition from (4), this correspondingly implies that the total number of punishments or rewards a bin may deliver is at most $k$.

Consider now the decision problem: provided some set of bins $(b_1, b_2, ...)$, initial ball counts $(c_1, c_2, ...)$, and access to all of the dependencies elaborated on in rule (2), can all of the bins be capped?

This problem is trivially in $NP$, but for what smallest value of $k$ is it $NP$-complete?  Can the decision problem be $NP$-complete for $k=2$?  Is there an easy reduction from an $NP$-complete problem or a problem solvable in polynomial time?

Update // Added further constraints (4) + (5), where (5) is implied by (4).  That should be it.


texts: Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

texts:
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.

I have asked some people who are more familiar with the research whether they think that there is a $k>0$ independent of $n$ such that there exists an $O(n^2 \log^k n)$ algorithm for matrix multiplication and they overwhelmingly seemed to have intuition that the answer is "no" but could not explain why. That is, they believe that we can do it in $O(n^{2.001})$ time, but not $O(n^2 \log^{100} n)$ time.

What reasons are there to believe that there is no $O(n^2 \log^k n)$ algorithm at a fixed $k>0$?


texts: An equation relating Time complexity, Space complexity, and entropy of output

texts:
Is there an equation that relates minimum time complexity, minimum space complexity, and entropy of the output of a function? It seems to me that there should be a relatively intuitive relationship between the three, something like $E=f(T+S)$ where $E$ is shannon entropy of the output, $T$ is time, $S$ is space, and f is a linear function or something like that. The main argument being that any function can be written as a hash map that takes its input to its output. This hashmap could be compressed based on its entropy.

I have a hunch that the only way to decrease the space an algorithm uses more than that is to increase the time complexity, as if the hashmap is moved onto a time axis instead of a space one. Is this crazy? Has there been any research done on this subject?

Edit for clarification: What I mean by "entropy of the output of a function" is this. Assume a function $g$ takes as input a bit string $x$ and outputs a message $y$. Now $g$ can thought of a source who's $x$th output is $y$. By "entropy of the output" I mean the shannon entropy of $g$ when thought of as a source.

Again, the argument is that $g$ can be implemented using a hash map in exponential space but in $O(1)$ time. However, I have a hunch that it seems reasonable that this space complexity can be reduced based on the entropy of $g$ (i.e. the entropy of the hashmap) and still maintain $O(1)$ time, essentially by compressing the hash map.

Beyond this reduction I also have a hunch that that you can decrease the space further, but in doing so you have to increase time proportionally. The idea being that you can't actually compress the information in the hash map any more than you already have (even when you compress using other measures of entropy like kolmogorov complexity), you can just "move" it along the time axis.


texts: Why Tomita created GLR and didn't use Earley?

texts:
When I look at Earley parsing, it looks very elegant, and I wonder why GLR techniques become popular? Does anyone know what was wrong with Earley parsing that Tomita created GLR?
Performance? Any publications on these discussion is highly appreciated.


texts: Computing Functions with Dynamical Systems

texts:
I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes all initial conditions - The initial tape content, starting state, initial head position) "evolves" to a specific configuration after a finite number of steps and if the function is computable, it halts with the output of the function on the tape. I am trying to draw an analogy of Turing Machines with other "time-evolving" systems and the most intuitive of all is a Dynamical System as a set of differential equations. As an attempt, I formulated a dynamical system which could compute asymptotically the square of a number.

Suppose I want to find the functions $f(x,y,t)$ and $g(x,y,t)$ such that the following dynamical system:

$\frac{dx}{dt}=f(x,y,t)$

$\frac{dy}{dt}=g(x,y,t)$

is such that:

In the phase plane (with $x$ on X axis and $y$ on Y axis), every point on the X axis is a fixed point.
Any initial point on the line y=$\alpha$ (with $\alpha\neq0 $) with coordinates $(x(0),\alpha)$ goes towards the fixed point $(x(0)^2,0)$ for $t\rightarrow\infty$

The functions $f$ and $g$ may contain the $\alpha$ term

With such a dynamical system at hand, if we wanted to compute the square of a number $a$, all we have to do is to start off with initial conditions $x(0)=a$ and $y(0)=\alpha$ (Just like we place the initial input on the Turing Machine's tape,set the initial state to the starting state and correctly position the head; In this case we place the input $a$ as the x coordinate of the initial point of the phase trajectory) and "let the Dynamical System evolve" (Just like we let the Turing Machine evolve after placing the inputs), the phase trajectory will converge to $a^2$ for $t\rightarrow\infty$ (Assuming the function to be computable, the turing machine stops in finite time and it prints the output on tape; the given dynamical system doesn't stop in finite time but it also "prints the output" as the x coordinate of the evolved phase trajectory for $t\rightarrow\infty$). In other words if we had a "machine M" following the given dynamical system, we could say that: M computes the "square" function asymptotically. (Just like the way the turing machine computes the "square" function in finite time) The computations in this case happens over reals as opposed to that over members of a countable alphabet.

But I cant really think of such functions $f$ and $g$ for computing the "square" function and I need help finding these. Furthermore if I start taking up more complicated functions to compute, finding the corresponding $f$ and $g$ will not be a trivial task. Can someone guide me on what possible difficulties I may face and how I can overcome them?

If I can formulate computation using Dynamical Systems the way I described above, is there a possibility to prove some theorems in computability (and complexity?) using these formulations?

Thankyou!


texts:
Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention:

  Build a public library of 3SAT instances, with as few variables and clauses as possible, that would have noteworthy consequences if solved.  (For example, instances encoding the RSA factoring challenges.)  Investigate the performance of the best current SAT-solvers on this library.

This triggered my question: What's the standard technique for reducing RSA/factoring problems to SAT, and how fast is it? Is there such a standard reduction?

Just to be clear, by "fast" I don't mean polynomial time. I'm wondering whether we have tighter upper bounds on the reduction's complexity. For example, is there a known cubic reduction?


texts:
A spanning tree of a graph is called a completeness tree if the set of
its leaves induces a complete subgraph in the host graph. Given a graph $G$
and an integer $k$, what is the complexity of deciding if $G$ contains a
completeness tree with at most $k$ leaves?

A reason for asking this question is that the corresponding problem for
independency trees
is NP-complete, here an independency tree is a spanning tree such that the set of its
leaves is an independent set in the host graph.

Another reason is this question
(and the corresponding answers). It turns out that every spanning tree of $G$ is a completeness tree
if and only if $G$ is a complete graph or a cycle.


texts: Are there any applications of analytic number theory in TCS?


texts: Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

texts:
Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function.

The Fourier expansion of $f$ is
$$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$
where $\widehat{f}(S)$ are real numbers and $\chi_S(T)=\Pi_{i \in S} T_i$ is a parity function.

Let $d$ be the degree of the the Fourier expansion of $f$, i.e.
$d= \max_{\widehat{f}(S)\neq 0} |S|$.

By Parseval's identity we have
$$\sum_{S \subseteq [n]} \widehat{f}(S)^2=1$$

I am looking for a bound on
$$\sum_{S \subseteq [n]} |\widehat{f}(S)|$$

I think it is bounded by $d$.
But I have neither a proof nor a counterexample for this claim. Can someone provide a proof or give a counterexample?


texts: The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

texts: In the movie Inception  Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource limited by some amount and whoever will verify that this problem is in the given complexity class that either will take more time and or space to solve. Is this a novel problem?


texts: Reference Request: Oracle applications outside cryptography

texts: Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have specifically considered applying oracles to decision problems in some specific domain/field. I am just looking for general pointers and do not have a specific domain in mind.


texts:
For a naive feature detection algorithm, I'll divide the image in 8x8 grayscale tiles. I want to be able to represent the 64 pixels of each tile in a lower dimensional form. Each tile should be an approximation of a linear combination of less than 64 tiles. What is the name for what I am trying to do? Could you point out some references to this?
I hope this is the appropriate site to ask this question.
Thanks


texts: complexity of games with just doors and keys

texts:
(This essentially copies my unaswnered question

from math.stackexchange.com/questions/275685)

I was reading http://arxiv.org/abs/1201.4995, and I thought

back to a game I used to play, which is close to being covered

by Metatheorem 3 (on page 5), but does not have one-way paths.

  What is the computational complexity of the following problem?

For an undirected graph G whose vertices have non-negative integer weights,

for vertices s and t, is there a path from s to t such that the sum of the weights

of the vertices (including s) reached at any given point along it is always

greater than the number of distinct edges traversed to get to that point?

(The vertices are not counted with multiplicity either.)


texts: Was Babbage's Analytical Engine really turing-complete?

texts:
According to literature, Babbage's Analytical Engine is turing-complete because it supports conditional branching: it can perform different operations depending on the sign of the result last operation using a conditional arm (see http://web.archive.org/web/20100426034840/http://halfbakedmaker.org/2009/12/26/rod-logic-alu-2/).

However, the instruction set as devised by Babbage seems to support only going back or jumping ahead one single punched card. (see http://www.fourmilab.ch/babbage/cards.html, "Combinaritorial Cards")
Surely this is computationally less mighty than supporting a goto-statement for jumping to arbitrary statements?

If any two turing machines can emulate each other, how can the goto-behaviour be emulated using the conditional jumping of just one instruction?


texts: Is it possible to model maximization in a petri net without using inhibitor arcs?

texts:
Creating a petri-net that models the minimum function is quite simple:

 -----     -----
   |         |
   |         |
   O         O
   |         |
   v         v
  -------------

If a tokens arrive via source 1 and b tokens arrive via source 2, min(a, b) tokens will eventually end up in the sink.

Now I would like to model the maximum function. I found a solution, but it requires the use of inhibitor arcs. Question: Is is possible to model the maximum function without the use of inhibitor arcs?


texts: Is $UP\not=NP$ with respect to random oracle?

texts:
It is shown in An average-case depth hierarchy theorem for Boolean circuits a random oracle makes $PH$ infinite.

  Is it possible to also show $UP\not=NP\not=\Sigma_2^P\not=\Sigma_3^P\not=\Sigma_4^P\not=\dots\not=PH\not=PSPACE$ with respect to a random oracle or does a random oracle give $UP=NP$?


texts: Rewrite relations - proof of correctness

texts:
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := Id(\Sigma^* \setminus (\Sigma^* \cdot dom(T) \cdot \Sigma^*)) \cup \{ \langle \epsilon, \epsilon \rangle \}
$$
$N(T)$ is the identity relation of the set of all words that don't contain an infix in $dom(T)$ including the pair $\langle \epsilon, \epsilon \rangle$.
The idea is the following - we have an input string $t \in \Sigma^*$ and $R^{obl}(T)(t)$ will result in the translation of the substrings of $t$ which $\in dom(T)$ via $Т$, and the ones $\notin dom(T)$ via identity.
Example 1: $T = \{ \langle ab, d \rangle, \langle bc, d \rangle \}$, the input text $t = babacbca$ is decomposed as $t = b \cdot ab \cdot ac \cdot bc \cdot a$ and the substrings $\{ b,ac,a \} \subseteq dom(N(T))$, whereas, $\{ab, bc\} \subseteq dom(T)$. So $R^{obl}(T)(t) = b \cdot d \cdot ac \cdot d \cdot a = bdacda$
Example 2: $T = \{ \langle ab, d \rangle, \langle bc, d \rangle \}, t = abcc$. This time we have two possible decompositions due to overlapping. $t = ab \cdot cc = a \cdot bc \cdot c$, therefore, two possible translations $\langle abcc, dcc \rangle \in R^{obl}(T), \langle abcc, adc \rangle \in R^{obl}(T)$.
My questions is - how do we formulate a proof of correctness for such a construction? That it indeed translates the words as described
A bit of a context. I've studying rewrite systems based on regular relations (implemented as finite-state transducers) and more specifically the papers "Regular Models of Phonological Rule Systems" by Kaplan & Kay (1994) and "Directed Replacement" by Karttunnen (1996). They construct complex rewrite relations by using only the regular set and relation algebra, however, the papers do not provide formal proofs that their method is correct. If anyone has experience in this field and can provide some guidance, I'll greatly appreciate it.


texts: Encoding quadratic constraints in a constraint satisfaction problem into SAT

texts:
It seems like most constraint satisfaction problems can be posed in terms of SAT.

The question is two fold:

How can any CSP with quadratic constraints be framed as a
satisfiability instance
Is there an algorithm which performs this
transformation.


texts: Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d?

texts: I'm not sure I can find an explicit formula. Wondering if anyone can come up with lower/upper bounds.


texts: Optimal random bits complexity for universal hashing

texts:
Let $Q_N:=\{0,1\}^N$ denote the $N$-dimensional Hamming cube. Let $a\in Q^N$ and $X\sim\mathrm{Unif}(Q^M)$ be input and random bits respectively, and function $f$ maps the the joint space to the $P$-dimensional cube $f:Q^{N+M}\to Q^P$. Defining hash function as $H(a):=f(a,X)$, what is the optimal $M$ if we require hash $H$ to be universal and uniform?
\begin{align}
&\Pr(H(a)=H(b))\le 2^{-P} &&\forall a,b\in Q^N, a\neq b\\
&\Pr(H(a)=c)=2^{-P} &&\forall c\in Q^P,a\in Q^N
\end{align}I'm interested in constructive answers, where $f$ can explicitly designed.


texts:
First of all I am of course aware of the wikipedia article: http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

However I still do not understand exactly what the problem is. To demonstrate that I've tried, I think it is as follows but I am not sure:

  The problem of checking whether a given boolean equation with k distinct
  variables is satisfiable.

For example, is this an instance of the 3-sat problem?

x OR y OR z


texts: Assume that Discrete logarithms can be solved in linear time over any group (hence factorization is also trivial by a result of Eric Bach), is there any other candidate public key exchange problem that will facilitate computationally secure key exchange?


texts: Are there any conditions for which ($k$-)apexness is preserved under $Y-\Delta$ transformations?

texts:
Lately, something I've been interested in is finding the set of forbidden minors for the apex graphs. One thing I tried to do was to look at the graphs which were known, and try to find a pattern in the planar subgraphs that result from deleting two vertices. However, when trying this on the Petersen family, what came out of it didn't look that nice. Luckily, the $Y-\Delta$ transformations give a simple characterization of the Petersen family as the equivalence class containing, say, $K_6$ under $Y-\Delta$ transformations.

After some preliminary googling, I came across a blog post by David Eppstein in which he lists a bunch of forbidden minors for apex graphs by carefully attaching copies of $K_5$ and $K_{3,3}$ together. I was hoping to find some more not listed there (besides the trivial disjoint unions of $K_5$ and $K_{3,3}$) using $Y-\Delta$ transformations, but found that sometimes the resulting graphs are apex. Is there any characterization (or just weak conditions) of when apexness is preserved?


texts: Diameter of Cayley graphs of subgroups of $S_n$ without inverses

texts:
Babai and Seress proved that given a subgroup $G \leq S_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators and their inverses of length $e^{(1+o(1))\sqrt{n\log n}}$. This bound is optimal since $S_n$ has an element of order $e^{(1+o(1))\sqrt{n\log n}}$.

The classical fact that every element in $S_n$ has order at most $e^{(1+o(1))\sqrt{n\log n}}$, combined with the result of Babai and Seress, shows that given a subgroup $G \leq S_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators of length at most $e^{2(1+o(1))\sqrt{n\log n}}$.

  Can we improve the upper bound $e^{2(1+o(1))\sqrt{n\log n}}$ to $e^{(1+o(1))\sqrt{n\log n}}$?

This question has been inspired by the recent question Automata and a kind of pumping lemma on state transition function.


texts: Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability

texts:
A generalized sequential machine (GSM) is a generalization of a Mealy machine where on each transition one input symbol is read and 0 or more output symbols are written. As in a Mealy machine, we assume that there are no final states, i.e. a GSM operates on infinite input/output words. A GSM has finitely many states.

Assume $A$ and $B$ are two single-valued GSMs and $C$ is a not necessarily single-valued GSM. Single-valued means that for each infinite input word there is at most one infinite output word (determinism is a sufficient but not necessary condition for single-valuedness). Suppose in addition that $A$ and $C$ are fully reachable, i.e. there is a path from the start state to every other state. In the following, two GSM synthesis problems are described. Let $T_X$ denote the set of states of GSM $X$.

Are there single-valued GSMs $X$ and $Y$ such that $X \circ A \equiv Y \circ B$ and in $X \circ A$ for every $t \in T_A$ there is a state $(\_, t) \in T_X \times T_A$ reachable from the start state, i.e. $A$ remains fully reachable in $X \circ A$? Note that $\circ$ denotes transducer composition.
Are there single-valued, finite state transducers $X$ and $Y$ such that $X \circ C \supseteq Y \circ B$ and in $X \circ C$ for every $t \in T_C$ there is a state $(\_, t) \in T_X \times T_C$ reachable from the start state, i.e. $C$ remains fully reachable in $X \circ C$?

Clearly, 1. is semi-decidable and 2. is undecidable if $C$ is non-deterministic (without restriction, i.e. infinitely-valued). However, is 1. decidable and if so what is the complexity? For it to be decidable it must be possible to bound the number of states of $X$ and $Y$. Moreover, is 2. decidable if $C$ is finitely-valued, i.e. there is a bounded number of infinite output words for each infinite input word? I'm particularly interested in symbolic methods, also references to practical bounded synthesis approaches. I appreciate any hints that relate this problem to a standard problem as well. Thanks for your input.


texts: Does Standard ML validate (CBV) eta equivalence?

texts:
$\eta$ equality of functions is fundamental in their Category-theoretic semantics but in practice even "functional" languages include "impure" features that violate it.
Note that this is not an issue of CBN vs CBV, in CBN eta equality $M = \lambda x. M x$ should hold for any term $M : A \to B$ whereas in CBV this will be restricted to values $V = \lambda x. V x$. The CBV $\eta$ equality has a perfectly good category-theoretic explanation, see Levy's Call-by-push-value.

Haskell includes seq, which can distinguish between (\x -> error "") and error ""
OCaml includes operations like "physical equality" (==), and which will distinguish fun x => x from fun y => (fun x => x) y because == corresponds to pointer equality.

So I wonder do any "real" languages satisfy eta for observational equivalence at all?
All the better if it is known that a (correct) compiler implementation performs eta reductions just based on the type.

The only example I know of is Coq which includes it as a definitional equality as of a recent version. Maybe similar languages (Agda, Idris) do as well. These are not surprising because they include an equality type and it is very frustrating to prove equality of functions without $\eta$ or the stronger(?) extensionality principle.

My main question is about Standard ML specifically which I think does not have pointer equality for functions. Does it satisfy the CBV $\eta$ law? Furthermore do compilers for SML such as MLton use $\eta$ when optimizing programs?


texts: Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?

texts:
$\DeclareMathOperator*{\argmin}{arg\,min}$Can something be said about the difficulty of minimizing the quantity

$$g(x) = \sum_{i=1}^n\sum_{j=i+1}^n f(x_i, x_j)$$

of some string of symbols $x \in \Sigma^n$ solely through permuting $x$? That is, finding

$$\underset{\sigma\in S_n}{\argmin}\ g(\sigma(x))$$

$f: \Sigma \times \Sigma \to \mathbb{R}$ is here a black-box function with no other properties.


texts: I want to ask if strong coloring of a k-uniform hypergraph using only k colors is NP-Hard or NP-Complete? If you can add a reference this will be helpful.


texts:
Suppose I want to find the rank of an $m \times n$ matrix $A$ over $GF(2)$, where $m \ll n$. The algorithms for rank in the literature seem to be focused on the case when $m = n$, giving a time complexity of $O(log^2 n)$ and $n^{4.5}$ processors. Are there better algorithms known when $m$ and $n$ are very different? I am thinking that $m \approx \text{polylog}(n)$.

In the case when $m = c \log n$, then one can simply exhaust over all $2^m$ subsets of the rows of $A$, and this is actually more efficient than Gauss elimination.


texts: Algorithm to go from a picture (or pictures) of a string in space, to a piecewise-linear representation of the curve

texts:
Say you have a knotted-up string or, as in this case, USB cable:

I am wondering to what extent there are algorithms that could turn a picture like this (or a succession of pictures of the same object) into a proper 3d mathematical representation of the object?

For example, I would be happy with a 1-dimensional polygon in $\mathbb R^3$ that describes the rough shape of a cable, given in a picture like the above.  It would be useful if the algorithm could tell the difference between an "open" knot and a closed knot -- meaning the knot is a (possibly tangled) loop, vs just some length of string with free ends.

In the case of the above picture, I would be happy with output a list like:

$$ (-2,0,0) \to (1,0.2,0) \to (1,-1,1) \to (-1,-1,-1) \to (-1,0.2,-1) \to (-1,0.2,1) \to (1,0,-0.2) \to (2,0,0) $$

from the algorithm.  Roughly the $(x,y,z)$ coordinate corresponds to the picture with the x-axis horizontal, the y-axis vertical, and the z-axis would be into the table.

Are there any algorithms out there that are (?close?) to capable of such a task?

Apologies in advance if I am using inappropriate tags.


texts: Studying the hardness of polynomial-time approximability using the concept of stability of approximation

texts:
In the Conclusion section, the author of this paper "Stability of Approximation Algorithms for Hard Optimization Problems" by Juraj Hromkovič, 1999 claims that

  Using the notion of stability one can search for a spectrum of the hardness of a problem according to the set of inputs. For instance, considering a hard problem like TSP one could get an infinite sequence of input languages $L_0, L_1, L_2, \ldots$ given by some distance measure, where $\epsilon_r(n)$ is the best achievable relative error for the language $L_r$.

As I understand, the notion of stability of approximation is relative to a specific problem $Q$ (e.g., TSP above), a specific approximation algorithm for some subproblem of $Q_0$ (corresponding to $L_0$ above), and a specific distance measure. Given that, how can we construct a spectrum of the hardness of of problem $Q$ according to their polynomial-time approximability? Specifically, how to show that "$\epsilon_r(n)$ is the best achievable relative error for the language $L_r$" using the concept of stability of approximation?

Concrete examples are appreciated.


texts: Problems that are decidable but cannot be verified in polynomial time

texts:
While working on a somewhat unrelated project for Suresh I recently came across some work done by Page and Opper about User-Composable systems and a portion of their work briefly discussed problems that cannot be verified in polynomial time.  I have been unable to find much information about other problems that cannot be verified in polynomial time or an analysis of a such a problem.  I was wondering if any of you knew of any such problems and/or how to analyze them.

As stated in the comments a better way to phrase this question is:
What problems are decidable but outside of NP?


texts:
I'm pretty sure this has a trivial answer but it's always faster to ask the community :-)

I understand that, relative to a random oracle, P=BPP. But this is sometimes phrased via the shorthand "Almost-P=BPP", which I find rather confusing.

Complexity zoo defines Almost-P as "The class of problems that are in $P^A$ with probability 1, where A is an oracle chosen uniformly at random."

Logically, L belonging to Almost-P would then mean that: With probability 1 over a random instantiation of an oracle tape A, there is a polynomial time Turing machine T(A) that decides L.

Now, the poor BPP machine trying to decide L would have no idea which T(A) to simulate. The choice of T(A) may wildly vary depending on A.

Should Almost-P (similarly, Almost-anything) be rather defined as the set of languages L for which there is a polynomial time Turing machine T with an oracle tape such that, with probability 1 over the instantiation of the oracle tape, the language decided by T ends up being L?

Under neither of the above definitions does the statement BPP=Almost-P seems to be logically equivalent to "relative to a random oracle A, $P^A=BPP^A$".

My question is now, what is the precise definition of the class Almost-P (or, for that matter, Almost-anything)? And/or, what am I missing above?


texts: Searching for the original definition of online algorithms

texts:
I'm currently searching for the original formal definition of online algorithms. The earliest mentions of online algorithms that I found are from the mid 80s. But none of these papers seem to be the one that was the original reference.

Note: English is my second language.


texts: Best known algorithm for a common problem.

texts:
I am looking for the best known algorithm for the following problem:
Input: Matrix M with R rows and C cols and values true-false in each position
Output: Minimum number of cols such that the OR operation between all selected cols results in R trues.

I think another form of this problem is: Given C numbers of N bits, get the minimum amount of numbers needed to sum 2^N - 1.

In case this is NP-Complete, then does someone know where can I find the reduction? And is there any pseudo-polynomial algorithm? Maybe using dynamic programming on some bounded variable?

Thanks in advance.


texts: Big O notation for "modulo a polynomial"

texts:
Is there a notation that would be like the Big O notation (let's say Big P), but with the following definition:

$f=P(g)$ if there exists a polynomial p such that for n large enough, $f\leq p(g(n))$?

It would be quite useful when establishing the complexity class of some problems. If one wants to prove that a problem is in EXPTIME for example, when establishing the complexity of some decision procedure, it is a bit annoying to carry details like $2^{O(np(1+p))}$, when we only need to know that it is exponential in $n+p$. It would be simpler to write $2^{P(n+p)}$. The last time I asked someone, he did not have the answer but had just faced the same situation and wondered also if such a notation exists.


texts: Confusing (to me) statement from "Type Classes in Haskell"

texts:
I'm reading up on type classes, and started looking at the paper Type Classes in Haskell.

In Section 2.2 - Superclasses, the authors use the following example:

class (Eq a) => Ord a where
   (<)  :: a -> a -> Bool
   (<=) :: a -> a -> Bool

Then, they proceed to state that "This declares that type a belongs to class Ord if there are operations (<) and (<=) of the appropriate type and if a belongs to class Eq. Thus, if (<) is defined on some type, then (==) must be defined on that type as well."

The second sentence does not make any sense to me; why would a type that defines (<) have to define (==) if it is not declared to be an instance of either Ord or Eq?


texts: Is linearizability equivalent to consensus problem?

texts:
In the introduction of this paper Eventually Linearizable Shared Objects (PODC'10), the authors have presented the following statement without references:

  Linearizability, however, can be achieved if and only if consensus can be solved.

Here, linearizability is the strongest known consistency property of shared objects, which is proposed in the paper Linearizability: A Correctness Condition for Concurrent Objects.

I get confused about the above statement due to the following arguments:

In the paper Sharing Memory Robustly in Message-Passing Systems (JACM95), we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes:

  Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected.

On the other hand, the paper Impossibility of Distributed Consensus with One Faulty Process (JACM85) has proved the impossibility result of consensus even with only one process crash:

  The consensus problem  involves  an asynchronous system of processes, some of which  may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of  nontermination, even with only one faulty process.

Therefore, can we reach the following conclusion:

  consensus is stronger than linearizability?

What is wrong with my arguments? Are there some direct references for the equivalence conclusion?


texts: Relation between interval temporal logic and linear temporal logic

texts:
I am trying to understand the relation between interval temporal logic and linear temporal logic. Do the two form of expressing temporal constraints have the same expressive power, or is one of the two more expressive?

I found a proof of the ability of translating Allen Interval temporal logic formulas into linear temporal logic formulas (http://fsl.cs.uiuc.edu/index.php/Allen_Linear_(Interval)_Temporal_Logic_-Translation_to_LTL_and_Monitor_Synthesis-), but I couldn't find much info for the other direction.


texts: Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$?

texts:
A complete problem for $\mathsf{PPP}$ is the pigeon problem which is 'Given a Boolean circuit ${\displaystyle C}$ having the same number ${\displaystyle n}$ of input bits as output bits, find either an input ${\displaystyle x}$ that is mapped to the output ${\displaystyle C(x)=0^{n}}$, or two distinct inputs ${\displaystyle x\neq y}$ that are mapped to the same output ${\displaystyle C(x)=C(y)}$'.

$\mathsf{PPP}$ contains functional version of integer factorization, discrete logarithm etc. (page $148$ in https://simons.berkeley.edu/sites/default/files/docs/15391/ppp.pdf is reference). Decisional version of the problems are in $\mathsf{UP}$. So is $\mathsf{PPP}\subseteq\mathsf{FP}^\mathsf{UP}$ or $\mathsf{UP}\subseteq\mathsf{P}^{\mathsf{PPP}}$ believed?

Similarly is $\mathsf{TFNP}\subseteq\mathsf{FP}^\mathsf{UP}$ or $\mathsf{UP}\subseteq\mathsf{P}^{\mathsf{TFNP}}$ believed?


texts: What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)?

texts: I am planning to join a CS Ph.D. program in 6 months. My topics of research will be in the area of Reinforcement Learning and Game Theory. Even though I have a good grasp of these two topics’ applications and empirical side, I struggle with the theory a lot when reading papers. For example, It is taking me a lot of time to understand the regret analysis of advanced Bandits. I have taken most of the essential math courses during my undergrad, including Differential + Integral + Multivariate calculus, Linnear Algebra, Probability, Stat, etc. But I feel most of those courses did not go deep enough. So I want to revisit some of my undergrad math and would also like to learn additional topics. Given my area of Ph.D., I would like to know the essential math topics I should study in the next six months to have a good grasp on the theoretical side and do well in graduate-level courses consistent with such a Ph.D.


texts: The regularity of Markov chains with a threshold

texts:
(This question has been asked on math.se, with no response.)

I am studying Paz's "Introduction to Probabilistic Automata" and there is an exercise I cannot solve:

  Ex. 11, p. 170: Let $\Sigma = \{a\}$.  Show that the number of nonregular events of the form $\{x \mid p^A(x) > \lambda\} \subseteq \Sigma^*$, where $A$ is a given $n$-state probabilistic automaton over $\Sigma$ is $\leq n$.

(Recall that a probabilistic automaton is simply an automaton where each transition has a given probability of crossing; then  $p^A(x)$ is the probability of acceptance of $x$, that is, the probability that starting from the initial state the automaton reaches a final state after $|x|$ transitions.)

I can rephrase it, for instance, as:

  Let $M$ be a stochastic matrix of dimension $n \times n$ and $a$ be a letter.  There are at most $n$ different values of $\lambda \in [0,1]$ for which  $\{a^k \mid (1, 0, \ldots, 0)M^k(0,\ldots,0,1)^{\mbox{T}} > \lambda\}$ is nonregular.

I am strongly interested in the form those nonregular languages may have, so this could be a good start.  Any help?