texts: Schönhage-Strassen algorithm: why don't we work over $\mathbb{C}$

texts:
I am trying to understand how Schönhage-Strassen works for integers by studying von zur Gathen and Gerhard's Modern computer algebra. However they only talk about multiplication of polynomials.
In the book they use fast Fourier transform over a specifically crafted ring such that it has a certain primitive root of unity, but since we are working with integers, isn't it possible to just work over $\mathbb{C}$?
What are the disadvantages of doing this?


texts: Do there exist polynomial time algorithms that admit Probably Approximately Correct (PAC) bounds for APX-Hard problems? That is, does there exist a problem $P$ that is APX-Hard, such that for every $\epsilon, \delta > 0$, we have an algorithm that runs in polynomial time in $n$ that gives a $1 + \epsilon$ approximation to it with probability $1 - \delta$. Note that the randomness is not dependent on the instance of $P$ given, but some randomness of the algorithm.


texts: Why is finding the ground state of a Hamiltonian in QMA?

texts:
Why is finding the ground stte of a Hamiltonian in QMA?

It's in QMA to figure out if a hamiltonian has any energy eigenvalue within a certain window range which is at least inverse polynomial in size. But what if the energy gap for the ground state is inverse exponentially small? Then why is specifying the ground state in QMA? It takes an exponential time to measure energy up to inverse exponential accuracy, right? So, Arthur needs more than polynomial time to verify, right?


texts: Complexity of finding the smallest well-covered completion

texts:
This is related to an earlier question on which graphs have the property that all maximal independent sets are maximum — such graphs turn out to be known as the well-covered graphs. Any graph $G$ is an induced subgraph of a well-covered graph: for instance, find a clique cover of $G$, and add one more vertex to each of the cliques in the cover. Smaller clique covers lead to well-covered supergraphs of $G$ with fewer vertices. Which leads to the following problem:

Input: a graph $G$ and a number $k$

Output: yes if $G$ is an induced subgraph of a $k$-vertex well-covered graph, no otherwise

What is known if anything about the complexity of this problem? Testing whether a graph is well-covered is coNP-complete, so the obvious complexity class for finding a small well-covered completion is $\Sigma^P_2$ — but is it complete for $\Sigma^P_2$?


texts: "Checking equality for Kolmogorov complexity of two sequences" is computable?

texts:
It is a known result that Kolmogorov complexity is not computable for every arbitrary sequence. I wonder whether the following problem is computable or not:

"Given $x$ and $y$ as two sequences, whether $K(x)\overset{+}{=}K(y)$, where $\overset{+}{=}$ means equality in Kolmogorov complexity sense."

My next question is a generalisation of this one, i.e. whether the following is computable:

"Given $x$ and $y$ as two sequences, whether $K(x)\overset{+}{<}K(y)$, where $\overset{+}{<}$ means strictly smaller in Kolmogorov complexity sense."


texts: What is the relation of HOL Light type theory and some of the intuitionistic type theories?

texts:
I'm trying to understand how HOL Light deductive rules relate to mainstream intuitionistic type theories.
Here is a sample of questions that come to my mind.

Does HOL Light derivations admit cut-elimination and what sub-formula property would mean? Is there some kind of canonicity result?

Can HOL equality be modeled with Identity types (with J axiom)?

Somewhat specific question: DEDUCT_ANTISYM_RULE axiom allows us to deduce that if you have  (entilement) both $q \vdash p$ and $p \vdash q$, we can deduce $\vdash p=q$. How can we assert that rule without a condition that the entailments are "each other inverses forming an isomorphism"?

I realize that many of these question might be wrong questions to ask. Perhaps I even am wrong to focus on the deduction rules?
How should I be thinking when comparing theories such as HOL Light and some intuitionistic type theories?


texts: We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?


texts: What's the relation between the dominating set and vertex cover?

texts: I wonder if the minimal dominating set is always a subset of the minimal vertex cover in any graph. If so, what's the proof?


texts:
(1) Is there a relation ( conjectured relation) between $\mathsf{\#P}$ and $\mathsf{CH}$?

(2) How does $\tau$ conjecture in complexity of factorial fit in the picture?

Is there a good reference?

$\mathsf{CH}$ is counting hierarchy and $\mathsf\tau$ conjecture essentially conjectures a lower bound of $\omega(\log^cn)$ for any fixed $c>0$ on number of $\{+,-,\times\}$ operations needed for $n!$ computation.

(I searched on answers in ctheory but was unsuccessful)


texts: Is there such a thing as a weak coalgebra homomorphism?

texts:
Given an endofunctor $F : Set \rightarrow Set$, we can define observation functions as functions that are polymorphic for any $F$-coalgebra, that is $obs$ is defined for any $F$-coalgebra $\langle A, c : A \rightarrow FA\rangle$.
$$
obs : \forall \langle A, c \rangle . A \to B
$$
Another way of looking at observation functions is as functions of the final $F$-coalgebra if it exists. We get the polymorphism automatically by composing the observation function with the unique homomorphism to the final $F$-coalgebra. But this only works if the final $F$-coalgebra exists.

One of the defining characteristics of an observation function is that it cancels any coalgebra homomorphism composed to the right, due to its polymorphism. If $hom$ is an $F$-coalgebra homomorphism, then:
$$
obs = obs \circ hom
$$
During my research, in an attempt to define a notion of observational consistency between one coalgebra and another, I had the idea of a weak coalgebra homomorphism. The idea is that we can "fake" a coalgebra homomorphism if we know the observation function ahead of time. Thus, we might satisfy,
$$
obs = obs \circ hom
$$
but only for one particular $obs$.

For example, let $FX = \{0,1\} \times X$, and let $obs$ be defined as
$$
obs : \forall \langle A, c\rangle. A \to \{0,1\}^2
$$ $$
obs = \langle (\pi_1 \circ c), (\pi_1 \circ c \circ \pi_2 \circ c) \rangle
$$
That is, $obs$ takes the first two elements of a stream.

Then, an F-coalgebra homomorphism would need to ensure that it preserves all the elements of the stream, whereas a weak homomorphism for $obs$ only needs to preserve the first two elements of the stream.

In my research, this notion would be useful in order to show that one coalgebra is observationally consistent with another by showing that every finite linear observation function has a weak homomorphism from the first coalgebra to the second coalgebra. In other words, every finite linear observation on the first coalgebra can be reproduced on the second coalgebra.

(What I mean by linear observation function feels mostly irrelevant, but for the sake of sharing... A linear observation function is more or less one that uses each state of the carrier set only once. I'm trying to model an oracle, and the user is not allowed to go back and pretend it never asked a question.)

My questions are thus:

Has this been researched? Do "weak coalgebra homomorphisms" exist already, under some other name perhaps?
Is there a more "category theory" way to present this?

Edit: Removed two questions which aren't that important.


texts:
The question looks very simple, that is why I posted it first on MathSE, unsuccesfully - no answer for 12 days. I tried to find a short and elegant answer to the question, but I haven't succeed yet. Thank you for your attention.

A CNF formula is closed under resolution if all the possible resolvents are subsumed by a clause of the formula - a clause $c_1$ is subsumed by a clause $c_2$ if all the literals of $c_2$ are in $c_1$ (any clause is subsumed by itself then).

Given $F$,  a 3-CNF formula on $n$ variables $(x_i)$$_{i\le 1 \le n}$ which is closed under resolution. Given $I$, a partial assignment of $k$ variables among $(x_i)\   (k\le n)$. Let $F_{|I}$ the induced formula by applying $I$ to $F$: Any clause that contains a literal which evaluates to "true" under $I$ is deleted from the formula and any literals that evaluate to "false" under $I$ are deleted from all clauses -  the clauses that become empty by this deletion remain in the formula as the empty clause.

Question: Is $F_{|I}$ closed under resolution ?


texts: On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$

texts:
We know that $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$. From Savitch's Theorem, $\mathcal{N\!L}\subseteq\mathcal{L}^2$, and, from Space Hierarchy Teorem, $\mathcal{L}\neq\mathcal{L}^2$. So, as we don't know if $\mathcal L\neq\mathcal P$, we don't know if $\mathcal L^2\subseteq\mathcal P$, or do we know that $\mathcal L^2\not\subseteq\mathcal P$? Has anybody been trying to prove that $\mathcal L^2\subseteq\mathcal P$? What are the latest results, or efforts, in this way? I've been trying to write a survey on this topic, but haven't found anything relevant.

Furthermore, whether exists or not a $\mathcal{N\!P}$ problem which is not $\mathcal{N\!P}$-complete is an open question, and such existence would imply $\mathcal L\neq\mathcal{N\!P}$, as every $\mathcal L$ problem is complete for $\mathcal L$. But do we really not know that $\mathcal L\neq\mathcal{N\!P}$? Has anybody been trying to prove this? Again, what are the latest results, or efforts, in this way?

Maybe I'm missing something, or searching wrongly, but I couldn't find anyone working on the $\mathcal L^2\subseteq \mathcal P$ and $\mathcal L\neq\mathcal{N\!P}$ questions.


texts: On space complexity of permanent modulo $2^t$?

texts:
We know from here that permanent of $0/1$ matrix modulo $2^t$ is in $DTIME(n^{t+3})$ and hence in $P$. My question is whether permanent of $0/1$ matrix modulo $2^t$ is in $L$ as well or is the current best algorithm outside $NL$?
Suppose deciding if permanent of $\{0,1\}$ matrices is greater than $r\in\Bbb R$ has a $BPP$ algorithm which uses only logarithmic space then is there a name for the complexity class of such a situation? Clearly it cannot be $BPP\cap L$ since $BPP\cap L=L$ would mean $PP=L$ ands the algorithm is deterministic which it clearly is not?


texts:
What if we had an oracle for solving all NP problems which has exactly one solution in polynomial time.

The oracle fails if the NP problem has more than 1 solution.
The question is can we use this oracle to solve all NP problems in polynomial time even if they have multiple solutions?


texts: What is an algorithm to find a minimum vertex cover on a bipartite graph with weighted vertices?

texts: I know that for an unweighted bipartite graph, I can find the minimum vertex cover by first finding the maximum matching and turning it into a vertex cover using König's Theorem. Is there a modification one could use if the nodes are weighted?


texts: Addding edges to spanning tree without destroying planarity

texts: Given a graph $G=(V,E)$ with n vertices, m edges, and the maximum degree $\Delta$. Let $T$ be a spanning tree of $G$. Let $E_c \subseteq E - E(T)$ be the maximum number of edges that we can add to $T$ so that $T \cup E_c$ is a planar graph. Is there any known upper or lower bound on the size of $E_c$ in term of $n, m$ and $\Delta$


texts: Space efficient "industrial" unbalanced expanders

texts:
I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-expander if for any $S \subset A$ of size at most $k$, the number of distinct neighbors of $S$ in $B$ is at least $(1-\epsilon)d|S|$. It is known that the probabilistic method yields such a graph with $d=O(\log (n/k)/\epsilon)$ and $m=O(k \log(n/k)/\epsilon^2)$. However, one needs $O(n d)$ space to store such a graph. Also one also needs to access this storage when doing anything with the graph, which can cost as well. Ideally, one would like an explicit construction. However, as far as I know, known constructions achieve parameters that are still somewhat far from the above (at least provably so).

My question: are there any other constructions, possibly non-explicit, which achieve bounds "closer" to the ones above, yet use "significantly less" than $O(nd)$ space ?

I am looking for answers in any of these three categories: (a) theorems (b) conjectures (c) observations and "war-stories" such as "we did this and it kind of seemed to work (sort of)". I.e., "industrial" expanders are OK. I prefer (a) over (b) and (b) over (c), but beggars cannot be choosers :)

Here is an example of a construction of type (c). Take $d$ random linear hash functions $h_i: [n] \to [m]$ (mod $m$), and connect each vertex $i$ to $h_1(i) \ldots h_d(i)$. Me and my student did some experiments on it, and it seemed to work "fine". Are there any theorems or conjectures about this or related constructions ?

Thanks!


texts: Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?

texts:
Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent.  Since finding a perfect matching in a non-bipartite graph is in NP, there exists some reduction from non-bipartite graphs to the permanent, but it may involve a nasty polynomial blowup by using Cook's reduction to SAT and then Valiant's theorem to reduce to the permanent.

An efficient and natural reduction $f$ from a non-bipartite graph $G$ to a matrix $A = f(G)$ where $\operatorname{perm}(A) = \Phi(G)$ would be useful for an actual implementation to count perfect matchings by using existing, heavily-optimized libraries that compute the permanent.

Updated: I added a bounty for an answer including an efficiently-computable function to take an arbitrary graph $G$ to a bipartite graph $H$ with the same number of perfect matchings and no more than $O(n^2)$ vertices.


texts: Are theoretically sound pseudorandom generators used in practice?

texts:
As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they pass lots of (heuristic) statistical tests, there are no theoretical guarantees that they look pseudorandom to, say, all efficiently computable statistical tests. Yet these methods are used indiscriminately in all sorts of applications, ranging from cryptographic protocols to scientific computing to banking (probably). I find it somewhat worrisome that we have little to no guarantee about whether these applications work as intended (because any sort of analysis would likely have assumed true randomness as input).

On the other hand, complexity theory and cryptography provide a very rich theory of pseudorandomness, and we even have candidate constructions of pseudorandom generators that would fool ANY efficient statistical test you could come up with, using candidate one way functions.

My question is: has this theory made its way into practice? I would hope that for important uses of randomness, such as cryptography or scientific computing, theoretically sound PRGs are used.

As an aside, I could find some limited analysis of how well popular algorithms such as quicksort work when using LSFRs as a source of randomness, and apparently they work well. See Karloff and Raghavan's "Randomized algorithms and pseudorandom numbers".


texts: Intractability of restricted decomposition of connected bridgeless cubic graphs

texts:
A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known that every connected bridgeless cubic graph contains a 2-factor (and a disjoint perfect matching). I'm interested in the computational properties of 2-factors in connected bridgeless cubic graphs.

There are two parameters of two-factor: the number of disjoint-cycles and the size of each cycle. It seems that restricting cycles sizes and/or the number of cycles in the 2-factor makes the following decision problem $NP$-complete. The problem is to decide the existence of restricted 2-factor in the specified class of graphs.

Restricted 2-factor problem:

Input: connected bridgeless cubic graph.

Output: Decide whether there is a 2-factor such that forbidden lengths of the cycles of the 2-factor form a proper non-empty subset of $N=\{5, 6, 7, ..., |V|\}$.

Such decomposition must partition the class of connected bridgeless cubic graphs into two infinite sets. That means, there is infinite set of connected bridgeless cubic graphs with such restricted 2-factor and infinite set not satisfying the above property.

I conjecture that deciding the existence of such restricted 2-factor in connected bridgeless cubic graph is $NP$-complete.

I am aware of several $NP$-complete decomposition problems with restricted 2-factor in connected bridgeless cubic graphs that support the conjecture. For instance, Deciding the existence of connected 2-factor, even 2-factor, and odd 2-factor are all $NP$-complete problems. In general graphs,  Papadimitriou showed that deciding the existence of $C_k$-free 2-factor is $NP$-complete when $k \ge 5$  (A 2-factor is $C_k$-free if it contains no cycles of length $k$ or less). Also, deciding the existence of $C_4$-free 2-factor is an open problem.

  Is there a counter-example to the conjecture?

A counter-example is a polynomial-time solvable decomposition decision problem where the forbidden lengths of the 2-factor cycles form a proper non-empty subset of $N=\{5, 6, 7, ..., |V| \}$.

This is motivated by my post on CS SE.


texts: Simple Constructions of Special Graph Families

texts:
Consider the following definition, taken from Chung's 1978 paper:

  An $(n, m)$-concentrator is a graph with $n$ input vertices and $m$ output vertices,
  $n \ge m$, having the property that, for any set of $m$ or fewer inputs, a set of vertex-disjoint paths exists that join the given inputs in a one-to-one fashion to different outputs. If this graph is directed or acyclic, we call it a directed or acyclic $(n, m)$-concentrator, respectively.

The paper includes definitions for superconcentrators, generalizers, and non-blocking networks. One may also encounter other types of graphs, such as expanders and Ramanujan graphs in the literature.

These types of graphs are usually studied as "families of graphs." There are a number of papers (such as Pinsker [1], Valiant, Pippenger, and Gabber-Galil) which try to explicitly construct such families, while optimizing parameters like size, density, sparsity, and the like.

The problem is that while those papers are excellent for research, they don't help much pedagogically. Let's clarify: Consider a student who sees the definition of a concentrator (or any similar graph) for the first time. His best bet to understand the definition is to imagine it pictorially, or see an illustration of examples and non-examples of a concentrator.

I've been searching for such simple examples of Special Graph Families for quite a while, but didn't achieve much. So, the question is:

  Could you describe simple constructions of special graph families? Illustrations are much appreciated.

Note that the simple constructions need not be optimum in any sense, but they must not be trivial either (e.g. a complete graph is a trivial example for some graph families). I don't formalize the word trivial, and leave it to your judgement.

[1] M. S. Pinsker. "On the complexity of a concentrator", 7th International Teletraffic Conference, pages 318/1-318/4, 1973.


texts: what is the best heuristic to solve 3AP with Euclidean costs?

texts:
As is well known, assignment problems for $n$-partite graphs, with $n$>2 are NP-hard, where as assignment problems on bipartite graphs can be solved in polynomial time using the Kuhn's Hungarian algorithm.

There is a 1992 paper by Crama & Spieksma (link to paper) that discusses two special case of 3AP:

3AP where the cost is the sum of the costs within the triple (i.e. circumference of the triangle)
3AP where the cost is the sum of the two shortest lengths

Both are shown to still be NP hard, but the do give a heuristic, the solution of which is at most 3/2 or 4/3 of the correct solution respectively.

There is an interesting recent review paper (link to paper) by Gutin and Karapetyan discussing various heuristics for n-AP and their performance in general ,

What is the best-performing heuristic to solve class 1 of Crama & Spieksma. Is it their original heuristic as given in their paper or have there been new developments? Bonus points if it is broken down to Hungarian Algorithm for example as in Huang & Lim (PDF)


texts: Sufficient conditions to guarantee unique fixpoint (not unique least/greatest fixpoint) for monotone functions on complete lattice

texts:
Tarski's fixpoint theorem states, that the fixpoints of a monotone operator on a complete lattice is a complete lattice. By consequence, we have a unique greatest fixpoint and unique least fixpoint for a monotone operator on a complete lattice.

The fixpoints can be unique but in general can be many.

My question would be, under which conditions can a monotone function have a unique fixpoint on a complete lattice? Is there some practical sufficient conditions to guarantee a unique fixpoint? It would useful to know this, because sometimes you have a monotone operator that specifies a property. It can be non-trivial to spell out whether it is the greatest fix point or the least fix point you really want to specify. In some cases, the two coincide, and you know to iterate from top or from bottom yields the same result and you would be happy to pick up the one that is more simple or more efficient.


texts: Can we prove that for every language $L\in\mathsf{NP}$ that is not $\mathsf{NP}$-hard (this assumes $\mathsf P \ne \mathsf{NP}$), $\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}$?  Alternately, can this be proven under any reasonable assumptions?


texts: How to go about proving the basic operators in relational algebra are independent of each other?

texts: The five basic operator select, project, cross, union and diff in relational algebra are independent of each other. I'm trying to formally prove this statement but can only progress for cross product as it would have columns greater than the rest which cannot be made possible by others. But can't think of anything for Select etc.


texts: Gradient descent step size for strongly convex functions

texts:
Suppose we are optimizing a strongly convex function $f(x)$ via gradient descent $x_{t+1} = x_t - \eta_t \nabla f(x_t)$. By strongly convex I mean that $f(x+h) \ge f(x) + \langle \nabla f(x), h \rangle + \frac{\alpha}{2}||h||^2$.

This nice survey paper by Bansal and Gupta (Section 2.2) suggests using a step size $\eta_{t} = \frac{1}{\alpha (t+1)}$ and mentions it is optimal. I am curious how does the $1/(t+1)$ term pop up? Is there a simple-to-state reason for it?

For comparison, when optimizing a smooth function (i.e., upper bounded by some quadratic) the step size $\eta_t = \frac{1}{\beta}$ is very natural because it minimizes the upper bound.


texts:
I have been having a great deal of difficulty finding a reference that gives simple and straightforward explanation of the following:

Suppose we have $n$ random variables $Y_1, \dots, Y_n$, each of $b$-bits long. (I.e. with values in $\{0, \dots, 2^b-1 \}$). We want a probability space where each $Y_i$ is unbiased (takes on each value with probability exactly $2^{-b}$), and has $k$-independence. That is, for any $i_1 < \dots < i_k$ and any $y_1, \dots, y_k$ we have
$$
P(Y_{i_1} = y_1 \wedge \dots \wedge Y_{i_k} = y_k) = 2^{-k b}
$$

When $b = 1$ you can always get a probability space of size $n^{k}$ and sometimes you can get $n^{k/2}$ -- is there any clear statement about when these are possible?

Can someone point me to references about what happens when $b > 1$?

Thanks


texts: Size depth tradeoffs for monotone arithmetic circuits

texts: Are there any size depth trade-offs known for monotone arithmetic circuits that compute permanent and determinant?


texts:
In the context of constructive type theory, a term inhabiting some type is said to be in canonical form if it is explicitly built up using the constructors of that type.

Particularly, the only constructor of the identity type of $A$ is $\text{refl }:  \Pi x. \text{id}_A \text{ } x \text{ }  x$, so

  Question 1: What is a canonical term of $\text{Id}_A(x,y)$  if $x$ is not jugdmentally identical to $y$?

Apparently there cannot be such a canonical term, for neither $\text{refl } x$ nor $\text{refl } y$ type check.
Does this mean that the identity type of $A$ does not have a canonical form in general? That is, that $\text{Id}_A(x,y)$ only has a canonical form in the particular case where $x$ is judgmentally equal to $y$?

But in this case how propositional equality differs in practice from judgmental equality then – except for the fact that the former occurs as a type and the other as a judgment?

  Question 2: What is a closed term of $\text{Id}_A(x,y)$? Are there two closed terms $p, q$ of $\text{Id}_A(x,y)$ such that $p$ and $q$ are not judgmental equal?


texts: Can you partially sort using $O(\log n)$ comparisons per element?

texts:
Input is a list of $n$ integers in an array A. Desired output is stored in Array B, such that $|rank(B[i])- i | \leq \sqrt{n}$.
Can this be done using $O(\log n)$ comparisons per element?
Just looking for some unusual tricks, other than finding the $\{\sqrt{n}, 2\sqrt{n}\ldots n-\sqrt{n}\}$ ranked integers and then partitioning the rest of the elements in these sets.

In simple terms, the desired output is such that every element in the output, should be at most $\sqrt{n}$ distance away from its sorted location.


texts: Complexity of deciding whether a family is a Sperner familiy

texts:
We are given a family $\mathcal{F}$ of $m$ subsets of {1, ...,n}. Is it possible to find a non-trivial lower bound on the complexity of deciding whether $\mathcal{F}$ is a Sperner family ? The trivial lower bound is $O(n m)$ and I strongly suspect that it is not tight.

Recall that a set $\mathcal{S}$ is a Sperner family
if for $X$ and $Y$ in $\mathcal{S}$; $X \ne Y$ implies that $X \nsubseteq Y$ and $Y \nsubseteq X$.


texts:
Following Josh Grochow's suggestion, I am converting my comment from a previous question into a new question.

  What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

Here $\mathsf{UP}$ is the class of languages recognizable by polynomial time non-deterministic Turing machines that have a unique accepting path on "yes" instances and no accepting path on "no" instances.

Obviously $\mathsf{UP} \subseteq \mathsf{NP}$, but why would we believe that the containment is strict? The evidence I can find is oracle separation: subject to a random oracle, $\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$. Also, the Complexity Zoo suggests that $\mathsf{UP}$ is not believed to have complete problems.


texts: What does it mean by the statement: "a problem is hard to approximate "?

texts:
In most of the research papers that I have read so far, I often come across the statement of the following form: "the problem is hard to approximate within any factor smaller than some constant".
What is the meaning of hardness here? I am confused. Does it specifically mean NP-hardness or is it an informal way of saying: "general difficulty in obtaining the approximation"?
For example consider this paper. In the abstract, the authors have repeatedly written the statement of the form "hard to approximate". However, some of their inapproximability results are based on the Unique Games Conjecture. Therefore, considering "hard" to be "NP-hard" would be incorrect here. It would be great if somebody could clarify this terminology. Thank You.


texts: Relational model for data structure reasoning

texts:
I am trying to find out if there is any work on applying the Codd's relational model (underlying relational databases) for reasoning about linked data structures.  Any connections with UML models and reasoning about them (other than drawing diagrams) would also be of interest to me.

[There is of course a lot of work - and tool sets - for mapping data structures to relational databases and back.  But my interest is in reasoning about in-memory data structures using relational models.]

[For example, a doubly-linked list can be represented in the relational model as a pair of relations: $successor$ and $predecessor$, tied together by a couple of integrity constraints $successor(x,y) \Rightarrow predecessor(y,x)$ and its converse (modulo boundary cases).  In more interesting examples, we would have tons of relations and constraints.  The question I am wondering about is whether the relational database theory can help us get handle on how to build good data structures, modularise them appropriately and provide some structure to the constraints (or "invariants") so that it is easier to verify them or to ensure correctness by construction.]


texts: A public key cryptographic technique usable without aid of computer

texts:
I wondered if there is any known algorithm for secure messaging without pre-shared keys (i.e. public key cryptography) that is practical to use without the aid of a computer?

Obviously I would not expect it to be as secure as modern 256-bit encryption, but I wondered whether it was theoretically possible that older civilizations ever could have used something akin to public key cryptography, perhaps something with a computational complexity on the order of the Vigenere technique but without the need for a pre-arranged shared key?


texts: Preserving termination when rewriting recursive programs

texts:
Powerful program transformations like partial evaluation, deforestation and supercompilation are based on applying three kinds of transformations:

Rewrite using axioms, e.g. a+b = b+a.
Unfolding/inlining: replace a function call with the body of the function.
Folding/un-inlining: replace a subexpression that matches the body of a function with a call to the function.

Each of these transformations will not change the result of a computation if it still terminates, but rule #3 may introduce non-termination. Here is a simple example of this. We have this program:

f(x) = x+1

We apply transformation #3 to the expression (x+1) and replace it with an equivalent function call:

f(x) = f(x)

Now the program doesn't terminate any more (infinite recursion). Rule #3 is however essential for powerful program transformations (see example below).

Transformations like deforestation and supercompilation ensure that termination behavior is not changed as a side effect of how these algorithms work. However, whether or not a sequence of transformations preserves the termination behavior is a property of the sequence itself, independent of any algorithm that generated it. My question is: how can we limit the application of the rules in such a way that a terminating program is never turned into a non-terminating program, but is still sufficiently general to allow useful program transformations, like deforestation and supercompilation (and hopefully, more)?

Algorithms like deforestation and supercompilation intertwine in their execution the search for good program transformations with ensuring that they preserve termination. I'm looking for a way to separate that into two problems: (1) characterizing a class of transformations that preserve termination (2) the search for good transformations in that class.

Here is an example. Suppose we have an append function in a language like Haskell:

app xs ys = case xs of
            [] -> ys
            x:xs' -> x:(app xs' ys)

And we have a function that appends three lists:

app3 a b c = app (app a b) c

The problem with this is that the outer app copies the (app a b), so the newly constructed list immediately becomes garbage. We can avoid this with a transformation:

Step 1. Unfold the inner app:

 app3 a b c = app (case a of
                  [] -> b
                  x:a' -> x:(app a' b)) c

Step 2. Apply an axiom that distributes a function over a case expression:

app3 a b c = case a of
             [] -> app b c
             x:a' -> app (x:(app a' b)) c

Step 3. Unfold the outer app:

app3 a b c = case a of
             [] -> app b c
             x:a' -> case x:(app a' b)
                     [] -> c
                     x:d -> x:(app d c)

Step 4. Apply axiom to eliminate dead case alternative:

app3 a b c = case a of
             [] -> app b c
             x:a' -> x:(app (app a' b) c)

Note that this is the step where the needless allocation is eliminated! We eliminate the pair x:(app a' b), because it then is immediately destructured again.

Step 5. Fold the expression app (app a' b) c:

app3 a b c = case a of
             [] -> app b c
             x:a' -> x:(app3 a' b c)

This function is equivalent to the original one, but more efficient because it does not construct an intermediate list. Note that the after step 4, only a single node allocation is eliminated. By folding in step 5, we generalize that to eliminating the allocation of the entire list (supercompilation can do this transformation automatically).


texts: Is the edge cover polytope integral on graphs with self-loops?

texts:
It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops.
Here is a Linear Relaxation of the edge cover polytope, which I am trying to show is integral:
(1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$
(2) For each $S \subseteq V, |S|$ is odd, $\sum_{e \in E[S] \cup \delta(S)} x_e \geq \frac{|S| + 1}{2}.$
(3) For each $e \in E$, $0 \leq x_e \leq 1.$
Here $\delta(S)$ is the set of edges with exactly one endpoint in $S$ - note that this includes self-loops on vertices in $S$. However, $E[S]$ does not count self-loops. With these definitions it can be shown that these inequalities are valid for the edge cover polytope.
To show this, my goal is to reduce this problem to the integrality of the edge cover polytope on simple graphs.
Here is my idea: given a graph $G$ which may have self-loops, we construct a doubled graph $\tilde G$ which has two copies of the nodes in $G$. Also, if $v$ had a self-loop in $G$, then we put a "bridge" edge $e = (v,v')$ between the two copies of vertex $v$ in $\tilde G$.
I want to say that given an edge cover $x$ in $G$, it can be made into an edge cover $\tilde x$ in $\tilde G$ by duplicating the graph, and putting the value of the self-loops onto the bridges. But does $\tilde x$ satisfy all the odd set constraints for $\tilde G$? In some sense my problem reduces to the following:
In $\tilde G$ suppose that $\tilde x$ satisfies all odd sets $S$ which lie on ONE SIDE of the graph. Then can we show that actually all odd set constraints are satisfied?


texts: Efficient game traversal of a DAG of 3-colorings

texts:
Let $X$ be a set of size $n$.  Consider a game played on board $X$ by two players black and white.  Starting with the empty board, each player chooses an empty spot to place a stone.  Black moves first.  There is some rule determining the winner at each end state, but this rule does not matter for the question.  I am interested in memory efficient traversals of the graph of positions in this game.

Formally, $C = \{e, w, b\}$ the set of colors each $x \in X$ can have (empty, white, or black).  Let
$$S_k = \{f : X \to C | f^{-1}(w) = \lfloor k/2 \rfloor, f^{-1}(b) = \lceil k/2 \rceil\}$$
be the set of possible states after $k$ moves, and $S = S_0 \cup \cdots \cup S_n$.  We define a leveled directed graph on $S$ by connecting each state to all ways of adding one more stone of the appropriate color.

We are given the result of the game at each $S_n$, and want to back this up to the result at $S_0$.  The result at a state depends only on the state and the result of its immediate successors.

The simplest way of doing the traversal is to compute all results for each layer $S_k$ in backwards order of $k$.   The largest layer is at $k \approx 2n/3$, and we need to store one input layer and one output layer at a time, so the peak memory is roughly
$$2\left|S_{2n/3}\right| \approx \frac{2(n!)}{(n/3)!^3}$$

Question: Is there a way of traversing this graph of positions using significantly less memory, while still computing the result of each state only once?  Is there an available time-space tradeoff?

Motivation: A better algorithm here would reduce the memory usage for midgame solving at https://perfect-pentago.net.  In this case, $n = 18$.


texts: Classes and types in object-oriented languages

texts:
In typical object-oriented programming languages like Java, classes are used as types.  On the other hand, type-theoretic approaches to object-oriented languages treat interfaces as types.

Are there any theoretical frameworks that formalize the use of classes as types?


texts: Finding the cardinality of classes that divide all possible directed graphs into those that share k-subgraph cardinalities?

texts:
Let us have a set of nodes $V$, such that $|V|=N$. Let $G= (V,E)$  be an arbitrary directed graph on $V$. Let $U$ be the set of all possible directed graphs on $V$.Hence, $|U| = 2^{|V|^2}$. Now,  for a given directed graph $G$, we define $G[k]$ as the set of all $k$-subgraphs on $G$. Hence, for any $G$, $|G[k]| = \binom{|V|}{k} $. Now, let $O_{k}$ be the set of all possible $k$-sized directed graphs, then all the k-subgraphs in $G[k]$ must be isomorphic to one of the elements of $O_k$, which has a size $2^{k^2}$.
For any graph $G$ let $G(k) = <a_1,a_2...a_{2^{k^2}}>$ be a vector, such that $a_i$ is the number of  k-subgraph in $G$ which are  isomorphic to the $i^{th}$ element in  $O_{k}$. What is the most efficient way of finding the number of $G's$ that share the same $G(k)$ ?
PS: The number of $G's$ counts isomorphic graphs distinctly.


texts: Improving Cook's generic reduction for Clique to SAT?

texts:
I am interested in reducing $k$-Clique to SAT without making the instance much larger.

Clique is in NP so it can be reduced to SAT using logarithmic space.
The straightforward Garey/Johnson textbook reduction blows up the instance to cubic size.
However, $k$-Clique is in P for every fixed $k$ so there "ought" to be an efficient reduction at least for fixed $k$.

One way to build the reduction is by using the SAT variables as a characteristic vector, with a variable that is set to true indicating that the associated vertex is in the clique.
This reduction is natural but creates a SAT instance of quadratic size if the graph is sparse.
For a sparse graph, quadratically many clauses are required to enforce that in every pair of non-adjacent vertices at most one vertex may be in the clique.

Let's try to do better than $O(n^2)$.

The generic reduction of Cook/Schnorr/Pippenger/Fischer works by first taking a polynomially time-bounded NDTM that decides the language, simulating the NDTM by an oblivious DTM, simulating the oblivious DTM by a circuit, and then simulating the circuit by a 3-SAT instance.
This creates a 3-SAT instance of size $O(t(n)\log t(n))$ if the NDTM time bound is $t(n)$.
The log factor seems unavoidable due to overhead when simulating by an oblivious machine.
For $k$-Clique one seems to have $t(n) = O(nk)$, which yields a 3-SAT instance of $O(nk(\log n + \log k))$ size, which is quasilinear for fixed $k$.
In his 1988 paper Cook asked whether a better generic reduction exists for languages in NP, and as far as I know this is still open.
However, Clique has a lot of structure so perhaps one can do better in this case.

  Is there a better reduction known from Clique to SAT?

In particular, is it possible for fixed $k$ to reduce $k$-Clique to SAT while keeping the increase in instance size linear?
Or can one use an existing result to argue that this is unlikely to be possible?
I have tried using Fortnow/Santhanam and Dell/van Melkebeek but the overheads seem too large for these results to imply anything specific.

(I have been working with a reduction that seems to avoid the log factor, but before wasting more time on the gory details to verify its correctness, I'd like to know if such a reduction is already known, or if it is unlikely to exist.)


texts:
I am looking for an efficient encoding algorithm $E:\{0,1\}^n\to\{0,1\}^m$ such that given $E(x)\oplus E(y)$ for $x\neq y$, we can reconstruct $x$ and $y$.
One example of such an algorithm would be mapping from $\{0,1\}^n$ to $\{0,1\}^{2^n}$ using a unit vector with $1$ only at the input coordinate. However, this is not an efficient solution in $n$.
I thought of maybe working over $GF(2^n)$ and mapping $x$ to $x^2,x$ or something of the sort, but I do not know if we can reconstruct efficiently and with certainty $x,y$ from $x^2+y^2,x+y$.
What do you think?
Thanks


texts:
The following is a fun problem we stumbled into today.

We have work we wish to distribute on machines $1..n$. Each piece of work is given a list of machines to try, in order. If any machine fails, the work is passed on to the next machine. We desire to make this as fair as possible. That is to say, all work is initially divided as evenly as possible. If any one machine fails, the leftover work should be distributed among all remaining machines as close to equally as possible. If two machines fail, we wish the same property to hold, all the way up to $n-1$ machines.

If we generate all permutations, and assign each piece of work one of the permutations (cycling through after exhausting them), in sequence, then this property should hold, assuming a large enough quantity of work.

But now we add a requirement that we want good results for small quantities of work, and generally quantities of work that aren't evenly divided by the number of permutations, and things get harder. We want a suitable ordering on permutations such that for any $m$, the optimal distribution/optimal redistribution property holds as closely as possible.

Here's an example of the first four elements of an optimal distribution/redistribution list for four machines:

a) 1 2 3 4
b) 2 1 4 3
c) 3 4 1 2
d) 4 3 2 1

Trivially, if any one number is removed, its work goes to one other location. Similarly, if any three numbers are removed, all work falls to the remaining machine. However, also note that for any choice of two failures, the remaining work remains evenly distributed. I.e. if 1 and 4 fail, list $a$ falls back to 2, and the list $d$ falls back to 3, preserving fairness.

Given an optimal list of length $n$ consisting of choice lists also of length $n$, we can treat it as a matrix. It should, I think, always have the property that there is not only only one entry of any number per row, but also per column (shades of generalized soduku). If this is the case, then by holding the first column fixed, we can generate all remaining permutations (and optimal lists of length $n$) by taking permutations on the remaining columns.

Has this problem been studied before? Under what name? Is the production of a list that preserves optimal distribution/redistribution for any $m$ possible? How close can we get? What is the nicest algorithm for it?

Or, more basically, what is the simplest algorithm for generating an optimal distribution list of length $n$?


texts: Major unsolved problems in theoretical computer science?

texts:
Wikipedia only lists two problems under "unsolved problems in computer science":

P = NP?
The existence of one-way functions

What are other major problems that should be added to this list?

Rules:

Only one problem per answer
Provide a brief description and any relevant links


texts: Does the Hindley-Milner type system (i.e. STLC with prenex polymorphism) have a category-theoretic model?

texts:
It is well known that any CCC (cartesian closed category) is a model of the simply-typed $\lambda$-calculus. It is less well known that System F admits a categorical model, but it is also well studied (see, e.g., Amadio & Curien, Domains and Lambda-Calculi).
H-M lies between STLC and System F, but can we find a sensible categorical model for it? Particularly, I am interested in studying type inference in this categorical framework. Can we give H-M type inference a category-theoretic specification?
This presentation by Kammar and Moss presents some ideas in this direction, but I wonder if there's more work on this, particularly work that incorporates type inference.


texts: What is the value of this "game" (counters rebalancing)?

texts:
This question was posted in CS.SE two weeks ago, but it didn't get a satisfying answer.

Suppose you have the following game:

There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized to 0.

In each step, you choose a counter $c_i$ and increase it's value by 1.

Unfortunately, every $T$ steps, each counter that has a positive value is decremented by 1.

Also, the values of the counters are bounded by $M$, so you can't increment a counter any further.

  1. Given as many steps as you like, can many positive valued counters can you reach?

  2. How many positively valued counters are reachable after $T\cdot M - 1$ steps?

For question (1), here's a a detailed buildup for $\approx T\log(M)$ positive counters:

While you have less than $T-1$ counters at value $M$:

Increment the minimal index counter whose value is strictly less than $M$.

(This has to converge as the sum of the counters are bound to increase every $T$ steps.)

Let $r = T$.
While ($c_0>1$)

a.  while ($c_0>c_r$)

Increment $c_r$

b. $r = r + 1$

Now for the analysis: first observation is that the number of positive counters is $r$.

Now let $m_r$ be the maximal value $c_{r}$ have reached. For $r=T$ we get $M(1-\frac{1}{T})$. For $r=T+1$ we get $m_r(1-\frac{1}{T})=M(1-\frac{1}{T})^2$, or in general $$\forall r\geq T:m_r = M(1-\frac{1}{T})^{r-T+1}$$

Next we notice that when $\forall m_r$ is achieved, $c_0=m_r$.
This means the loop will halt when $m_r < 1$ (give or take integrality and end-of-game-strategies).

This gives us
$$M(1-\frac{1}{T})^{r-T+1} < 1$$
$$(1-\frac{1}{T})^{r-T+1} < M^{-1}$$
$$({r-T+1}) \log (1-\frac{1}{T}) < -\log M$$
$${r-T+1}  < \frac{-\log M}{\log (1-\frac{1}{T})}$$
$$r  < \frac{-\log M}{\log (1-\frac{1}{T})} + T - 1$$
$$r  < \frac{\log M}{\sum_{k\geq 1}^{\infty} {\frac{1}{kT^k}}} + T - 1 < T(\log M + 1) -1$$

Is it possible to do better? Can anyone prove this is optimal?


texts:
Given a threshold $k$ is it possible to make a succinct data structure $S$ to answer queries of the form,  given query $x$ does there exist a value $s$ in $S$ such that $s-k \leq x \leq s+k$?  Like a Bloom filter it would allow rare false positives and would only report yes or no.

To clarify a little, I am looking for a data structure that uses much less space than a binary search tree would but with comparable or better performance. Also, what is theoretical minimum space for a randomized data structure for this problem with a given false positive rate?

Another related problem is (1d) emptiness queries in computational geometry but in our case the range is fixed in advance.


texts: This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this question?


texts: Canonical forms for relational algebra expressions

texts:
I'm looking for whatever work may exist, or thoughts people have, on the question of whether/to what extent there exist(s) one or more canonical form(s) to which relational algebra expressions may be reduced.

I'm investigating the feasability of building a relational query optimizer which allows hand-writing of query plans but proves (or assists the user in proving) that the plan satisfies the query.

If there isn't a (usefully non-enormous) canonical form, then I wouldn't know the first thing about how to attack the problem. I suppose read up on Coq or Isabelle, work on translating my equivalence question into theorem prover's language, and work on providing a less-grad-school-required interface that exposes (relevant parts of) the theorem prover's output.

If there is a canonical form that doesn't tend to blow up to enormous sizes, then of course its a much easier problem.


texts: Is there any known result for 1-median problem with negative weights in Euclidean space?

texts:
Given a set of $n$ points $v_1,\ldots,v_n$ in $R^d$, find a point $p$
  such that $\sum_{i=1}^n w_i d(p,v_i)$ is minimized, where $w_i$ is the
  weight of $v_i$, which may be  positive or negative.

Is there any known result for this problem. It seems the problem has been considered in graphs (one, two). What about in $R^d$ ?  Due to the negative weights, the problem is not convex any more.


texts: Information theoretic characterization and consequences of reductions between computational problems

texts:
For two computational problems $A$ and $B$ in complexity class C (let say $NP$), the existence of a reduction $A <_m^L B$ computable in class (say $L$) implies that $A$ is not computationally harder than $B$ and $B$ is at least as hard as $A$.

I am interested in information theoretic characterization and implications for the existence and non-existence of $<_m^L$-reductions between computational problems. I'm aware of concepts such as computational entropy and hardness amplification but my limited understanding of these notions, which I guess originated from cryptographic applications, does not seem to shed light on the information theoretic characterization of $<_m^L$-reductions.

What is known about information theoretic characterization and consequences of the existence and non-existence of such reductions? Can notions such as computational entropy and hardness amplification help in answering my previous question?


texts: Stronger Lower Bounds on Nondeterministic Multiparty Communication

texts:
This is a continuation of my previous question on Lower bounds for Nondeterministic Multiparty Communication.

From the answer, the $\mu^\infty$ norm lower bounds nondeterministic multiparty communication in the number-on-the-forehead model (see the paper by Lee and Shraibman). The problem is that for any given sign matrix $M$, $\mu^\infty(M)=1/Disc(M)$, where $Disc(M)$ is the discrepancy of $M$. It is a problem because the best lower bounds we can prove using discrepancy are polylogarithmic in the size of the input. For example, for disjointment with $k$ parties the lower bound is $\Omega(\log n/(k-1))$. In the same piece of work, the authors show that for randomized protocols, disjointment requires $\Omega(\frac{n^{1/(k+1)}}{2^{2^k}})$ using the $\mu^\alpha$ norm.

Is there any other norm stronger than discrepancy that can be used for lower bounds in nondeterministic multiparty communication? Or is it tight? These results are very recent, so maybe this is an open problem.

Edit(dec/8/2010): I have two more questions,

2) Corruption (cf. Lee and Shraibman 2007, section 4.5) is used for lower bounding 2-sided error randomized communication. Is there any extension of corruption to nondeterminism? A nondeterministic protocol accepts with probability strictly greater than 0, and rejects with probability 1.

3) Is there any other lower bound based on information-theoretic arguments?


texts: K-fold Traveling salesman problem - A variant of TSP

texts:
Consider a weighted graph $K_n$ and where the weights between vertices $i,j$ is $w_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma_i$ is the vertex in the $(i\%n)^{th}$ step of the path. (For example, $\sigma_{n+1} = \sigma_1$)

Traveling salesman problem (TSP) minimizes the following objective : $$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}$$

A variant of TSP, 2-Fold TSP, will additionally consider the weights between the 1-skipped vertices on the path. The objective of a 2-Fold TSP is to minimize

$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}$$

and similarly the objective of K-fold TSP is to minimize

$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}+\cdots+w_{\sigma_i,\sigma_{i+k}}$$

Question

Can this be reduced to the original TSP?
Is there any reference which deals with k-fold TSP? What is the name of this problem in the literature?
Any heuristics/approximation algorithms?


texts: Why do people like using evolution computing techniques like GA on multi-objective optimisation?

texts:
I am new to the field of multi-objective optimisation and I try to find some books to read on this topic.

Yet when I search around my library I found there are many books on using evolution computing technique like GA on multi-objective optimisation.

Why is there such a strong link between this the problem and this technique?

p.s. I saw some books talk about reducing the problem into single objective optimisation and make use of conventional optimisation techniques but its always a small chapter, any suggesting materials on this direction?


texts: how to achieve a topological sort of an given sequence with minimum swaps

texts: For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum swaps


texts:
In his answer to this question, Stephane Gimenez pointed me to a polynomial-time normalization algorithm for proofs in linear logic. The proof in Girard's paper uses proof nets, which are an aspect of linear logic I don't actually know very much about.

Now, I've tried to read papers on proof nets before (such as Pierre-Louis Curien's notes on them), but I have not really understood them.  So my question is: how should I think about them? By "how to think about them", I mean both the informal intuition behind them (e.g., how they behave computationally, or how they are related to  sequents), and also which theorems about them I should prove for myself to really get them.

In answering this question, you can assume (1) I know the proof theory of linear logic well (including things like how the cut-elimination proof goes, and in focalized form too), (2) their categorical semantics in terms of coherence spaces or via Day convolution, and (3) the very basic rudiments of the GoI construction.


texts:
Objective: Settle the conjecture that there is no projective plane of order 12.

In 1989, using computer search on a Cray, Lam proved that no projective plane of order 10 exists.  Now that God's Number for Rubik's Cube has been determined after just a few weeks of massive brute force search (plus clever math of symmetry), it seems to me that this longstanding open problem might be within reach.  (Plus maybe we could use such techniques to solve something mathematically fundamental.)  I'm hoping this question can serve as a sanity check.

The Cube was solved by reducing the total problem size to "only" 2,217,093,120 distinct tests, which could be run in parallel.

Questions:

There have been several special cases of nonexistence shown.  Does anyone know, if we remove those and exhaustively search the rest, if the problem size is on the order of the Cube search?  (Maybe to much to hope for that someone knows this....)
Any partial information in this vein?

Edited to add: I asked this question on MathOverflow here.  So far it seems as though no search space reduction is achieved from the known partial results.  I still don't know the size of the total search space.


texts: Which monotone Boolean functions are representable as thresholds on sums?

texts:
I will introduce my problem with an example. Say you are designing an exam, which consists of a certain set of $n$ independent questions (that the candidates can get either right or wrong). You want to decide on a score to give to each of the questions, with the rule being that candidates with total score above a certain threshold will pass, and the others will fail.

In fact, you are very thorough about this, and you have envisioned all the possible $2^n$ results, and decided for each of them whether a candidate with this performance should pass or fail. So you have a Boolean function $f : \{0, 1\}^n \to \{0, 1\}$ that indicates whether the candidate should pass or fail depending on their exact answers. Of course this function should be monotone: when getting a set of questions right makes you pass, getting any superset right must make you pass as well.

Can you decide on scores (positive real numbers) to give to the questions, and on a threshold, so that your function $f$ is exactly captured by the rule "a candidate passes if the sum of scores for the correct questions is above the threshold"? (Of course the threshold can be taken to be 1 without loss of generality, up to multiplying the scores by a constant.)

Formally: Is there a characterization of the monotone Boolean functions $f: \{0, 1\}^n \to \{0, 1\}$ for which there exist $w_1, \ldots, w_n \in \mathbb{R}_+$ such that for all $v \in \{0, 1\}^n$, we have $f(v) = 1$ iff $\sum_i w_i v_i \geq 1$?

It is not so hard to see that not all functions can be thus represented. For instance the function $(x_1 \wedge x_2) \vee (x_3 \wedge x_4)$ cannot: as $(1, 1, 0, 0)$ is accepted we must have $w_1 + w_2 \geq 1$, so one of $w_1, w_2$ must be $\geq 1/2$, and likewise for $w_3, w_4$. Now, if it is, e.g., $w_1$ and $w_3$, we have a contradiction because $w_1 + w_3 \geq 1$ but $(1, 0, 1, 0)$ is rejected; the other cases are analogous.

This looks to me like a very natural problem, so my main question is to know under which name this has been studied. Asking for a "characterization" is vague, of course; my question is to know whether the class of functions that can be represented in this way has a name, what is known about the complexity of testing whether an input function belongs to it (given as a formula, or as a circuit), etc.

Of course one can think of many variations on this theme. For instance, on real exams, questions are not independent, but there is a DAG on questions indicating the dependence, and candidates can only answer a question if all prerequisites have been answered. The condition on the monotone functions could then be restricted to valuations in $\{0, 1\}^n$ that satisfy the dependencies, and the question would be to determine whether an input function can be thus captured given an input DAG on the variables. One could also think of variants where the scores are $k$-tuples for fixed $k$ (summed pointwise, and compared pointwise to a threshold vector), which can capture more functions than $k = 1$. Alternatively you could want to capture more expressive functions which are not Boolean but go to a totally ordered domain, with different thresholds that should indicate your position in the domain. Last, I'm not sure about what would happen if you allowed negative scores (so you could drop the monotone restriction about the functions).

(Note: What made me wonder about this is the Google Code Jam selection round, where candidates are selected if they reach a certain score threshold, and the scores of problems are presumably carefully designed to reflect what sets of problems are deemed sufficient to get selected. Code Jam has a dependency structure on the questions, with some "large input" questions that cannot be solved unless you have solved the "small input" one first.)


texts: Programming Language Theory and Abstract Algebra

texts: Are there any applications of Abstract Algebra to Programming Language Theory? Is there anything that would be useful in language design and compiler implementation?


texts:
The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, suppose all Fourier coefficients are at most $\epsilon$.

The argument is a simple application of Cauchy—Schwarz with the fact Fourier preserves the $L_2$ norm to obtain:

$$|U-D|_1 \leq 2^{n/2} \epsilon$$

How tight is this? I obviously care about the exponent of $2$, not a constant outside.

I was a certain a 'probabilistic' $D$ would show tightness but that doesn't seem to be the case. Below is an explanation:

Consider generating $D$ as follows: let $D(x)$ be $\frac{1}{2^n} + z(x)\frac{\epsilon}{2^{n/2}}$ where $z(x)$ is iid on $\{-1,1\}$.

Even if we ignore this is probably not a distribution (I'm trying to point here that a probabilistic construction seems to fail so that's okay.) , this can't be turned into a tight example since there are so many Fourier coefficients, one of them will correlate significantly more in signs than the random $2^{n/2}$ with our $z$, and then we'll get more than $2^{n/2} \frac{\epsilon}{2^{n/2}}$.

Thus tightness if it exists needs to come from a controlled pseudorandom construction.

EDIT-
As clement posted in a comment, bent functions are apparently a thing and clearly solve our tightness.

First notice that if $f,g$ are each bent functions on a different set of variables, then so is $fg$. Thus if there is one for $m,n$ variables, there is one for $m+n$.

Now consider $1/2-1/2x+1/2y+1/2xy$, it's a bent function in two varibles, so tensoring gives for any even $n$ gives a bent function.


texts: Span programs, witness size, and certificate complexity

texts:
A span program is a linear-algebraic way of specifying a boolean function introduced here. Recently, this model was used to show that the negative adversary method provides a tight characterization (at least up to $\log n/ \log \log n$) of quantum query complexity.

The complexity measure connecting span programs to quantum query complexity is witness size. This measure seems rather similar to certificate complexity. Are there known connections between the two measures? What about the size (number of input vectors) measure for span programs and other measures like deterministic and randomized query complexity? What are the best known classical algorithms for evaluating span programs?

EDIT (after an answer by Martin Schwarz):

Of particular interest are conceptual connections that go directly through span programs as opposed to through the correspondence between witness size and quantum query complexity. Are there classical results that provide intuition about span programs/witness size and how they relate to deterministic and randomized query complexity?


texts: Diameter Constrained Minimum Spanning Graph

texts:
The idea of a diameter constrained MST is that you keep all vertices connected and within a certain distance of each other. But all papers I've seen keep the requirement that you produce a tree, when allowing cycles could help reduce the diameter. Does anyone know any papers that explore this? (It's difficult to search for.)

For example, consider a complete graph with vertices arranged in a circle on a plane (edge weight = Euclidean distance). The MST (e.g. via Prim's) will follow the circle, so that the diameter of the graph is roughly the circumference of the circle. By allowing the final edge to be connected we can halve the diameter, without increasing the total weight much.


texts:
In Short: Assuming one-way permutations exist, can we construct one that has no trapdoor?
More info:
A one-way permutation is a permutation $\pi$ which is easy to compute, but hard to invert (see the one-way-function tag wiki for a more formal definition). We usually consider families of one-way permutation, $\pi = \{\pi_n\}_{n \in \mathbb{N}}$, where each $\pi_n$ is a one-way permutation, acting on a finite domain $D_n$. A trapdoor one-way permutation is defined as above, except that there exists a trapdoor set $\{t_n\}_{n \in \mathbb{N}}$ and an poly-time inverting algorithm $I$, such that for all $n$, $|t_n| \le {\rm poly}(n)$, and $I$ can invert $\pi_n$ provided that it is given $t_n$.
I know one-way permutations which are generated so that it is infeasible to find the trapdoor (yet the trapdoor exists). An example, based on RSA-assumption, is given here. The question is,

Do there exist (families of) one-way permutations which do not have a trapdoor (set)?

Edit: (More Formalization)
Assume there exists some one-way permutation $\pi$ with (infinite) domain $D \subseteq \{0,1\}^*$. That is, there exists a probabilistic polynomial-time algorithm $\mathcal{D}$ (which, on input $1^n$, induces some distribution over $D_n=\\{0,1\\}^n \cap D$), such that
for any polynomial-time adversary $\mathcal{A}$, any $c>0$, and all sufficiently large integer $n$:
$\Pr[x \leftarrow \mathcal{D}(1^n) \colon \quad \mathcal{A}(\pi(x))=x]<n^{-c}$
(The probability is taken over the internal coin tosses of $\mathcal{D}$ and $\mathcal{A}$.)
The question, is whether we can construct a one-way permutation $\pi'$, for which there exists a probabilistic polynomial-time algorithm $\mathcal{D}'$ such that for any poly-size family of circuits $\mathcal{A}'=\{\mathcal{A}'_n\}_{n \in \mathbb{N}}$, any $c>0$, and all sufficiently large integer $n$:
$\Pr[x \leftarrow \mathcal{D}'(1^n) \colon \quad \mathcal{A}'_n(\pi'(x))=x]<n^{-c}$
(The probability is taken over the internal coin tosses of $\mathcal{D}'$, since $\mathcal{A}'$ is deterministic.)


texts: How to state the adequacy of an encoding of lambda calculus in itself?

texts:
In the paper Discriminating coded lambda terms - Henk Barendregt a coding $\ulcorner M \urcorner$ of a lambda term $M$ is a term such that $M$ (and its parts) can be reconstructed from it in a lambda-definable way. Essentially we need to be able to write a self-interpreter $\mathsf E$:

$$\mathsf E \ulcorner M \urcorner =_\beta M.$$

There are a variety of encodings like Kleene's which uses natural numbers and the most efficient modern encoding is a higher-order syntax by Mogensen. Another possible (trivial) encoding is the identity function, then the interpreter is again the identity function.

  Is there any reasonable notion of an "adequate encoding" that outlaws trivial encodings?

This question came up when considering the halting problem applied to lambda calculus rather than Turing machines: If stated in terms of the trivial encoding then it holds for the trivial reason that there is essentially nothing we can do with a quoted lambda term.

Put differently: What is the set of functions that we should expect to be able to compute on quoted lambda terms?

I can list a few like: counting the depth of the term, taking subterms, telling if the root node of a term is a lambda or application, ... but I would hesitate to define an "adequate encoding" by just listing assorted functions that came to mind.


texts: Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

texts:
A recent question discussed the now-classical dynamic programming algorithm for TSP, due independently to Bellman and Held-Karp.  The algorithm is universally reported to run in $O(2^n n^2)$ time.  However, as one of my students recently pointed out, this running time may require an unreasonably powerful model of computation.

Here is a brief description of the algorithm.  The input consists of a directed graph $G=(V,E)$ with $n$ vertices and a non-negative length function $\ell\colon E\to\mathbb{R}^+$.  For any vertices $s$ and $t$, and any subset $X$ of vertices that excludes $s$ and $t$, let $L(s,X,t)$ denote the length of the shortest Hamiltonian path from $s$ to $t$ in the induced subgraph $G[X\cup\{s,t\}]$.  The Bellman-Held-Karp algorithm is based on the following recurrence (or as economists and control theorists like to call it, “Bellman's equation”):

$$
    L(s,X,t) = \begin{cases}
       \ell(s,t) & \text{if $X = \varnothing_{\strut} $} \\
       \min_{v\in X}~  \big(L(s, X\setminus\lbrace v\rbrace, v) + \ell(v,t)\big)
              & \text{otherwise}
    \end{cases}
$$

For any vertex $s$, the length of the optimal traveling salesman tour is $L(s,V\setminus\{s\}, s)$.  Because the first parameter $s$ is constant in all recursive calls, there are $\Theta(2^n n)$ different subproblems, and each subproblem depends on at most $n$ others.  Thus, the dynamic programming algorithm runs in $O(2^n n^2)$ time.

Or does it?!

The standard integer RAM model allows constant-time manipulation of integers with $O(\log n)$ bits, but at least for arithmetic and logical operations, larger integers must be broken into word-sized chunks.  (Otherwise, strange things can happen.)  Is this not also true of access to longer memory addresses?  If an algorithm uses superpolynomial space, is it reasonable to assume that memory accesses require only constant time?

For the Bellman-Held-Karp algorithm in particular, the algorithm must transform the description of the subset $X$ into the description of the subset $X\setminus\{v\}$, for each $v$, in order to access the memoization table.  If the subsets are represented by integers, these integers require $n$ bits and therefore cannot be manipulated in constant time; if they are not represented by integers, their representation cannot be used directly as an index into the memoization table.

So: What is the actual asymptotic running time of the Bellman-Held-Karp algorithm?


texts: Is a quadratic nondeterminism speed-up of deterministic computation plausible?

texts:
This is a follow up to
nondeterministic speed-up of deterministic computation.

Is it plausible that nondeterminism (or more generally alternation)
would allow a general quadratic speed-up of deterministic computation?
Or are there any known implausible consequences for something like
 $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$?


texts:
I am trying to understand these subtle differences between LTL and CTL logic and one thing I simply don't have an idea how to understand.

Formula

AG AF p

in CTL and a formula

GF p

in LTL. Why aren't they equivalent? Can you give me an example, please? I tried finding and drawing things, but I simply can't find a counter example and there is no explanation in the lecture materials I have.


texts: Statistical Distance Growth Given K Independent Copies

texts:
Let $X$ and $Y$ be distributions with statistical distance (total variation distance) at most $d$. What is the best upper bound you can give on the statistical distance between $k$ independent copies of $X$ and $k$ independent copies of $Y$?
I can show using a "hybrid argument" that it is at most $k\cdot d$, and I am looking for something better (maybe not always, but at least in some cases).

For example if $d=1/2$ and $k=2$ this bound is $1$ which is meaningless and it cannot be reached by actual distributions because $X_1,X_2$ and $Y_1,Y_2$ have statistical distance $1$ iff their supports are disjoint which would imply that the supports of $X$ and $Y$ are also disjoint in contradiction to $X$ and $Y$ having statistical distance at most $1/2$. The best example I could find was $X\equiv1$ and $Y$ being a uniformly distributed bit so the distance between $X$ and $Y$ is $1/2$ and the distance between $X_1,X_2$ and $Y_1,Y_2$ is $3/4$.

For general $k,d$ I'd like to show that the distance between $k$ samples of $X$ and $k$ samples of $Y$ is at most $1-\left(1-d\right)^k$. (For sanity check: $\left(1-d\right)^k\geq 1-d\cdot k$ for $k\geq 1,d\in\left[0,1\right]$ can be easily shown using basic calculus).
Can you do better (give a counter example), or can you prove that it is the best?


texts: Complexity of hex with random turn order.

texts: I've been thinking of a variant of hex, where instead of the two players making moves alternately, each turn a player picked at random makes a move. How hard is it to determine the chances for each player winning? This problem is obviously in PSPACE, but can't it to be NP-hard, much less PSPACE-complete. The difficulties come from how the randomness makes it impossible for a player to be forced into making a choice among options; if that player is lucky he gets enough moves two take both options, and if the player is unlucky the opponent gets enough moves to block both options. On the other hand, I can't think of any polynomial-time algorithms for this.


texts: Latest results on the k-stacker crane problem?

texts:
I was searching for the $k$-stacker crane problem on google scholar but the best known result is dated back to 1976 with the original paper. I'm unsure whether there would be newer results of the problem, or there are related problem of different names.
Problem description: the 1-SCP problem has a mixed graph and asks for a tour starting from a point $s$ of minimum length so that all arcs are traversed. The $k$-SCP problem is the same but we now need to find k tours so that each arc are traversed at least once, and we want to minimize the maximum tour length.


texts:
This question is probably on the border line between on-topic and off-topic, however I've seen similar questions here, therefore I'll ask it.

I'm implementing a Unique $k$-SAT solver, whose input is a $k$-CNF formula having at most $1$ satisfying assignment. To test its practical behaviour, I need a set of such formulas. I've searched for them on the web, and found nothing (while, on the other hand, it is very easy to find suites of ordinary $k$-CNF formulas).

  Where can I find Unique $k$-SAT instances?

Alternatively, I would be content also to know any procedure to generate uniquely satisfiable instances. The only approach I'm aware of goes under the name of planted SAT instance generation: you randomly generate an assignment of $n$ variables, then you generate only those clauses which agree with such assignment. This approach is unsatisfactory for my purposes, for the following reasons:

The obtained formula may have further undesired satisfying assignments.
To be sure that the formula is satisfied uniquely by the desired assignment, you should introduce all the possible clauses that agree with it. This would produce formulas with too many clauses, which will probably be easy to solve and therefore not representative of the worst case behaviour of the solver. It is not obvious to me how we can efficiently force uniqueness while keeping the number of clauses reasonable.

  How can we generate uniquely satisfiable formulas with a reasonable number of clauses? By reasonable I mean far from the maximum $2^k \cdot {n \choose k}$.


texts: Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$

texts:
In "The Similarity Metric" Li, et al give the first definition of the normalized information distance as

$\displaystyle d(x,y) = \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \}}{\max \left \{ K(x), K(y) \right \}}$

where $x^*$ is the shortest program outputting $x$. I.e. $K(x) = |x^*|$. In most future papers they drop the star notation, turning the metric into

$\displaystyle d(x,y) = \frac{\max \left \{ K(x|y), K(y|x) \right \}}{\max \left \{ K(x), K(y) \right \}}$

I'm unclear on the relationship between the two quantities $K(x|y^*)$ and $K(x|y)$. It seems to me that the former is quite different from the latter, as the latter is providing both $y$ and $K(y)$ as an input to the program computing $x$. However, I can't find any justification as to how these metrics are the same (up to whatever sufficiently sloppy additive precision you like). Could someone point me to an explanation or a reference that clarifies this?


texts: Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

texts:
It seems to be known that to find an answer to a query $Q$ over a relational database $D$, one needs time $|D|^{|Q|}$, and one cannot get rid of the exponent $|Q|$.
As $D$ can be very large, we wonder why databases work at all in practice.
Is it just a matter of the usual queries not being large at all in the real-world applications? (Then it is interesting to know what the usual size of the queries posed to relational database systems is, and what the "maximal" size of the queries that are expected to be effectively answerable by a DB system in practice is.)
Notes on the exponent $|Q|$ not `removable'
To show that the exponent $|Q|$ is not removable, one can use a query asking whether there exists a clique of size $n$ in the graph given by the database. To check whether a graph has an $n$-clique is an NP-complete problem. Moreover, it is not fixed-parameter tractable, with parameter $n$. Details can be found in, e.g.,
Libkin, L.: Elements Of Finite Model Theory. Springer (2004)
or
Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J.
Comput. Syst. Sci. 58(3), 407–427 (1999)


texts: Policy Adjustment in Markov Decision Process

texts:
I was using MDP on my work to make optimal decision. I used discrete time, finite state MDP. I assumed that I will have an initial parameters, like the Reward/Cost, state transition probabilities and actions, to make the optimal decisions. Then, I used the value iteration algorithm to find the expected values for each possible state under the given MDP configuration.

Here is my problem. As I understand, after getting the optimal policy from Value Iteration Algorithm, the policy will stay valid under the initial MDP configuration. However, I believe the policy must be adjusted whenever there is change on MDP configurations (specifically change in Reward/Cost and Transition probabilities). So, I am looking for the best solution that adjust the policy instead of recalculating the policy again using VIA under the new MDP configuration.

My work assumes the states and action doesn't change, only the cost and transition probability changes. Please suggest me any solution or reference to similar works. Thanks.


texts: Grammars whose LR automata have singleton item sets?

texts:
The states in LR parsers correspond to sets of items (ie, sets of productions from the original grammar, with a "dot" marking how far into the rule the parser has gotten). In general, states correspond to multiple items, since in general it is not possible to predict which rule will be used for reduction.

What is known about the case when it is? That is, what is known about grammars for which the corresponding LR(k) automata (both $k=0$ and $k>0$) have states with singleton item sets? Has this class been studied, and does it correspond to any well-known class of grammars? (Eg, does it correspond to LL(k), or operator precedence, or similar?)

I'm curious about this case since the singleton item restriction means that the size of the parse automaton will be bounded by the size of the grammar.


texts: Tight estimates on the Lovász and Multilinear extensions of a submodular function

texts:
I assume here some familiarity with the jargon used in submodular optimization (please let me know if something is unclear).

Let $f:2^V \to \mathbb{R}$ be monotone, normalized and submodular. For any $A \subset V, j \in V$, let $f_{A}(j)$ denote the marginal benefit of adding $j$ to $A$ i.e., $f_{A}(j) \stackrel{\text{def}}{=} f(A \cup \{j\})-f(A)$.

We define the curvature $c$ of $f$ as $$c \stackrel{\text{def}}{=}\max_{j \in V} \frac{f(\{j\})-f_{V-j}(j)}{f(\{j\})} = 1-\min_{j \in V} \frac{f_{V-j}(j)}{f(\{j\})}$$

This is a measure of how far $f$ is from being modular. It's easy to see that $c=0$ if and only if $f$ is modular. Moreover, always we have $c \in [0,1]$. It's also easy to see that given $A,B \subset V$, we have that $(1-c)f_{A}(j) \leq f_B(j)$. (These facts are supposed to be helpful for the problem I'm about to describe).

Let $f_L, f_M:[0,1]^V \to \mathbb{R}$ respectively denote the Lovász and Multilinear extensions of $f$. It's well-known that $f_L \leq f_M$. The problem is to show $f_M \leq \frac{1}{1-c}f_L$. This yields a tight estimate $f_L \leq f_M \leq \frac{1}{1-c}f_L$.

  Does anyone know of a reference where this is proven? Or can anyone provide a proof (or just an outline)?

Thanks!


texts:
Monadic First Order Logic, also known as the Monadic Class of the Decision Problem, is where all predicates take one argument. It was shown to be decidable by Ackermann, and is NEXPTIME-complete.

However, problems like SAT and SMT have fast algorithms for solving them, despite the theoretical bounds.

I'm wondering, is there research analogous to SAT/SMT for monadic first order logic? What is the "state of the art" in this case, and are there algorithms which are efficient in practice, despite hitting the theoretical limits in the worst case?


texts:
Suppose we are given a large bipartite graph with weighted edges, and a small parameter $d$ (e.g. $d$ is 3 or 4).
What is known about the run-time to find the minimum weight complete bipartite subgraph $K_{d,d}$?

I'm looking for an algorithm that beats the trivial $n^{O(d)}$ algorithm. I would like $o(n^d)$ or a fixed parameter version: $O(f(d)\cdot n^c)$ for some computable function $f$ and constant $c$.

I expect that the former should be possible, since a related question of finding $3r$-cliques in $O(n^{\omega r})$ time is possible using matrix multiplication. See A new algorithm for optimal constraint satisfaction
and its implications by Ryan Williams.


texts:
In Purely Functional Worst Case Constant Time Catenable Sorted Lists, Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data structure is somewhat complicated.

Is there a simpler balanced search tree with O(1) concatenate, functional or not?


texts: What are the practical issues with intersection and union types?

texts:
I'm designing a simple statically typed functional programming language as a learning experience.

It appears that the type system I have implemented so far could (with a little extra work) incorporate intersection and union types, e.g. you could have:

<Union String Integer>
<Union Integer Foo>
The intersection of the two types above would be a plain Integer
The union of the two types would be <Union String Integer Foo>

The fact that this is possible, of course, doesn't necessary mean it is a good design idea. In particular, I'm a somewhat concerned about the implementation difficulties of keeping the types disjoint and/or handling overlaps.

What are the pros/cons of incorporating such features in the type system?


texts: What languages have been successfully cryptographically trapdoored?

texts:
An observation associated with asymmetric cryptography is that some functions are (believed to be) easy to perform in one direction but difficult to invert. Furthermore, if there exists some 'trapdoor' information that allows the inverse operation to be computed quickly then the problem becomes a candidate for a public key cryptography scheme.

Classic trapdoor problems, made famous by RSA, include the factoring problem and the discrete log problem. Around the same time that RSA was published, Rabin invented a public key cryptosystem grounded on finding discrete square roots (this was later proved to be at least as difficult as factoring).

Other candidates have cropped up over the years. KNAPSACK (soon after RSA), Elliptic Curve "Logarithms" with specific parameters, and Lattice Shortest Basis Problems are examples of problems whose trapdoor problems used in other published schemes. It is also easy to see that such problems must reside somewhere in NP.

This exhausts my knowledge of trapdoor functions. It also seems to exhaust the list on Wikipedia as well.

I am hoping that we can get a community wiki list of languages that admit trapdoors and relevant literature. The list will be useful. Evolving demands of cryptography also change which trapdoor functions can be the basis of cryptosystems. The explosion of storage on computers makes schemes with large keysizes possible. The perpetual-looming spectre of Quantum Computing invalidates schemes that can be broken with an oracle for finding hidden abelian subgroups. Gentry's Fully Homomorphic Cryptosystem works only because we've discovered trapdoor functions that respect homomorphisms.

I am especially interested in problems that are not NP-Complete.


texts: Ordering sequences containing bitvectors for size-change termination

texts:
I'm working with the size-change termination principle to show program termination. In the system I work with, there is a so-called bit-vector ordering that goes as follows:

Given two sequences of arguments $s_1,s_2$.

Filter the bitvector arguments (long/int/short/byte)
Divide each sequence of arguments $s$ according to length (so one group is int, other short and so on). Denote the arguments of type $t$ in sequence $s$ as $s.t$.
If $s.t$ is defined for $s_1,s_2$, compare $s_1.t$ with $s_2.t$ lexicographically.

We define $s_1 < s_2$ when there exists a type $t$ such that $s_1.t < s_2.t$.

I have confirmed that this behaviour is wrong. Indeed, if one has two sequences $s_1,s_2$ that contain ints and shorts where $s_1.int < s_2.int$ and $s_2.short < s_1.short$ we would deduce that $s_1 < s_2$ and $s_2 < s_1$.

What is the standard orders for lists of bitvectors while using the size-change termination principle?


texts: Is there a notion of Probably Approximately Correctness in Unsupervised Learning?

texts:
I've been learning a little bit about computational learning theory, but most of what I've seen so far is related to supervised learning. Perhaps dimensionality reduction will be touched on, but not very in depth.

So I'm wondering - is there a formal notion of "generalization" in unsupervised learning that is analogous to the PAC model for supervised learning? I'm actually curious how we can get a sense of how "good" a particular unsupervised technique is without the notion of a loss function and labels.


texts: For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

texts:
Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and $b$ with some modulo conditions, e.g., $R(a,b)$ if and only if ($a<2b+1$ and $a\equiv 2 \bmod 6$) OR ($a-b=2$ and $a\equiv 2 \bmod 6$) OR ($2a-3b>5$ and $2a+b\equiv 3 \bmod 6$).

Is there some similar characterization known when the language can contain only some fixed, bounded number of non-zero characters?

For example, for which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

Related: I've discovered that this topic has been studied a lot for primitive words, see Kaszonyi-Katsura: Some new results on the context-freeness of languages.


texts: What will go wrong if a recursive record type has a negative eta rule?

texts:
In the context of Agda like dependent type theory:

This short paper https://jesper.sikanda.be/files/vectors-are-records-too.pdf says some inductive type can be seen as records, for example Vector of fixed-length list can be seen as inductively-defined family of non-recursive types.

But they argue that for example natural number type should not have a eta rule because it is a recursive type (the original paper says N = Unit \/ N is non-terminating.)

So what will go wrong if we have this type:

data out where
  cons : out => out

in : out => out
in (cons a) = a

and give it a negative eta-rule:

(a: out)  then  a = cons (in a) judgementally

Can it proof False? Or just this is a bad idea....?

edit: It seems Agda has eta-rule for recursive records? but not for the one previously defined, see this issue https://github.com/agda/agda/issues/402 . but the previously defined one is ruled out I think by implementation issues, not theoretical one?


texts: Correct algorithms with sequentially inconsistent executions

texts:
as far as I understood one wants that an algorithm produces only results that can be also achieved by a sequentially consistent execution.

My question is whether this is true or whether there are correct algorithms that have results that can be only achieved by sequentially inconsistent executions?


texts: Quantum algorithms based on transforms other than Fourier transforms

texts:
In Quantum Computation and Quantum Information by Nielsen and Chuang they say that many of the algorithms based on quantum Fourier transforms rely on the Coset Invariance property of Fourier transforms and suggests that invariance properties of other transforms might yield new algorithms.

Has there been any fruitful research on other transforms?


texts: Finding containing sets, within sets of sets

texts:
Let $s = \{\sigma_1, \sigma_2 \ldots \sigma_n\}$, where $\sigma_i \in \Sigma$, denote a set of alphabet characters.
And $s \in S$ where $S$ denotes a set of sets.
Given a new set $s' = \{\sigma'_1, \sigma'_2, \ldots \sigma'_n \}$ is there an efficient algorithm for getting all sets, $s'' \in S$, where $s' \subset s''$
In other words, given a set of sets, is there a way of getting the subset of sets the contain specific set of attributes?
I would be willing to build data structures with search and update complexities in the $O(\log (n))$ range, $n$ being the number of sets - also I would like the alphabet $\Sigma$ to be infinite.
The alphabet size is not known in advance.
This seems like a pretty simple problem, I am however not able to get my head around it.
Example:
Given the dataset $S$:

$s_1$: {a,b,c,d}
$s_2$: {a,c,d}
$s_3$: {b,c,d,f}
$s_4$: {a,b,d,h}

and the query string $s'$ = {a,b}
I would like the result :

$s_1$: {a,b,c,d}
$s_4$: {a,b,d,h}

The only sets containing the two elements.


texts: Rate of convergence for the Perron–Frobenius theorem

texts:
The Perron–Frobenius Theorem states the following.

Let $A = (a_{ij})$ be an $n \times n$ irreducible, non-negative matrix ($a_{ij} \geq 0, \forall i,j: 1\leq i,j \leq n$). Then the following statements are true.

$A$ has a real eigenvalue $c \geq 0$ such that $c > |c'|$ for all other eigenvalues $c'$.
There is an eigenvector $v$ with non-negative real components corresponding to the largest
eigenvalue $c: Av = cv, v_i \ge 0, 1 \leq i \leq n$, and $v$ is unique up to multiplication by a constant.
If the largest eigenvalue $c$ is equal to $1$, then for any starting vector $x^{\langle 0\rangle} \neq 0$ with non-negative components, the sequence of vectors $A^k x^{\langle 0\rangle}$ converge to a vector in the direction of $v$ as $k \rightarrow \infty$.

But the theorem does not say how fast the sequence of vectors $A^k x^{\langle 0\rangle}$ will converge. Are there any known results on the rate of convergence? What are some good, polynomial-time algorithms to compute this limiting vector?


texts:
In my thesis on object recognition based on spatial relations and visual features, I need to convert the images to graphs to be able to work on their spatial relations. Could you introduce some methods you're familiar with along with their advantages and disadvantages? Google yielded no relevant results.

I haven't done much research yet, except for reading a few articles to get familiar with different approaches and methods and have a clear view of what I want to do. Going through this article, a method is proposed for converting an image to graph, which is called irregular pyramids. So all I want to know is whether there are other methods for such propose?


texts: Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't?

texts:
The popular DEFLATE algorithm uses Huffman coding on top of Lempel-Ziv.

In general, if we have a random source of data (= 1 bit entropy/bit), no encoding, including Huffman, is likely to compress it on average.  If Lempel-Ziv were "perfect" (which it approaches for most classes of sources, as the length goes to infinity), post encoding with Huffman wouldn't help.  Of course, Lempel-Ziv isn't perfect, at least with finite length, and so some redundancy remains.

It is this remaining redundancy which the Huffman coding partially eliminates and thereby improves compression.

My question is: Why is this remaining redundancy successfully eliminated by Huffman coding and not LZ? What properties of Huffman versus LZ make this happen? Would simply running LZ again (that is, encoding the LZ compressed data with LZ a second time) accomplish something similar? If not, why not? Likewise, would first compressing with Huffman and then afterwards with LZ work, and if not, why?

UPDATE:
It is clear that even after LZ, some redundancy will remain.  Several people have made that point.  What isn't clear is: Why is that remaining redundancy better addressed by Huffman than LZ? What's unique about it in contrast with the original source redundancy, where LZ works better than Huffman?


texts: Computational complexity in linear solvers

texts:
I have recently been trying out methods of coding for solving systems of linear equations on Python. Of course, I first used the inbuilt function $\mathit{inv}$ under certain if-conditions to obtain the solution, if unique. I also tried the LU decomposition method, and the Gaussian Elimination Method, neither of which proved very efficient either. I have not tried the QR method, but found an article online that suggested that it would be less efficient than the LU one, which makes it uninteresting to me.

I am trying to find resources about the most efficient complexity achieved on this problem, hopefully of O($n^{r}$), where $r < 3$. In fact, I would like a complete (or even less-than-complete) list of all improvements made in this area, and the most efficient solution currently available. Links to the code itself will be helpful, but are not necessary. I am more interested in the technique used, rather than the program itself, so links to the papers that illustrate the method and prove complexity of said method are what I am looking for here.


texts:
What is the complexity of the following problem ($\in$ P? NP-hard?):

Input: a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$.

Question: Let $G=(V,E\cup E')$ denote the graph formed by adding to $D$ the edges from $E'$. Is there a simple path from $s$ to $t$ in $G$ that uses at least one backward edge?

Note: 0) A simple path is a path in which no vertex is repeated, A backward edge is an edge that contradicts the partial order implied by the DAG.
1) the problem is easy if we request the simple path to use exactly
one backward edge (or a constant number) by trivial reduction to the disjoint path problem, which admits a simple PTime solution in DAGs
(Perl and Shiloach, JACM'78)
2) the disjoint path problem is NP-complete in general graphs (Fortune et al., TCS'80).


texts:
Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete.

My questions are the following:

$(1)$ Are there natural good examples of coding theory problems that lie in different levels of the polynomial hierarchy above NP and are complete for those levels?

$(2)$ Are there natural good examples of coding theory problems that are PSPACE complete? (Note that a coding theory approach is used to show IP=PSPACE in http://www.math.ias.edu/~ormeir/papers/ip_pspace.pdf)


texts: What is the difference between propositions and judgments?

texts: I get confused by the subtle difference between propositions and judgments when exposed to intuitionistic type theory. Can any one explain to me what is the point to distinguish them and what distinguishes them? Especially in view of the Curry-Howard Isomorphsim.


texts: Linear time algorithm for computing the labels of leaves in a recursively defined tree

texts:
The original copy of the question on MSE.

Let $S=(s_0, ..., s_{N-1})$ be a sequence of $N=2^p$ numbers. We consider a labelled binary tree of height $p$ as follows:

The root has label $S$,
for each node $x$ in the tree, and label $l$,

$x.left.l = x.l_0 + x.l_1$,
$x.right.l = x.l_0 - x.l_1$,

where $l_0$ and $l_1$ are the first and second half of the sequence $l$.

For example, if $S=(1,2,3,4,5,6,7,8)$ we have the tree:

                 1, 2, 3, 4, 5, 6, 7, 8
                /                      \
    6, 8, 10, 12                       -4, -4, -4, -4
   /            \                      /             \
 16, 20       -4, -4                -8, -8,         0, 0
 /    \       /    \                /     \        /    \
36    -4    -8      0             -16      0      0      0

where the second level is obtain by

$(6 = 1+5, 8 = 2+6, 10 = 3+7, 12 = 4+8)$,
$(-4 = 1-5, -4 = 2-6, -4 = 3-7, -4 = 4-7)$.

The problem is to compute the labels for the leaves.
In the example, the labels for the leaves are: $36, -4, -8, 0, -16, 0, 0, 0$.

If I compute the tree recursively, the computational complexity will be $O(N \log N)$. That is a little slow for the purpose of the algorithm. Is it possible to calculate the labels for the leaves in linear time?


texts:
Cantor's theorem states that

  For any set A, the set of all subsets of A has a strictly greater cardinality than A itself.

Is it possible to encode something like this using only types / propositions without referring to ZFC sets? Code or pseudocode for encoding this proposition in a dependently typed language would be appreciated.