texts: Is scalable hardware support for LogCFL (= sAC^1) possible?

texts:
The (uniform) circuit classes $TC^0$, $NC^1$ and $sAC^1$ seem to lend themselves to efficient hardware implementation. But using an FPGA approach to create the circuits on the fly seems problematic, because the wiring could destroy the theoretical speed benefits.

A more promising approach could be to look for problems complete under appropriate many-one reductions for these classes. The word problem for $\bar{A}_5$ (or $\bar{S}_5$) would be such a problem for $NC^1$. The solution of that word problem is nicely scalable, since one can subdivide the word into smaller parts, and thereby generate a smaller word on which the same procedure can be applied again.

Is something similar also possible for LogCFL ($= sAC^1$)? Does it have a nice problem (probably some CFL) complete under $NC^1$ reductions? And is the solution of that CFL scalable in a way that hardware solutions to subproblems can easily be combined to the total solution?

Or does the dynamic programming algorithm which can solve LogCFL allows scalable hardware support in some way?


texts: Why economists should care about computational complexity

texts:
When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and chapter 11 of Scott Aaronson's essay. These posts are accessible for computer scientists, but do not use the language of economists and are not published in venues typically read by them. Are there good arguments for the importance of the complexity of equilibiria, etc. targeted at economists? Is there a good historic overview of how economists have responded to pressure from computer scientists?
It could be argued that neoclassical economics is simply closed off and hence such papers can't exist, but there are slightly heterodox fields such as evolutionary economics and complexity (in the SFI sense) economics that justify themselves in language familiar to economists. These fields also make similar critiques as the computational complexity approach (such as moving away from assumptions of equilibria), but don't justify them as rigorously as CS does.

Related questions

Algorithmic lens in the social sciences

Computational complexity in quantitative finance


texts:
I am wondering if this is a studied variant of the Set Cover problem.

We are given a universe $X$, a collection of sets $S = \{S_1, ..., S_m\}$ and integers $c_i$.  We want to cover all elements in $X$ with sets $S'_i \subseteq S_i$ such that $|S'_i| \leq c_i$.  In other words we want to cover the elements with as few sets as possible but we are only allowed to use $c_i$ elements of each set.

The most similar variant I found is described in "Maximum Coverage Problem with Group Budget Constraints and Applications"

Thank you


texts:
Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution.

For two bins and uniform distribution, this problem is similar to the partition problem. I know there is a simple greedy algorithm for that but I could not generalize it for my problem.


texts:
There is a definition of a 'monotone machine' in Li &  Vitany's Book, and another one which is for example stated in this paper via c.e. (computably enumerable) sets. I can't see why these definitions should be equivalent.
Furthermore in Li & Vitany's book, there is a statement which says that monotone machines compute p.r. (primitive recursive) functions f with $f(x) \le f(y)$ when $x \le y$ (lexicographical ordering).
I don't see how such a function can be computed by a monotone machine.

Maybe someone can explain this to me or refer to a paper / book which descripes these connections.

Thanks

edit:
The first definition:
A monotone machine has a one-way read-only input tape, a one-way write-only output tape and work tapes. The input is read one bit at a time, and the output written one bit at a time, with the one-way nature of the output tape allowing no revisions. For such a machine M, we have M(x) terminates with output y, where x is a finite string and y is a possibly infinite string, if either M halts after reading the bits of x from the input tape and y is what is on the output tape at that point, or M computes forever after reading exactly the bits of x, and y is on the output tape on the limit.

The second one:
A monotone machine L is a c.e. (computably enumerable) set of pairs of finite strings such that if , is in L and $x \le x'$ then $y$ and $y'$ are comparable (i.e. $y \le y'$ or $y' \le y$).


texts:
Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the maximum load, and throw them to random bins.

What the expected number of balls in the bin with the maximum load is converges to?

A variation of the problem is described in https://www.cs.tau.ac.il/~azar/box.pdf, where instead of taken  the bin with the maximum load, a random ball is  selected at random.

In addition, by my experiments, it seems that for $n=\Theta(m)$ the bin with the maximum load converges $2n/m+1$ balls. I am trying to prove  it.


texts:
A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are incident on the same vertex. It is known that the minimum number of colours required for edge colouring is between $\Delta(G)$ and $\Delta(G)+1$, and yet it is NP-complete to distinguish between the two cases.
Let us define a relaxed $k$-edge colouring of $G$ as a function $f:E\to\{1,2,\dots,k\}$ such that for every vertex $v$ of $G$, at most two edges incident on $v$ have the same colour.
What is the complexity of relaxed edge colouring?
I am particularly interested in the complexity of relaxed $k$-edge colouring for graphs of maximum degree $k$.
Edit: The part below was part of the question earlier. But, it is wrong because proper $k$-edge colouring and thus relaxed $k$-edge colouring are trivially in P for graphs with maximum degree $k-1$.

I am particularly interested in the complexity of relaxed $k$-edge
colouring for graphs of maximum degree $k-1$. I have a hunch the
problem is going to be computationally hard, which is interesting
because $k$-edge colouring is polynomial time solvable for the class.


texts: How would a theory of computation course that culminated in lambda-calculus as "the" model of computation, instead of Turing machines, look like?

texts:
Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics:

Finite automata and regular languages
Pushdown automata and context-free languages
Turing Machines
Undecidability and TMs
Complexity classes (P, NP etc.)

If one were to redesign the ToC course where TMs in #3 and #4 above would be replaced by $\lambda$-calculus how would the rest of the course look like? That is, what would we teach in place of #1 & #2 above to progressively lead to $\lambda$-calculus? Also, could there really be chapter on complexity classes with $\lambda$-calculus as THE model of computation?


texts: Real number $p$ such that a $p$-coin makes the undecidable decidable

texts:
This is an exercice from Arora & Barak, Chapter 7 :

  Describe a real number $p$ such that given a random coin that comes up
  "heads" with probability $p$, a Turing machine can decide an undecidable
  language in polynomial time.

This follows a discussion about the fact that if $p$ is efficiently computable, then it's no better than a $1/2$-coin.  But if $p$ can be anything, we get new powers.  I guess in this case the way to do is to recover the bits of $p$, but I can't think of a deterministic way to do so.

EDIT : based on comments, this question doesn't seem clear.  I'll rephrase it like this, based on my interpretation of 'decide' (if I'm wrong, please let me know):

  Describe a real number $p$ such that given a random coin that comes up
  "heads" with probability $p$, there exists an undecidable language $L$ and a Turing machine $M$ such that $M$ runs in polynomial time, and on input $x$, $M$ outputs $1$ if and only if $x \in L$.

Note that stated like this $M$ makes zero error.


texts: Is there a 'process algebra' to describe ACID transactions on a database?

texts:
There appears to be this beautiful algebra to help you think through the implications of Communicating Sequential Processes by Hoare.

What I'm wondering, is there an equivalent algebra that helps you think through ACID transactions on a database, where one suceeds and another rolls back?


texts: Counting solutions to extended MSO formulas, and sampling -- do these appear in the literature?

texts:
I am trying to determine if the literature contains various extensions of Courcelle's theorem. Since I haven't been able to find these in the literature, I guess that these are folklore results, or else false, since it seems that their proofs are only a few steps away from what appears in the literature already.

Background:

1) $EMS$ is an extension of $MSO$ that, among other things, allows the comparison of the cardinality of set variables. See the discussion around definition 3.4 of this paper for a more precise description.

It is proven in the previously linked paper (Theorem 5.4) that $EMS$ decision problems are $XP$ in the tree-width.

2) It is proven in the same paper (Theorem 5.7) that $MSO$ counting problems are $FPT$ in the tree-width. (The definition of an enumeration problem appears on the top of page 317.)

Question 1: I think it is also true that $EMS$ counting problems are $XP$ in the tree-width. Does anyone know if this is explicitly stated anywhere in the literature?

Proof sketch for the claim of question 1: The broad steps of the argument should be the same as the proof of Theorem 5.7: one can polynomial time interpret the class of graphs of tree-width $\leq m$ into the class of rooted binary trees as described theorem 4.5. The transformation of an EMS problem $P$ on graphs into a corresponding EMS problem over binary trees induces a bijective correspondence of solution sets (remarks on page 322). Then, similarly to what is described prior to Theorem 5.7, the evaluation of the $MSO$ formula tree-automata on the labelled tree will be modified keep track of counts for the number of occurrences of all possible pairs of $(\text{tree automata state}, \text{evaluations})$ at each node of the tree. The total number of solutions can then be read off of the root by summing up the counts of all of the  $(\text{tree automata state}, \text{evaluations})$ pairs at the root node that satisfy the $EMS$ formula. This will be pseudopolynomial in the total (multiplicative) height of the coefficients of the evaluations, since one will need a tree-automata-states-many counters for each possible sub-evaluation. (The number of tree-automata-states is constant, since it is determined by the $MSO$ formula, but the number of sub-evaluations grows pseudopolynomially.)

Similarly:

Question 2: Likewise, one should obtain in the same way an algorithm for computing generating functions for the set of solutions to an EMS formula over some given weights, as in this paper by Courcelle et al.. Does this appear in the literature anywhere?

Question 3: The same general kind of argument would show that it is possible to count the number of solutions to some formula $\phi(X,A,B)$ where $X$ is a free variable, and $A$ and $B$ are set-valued parameters, $FPT$ in tree-width if $\phi \in MSO_2$ or $XP$ in tree-width if $\phi \in EMS$ (with a constant that depends on the tree-width and $\phi$, not the choice of $A$ and $B$). In particular, by defining $\phi(X,A,B) = \psi(X) \wedge ( A \cap X = \emptyset) \wedge ( B \subseteq A)$, where $\psi \in MSO$ (resp. EMS), this means that one can make the necessary marginal counts in order to uniformly sample from the set of solutions to $\psi$ $FTP$ in tree-width (resp. $XP$ in tree-width). Similar (pseudopolynomial) statements for sampling from distributions of sets where probabilities are proportional to multiplying node/edge weights over the subset also ought to exist by similar reasoning. Does a statement like this about tree-width FPT/XP algorithms for MSO/EMS sampling problems appear in the literature anywhere?

Thank you for reading!


texts:
It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is Yutsis graph). The preceding two example problems demonstrates what I mean by natural interesting property of cubic graphs.

Another natural interesting property of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer using his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which natural interesting problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

  Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

As it is apparent from the examples, I'm only interested in decision problems where the validity of a solution can be expressed independent of the solution size. I require that the solution has a specific structural property. Bach's post may help in clarifying my motivation. My answer to Bach's post which involves the efficient dominating set problem ( 1-perfect code ) on cubic graphs is a perfect example for natural interesting property of cubic graphs.

Another famous natural interesting property of cubic graphs is being Hamiltonian. Also, it may not be obvious, I'm only interested in natural interesting properties of connected cubic graphs.

EDIT 1-30-2014:  To capture the essence of natural property of cubic graphs, I accept a natural $NP$ property $X$ of cubic graphs where there is natural efficient verifier that verifies a natural interesting relation $(x, c)$ where $x$ is an input instance (i.e. connected cubic graph) and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier. Such natural $NP$ property must partition the class of cubic graphs into two infinite sets.


texts: Languages whose Parikh image is recognizable

texts:
Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By Parikh's theorem, every context-free language is a slip-language. But not every slip-language is context-free. For example, the commutative closure of $(abc)^*$ is not context-free.
In $\mathbb N_0^k$ with $k = |\Sigma|$, the semilinear set are precisely the rational sets. The recognizable set in $\mathbb N_0^k$ are finite unions of sets of the form $R_1 \times \ldots \times R_k$, with each $R_i$, for $i \in \{1,\ldots, k\}$, either finite or ultimately periodic.
The slip languages are an established concept. For example, we have work from the 70's, and such neat results as that the commutative closure of binary slip languages is context-free.
Now I am just curious. Is there anything known, or is there any research, on languages whose Parikh image is recognizable?
As recognizability is preserved under inverse homomorphism, the commutative closure of such a language is regular. But, there exist non-regular languages whose Parikh image is recognizable. For example, the language given by the context-free grammar $A \to aBaA | \varepsilon, B \to bAbB |\varepsilon$. It has the commutative closure
$$
 \{ w \in \{a,b\}^* \mid |w|_{a} \equiv 0 \pmod{2}, |w|_b \equiv 0 \pmod{2},
 |w|_a \ge \min\{1, |w|_b\}. \},
$$
where $|w|_a$ and $|w|_b$ denote the number of $a$'s, respectively $b$'s, in $w$.
EDIT (8/5/2020): There was an error in the specification of the context-free grammar. I corrected it. Also I will give the proofs, just to be on the safe side. Let $L$ be the language generated by the grammar. Suppose it where regular with pumping constant $N$. Consider $w = (ab)^N(ba)^N \in L$, and let $v$ be some pumpable factor in $(ab)^N$. As any word in $L$ must have even length, this factor itself must have even length. Hence it starts with different symbols. So, we either have $w = (ab)^x(ab)^y(ab)^z(ba)^N$ with $N = x+y+z$ and $v = (ab)^y$, or $w = (ab)^xa(ba)^yb(ab)^z(ba)^N$ with $N - 1 = x+y+z$ and $v = (ba)^y$. But in either case, none of the pumped up strings would be in $L$, as they still only contain $bb$ as a factor with two consecutive equal symbols. But if the factor $bb$ (or $aa$) only appears once in a given word from $L$, it must have the form $(ab)^k(ba)^k$ or $(ab)^{k-1}aa(ab)^{k-1}$ for some $k > 0$. Alternatively, we could note that an infinite accepting automaton is given by the state set $\{1,2,3,\ldots\}$, with the letter $a$ interchanging $1$ and $2$, $3$ and $4$, and so on, and $b$ interchanging $2$ and $3$, $4$ and $5$ and so. As this is a permutation automaton with the single final state $\{1\}$, it is minimal.
Finally, as $(aa)^{n-1}a(bb)^ma \in L$ for each $m \ge 0$, $n > 0$, and $(aa)^m \in L$ for each $m \ge 0$, and every word in $L$ has an even number of $a$'s and $b$'s, the claim about the commutative closure is implied.


texts:
Einstein summation is a convenient way to express tensor operations which has found its way in tensor libraries like numpy, torch, tensorflow, etc.
Its flexibility lets us represent the product of three matrices, $X$, $Y$, $Z$  of dimensions $(a,b)$, $(b,c)$, $(c,d)$ as
X.Y.Z = einsum('ab,bc,cd->ad',X,Y,Z)

However, the above compiles to something like
for a_ in range(a):
  for d_ in range(d):
     res[a_,d_] = 0
     for b_ in range(b):
        for c_ in range(c):
           res[a_,d_] += X[a_,b_] * Y[b_,c_] * Z[c_, d_]

This native is quadratic in the size of the matrices when simply doing
einsum('ac,cd->ad',einsum('ab,bc'->'ac', X, Y), Z)

Would be merely cubic.
There are roughly three levels of optimization we can imagine a smarter implementation of einsum to perform.

Decompose an einsum of tensors $(x_1, \ldots, x_n)$ into an einsum of pairs of tensors $x_1, x_2$, $e(x_1, x_2), x_3$, etc to optimize computation time.

Rely on associativity (where applicable) to pick those pairs judiciously (this is a classic dynamic programming problem) and construct the appropriate intermediary tensors.

Discover Strassen-like formulas for the specific tensor computation

While 3 seems clearly out of reach, 1 and 2 seem like they could be achievable exactly with a reasonably straightforward algorithm. Are such algorithms known for generic einstein summations? Have they been studied?


texts: Maximizing a convex function with linear constraints

texts:
I have the following optimization problem:
$$
\arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\}
\mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq 1,\forall p=1,\ldots,M,
$$
where $a_{ij} \geq 0,\forall i,j$. The objective function is clearly convex since $\max_{p}\{\phi_p a_{ip}\}$ is convex in $\{\phi_p\}$.

I realize that, in general, convex maximization problems can be NP-hard but I was wondering whether there are any known efficient solutions for this specific problem structure.

I apologize but there was a typo in my question. The constraint is supposed to be $\sum_{p}\phi_p\leq K$. Hence, I need to search over ${M\choose K}$ vertices, which may be an exponential number of vertices if $K=O(M)$.


texts:
Given a word $w$ over $\{ [, ] \}$, the alphabet of the two square brackets, the Dyck correction problem is to find the shortest sequence of edit operations that would make $w$ a Dyck word, i.e., a word in which the squared brackets are balanced.
I can imagine a few practical applications, but my bibliography search yielded nothing. It looks like dynamic programming though. Any ideas?


texts:
I am reading this recent paper by Schrijver, in particular, section 4.2: Enumerating homologies of disjoint paths.
I did not understand how do they re-route the paths through a spanning tree and obtain the walks with the mentioned properties, so I decided to work out an example. This is what I have:

A planar graph with two pairs of terminals and want to find vertex disjoint paths between them (that is $F=\{\{1,2\}\}$). I have also marked a spanning tree $T$ (purple highlighted edges) and numbered the edges $e_1, e_2, e_3, e_4$ not in the tree such that if $Q_{e_j}$ is longer than $Q_{e_i}$ then $j > i$.
(I haven't marked the direction of the edges because we are considering undirected walks)

Now I have marked two disjoint paths between the terminals. And according to the algorithm next I am supposed to eliminate $e_2$ from $P_2$ and then $e_4$ from $P_1$.

But notice that the two walks now cross each other at the top-middle vertex, but the algorithm claimed that the walks obtained will be non-crossing.
Can someone please point out my mistake. Any help would be really appreciated.

Even in this 1994 paper, they described a way to enumerate homologies but this method, as it is described, seems more difficult for me to understand.

Edit: Following is the only way, I was able to find, to re-route those paths through the tree, but as far as I understand, this is not what the paper describes.


texts: Finding k shortest Paths with Eppstein's Algorithm

texts:
I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works
and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap construction $H(G)$.

So far:

$out(v)$ contains all edges leaving a vertex $v$ in a graph $G$ which are not part of a shortest path in $G$. They are heap-ordered by the "waste of time" called $\delta(e)$ when using this edge instead of the one on a shortest paths. By applying Dijkstra I find the shortest paths to every vertex from $t$.

I can calculate this by taking the length of the edge + (the value of the head vertex (where the directed edge is pointing to) - the value of the tail vertex (where the directed edge is starting). If this is $> 0$ it is not on a shortest path, if it is $= 0$ it is on a shortest path.

Now I build a 2-Min-Heap $H_{out}(v)$ by heapifying the set of edges $out(v)$ according to their $\delta(e)$ for any $v \in V$, where the root $outroot(v)$ has only one child (= subtree).

In order to build $H_T(v)$ I insert $outroot(v)$ in $H_T(next_T(v))$ beginning at the terminal vertex $t$. Everytime a vertex is somehow touched while inserting it is marked with a $*$.

Now I can build $H_G(v)$ by inserting the rest of $H_{out}(w)$ in $H_T(v)$. Every vertex in $H_G(v)$ contains either $2$ children from $H_T(v)$ and $1$ from $H_{out}(w)$ or $0$ from the first and $2$ from the second and is a 3-heap.

With $H_G(v)$ I can build a DAG called $D(G)$ containing a vertex for each $*$-marked vertex from $H_T(v)$ and for each non-root vertex from $H_{out}(v)$.

The roots of $H_G(v)$ in $D(G)$ are called $h(v)$ and they are connected to the vertices they belong to according to $out(v)$ by a "mapping".

So far, so good.

The paper says I can build $P(G)$ by inserting a root $r = r(s)$ and connecting this to $h(s)$ by an inital edge with $\delta(h(s))$. The vertices of $D(G)$ are the same in $P(G)$ but they are not weighted. The edges have lengths. Then for each directed edge $(u,v) \in D(G)$ the corresponding edges in $P(G)$ are created and weighted by $\delta(v) - \delta(u)$. They are called Heap Edges. Then for each vertex $v \in P(G)$, which represents an edge not in a shortest path connecting a pair of vertices $u$ and $w$, "cross edges" are created from $v$ to $h(w)$ in $P(G)$ having a length $\delta(h(w))$. Every vertex in $P(G)$ only has a out going degree of $4$ max.

$P(G)$'s paths starting from $r$ are supposed to be a one-to-one length correspondence between $s$-$t$-paths in $G$.

In the end a new heap ordered 4-Heap $H(G)$ is build. Each vertex corresponds to a path in $P(G)$ rooted at $r$. The parent of any vertex has one fewer edge. The weight of a vertex is the lenght of the corresponding path.

To find the $k$ shortest paths I use BFS to $P(G)$ and "translate" the search result to paths by using $H(G)$.

Unfortunately, I don't understand how I can "read" $P(G)$ and then "translate" it through $H(G)$ to receive the $k$ shortest paths.


texts: Drunken birds vs drunken ants: random walks between two and three dimensions

texts:
It's well known that a random walk in the two dimensional grid will return to the origin with probability 1. It's also known that the same random walk in THREE dimensions has a probability strictly less than 1 of returning to the origin.

My question is:

  Is there something in between ? For example, suppose my space was
  actually a bounded region of the plane extruded out to infinity in the
  z-direction. (what's often called 2.5 dimensional). Do the
  two-dimensional results apply, or the three dimensional ?

This came up in discussions, and one heuristic argument saying that it behaves two dimensionally is that since the finite region of the plane will be covered eventually, the only nontrivial part of the walk is the 1 dimensional ray along the z direction, and so return to the origin will happen.

Are there other shapes that interpolate between the two-D and the three-D case ?

Update (pulled in from comments): a related question was asked on MO - a short summary is that if the walk is even (2+ϵ) dimensional, then uncertain return follows loosely from a diverging series. However, the above question is slightly different IMO since I'm asking about other kinds of shapes that might admit certain return.


texts: Universe polymorphism: the inference of universes and their constraints

texts: When making a universe polymorphic definition in Coq, universes and their constraints are automatically inferred. Are they somewhat the most general ones (in a sense similar to the principal type property in ML)? Or are they just the result of arbitrary heuristics? Or something in between?


texts: Relationship between lambda-definability, specification and definability in model theory

texts:
I am new to lambda calculus and definability theory, and I am trying to clarify my understanding of the relationship among the following concepts:

An element $a$ in the domain of a type $A_\sigma$ is $\lambda$-definable if it is the denotation of a closed lambda-term
A subset $X$ is definable, in the model-theoretic sense, if it is the denotation of some formulas in the background language
Let $L^+$ be an extension of a ground langauge $L$ with a new signature term $r$. We say $r$ is explicitly definable in $L$ if it is extensionally equivalent to a formula in $L$, i.e.~there is $\varphi(x)$ in $L$ such that $\forall x(r(x)\leftrightarrow \varphi(x))$ (if $r$ is a constant, then $r(x)$ stands for $x=r$).
The axiom of restricted comprehension/specification says, roughly, for every formula and a given set, there is a subset of that set specified by that formula.

Is it right to think that
1. comprehension and $\lambda$-definability are inversions of each other: the former says, given a description there is a denotation of that description, whereas the latter asks, given a term is it denotated by some description (I have also read somewhere that $\lambda$-abstraction is tantamount to comprehension principles-is it correct?)
2. model-theoretic explicit definability and $\lambda$-definability are largely orthogonal to each other. The former is strictly a question about the relative expressiveness of two languagues, whereas the latter concerns the syntax-semantic interface.
On this note, I am also wondering if there has been any work on the relationship between explicit definability in the model-theoretic sense, and definability by $\lambda$-abstraction. For instance, assuming $\beta$-conversion, if $X\equiv\lambda x:\sigma. \varphi(x)$, then $\varphi(x)$ is automatically an explicit definition for $X$ (assuming, of course that we have $\forall^\sigma$ in our language). But we also know that explicit and implicit definability come apart in higher-order logic. Is there a precise definition of implicit definability in type-theoretic terms?

Many thanks in advance.


texts: What are the differences between Theta* and Field D*?

texts:
Both Theta* and Field D* are variations on the A* algorithm, but are adapted for any-angle pathfinding rather than pathfinding constrained to a grid. The primary difference between these two algorithms that I've seen is that Field D* can quickly recalculate the path at any time to adjust if the grid changes, while Theta* provides no such functionality.

Besides this change, what are the major differences between these algorithms? What are the pros/cons? Which is faster, and which will generate a superior path?


texts: What is best known space requrement for solving SATISFIABILITY problem in exp time

texts: I searched a lot for finding best space requirement algorithm for SATISFIABILITY problem but I didn't find any thing better than brute force that is in DSPACE(n). is there exists better bound? and what is best known bound.


texts: NP-hardness of a quadratic programming problem

texts:
Motivated by the mean-variance optimization, I came up with the following question: Given

$n$ integers $a_1, \cdots, a_n$;
$n$ lower bounds $0<\ell_1, \cdots, \ell_n<1$
$n$ upper bounds $0<u_1, \cdots, u_n<1$

The problem is to solve

minimize $\sum_{i=1}^n a_i^2 x_i- (\sum_{i=1}^n a_i x_i)^2$
subject to $\sum_{i=1}^n x_i=1$ and
         $\ell_i \leq x_i\leq u_i$ for all $1\leq i\leq n$.

For the complexity consideration, let's consider the decision version of the problem. Obviously this is a quadratic programming problem, so it is in NP. However, I do not know whether it is NP-hard. (My conjecture is, yes, it is.)

The intuition is that the (linear) constraints give exponentially many vertices, and it appears that one has to (and only needs to) compare them one by one, hence obstructs a polynomial-time algorithm. But I do not know how to show this formally. Any hints are appreciated.


texts: Finding a permutation $p$ of $x_1, x_2, \dots, x_n$ which maximises $\sum_{i=1}^{n-1}|x_{p_{i+1}}-x_{p_i}|$

texts:
Here is the algorithmic problem I'm trying to solve:

Given a list of integers $x_1, x_2, \dots, x_n$ find a permutation $p_1, p_2, \dots, p_n \in [n]$ that maximises the sum $\sum_{i=1}^{n-1}|x_{p_{i+1}} - x_{p_i}|$.

I think this can be solved in $O(n\log n)$, I thought of sorting the list and returning a list where first element is maximum element, next element is minimum, next is maximum of those which are left, etc. But this leads to nowhere, I cannot prove that it's correct, so probably it isn't. So, any tips how to tackle this problem?


texts:
Are there any recent books on Online Algorithms? I know of only two books on the subject.

Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv: This is a classic but old book, and does not contain many recent advances in the field.
The Design of Competitive Online Algorithms via a Primal-Dual Approach by Niv Buchbinder and Joseph (Seffi) Naor: This is a new book and contains lot of recent results. However, it's scope is limited to LP based primal-dual algorithms.

Please list here all the books on Online Algorithms that you may know. If there are any books freely available on the web, that will be great.


texts: A generalization of the geometric closest pair problem to balls

texts:
In one version of the classical closest pair problem, one is given a set $S \subseteq \mathbb{R}^2$ and asked to find distinct $x, y \in S$ such that $\|x - y\|$ is minimized for some norm $\| \cdot \|$. This problem admits a well-known $O(n \log n)$ divide and conquer solution for $L^p$ spaces (Wikipedia).

Instead of a point set, I have instead a finite set of closed balls $S = \{B_{r_i} (\mathbf{x}_i) : \mathbf{x}_i \in \mathbb{R}^2\}$, and I would like to solve the associated distance problem. That is, for a given $p$, I want to find distinct $i$, $j$ such that the distance between $B_{r_i}(\mathbf{x}_i)$ and $B_{r_j}(\mathbf{x}_j)$ is minimal.

I have been unable to adapt the divide and conquer technique to this situation. Has any work been done on this problem? I care specifically about an asymptotically fast solution for the case $p = 1$, though I am also interested in the general solution (my examples and scribblings so far indicate that the case $1 \leq p \leq \infty$ may be easier than the case $0 < p < 1$). Is it known, for instance, whether this problem is $\Theta(n^2)$ for $0 < 1 < p$?

Edit: I will make the simplifying assumption that the balls' interiors do not intersect (though their boundaries may).


texts:
Is the following Busy Beaver variant known?

A Universal Turing machine $J$, feeded with a description of a deterministic Turing machine $M_i$, starts simulating $M_i$ on inputs $x_j = 1,2,3,...$ for $|x_j|^i$ steps until $M_i(x_j)$ accepts; then $J$ outputs $x_j$ (if $M_i$ doesn't halt in $|x_j|^i$ steps  $J$ continues with the next $x_j$). In other words:

$$J(M_i) = min\{ x \mid M_i(x) \text{ halts and accept in less than } |x|^i \text{ steps}\}$$

Fancifully, $J(M_i)$ - when defined - represents how high the polynomial-time Turing machine $M_i$ can "jump". So, for every $n$, we can define the Jumping Beaver as the Turing machine $M$ of size $n$ that achieve the highest jump $j(n) = max \{ J(M) \mid |M| = n\}$ .

But in a similar way we can define $J'$ that "measures" the jumps of a nondeterministic Turing machine $N_i$ ($J'$ simulates all branches of $N_i$ on input $x$ for at most $|x|^i$ steps).

  Do nondeterministic jumping beavers perform better than deterministic jumping beavers? I.e. does $j'(n) > j(n)$ hold? (for some values of $n$ or infinitely often)
  What about the limit $\lim_{n \to \infty}j'(n)/j(n)$?

Note: the enumeration of the deterministic Turing machines $M_i$ is different from the enumeration of the nondeterministic $N_i$ (due to the nondeterministic transitions), so, to make $J$ and $J'$ directly comparable, we can follow this alternative approach: $J$ simulates $M_i$ on input $x_j \# 0^{|x_j|}$;  $J'$ can take as input a deterministic Turing machine $M_i$, too but simulates it on inputs $x_j \# y$ for all $y \in \{0,1\}^{|x_j|}$ and stops its search if at least one computation accepts. In this setting that seems equivalent to the formulation above (indeed $J'$ seems to capture all the power of NP), it is easy to see that $j(n) = j'(n)$.


texts:
In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe.   They were able to provide an algorithm with running time $O(n^{13/7})$ for solving 3-Sum on the subset of the universe of size $n$, assuming some preprocessing was allowed.

What other examples of such algorithms in preprocessed universe do you know?


texts:
Approximations for the set multicover problem have been studied (Rajagopalan & Vazirani (section 5)), as have approximations for the min-sum set cover problem (Feige et al.). The greedy heuristic gives a $\log(n)$-approximation for the set multicover problem and a 4-approximation for min-sum set cover.

Consider the min-sum set multicover problem, i.e. for each ground element $e_i$ with coverage requirement $r_i$, let $f(e_i)$ be the step in which the coverage requirement is met; we then wish to minimize $\textstyle\sum_{i=1}^n f(e_i)$.

By extending the 4-approximation in Feige et al., it is trivial to get a $4r$-approximation for min-sum set multicover, where $r=\max r_i$. It is most likely that a better approximation ratio can be achieved.

Does anyone know of any work that has been done on the min-sum set multicover problem? Any pointers to other names for the problem would also be very helpful. Thanks in advance!


texts: When to use the Johnson-Lindenstrauss lemma over SVD?

texts: The Johnson-Lindenstrauss lemma allows one to represent points in a high dimensional space into points in lower dimension. When finding lower dimensional spaces of best fit, a standard technique is to find the singular value decomposition and then take the subspace generated by the largest singular values. When is it of interest to use Johnson-Lindenstrauss over the SVD?


texts:
Let $F$ be a random k-CNF formula with $n$ variables and $m$ clauses. Let $G$ be the undirected graph built in the following manner: there is a vertex $v$ for every clause $c \in F$, and there is an edge $e = (v, u)$ if and only if the clause corresponding to $v$ has at least one variable in common with the clause corresponding to $u$.

The question is: how many variables, on average, shall I remove from $F$ before $G$ gets divided into 2 or more connected components? Is such number of variables related to $r = \frac{m}{n}$?

Here is what I mean by "removing  a variable $v$ from a formula $F$": every clause $c$ in which $v$ is mentioned (no matter if positive or negative) gets shortened; if $c$ becomes empty, then it is removed from $F$.


texts: Sparse Boolean Function and Other Boolean Functions

texts:
Let $s$ be a Sparse boolean function $s:\{0,1\}^{n}\rightarrow \{0,1\}$ such that $|s^{-1}(1)| \leq 2^{n\delta}, 0 < \delta <1$

The majority function $MAJ_{n}$ takes value 1 if and only if the number of 1 bits in the input is greater than or equal $\frac{n}{2}$.

My question is the following.

Can we $\epsilon$-approximate $MAJ_{n}(x_{1},..,x_{n})$ as a function of a few sparse functions: $f( s_{1}(x_{1},...,x_{n}),...,s_{m}(x_{1},...,x_{n}) )$ ? ($f$ is some boolean function, and $\epsilon$ approximate means that except for an $\epsilon$ fraction of the inputs, the funciton value of $MAJ_{n}$  is equals to that of $f$  )

What is a good upper bound of m( if  the answer of previous question is YES )?


texts: Interaction between metamathematics and combinatorics?

texts:
Metamathematics started in the 19th century with the discovery of paradoxes intrinsic to certain axiom systems involving infinite objects; attempts to resolve these paradoxes led to the formulation of set theory, transfinite arithmetics, and more recently to model theory/proof theory.

While of interest to mathematicians, this line of research had so far a small impact on combinatoricians / computer scientists which deal with finite or countable structures. In particular the countable structures we are interested in are often $\omega$-categorical which rules out the possibility of independence results à la Gödel.

So I would like to know if there are examples of interactions of metamathematics with "concrete" combinatorics (by which I mean essentially discrete algebra, structured algorithms and computational complexity), and how these kinds of interaction could possibly materialize given the apparent absence of overlap of the fields.


texts:
Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$.

One example is counting spin configurations on graphs. Counting weighted proper colorings, independent sets, Eulerian subgraphs correspond to partition functions of hardcore, Potts and Ising models respectively, which are easy to approximate for "high temperature" and hard for "low temperature". For simple MCMC, hardness phase transition corresponds to a point at which mixing time jumps from polynomial to exponential (Martineli,2006).

Another example is inference in probabilistic models. We "simplify" given model by taking $1-p$, $p$ combination of it with a "all variables are independent" model. For $p=1$ the problem is trivial, for $p=0$ it is intractable, and hardness threshold lies somewhere in between. For the most popular inference method, problem becomes hard when the method fails to converge, and the point when it happens corresponds to the phase transition (in a physical sense) of a certain Gibbs distribution (Tatikonda,2002).

What are other interesting examples of the hardness "jump" as some continuous parameter is varied?

Motivation: to see examples of another "dimension" of hardness besides graph type or logic type


texts:
Is there such a thing as a "normalized tensor rank" for non-square tensors (i.e. a tensor with different sizes along each mode)?

For example: If a 3rd order tensor (dimensions = 60 x 120 x 30) has mode-ranks

rank-mode1 = 15 (i.e. the matrix-rank after unfolding the 3D-tensor along mode1)
rank-mode2 = 16 (ditto)
rank-mode3 = 10 (ditto)

Does it make sense to normalize the ranks by their respective mode-lengths"?

normalized rank-mode1 = 15/60
normalized rank-mode2 = 16/120
normalized rank-mode3 = 10/30

And, for the example above, can I use this normalized rank to infer a simpler "structure" along mode2-unfolding?

OR does the lowest rank, regardless of mode-direction, define the "simplest" structure direction?

EDIT: Motivation - I'm working with reconstruction algorithms and trying to understand the significance of rank along different modes
Thank you


texts:
This is bothering me for some time. Consider that I have a set of CNF formulae:

$F_1 = \left( A \lor B \lor C \right) \land \left( C \lor D \lor E \right) \land \left( B \lor F \lor G \right)$

$F_2 = \left( B \lor F \lor G \right)$

$F_3 = \left( A \lor B \lor D \right)$

Now, given the values (T/F) of the literals ($A$, $B$, $\cdots$), I wish to evaluate these formulae.

However, the point is that, if we observe closely, we can see that formula $F_1$ subsumes formula $F_2$ (i.e., while evaluating $F_1$, I will be automatically evaluating $F_2$). If I evaluate $F_1$ first followed by $F_2$, I will be unnecessarily repeating the efforts (since I already evaluated the $3^{rd}$ clause in $F_1$, I could have used that result for $F_2$, if I had some way of knowing it). Again, in case of $F_1$ and $F_3$, they do share some parts of the $1^{st}$ clause.

So, the question is, whether I can re-use the work done while performing this evaluation, by discovering the relationships (or hierarchy) of these CNF rules. I would like some scheme which tells me to evaluate $\left(A \lor B \right)$, use that for $F_1$ and $F_3$, tells me to evaluate $F_2$ before $F_1$ and directly use that result while evaluating $F_1$ (and so on...)

Is anyone aware of such problems? I know concepts such as Junction Trees in machine learning, Memoization in DP, or data structures like Trie which loosely achieve the same, but I am not able to fit my problem to these formulations. Any help would be greatly appreciated.

Thanks,

Salil

(PS: I posted this earlier on math.SE, but could not get any ideas, and was instead suggested to post this problem here)


texts:
I'm searching for an authoritative definition of resolution (logic resolution).

Preferably on a reference freely available on the Internet (so I can read it right now).

If this is too broad then resolution for first order logic.

Thank you.


texts: Would polynomial solution for #P-complete problem mean polynomial solution for PSPACE problem?

texts: After looking at textbooks and trying to derive by my own deductive abilities, I was not able to see whether polynomial solution for #P-complete problem (that is counting problem done in polynomial time) do or do not lead to polynomial solution for PSPACE problem. Can anyone show me why it has to be one or the other way?


texts: "Security Against Covert Adversaries" question

texts:
I was reading the paper Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries by Aumann and Lindell, and had some questions with the protocol for covert OT given errorless homomorphic encryption.  This is section 5.1, and in this .pdf it's page 25.
I've put just pages 25 and 26 (the ones relevant to my question) here.

The protocol itself is a little long (a little over a page for the full description).  I'll mention the part I have questions about.

As part of the protocol, the ciphertext $\tilde{c}_0 = x_0\cdot_E c_0$ is computed.
Later it's claimed that (if $c_0$ is an encryption of $0$) that:
$$\tilde{c}_0 = x_0\cdot_E c_0 = E_{pk}(0\cdot x_0) = E_{pk}(0)$$

I have two real questions about this:

It seems like it should be true that $x_0\cdot_E c_0 = Enc_{pk}(Dec_{sk}(x_0)\cdot Dec_{sk}(c_0))$.
It's instead stated (implicitly) that $x_0\cdot_E c_0 = Enc_{pk}(x_0\cdot Dec_{sk}(c_0))$.
Is this a typo, or a misunderstanding on my part of what homomorphic encryption is?
In the part I mentioned about $\tilde{c}_0$, it seems like $0\cdot x_0$ is an operation in the message-space group.
For the proof of security, it seems vital that $0\cdot x_0 = 0$.
But this seems to imply that $0$ isn't invertible (as it typically isn't), so is this really occuring in a group?
If not, is this ok for some other reason?

I haven't really worked with homomorphic encryption before (or much computer science to be honest), so I apologize if these questions are rather basic.


texts: Testing sortedness of a normalized list of $n$ numbers

texts:
It is known that testing whether a list of $n$ arbitrary real numbers is $\varepsilon$-close of being sorted (in Hamming distance) has query complexity $\Theta(\log n)$ [1]. It is also easy to show that if the function is Boolean-valued, then this becomes $\Theta(1/\varepsilon)$.

Recent work of Berman et al. [2] considers the same problem for sequences with elements in $[0,1]$, but with another distance (namely, a (normalized) $L_p$ distance instead of Hamming — the normalization being done to ensure the distances lie indeed in $[0,1]$). They show the query complexity then becomes $O(1/\varepsilon^p)$, for $p\in\{1,2\}$.

Now, does anyone know if any of these two variants has been considered (either Hamming or non-normalized $L_1$), but with the further restriction that the sequence has bounded $L_1$ norm? That is, decide (with high probability) whether a sequence of non-negative numbers $a_1,\dots, a_n$ with $\sum_{k=1}^{n} a_k = 1$ is (a) sorted or (b) $\varepsilon$-far from sorted?

I tried to find references, but so far didn't find any -- and want to make sure there is no prior work I'm unaware of before diving further into this (I am in particular interested in adaptive algorithms, as I (think I) have a non-adaptive tight bound for this question).

Eldar Fischer. 2004. On the strength of comparisons in property testing.
Berman, Raskhodnikova, and Yaroslavtsev. 2014. $L_p$-testing.


texts: Uniform mortality problem for Turing Machines

texts:
Consider the following generalisation of the mortality problem for Turing Machines.

  Given a Turing Machine $M$. Is there a bound $k_M$ such that starting
  from any configuration $c$ machine $M$ stops after at most $k_M$ steps?

Is the presented problem (un)decidable? Can you provide any references?

We stress that "configuration" here means any possible configuration, not only the initial one.


texts: Is it possible to prove that a game(ex. chess or othello...) will eventually halt at some point.

texts: Is it possible to prove that a game(ex. chess or othello...) is solvable and will eventually halt at some point. I wonder as the halting problem is undecidable, will it be possible to prove that a particular game will end after a finite number of moves


texts:
(I posted this question on MathSE first, no answer, that is the reason why I come here.)

Let $F$ be a 3-CNF formula on $n$ variables. A clause $c$ is implied by the formula if $F$ and $F \wedge c$ are equivalent.

Question : Is it true that each 4-clause  implied by $F$ (if there are any) is also the resolvent of two implied 3-clauses ?
By extension, is it true that each $k$-clause ($k> 3$) implied by $F$ is also the resolvent of two strictly smaller implied clauses ? (a $k$-clause ($k\leq n$) contains exactly $k$ literals in it).

Thank you for your answers.


texts:
I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time.
All textbooks and lecture notes I could find initially introduce Markov chains this way but then quickly restrict themselves to the time-homogeneous case where you have one transition matrix.

Obviously, in general such Markov chains might not converge to a unique stationary distribution, but I would be surprised if there isn't a large (sub)class of these chains where convergence is guaranteed. I'm particularly interested in theorems on the mixing time and convergence theorems that state when there exists a stationary distribution.


texts: How to quantify the tree-like-ness of a graph?

texts: What are good measures of tree-like-ness of a graph and algorithms for calculating them?


texts: Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion

texts:
I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if my terminology is not exactly right.

I have a database system where user can add/remove/move objects by creating/deleting and altering relationships. As such, I can see the objects as been vertices in a graph and the relationships been edges and edges can be weighted depending on the type of relationships (either composition, association, or aggregation).

From the user's point of view, adding a new element can be a single click and underneath the hood, the program creates a graph of objects linked by relationships. This graph, is then added to the main graph that defines the entire database. Removing an element, would be the reverse where links/edges are disconnected and the graph becomes two disjoint graphs where 1 is the database, and the other consists of vertices formed by the element and its sub elements.

I need a really quick way to determine when I have a disjoint graphs and when 2 disjoint graphs becomes 1 again. I had a brief look at Holm, de Lichtenberg, and Thorup (2001; pdf). It seems like the way to go, but the author did mention they are only considering a graph with fixed number of vertices. Just wondering do algorithms usually extend themselves to adding/removal of vertices by just performing the adding of edges incrementally? Or has there been works that tailors specifically for such scenario?


texts: Inductive definition of ECTL*: how are recursive formulas forbidden?

texts:
In [1], the extended computation tree logic ECTL* is inductively defined as the propositional formulas over all E($A(F_1,..F_n)$), where E is the existential path quantifier and $A$ some Büchi automaton whose alphabet is $2^{\{F_1,..,F_n\}}$ for some ECTL* formulas $F_1,..F_n$.

Obviously E($A(F_1)$) with $F_1=$E$(A(F_1)$) is not well-defined for some Büchi automata. So what does inductively defined exactly mean in this case?

Maybe that no $F_1,..,F_n$ may use $F_1,..,F_n$ in their respective Büchi automata, but the Büchi automata may occur recursively if the alphabet is correctly exchanged. Or may, e.g., $F_1$ use $F_2,..,F_n$, as long as there is no mutual recursion between the $F_i$?

Update: Does the following define ECTL*'s syntax?

$\langle\text{sf}\rangle::=\;
  \langle\text{atomic prop}\rangle\;\big\vert\;
\langle\text{sf}\rangle \vee \langle\text{sf}\rangle\;\big\vert
\neg\langle\text{sf}\rangle\;\big\vert\; \text{E
}\langle \text{Buechi}\;\mathcal{A}\rangle (\langle\text{sf}\rangle,\dots,\langle\text{sf}\rangle);
$

(as opposed to
$\langle\text{sf}\rangle::=\;
  \langle\text{atomic prop}\rangle\;\big\vert\;
\langle\text{sf}\rangle \vee \langle\text{sf}\rangle\;\big\vert
\neg\langle\text{sf}\rangle\;\big\vert\; \text{E
}\langle \text{Buechi}\;\mathcal{A}\rangle (F_1,\dots,F_n);
$ where the $F_i$ are ECTL* formulas).

 In detail,

[1] says

  Formulas of ECTL* are inductively defined as usual and built from
  propositional variables using boolean connectives and containing the
  formula $E(A)$ for each Büchi automaton $A$ over an alphabet
  $2^{\{F_1,..,F_n\}}$ where the $F_i$ are ECTL* formulas.

[1] CTL* and ECTL* as fragements of the modal $\mu$-calculus by Mads Dam


texts: Is it possible to create an algorithm-aware optimizer?

texts:
I've recently implemented a physics system where each object has to interact with eachother. It consisted of, pretty much, the following algorithm:

for obj_a in world
    for obj_b in world
        obj_a.collide(obj_b)

This is O(N^2) and obviously scales very badly. I know, though, that distant objects don't collide, so I partitioned the space. The algorithm became:

for obj_a in world
    for obj_b in space_partition_of(obj_a)
        obj_a.collide(obj_b)

Considering the second loop iterates only over objects close to A, it brings the complexity down to almost O(N) and is ridiculously faster.

That made me think: it does not matter which language I implemented the first algorithm, it would always be sluggish. There is not a single compiler in the world that would fix my mistake, as much as obvious it seems for a human programmer. My question is: what is there stopping us to create a compiler that replaces the algorithms and data-structures used for the optimal ones? Is it impossible in a turing complete language? Would it be possible in a non-turing-complete language such as Idris?


texts: List of strongly NP-hard problems with numerical data

texts:
I am looking for strongly NP-hard problems for a reduction.
So far I have found the following problems:

3-partition problem
bin-packing problem
Numerical 3-dimensional matching
TSP
Any NP-complete problem without numerical data, e.g., SATISFIABILITY, HAMILTONIAN
CYCLE, 3-COLOURABILITY.

Does anyone know of a list of strongly NP-hard problems?

If not, let's build one here.
Do you know of other problems with numerical data that are strongly NP-hard?

I'm particularly interested in strongly NP-hard problems on weighted graphs.


texts: Implication of Bell test loopholes on Vazirani-Vidick random sequence generation scheme

texts:
I am trying to imagine what would be the implications of the loopholes on Bell test on the random sequence generation scheme proposed by Vazirani and Vidick (VV protocol) in the paper titled 'Certifiable Quantum Dice Or, True Random Number Generation Secure Against Quantum Adversaries'.

To my knowledge there are six loopholes to be discussed here.

Detection efficiency, or fair sampling
Communication, or locality
Disjoint sampling
Failure of rotational invariance
Sources of error in (optical) Bell test experiments
Free choice of detector orientations

Let me try to express my understanding one by one.

Detection efficiency, or fair sampling
If a very high efficiency detector is used it could be claimed that the loophole for Bell test is fixed. But the detector is a component of the device manufactured by the adversary. So, we should not be assured if the vendor claims that they are using very high efficiency detector.

Communication, or locality
Non-locality is an assumption for the VV protocol so I assume this loophole has impact on the protocol.

Disjoint sampling
I didn't get the whole thing but should I assume that this loophole will have impact if someone extends the VV protocol to a 3-party system?

Failure of rotational invariance
I have no clue. Anyone with help?

Sources of error in (optical) Bell test experiments
Is my logic used in case 1 applicable here too?

Free choice of detector orientations
I am not sure but is it related to choosing the basis of measurements?

Are my understandings correct? Thanks in advance for your help.


texts:
This is a restatement of an earlier question.

Consider the following impartial perfect information game between two players, Alice and Bob.  The players are given a permutation of the integers 1 through n.  At each turn, if the current permutation is increasing, the current player loses and the other player wins; otherwise, the current player removes one of the numbers, and play passes to the other player.  Alice plays first.  For example:

(1,2,3,4) — Bob wins immediately, by definition.
(4,3,2,1) — Alice wins after three turns, no matter how anyone plays.
(2,4,1,3) — Bob can win on his first turn, no matter how Alice plays.
(1,3,2,4) — Alice wins immediately by removing the 2 or the 3; otherwise, Bob can win on his first turn by removing the 2 or the 3.
(1,4,3,2) — Alice eventually wins if she takes the 1 on her first turn; otherwise, Bob can win on his first turn by not removing the 1.

Is there a polynomial-time algorithm to determine which player wins this game from a given starting permutation, assuming perfect play?  More generally, because this is a standard impartial game, every permutation has a Sprague–Grundy value; for example, (1,2,4,3) has value *1 and (1,3,2) has value *2.  How hard is it to compute this value?

The obvious backtracking algorithm runs in O(n!) time, although this can be reduced to $O(2^n poly(n))$ time via dynamic programming.


texts: Relative error estimation of a special type of GapP function

texts:
Consider the functions included in the complexity class GapP.
We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly finding the sign of $f(x)$ (for a worst case function $f$) is #P-hard --- if we can find the sign, we can use a padding argument, coupled with binary search, to exactly find the value of the function. (For reference, see this.)
Now, consider another class of functions: let's name the class SpecialGap. A function $g(x)$ belongs to SpecialGap if and only if there exists a GapP function $f(x)$ such that $g(x) = f(x)^{2}$.
Note some properties of SpecialGap. In the worst case, computing the sign of a function in SpecialGap is easy --- it is always positive, as it is the square of a function. In the worst case, exactly computing a function from SpecialGap is #P-hard --- noting that #P functions are a subset of GapP functions, if we want to exactly estimate the value of a #P function, we use the procedure we have for finding the exact value of a SpecialGap function to find the exact value of the square of our desired #P function, and then we just take the square root to get the exact value of our #P function. Note that exactly estimating the value of a #P function is #P-hard.
Is multiplicatively estimating the value of a worst-case function, to inverse polynomial error, from SpecialGap also #P-hard?

Here's an attempt at a proof.
Consider a procedure to multiplicatively estimate (upto inverse polynomial relative error) the value of a SpecialGap function $g(x)$, where $g(x) = f(x)^{2}$, for a GapP function $f(x)$. Let the estimate be $\tilde g(x)$, where
\begin{equation}
\left(1 - \frac{1}{p}\right)f(x)^{2} \leq \tilde g(x) \leq \left(1 + \frac{1}{p}\right)f(x)^{2},
\end{equation}
for some polynomially bounded function $p$. Taking the square root, we have
\begin{equation}
\left(1 - \frac{1}{2p}\right)|f(x)| \leq \sqrt{\tilde g(x)} \leq \left(1 + \frac{1}{2p}\right)|f(x)|,
\end{equation}
which is an inverse polynomial multiplicative error estimate to $|f(x)|$.
The proof now reduces to proving that for a function $f(x)$ belonging to GapP, in the worst case, it is #P-hard to have an inverse polynomial multiplicative error estimate to $|f(x)|$. I didn't have any idea on how to prove this. For one, since $|f(x)|$ is always positive, making use of a procedure to find the sign of $|f(x)|$, and then using binary search and padding, fails.


texts:
Given a data matrix $D=[d_1 ... d_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized.

It can be formulated as follows

$\min_{P\in\Pi} \sum_i w_i ||Pd_i-y||_2 $

where $w_i$ is the weight, $\Pi$ is the set of permutation matrix: $\Pi = \{P|Pe=e,P^Te=e,P_{ij}\in \{0,1\}\}$

Is there any optimal sorting strategy?


texts: An example where smallest normal lambda term is not fastest

texts:
Let the $size$ of $\lambda$-terms be defined as follows:

$size(x) = 1$,
$size(λx.t) = size(t) + 1$,
$size(t s) = size(t) + size(s) + 1$.

Let the complexity of a $\lambda$-term $t$ be defined as
the number of parallel beta reductions from $t x$ to its normal form
(using an optimal evaluator in Levy's sense).

I am looking for an example of two normal $\lambda$-terms for the same function where
the larger term has lower complexity.

...

Edit for clarity

since it seems that it is not obvious what I'm asking, I'll try to give a solid example. There is often a belief that the "naive"/"simplest" definition of a function is slow and not optimal. Better performance increase the complexity of the term, since you need added data-structures, formulas, etc. A great example is fibonacci, which can be "naively" defined as:

-- The fixed fibonacci definition
fib_rec fib n =
    if (is_zero x)
        then 1
        else fib (n - 1) + f (n - 2)

-- Using church numbers instead of the λ-combinator to get a normal form
fib n = n fib_rec 0 n

This is often regarded as the "simplest" definition of fib, and is very slow (exponential). If we expand the dependencies of fib (the usual definitions for church-number addition, pred, is_zero), and normalize it, we get this term:

fib = (λa.(a(λbc.(c(λdef.f)(λde.d)(λde.(de))
      (λde.(b(λfg.(c(λhi.(i(hf)))(λh.g)(λh.h)))
      d(b(λfg.(c(λhi.(i(h(λjk.(k(jf))))))(λhi.g)
      (λh.h)(λh.h)))de)))))(λbc.c)a))

Improvements such as memoization tables would make this term bigger. Yet, there exists a different term that is much smaller...

fib = (λa.(a(λb.(b(λcde.(e(λfg.(cf(dfg)))c))))
      (λb.(b(λcd.(cd))(λcd.d)))(λbc.b)))

and, curiously, is also asymptotically superior to the naive one, running in O(N). Of all definitions I'm aware, this is both the fastest and the simplest. The same effect happens with sort. "Naive" definitions such as bubble sort and insertion sort often get expanded to huge terms (20+ lines long), but there exists a small definition:

-- sorts a church list (represented as the fold) of church numbers
sort = λabc.a(λdefg.f(d(λhij.j(λkl.k(λmn.mhi)l)(h(λkl.l)i))
       (λhi.i(λjk.bd(jhk))(bd(h(λjk.j(λlm.m)k)c))))e)(λde.e)
       (λde.d(λfg.g)e)c

Which also happens to be faster, asymptotically, than every other definition I know. This observation leads me to believe that, as opposed to common belief, the simplest term, with smallest Kolmogorov complexity, is usually the faster. My question is basically wether there is any evidence of the opposite, although I'd have a hard time in formalizing it.


texts: Worst case of heuristics for symmetric TSP

texts:
I have implemented the nearest neighbor heuristic for solving symmetric TSP problems.
I was wondering if there is any relation between the solution found by the heuristic and the optimal solution?

Can we state theoretically how much higher the route length is in a worst case scenario?

Same question for simulated annealing, tabu-search and 2-opt search.


texts: Asking optimal questions to differentiate object in set

texts:
I have a problem in mind and I am sure this is likely an area of active research, but am at a loss as to the correct terminology and thus unable to find any reference literature.  It is best explained by example:

Say I have several objects, for example mahogany chairs.  For each of these chairs I know a number of attributes about them such as their weight, texture, colour, age, etc.

If you contact me inquiring about one of my chairs and tell me some incomplete information, e.g. "dark brown, 60's era chair"  I want to decide optimally what further information (if any) do I require from you to identiy the chair of interest, i.e. what questions do I need to ask to obtain the required attribute information.  Additionally, in the likely case that there are many questions I will need to ask you, how can I optimise the questions I ask you.  Optimisation could mean minimising the expected number of quesitons I need to ask you, or asking questions I think you are most likely to be able to answer.

So I would appreciate some information or references for this kind of problem.  It's worth noting I am interested in implementing this computationally (hence posting here) as opposed to a purely abstract problem.


texts: Computational Library to compute Quantum Cluster States

texts:
I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? Specifically I want to compute a cluster state of a specific topological quantum computation. I am investigating algorithms using this model and I would like to have a toy implementation for a presentation.
The specific algorithm would perform similarly to this.

Encode the given knot algorithm into a set of braids and create a cluster state of those braids
Perform measurement on those braids
Return a element of $Z_{n} \in_{1,0}$
Perform a classical operation on the knot.
Perform another operation until the knot is in a desired state.

See http://arxiv.org/pdf/1101.4722.pdf for a very simlar model.


texts: What does "hold uniformly" mean in the context of asymptotic analysis?

texts:
What does "hold uniformly" mean in the statement of Theorem 1.7 in
A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):


texts: Why do Agda and Coq disagree on strict positivity?

texts:
I've stumbled across a confusing disagreement between Agda and Coq that is not obviously related to the most well known distinctions between their type theories (e.g., (im)predicativity, induction-recursion, etc.).

In particular, the following definition is accepted by Agda:

  data Ty : Set0 -> Set0 where
    c1 : Ty ℕ
    c2 : Ty (Ty ℕ)

whereas the equivalent Coq definition is rejected because the appearance of [Ty _] as an index of itself in c2 is considered to violate strict positivity.

  Inductive Ty : Set -> Set :=
    | c1 : Ty nat
    | c2 : Ty (Ty nat).

In fact, this case is almost verbatim an example from Coq'Art Section 14.1.2.1 of violating strict positivity:

  Inductive T : Set -> Set := c : (T (T nat)).

But I don't see the reasons for this difference between the type theories.  The classic example of proving False using a negative occurrence of a type in a constructor argument is clear to me, but I can't see how one might derive a contradiction from this style of indexing (regardless of otherwise strictly positive constructor arguments).

Poking around the literature, Dybjer's early Inductive Families paper makes an offhand comment about Paulin-Mohring's solution in the CID paper having slightly different restrictions, and vaguely suggests the differences might be related to impredicativity, but doesn't elaborate further.  Dybjer's paper seems to allow this, while Paulin-Mohring's clearly prohibits it.

Apparently I'm not the first to notice this difference of opinion, and some believe this definition shouldn't be permitted in either system (https://lists.chalmers.se/pipermail/agda/2012/004249.html), but I haven't found any explanations of why it is either sound in one system but not the other, or just a difference of opinion.

So I suppose I have several questions:

Is this an example of a monotone, but non-strictly-positive type? (In Coq; clearly Agda considers it strictly positive)
Why does Agda permit this while Coq rejects it?  It is simply an idiosyncratic difference in the interpretation of "strictly positive," is there a subtle difference between Coq and Agda that makes it sound in Agda and unsound in Coq, or is it a matter of taste driven by particular theoretical preferences?
Is there a meaningful difference between the first definition above, and the equivalent inductive-recursive definition below?

Inductive-recursive definition:

  mutual
    data U : Set0 -> Set0 where
      c : (i : Fin 2) -> U (T i)
    T : Fin 2 -> Set0
    T zero = ℕ
    T (suc zero) = U ℕ

I'm happy to have pointers to relevant literature.

Thanks in advance.


texts:
We "know" that $\mathsf{SC}$ is named for Steve Cook and $\mathsf{NC}$ is named for Nick Pippenger. If I'm not mistaken, Steve Cook named NC in honor of Nick Pippenger, and I was told that the reverse is true as well. However, I wasn't able to find any evidence of this latter fact in either Steve Cook's paper on DCFLs or Nisan's proof that $\mathsf{RL} \subseteq \mathsf{SC}$.

Is there any documented evidence of the latter claim, or is this merely "in the air" ?

p.s I'm asking because I was browsing examples of Stigler's Law of Eponymy, and was wondering about what I'll call "Stigler Reciprocity": where something invented by A is named after B and vice versa. An example of this is Cartan Matrices and Killing forms.


texts: Hitting set of very restricted linear forms

texts:
We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear
form if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$.
A hitting set $H\subseteq\mathbb{Z}^{n}$ for {-1,0,1}-linear
forms is such that, for any non-zero {-1,0,1}-coef linear form $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$,
there is $\alpha\in H$ where $f(\alpha)\neq0$.

Observe that a singleton $\{(2^{1},\dots,2^{n})\}$ is already a hitting
set for $\{-1,0,1\}$-linear forms.

A hitting set is polynomially bounded if $H\subseteq\{-n^{c},\dots,n^{c}\}^{n}$
for some fixed constant $c$.

  What is the smallest size of polynomially bounded hitting set for
  {-1,0,1}-linear forms ?

By Chinese remaindering and this singleton $\{(2^{1},\dots,2^{n})\}$,
one can show a polynomially bounded hitting set of size $O(n/\log n)$.
Can we do better ?


texts: Randomized and deterministic query complexity of symmetric functions

texts:
The deterministic query complexity $D(f)$ of a symmetric function $f$ is $\Omega(n)$ (except for f = 0 or f = 1). I am wondering if the same result holds for the (bounded-error) randomized query complexity? Do we have $R_{1/4}(f) = \Omega(n)$?

I know it's true for some well-known functions (like the OR function), and that it doesn't hold in the quantum setting (for instance, $Q(OR) = \Theta(\sqrt{n})$ by Grover's algorithm). In fact, $D(f) = O(Q(f)^2)$ so we have at least $R_{1/4}(f) = \Omega(\sqrt{n})$.


texts:
How can you force a party to be honest (obey protocol rules)?

I have seen some mechanisms such as commitments, proofs and etc., but they simply do not seem to solve the whole problem. It seems to me that structure of the protocol design and such mechanisms must do the job. Does any one have a good classification of that.
Edit
When designing secure protocols, if you force a party to be honest, the design would be much easier though this enforcement has its own pay-off. I have seen when designing secure protocols, designers assume something which does not seem realistic to me, for instance to assume all the parties honest in worst case or assuming honesty of server which maintains user data. But when looking at design of protocols in stricter models, you rarely see such assumptions (at least I haven't seen it - I mostly study protocols over UC framework of Canetti which I think it is not totally formalized yet). I was wondering, is there any good classification of the ways in which you can force a party to be honest or is there any compiler which can convert the input protocol to one with honest parties?
Now I am going to explain why I think this merely does not do the job though it may seem irrelevant. When designing protocols in the UC framework, which benefits from ideal/real paradigm, every communication link in the ideal model is authenticated, which is not true in the real model. So protocol designers seeks alternative methods to implement this channel through means of PKI assumption or a CRS (Common Reference String). But when designing authentication protocols, assuming authenticated channels is wrong. Suppose that we are designing an authentication protocol in the UC framework, there is an attack in which adversary forges identity of a party, but due to assumption of authenticated links in the ideal model this attack is not assumed in this framework! You may refer to Modeling insider attacks on group key exchange protocols. You may notice that Canetti in his seminal work Universally composable notions of key exchange and secure channels mentions a previous notion of security called SK-Security which is simply enough to assure security of authentication protocols. He somehow confesses (by stating that this is the matter of technicality) that UC definition in this context is too restrictive and provides a relaxed variant called non-information oracle (which confused me, cause I haven't seen this model of security any where, I cannot match this security pattern with any other security pattern, probably my lack of knowledge :D).

[As a side note, You can nearly have any Sk-secure protocol converted to a UC secure one regardless of simulator time. For instance you may just remove the signings of the messages and have the simulator simulate the whole interactions in dummy way. See Universally Composable Contributory Group Key Exchange for proof! Now suppose this is a group key exchange protocol with polynomially many parties, what would be the efficiency of the simulator?? This is the origin of my other question in this forum.]

Anyway, due to lack of commitment in the plain model (over UC), I sought other means to make the protocol secure by just bypassing the need for that relaxation. This idea is so very basic in my mind and has come to my mind by just having studied latest commitment scheme of canetti in the plain model: Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions.
BTW, I don't seek zero-knowledge proofs because due to reason which I don't know, whenever someone has used one of them in a concurrent protocol (over UC framework), the others has mentioned the protocol as inefficient (may be due to rewinding of the simulator).


texts: Is P equal to the intersection of all superpolynomial time classes?

texts:
Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$.

It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf {DTIME}}(f(n))$ for every superpolynomial time bound $f(n)$. I wonder, wether the converse of this statement is also true? That is, if we know $L\in {\mathsf {DTIME}}(f(n))$ for every superpolynomial time bound $f(n)$, does it imply $L\in {\mathsf P}$? In other words, is it true that
$${\mathsf P} = \cap_f {\mathsf {DTIME}}(f(n))$$
where the intersection is taken over every superpolynomial $f(n)$.


texts: Trading treewidth for depth in Boolean circuits

texts:
We know that languages defined by (poly-sized) Boolean formulae equals $\mathbf{NC}^1$: that Boolean formulae can be simulated in $\mathbf{NC}^1$ was shown by Brent/Spira [B,S], and  the converse is quite trivial (simply duplicate the circuit whenever there is a ''collision''). A proof can be found, e.g., in this lecture note by Pitassi (Theorem 3).
Boolean formulae (since the underlying graph is a binary tree) can be thought of as circuits with treewidth $1$, where treewidth of a circuit can be defined as the treewidth of the graph obtained by ignoring the direction of the wires. Gal and Jang [GJ] extended the result in [B,S] by showing that a circuit of size $s$ with treewidth $w$ can be simulated in depth $w\log(s)$. My question is whether the converse is also true: e.g., whether $\mathbf{NC}^2$ can be simulated using  circuits with treewidth $\log(s)$ with only a polynomial blow-up (and more generally, whether $\mathbf{NC}^i$ can be simulated using circuits with treewidth $O(\log^{i-1}(s))$).
Intuitively, this should hold (by following the tree decomposition and then using the duplicating trick). But I could not find any resource regarding this (which makes me wonder whether it is false and there is a blow-up in some step). Any pointers would be appreciated!
[B]: Brent, The Parallel Evaluation of General Arithmetic Expressions. Journal of the ACM, 1974.
[GJ]: Gàl and Jang, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators,  Inf. Comput., 2016.
[S]: Spira, On time-hardware complexity tradeoffs for Boolean functions. Hawaii Symp. on System Sciences, 1971.


texts: Need help understanding Cumulative Match Score (CMS) Curves

texts:
I have been reading some papers regarding face recognition, and I often see statistics depicting the performance of the algorithms in the form of CMS or ROC curves.
I do understand what ROC curves are, but I am having difficulties understanding ranks in CMS curves. Usually the curves are plotted in charts with a % correct axis and rank axis. Can you please tell me what rank is? Or direct me to a resource that explains that?


texts:
Assume that a neuronal population $A$ is connected to a neuronal population $B$ by a bunch of synapses - one-directional channels that propagate spikes. For simplicity assume that the current propagating through a synapse is 0 most of the time, and is 1 during a very short time-interval called a spike.
How to evaluate the maximal amount of information that can be transferred by a bunch of synapses in a unit of time under the assumption that all of the information is carried by spikes? It is known that for any given synapse the minimal distance between spikes is $\Delta t$. It is also known that the desired quantity of spikes, as well as their precise location is subject to noise from a known distribution.
The canonical approach to this problem in neuroscience is called rate-code:

Time is split into intervals of some arbitrary duration $T$
A probability distribution for the resulting number of spikes in such interval is obtained as function of the desired number of spikes.
Standard channel capacity methods are applied to this new discrete-time problem.

The problems with this approach are:

The result depends on the selected interval duration $T$
The result only uses number of spikes as information storage. It ignores that the approximate positions of individual spikes may store information in addition to that already given by their quantity

Questions:

How to quantify the optimal capacity of such channels?
There is a lot of literature in computational neuroscience using inter-spike-intervals as medium for information transfer, but most of it is very complicated and I'm scared that diving deeper into it may take a lot of time. Do the inter-spike-intervals fully describe all information that could be transferred by a channel? Briefly, how would one move from an inter-spike interval distribution to a bitrate of such a channel.


texts: Linear optimization over intersection of totally unimodular matrices

texts:
I am currently dealing with a problem of the following form
\begin{alignat}{2}
&\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\
&\text{sub to} \hspace{0.05in}&& \nonumber\\
& \hspace{0.05in}&& x = y  \nonumber\\
& \hspace{0.05in}&& Ax \leq b \nonumber \\
& \hspace{0.05in}&& Cy \leq d \nonumber\\
& \hspace{0.05in}&& x, y \in \lbrace{0,1\rbrace}^n \nonumber
\end{alignat}
where A, C are totally unimodular matrices. I was wondering if there has been any theoretical work on problems with this type of constraints (intersection of TUMs). I am okay with not solving it exactly, a good lower bounding procedure for the problem is also welcome. Currently, I can only think of a Lagrangian based approach. Are there other alternatives?

In case you are curious, the context from which this problem came to me is in the computation of the longest path on a DAG, encoded using matrix $A$. However, the edges occurring on the longest path need to satisfy certain constraints, which are represented in $C$.


texts: How to read this formula for composition in an asynchronous interaction category?

texts:
The paper is available here Interaction Categories and the Foundations of Typed Concurrent Programming Abramsky, Gay, Nagarajan

p.38 composition of two processes $p:A \rightarrow B$, $q:B \rightarrow C$ is defined as:

$
  p;q = \{s\upharpoonright\Sigma_A,\Sigma_C
    \mid s \in Tr(\Sigma_A + \Sigma_B + \Sigma_C),
    s \upharpoonright \Sigma_A,\Sigma_B \in p,
    s \upharpoonright \Sigma_B,\Sigma_C \in q \}
$

If I am reading it correctly, I would have rendered it as:

$
  p;q = \{s\upharpoonright(\Sigma_A \cup \Sigma_C)
    \mid s \in Tr(\Sigma_A \cup \Sigma_B \cup \Sigma_C),
    s \upharpoonright (\Sigma_A \cup \Sigma_B) \in p,
    s \upharpoonright (\Sigma_B \cup \Sigma_C) \in q \}
$

The LHS of the harpoon is a trace $s \in Tr(\Sigma)$ defined as a sequence of subsets of $\Sigma$. The RHS is a subset of an alphabet $X \subseteq \Sigma$.
So far the rest of the paper has been clear on when notation is being 'abused' and nothing else has been questionable until this formula.

The main thing that's throwing me off is that alphabets are combined with '+' and ',' in different places (and so there are two "different" commas being used in the right hand side of the guard), but to me they look to be the same operation, namely set union. One possibility I've considered is that one of them is intended to be a disjoint union and the other an ordinary union.

Edit: It seems I missed the definition of '+' further up, so $Tr(\Sigma_A + \Sigma_B + \Sigma_C)$ is equivalent to $Tr(\Sigma_{A \otimes B \otimes C})$

$
  p;q = \{s\upharpoonright(\Sigma_A \cup \Sigma_C)
    \mid s \in Tr(\Sigma_{A \otimes B \otimes C}),
    s \upharpoonright (\Sigma_A \cup \Sigma_B) \in p,
    s \upharpoonright (\Sigma_B \cup \Sigma_C) \in q \}
$


texts:
I am creating a scheduling program that I need to either optimize or prove that what I have is already optimal.

I have n groups, all of which need to do some activity a in time slot t. A person can belong to several groups. A person cannot perform two activities in the same time slot. There is also a limit to the number of persons that can do an activity in the same time slot.

Here is pseudocode for my current (greedy) algorithm

sort groups by size (descending)
t = 1
for each group
  place group in slot t
  if there is a conflict in this slot ( p1->a1 && p1->a2)
    place group in slot t+1
  if slot t is full
    t++

What I am looking for is the minimum number of slots possible. I have an algorithm ready that does hill climbing with simulated annealing, which is used for another scheduling problem. The question is do I need it, or is there something else I can use? Or is this current algorithm already resulting in an optimal solution? And how do I find the theoretical minimum of slots?


texts: Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?


texts:
I am going through some questions and answers regarding Information Theory and I found this question and its solution. Can some one explain this solution to me.

We would like to encode a sequence of symbols that come from an alphabet with d+3 symbols. We want to encode symbols  a_1,a_2,and a_3 using code words that are three bits long and symbols a_4,a_5,…,a_(d+1) with code words that are eight bits long. What is the maximum value of d for which this will be possible, if the code must be uniquely decidable?

and the answer is:

The codeword lengths are possible if and only if they satisfy the Kraft-MacMillan inequality,which in this case is
1/2^3 +1/2^3 +1/2^3 +d/2^8 <= 1
This is equivalent to
d/256<=5/8
which is equivalent to d<=160. The maximum value possible value of d is therefore 160.
what is the function d+3 , and where we used it . How 5/8 appears in equation.

What is the effect of d+3 symbols on all this scenario. If I change it to d+1, what is the effect of it


texts: Validity of a modal argument about "vagueness"

texts:
(2nd version to make explicit my implicit assumptions about A, B and C, and the definitions of the non-logical constants "⊂" and "≡".)
Intuitively, the following modal argument seems valid to me and to other people. However, can it be formally proved valid? Or proved not valid?
Definition: "◇p" means "We don't know that not p".
Definition: "◻p" means "We know that p".

∃A
∃B
∃C
∀x, ∀y, ∀z, ((x ⊂ y) ∧ (y ⊂ z) → (x ⊂ z))
∀x, ∀y, ((x ⊂ y) ∧ (y ⊂ x) → (x ≡ y))
◇(A ⊂ C)
◻(B ⊂ C)
∴ ◇(A ≡ B)

Or, in ordinary language, where "⊂" means set inclusion and "≡" means identity:

A, B and C exist
A may be some part of C
B is some part of C
Therefore, A and B may be the same part of C

I'm researching expressiveness of modal logic, i.e. to what extent modal logic can express the kind of assertions people make using some ordinary, informal language.
The particular relation identified in the argument here, which I think we can best describe as one of vagueness, seems to polarise the population surveyed into (mainly) two groups, and broadly equal in size: those who accept the argument as valid, and those who do not. However, those who do not accept validity appear for the moment, as I see it, unable to articulate a conclusive rationale in favour of invalidity.
The only substantial rationale for invalidity offered so far is to exhibit an interpretation of A, B and C which keeps both premises true but makes the assertoric version of the conclusion, i.e. "Therefore, A is the same as B", false. This is sometimes loosely qualified as a form of "undistributed term".
However, I take this to be inconclusive as it doesn't preclude other interpretations of A, B and C that make true the same assertoric conclusion "Therefore, A is the same as B". So, A and B may be the same. QED.
As I see it, there is nothing in the premises that implies that A and B are necessarily different. This in turn implies that they are possibly the same, which is the conclusion of the argument. QED.
Isn't that good enough?


texts:
While browsing old CStheory.se posts, I ran across a fascinating blog post on the matrix mortality problem.  Unless I've misinterpreted the problem, it states that given a finite collection of 3 x 3 matrices with integer entries for each matrix value, one must decide if there exists a finite product of those matrices that equals a matrix comprised of all zeros.

Amazingly, this problem is undecidable, due to a reduction from the Post correspondence problem.  My question is:  Given the undecidability of the problem, and its link to a problem that is linked to Turing machines, can you show that there exists a way to characterize (for example) all r.e. languages, the class P, and the class NP using matrices?

I've done a little work on this myself, but lack the training to be sure if my belief is correct.  This problem would, I think, require a little bit of work on the reader's part to solve.

I don't know how to use LaTeX to write matrices on SE, but here's my first attempt to characterize NP:

  Given a finite set $S$ of 3 x 3 matrices with integer entries and an integer $k$ as an NP "query," let an additional matrix $M$ be taken as a "structure."  The "query" accepts the "structure" if there exists a product of $|M|^k + k$ matrices from $S$ that equals a matrix that consists of only zeros.

This attempt is not complete and does include any proof, as you see, but I wanted to give my first thoughts on the problem to see if a more sophisticated attempt could be made to formalize a notion of matrix complexity.  This is interesting because, like Fagin's characterization of NP using descriptive complexity, it could be used to characterize NP in a machine-independent fashion.


texts: Is PP invariant under changing its cut-off from 1/2 to another number?

texts:
Suppose I have a fixed family of quantum circuits $\{C_i\}$ for which determining whether the maximum output acceptance probabilities are $p\geq 1/2$ or $p< 1/2$ is PP-hard.

Now suppose I have the same family of circuits $\{C_i\}$, but ask for $p\geq b$ or $p< b$, for $0<b<1$, $b\neq 1/2$. $b$ may be some function that depends on the number of input bits. Then is this second problem still PP-hard?

I'm aware that normally in the definition of PP we are able to change the value of $b$, but this is done by amplifying and shifting the circuit a polynomial number of times so that we get a different set of circuits which are not the same as $\{C_i\}$ (but are polynomially equivalent).

I suppose the question boils down to: is the statement of PP-hardness that estimating $p$ for some particular $b$ is PP-hard (e.g. for $b=1/2$), or for all $0<b<1$ is estimating $p$ is PP-hard?

Edit: A summary of the question is: if we let the cut-off be $b$, then is it the case that $PP(1/2)\subseteq PP(b)$?


texts: Counting number of solutions to a specific SAT formula

texts:
I have a n×n grid of binary bits, where n is a natural number. I want to count the number of bit patterns which have the following property: out of the four (North, West, South and East) adjacent bits of any bit, at most 3 can have a value different from it. Alternatively, if C is the center bit, and N, W, E and S are its four adjacent neighbours, then
              (C xor W)∧(C xor S)∧(C xor E)∧(C xor N)=0

              N
            W-C-E
              S

This should hold for every bit in any valid pattern. I am not sure if this is a #P problem. The counting for 1D version of this problem (a 1×n or n×1 grid), where every bit has only two adjacent neighbours, and at most one can be different from the bit, can be done in polynomial time. I am not sure if the same is true for this problem or not..

Inductive Proof for the case of a $n \times 1$ grid:

Counting for the 1D case can be done using the following inductive argument:

For an $n \times 1$ grid, let $b_{n}b_{n-1}...b_{1}b_{0}$ be a unique bit pattern. For this pattern to be valid, for any $b_{i}$, $i \in [1, n-1]$, atmost one of $b_{i-1}$ or $b_{i+1}$ can be equal to $\neg b_{i}$.
We now define the following quantities for a $n \times 1$ grid:
• $T(n)$ is the total number of distinct $n$ bit patterns
• $T_{v}(n)$ is the total number of valid patterns
• $T_{iv}(n)$ is the total number of invalid patterns
• $T_{vs}(n)$ is the total number of valid patterns which satisfy the property $b_{n} = b_{n-1}$
• $T_{vd}(n)$ is the total number of valid patterns which satisfy the property $b_{n} \neq b_{n-1}$

Then, for $n \geq 3$:
$T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$
$T_{vs}(n) = T_{vs}(n-1) + T_{vd}(n-1)$
$T_{vd}(n) = T_{vs}(n-1)$

Also, by the definition of $T_{v}(n)$ and $T_{vs}(n)$, we have:
$T_{v}(n)=T_{vs}(n)+T_{vd}(n)$
$T_{vs}(n)=T_{v}(n-1)$  (Only one pattern of the type $T_{vs}$ for a $1 \times n$ grid can be created from a $T_{v}$ pattern for a $1 \times n-1$ grid)

Now,
$T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$
$T_{v}(n) = T_{vs}(n-1) + T_{vs}(n-1) + T_{vd}(n-1)$
$T_{v}(n) = (T_{vs}(n-1) + T_{vd}(n-1)) + T_{vs}(n-1)$
$T_{v}(n) = T_{v}(n-1) + T_{v}(n-2)$

By using $n=2$ and $n=1$ as the base cases, we can compute the number of valid patterns for a $n \times 1$ grid for any $n$. This inductive method breaks for a $n \times n$ grid, because it would require creating exponential intermediate variables to do an exact counting.

Thanks,
Rajeev


texts: minimal finite automata given in-words and out-words

texts:
this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight.

  given: two finite sets of words $S_{in}$ and $S_{out}$. find the smallest FSM with language $L$ such that for each $x \in S_{in}$, $x \in L$ and for each $y \in S_{out}$, $y \notin L$.

in other words one is given finite lists of words that are in the language and not in the language. there is a simple algorithm of creating an FSM with the given (non)acceptance and then minimizing it, but is this also the smallest possible? it seems to come down some to the question of cycles in the FSM graph. the simple strategy will not have cycles, so could smaller FSMs with cycles exist? there is also the question of nondeterminism.


texts: Classifying noetherian simple groups by order type?

texts:
A (possibly infinite) group $G$ is noetherian if it satisfies the following equivalent conditions:

(1) every subgroup of $G$ is finitely generated,

(2) there is no infinite strict ascending chain of subgroups,

(3) any non-empty collection of subgroups has a maximal element under inclusion.

Note that this property is hereditary: if $G$ is noetherian then so are all its subgroups. Also, being noetherian is equivalent to require that the poset of subgroups $(Sub(G),\subseteq)$ is a well-order.

The order type of a well-order $(S,\leq)$ is defined as the supremum of the order type of its linear extensions. By extension, we may define the order type of a noetherian group $G$, denoted by $ot(G)$, as the order type of $(Sub(G),\subseteq)$. We may then ask the following questions:

(1) What ordinals $\alpha$ can be obtained as the order type of a noetherian
group?

(2) Is it possible to reduce that question to noetherian simple groups? For instance, if $H$ is a normal subgroup of $G$, is it true that $ot(G) = ot(H) + ot(G/H)$?


texts: Does this problem related to subset sum have a name?

texts:
I'm looking for research into this problem -- computational complexity, solution algorithms, approximation algorithms, etc. If it has a canonical name, that would help me look into prior research.

Suppose there are two sets of integers S1 and S2 that are subsets of the positive integers.

The sum of all numbers in S1 equals the sum of all numbers in S2.

Find all subsets of S1 and subsets of S2 such that the the subsets sum up equivalently between the two. For example:

S1 = (1,2,3,4) S2 = (2, 2, 3, 3)

solutions:

(1+2 = 3, 3 = 3, 4 = 2+2)
(1+2+3 = 3+3, 4 = 2+2)
(1+2+3+4 = 2+2+3+3)
(1+3 = 2+2, 2+4 = 3+3)
(1+3+4 = 2+3+3, 2=2)
(2+3 = 2+3, 1+4 = 2+3)
etc.

You could also frame this in terms of making all numbers in S2 negative, collapsing them into one set, and finding all permutation subsets such that each subset adds up to 0.

If the numbers in S2 are expressed as negative numbers, the problem could also be expressed as a graph in which each node is an integer, and the goal is to find all possible disjoint sets such that the members of each set add up to 0.


texts: Balanced partitioning of a set of axis-parallel 2D rectangles

texts:
Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the range $[0,M]$ for some $M$. Let $W=\sum w_i$. Find a simple (i.e. non self-intersecting) curve that partitions them into two sets of rectangles such that each set has total weight at least $\alpha W$ and the total weight of all rectangles cut by the curve is as small as possible, or output that no such curve exists. This is NP-complete, and I'm interested in a good heuristic/approximation algorithms with $O(N+poly(M))$ time (or more exactly $O(N+poly(M)+polylog(W))$ time).

A thorough search doesn't give me any reference in literature that studies this problem. Any insight is appreciated!


texts: Succinct representation of boolean functions

texts:
Let $f$ be a boolean function over $n$ variables $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}$. We are looking now for a representation of $f$ s.t. when given that representation and values $x_1, \ldots, x_n$, a turing machine in $PH$ can decide whether $f(x_1, \ldots, x_n) = 1$.

  What is the smallest representation of a boolean function meeting these requirements?

Circuits seem an intuitive choice, and a turing machine in $P$ can decide whether a set of values $x_1, \ldots, x_n$ satisfies that function. But circuits take upto exponential size in $n$, so we're hoping on smaller representations, given that the complexity of the machine calculating the result of the function can be much higher.

There are no bounds on the complexity of the function computing the representation.


texts: State-of-the-art unification for associative-commutative functions

texts:
I am interested what are the open problems on unification methods for associative-commutative functions, and what is the state-of-the-art work? I have found some old work, but nothing new. I am wondering if I am missing something since I am quite new to this.

It might help to say that I am generally interested in this area as I would like to apply it to modern programming languages, in terms of code canonicalization.


texts: Largest embeddable hypersphere given membership oracle

texts:
I have a membership oracle to tell me whether a point is inside of some set, S. I would like to find the radius of the largest (origin-centered) hypersphere that is contained in S.

Do you know any good references for this problem? (I'm looking for an algorithm along with a confidence that the hypersphere is fully contained in S).


texts: Natural notion for computational hardness

texts:
When I teach students concepts like intractable problems and efficient algorithms in discrete structures or data structures and algorithms, it is difficult for students to intuitively grasp somewhat artificial concepts of asymptotic time complexity and polynomial growth rates. Artificial $NP$-complete problems were known before the discovery of Cook's first natural $NP$-complete problem, which sparked huge interest in the field. Under some acceptable definition of natural:

  What is the most natural way to express the computational hardness of natural problems to students who encounter the subject for the first time?

EDIT: Motivated by Marc's answer, it would be more natural to find how hard is the self reducibility of clique problem. For instance, How hard is it to reduce an instance of clique of input size $(1+ \epsilon)n$ to an instance of size $n$ using Turing reduction?.


texts: Example of a $U^\omega$ that is not Deterministic Büchi recognizable

texts: Is there a regular language $U$, for which $U^\omega$ is not a Deterministic Büchi recognizable language. I have been thinking over it for some time, but have been unable to come up with an example.


texts:
The class $XP$ is the class of problems parameterized by $k$ that can be solved in time $n^{f(k)}$ for some function $f$ (each $k$ may require a different algorithm).

In their book on parameterized complexity, Downey and Fellows give an example of an XP-complete problem, which is called the $(2k + 1)$-pebbling game.  The XP-hardness reduction is generic and reduces Turing machinery to this game.

The literature on other XP-hard problem is very sparse.
I'd like to know if there are other known XP-hard problems, perhaps that use a more natural type of reduction.