texts: Finding the Length of the shortest Accepting path of a NDTM

texts:
Let $M$ be a NDTM (non deterministic Turing machine) which decides a certain NP-complete language, say SAT.

$M$ computes any instance $I$ of the NP-complete problem in at most $p(n)$ non deterministic steps ($p$ in a polynomial function, $n$ is the input size). The length of a computation path can be measured as the "rank" of the non deterministic step where $M$ halts. Let call $rank_M(I)$  the rank of the shortest accepting path ($rank_M(I)$ is $p(n)+1$ if $M$ rejects $I$).

Is this problem NP-complete : Given a boolean expression $I$, is it true that $rank_M(I)=k$ ? ($k$ is polynomially bounded in $n$)

Edit --- $rank_M(I)$ has been modified : it defines now the shortest accepting path (instead of just the rank of the step where $M$ halts).

Thank you.


texts:
I've got a reduction of the following partition problem to a certain scheduling problem:

Input: A list $a_1\leqslant\cdots\leqslant a_n$ of positive integers in non-decreasing order.

Question: Does there exist a vector $(x_1,\ldots,x_n)\in\{-1,1\}^n$ such that

\[\sum_{i=1}^na_ix_i=0\qquad\text{and}\]
\[\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\}\]

Without the second condition it's just PARTITION, hence NP-hard. But the second condition seems to provide a lot of additional information. I'm wondering if there is an efficient way of deciding this variant. Or is it still hard?


texts: Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$

texts:
Does $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$  has any separation of classes or consequences?

  My main question is can use this to show that $P \neq NP$ or some thing useful about $P \neq NP$ .


texts: On the impossibility of representing/approximating subadditive function using additive functions

texts:
I am trying to understand whether a monotone and subadditive function $f(S), S \subseteq 2^{[n]}$ and $ f : 2^{[n]} \rightarrow R_{\geq0}$ can be represented using an additive function $\hat{f}(S) = \sum_{i \in S} w_i$. In other words, is it possible to approximate $f$ for all $S$ by finding the value of the weights $w_i$?

The best I can do is the following : $\hat{f} = \sum_{i \in S} \frac{f({i})}{n}$ which can be shown to be $\frac{f(S)}{n} \leq \hat{f}(S) \leq f(S)$ i.e an $n-$approximation. Note that I just need to argue about existence of such a function and not the construction. There are known results on how this is impossible to do in subexponential queries using an oracle that gives you access to $f$ and queries are of the form $f(S)$ for any $S$. I am looking for lower bounds assuming infinite computational power. Is it possible to show that this is tight and we cannot hope to have a better function?

My intuition is that a subadditive function is still pretty linear and a bad instance would be when the values of all sets of fixed size (say $k$) vary wildly rather than being a constant/additive/linearly.

Any reference about representing function using additive linear functions will be very helpful!


texts: Complexity of Encoding a Matroid Flow Problem in a Matrix

texts:
Context:
Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$.
We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct vertices in $S$ which can be connected to distinct vertices of $I$ via a collection of $r$ vertex-disjoint paths in $G$. In other words, there is a flow of size $r$ from $S$ to $I$.
It turns out that a graph together with independent subsets of vertices defined in this way forms a structure known as a gammoid, which is itself a special case of a structure known as a matroid.
Many algorithms that work with matroids take as input a linear representation of the matroid. In the context of this problem, this representation is a matrix $M$ whose column vectors $\vec{v}_u$ are indexed by vertices $u$ in $G$, with the property that a subset $I$ of vertices is independent if and only if the corresponding list of column vectors $\{\vec{v}_u\}_{u\in I}$ is linearly independent.
Several sources (see here and here for example) observe that is well-known that given $G$, $S$, and $T$, one can build a matrix representation of the associated gammoid in randomized polynomial time. However, I have not been able to find any reference to the precise running time of this algorithm.
This motivates the following question.
Question: Given a graph $G$ with source set $S$ and target set $T$, how quickly can we build a matrix representation of the associated gammoid? Randomness is allowed.
I'm mainly interested in the dependence on the the number of vertices $n$ in the graph, but it would be good to know the dependence on the number of source vertices $|S| = k$ as well.


texts:
I was wondering if this problem has a name and/or it has been already studied.

  Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$ :
  Does there exist a subset $S\subseteq V$ with $|S| \geqslant k$, such that
  $$ \forall v \in V \,:\, \biggl|\;\Bigr(N(v) \cup \{v\}\Bigr) \cap S\;\biggr| \;\leqslant\; f(v) \;?$$

Question.
Is this problem NP-complete? Are there good approximation algorithms?


texts: Natural problem in S2P not known to be in any smaller class

texts: Is there a decision problem in $\textsf{S}_2\textsf{P}$ that (presumably) requires the full power of $\textsf{S}_2\textsf{P}$-computations? Specifically, is there a language in $\textsf{S}_2\textsf{P}$ that doesn't obviously belong to any 'natural' smaller class? The two 'natural' classes that I have in mind are $\textsf{P}^{\textsf{NP}}$ and $\textsf{BPP}$.


texts:
Discussion:

I've been spending some personal time lately learning various things in communication complexity. For instance, I've re-familiarized myself with the relevant chapter in Arora/Barak, started reading some papers, and ordered the book by Kushilevitz/Nisan. Intuitively, I want to contrast communication complexity with computational complexity. And in particular, I'm struck by the fact that computational complexity has developed into a rich theory of placing computational problems into complexity classes, some of which can be in turn (from one perspective, at least) envisioned in terms of complete problems for each given class. For instance, when explaining $NP$ to someone for the first time, it's hard to avoid comparisons to SAT or some other NP-complete problem.

By comparison, I've never heard anything of an analogous concept for communication complexity classes. There are many examples that I'm aware of, of problems "complete for a theorem." For instance, as a general framework, the authors might describe a given communication problem $P$ and then prove that a related theorem $T$ holds $iff$ the communication problem can be solved in $X$ or less bits (for some $X$ that depends on the specific theorem/problem pair in question). The terminology used then in literature is that $P$ is "complete" for $T$.

Further, there is a tantalizing line in the Arora/Barak communication complexity chapter draft (that seems to have been removed/tweaked in the final printing) that states "In general, one can consider communication protocols analogous to $NP$, $coNP$, $PH$ etc." However, I notice two important omissions:

 The "analogous" concept appears to be a manner of computing the communication complexity of solving a given protocol with access to different types of resources, but stops just short of defining proper communication complexity classes...
 Most of communication complexity seems to be relatively "low-level," in the sense that the overwhelming majority of results/theorems/etc. revolve around small-ish, specific, polynomial-sized values. This somewhat begs the question of why, say, $NEXP$ is interesting for computation but the analogous concept appears to be less interesting for communication. (Of course, I could just be at fault for simply being unaware of "higher-level" communication complexity concepts.)

Question(s):

Is there an analogous concept to computational complexity classes for communication complexity?

And:

If so, how does it compare to the "standard" notion of complexity classes? (e.g. are there natural limitations to "communication complexity classes" that cause them to inherently fall short of the full range of computational complexity classes?) If not, what's the "big picture" reason that classes are an interesting formalism for computational complexity but not for communication complexity?


texts: Matching of two weighted graphs allowing one-to-many mapping

texts:
I am looking for a heuristic for a graph matching problem as follows.

Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than that of $A$.

Each node and edge in two graphs has weight. The task is to match graph $A$ to graph $B$, i.e., find a set of nodes and links in $B$ to map each node and link of $A$, such as the host node/link in $B$ has larger weight than the corresponding node/link of $A$.

The following figure illustrates two possible cases (or solution) of mapping (matching):

Case 1: One-to-one mapping: Each node or edge of $A$ needs only one node or link of $B$ to map. Here the nodes $a_1, a_2, a_3$ are mapped on to $b_1, b_2, b_3$, and the edges $a_1a_2, a_2a_3$ are mapped onto $b_1b_2$ and $b_2b_3$ respectively.

Constraints are satisfied: For nodes: $b_1 > a_1$, $b_2 > a_2$, $b_3 > a_3$. For edges: $b_1b_2 > a_1a_2$ and $b_2b_3 > a_2a_3$.

Case 2: One-to-many mapping: One needs more than 1 node/edge of $B$ to host a node/edge of $A$. In the example, $a_1$ is mapped on to $b_1$ and $b_4$, $a_2, a_3$ are mapped onto $b_2, b_3$. For the edges: $a_1a_2$ is mapped onto $b_1b_2$ and $b_4b_2$, and $a_2a_3$ is mapped onto $b_2b_3$.

Constraints are satisfied: For nodes: $b_1 + b_4 = 11 > a_1$, $b_2 > a_2$, $b_3 > a_3$. For edges: $b_1b_2 + b_4b_2 = 8 > a_1a_2$ and $b_2b_3 > a_2a_3$.

Heuristics for Case 1 have been well studied, e.g., using eigendecomposition to solve the Weighted Graph Matching Problem (WGMP). Nevertheless, I could not find an appropriate algorithm to find a solution as in Case 2. Any suggestions?


texts:
I'm currently trying to find a reduction to this problem:
Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as vertices) which fulfill these conditions?:

Each pair of triangles on the result set can only share 0 or 1 vertex.
If a pair of triangles share 1 vertex they cannot overlap and if they do not share a vertex, they can overlap.

I have the intuition that answering the above question is NP complete, I already tried some reductions with no luck
I tried reducing some these problems: https://en.wikipedia.org/wiki/List_of_NP-complete_problems, like 3-SAT, 3 dimensional matching, just to name 2.

Have someone encounter a similar problem which is NP-complete?
Can it be in another complexity class?

Any help or view on
the problem will be much appreciated.
thanks.


texts: An exponentially-ambiguous weighted automaton without an equivalent polynomially-ambiguous automaton

texts:
A min-plus weighted automaton (WFA) is a nondeterministic automaton with a weight function that assigns each transition a weight in $\mathbb{N}$. The weights along a run are summed, and the value of a word is the value of the minimal accepting run of the automaton on it.

In a beautiful paper, Kirsten and Lombardy show that deciding unambiguity and sequentiality (i.e. determinizability) for WFAs is decidable for polynomially ambiguous WFA (the general case has been open for years).

Working on related problems, I am trying to tackle the following:

  Is there an example of an exponentially-ambiguous WFA for which there is no equivalent polynomially ambiguous WFA?

Note that by "equivalent" we mean that they represent the same (perhaps partial) function $f:\Sigma^*\to \mathbb{N}$.

Some side-notes:

It is known that exponentially-ambiguous NFAs are exponentially more succinct than polynomially-ambiguous NFAs. But this is non-trivial. This suggests that in the WFA case this would also be not easy.
It is well known that WFAs are, in general, non-determinizable. For example, it is easy to construct a WFA for the function that returns the minimal number of occurrences of a certain letter in a word, but this cannot be done with a deterministic WFA. This suggests that the hierarchy between different classes of ambiguity might also be proper (hence my question).
Exponentially ambiguous automata have a very simple syntactic structure: an automaton is exponentially ambiguous iff there is a state $q$ and a word $w$ such that $q$ is reachable from itself using $w$ in at least two different paths.


texts: Complexity of type inference in the simply typed lambda calculus

texts:
A similar question was answered here:
Is simply typed lambda calculus equivalent to primitive recursive functions
What I conclude from the answers is that the complexity is that of the extended polynomials, but this refers to what can be computed in the STLC, not of type checking expressions in the STLC.
This link provides an algorithm for type-checking. It is claimed that
type checking is linear time in an answer to this question: Complexity of type-checking in relation to complexity of normalization
Also, a survey of algorithms that do type inference for STLC, using unification occurs here, but no complexity result is given.


texts: Space-time tradeoff and the best algorithm

texts:
Consider some language $L$ such that:

$L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$

and so that

$L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$

In other words, the fastest machine $M$ computes $L$ in time $O(f(n))$ and the most space efficient machine $M'$ computes $L$ while using space $O(g(n))$.

What can be said about the space efficiency of M or the time efficiency of M'? Or more precisely, if $\mathbb{M}_T$ is the set of all machines that compute $L$ in $O(f(n))$ then what can we say about the most space efficient machine in $\mathbb{M}_T$? What about the same thing for the obvious space version: $\mathbb{M}_S$.

Alternatively, can $f(n)$ and $g(n)$ be used to define some good space-time tradeoffs? Under what conditions is $TS \in o(f(n)g(n))$ or more generally for some space-time tradeoff $h(T,S)$ under what conditions is $h(T,S) \in h(o(f(n)),o(g(n)))$.


texts: Is there a publicly available testbed of perfect graphs? Ideally, the number of vertices should be 100 or more.


texts: Riemann Hypothesis and Complexity Theory

texts: It is known that "Assuming the generalized Riemann hypothesis (GRH) if VP = VNP then PH collapses to second level". Why would one think of a relation between VP,VNP and the Riemann hypothesis. Where does a statement about the zeros of the Riemann zeta function appear in a statement about complexity classes ? I have not read the original result. It would be nice if anyone could provide some intuition.


texts: Complexity Class Equalities on the Edge of Inconsistency

texts:
What are some of the most extreme potential equalities between computational complexity classes (especially if there is a barrier to refuting them)?  These may give us an opportunity to prove better bounds, or provide a clearer understanding of the fundamental obstacles in complexity theory.

Here is my list (at most one and probably zero equalities actually hold):
* uniform TC0 = NP
* NC1 = CH (defined using logtime uniformity; implies NC1 = LOGSPACE = PP)
* P = PSPACE
* ZPP = EXP = ⊕EXP
* BPP = NEXP = EXPNP

It remains open whether P=PSPACE can be combined with P having non-uniform TC0-circuits, which would allow P-uniform TC0-circuits for PSPACE, and analogously for ZPP/EXP and BPP/NEXP.  It is also open whether (logtime) uniform TC0 with an additional random input can simulate EXP (with zero error and unlikely failure) or NEXP (with bounded error).  TC0 < PP was only proved for (logtime) uniform TC0 without randomness.  Also, if TC0 is ruled out, we can fallback to NC1 (with the same uniformity conditions).

More items:
* Uniform AC0[6]=PH has not yet been ruled out, but AC0[6] is arguably not a natural complexity class.
* PRP = NEXP
* PNP = ⊕P = PEXP (though this prevents PNP from being 'feasible')

Quasilinear Time

In the above, polynomial transformations of input size are immaterial, but the sharpened versions below care about the exact (up to a constant factor) size.

Sharpened version of P=PSPACE: Every function in nondeterministic linear space with linear output size can be computed in O(n*log n) time and O(n) space using a Turing machine with a single tape and a stack.  We can also ask for the machine to be reversible, and also oblivious with LOGSPACE computable movement.

Sharpened version of BPP=NEXP:  Every function (with linear output size) in ENP can be computed with linear size logarithmic depth bounded fan-in bounded fan-out uniform circuits, if O(n) random bits are appended to the input string, allowing 2-O(n) error probability.
Notes:
* This is arguably the most extreme equality that we cannot yet rule out.
* There are different notions of (essentially logtime) uniformity that allow quasilinear-time circuit construction, with one reasonable choice being a Time(O(log n * (log log n)O(1))) algorithm that given gate number (perhaps with gate ordering consistent with causality) gives the type of gate and the numbers where to send the output.
* One can also ask about zero error, 2-O(n) failure probability, and functions in E (but not simultaneously with BPP=NEXP).
* If linear size logarithmic depth circuits are finally ruled out, we can backtrack to logarithmic time on uniform linear size O(1)-depth recurrent circuits (even with reversibility, and bounded fan-in and fan-out).
* Also, uniform TC0 of size O(n1+ε) (with randomness as above; depth depends on ε) has not been ruled out.


texts: How hard is it to determine the chromatic number of a unit distance graph?

texts: For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?


texts: How to select good examples for inductive logic programming?

texts:
I encounter a question while reading Quinlan's 1990 paper "Learning Logical Definitions from Relations". He described that (section 5.2) for learning the recursive relations on lists, the following is "a simple set of examples that are somehow sufficient to discover the relations" and is not randomly generated.
Examples:

list: {<()>, <(a)>, <(b(a)d)>, <((a)d)>, <(d)>}

null: {<()>}

components: {<(a), a, ()>, <(b(a)b), b, ((a)d)>, <((a)d), ((a)), (d)>, <(d), d, ()>, <(e.f), e, f>}
with negative tuples provided by closed-world assumption.

The induced theories are

list(A) <- components(A, B, C), list(C)
list(A) <- null(A)

I don't understand why the provided examples serves as simple and sufficient. Besides, I wonder is there any general principles for selecting good examples in ILP?
I'm not from this area hence I'm not sure if partial answers have been provided in any other related literature.


texts: What is a good Category Theory-Domain Theory dictionary?

texts:
When dealing with the domain theoretic categories (say CPO and $\omega$CPO), I frequently wish for a dictionary for the language of category theory in domain theory.

That is, given a concept, say monic arrow, I could look it up in the dictionary and see what are the known characterisations of it in the different domain categories.

I realise this wish is too much to hope for, but is there any text or resource approximating it?


texts:
I use the following Lemma and I wonder whether it is known in literature. If you look at the proof it feels like it should be known from combinatorics or extremal graph theory.

Lemma. Let $A$ be an $n$-element set and let $A_1,\ldots, A_n\subseteq A$ be a collection of sets, each of size at least $d$ such that $A=\bigcup_{1\leq i\leq n}A_i$. Let $d\leq s\leq n$. Then there exists a set $S\subseteq A$ of size $s$ such that $|A_i\cap S|\geq \left\lfloor sd/n\right\rfloor$ for at least $n/2$ of the $A_i$.

Proof. We may assume without loss of generality that every set $A_i$ has
  exactly $d$ elements. For each $i$, the number of subsets of $A$ of
  size $s$ including exactly $k$ elements of $A_i$ is
  $\binom{n-d}{s-k}\binom{d}{k}$ (choose $k$ elements of $A_i$ and
  $s-k$ elements of $A\setminus A_i$). Hence the number of subsets of
  $A$ of size $s$ including at least $k$ elements from $A_i$ is
  $\sum_{k\leq \ell}\binom{n-d}{s-\ell}\binom{d}{\ell}$.

For $k\leq d$ consider the bipartite graphs $G_k$, where one part
  consists of the $s$-element subsets of $A$ and the other part
  consists of the sets $A_i$. We introduce an edge between $(B, A_i)$
  if and only if $|B\cap A_i|\geq k$. The degree of $B$ in $G_k$
  corresponds to the number of $A_i$ that $B$ shares at least $k$
  elements with. As observed above, every $A_i$ has degree
  $\sum_{k\leq
    \ell}\binom{n-d}{s-\ell}\binom{d}{\ell}$. Hence $|E(G_k)|=n\cdot
  \sum_{k\leq \ell}\binom{n-d}{s-\ell}\binom{d}{\ell}$.  The average
  degree of a vertex $B$ in $G_k$ is $\frac{n\cdot\sum_{k\leq \ell}
    \binom{n-d}{s-\ell}\binom{d}{\ell}}{\binom{n}{s}}$ and there must
  be one vertex $S$ with at least this degree.

Observe that $\frac{\binom{n-d}{s-k}\binom{d}{k}}{\binom{n}{s}}$ is
  the probability mass function of a hypergeometric distribution with
  mean $\frac{ds}{n}$. Hence for
  $k=\left\lfloor\frac{ds}{n}\right\rfloor$ the above sum is greater
  than $1/2$ and hence $d(S)\geq n/2$ for this $k$. We conclude that
  $|A_i\cap S|=k=\left\lfloor\frac{ds}{n}\right\rfloor$ for at least
  $n/2$ of the $A_i$. $\hspace{4.5cm}\square$


texts: What is the goal behind abstract interpretation in programming languages?

texts:
I am now trying to understand better what "abstract interpretation" in programming languages are. I found a good book chapter that explains the idea of extending the domain with a least fixed element, the four axioms that yield a fixed point for a continuous function, and so on. I understand these technical details (though I am not quite sure what is "abstract interpretation" exactly referring to in this whole scheme).

What I am not sure about is what motivates the use of abstract interpretation? Is it just identifying fixed points for computable functions? Is the main motivation coming from having recursion in most programming languages?

Would also be glad to get some high-level overview which does go technically deep enough for someone who has a degree in computer science. I find the Wikipedia page rather unsettling.


texts: Compactly representing the solution set of a SAT instance

texts:
This question has risen in my mind after reading András Salamon's and Colin McQuillan's contributions to my previous question Counting solutions of Monotone-2CNF formulas.

EDIT 30th Mar 2011
Added question n° 2.
EDIT 29th Oct 2010
Question rephrased after András proposal to formalize it through the notion of nice representation of a solution set (I've modified his notion a little bit).

Let $F$ be a generic CNF formula with $n$ variables. Let $S$ be its solution set. Clearly, $|S|$ may be exponential in $n$. Let $R$ be a representation of $S$. $R$ is said to be nice if and only if the following facts are all true:

$R$ has polynomial size in $n$.
$R$ allows to enumerate the solutions in $S$ with polynomial delay.
$R$ allows to determine $|S|$ in polynomial time (i.e. without enumerating all the solutions).

It would be great if it is possible, in polynomial time, to build such a $R$ for every formula.

  Questions:

  Did anyone ever prove that there exists a family of formulas for which such a nice representation can't exist?
  Did anyone study the relationship between the representation of $S$ and the symmetries exhibited by $F$? Intuitively, symmetries should help to compactly represent $S$ because they avoid the explicit representation of a solution subset $S' \subset S$ when $S'$ actually boils down to just one solution (i.e. from every $s_i \in S'$ you can recover every other $s_j \in S'$ by applying a proper symmetry, thus every $s_i \in S'$ is itself representative of the whole $S'$)


texts: Maximum flow using Ford-Fulkerson and DFS

texts:
This question is about the time complexity of the Ford-Fulkerson
maximum flow algorithm when using DFS to find augmenting paths.

There is a well-known example showing that using DFS one can need a
linear number of iterations in the maximum flow, see for instance the
Wikipedia page linked to above.

However, I'm not really convinced by this example: a standard DFS
implementation would not exhibit the behaviour of alternating between B and C as
first node of the path (using the vertex names from the Wikipedia page).

So, let us impose the very natural condition that whenever the DFS visits a node
$u$, it always examines the neighbors of $u$ in the same order.  Are there
still examples for which FF with DFS uses a large number of
iterations?

As a variant, suppose that we have the additional property that the
different orderings of neighbors are consistent with some arbitrary
but fixed global ordering of the vertices.  Does that make a
difference?

This seems to me like a pretty basic question; I apologize in advance
if the answer is well-known but I am not an expert on flows and some
googling did not turn up anything.

Edit:
The answer turns out to be yes, there are still examples.  See Figure 2 of this paper.  In these examples FF with DFS take an exponential (in the number of vertices) number of iterations.  It seems easy to prove that this is tight, i.e., that the number of iterations are always bounded by $2^{O(n)}$ (regardless of the values of the capacities).


texts: NP-hardness of minimizing sum of weighted product

texts:
Consider a total of $d$ items, $\{I_1,I_2,\cdots,I_d\}$, each having a weight $w_i$ (a positive integer), and a total of $m$ bins, $\{B_1,B_2,\cdots,B_m\}$. We would like to distribute the items into the bins such that:

(1) no bin is empty;

(2) $\sum_{B_i}(|Bi|\prod_{I_j \in B_i}w_j)$ is minimized.

where $|B_i|$ is the number of items in $B_i$. Is this an NP-hard problem? If yes, how to prove it?


texts: How fast can we solve a totally unimodular integer linear program?

texts:
(This is a follow-up to this question  and its answer.)
I have the following totally unimodular (TU) integer linear program (ILP). Here  $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive integers given as part of the input. A specified subset of the variables $x_{ij}$ is set to zero, and the rest can take positive integral values:

Minimize
$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$
Subject to:
$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$
$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

The coefficient matrix of the standard form is a $(2\ell+m)\times \ell m$ matrix with entries from ${-1,0,1}$.
My question is:

What are the best upper bounds known for the running time of polynomial-time algorithms that solve such an ILP? Could you point me to some references on this?

I did some searching, but at most places they stop with saying that a TU ILP can be solved in polynomial time using polynomial-time algorithms for LP. One thing that looked promising is a 1986 paper by Tardos [1] where she proves that such problems can be solved in time polynomial in the size of the coefficient matrix. As far as I could figure out from the paper, however, the running time of that algorithm depends in turn on the running time of a polynomial-time algorithm for solving LP.

Do we know of algorithms that solve this special case (of TU ILP) significantly faster than the general algorithms that solve the LP problem?

If not,

Which algorithm for LP would solve such an ILP the fastest (in an asymptotic sense)?

[1] A strongly polynomial algorithm to solve combinatorial linear programs, Eva Tardos, Operations Research 34(2), 1986


texts: Intersection of two deterministic parity automata

texts:
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the transition function $\delta_i : Q_i \times \Sigma \rightarrow Q_i$, the initial state $q_{0i}$ in $Q_i$, and the coloring function $c_i : Q_i \rightarrow \mathbb{N}$, with $i \in\{0,1\}$.

How is the intersection of two deterministic parity automata formally defined? In particular, how are the coloring functions combined?


texts: Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?

texts: Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient algorithm for calculating permanents of 0/1 matrices exactly. On the other hand, Valiant provided a polynomial time reduction from the permanent of an arbitrary matrix with integer entries to the permanent of a 0/1 matrix. Why could one not make use of this reduction, followed by an application of the JSV algorithm (which can efficiently approximate the permanents of matrices with nonnegative entries but cannot handle matrices with negative entries) to efficiently approximate the permanents of arbitrary integer matrices?


texts: Doubt in John Langford's "Tutorial on Practical Prediction Theory for Classiﬁcation" paper

texts:
I am reading John Langford's paper on practical prediction theory (link), and I have the following doubt with definition of Binomial Tail inversion.

The paper says that binomial tail inversion is the largest true error such that the probability of having k or more errors is at least $\delta$.

But the expression used in the paper reads "largest true error such that probability of having k or less errors is at least $\delta$"

Can anyone help?


texts: Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry?

texts: Are there any problems that are NP-complete when using Euclidean geometry but are well-defined and solvable in polynomial time for some non-euclidean geometry?


texts: Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1". The result of each operation is a set of updated cells (not just affected, it is important that value is changed from 0 to 1) in matrix C. Is there any research on this problem? Can we do the update (theoretically) faster than in a naive way? For example, are there estimations on possible speedup by a logarithmic factor? The problem looks slightly similar to incremental transitive closure or dynamic matrix inverse, but quite specific.


texts: Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

texts:
Context.

I am writing on topics such as the Gottesman-Knill theorem, using Pauli stabilizer groups, but in the case of d-dimensional qudits — where d may have more than one prime factor. (I emphasize this because the vast majority of literature on stabilizer formalism in "higher dimensions" involves the cases of d prime or d a prime power, and makes use of finite fields; I'm considering instead the cyclic groups ℤd .)

For any dimension, I characterize a (Pauli) stabilizer group as an abelian subgroup of the Pauli group, in which every operator has a +1 eigenspace.

I'm writing about a result which is well-known for d = 2 (and easily generalized to d prime):

  A stabilizer group stabilizes a unique pure state if and only if it is maximal

where by maximality, I mean that any extension either lies outside the Pauli group, or is non-abelian, or contains operators without +1 eigenvalues.
Proofs of such results for d prime usually rely on the fact that ℤd2n is a vector space (i.e. that ℤd is a field): this does not hold for d composite. There are two recourses: generalize the existing proofs in a way that is robust to the existence of zero divisiors (e.g. using tools such as the Smith normal form), or avoid number theory altogether and use ideas such as orthogonality relations of Pauli operators.

Problem.

I actually do have a concise proof of this result already, essentially using no more than orthogonality relations of Pauli operators. But I suspect that I've seen something like it before, and I would like to refer to the prior art if I can (not to mention see if there are better techniques than the one I used, which while not onerous felt less than perfect).

Certainly Knill's papers [quant-ph/9608048] and [quant-ph/9608049] consider similar subjects and use similar techniques; but I couldn't find the result I was looking for there, or in Gottesman's [quant-ph/9802007]. I'm hoping that someone can point me to where such a proof might have been published before.

Note — the result I'm considering is not one which relates the cardinality of the group to the dimension of the stabilized space (which is nice, but trivial both to prove and to find references to); I'm concerned specifically with showing that any stabilizer group which cannot be extended stabilizes a unique state, and vice versa.
A reference to a proof that any maximal stabilizer group has the same cardinality would be fine; but again, it must not rely on d being prime or ℤd2n being a vector space.


texts:
While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such problems have not been well studied in the motion planning area (imagine for example a chain of linked carriages or robots). The games are well known, however this is a short description of the related reconfiguration model:

SNAKE PROBLEM

Input: given a planar graph $G = (V,E)$, $l$ pebbles $p_1,...,p_l$ are placed on nodes $u_1,...,u_l$ that form a simple path. The pebbles represent the snake, and the first one $p_1$ is his head. The head can be moved from its current position to an adjacent free node, and the body follows it. Some nodes are marked with a dot; when the head reaches a node with a dot, the body will increase by $e$ pebbles in the following $e$ moves of the head. The dot on the node is deleted after the traversal of the snake.

Problem: We ask if the snake can be moved along the graph and reach a target configuration $T$ where the target configuration is the full description of the snake position, i.e. the position of the pebbles.

It is easy to prove that the SNAKE problem is NP-hard on planar graphs of max degree 3 even if no dots are used and also on SOLID grid graphs if we can use an arbitrary number of dots. Things get complicated on solid grid graphs without dots (it is related to another open problem).

  I would like to know if the problem has been studied under another name.
  and, in particular, if there is a proof that it is in NP ...

Edit: the problem turned out to be PSPACE-complete even on planar graphs and the result seems very interesting, so it remains to find out if it is a new problem
and if there are known results about it.

A simple example (pebbles are shown in green, the snake's head is P1).


texts: Isomorphism preserving transformation CNF to Graph?

texts:
In short we are interested in isomorphism preserving
transformation CNF to Graph.
Let $\phi_1,\phi_2$ be CNF formulas.
Define $\phi_1$ and $\phi_2$ to be isomorphic $\phi_1 \cong \phi_2$
if there exist permutation $\pi'$ of the clauses of $\phi_2$ and
permutation $\pi$ of the variables of $\phi_2$ such that
$\phi_1(x_i)=\pi'(\phi_2(\pi(x_i)))$.
XXX this isomorphism definition might be non-standard, please
fix it.

Main question:  Is there transformation $\Gamma(\phi)$ CNF to
polynomially sized Graph
such that $\phi_1 \cong \phi_2 \iff \Gamma(\phi_1) \cong \Gamma(\phi_2)$

Several papers about satisfiability define the "constraint graph"
of CNF, but it doesn't appear to preserve isomorphism.
Solution might exist when transforming CNF satisfiability as a
problem on a graph.
Here is attempt at solution.
Given CNF formula with $n$ variables $v_i$ and $m$ clauses
$c_i$, construct graph $\Gamma(\phi)$ with vertices $c_i \cup v_i \cup \lnot v_i$.
Add edges $(v_i,\lnot v_i)$, $(v,c_i)$ for $v \in c_i$,
$(\lnot v,c_i)$ for $\lnot v \in c_i$.
Set the weights of $c_i$ have prohibitively large $2n$ and the weights of
$v,\lnot v$  to $1$.
We believe Minimum Weighted Independent Dominating Sets (MWIDS) of weight $n$
in $\Gamma(\phi)$ are in bijection with the satisfying assignment of $\phi$.
If $v$ dominates $c_j$, the clause $c_j$ is satisfied. MWIDS dominates
all clauses, so they are satisfied.
In a satisfying assignment of $\phi$ all clauses are satisfied
and the solution is MWIDS.
We saw very similar unweighted reduction of SAT to MIDS in a paper.

Q2 Does the above construction preserves isomorphism?

Q3 If the construction is correct, but the definition of isomorphism
is incorrect, what does $\Gamma(\phi_1) \cong \Gamma(\phi_2)$
implies about $\phi_1$ and $\phi_2$?


texts: Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

texts:
I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs.

If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane graphs, is the problem still NP complete?

My intuition is that this extra requirement shouldn't make the problem easier, but maybe this feeling is naive since after all it means that the reduction has to be more intricate.


texts: Algorithms and approximations for optimal offline binary tree operations

texts:
Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted element must exist in the set, and an inserted element must not already be in the set. The goal is to transform the trees to represent the requested sets using the minimum number of basic operations. What makes the problem interesting is that this is an offline algorithm: we know in advance the full sequence of operations, and need to plan ahead so that elements that will be deleted are near the root.
We shall represent trees as bracketed expressions like $a(b(cd))$ which are transformed by commutative / associative transforms. The set represented by a tree is the set of its (distinct) leaf nodes. Transformation costs are such that:

$u(vw)\leftrightarrow (uv)w$ and $uv\leftrightarrow vu$ in one step
If $u\to u'$ in $n$ steps then $uv\to u'v$ and $vu\to vu'$ in $n+1$ steps.

Given a sequence of requests $r_1,\dots,r_n$ where each $r_i$ is $\mathsf{insert}(a)$ or $\mathsf{delete}(a)$, a valid solution is a sequence of trees $t_1,\dots,t_n$ such that:

$t_1=a$ if $r_1=\mathsf{insert}(a)$ in $n_1:=0$ steps
If $r_{i+1}=\mathsf{insert}(a)$ then $t_ia\to t_{i+1}$ in $n_{i+1}$ steps
If $r_{i+1}=\mathsf{delete}(a)$ then $t_i\to t_{i+1}a$ in $n_{i+1}$ steps

The total cost of the solution is the sum of the $n_i$'s. OPT is one with minimal cost. Is it possible to efficiently compute the optimal solution, or a solution with cost within a constant factor?
This problem is similar to the dynamic optimal BST problem, but there are some notable differences:

Lookup time is not a factor in this problem, as we have complete knowledge and are not performing lookup. Still, the cost of doing a deletion is about the same as what you would get with a lookup in a BST.
The binary trees need not be sorted. Again, because the algorithm is working from complete information the BST property is only deadweight here, and OPT can possibly make better moves if it is allowed to use the $uv\to vu$ transformation.
This is an offline algorithm, meaning that we "know the future". Most research on the dynamic optimal BST problem assume that while OPT can see the future our algorithm is a best online approximation to that. Here OPT can actually be calculated (at exponential time complexity by brute force), and the question is whether we can do better than that.


texts: Finding an equivalent NP-complete instance for this game-theory problem

texts:
I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't explicitly required it, I'd like to prove the NP-hardness or completeness of the problem since it's something I'd like to learn to do. I'm pretty new at theoretical CS since I've been working as a software-engineer for the past 8 or so years.

My problem is as follows. The defender has a set of targets $T = \{a, b, c, d, e, f, g\}$ and $k$ resources, where $k < |T|$. The defender can place at most one resource on one target to cover it.

There is an attacker who can attack any subset of targets in $T$. So the attacker's pure strategy $A \subseteq T$ and $A \in \mathcal{P}(T)$.

The attacker succeeds if all the targets he attacks are not covered by the defender. If at least one of the targets that he attacks is covered by the defender, he fails.

The defender does not know which targets the attacker will attack, and he also does not know the number of targets either. The defender's job is to come up with an optimal mixed strategy (a vector with a probability assigned to each pure strategy) to guard against the attacker. The probability assigned to a pure-strategy is the probability that the defender will play that pure strategy. This information is also known to the attacker.

I know that the strategy space for both players is large. The total number of pure strategies for the defender is $\binom{|T|}{k}$, and for the attacker it is $2^{|T|}$. There is a standard algorithm that generates a set of linear programs to solve for the defender's mixed strategy. However, we will end up with $2^{|T|}$ linear programs, each with $\binom{|T|}{k}$ variables. So the complexity is $O\big(2^{|T|} \times \binom{|T|}{k}^{3.5}\big)$ (Karmarkar's algorithm).

The algorithm won't perform well at all, because there combinatorial explosion in the strategy space for both the defender and attacker. I'm trying to see if there is an NP-complete problem I can reduce this to, but I'm not sure where to go from here. I have looked at set cover, and exact set cover, but I'm still not sure how I would reduce it to that, or even if those are applicable here.

I read this paper where they deal with a somewhat similar problem (urban network graph, where an attacker can attack any target from a starting point by using any of the paths available; the defender has $k$ resources that he can place on edges to block the attacker). Here, they use a double oracle approach and then prove the NP hardness of the defender and attacker oracle by reducing to set-cover and 3-SAT respectively. The defender oracle tries to find a pure strategy for a given attacker mixed-strategy, and the attacker tries to find a pure strategy for a given defender mixed-strategy.

I'm trying to do something similar, but I'm not sure where to start, or even of it would be applicable in my case. For example, if we have an attacker with the following mixed-strategy $\{\{b, c\}, \{a, b, c,\}, \{a, b, d\}, \{b, c\}\}$ (where each one has an associated probability), the defender needs to find the optimal pure strategy that covers the most targets and gives him the most payoff. If we assume that the defender has 3 resources, the optimal pure strategy would be one of $\{\{a, b, c\}, \{a, b, d\}, \{a, c, d\}, \{b, c, d\}\}$. Here, it doesn't look like finding a cover would help, since the defender only has 3 resources. So I'm not sure where to go from here.

EDIT:  Each target $t \in T$ has an associated payoff of $\tau_t$.


texts:
Suppose Mario is walking on the surface of a planet.  If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop?

More formally, suppose we are given a convex polytope $P$ in 3-space, a starting point $s$ on the surface of $P$, a direction vector $v$ (in the plane of some facet containing $p$), and a distance $\ell$.  How quickly can we determine which facet of $P$ Mario will stop inside?  (As a technical point, assume that if Mario walks into a vertex of $P$, he immediately explodes; fortunately, this almost never happens.)

Or if you prefer: suppose we are given the polytope $P$, the source point $s$, and the direction vector $v$ in advance.  After preprocessing, how quickly can we answer the question for a given distance $\ell$?

It's easy to simply trace Mario's footsteps, especially if $P$ has only triangular facets.  Whenever Mario enters a facet through one of its edges, we can determine in $O(1)$ time which of the other two edges he must leave through.  Although the running time of this algorithm is only linear in the number of edge-crossings, it's unbounded as a function of the input size, because the distance $\ell$ could be arbitrarily larger than the diameter of $P$.  Can we do better?

(In practice, the path length isn't actually unbounded; there is a global upper bound in terms of the number of bits needed to represent the input.  But insisting on integer inputs raises some rather nasty numerical issues — How do we compute exactly where to stop? — so let's stick to real inputs and exact real arithmetic.)

Is anything nontrivial known about the complexity of this problem?

Update: In light of julkiewicz's comment, it seems clear that a real-RAM running time bounded purely in terms of $n$ (the complexity of the polytope) is impossible.  Consider the special case of a two-sided unit square $[0,1]^2$, with Mario starting at $(0,1/2)$ and walking in direction $(1,0)$.  Mario will stop on the front or the back of the square depending on the parity of the integer $\lfloor \ell \rfloor$.  We can't compute the floor function in constant time on the real RAM, unless we're happy equating PSPACE and P.  But we can compute $\lfloor \ell \rfloor$ in $O(\log \ell)$ time by exponential search, which is an exponential improvement over the naive algorithm.  Is time polynomial in $n$ and $\log \ell$ always achievable?


texts: Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?

texts:
It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them.
However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most one push or pop in each move?

To be more specific, call a PDA real-time if the machine can see the currently read letter and the top of the stack, then based on this, it either needs to delete the top element of the stack (pop), or push one element onto the stack (push), or leave the stack as it is. In either case, it has to move to the next letter.

  Is there a CFL that no real-time PDA can recognize?

Related: Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

Crossposted: https://cs.stackexchange.com/questions/114995/pdas-without-%ce%bb-steps-or-popping-more-than-one-from-stack


texts: Find the most/least repeated group of N-members in given draws

texts:
Can someone suggest a good algorithm for the following problem (or a reference to look up)?
You have a set of numbers from 1 to $m$ (m=80) (inclusive). $n$ (=20) non-repeating numbers will be drawn from the set in an increasing order in a single draw. There will be 2 to N draws, and you will have the results of those draws. Design an algorithm, which will find the most and the least repeated group ($N$-members) of numbers in the draws.

Sample draws
1) 4   5   7   19  28  32  39  40  43  44  46  47  48  49  55  56  59  69  73  79
2) 1   10  11  19  20  27  32  35  41  42  46  49  51  54  58  61  63  67  68  76
3) 3   4   5   8   11  16  24  25  27  34  37  48  49  50  57  58  59  68  71  73
4) 1   8   10  13  18  26  27  30  32  35  45  46  49  52  53  61  66  72  75  78
5) 7   14  20  21  25  26  38  40  43  46  49  53  54  58  60  61  66  68  74  80

Further explanation
The algorithm should find the most repeating group of N-numbers (say 3 numbers). So, basically a tuple of three numbers that is repeated the most in the draws must be found. it is also possible that there will be a most/least common group of $N$-members, but it is quite as possible that there won't.


texts:
It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. Is it possible to define such $F$ so that given $x$ we can compute $F(x)$  efficiently ?

Thanks.


texts: Finding the point that maximizes a linear function

texts:
Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i > 0$ are positive integers. We will be given a workload of queries $Q = \{c_1, \dots, c_k\}$ where for each $c_j \in Q$ (a positive integer), we need to find the point that maximizes the linear function $c_j \cdot x+y$.
Ideally, I would like to preprocess all the points in at most $O(N \log N)$ time and then answer the query for each $c_j \in Q$ in $O(\log N)$ (or maybe even constant) time.
I feel there is such an algorithm where I can sort the points by $x_i$ and/or $y_i$ and do some binary searches but it is more complex than I thought. Any there tradeoffs between preprocessing vs answering time or lower bounds known for this problem?
Edit : A fellow graduate student gave the following idea - constructing a convex hull of the $N$ points, sorting the slopes of the line segments formed by consecutive points on the hull and then finding the line segments with the slope "closest" to $-c_j$ will identify the point that maximizes the linear function $c_j x + y$. I think this works but will verify the details tomorrow. My sleep will be ruined if there is a bug.


texts: Is education for research-based CS at odds with that of industrial CS?

texts:
I'm an undergraduate strongly interested (well, this is a hunch) in theoretical CS and all things mathematical. While I'd like to devote my time to participating in research opportunities and learning more about academia-related CS, I also want to develop a skillset (in software engineering) that, if I were unsuccessful in entering academia, would give me a fallback.

I suspect that the past an early point, the learning routes for academia-CS and industrial CS diverge, meaning that I can't prepare myself for both. To what extent is this true  -- everybody needs to have experience in a couple of programming languages, for example, but that aside, are there commonalities or differences between preparing for academia and industry that bar or support my plan? Is what I want feasible and, if so, how? Many Thanks.


texts: Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

texts:
$CFL$ is the class of context-free languages.

  Question

  Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space?  What about $DCFL$?


texts:
I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless.
So that is why I'm asking.

1)
Is there a mathematical proof that the Langton's ant will stay forever on the highway once it's enter in it ?

2)
Is there a proof that for only one initial condition the Langton's ant will always build the highway ?


texts:
According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles, and below $S_n$ refers to the sphere with exactly $n$ handles), one can define a dual multigraph by treating the faces of the original graph embedding as vertices and adding an edge between two vertices for every side the corresponding faces have in common in the original graph.

Here's my problem. Given a graph $G$, I need to find another graph $G'$ such that there exists a surface $S$ and a cellular embedding of $G$ on $S$ such that $G'$ is the dual of this embedding of $G$. I know that there are many possible graphs $G'$; I just need to find one for every graph $G$.

I have several questions. My current strategy is to (1) determine the genus $n$ of $G$, (2) find an embedding of $G$ on $S_n$, and (3) find the dual of this embedding. All those steps have known algorithms (although (1) is NP-Hard). I wonder if there's a way to find a $G'$ that bypasses the computation of the genus, since that is the bottleneck of this approach, and that's my first question. My second question is: If I know that $G$ is regular, can that ease the computation of the genus? And my third question is a request for any references that can help me solve this problem.


texts: PARITY $\notin$ $AC^0$ with bounded fanout: easy proof?

texts:
$AC^0$ is the class of constant-depth polynomial-size circuits with NOT gates and  unbounded fan-in AND and OR gates, where inputs and gates also have unbounded fanout.

Now consider a new class, call it $AC^0_{bf}$ which is like $AC^0$ but for which inputs and gates have fanout at most $O(1)$.  This class is clearly in $AC^0$.  In fact, it is strictly contained in $AC^0$, as noted here.  Therefore, PARITY is obviously not in $AC^0_{bf}$.

Is there a proof of PARITY $\notin AC^0_{bf}$ which does not also go through for $AC^0$? In other words, is there a proof which does not use powerful techniques like the switching lemma or the Razborov/Smolensky method?


texts: Complexity of Computing Lexicographically Minimal Element of Orbit

texts: Given strong generators for a group $(G \leq S_n, *)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, the orbit of $s$ in $G$?


texts: description of continuous probability distribution

texts:
The minimum description length of the realization of a random variable $x$ is given by the entropy of its probability mass function. It can be asymptotically communicated at this rate with an optimal coding. But that's for just one $x$ from the optimal coding table. How do we cover the whole support efficiently? (Of course, we'll have issues with quantization of real valued $x$-s in our code table, however optimized it's going to be.)

Viewing it differently, entropy of the representation of a generic probability distribution with CDF $F(x)$, where $F(x) \sim p(F(x))$ on some space of distributions $D$, seems to be bounded from above by entropy of uniform $p$ on space $D$: $-\int_D{p(F(x))\ln{p(F(x))}dF(x)}$. But this is clearly not a sharp maximum description length bound (probably need to introduce some reasonable restrictions).

Looks like I'm missing something obvious, any ideas would be appreciated...

Oh, and this has nothing to do with differential vs discrete entropy, the same question can be posed for the latter case.

[Updated after Peter Shor's comments; also cleaned up language and formulations a bit.]


texts:
Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This was the motivation behind one of my previous questions asking for NP-hard problems on trees.

There are several directed versions of tree width measuring how close a directed graph is to a directed acyclic graph (DAG). What are some directed problems that remain NP-hard on DAGs ? A directed problem makes essential use of the directions of the edges. For example, hamiltonian path is a directed problem whereas vertex cover is not. One of the answers to my previous question gave a general recipe for generating problems that are hard on trees. Is there such a recipe for DAGs ?


texts: Papers on using resource states to implement QFT efficiently

texts:
I recently stumbled onto the idea of using a pre-existing re-usable phase gradient to implement the QFT, instead of having to keep re-applying exponentially precise phase gates. I'm looking for papers on this general idea (or improvements thereof).

I don't even know the technical name for this technique, so even that information would be useful.

An example QFT circuit showing the phasing-by-subtraction that I'm talking about (and the equivalent circuit in Quirk, where numbers have opposite endian-ness so lots of reversing is required):

Note that the above isn't quite as optimized as what I have in mind. In particular, when you break the subtractions down into H/CX/T gates you find that they start by undoing work the last subtraction ended with. This lets you save half of the T gates.


texts: Using Pearson Correlation Coefficient in computing user/item similarity

texts:
I'm researching for an algorithm for item-based/user-based collaborative filtering and I've come to this site.

It uses Pearson correlation coefficient to compute similarity between users and when I read this line:

  A strength of this formula is that it takes into account average
  ratings for each user. So if user a rates everything a 5 and user u
  rates everything a 1, then they still have a similarity rating of 1.

I wonder why it would give a similarity of 1 because using the said equation which is the Pearson and using the given (user a, 5 and user u, 1), it would give a zero for the numerator and denominator.

So what is the reason he said that the similarity of user a and user u with a rating of 5 and 1, respectively is equal to one? Is zero over zero equals to one?


texts: Proof software for Primitive Recursive Arithmetic

texts:
Primitive Recursive Arithmetic is a critical foundational system in mathematics at large, and all the more so in areas studying constructive reasoning and/or computability such as Theoretical Computer Science.

Is there any proof software that deals with Primitive Recursive Arithmetic... or equivalent systems?


texts: When does an FO property kill off NL-hardness?

texts:
Context:  We consider only digraphs.  Let CYCLE be the language of graphs with a cycle; it is an NL-complete problem.  Let HASEDGE be the language of graphs with at least one edge. Then trivially, $\text{CYCLE} \cup \text{HASEDGE}$ is no longer NL-hard, while $\text{CYCLE} \cup \overline{\text{HASEDGE}}$ stays so.

Actual problem: I'm wondering if the language $$\text{CYCLE} \cup \{(V, E):(\exists u,v,x,y)[E(u, v) \land E(x, y) \land \neg E(u, y) \land \neg E(x, v)]\}$$ is still NL-hard.

Question: For which FO formula $\phi$ on the vocabulary of graphs is
$$\text{CYCLE} \cup \{(V, E) : (V, E) \models \phi\}$$
NL-hard?  Is this property decidable?

Thanks for your input!


texts:
Problem: In a directed graph $G=(V,E)$, each edge $e\in E$ is associated with a weight $w_e$ which is geometrically distributed with a parameter $p$, i.e. $P(w_e=i)=p(1-p)^{i-1}, i\geq 1$. $s,t$ are two nodes in $G$ and $k$ is a positive integer. What is the probability of the event that the shortest path from $s$ to $t$ has length at least $k$?

I feel this problem should be #P-hard, but I have no idea how to prove its #P-hardness.

I know I should choose a known #P-complete problem, and reduce it to the problem above. But I don't know which one to choose.


texts: Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

texts:
The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the rectangles using minimum number of colors such that any two overlapping rectangles are assigned different colors.

This problem is known to be NP-hard. Xin Han, Kazuo Iwama, Rolf Klein and Andrezej Lingas (Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs) gave an O(log n) approximation. Is there a better approximation algorithm?

We know that the interval coloring problem is solved in polynomial time by first-fit algorithm by considering intervals according to their left endpoints. However, first-fit online algorithm is 8-competitive when the intervals appear in arbitrary order.

What is the performance of the first-fit algorithm for the rectangle coloring problem? What happens to first-fit algorithm when the rectangles appear according to their left (vertical) sides?

Thanks in advance for any help on this.


texts: Largest common subgraph of two maximal planar graphs

texts:
Consider the following problem -

Given maximal planar graphs $G_1$ and $G_2$, find the graph $G$ with maximum number of edges such that there is a subgraph (not necessarily induced) in both $G_1$ and $G_2$ that is isomorphic to $G$.

Can this be done in polynomial time? If yes, then how?

It's known that if $G_1$ and $G_2$ are general graphs, then the problem is NP-complete (because $G_1$ could be a clique). It's also known that if $G_1$ and $G_2$ are trees, or bounded degree partial k-trees, then the problem can be solved in polynomial time. So what about the maximal planar case? Does anyone know this? Graph isomorphism on two maximal planar graphs is polynomial. Perhaps this helps somehow?


texts: Relation between Kleene star, union and difference in relation algebra

texts:
So I'm wondering about some finer points of relation algebra, a field in which I'm not an expert:

Given relations $A$, $B$ and $C$ over the same set $S$, is it always true that $A^*\subseteq (B\cup C)^*$ iff $(A\setminus B)^*\subseteq C^*$ ?

Here, $A^*$ denotes the reflexive, transitive closure of $A$, $\cup$ is set union, and $\setminus$ is set difference.


texts: Maximum matching versus preferential assignment

texts:
There are several ways to solve the marriage problem. The "preferential assignment" approach consists in forming couples on the basis of preferred characteristics expressed by each individual. An alternative approach consists in selecting preferred partners among lovers: suppose that you have the graph $G$ of sexual relations, and that each relation $e$ is rated with some preference factor $w(e)$, then computing a maximum weighted matching in $G$ would aim at optimizing the sexual adequacy between lovers.

If there are only heterosexual relationships with two sexes (men and women), then this is a bipartite matching problem, which is conjectured to be in $NC_2$ . Now suppose that a devious adversary had the following abilities: (i) control of the sexual performances of the individuals, (ii) ability to solve parallel problems efficiently. Then this adversary could trick the heterosexual group into forming "bad unions" in a pessimistic sense, i.e. leading to increased instability or corruption.

So my question is: what are the remedies to this problem? Does the introduction of same-sex relations or ternary relations change the situation? I suspect that the goal would be to obtain a P-complete matching problem to defeat the parallel adversary.


texts: Decidability of the monadic second-order theory of a class of finite structures

texts:
Let $L$ be the set of sentences in some logic.  I am interested in cases where $L$ is the set of sentences in monadic second-order logic, or it is its $\Pi^1_1$ fragment.  Let $K$ be a class of finite structures.  The theory $\mathrm{Th}_L(K)$ of $K$ is the set of sentences $\phi$ such that $\forall M \in K$ $M \models \phi$.  I am interested in decidability of $\mathrm{Th}_L(K)$.

For what kind of class $K$ is this known?  What are important / deep techniques here?  What is a good source to learn the results and the techniques?


texts:
My question is about finite model theory/descriptive complexity, so $FO(R)$ will mean "first order over finite binary words, using predicates Rs and a unary predicate P true on the position of the 1 in the word".

I would like to know, are there any caracterisation of $FO(<,R)$ with R any predicate on $\mathbb N^r$ for some r? For example on $FO(<,+)$, or $FO(<,P_2)$ where $P_2$ is the set of power of 2. Especially, it seems to me that it should be equal to $AC^0$ with some uniformity condition, but I can not find any resultat that states this.

Here is what I already know, for some value of $R$.

It is well known that $FO(<,bit)$, the first order logic on words with an order and a bit predicate is equal to $AC^0$-$FO(<,bit)$ uniform. By this it means they both recognise exactly the same languages.  See for example "Descriptive complexity" of Immerman, page 82.
(It is also equal to a lot of other caracterisation, such as $AC^0$-logtime uniform, and constant-time parallel random access machine, but it is not what I am searching for here.)

If we can use arbitrary numerical predicate in our first order logic, then we have $AC^0$ (non uniform), if $C$ is a class of function containing the log-time computable function, then $FO(<,C)$ is equal to $AC^0-C$-uniform (for these two results see Barrington, "Extensions of an Idea of Mc-Naughton", 1993).

Finally $FO(<)$ is the class of star-free language (language that can be defined by a regular expression using no Kleene star), but this give no information in term of circuit complexity.


texts: Finding a sub rectangle with maximum sum

texts:
Given a $n \times n$ matrix filled with positive or negative numbers, find a sub rectangle with maximum sum and output the sum.

There's a well-known algorithm which runs in $O(n^3)$, but can the complexity be improved any further?


texts: Concepts in theoretical CS that would be approachable ages 8-14

texts: Guessing it's unlikely a common question, but wondering if anyone has seen material that was clearly made to address this audience in a meaningful way.


texts: What is the formalism behind ?- (query) in Prolog?

texts:
I am in general interested in a more formal (better be logical, as in related to mathematical logic) definition of a query.  As an example, there's Prolog operator ?- which takes as its argument a sentence in first order logic + meta-logical operators specific to Prolog and produces an "answer".

I'm interested to know what kind of logic deals with this (kind of) operator.


texts: Convergence of first order subgradient methods for non-convex functions

texts:
This lecture note gives the proof for how deterministic subgradient method converges on non-smooth convex and strongly convex Lipschitz functions.
Is there a non-convex version of this proof?
Like convergence of subgradient method for,

non-smooth Lipschitz non-convex functions (like $\frac{1}{1+e^{-\vert x \vert}}$) ?
non-smooth non-Lipschitz non-convex functions (like $(1-\vert x \vert)^2$)?

(happy to get references for the the stochastic versions of these too!)


texts: What does the contention-free communication assumption really mean in the context of DAG scheduling?

texts:
In many papers about DAG (directed-acyclic graph) scheduling in distributed systems, the authors make the assumption that the communication between the processors of the system where the DAG is scheduled is contention-free.

Does that mean they assume that each communication link can transfer concurrently an infinite number of messages (connections) and each connection uses the full bandwidth of the communication link?

For example, in case there are 5 concurrent connections on a 100Mb/s communication link from processor A to processor B, the speed of each connection is assumed to be 100Mb/s instead of 20Mb/s (i.e. 100/5=20)?

Many thanks in advance.


texts: Are there any known problems that have an Ackermann function time complexity lower bound?


texts: resolution based theorem prover for temporal logic

texts:
I am looking at implementing a a resolution-based theorem prover for propositional linear temporal logic (PLTL) (as opposed to a model checker). The ones out there (by Fisher et. al. and others) are complex on account have having to deal directly with temporal resolution. So looking for something quick and good enough for now (I'm not too concerned with retaining decidability or its efficiency at this point), I am considering the translation of PLTL into first order logic (FOL). The propositions are turned into unary predicates over numbers. This translation is well known and described in several places (eg Fisher)

p → p(i)

$\circ$p → p(i + 1)

$\diamond$p → ∃j. (j ≥ i) ∧ p(j)

$\Box$p → ∀j. (j ≥ i) ⇒ p(j)

The problem is that these first order formulas have distinguished symbols > and succ (as well as equality) - alternatively the FOL formulas are meant to be interpreted w.r.t. a natural number line which corresponds to the timeline of PLTL. Is there a good way to implement a resolution prover that can take into account or provide these symbols with their required interpretation? More specifically:

For example, would it work to add the theory of the successor function to the translation and go from there?
How would I handle equality? (paramodulation?)
I'd like to be able to implement this in Prolog but you can't encode equational theories like subsets of arithmetic in Prolog, but would Prolog's built-in arithmetic operators perhaps suffice?

Thanks!


texts: Is this greedy algorithm for vertex cover studied before?

texts:
For the vertex cover problem (Given a graph $G$, find a minimum set $S$ of vertices such that $G - S$ is edgeless), there are two famous greedy algorithms.  The edge greedy (finding an edge and taking its both ends) has ratio 2, while the maximum-degree greedy (taking a vertex with the maximum degree) has ratio O(log n). How about the following one:

Repeat until the graph is edgeless,
take a vertex $v$ with the minimum degree, add $N(v)$ into the solution, and $G \leftarrow G - N[v]$.

I noticed some experiments on this algorithm (e.g., https://doi.org/10.1109/ICPCI.2012.6486444). But my interest is on rigorous analyses. Is there any known ratio for it?

Any suggestion of bad examples for this algorithm is also very appreciated.


texts: Are (empirical) Rademacher complexity always positive?

texts:
Rademacher complexity and empirical Rademacher complexity are used to provide upper bound on the loss of solving an learning problem.
That seems to imply that Rademacher complexity and empirical Rademacher complexity can't be negative.

But from their definitions, I can't figure out if they are indeed always nonnegative. So what is the truth? Thanks.

For their definitions, I refer to  http://www.cc.gatech.edu/~ninamf/ML11/lect1115.pdf.


texts: Lower bounds on the size of CFGs for specific finite languages

texts:
Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?

We can make the question more interesting by specifying a sequence of languages $L_n$, for example $L_n$ is the set of all permutations of $\{1,\ldots,n\}$: intuitively, a CFG for $L_n$ would "need" to have size $\Omega(n!)$. So we're interested in the asymptotic size of the smallest CFGs for the languages.

Similar questions have been dealt with in several papers:

Charikar et al. ("Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models") consider how difficult it is to approximate the size of the smallest CFG generating a given word.
More work in that direction is Arpe and Reischuk, "On the Complexity of Optimal Grammar-Based Compression".
Peter Asveld has several papers on the subject (e.g. "Generating All Permutations by Context-Free Grammars in Chomsky Normal Form"). He's trying to optimize some parameters on specific types of grammars generating the set of all permutations, specifically Chomsky and Greibach normal forms.

However, so far I haven't been able to find any paper trying to prove a bound of $\Omega(n!)$ on the size of a CFG generating $L_n$.

  Are there papers providing lower bounds for the size of context-free grammars for specific finite languages?

In response to several questions on this site as well as on math.stackexchange, I came up with a simple method able to prove exponential lower bounds on CFGs for specific languages, for example $L_n$. Are these results new? I find that hard to believe, and I'll be glad to get any literature pointers.


texts: An oracle in $\mathsf{NEXP}$ that separates ZPP from BPP

texts: Does there exist an oracle $A \in \mathsf{NEXP}$ such that $ \mathsf{ZPP}^A \neq  \mathsf{BPP}^A$?


texts: Is it NP-Complete to determine if a quadratic program (QP) has multiple solutions?

texts:
If this is known, can someone point me to a proof?

Edit:

A QP is essentially a LP with a quadratic objective. That is, it looks like:

minimize $\frac{1}{2} x^T Q x + c^T x$

s.t. $Ax \leq b$

It's known that in general, solving a QP is NP-Hard. Is it NP-Complete to know if there are at least two different solutions to the QP?


texts: What is the state complexity of the copy language?

texts:
Let a number $n$ be given.  Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$.

In words, $L_n$ is the set of copy strings of length $2n$.

Consider the following state complexity function $s$ such that $s(n)$ is the number of states in the smallest Pushdown Automata that recognizes $L_n$.

Question: Can you formally prove any meaningful lower bound for $s(n)$?

My Conjecture: $s(n) = 2^{\Theta(n)}$.

Known Upperbound: $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$.

Rules:

(1) The stack alphabet must be binary.

(2) The input tape is one-way and can't stop on any input character.


texts: Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?

texts:
Suppose that, for each $\epsilon > 0$, there is an Turing machine $M_{\epsilon}$ that decides a language $L$ in time $O(n^{a + \epsilon})$. Is there a single algorithm deciding $L$ in time $O(n^{a + o(1)})$? (Here, the $o(1)$ term is measured in terms of $n$, the input length.)

Does it make a difference if the algorithms $M_{\epsilon}$ are computable, or efficiently computable, in terms of $\epsilon$?

Motivation: in many proofs, it is easier to construct algorithms of time $O(n^{a + \epsilon})$ than the limiting algorithm $O(n^{a + o(1)})$. In particular, you need to bound the constant term in $O(n^{a + \epsilon})$ to pass to the limit $O(n^{a+o(1)})$. It would be nice if there is some general result you can invoke to pass to the limit directly.


texts: Good description of Calculus of Inductive Construction

texts:
I want to learn more about Calculus of Inductive Constructions. What can you recommend to read on this topic? All the materials which I found are either in French or too basic (the Coq'Art book).

The thing I am interested the most are not definitions but the proofs of important properties.


texts: How to calculate the cost of factoring a large integer?

texts:
I would like to know how much it would cost to factor a large integer. The cost can be given computer operations, time to process it or even monetary value. I know there are people that factored 200 bit RSA keys, but Wikipedia doesn't say how long it would take in modern CPUs.

-- Background --

I am designing a virtual roulette game where the ball is spun (the number is chosen) before the player bets. As a proof of that but I show the player the product of two primes, one of them is used as the random number seed.

I would like to know what is the minimum suitable size for this number such as the cost of factoring it will be greater than the maximum prize I offer.


texts: P=BPP and derandomizing Vazirani-Valiant?

texts:
Vazirani-Valiant reduction is a randomized reduction from $SAT$ to unambiguous $SAT$.

1. Is $P=BPP$ strong enough to derandomize Vazirani-Valiant reduction?

2. If not what other ingredients are necessary to derandomize Vazirani-Valiant reduction?

The above two are addressed in Derandomizing Valiant-Vazirani?. However we can still ask whether there is a possibility of $P$ is not $BPP$ and still if it would be possible to derandomize Vazirani-Valiant.

Is $P=BPP$ necessary to derandomize Vazirani-Valiant reduction?
If not what would derandomizing Vazirani-Valiant reduction tell about $P=BPP$?


texts: Regular languages from category-theoretical point of view

texts:
I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a strict monoidal structure on this category that is distributive over joins (I'm not sure about meets). Is this a useful construct in theory or practice of regular languages? Are there some nice adjunctions to be found, e.g. can we define the Kleene star as one?

This is a copy of a question asked at the Compilers course at Coursera:
https://class.coursera.org/compilers/forum/thread?thread_id=311


texts: Data structure that allows moving groups of elements into buckets

texts:
I'm looking for a data structure that can do the following geometric operation:

Suppose there are a set of buckets $b_0, b_1..., b_n$ each of which contains some elements. Suppose I want to move all the elements in buckets $b_i$ where $i > k$ one bucket forward. So the elements in bucket $b_{k+1}$ would be moved to bucket $b_k$ and the elements in bucket $b_{k+2}$ would be moved to bucket $b_{k+1}$ and so on. The obvious way to move these elements is to go to each bucket and shift all the elements into the previous bucket. But is there a data structure that will allow me to move the buckets all at once?

I used buckets in the description because it's easier to formulate the question in terms of buckets. But the data structure doesn't necessarily have to be buckets. All I need is a data structure that can allow me to move "chunks" of elements in one go (for example shifting consecutive the buckets $x$ number of buckets forward all at once) and then allow me to query the structure as normal (for example, allow me to query $b_{k}$ now with all the elements shifted.

EDIT: I'm mainly interested in whether an already existing data structure that I'm not aware of does this.


texts: Has there been any work done on incremental connectivity in path graphs?

texts:
This set of lecture notes describes a data structure for decremental connectivity in path graphs that supports queries and removals in amortized O(1) each. Has there been any work done on incremental connectivity on path graphs? Using a disjoint-set forest it's possible to do queries and insertions in amortized O(α(n)) time each, but can that be sped up using the fact that we're only looking at a path graph, not a general graph?

Thanks!


texts: Approximation Algorithm for TSP-like problem

texts: Suppose we are given a graph with distances for each of the edges and merit for each of the nodes. What are the best (approximation) algorithms for computing the the most meritorious simple path with a cap on the maximum distance allowed?


texts:
What are "easy regions" for satisfiability? In other words, sufficient conditions for some SAT solver to be able to find a satisfying assignment, assuming it exists.

One example is when each clause shares variables with few other clauses, due to constructive proof of LLL, any other results along those lines?

There's sizable literature on easy regions for Belief Propagation, is there something along those lines for satisfiability?


texts: A class name for series-parallel graphs of same length

texts:
I'm currently working on graphs classes where the distance between two specific vertices is the same in every connected spanning subgraphs, and I am looking for a name for this class.
Given a connected non-directed graph $G$ and two of its vertices $u,v$ such that $G$ is a two-terminal series-parallel graph (TTSPG) from $u$ to $v$ and every path from $u$ to $v$ is of the same length (equal to $d(u,v)$), is there a name for such graphs ?
Given a graph $G$ and $u,v$ two vertices, $H \subseteq G$ the induced subgraph formed of all possible paths from $u$ to $v$ (or excluding any vertex that is not in a path from $u$ to $v$), the distance between $u$ and $v$ is preserved in spanning connected subgraphs of $G$ if and only if $H$ is a TTSPG with fixed length between $u$ and $v$. Does this graph class (or the definition of $H$) has a known name ?


texts: Open problems/Conjunctures in non-uniform complexity if proved would imply P=NP

texts: As we now, NP ⊈ P/poly would imply P≠NP. Can you mention some conjuncture/open problems in non-uniform complexity, that would imply P=NP,if proved


texts: Generalizing limit-colimit coincidence to Scott-continuous adjunctions: any uses?

texts:
In Abramsky and Jung's 1994 handbook chapter on denotational semantics, after proving that the limit and colimit of expanding sequences exist and coincide, they have the following to say about generalizing this theorem:

  We can generalize Theorem 3.3.7 [the limit-colimit coincidence of expanding sequences in DCPO] [...] we can use
  general Scott-continuous adjunctions instead of e-p-pairs. [...] By the passage
  from embeddings to, no longer injective, lower adjoints, we allow domains not only to
  grow but also to shrink as we move on in the index set. Thus points, which at some
  stage looked different, may at a later stage be recognized to be the same. [...] For the
  main text, we must remind ourselves that this generalization has so far not found any
  application in semantics.

It's been over fifteen years since this chapter was written. Have there been any applications of this generalization in semantics since then?


texts: Testing feasibility of special linear programs

texts: We have a linear program in the standard form $Ax=b,x\geq 0$ with $A(i,j)\in\{-1,0,1\}\:\forall\,i,j$ and $b(i)\in\{0,1\}\:\forall\,i$. $A$ is not full rank. Is the time complexity of testing the feasibility of this LP any better than that of general LPs? If yes, is there an algorithm known? Thanks in advance.


texts: Is there any system where function equality (extensionality) is decidable?

texts: Is there any programming language or system where function equality (extensionality) is decidable?


texts: Dinner-table description of theoretical computer science?

texts:
I'm often asked what a theoretical computer scientist does.  It would be great to have some nice responses to this question.  I tend to fall back to technical jargon and people's eyes usually glaze over at this point.

  What does a theoretical computer scientist do, in terms that can be understood by people who are not computer scientists?

A good answer should be snappy, accurate in spirit, without sounding vague or trite.  For bonus points, the answer should hint at why a theoretical computer scientist is neither a mathematician nor an IT practitioner.

This question is inspired by the MO question https://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics although the intent is different.


texts: Is there a standard definition of Quantum Randomness?

texts:
I hope this question is not too vague.

For classical bit generators there is the classical statistical definition which (informally) states that a source is ideally random if its output $X_1,X_2,\ldots$ is a sequence of uniform i.i.d. bits.

There is also the alternative Kolmogorov Complexity definition in which an individual string's complexity (informally analogous to randomness) is expressed by its compressibility which is defined as the length of the shortest computer program (w.r.t. a Universal Turing Machine) which will generate the string.

Another definition relates the randomness of the string to the computational complexity of predicting it. This is used, e.g., in the Blum-Blum-Shub generator, where it can be shown that its next output bit can be predicted with probability $(1/2 + \varepsilon)$
for some $\varepsilon>0$ if and only if the RSA problem (given 2 randomly chosen n bit primes $p,q$, form their product $N=pq$ and erase $p$ and $q$; how difficult is it to obtain $p$ and $q$ from $N$?) has an efficient solution polynomial in $n.$

I think some quantum randomness generators use photonic processes to generate bits at their output. However, what is the standard (if any) definition of quantum randomness? I don't know much about quantum theory, but if a quantum system is undergoing the normal Hermitian evolution it seems to me that the output obtained from such a system will not be very random.


texts: Deciding emptiness of intersection of regular languages in subquadratic time

texts:
Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input.

Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which computes the product automaton of $M_1,M_2$, but I was wondering if anything more efficient is known.

  Is there a $o(n^2)$ algorithm for deciding whether $L_1\cap L_2\neq \emptyset$? What is the fastest known algorithm?


texts: Minimum equivalent digraph with respect to sources and sinks

texts:
Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$.
Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that:

For all pairs $u \in S, v \in T$ there is a path from $u$ to $v$ in $D$ if and only if there is a path from $u$ to $v$ in $D'$.

One application of this is representing a set family by a DAG.
For such a representation each source is a variable in the universe and each sink is a set in the set family, and a element u is in a set S if and only if there is a path from the vertex representing u to the vertex representing the set S.

Is this problem well known?
Is there a polynomial algorithm for this problem?


texts:
Let $H$ be an almost universal hash family of functions from $D^2$ to $D$. For any functions $f,g \in H$ define the function $\langle f,g \rangle : D^4 \to D$ by $\langle f,g \rangle(a,b,c,d) \triangleq f(a,g(b,f(c,d)))$.

  Is the family $H' \triangleq \{\langle f,g \rangle : f,g \in H\}$ almost universal?
  If not, what conditions on $H$ would make $H'$ almost universal?

Note that if we instead defined $\langle f,g \rangle(a,b,c,d) \triangleq g(f(a,b),f(c,d))$, $H'$ would be almost universal. This was defined in Wegman and Carter's "New hash functions and their use in authentication and set equality", and it is sometimes called "tree hash".

The scheme in which $\langle f,g \rangle(a,b,c,d) \triangleq f(a,g(b,f(c,d)))$ is a variation on one in Shoup's "A composition theorem for universal one-way hash functions". Shoup proves that $H'$ is a family of Universal One-Way Hash Functions if $H$ is a family of Universal One-Way Hash Functions. However, I do not believe the proof works to show that $H'$ is almost universal if $H$ also is.

One advantage of Shoup's scheme over Carter and Wegman's is that Shoup's functions can be evaluated with room for only one temporary value from $D$.


texts: Shortest path on a hypergraph with no leftovers

texts:
In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by the code, and each hyperedge would be a set of parity checks a particular physical error flips. If you construct the graph correctly, paths between certain nodes will correspond to logical errors and the code distance will correspond to a shortest path because the shortest path corresponds to the minimum number of errors.
So that's the motivation for being interested in the shortest path problem on a hypergraph.

I did some preliminary searching for existing algorithms that solve this problem. Unfortunately, it seems that existing research is actually referring to a slightly different problem than what I had in mind. In particular, existing work seems to be happy to pass through edges that touch unrelated nodes an odd number of times. In the context of a code distance calculation this would be a bad idea, because it would cause parity check violations elsewhere in the graph. The "minimum length path" wouldn't successfully get back into the desired codespace.

The variant of the shortest hyperpath problem that I care about is as follows.
Let $n$ and $m$ be the start and end nodes.
Let $E$ be a set of hyperedges.
$E$ is a hyperpath between $n$ and $m$ if $n$ appears in an odd number of the hyperedges of $E$, $m$ also appears in an odd number of the hyperedges of $E$, and all other nodes appear an even number of times in the hyperedges of $E$.
I want $n$ and $m$ to be the only nodes whose corresponding parity check triggers when the corresponding errors from $E$ are applied.
The goal is to find the hyperpath with the minimum number of hyperedges.

Has there been previous work on this problem? Note that I'm mostly interested in the case where the hyperedge degree is bounded (e.g. the error graph of the surface code typically has no hyperedges with degree larger than 4, even with circuit level noise and two qubit gate errors).


texts: Is berklemap-massey works on extention field

texts:
According to the articles that i read (also wikipedia [1]), they refer that the above algorithm works on finite field $GF(q)$. But I cannot find an evidence that it still works on extension field, i.e: $GF(q^n)$.
It looks like from the algorithm itself that there is no problem, but I rather like an expert opinion.

[1]- https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm#CITEREFReedsSloane1985


texts: Why is the multi-step reduction of semantics reflexive?

texts:
I was reading Programming Languages and Lambda Calculi, which defines the multi-step reduction to be the reflexive-transitive closure of the one-step reduction. (Page 15, $\twoheadrightarrow_r$ is the reflexive-transitive closure of $\rightarrow_r$)

A quick search shows that this idea is widely accepted, for example by courses from Princeton, UPenn, CU, etc. However, I think the transtivity should be enough to capture the intuition of many steps. So why is reflexivity needed?


texts: What formalisms exist to describe the translation of an abstract syntax tree into another formal language?

texts:
I'm looking for a declarative formalism to describe the transformation of an abstract syntax tree generated by the parsing of one formal language into second formal language. An example of a transformation that it would have to describe is to transform following,

type Bool : Type {
    value false : Bool;
    value true : Bool;
};

into the following,

$Bool : Type;$

$Bool = (Unit \lor Unit);$

$true : Bool;$

$true = (inj_0 unit);$

$false : Bool;$

$false = (inj_1 unit);$

The only thing I can think of is defining piecewise-defined recursive function with nodes of the abstract syntax tree of the original language as input. Is there not a more concise way of declaring the transformation?

I've already implemented such transformations straightforwardly and compositionally in the programming language Haskell but I'm not doing so well on formalising the tranformation.

Also, to be clear I am not talking about attaching semantic actions t the original grammar (or an attribute grammar) because I assume an abstract syntax tree has already been generated by parsing the first formal language because other analysis and rewriting needs to be done on such a tree.

Note that I have no interest in algorithmic efficiency of such a formalism, I only want to show that a injective function from the original formal language to the second formal language exists.

I know I must have read about this in the formal language literature but I can't think of anything specific. I've probably forgotten something really obvious...

Edit:

What about natural deduction style? How could such translations be represented in natural deduction? I'll have to think about that...


texts: What is "Synthetic Network" in Network Science?

texts: I checked out several articles, books available, but didn't find what exactly is a "synthetic network".


texts:
I have an infinite collection of positive integers $n_1,n_2,n_3,\ldots$ and I would like to find the density of the numbers divisible by one or more of these.* If the density does not exist, the algorithm can do anything (it's a promise problem).

If the numbers were pairwise coprime, this would simply be
$$
1-\prod_{i=1}^\infty1-\frac{1}{n_i}
$$
which can be approximated with partial products (and an integral for the omitted terms, if they're sufficiently well-behaved).

In the general case this doesn't work, but you can always take the terms $n_1,\ldots,n_k$, take their least common multiple $L$, and check each number $1,2,\ldots,L$ to see how many are divisible by one of the $k$ chosen numbers. But this becomes unwieldy quickly: with $n_i=i^2$ and $k=10$ the sum is about 6 million (taking maybe a second to compute), but with $k=20$ it's 50 quadrillion (taking hundreds of years).

Is this problem known? Is there a good way to approximate this number?

* The density of a subset $S$ of the positive integers
$$
\lim_{n\to\infty}\frac{|\{1,2,\ldots,n\}\cap S|}{n},
$$
that is, the expected fraction of numbers in the set as you look at larger and larger initial intervals. Sometimes this doesn't exist ("numbers starting with 1") but in this case we're promised that it does.

Here's an example of a simplification we can make to the problem. If one of the $n_i$ is prime, then you can

Remove all $n_j$ which are multiples of $n_i$, including $n_i$ itself.
Compute the new density $D_\text{new}$.
The density is $D = 1 - (1-D_\text{old})(1-1/n_i).$

This can be generalized to composite $n_i$ if all terms are either divisible by $n_i$ or else coprime to $n_i$.

This expands the size we can approach with the naive lcm algorithm, but it doesn't fundamentally alter it.


texts: I was reading a paper about implementing the statistical programming language R on the JVM, and encountered this notation I haven't seen before (I'm not formally CS-trained). What is the name of notational style? I've seen it before in other papers--usually as it related to functional programming and the REPL.


texts: parallelizable fast matrix in-place transposition

texts:
what is the current state of the art in fast and parallel matrix in-place transposition?

I would be very happy, if I could be given some pseudocode for this problem. As far as I could find papers, they do not include very detailed descriptions.

Thanks!

PS:
Of course, we do not restrict to square matrices, but rather arbitrary rectangular matrices. Their memory layout is usually a linear sequence of entries in the memory (say, as in C) and it is a highly non-trivial task to convert this data block in-place/in-situ to the sequence that corresponds to the transposed matrix.

Some information can be found in this wikipedia article, whose references I did not find to be very helpful though: Wikipedia Entry.


texts: Relationship between sparsity and rank of a boolean function

texts:
I have the following question when I was going through the proof of the following theorem.

Theorem. For XOR function $f \circ XOR$, $rank(M_{f \circ XOR}) = ||\hat f ||_0$ where $M_{f \circ XOR}$ is a matrix such that $M_{f \circ XOR}(x,y) = f(x + y)$.

The proof of this theorem essentially shows that fourier coefficients of $f$ are the eigen values of $M$: $\hat f(S)$ is an eigen value and the corresponding eigen vector is $\chi_S$. And now, using spectral decomposition, one can conclude that the rank is equal to the sparsity.

My question is: Consider any function $F:\{0,1\}^N \rightarrow \{0,1\}$, and let $M_F \in \{0,1\}^{N/2} \times \{0,1\}^{N/2}$ be a $2^{N/2} \times 2^{N/2}$ dimensional matrix whose entries are as follows:
$$M_F(x,y) = F(xy).$$
Is there any relationship between $||\hat F||_0$ and $rank(M_F)$?


texts: Does having unique normal forms imply weak normalization and confluence?

texts:
Consider a term rewriting system $\mathcal{R} = (\Sigma, R)$ over a signature $\Sigma$ with basic rewrite rules $R$. If $\mathcal{R}$ is weakly normalizing and confluent, then we know that each $\Sigma$-term has a unique normal form (with respect to $\mathcal{R}$). Is the converse also true? I.e. if each term has a unique normal form with respect to $\mathcal{R}$, then does it follow that $\mathcal{R}$ is weakly normalizing and confluent? Obviously if each term has a unique normal form, then the system is weakly normalizing, so it remains to ask whether it will be confluent.

In short, I am wondering whether the property of a term rewriting system to be weakly normalizing and confluent is strictly stronger than the property of each term having a unique normal form (with respect to the system).


texts: Is the MapReduce framework a type of BSP?

texts: Is it accurate to call the mapReduce framework a type of bulk synchronous parallel programming framework with no local memory retention within processors between synchronizations? If not, what parallel programming model most accurately encapsulates the mapReduce framework?


texts:
Given a submodular function $f$ on $\Omega=X_1\cup X_2$ where $X_1$ and $X_2$ are disjoint and $f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$. Here $f_1$ and $f_2$ are submodular on $X_1$ and $X_2$ respectively.

Here $X_1,X_2,f_1,f_2$ are unknown and only a value query access to $f$ is given. Then is there a polytime algorithm which finds $X_1$. If there are multiple choices for $X_1$ any of them should be fine.

Some thoughts. If we can find any two elements $t_1,t_2$ such that both either belong to $X_1$ or belong to $X_2$ then we can merge them and proceed recursively. But it is not clear how to implement such a step.


texts: What kind of mathematical background is needed for complexity theory?

texts:
I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are considered helpful for TCS, especially (classical) complexity theory.

What fields do you consider essential for someone that wants to study complexity theory? Do you know of any good textbooks covering these fields and if yes, please include their difficulty level (introductory,graduate etc.).

If you consider a field that is not heavily used in complexity theory but you consider it critical for TCS, please also refer it.


texts: Is there a name for a hashtable with a tree for each bin instead of a list?

texts:
It is well-known that the worst case performance for a chaining hashtable, is O(n), where n is the number of objects in the table. The normal assumption is that the hash is either uniform, or secure, however this is not always the case.

One possible solution to this problem would be to use a tree, or other O($\log n$) data structure, instead of the list. This would result in the worst-case performance of O($\log n$) for insertion and retrieval, at the expense of adding an extra constraint on the import data, namely that it would need to be comparable.

Is there a name for such a data structure?


texts: Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?

texts: Greedy is a non-formal term, but it could be (not sure, that's why I'm asking) that for certain problems, greediness can be mathematically formulated and thus be proven that no optimal greedy algorithm exist. Is this possible?