texts: Can an efficiently computable non-one way permutation be written as the composition of polynomially many easy to compute involutions?

texts:
Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ where if $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijection where both $f$ and $f^{-1}$ are computable by circuits with at most $p(n)$ gates, then there exists involutions $\iota_{1},\dots,\iota_{k}:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ where
$$f=\iota_{k}\circ\dots\circ\iota_{1}$$
 and where each $\iota_{i}$ is computable by a circuit with at most $q(n)$ gates and where $k\leq q(n)$.


texts: Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is the single reason they are called perfect? Or is it just a aesthetic preference by Berge?


texts: Reduction between functions that preserves time and space-complexity

texts:
Under which reduction(s) is the class $\mathsf{FTISP}(t(n), s(n))$ closed?

Let $\mathsf{FTISP}(t(n), s(n))$ the class of functions from $\{0,1\}^*$ to itself that are computable by a Turing machine in time $O(t(n))$ and space $O(s(n))$. (This is the analog of the class of decision problems $\mathsf{TISP}(t(n), s(n))$.) Classical reductions such as polytime (Karp) reduction or logspace reduction only preserve either time or space, but not both. Therefore my question is whether there exists some known notion of reduction under which $\mathsf{TISP}(t(n), s(n))$ is closed.

Notes.

There may be several answers for different range of time and space bounds. I am mainly interested in fine-grained reductions (that is where $t(n)$ and $s(n)$ are precise bounds), but also for unions like $t(n) = \mathsf{poly(n)}$ or $s(n) = \mathsf{polylog(n)}$ for instance.
For the space bound, I am mostly interested in the case $s(n) \le n$ (or even $s(n)\ll n$).
I am also interested in reductions for the classes of decision-problems $\mathsf{TISP}(t(n), s(n))$ if they have been studied.
Of course, my requirements are enough to characterize the reduction I want. My question is really whether this kind of reduction has been studied in the literature, and to have pointers in such case. My impression is that the simultaneous time and space bounds imply that the reduction is necessary an oracle reduction. Indeed, it seems out of question to have a many-one reduction: If we take the input $x$ of a problem $A$ and compute an input $y$ to a problem $B$, the composition of the reduction with the algorithm for $B$ has no reason to run in time $t(n)$ and space $s(n)$: Either we compute $y$ before applying the algorithm for $B$ but the space may be larger than $s(n)$, or we compute the bits of $y$ when needed but the time increases... At least, this is not possible for fine-grained complexity bounds.

Remark. The space-complexity of an algorithm computing a function can be defined using multi-tape Turing machines: The machine has a read-only input tape, a write-once output tape, and a finite number of work tapes; The space complexity is the number of cells of the work tapes that are used during the computation.


texts: Is there an algorithm to find whether 2 combinators form a Turing-complete system?

texts: It is known that K = (λx.(λy.x)) and S = (λx.(λy.(λz.((x z) (y z))))) define a turing complete system, and we know procedures to map back and forth from lambda calculus to SK calculus. Now, given two arbitrary combinators, A and B in the set of valid lambda terms, is there an algorithm that will answer whether those combinators define a turing-complete system, and what is the corresponding mapping between a lambda term and those combinators? If not, is there such an algorithm with additional restrictions on the shape of A and B (say, its depth), that could be effectively used to find systems that are similar to SK?


texts: Non-trivial PCP characterizations of complexity classes beyond ELEMENTARY?

texts:
There are interesting results of the form $PCP[a(n), b(n)] = \texttt{SOMECLASS(n)}$ for multiple classes in the exponential hierarchy: the most famous one is probably $PCP[O(log(n)), O(1)] = NP$.

Are there similar theorems for larger complexity classes, such as PR, $F_\omega$, and other beyond ELEMENTARY?  Do these theorems cover the complexity classes implied by proof assistants that only accept total functions?


texts: What is the name of this algorithm on direct acyclic graph?

texts:
I am trying to linearize the history of a git branch for display purpose. I want commits to be collocated by branch instead of simply displaying commits in the order given by the time of commit.

In this graph problem, there is a start node and an final node and in between there is a direct acyclic graph (DAG). It looks like the following:

One possible solution is the following:

a0 a b d1 x2 x1 d2 d3 c3 c1 e c2 f z1 z2 z3 g h i j k

It walks the graph upward, consuming both branches of merge commmits. It moves to the next branch, when it meets a vertex that has several outgoings vertices - a source vertex like b and d1. A source vertices is added to the result list when all it children are already in the result list.

Here is a proof of concept implementation in scheme:

(define (linearize graph start)
  (let loop ((todos (list start))
             (out '()))
    (pk 'todos todos)
    (if (null? todos)
        out
        (let ((todo (car todos))
              (rest (cdr todos)))
          (let ((incomings (ref-incomings graph todo)))
            (case (length incomings)
              ((0) (loop '() (cons todo out)))
              ((1) (if (null? rest)
                       (loop (reverse incomings) (cons todo out))
                       (if (eq? (length (ref-outgoings graph (car incomings))) 1)
                           (loop (append incomings rest) (cons todo out))
                           (loop rest (cons todo out)))))
              (else (loop (append (reverse incomings) rest) (cons todo out)))))))))

What is the name of this algorithm?


texts: What is the maximal load of a "latency-bounded" Cuckoo Hash?

texts:
Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time.

They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is the set of keys, and $[n]=\{1,\ldots,n\}$ are indices of the array in which we store the data.

Whenever we wish to insert a key $k$, we first check if there is either $h_1(k)$ or $h_2(k)$ are free. Otherwise, we insert it into $h_2(k)$ by replacing the key $k'$ that was stored there. If $h_1(k')$ is free then we're done, otherwise, we replace the key that is there $k''$ which then looks for $h_2(k'')$ and so forth.

This operation may fail if there is a loop of keys trying to evict each other.

It is known that if the load of the hash table is at most half (i.e., we don't insert more than $n/2$ keys), with high probability all operations succeed.

I'm interested in the load I can use without making more than $T$ evictions for some $T\in\mathbb N$.

Clearly, smaller $T$ will allow smaller load. For example, if $T=0$ (no eviction permitted), then we cannot load more than $O(\sqrt n)$ elements without getting a colision.

  How many elements can we insert for larger $T$ so that we succeed, say, with probability 9/10?


texts:
Consider this problem: Given a list of finite sets, find an ordering $s_1, s_2, s_3, \ldots$ that minimizes $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$.

Are there known algorithms for this? What is its complexity? I haven't been able to think of an efficient optimal algorithm yet, but it's not obviously in NP-Hard either.


texts:
If we have a machine which can solve any problem in the second level of PH,
can this machine solve optimization problems which is generalized version of NP-complete problems such as MAX-CLIQUE or MIN-COLORING ?

I think that the answer is yes and that the power of this machine is strictly powerful than the one for solving the optimization version.  However, I am not sure the differences between decision class and function class,i.e, PH is a class of decision problems but optimization problems are not.


texts: What is the most intuitive dependent type theory I could learn?

texts:
I am interested in getting a really solid grasp on dependent typing. I've read most of TaPL and read (if not fully absorbed) 'Dependent Types' in ATTaPL. I've also read and skimmed a bunch of articles on dependent typing.

Many type theory discussions seem to focus on adding incremental features to previous type systems, not "what's the next large generalization up from type system X?". Dependent types seem to be the next large generalization from System F, but I have yet to find the intuitive, canonical dependently typed language. The many references to Calculus of (inductive) Constructions makes me think CoC is that language, but the explanations of the language I have seen don't seem very clear or intuitive to me.

I am expecting/guessing such a language would have features like: (and please let me know if anything in particular jumps out as confused or unrealistic)

Generalized abstraction (can have functions from any domain in the type hierarchy to other, kind -> term, term->type''' etc.)
Has an infinite hierarchy of typing (terms : types : types' : types'' : ...)
A minimum number of basic elements. I am imagining that the language only asserts a single element for each level. For example it might assert that (() : Unit : Type : Type' : ...). Other elements are built from these elements.
Sum and product types are derivable.

I am also looking for an explanation of that language which ideally would discuss:

The relationship between abstraction and quantification in that language. If they are not unified, then explain why they are not unified.
The infinite type hierarchy explicitly

I am asking this question because I want to learn dependent type theory but also because I want to put together a guide that, assuming a little CS background, teaches the use of and how to understand proof assistants and dependently typed languages.

(Cross posted to Reddit)


texts: Known algorithms to go from a DFA to a regular expression

texts:
I was wondering whether there is a ``better'' (I will explain in what sense) algorithm to start from a DFA $\mathcal{A}$ and construct a regular expression $r$ such that $L(\mathcal{A})=L(r)$, than the one in the book by Hopcroft and Ullman (1979). In there, the sets $R_{ij}^k$ are used to represent sets of strings that take the DFA from state $q_i$ to $q_j$ without going through any state numbered higher than $k$. This construction, although obviously correct and very useful, is rather technical.

I'm writing a monograph about algebraic automata theory and I don't want to distract my audience with too many technical details (at least not with details that are irrelevant for the results I want to show), but I do want to include a proof of the equivalence between DFA and regular expressions for the sake of completeness. For the record, I'm using Glushkov automata to go from a regular expression to a DFA. It seemed more intuitive than $\varepsilon$-transitions, which I didn't define at all (again, because I don't need them).

What other algorithms are known to go from a DFA to a regular expression? I value simplicity over efficiency (that's ``better'' for me in this case), but that is not a requirement.

Thanks in advance for your help!


texts: Difference between infinite state machines and turing machines

texts:
Finite state machines (FSM) are strictly less powerful than turing machines (TM).  But this is not the case with infinite state machines (ISM).  For example, every TM can be embedded into some ISM.  The opposite (that for every ISM there exists a TM that can be embedded within the ISM), however, is not true.  We can construct a counterexample from any FSM by adding an infinite number of states and no transitions.

I have two questions:

Are all ISMs equivalent to either a FSM or TM?  (For example, does there exist an ISM that can recognize a context-free grammar, but nothing more powerful?)
Is there an algorithm for determining how powerful an ISM is?

EDIT: If such an algorithm doesn't exist, are there any reasonable heuristics or rules of thumb?


texts: Models of random graphs, for real computer networks

texts:
I am interested in models of random graphs which are similar to the graphs of real computer networks. I am not sure if the common well-studied $G(n,p)$ model ($n$ vertices, each possible edge is selected with probability $p$) is good for studying real computer networks (is it?).

  what models of random graphs are useful for understanding computer networks araising in practice?

More generally, what other models of finite random graphs (other than those equivalent to the $G(n,p)$ model) have been studied in the literature? (An ideal answer would be a pointer to a survey for studied models of finite random graphs.)


texts: Math talk: Theorem about git revision control system?

texts:
I would like to give a mathematics talk on the git revision control system. It is now widely used in mathematics as well as in the computer science industry.  For example, the HoTT (Homotopy Type Theory) community uses it, and it is the go to system for collaborative editing of text files, whether they be source code or latex markup.

I know git uses the notion of a directed acyclic graph, which is a start.  However, a good mathematics talk mentions proofs and theorems.

What theorem might I prove about git that is actually relevant for its use?


texts: Cook reduction for search problems, by universal property?

texts:
A search problem is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ solves $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be reasonable if for all $(x,y)\in R$ the word $x$ is at least as long as $y$.

Let $R$ and $S$ be reasonable search problems. Consider the following two properties.

There is a Cook-reduction from $R$ to $S$ (That is, there is a polynomial-time oracle Turing machine $M$ such that for all $f$ solving $S$, the function $M^f$ solves $R$. This is Definition 3.1 of Goldreich's "P, NP, and NP-Completeness: The Basics of Computational Complexity".)
For all functions $f$ such that $S\in\mathsf{FP}^f$, we have $R\in\mathsf{FP}^f$. (Here $\mathsf{FP}^f$ is the set of search problems solved by $M^f$ for some polynomial-time oracle Turing machine $M$.)

Clearly (1.) implies (2.). Also, if $S$ solves itself (i.e. $S$ is a function) then (2.) implies (1.) because we can take the oracle in (2.) to be $S$ itself to obtain an appropriate $M$. Does (2.) imply (1.) in general? I'd guess the answer is no, but I can't think of a counterexample.


texts: Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons

texts:
Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons?

Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem, but the average case suffices for a randomized algorithm with expected $\mathrm{lg}(n!)+o(n)$ comparisons for every input.  The significance of $\mathrm{lg}(n!)+o(n)$ is that it is $o(n)$ comparisons from optimal, wasting an average of only $o(1)$ comparisons per element.

Since I already have such an algorithm, I am including it as an answer (using Q/A format), but I welcome additional answers, including other algorithms, whether such an algorithm was already known, improving $o(n)$, and worst-case $\mathrm{lg}(n!)+o(n)$.

Prior work:
Merge sort uses $\mathrm{lg}(n!)+ Θ(n)$ comparisons (even in the worst case).
Merge-insertion sort (also known as Ford–Johnson sort) also uses $\mathrm{lg}(n!)+ Θ(n)$ comparisons but with a much smaller constant in $Θ(n)$.
Improved Average Complexity for Comparison-Based Sorting (by Kazuo Iwama and Junichi Teruyama) — their (1,2)Insertion algorithm resembles a portion of my answer below.


texts: Does the existence of an RP-complete language imply P = RP?

texts:
(I'm not sure if this is research-level, but I couldn't find an answer to this question elsewhere)
The question of whether there exists an RP-complete language seems to be open, but I guess we believe that there exists one (because we believe that P = RP). In other words, P = RP implies that there exists an RP-complete language. Is the converse known to be true/false?


texts: Graph-based backjumping vs Conflict-based backjumping comparison in CSP

texts:
Graph-based backjumping vs Conflict-based backjumping in CSP
I have been studying techniques to find solutions in backtracking to model and solve a problem in c++ with this methods and I have the following questions:

In which cases is it optimal to use Graph-based backjumping (GBJ)?
In which cases is it optimal to use Conflict-based backjumping (CBJ)?
If I use fordward checking(FC) + GBJ in which cases is it more optimal than fordward checking + GBJ ?
Which of the two methods (GBJ, CBJ) generates a smaller search tree?
What conditions must the constraint graph have in order for GBJ and CBJ to be sub-optimal (similar to backtracking)?

I've been looking at artificial intelligence a modern approach 2nd edition book, but it didn't help me much. I would appreciate it if you could help me to clarify these doubts


texts: Dependences imposed on Subset Sum Problem

texts:
Given a set of $n$ positive integer variables, namely $S=\{ s_1, s_2, \cdots, s_n\}$. Find a subset $A \subseteq S$, so that $\Sigma_{s_i \in A} s_i = K$. $K$ is a given parameter.

Unlike the usual one, there is a dependence constraint set here, $D=\{ (a_1, b_1), \cdots, (a_m, b_m) \}$. Here $(a_i, b_i)$ means $a_i \in A$ implies $b_i \in A$. Furthermore, the dependence is not circular. Put another way, if we represent $D$ as a directed graph $G'(V, E)$, that nodes in $G$ corresponds to variable in $S$ and $(a,b) \in D$ iff $(a,b) \in E$, then $G$ is a DAG (acyclic digraph).

Note: Pseudo-polynomial time in terms of $\Sigma_{s \in S} s$ is acceptable for my problem.

I have proved this problem as strongly NP-complete via a reduction from CLIQUE.

  Question. I am looking forward to an algorithm that finds a subset $A$ so that $\Sigma_{s_i \in A} s_i$ lies in a neighbourhood of $K$, e.g., between $(1-\alpha)*K$ and $(1+\alpha)*K$.

Thank you very much for your comment and answer. :) Any reference concerning is welcome.

Special case solved: When each variable is implied by at most one another variable, i.e., $\forall_{b \in S}$, $|\{(a,b) \in D \}| \le 1$, it could be solved by DP in $O(n*M*M)$. $M=\Sigma_{s_i \in S} s_i$.


texts: Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$?

texts:
We got an argument that 3-coloring bounded degree graphs is subexponential
with complexity $O(\exp{(\sqrt{n}\log^2{n})})$.

The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$
and 3-coloring it is $O(\exp{\sqrt{n}})$ as shown here p. 8 of the pdf.

This paper gives reduction from 3-coloring to 3-coloring planar graph
and the main idea is replace each edge crossing with a small gadget,
which preserves colorability.

If for a bounded degree graph we can find drawing with $o(n^2)$ crossings,
we get subexponential algorithm for 3-coloring it.

According to second paper for bounded
degree graphs, we get approximation with $O(n\log^4{n})$ crossings.

After we have found drawing with few crossings, we planarize using the
gadget. The resulting graph is bounded degree and planar
and on $n+ C n\log^4{n}$ vertices.

  Q1 Is this result correct?

To our knowledge edge coloring 3-regular graph is exponential.


texts: Finding the smallest-cost way to deliver goods

texts:
I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each supplier. In particular, each supplier ("source") specifies a minimum and maximum quantity of the product that should be taken from them (i.e. the "minimum" indicates that we must purchase at least that amount, whereas the "maximum" indicates that we must take no more than that amount). So the sum of the minimums is less than the sum of the total product we must provide, and the sum of the total product we must provide is less than the sum of the maximums.
My manager tells me that they have computer code that can solve the capacitated minimum spanning tree problem (see: https://en.wikipedia.org/wiki/Capacitated_minimum_spanning_tree). Using this as a oracle, how can you determine a method to determine which supplier(s) should deliver their products to which destination(s) at a lowest total cost (or explain why it can't be used to solve the problem)? I'm provided with the costs $c_{i, j}$ of transporting from source $i$ to destination $j$, and I'm also provided with the minimum and maximum quantities of product to be taken from each supplier.

This is a practice problem that I encountered while studying NP completeness and reductions.
I know that I need to somehow construct a graph to pass into the blackbox but coming up with the graph is the tricky part. I thought about constructing a graph with all of the $c_{i, j}'s$ as edge weights, but then I can't get the maximum and minimum quantities to come into play. I've thought about this problem for a while now, but I still can't figure it out. Does anyone have any suggestions? This reduction seems a lot more complicated than the other ones I've seen, or maybe I'm just overthinking it?


texts: Is there any efficient Network stable sort (not bubble sort)?

texts:
Ok, I realize Bitonic sort is not stable and any attempt to make it stable is inefficient, or is there some efficient way?
But is there some other network sort which is indeed stable beside bubble sort which is O(N*N)?
Stability definition could be found at https://en.wikipedia.org/wiki/Sorting_algorithm as:
Stable sort algorithms sort repeated elements in the same order that they appear in the input
The key of making any sort as stable is also there as:
Unstable sorting algorithms can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, so that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original input list as a tie-breaker
For Bitonic sort it would be:
if ((a[i].data == a[j].data) &&
    (((ASCENDING == true) &&
    (((!dir) && a[i].index < a[j].index) || (dir && a[i].index > a[j].index)))
    ||
    (((ASCENDING == false) &&
        (((!dir) && a[i].index > a[j].index) || (dir && a[i].index < a[j].index))))))
{
    exchange(a, i, j);
}

When:
a[].data is your data, a[].index is your indices and dir=true for Ascending order
and exchange is the exchange function

But this is not so efficient way especially if you have input indices besides the sorted data, which is not in linear order and then you need to perform Gather after Sort


texts: Number of reachable vertices in DAG for every vertex

texts: Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running dfs from every vertex and this will take $O(|V||E|)$ time. Is there a better way to solve this problem?


texts:
I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such:
$p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)$,
which is of degree $n$.

But how could I show, what seems obvious, that if $p$ is a polynomial that represents the OR function exactly (so $\forall x \in \{0,1\}^n : p(x) = \bigvee_{i = 1}^n x_i$), then $\deg(p) \ge n$?


texts:
Does Spectral Gap remains same after removal of some edges from a Expander Graph ?

Suppose we take a d-regular graph and remove m edges from it. For a $d$-regular graph We have $\lambda_1 = d$ and $\lambda_2 \leq (1-\epsilon)d $. After removing $m >=0 $ edges, will we have the same spectral gap i.e. $|\lambda_1 - \lambda_2|$ .


texts: What is the smallest deterministic construction of an ordered perfect hashing family?

texts:
A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$.

There are known (deterministic) builds of such family of size $O(e^{k+log^2k}log n)$, while there is a $\Omega(e^k \cdot \frac{log n}{\sqrt k})$ lower bound , which is almost tight.

I'm looking at a slight variation of this, and require that for every (ordered) sequence $X=<x_1,x_2,...,x_k>$ such that $\forall i\neq j:x_i\in [n],x_i\neq x_j$, there exists some $h_S$ such that $\forall i\in [k]: h(x_i)=i$.

Showing a small (of size $O(k^{k+1} \log n)$) family exists is quite simple:

The probability that such random $h$ satisfies the condition for $X$ is $k^{-k}$, and there are $\frac{n!}{(n-k)!}$ such vectors, so if I pick a random set of $r$ functions the chance that any $X$ was left uncovered is at most (union bound)

$$ (1-k^{-k})^r\frac{n!}{(n-k)!} < (1-k^{-k})^r\cdot n^k < n^ke^{rk^{-k}}$$

Now we can demand that the probability will be strictly smaller than 1 (which means that family of size $r$ exists), we get:
$$r > k^{k+1}\text{log}n$$

What is the smallest ordered perfect hashing family we can build deterministically?


texts: Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?

texts:
I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ worst-case slowdown. Is there a definitive reference I can cite? In my case I am working on a purely-functional data structure and I use Standard ML, if these details matter.

And perhaps this question would be even more relevant when applied to data structures specified in, say, Java? Maybe there is some relevant discussions in algorithms/data structure textbooks that use Java? (I know Sedgewick has a Java version, but I have access to the C version only.)


texts: The complexity of tensor formula evaluation problem over an infinite field

texts:
In the paper The complexity of tensor calculus by C. Damm, M. Holzer and P. McKenzie (link), the authors reduced the problem of computing the permanent of 0/1-matrices to that of evaluating tensor formulae over $ \mathbb{N} $, i.e., the semiring of natural numbers including zero. With that, the authors reached the conclusion that "For any infinite field $ \mathbb{F} $, $ \operatorname{val}_{\mathbb{F}} $ is #P-hard under polytime Turing reductions." by claiming that "$ \mathbb{N} $ is embedded in every infinite field." (See Corollary 10 in the original paper)
My question is exactly about the last sentence. Don't there exist cases where an infinite field has a finite characteristic? Or is there any way to prove Corollary 10 without following this line of reasoning?


texts:
It is a well-known fact that $ \mathsf{NL} = \cup_{k>0} \mathsf{2NFA[k]} $, where $ \mathsf{2NFA[k]} $ is the class of languages recognized by two-way nondeterministic finite automata with $ k>0 $ input heads, shortly 2nfa(k).

I have two but similar questions:

Is there any known language in $ \mathsf{NL} $ requiring super-linear time, where the model is a standard space-bounded NTM having a read-only input tape and a read/write work tape?

Is there any known language recognized by some 2nfa(k) in super-linear time but not recognized by any 2nfa(k) in linear time?


texts:
I am studying the BSS model of computation recently (cf. for instance Complexity and Real Computation; Blum, Cucker, Shub, Smale.)

For reals $R$, it is shown that, given a system of polynomials $f_1,\cdots, f_m\in R[x_1, \cdots, x_n]$, the existence of zeros is $NP_R$-complete. However, I am wondering, if those $f$'s are polynomials only have integer coefficients, i.e., $f_1,\cdots, f_m\in Z[x_1, \cdots, x_n]$, is still the problem $NP_R$-hard? (it is obviously in $NP_R$).

I suspect yes, but is there a simple proof?


texts: Minimum Weight Ordering of nodes on a directed graph

texts:
I'm bumping my head against the wall trying to prove this problem is NP-complete (it might not be)

Let $G = (V,E)$ be a directed graph with weights $w:E \to \mathbb{R_{\geq 0}}$ on the edges.

The goal is to find a an ordering $\sigma(1),...,\sigma(|V|)$ of $V$ such that the sum of  weights of ``forward edges''
$\sum_{(\sigma(i),\sigma(j)) \in E, i < j} w(\sigma(i),\sigma(j))$
is minimized.

Is this problem NP-complete, or am I missing an obvious algorithm?


texts: What is a commutative transitive closure operator?

texts: When reading about descriptive complexity theory, I have read about a "commutative transitive closure operator". I understand transitive closure operators, but what is a commutative transitive closure operator?


texts: Counting reduction maintaining the length of the witness for #Knapsack

texts:
I want to know if there is counting reduction (weakly or strongly parsimonious) maintaining the length of the witness between two variations of $\#Knapsack$ problem. Let me define the problems first in decision version.

$Knapsack_{1} :$
$S_1$ is a set of $n_1$ items as follows $S_1 = \{a_1, a_2, \ldots,a_{n_1}\}$. $f : a_i\to \mathbb{N}$ is a function mapping each variable to some natural number. Two other integers $k$ $\leq$ $n_1$ and $B$ are given. $Question:$ Is there a subset $S^{'} \subseteq S_1$, $|S^'|= k$ such that $\Sigma_{z \in S^'}$ $f(z)$ $\leq$ $B$ $?$

Here the witness length is the number of bits required to represent $S^'$.

$Knapsack_{2} :$
$S_2$ is a set of $n_2$ items as follows $S_2 = \{b_1, b_2, \ldots,b_{n_2}\}$. $f : b_i\to \mathbb{N}$ is a function mapping each variable to some natural number. Another integer $C$ is given.
$Question:$ Is there a binary string $x$ of length $n_2$ $( x = x_1x_2\ldots x_{n_2}$, $x_i \in \{0,1\} )$ such that $\Sigma_{i=1}^{n_2}$ $f(b_i)x_i$ $\leq$ $C$ $?$

Here the witness length is the number of bits required to represent $x$.

The way problems are defined, both the decision versions are actually solvable in polynomial time. But I am interested in counting version (i.e. the number of witnesses) and I think counting versions are $\#P$-complete. If we consider the length of the witness, for $Knapsack_1$ problem, it is $k.log(n_1)$. For $Knapsack_2$ length of the witness is $n_2$.

Now my question is, is it possible to find a counting reduction (weakly or strongly parsimonious) from $\#Knapsack_1$ to $\#Knapsack_2$ so that the length of the witness of the reduced problem instance is at most polynomially bounded to the length of the witness of the original problem instance $?$ I think in the opposite direction it is easy, just by taking $S_1 = S_2$. But for $\#Knapsack_1$ to $\#Knapsack_2$, it won't work as $n_2$ may not be polynomially bounded to $k.log(n_1)$ for any arbitrary $k$ if $n_1 = n_2$. Or can we show that it is not possible to find any such reduction unless some complexity theoretic assumption fails ? Any thoughts/references ?


texts: Automated proving that a program doesn't halt

texts:
If you are a computer and you are given a program $P$ (with no input parameter) that doesn't halt, how would you try proving it doesn't halt ?  (here proving means convincing ourselves that it is true)
I guess most people would say to translate the statement " $P$ doesn't halt " into an arithmetic sentence $\forall n, S(n) \ne 0$ (where $S(n+1) = P(S(n))$ is the $n$-th state of the program) and enumerate the theorems of PA until it proves the sentence.  Or is there a more elegant way ?
Ie. how would you try (and success in) solving the halting problem, except in a few pathological cases  ?
Then I'd like to get some intuition on how to visualize (and solve) those pathological cases arising from undecidable problems (in PA). Is there a way to solve them (except in a $\scriptstyle\text{fewer}$ pathological cases) using a new routine enumerating the theorems of a meta-theory (which one) ?
Finally, is it hard to write the concrete code of all this, will it be readable and useful for teaching and for the intuition ?

Concretely I'm asking if this is the algorithm I'm supposed to think to, in that case can I find the concrete code of it somewhere :

Input : a program $P$ with no arguments. Let $ S(n+1) = P(S(n))$ be its sequence of states.
Compute $S(n),n=1,2,\ldots$. If for some $n ,S(n)=0$ then output "$P$ halts".
In the same time enumerate the parenthesized and annotated sentences of PA, where the annotation indicates which inference rules to apply, thus it is trivial to check if a given sentence is a valid theorem of PA and if it proves $\forall n, S(n+1) = P(S(n)) \land S(n) \ne 0$, in that case output "$P$ doesn't halt".
The other cases ($P$ doesn't halt but PA doesn't prove it) are said pathological.


texts: Select circle with given radius that contains most points

texts:
Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points.

I tried solving it by taking each pair of points and if it is possible, generate the two circles that pass trough those two points and have radius r.

Here I found 2 possible circles that have points a and b on their perimeter with radius 2. One circle contains most points so that would be the solution of this problem.

However, I am not sure that this works. One easy counter example is when we have only one point. No pairs can be generated so no circles can be generated. In my code, I just added a circle for every point in addition to my circle generating nonsense from before. But that also fails to give me the correct result.

How do I really go about solving this?


texts: Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time

texts:
Recently I've begun considering how one could generate and solve an $n \times n\times n$ Rubik's cube for $n$ well over 10,000. To solve such a cube is feasible; easily implementable parallelizable algorithms to solve such large cubes can be created with the methods listed here:

link 1

link 2

Such can be executed in $O(n^2)$ time, considering that they rely on short sequences of moves that only displace a couple of cubes, and do not have to compute individual rotations. But scrambling is another story. Given that a randomly executed move takes time $\Omega(n)$ and the diameter of the graph of the group of Rubik's cubes is $\Theta(n^2/\log n)$, a naive scramble would take $\Omega(n^3/ \log n)$, which is not at all feasible. Given that, is there an algorithm for scrambling large Rubik's cubes which:

Takes $O(n^{2+\epsilon})$ time
Produces every possible reachable configuration with positive probability, and only produces such configurations
Is not extremely skewed


texts: Are there any continuous-time stochastic processes in which transition probabilities are discontinuous functions over time?

texts:
In stochastic processes, like homogeneous Markov processes, Poisson processes, Queueing systems etc., the functions that represent (transition) probabilities are continuous over time. This is also very convenient mathematically, since it allows further useful analysis to be done, such as transition rates in Markov processes.

I recently read a paper ( https://arxiv.org/abs/1811.07401 ) where a stochastic process is described, with probabilities being discontinuous at an infinite (!!) number of points. According to the paper, it shows the problematic nature of a certain class of algorithms with which the process is associated.

Are there any continuous-time stochastic processes with discontinuous transition probabilities or is it fundamentally incompatible with mathematical/physical reality?? I would like an answer for stochastic processes describing real phenomena/systems, not for theoretically/artificially constructed processes.


texts: Lynch's Distributed Algorithms book is a classic but it is from 1996 and rather out of date. Are there any recent distributed computing books that can be used as textbooks for a graduate distributed computing and algorithms course?


texts: Applications of solvability in the λ-calculus

texts:
What are applications of solvability / unsolvability, and of operational characterizations of solvability?

Solvability
In the (untyped pure call-by-name) $\lambda$-calculus, a closed term is said to be solvable if there is a head context $H=\lambda x_1.\dots.\lambda x_p.\square u_1\dots u_q$ such that $H[t]\to ^* I$ (where $I$ is the identity $\lambda x.x$), and unsolvable otherwise.
I am aware of two applications of solvability:

When encoding partial recursive functions in the $\lambda$-calculus, sending arguments for which the function is not defined to unsolvable terms helps with compositionality (On Undefined and Meaningless in Lambda Definability, Fer-Jan de Vries)

When studying observational / contextual equivalence of $\lambda$-terms, unsolvable terms are one of the equivalence classes. In some cases, the observational equivalence can be generalized to an observational preorder, and the set of unsolvable terms is then the minimal equivalence class [1]. Solvability therefore appears often when building models, e.g. with Böhm trees.

Is solvability useful in other contexts?
[1] This may clash with some definition of solvability in the call-by-value and / or weak / lazy $\lambda$-calculus, where people sometimes define "unsolvability of order $n$". In these settings, "unsolvable" should be understood as meaning "unsolvable of order 0".

Operational characterization of solvability
A reduction $\rightharpoonup$ is said to operationally characterize a set $X$ of $\lambda$-terms when the set of weakly normalizing terms with respect to $\rightharpoonup$ is exactly $X$, and it is "nice" (for some random definition of "nice" that makes it non-trivial to get an operational characterization of solvability, e.g. deterministic and computable).
In the untyped pure call-by-name $\lambda$-calculus, the head reduction operationally characterizes solvability.
I am aware of the following two (potential) applications of the operational characterization:

The head reduction is useful to define Böhm trees;

If one has two calculi, each with a definition of solvability, proving that a translation preservers solvability is easy: one just needs to extend the translation to (head) contexts, and ensure that the identity is translated to the identity (or something that can be mapped to it by some head context in the target). Proving that it preserves unsolvability, however, is much harder since the target may have more contexts, and so having no context that works in the source does not imply that no context works in the target. If one has an operational characterization of solvability in both calculi, proving the translation preserves unsolvability can be reduced to proving that it respects the reduction that operationally characterizes solvability. This can probably sometimes be extended in some way to prove that observational equivalence is preserved. (I do not have a reference for this application, so a reference for this would be welcome)

Are operational characterizations of solvability useful in other contexts?


texts: Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?


texts: Is the 3-sphere recognition problem NP-complete?

texts:
It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere
is in NP, via work by
Saul Schleimer in 2004: "Sphere recognition lies in NP"
arXiv:math/0407047v1 [math.GT].
I am wondering if this has been established to be NP-complete in the last five or six years?
Analogous problems, such as the 3-manifold knot genus problem, have been shown NP-complete.


texts: Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit

texts:
I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-MOD_3)$ circuit. They claim what follows:

  It was known that the $OR$ function of $n$
  variables, i.e., $\vee_{i=1}^n x_i$
  , can be
  computed by a depth two $(MOD_3-MOD_2)$ circuit.

I agree with the above part and I am able to show a construction for $n$-ary $OR$. Based on this fact they note that:

  This implies that every disjunction of $n$
  literals, i.e., $\vee_{i=1}^n l_i$
  where $l_i\in \{x_i,\overline{x_i}\}$
  ,
  also can be computed by a depth two $(MOD_3-MOD_2)$ circuit.

Which I also accept. Afterward, they set up grounds for the main proof:

  Let $f$ be an arbitrary Boolean function on $n$
  variables. Consider a CNF formula representing
  $f$, where each clause contains exactly $n$
  literals. Without loss of generality, we
  can assume that the formula has $m\equiv 1(\mod 3)$ clauses.

So far so good. But then comes the part I get lost at:

  If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$
  clauses of $f$ takes value $1$, and if the value of $f$
  is $1$, then all of the $m\equiv 0(\mod 3)$ clauses takes value $1$. Thus the $MOD_3$ gate, whose inputs are all $(MOD_3-MOD_2)$
  circuit computing each clause in the CNF formula, evaluates the func-
  tion $f$

Could anyone please explain to me why the sentence

  If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$
  clauses of $f$ takes value $1$

is true? Isn't it possible for a CNF with $m$ clauses to evaluate to $0$ and have $m-2$ clauses true? Or $m-3$ or $m-113$. What if, for example, my CNF is a big $AND$ of $n$ variables? Then this doesn't hold, any number of clauses might be 'dead'...

(Note this is not the whole proof, you have to show how to transform this bigger circuit to a smaller one).


texts: Is the feasible region of this SDP polyhedral?

texts:
We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral?

We believe this to be true since the 'circular' portion of the cone of semidefinite matrices is due to the extreme rank-$1$ matrices. Any 'curved' boundary of the feasible region must occur from an infinite number of extreme rays.

As a consequence, can we claim that this SDP can be solved exactly in polynomial time just like linear programs which too have a polyhedral feasible region?


texts: How can DES have 6x4 S-Boxes and still be reversible?

texts: Wouldn't data be lost when mapping 6-bit values to 4-bit values in DES's S-Boxes? If so, how can we reverse it so the correct output appears?


texts:
I'm reading the book Introduction to Algorithms (Cormel et al., 2009) on the chapter about multithreaded algorithms, and I'm confused about the following:

  We must also account for the overhead of recursive spawning when analyzing the
  span of a parallel-loop construct. Since the depth of recursive calling is logarithmic in the number of iterations, for a parallel loop with $n$ iterations in which the $i$th iteration has span $iter_{\infty}(i)$, the span is $$T_\infty(n)=\Theta(\lg n)+\max_{1\leq i\leq n}iter_\infty(i).$$

I agree that if there are a fixed number of processor, say $2$, then the depth is indeed $\log n$. But what if there are a huge number of processors, so that it can handle even large values of $n$? Wouldn't the depth of recursive calling be $\Theta(1)$ in that case?


texts: Fractional but not integer multi-commodity minimum cost flow

texts:
I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar question but it considers an undirected graph or to be precise I don't catch Andreas Björklund's last comment.

Can anyone help? Thank you in advance!


texts: Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)

texts:
I am looking for an implementation of an algorithm to compute the pathwidth of a graph. It is well known that computing the pathwidth is equivalent to computing the node searching number, vertex separation number, or interval thickness of the graph. The algorithm does not have to be very fast; I want to run it on graphs of at most 20 vertices. I do require the algorithm to compute the pathwidth exactly, rather than giving an approximation.

I am aware that there are some implementations to compute the treewidth of a graph (a related concept) but have not been able to find any to compute the pathwidth. Any pointers are appreciated!


texts: Standard Name for a vertex removal like operation

texts:
I have an operation that looks a lot like vertex removal, and I'm wondering if there's a standard name for it. Given a graph $G$ we remove a vertex $v$, but instead of removing the edges that were incident on $v$, we "re-route" them by connecting all incoming and outgoing edge pairs. Specifically, if $-$ is normal vertex deletion and we're trying to define $\ominus$, then
$$G \ominus v \equiv G - v + \{ uw | uv \in G \land vw \in G\}.$$
Is there any standard name for this operation?


texts: Can concurrency models be compared in terms of some metrics?

texts:
In Seven Concurrency Models in Seven Weeks by Butcher, it compares Actor Model and Communicating Sequential Processes (CSP):

CSP is more flexible than actor model:
In actor model, the medium of communication is tightly coupled to the unit of execution: each actor has precisely one mailbox;
In CSP, channels are first class and can be independently created, written to, read from, and passed between tasks.

Nothing stops  CSP  from  supporting distribution  and  fault  tolerance,  but historically  CSP  has not had  the  same  level  of  focus  and  support  of the two as actor model does.

Both actor model and CSP do not directly support parallelism. Parallelism has to be created based on concurrency building blocks.

I was wondering if the two concurrency models can be compared in terms of some metrics (some measurement, quantities, ...) in aspects either mentioned above or not. (Butcher's book doesn't mention such metrics. I also tried  but haven't found it in Varela's Programming Distributed Computing Systems.)
If concurrency models can not be compared in metrics, how can they be compared?
I am looking for some metrics to fit into the comparison between the concurrency models. Also for books, papers and articles for comparing them.
Thanks.


texts: Counting quotient graphs, but not exactly

texts:
All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$-valuation of $G$ is a mapping $\nu: V \to [k]$. Given a $k$-valuation $\nu$ of $G=(V,E)$, I define the graph $\nu(G)=(V_\nu,E_\nu)$ by $V_\nu = \{\nu(v) \mid v \in V\}$ and $E_\nu = \{(\nu(v),\nu(v')) \mid (v,v') \in E\}$. I am interested in the following counting problem:

  INPUT: a directed graph $G=(V,E)$, and integer $k \in \mathbb{N}_{\geq 1}$.

  OUTPUT: $|\mathrm{Span}_k(G)|$, where $\mathrm{Span}_k(G) = \{\nu(G) \mid \nu:V \to [k]\}$.

In other words, I want to count the number of distinct graphs that can be obtained from $G$ by a $k$-valuation of $G$.

My question: has this problem already been studied? What is its complexity?

Small example

Let $G=(V,E)$ be the triangle graph, i.e., $V=\{a,b,c\}$ and $E = \{(a,b),(b,c),(c,a)\}$, and let $k=2$. Then $\mathrm{Span}_k(G)$ contains $4$ graphs:

$G_1 = \{V_1,E_1\}$ where $V_1 = \{1\}$ and $E_1 = \{(1,1)\}$;
$G_2 = \{V_2,E_2\}$ where $V_2 = \{2\}$ and $E_2 = \{(2,2)\}$;
$G_3 = \{V_3,E_3\}$ where $V_3 = \{1,2\}$ and $E_3 = \{(1,2),(2,2),(2,1)\}$;
$G_4 = \{V_4,E_4\}$ where $V_4 = \{1,2\}$ and $E_4 = \{(2,1),(1,1),(1,2)\}$.

So the output should be $4$. Note that, although $G_1$ and $G_2$ (and $G_3$ and $G_4$) are isomorphic, they are still counted as different.

Preliminary observations

It seems to be a variant of counting the number of quotient graphs of $G$, but I don't see an obvious reduction. Also, I have not found any work on counting the quotient graphs.
My problem is in the class Span-P, which is the class of counting problems that can be defined as the number of distinct outputs of a nondeterministic Turing machine running in polynomial time. This class was introduced in Köbler, J., Schöning, U., & Torán, J. (1989). On counting and approximation. Acta Informatica, 26(4), 363-379. Indeed, a machine can just guess a $k$-valuation $\nu$, and then write the graph $\nu(G)$ (in the right order). Ideally I would like to show that it is Span-P complete. For the hardness part, if it helps I don't mind considering the version of the problem where edges can be labeled with a fixed, finite alphabet.
Since it is in Span-P, according to this same paper (Theorem 7.2) this problem can be approximated in polynomial time, but using an oracle to NP. Can we get rid of the oracle to show that the problem has a FPRAS?
Is it in #P? It doesn't seem so, but I don't see a simple #P-harness proof either...
If we define $\mathrm{SurjSpan}_k(G)$ to be just like $\mathrm{Span}_k(G)$ but restricted to $k$-valuations that are surjective, then clearly we have $|\mathrm{Span}_k(G)| = \sum_{i=1}^k \binom{k}{i} |\mathrm{SurjSpan}_i(G)|$. So the problems of counting $|\mathrm{SurjSpan}_k(G)|$ and $|\mathrm{Span}_k(G)|$ are reducible to each other (using Turing reductions here).


texts: Bitcoin and preventing double spending in decentralized digital currencies

texts:
A recent approach to creating a decentralized online currency, called Bitcoin, has been generating some interest. The goal is to have a way to transfer currency without a central authority and without double spending or counterfeiting. Their approach is to have all the nodes in the network try to verify a transaction by doing a proof-of-work computation and then the transactions with the most verification are considered official. If an attacker wants to forge the official record (to reverse their first spending and use the coin again), then they must have the majority of the computing power in the network. The biggest downside is that in this scheme, the record of all transactions must be public, which the author assumes is a must:

The only way to confirm the absence of a transaction is to be aware of all transactions. In the mint based model, the mint was aware of all transactions and decided which arrived first.  To accomplish this without a trusted party, transactions must be publicly announced

Is it obvious that all transactions must be publicly known in any such scheme? More broadly: is there any cstheory/crypto research on decentralized digital currencies or related ideas?
Notes
I cross-posted to crypto.SE after a meta discussion.


texts: Where does the "intuitive" understanding of Kolmogorov complexity fails

texts:
Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia.

So to give this more formal meaning, define
$$
 K'(x) := |f| + |a_1| + \ldots |a_k|
$$
where $f(s_1, s_2,\ldots, s_k)$ is some function with $k$ arguments in some specific programming language (like C++ for example).

How does this definition relates to Kolmogorov complexity? I mean this could not be the same, as with this definition we have
$$
 K'(xy) \le K'(x) + K'(y) + C
$$
with some constant $C$. For if $f(a_1, \ldots, a_k) = x$ and $g(b_1,\ldots, b_l) = y$ are functions to compute $x$ and $y$, then

  h() {
   return concat(f(a1, ..., ak), g(b1,...,bl));
  }

would be a function to compute $xy$ of complexity $|f| + |a1| + \ldots + |ak| + |g| + |b1| + \ldots |bl| + C$, where $C$ represents the bits needed to declare $h$, the parentheses, the return statement and to call concat (string concatentation function).

Hence $K'(xy) \le K'(x) + K'(y) + C$.

But as is well-know for the usual Kolmogorov complexity we do not have such an subadditivity?

EDIT: This will also work if we just allow functions with a single parameter.


texts: What are some theory problems in Information Retrieval and Search Engines which are not yet solved or can be bettered?

texts: I'm interested in IR and Search Engines and want to work on a theory problem in this space. Most thoughts that I get are focused towards implementation and would like to explore something not solved or can be bettered instead of implementing


texts: On the goal of learned clause database reduction in CDCL SAT solvers

texts:
Modern SAT solvers frequently reduce the size of their learned clause database in order to keep its size as manageable as possible. This has as effect not to slow down the speed of unit propagations.

I think that in addition to keep reasonable the size of the learned clause database, the reduction also helps to improve diversification which increases the chance of the solver to rapidly find a solution for satisfiable formulas. I also think that restarts don't help enough to increase diversification in the solver since upon restart all learned clauses are kept as well as variable activities and polarities. For myself these information contribute to redirect the search in the same search space.

can the reduction of the learned clause database in CDCL SAT solvers be seen as a way to increase diversification ?
By diversification, I mean a reasonable coverage of the search space.


texts: Explaining computer science algorithms/concepts/ideas using metaphors

texts:
Recently I found an interesting algorithm book entitled 'Explaining Algorithms Using Metaphors' (Google books) by Michal Forišek and Monika Steinová. "Good" metaphors help people understand and even visualize the abstract concepts and ideas behind algorithms.

For example,

  One well-known exposition of the shortest path using the balls-and-strings model
  looks as follows: To find the shortest path between $s$ and $t$, one just grabs the corresponding two balls and tries to pull them apart.

My question:

  I would like to see as many metaphors as possible for computer science algorithms/concepts/ideas.
  Do you know any? Do you have your own ones?


texts: Minimizing Automata accepting $\omega$-words (i.e. infinite words)

texts: What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" of the states which are accepted are the same, will not work. For example consider the Büchi-Automoton accepting all words with an infinite number of a's consisting of two states,  a initial and a final state, and the final state is entered each time an a is read, and the initial state is entered each time a different symbol is read. Both states are considered equal by the above defintion, but collapsing them yields an automata consisting of a single state, and thereby accepting every words.


texts: dynamic algorithms for the subset-sum problem hold for vectors?

texts:
I have a vector (er, array) that is the sum of a number of other known vectors. I would like to reverse the process and find the specific known vectors that were summed to make the final vector. The problem appears to be similar to the subset-sum problem. I see some algorithms for the subset sum problem on the internet. However, it's not clear if they would work for my scenario.

Do you have any suggested algorithms for this problem? Can someone help me write the problem in summation notation? Can you see some way of grouping the vectors out of the solution set for a branch and bound algorithm approach?

I've attempted to solve the problem with a matrix multiply; details here: https://math.stackexchange.com/questions/516208/minimize-ax-b-where-x-is-a-binary-vector

I've attempted to solve the problem with genetic algorithms. I'm no longer a believer in evolution. Details here: https://stackoverflow.com/questions/17297313/genetic-algorithms-name-the-piece-that-drives-the-mutation-location

(The known vectors are smaller than the final result, but I can fake a full length through an approach of "known vectors at all possible offsets". My numbers all range between -1 and 1. It seems I could add 1 to make them all positive.)


texts:
The "name the biggest number game" asks two players to write down a number secretly, and the winner is the person who wrote down the larger number. The game commonly allows players to write down functions evaluated at a point, so $2^{2^{2^{2}}}$ would also be an acceptable thing to write down.

The value of the Busy Beaver function, $BB(x)$, cannot be determined (in ZFC, or any reasonable consistent axiomatic system) for large values of $x$. In particular, $BB(10^4)$ cannot be determined as per this paper. However, this doesn't mean that we cannot compare values of the Busy Beaver function. For example, we can prove that $BB(x)$ is strictly monotonic.

Lets suppose that we allow players to write down expressions involving compositions of elementary functions, natural numbers, and the Busy Beaver function. Are there two expressions that the two players can write down such we can prove in ZFC that determining the winner in ZFC is impossible (assuming ZFC is consistent)?

EDIT: Originally this question said “... arbitrary combinations of computable functions, natural numbers, and the Busy Beaver function.”

If we let $f(x)$ take on the value of $3$ if $BB(x) >$ [something ungodly large and inexpressible on this website] and $7$ if it’s not, then $f(10^4)$ and $6$ are incomparable.

This doesn’t satisfy me, largely because $f$ isn’t a reasonable function for someone to use in this game. I don’t see how to phrase my intuition about this though, so I’ve restricted the question to avoid piecewise functions.


texts: Parsimonious Reduction from Unique-3SAT to NAE-3SAT

texts:
Using the result by Valiant and Vazirani, we know that Unique-3SAT (3SAT with a unique solution) is hard unless NP=RP. Also it is widely believed that the "Unique" version of any NP-complete problem admits the same result comment after Theorem 2.1.

However, there are NP-complete problems whose instances admit only zero or more than one feasible solutions. Consider, NAE-3SAT where in each feasible solution, each clause must have at least one true and at least one false literal. Thus, by definition, the complement (make true to false and false to true for all variables) of any feasible assignment is also feasible. Thus this problem can have zero or more than one solutions.

Is it possible, to find a parsimonious reduction from Unique-3SAT to Unique-NAE-3SAT? How do you preserve the number of solutions in such a reduction? If there is no such reduction, then is not the widely believed statement as mentioned above is false?


texts: Multicuts (or multiway cuts) for 3 Terminals of Minimum Capacity

texts:
For each fixed $k \geq 3$, the following well-known problem is NP-complete.

k-Multicut (aka "Multiway Cut", "k-Way Cut", "Multicut")

Input: $(N,l)$ where $N=(V,E,T,c)$ is an undirected $k$-terminal network with nodes $V$, edges $E$, terminals $T \subseteq V$ with $|T|=k$, a capacity function $c$ and a positive integer $l$.
Question: Is there set $E' \subseteq E$ that separates each pair of terminals from each other such that $\sum_{e \in E'} c(e) \leq l$?

I only consider $k=3$ from now on, so let the set of terminals be $T = \{t_1,t_2,t_3\}$. The minimum conceivable capacity possible for a multicut in a given 3-terminal network $N$ is $\frac{c_1+c_2+c_3}{2}$, where $c_i$ is the capacity of a min-cut separating $t_i$ from the other two terminals in $N$. I wonder what the complexity is to decide whether a given network allows a multicut of this minimum capacity.

Formally, I would like to know the complexity of:

Minimum 3-Multicut

Input: A 3-terminal network $N$.
Question: Is $\left(N,\frac{c_1+c_2+c_3}{2}\right) \in \textrm{3-Multicut}$?

While this problem clearly is in NP, it is not clear whether this problem is in P since each single terminal can be separated from the other two terminals by up to exponentially in $|V|$ many min-cuts. On the other side, a promising candidate for a reduction to show NP-hardness is k-Multicut. However, it is not clear how such a reduction might work.


texts: Constant time Lookup for Inversion Problem

texts:
I'm trying to figure out how to compute all the significant inversions $(i,j)$
in a list $l = [a_1, \ldots a_n]$ where an inversion $(i,j)$ is significant if $i < j$ but $a_i > 2a_j$. Now there is a recursive algorithm running in $O(n \log n)$ for computing normal inversions. The task is to modify this algorithm to only count significant inversions. The step I need to accomplish this is the following fact:
given a sorted list $L$, and a value $b_j$, I want to count the number of elements $l \in L, s.t. l > b_j$. Note since $l$ is sorted, this is equivalent to finding the index of the smallest $l$ such that $l > b_j$. My question is theoretically can $l$ be stored in a data structure so that this determination is $O(1)$?


texts:
Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it. C(x) contains all edges on all paths from a node 0 ( C(0) = {} ). Each edge can be in a set at most once!

You can also describe this data structure by the rules for its growth:

Start with node 0 with associated empty set C(0) = {} = creating new object
For any node x create a new node y where (x,y) is oriented edge from x to y and C(y) = C(x) union { (x,y) } = versioning and branching
For any nodes f and t, create node r, where (f,r) and (t,r) are oriented edges and C(r) = C(f) union C(t) union { (f,r), (t,r) } = merging

Note: You can see there is no mathematical difference between creating new version and a branch. It is a semantical difference depending on whether there is already an edge leading from the node or not.

Base node is defined as a node b, such as C(b) = C(f) intersect C(t), where f and t are nodes representing two versions to be merged.

Simple Merge equation Result=To + (From-Base) = means that if we subtract every edge in C(b) from C(f) and add all edges in C(t) we get a resulting C(r) minus (f,r) and (t,r) edges exactly. No edge would appear twice and all edges in C(f) and C(t) would be represented. = 3-way merge

Complex merge equation Result = To + Sum(i=1..n) for (Fi-Bi), where Fn = From. Each edge can be in exactly one of the sets To, (Fi-Bi). For n=1 this turns into a simple merge equation. In case there exist no base in simple case, we might find sequence of F,B nodes to fit the complex equation. (1+2n)-way merge

I have actually several questions pertaining to this data structure. I am posing the first 3 for "frame of mind", as I already know the answers. And I believe question 4 directly leads to answering question 5, which I really try to get answered.

  Prove there can be no circles in the graph
  Prove that for certain graphs there are such nodes F,T for which base cannot be found as specified in simple equation.
  Create algorithm to find B in simple case where n = 1.
  Prove that for each RTG and each pair of nodes F and T, there is a set of n pairs of nodes Fi,Bi, where i=1..n to fit the complex merge equation.
  Create algorithm to find minimum n and Fi,Bi for i=1..n where n > 1.


texts: Calculating exact/approximate solution to a formula

texts:
Suppose we have a set of variable $\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions $g_i(y_i), 1 \leq i \leq n$. Note that $g_i()$ is dependent only on $y_i$.

Consider the program:
$$
\sum_{\mathbf{y} \in C} \prod_{i=1}^n g_i(y_i)
$$
Where $C$ is the feasible space for $\mathbf{y}$. The question is how to find this equation(or an approximation to it) efficiently?

Note that naively computing this is $m^n$ (assuming that each $y_i$ can take $m$ possible values, although some of these combinations might not lie in the feasible space $\mathcal{C}$). To make it more clear consider the following example:
$$
\begin{cases}
\sum_{(y_1, y_2) \in C} g_1(y_1) g_2(y_2)  \\
\mathcal{C}: y_1 + y_2 \leq 1 \\
y_1 \in \lbrace 0, 1 \rbrace \\
y_2 \in \lbrace 0, 1 \rbrace
\end{cases}
$$

You can make the following assumptions (but not limited to):

$\mathcal{C}$ is be represented with a linear constraint:
$$
A\mathbf{y} \leq b
 $$
$g_i(y_i)$ is bounded above with some number $M$.
g_i(y_i) is a convex/super-convex function
Or any other necessary assumption that can help to solve or approximate this.

Update1: It might be useful to know that
$$
\ln \sum_{\mathbf{y} \in C} \frac{ \prod_{i=1}^n g_i(y_i) } { |C| } \leq  \frac{1}{|C|} \sum_{\mathbf{y} \in C} \ln  \prod_{i=1}^n g_i(y_i) = \frac{1}{|C|} \sum_{\mathbf{y} \in C}   \sum_{i=1}^n \ln  g_i(y_i)
$$


texts:
What is the time complexity of computing betweenness centrality if we are given the shortest path predecessor matrix of a graph?

Predecessor matrix cells look like this:

If node $i$ and node $j$ are directly connected then the value in the cell is $0$;
if node $i$ and node $j$ are not connected then value in the cell is $-1$;
else the cell contains $\operatorname{predecessor}(j)$ (this can be only one predecessor if there is a single shortest path or an array of predecessors if there are more than one shortest paths between $i$ and $j$).


texts:
It seems that Goemans and Williamson give a unique representation for each graph of the semidefinite relaxation (elements $y_{ij}$ of Y). However, semidefinite programming may give the same maximum value of the objective function for different matrices Y, if I am correct. This means that you may get up to more than one unique representation in n dimensions of a graph. Can somebody tell me if this is correct please?

PS: the Cholesky decomposition we do, gives a unique set of n vectors after finding Y, however I believe that Y is not necessarily unique, so you may get many different sets of vectors $v_{ij}$.


texts: The balls and bins model: bounding the marginal contributions in the m>>n regime

texts:
Consider the standard balls and bins process, where $m$ balls are thrown into $n$ bins, and consider the case where $m >> n$. Denote the load on bin $i$ by the RV $L_i$.

Given a set $S \subseteq [n]$ of size $k$ which does not contain the maximum and minimum load bins, and a threshold $t \in [m]$, a bin $j$ is pivotal to $S$, if $\sum_{i \in S}L_i < t \leq \sum_{i \in S \cup j}L_i$.

For a value $k \in [m-2]$, I want to bound the number of sets of size $k$ for which the maximum load bin is pivotal to, but not the minimum load bin, as a function of $t$.

For $t$ sufficiently bounded away from $\frac{km}{n}$, it is not hard to show that, with high probability, bin $i$ is pivotal to set $S$ iff bin $j \neq i$ is pivotal to $S$, as the difference in the loads of every two bins is $O(\sqrt{\frac{m\log n}{n}})$ (using the Chernoff+union bound)

However, for $t$ very close to $\frac{km}{n}$, the converse seems to be true (i.e., the maximum load bin is pivotal to many more sets $S$).

Now, from this, we know that if $n\log n << m < n\cdot polylog n$, then $L_{max} = \frac{m}{n} + \Theta (\sqrt{\frac{m\log n}{n}})$ w.h.p. By showing that w.h.p. $|L_i - \frac{m}{n}| = O(\sqrt{\frac{m\log n}{n}})$, for all $i=1,\ldots,n$ w.h.p. (using a Chernoff bound), we get that $L_{max} - L_{min} = \Theta(\sqrt{\frac{m\log n}{n}})$ with high probability.

Any ideas on how to lower-bound the number of sets?

The problem is that the loads of the remaining $n-2$ bins cannot be treated as another balls and bins process with $m-L_{min} - L_{max} = m - \frac{2m}{n} - \Theta(\sqrt{\frac{m\log n}{n}})$ balls, as their loads depend on $L_{min}$ and $L_{max}$.


texts: state-of-the-art bit complexity of the determinant

texts:
I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits.
I would like to know what is the state-of-the-art bit-complexity.
As far as I could find, the two possible candidates are:

(1) The low-depth circuits, due to Csansky [1976], and Berkowitz [1984], but these, despite having $log^2(n)$ depth, require some $n^4$ bit operations.

(2) The Bunch and Hopcroft [1974] algorithm, which takes any black-box algorithm for integer matrix multiplication, and produces an algorithm for the determinant using the same $\textbf{arithmetic}$ complexity.  Since any two $M$-bit integers can be multiplied in $M \cdot log^2(M)$ operations, and the largest value during the computation can be as large as $2^{M n}$, it seems that its bit-complexity is $\tilde{O}(M n^{\omega+1})$, where $\omega$ is the state-of-the-art matrix product coefficient $< 2.38$.

Is there a better upper-bound?


texts: When did self-balancing binary search trees become known outside the soviet union?

texts:
According to wikipedia, the AVL tree was first published in 1962 by Soviet scientists Adelson-Velsky and Landis.  The earliest self-balancing binary search tree I can find by a non-soviet block scientist is the red-black tree, created by West German computer scientist Rudolf Bayer in 1972.
My questions are:

Did Bayer and other non-Soviets know about the AVL tree (or any other self-balancing binary search tree) at this point in time?

When did the AVL tree become known to non-Soviet researchers?  And in particular, when was it translated into English?

I can't find copies of the original publications online for these papers, but I'd like to read them for their references.  Can anyone help me find copies?


texts: Finding sets of heavily intersecting objects, while minimizing their size

texts:
Assume I have some array $a$ of length $n$.

If I place the elements contained in the array $a$ into a $\sqrt{n} \times \sqrt{n}$ matrix, then every row "intersects" with every column. That is, I cannot pick a row s.t. it will not intersect with all columns.
In addition, I can "reach" each element in the matrix via a column and via a row vector.
The row/column length is $\sqrt{n}$.

I'm not sure how to state this problem in more general terms or what would be a related field of research. Basically I am trying to find two sets $A$, $B$ of vectors/objects such that it holds that each element from $A$ intersects with all vectors from $B$ and in addition each element from $a$ should appear at least once in each set.

I was wondering whether the objects can be made even smaller by increasing the dimension to something bigger than 2.
For instance, for dimension 3 I could have one set of planes and one set of orthogonal vectors. For these two sets it holds that every element from one set will intersect with every element from the other set. However, when placing the elements from the array $a$ into such a 3 dimensional cube, I would have planes that are composed of $\sqrt[3]{n} \cdot \sqrt[3]{n}$ elements and $\sqrt[3]{n}$ sized vectors. Here, the sum of two objects from these two sets is bigger than in the matrix example.

I would like to minimize the total size of objects, one from each set for a given dimension.
What would be a related field of study to look at? Is dimension 2, i.e., the matrix already the best possible solution? If so, how would I show that?


texts: Bounding the cost of an approximation algorithm when subtraction involve

texts:
Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound $\alpha$ in terms of $\beta$ if
$(n-c) \leq \alpha (n- \beta c)$. That is, what can I say about $\alpha$ in terms of $\beta$ (assuming all positives, and $c < n$).


texts: What applications of Cantor space are there?

texts:
Are there well-established applications of the Cantor space ($2^\omega$) in computer science, other than those connected with computable real arithmetic?

John Tucker's page Computation on Topological Data Types mentions applications of the general area in signal processing, 3d graphics, and semantics of process algebras: have these applications been fruitful?


texts: Smooth Complexity of the Nonnegative Permanent

texts:
There has been fantastic work done on the Permanent going on for the last two decades.I have been wondering for a while about the possibility of a Smooth P algorithm for the Permanent of Nonnegative Matrices. There is of course the famous JSV algorithm but this is a fpras. Thinking about other work within Smoothed Complexity, a strong hint of being in Smoothed P was the existence of a fpras / Psuedopolynomial algorithm.

Are there any obstructions to the Nonnegative Permanent being in Smoothed P?

Thanks in advance

Zelah


texts: Is there a known bound on the size of a BSP tree for a simple polygon?  I am aware of the result by Toth which gives a tight $\Theta(n \log(n) / \log(\log(n)) )$ bound on the size of a BSP consisting of $n$ disjoint segments, but I wonder if it is possible to do better given some of the special properties of simple polygons.  For example, it is trivial to show that convex polygons can be represented by BSP trees using at most $O(n)$ nodes.  Is it possible to represent simple polygons in linear space as well?


texts: Linear time algorithm for finding shifted max

texts:
Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct).

Let $B$ be $A$ sorted in the nonincreasing order.
We want to compute
$$m = \max_{i\in [n]} B[i]+i.$$

The obvious solution is sorting $A$ and then compute $m$. This gives an algorithm that runs in time $O(n \lg n)$ in the worst case.

  Is it possible to do better? Can we compute $m$ in linear time?

My main question is the one above.
But it would be interesting to know about the following generalization of the problem.

Let $B$ be $A$ sorted according to some comparison oracle $\leq$
and $f$ a function given by an oracle.
Given $A$ and oracles for $\leq$ and $f$, what can we say about the time needed to compute $m = \max_{i \in [n]} f(B[i],i)$?

We can still compute $m$ in $O(n \lg n)$ time. But can we prove a super-linear lower-bound for this generalized case?

If the answer is yes does the lower-bound hold if we assume that $\leq$ is the usual order on integers and $f$ is a "nice" function (monotone, polynomial, linear, etc.)?


texts:
Tree decompositions and treewidth are a standard way to measure how close an undirected graph is to a tree. I am studying decompositions of directed acyclic graphs (DAGs), and have come to define them as follows:

Given a DAG $G = (V, E)$, letting $G'$ be the undirected graph obtained by forgetting about edge orientations, a tree decomposition of $G$ is a tree decomposition $T$ of $G'$ as a rooted, directed tree, such that for any bag $b \in T$ and any vertex $v$ of $V$ in $b$, if $v$ occurs in none of the children of $b$, then for any directed edge $(u, v) \in E$, we have $u \in b$. The width of $G$ under this definition is then, as usual, the minimum across all decompositions $T$ of the maximal cardinality of a bag in $T$ minus one.

My general question is: Is such a notion of tree decomposition of a DAG known?

I know that there are existing definitions of tree decompositions for directed graphs, such as D-width, DAG-width, and directed treewidth. However, I don't think they are related to this definition, because, according to all of them, DAGs have low treewidth. Indeed, these definitions consider acyclic graphs as "simple". By contrast my definition only applies to DAGs, and its extension to general directed graphs is not interesting: unless I'm wrong, it implies that all elements of each strongly connected component must co-occur in a bag.

Further, in my case, the width of a DAG may be more than that of the corresponding undirected graph. In fact, a tree decomposition of a DAG $G$ in this sense is a standard tree decomposition of the moral graph of $G$, with additional conditions enforcing it to have a certain "directed" shape. I think the treewidth of the DAG in this sense can still be arbitrarily larger than that of the moral graph, but I'm not sure how to characterize the DAGs that would have "bounded treewidth" in the sense I proposed.

Motivation. In my context, the DAG is a circuit, and I use the tree decomposition to reason about valuations. The property that I require is designed to ensure the following: when processing the tree decomposition bottom-up, when we reach a new bag and we see a new element, we can examine its valuations based on that of its children, which are known because the children must be in the bag: we do not need to guess the valuation (as we would have to if it depended on nodes we haven't seen yet). I suspect that there may also be a relationship to inference in graphical models, where message passing needs to be done in only one direction, but I was unable to find references.


texts: Are there classes where all Eulerian orientations can be listed in polynomial time?

texts:
Is there is a subclass of regular graphs (say 4-regular graphs) for which there is a polynomial time algorithm to list all Eulerian orienations?
An Eulerian orientaiton of an (undirected simple) graph $G$ is an orientation of $G$ such that every vertex has in-degree equal to out-degree. Obviously, a graph must be an even regular graph to admit an Eulerian orientation. Also, one can find an Eulerian orientation of an even regular graph by taking a directed Euler tour and orienting the edges in the direction of the tour.
The problem of counting Eulerian orientations of a 4-regular graph is studied in graph polynomials context [equivalent to evaluating the Tutte polynomial at the point (0, -2)], flow theory (equivalent to counting the number of maximum flows around a network) and in statistical physics (ice-type models). The counting problem is hard (#P-complete), but there are efficent approximation algorithms.
Naturally, listing all Euler orienations is hard. I have a problem which could be solved if we have the list of all Eulerian orienations (there is a one-one map from a set of objects I study to the set of Eulerian orienations of a fixed graph $G$). If it matters, we know that (i) $G$ can be decomposed into cycles of length divisible by three and (ii) $G$ is (diamond,$K_4$)-free.
I wonder whether there is a subclass of regular graphs in which the listing problem is polynomial time solvable. I would expect this class to be small (but it should be non-trivial to be of interest).
Is there a paper that deal with listing Eulerian orientaitons?
Thank you.


texts:
(I tried to ask at SO but maybe this has more to do with the CS theory.)

Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it belongs to, in constant time?

For example:

  |------------------|---------|---------------|
  0.0                4.5       7.853293843     9.123

Given a position:

                                   ^
                                   |
                                   8.005

I would like to get 3rd piece.

It is possible to easily get such answer in O(log n) time with binary search but is it possible to do it in O(1)? If I pre-process the "cut" positions somehow? Perhaps there is a data structure which could help to speed the search up?

PS: Is there a name for such problem? I know "rod cutting" refers to a slightly different problem...


texts: Unique games conjecture - edge permutations

texts: What do the edge permuations in the unique games conjecture represent?


texts:
In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\in\{1,\ldots,n\}$ such that, for some assignment, some $k$ clauses $c_{i1},\ldots,c_{ik}$ are true.

In MAX-MIN-SAT, given two different formulas, we want to maximize the minimum number of satisfied clauses in both.
I.e., given $\phi_a = a_1 \cap \cdots \cap a_n$ and $\phi_b = b_1 \cap \cdots \cap b_n$,  where each $a_i$ and each $b_i$ is a disjunction, find the largest $k$ such that, for some assignment, some $k$ clauses $a_{i1},\ldots,a_{ik}$ and some $k$ clauses $b_{j1},\ldots,b_{jk}$ are true.

To illustrate the difference between the problems, suppose we have two assignments: one assignment satisfies 10 clauses in $\phi_a$ and 1 clause in $\phi_b$, while another assignment satisfies 5 clauses in $\phi_a$ and 4 clauses in $\phi_b$. Then, MAX-SAT (on $\phi_a \cap \phi_b$) would prefer the first assignment since it satisfies $11>9$ clauses overall, while MAX-MIN-SAT would prefer the second assignment since it satisfies at least $4>1$ clauses in both formulas.

This problem is obviously NP-hard, so I am looking for reasonable approximations.

As a first approximation, suppose each formula is a conjunction of $n$ clauses, and each clause is a disjunction of $l$ variables. Suppose we set each variable randomly. Then, each clause is unsatisfied with probability $2^{-l}$. So the expected number of unsatisfied clauses in each formula is $2^{-l}n$. So the expected number of unsatisfied clauses in both formulas is $2^{1-l}n$. So there exists an assignment in which the total number of unsatisfied clauses is at most $2^{1-l}n$. In that assignment, in each formula, at least  $(1-2^{1-l})n$ clauses are satisfied.
So we have a constant-factor $(1-2^{1-l})$ approximation to MAX MIN SAT.

Is there a better approximation?

Posted some weeks ago in cs.SE, with no replies


texts: Chernoff-type inequality for random variable with 3 outcomes

texts:
Suppose we have a random variable which takes non-numeric values a,b,c and want to quantify how empirical distribution of $n$ samples of this variable deviates from true distribution. The following inequality (from Cover & Thomas) applies in this case.

  Theorem 12.4.1 (Sanov's theorem): Let $X_1, X_2, \ldots, X_n$ be i.i.d. $\sim Q(x)$.
  Let $E \subseteq \mathscr{P}$ be a set of probability distributions.
  Then
  $$Q^n(E) = Q^n(E \cap \mathscr{P}_n) \leq (n+1)^{|\mathcal{X}|}2^{-nD(P^*||Q)},$$
  where $$P^* = \arg\min_{P \in E} D(P||Q),$$
  is the distribution in $E$ that is closest to $Q$ in relative entropy.

This inequality is quite loose for small $n$. For binary outcomes, $|\mathcal{X}|=2$, and Chernoff-Hoeffding bound is much tighter.

Is there a similarly tight bound for for $|\mathcal{X}|=3$?


texts: In the context of bond percolation on $\mathbb{Z}^d$ where $d$ is a positive integer, consider the problem of computing a $2^{-k}$-approximation of the critical percolation $p_c$ given a lattice dimension $d\in\mathbb{N}$ and a precision parameter $k\in\mathbb{N}$ as inputs. Are there any known results about the complexity of such problem?


texts: Can we make a matrix stable by changing its upper-left submatrix?

texts:
A matrix $A$ is called strictly stable if its eigenvalues have negative real parts. Given a matrix $A \in \mathbb{R}^{n \times n}$, suppose we can change its upper-left $k \times k$ submatrix at will (i.e., we can change the entries $a_{ij}, 1 \leq i,j \leq k$). Can we make it strictly stable?

Example: if $$A = \begin{pmatrix} 1 & 1 \\ 2 & -1 \end{pmatrix}$$ and we allow ourselves to change the upper-left $1 \times 1$ submatrix (i.e., just the top-left entry) one can verify that the answer is yes. Changing the top left entry to $-3$ we obtain
$$\begin{pmatrix} -3 & 1 \\ 2 & -1 \end{pmatrix}$$ and one can verify that this is indeed strictly stable. On the other hand, if
$$A = \begin{pmatrix} 1 & 1 \\ 2 & 0 \end{pmatrix}$$ then the answer is negative. No matter what we put in the top-left entry, the matrix will not be strictly stable, because its determinant will be negative (which rules out strict stability for $2 \times 2$ matrices).

Question: is there a polynomial-time algorithm to decide on a yes/no answer?

In the case where the matrix $A$ is symmetric, I believe the answer is that the principal submatrix corresponding to the rows and columns $k+1,\ldots,n$ should be negative definite. However, I'm not sure what the answer is if we do not assume $A$ is symmetric.


texts: Lower bound proof for compressive sensing (Gel'fand widths)?

texts:
Let $x \in \mathbb{R}^n$ have $k$ non-zero entries. The main insight of compressive sensing is that there exist $m\times n$ matrices $A$ with $m = O(k \log n/k)$ such that any $x$ can be recovered from $Ax$ in polynomial time.

A little thought shows that $Ax$ must have at least $\log \binom{n}{k} = \Theta(k \log n/k)$ bits. I believe a stronger statement is true as well, namely, that we must have $m =\Omega(k \log n/k)$ measurements as well.

I know the lower bound on $m$ has something to do with Gel'fand widths, but am having a hard time finding a resource that lays out the argument explicitly. Either pointers to write-ups or a rough summary of the argument would be helpful.


texts:
What is the best known complexity for computing the exact edit distance between two strings of the same length using working space which is sublinear in the size of the input?  I assume the input is stored in some read-only format. Is this a previously studied problem?

To make the question a little more specific, how about $\Theta(\sqrt{n})$ space where $n$ is the length of each input string.

Edit. Following the answer of David Eppstein, it seems a good question is simply if the edit distance can be found in polynomial time and $\Theta(\sqrt{n})$ space. Any lower bounds would also be interesting.


texts: As I understand, in computer science data types are not based on set theory because of things like Russell's paradox, but as in real world programming languages we can't express such complex data types as "set that does not contain itself", can we say that in practice type is an infinite set of its members where instance membership is defined by of number of features that are intrinsic to this type/set (existence of certain properties, methods)? If no what would be the counterexample?


texts: Applications of small Kakeya sets over finite fields

texts:
It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$.

For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ as given by Blokhuis and Mazzocca in [1], where they also classified the sets attaining this lower bound. For $q$ even the bound is $q(q+1)/2$ and all Kakeya sets attaining this bound are known. Some more examples of "small" Kakeya sets are given in [2] and [3].

My question is, what are some possible applications of constructing these small Kakeya sets in $\mathbb{F}_q^2$?

Moreover, what is the state of the art for $n > 2$? What are the best known bounds and the examples that achieve those bounds? Would it be worthwhile to construct explicit examples attaining the bounds there? (which is of course subjective)

[1] A. Blokhuis and F. Mazzocca. The finite field kakeya problem. In Building Bridges, pages 205–218, 2008. http://link.springer.com/chapter/10.1007%2F978-3-540-85221-6_6

[2] A. Blokhuis, M. De Boeck, F. Mazzocca, L. Storme. The Kakeya problem: a gap in the spectrum and classification of the smallest examples. Des. Codes Cryptogr., 72 (1) (2014), 21–31.

[3] J. M. Dover and K. E. Mellinger. Small Kakeya sets in non-prime order planes. European J. of Combin.
Volume 47 (2015), pages 95–102.


texts: Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?

texts:
A set is $\mathsf{P}$-immune iff
it has no non-trivial $\mathsf{P}$ subset.

  Is every $\mathsf{coNP}$-complete language $\mathsf{P}$-isomorphic to
  an $\mathsf{P}$-immune $\mathsf{coNP}$-complete language?

Joshua Grochow's answer to my previous questions shows the answer is negative assuming cryptographic conjectures.
Is it possible to show the answer is negative
only assuming  $\mathsf{P}\neq\mathsf{NP}$?

Or show the answer as positive with  additional assumptions.

As @Kaveh points out based upon a P isomorphism assumption (Bertman-Hartmanis conjecture) one only has to show the existence of one such language.


texts: Ways to think formally about Satisfiability Modulo Theories

texts:
Apologies if this is not a well-thought-out question, but I am interested in formalizing a problem which is ultimately described by a SMT formula in the theory of quantified arrays and linear arithmetic, and I realized that, while I understand what SMT formulas are useful for in a practical sense, I do not have a good sense for how to fit what I know about foundations of logic/computing/type theory/category theory with the idea of SMT theories and formulas.  What can be said formally about the general theory about statements which can in some way be turned into SAT instances?

Edit: I understand that SAT solvers work with propositional logic and SMT solvers work with fragments of first-order logic, but how exactly do we understand what a "fragment of logic" is and how it chops up the whole universe of first-order logic?  Obviously we have different predicates and functions for linear arithmetic vs the theory of data types, but how at a formal level can we come up with a mathematical universe in which certain statements can be combined and others can't?


texts: Can a fully homomorphic encryption be used for oblivious code execution?

texts:
After reading this answer a while ago, I took an interest in fully homomorphic encryption. After reading the introduction of Gentry's thesis, I started wondering if his encryption scheme could be used for oblivious code execution as defined in the third paragraph.

In a fully homomorphic encryption scheme we typically encrypt some data, send it to a hostile environment where a certain function is computed on the data, the result of which is then sent back (encrypted), without the adversary finding out what the received data or the result of the function is.

With oblivious code execution I mean that we encrypt a piece of code $C$ designed to solve some problem $P$ and send it to a hostile environment. The adversary wants to use $C$ to solve $P$, but we don't want him to know how $C$ works. If he has an input $I$ for $P$, he can encrypt $I$ and then use (some encryption scheme on) $C$ with $I$, which then returns the (not encrypted) output $O$ (the solution of $P$ for the input $I$). The encryption scheme makes sure the adversary never finds out how the piece of code works, ie to him it works like an oracle does.

The main practical use (I can think of) for such an encryption scheme would be to make piracy more difficult or even impossible.

The reason I think this may be possible using a fully homomorphic encryption scheme is because we can execute arbitrary circuits on encrypted data, in particular an universal Turing machine. We could then encrypt the code as if it were data and then use the circuit for an universal Turing machine on this encrypted data to execute the code.

I pose this as a question here because I don't know whether this idea is usable: I never got much further than the introduction of Gentry's thesis, and my knowledge about cryptography is limited. Also, I don't know if there already is a often-used term for oblivious code execution: I tried searching Google for the idea but not knowing the proper term I found nothing.

There are multiple problems I can think of which may cause problems with this approach. Firstly, if we use a fully homomorphic encryption without modification, the result of the computation ($O$) would be encrypted. It would therefore be useless for the adversary who wishes to use your code to solve $P$. While this could still be useful for, say, cloud computing, this is not what I want to achieve.

Secondly, because we're using circuits and not arbitrary Turing machines, we can't use arbitrary amounts of memory: we're limited to a predetermined amount of memory. This means that if we want to run a program in this way, it's memory footprint will always be the same, namely it's peak memory usage.

Lastly, the constants involved would almost certainly kill off any practical use of such a system, but I think the idea is interesting nonetheless.


texts: How to generalize a map of type for many operators?

texts:
I am formalizing the type system for a small language, and thus writing inference rules.

Taking unary - operator for example, its entry may be a number as well as an array of number, thus there is an overloading: $-^1$ and $-^a$. Two of their typing rules are $-^1: \text{Integer} \rightarrow \text{Integer}$, and $-^a: \text{Integer Array} \rightarrow \text{Integer Array}$.

Actually there are a lot of operators like unary - operator, which can take one element as well as an array of elements as entry. I just don't know how to generalize this formalization.

For instance, when I introduce the typing rules for FACT operator, one of its rule is $\text{FACT}^1: \text{Integer} \rightarrow \text{Integer}$. I just would like to say $\text{FACT}^a$ exists, and follows "the map of type" logic as $-^a$. Does anyone know how to formalize that elegantly?

Going further for arithmetic binary operators, one rule is $\text{+}^1: \text{Integer} \rightarrow \text{Integer} \rightarrow \text{Integer}$, how could I say $\text{+}^a$ exists, and follows "a map of type" logic, which implies naturally that $\text{+}^a: \text{Integer Array} \rightarrow \text{Integer Array} \rightarrow \text{Integer Array}$?


texts: Is there any equivalent for Bondy-Chvátal theorem for directed graphs?

texts: Bondy-Chvátal theorem cannot be applied for directed graphs, is there any equivalent theorem that can be applied for them?


texts: Are there canonical non-relativizing techniques?

texts:
In a lot of domains, there are canonical techniques which everybody working in the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of not constructing the full output of the composed function, but always asking to recompute the result for every bit of output, permitting to keep logspace constraints.

My question is about non-relativizing techniques. Do theoricians have outlined some fundamental non-relativizing operations, or is there a different trick for each known non-relativizing proof ?


texts: Does this problem have a name? Finding a subset intersecting all subsets of a family

texts: I am pretty sure this problem has a name, or it can be reworded so it does. We are given a set $X$ and a family $\mathcal F$ of subsets of $X$, the problem is to find a subset $B$ such that $B\cap A\neq \emptyset$ for all $A\in \mathcal F$.


texts:
Suppose $f$ is a submodular set function on a universe $U$ of size $n$.

For $k \in \{0,\ldots,n\}$, let
$$ F(k) = \operatorname*{\mathbb{E}}_{X \in \binom{U}{k}} f(X), $$
where $\binom{U}{k}$ is the set of all subsets of $U$ of size $k$.

We are interested in proving the following inequality:
$$ F(k) \geq \frac{k}{n} F(n) + \frac{n-k}{n} F(0). $$
One can prove this inequality by induction on $k$ (or even directly, if we're careful), but this doesn't explain why the inequality holds. Instead, we will use some form of term rewriting.

Submodularity directly implies the following inequality, for $k \in \{1,\ldots,n-1\}$:
$$ F(k) \geq \frac{1}{2} F(k+1) + \frac{1}{2} F(k-1). $$
Imagine applying this inequality over and over again, in an arbitrary way. Here is an example for $n = 3$ and $k = 2$:
$$
\begin{align*}
F(2) &\geq
\frac{1}{2} F(3) + \frac{1}{2} F(1) \\ &\geq
\frac{1}{2} F(3) + \frac{1}{4} F(2) + \frac{1}{4} F(0) \\ &\geq
\frac{5}{8} F(3) + \frac{1}{8} F(1) + \frac{1}{4} F(0) \\ &\geq
\frac{5}{8} F(3) + \frac{1}{16} F(2) + \frac{5}{16} F(0) \\ &\geq
\cdots \\ &\geq
\frac{2}{3} F(3) + \frac{1}{3} F(0).
\end{align*}
$$
The dots hide infinitely many steps.

There is a way to make this argument completely rigorous. One can cook up some potential function that increases whenever one applies any instance of submodulary (for example, the expectation of squared cardinality). Taking the consequence of $F(k)$ maximizing this potential, it's easy to see that we get an inequality of the form
$$ F(k) \geq \alpha F(n) + \beta F(0). $$
If $f$ is any modular function then there is equality. Taking $f = 1$ we find that $\alpha + \beta = 1$, and taking $f(X) = |X|$ we determine $\alpha = k/n$.

This argument extends to prove more interesting inequalities on submodular functions.

  Does this sort of reasoning look familiar?


texts: Definition of MSO_1 for graph structures

texts:
What is the proper definition of MSO$_1$?

MSO$_1$ is also called the one-sorted MSO. In contrast, in MSO$_2$, the two-sorted MSO, first order variables and set variables are allowed to be of two sorts -- vertex (set) or edge (set).

Why not define MSO$_1$ as the fragment of MSO without any edge variables or edge set variable? (that is, there is only one sort)

Instead, it is usually defined as the fragment of MSO without edge set quantification [some authors say quantification over sets of edges; it is ambiguous whether quantification over $E(G)$ is allowed]. Most authors explicitly state that quantification over $E(G)$ is allowed. But some authors such as Langer et. al. forbid quantification over $E(G)$ (see quote below).

I think my definition and the definition by Langer are actually same because we can express edge variables by vertex sets instead (eg: $\exists S\ \exists a\ \exists b\ ( a\neq b \wedge \forall c (c\in S\implies c=a \vee c=b) )$. Or am I mistaken?

Details

Here is a quote from Practical algorithms for MSO model-checking on tree-decomposable graphs by Langer et. al. (emphasis mine)

  Every variable $x$, $X$ is said to have a type tp($x$), tp($X$) $\in \{1,2\}$ denoting whether it refers to
  vertices (tp($x$) = 1), edges (tp($x$) = 2), vertex sets (tp($X$) = 1),
  or edge sets (tp($X$) = 2), respectively. The formulas of MSO$_2$ are
  strings that are obtained from finitely many applications of
  the following rules:

  If $x_1$ and $x_2$ are individual variables with tp($x_1$ ) = tp($x_2$ ),
  then $x_1$ = $x_2$ is a formula.
  If $x_1$ , $x_2$ are individual variables with tp($x_1$ ) = tp($x_2$ ) = 1,
  then adj($x_1$ , $x_2$ ) is a formula.
  If $x_1$ , $x_2$ are individual variables with tp($x_1$ ) = 1 and
  tp($x_2$ ) = 2, then inc($x_1$ , $x_2$ ) is a formula.
  If $x$ is an individual variable and $X$ is a set variable with
  tp($x$) = tp($X$), then $x\in X$ is a formula.
  If $\phi$ is a formula then $\neg\phi$ is a formula.
  If $\phi_1, \cdots, \phi_k$ are formulas then $(\phi_1\vee \cdots \vee \phi_k)$ and $(\phi_1\wedge \cdots \wedge \phi_k)$
  are formulas.
  If $\phi$ is a formula and $x$ is an individual variable then $\exists x\phi$ and $\forall x\phi$ are formulas.
  If $\phi$ is a formula and $X$ is a set variable then $\exists X\phi$ and $\forall X\phi$ are formulas.

  If the formulas in 8 use edge set variables (tp($X$) = 2), we
  call this quantification an edge set quantification. .......... MSO without
  quantification over sets of edges, i.e., with quantification over
  sets of vertices only is called MSO$_1$ or one-sorted MSO.