texts: Comparing Shannon-Fano and Shannon coding

texts:
I am interested in a few algorithms for creating prefix codes:

Shannon coding: we take $l_i=\lceil -\log p_i\rceil$.
Shannon-Fano coding: list probabilities in decreasing order and then split them in half at each step to keep the probability on each side balanced. Then codes/lengths come from resulting binary tree.

My question is whether one of these algorithms always provides a better $L=\sum p_i l_i$? In a few examples I've done, Shannon-Fano seems better. Is this always true? Do you have any references or proofs? I realize these aren't the two best algorithms (Huffman coding is optimal). I'm just interested in comparing them.

Edit: Well, no interest so far? I guess this stuff isn't all that exciting, but I'd still like to know. Here's what I've come up with after some more google searching/playing around with numbers.

Practically, Shannon-Fano is often optimal for a small number of symbols with randomly generated probability distributions, or quite close to optimal for a larger number of symbols. I haven't found an example yet where Shannon-Fano is worse than Shannon coding.

In Shannon's original 1948 paper (p17) he gives a construction (equivalent to Shannon coding above) and claims that Fano's construction (Shannon-Fano above) is substantially equivalent, without any real proof. I haven't been able to find a copy of Fano's 1949 technical report to see whether it has any analysis.

Thomas and Cover's Elements of Information Theory says that Fano codes give $L \leq H +2$ and Shannon codes give $L \leq H+1$. However the reference they give for the Fano code analysis I think applies to alphabetical codes where you're not allowed to reorder the probabilities.

Stefan Moser's Information Theory Lecture Notes (pp 50-59) agree with my historical analysis above and purport to prove that for Fano codes we have $l_i \leq \lceil -\log p_i \rceil$ which would be sufficient to prove they are better than Shannon codes. However I don't follow the proof and I think I have a counterexample:

Take probabilities $(0.4, 0.26, 0.02, 0.02, 0.02, \ldots, 0.02)$ (we have 17 0.02's so that probabilities add to 1). Then Shannon coding has lengths $(2,2,6,6,6,\ldots,6)$ while Fano coding splits between 0.4 and 0.26 and then for the 0.6 probability on the right it splits between the second and third 0.02. Continuing on we see that 0.26 is encoded with a length of 3, larger than Shannon length. However, the average length is still less for Fano than for Shannon (according to my program implementing Fano coding).

So, am I doing something wrong? Can you see how to construct a probability distribution to make Shannon code perform better than Fano, or a way to prove it's not possible?


texts:
Recently I have seen several articles on arxiv that refer to a proof system called sum-of-squares.

Can someone explain what is a sum-of-squares proof and why such proofs are important/interesting?

How are they related to other algebraic proof systems? Are they some kind of dual to Lassere?


texts:
Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra:

A quantum-inspired classical algorithm for recommendation systems
Quantum-inspired classical algorithms for principal component analysis and supervised clustering
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
Quantum-inspired sublinear classical algorithms for solving
low-rank linear systems

and for Max 3LIN:

Beating the random assignment on constraint satisfaction problems of bounded degree.

It may be very useful to compile a list of all known classical algorithms inspired from quantum computing. What other examples are known?


texts: What is the space complexity of computing the eigenvectors of a matrix?

texts:
By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to within precision $2^{-n}$ in polylogarithmic space?

We can try to find the eigenvectors from the eigenvalues, but since we only have the eigenvalues up to precision $2^{-n}$, this seems to lead to a host of numerical stability issues (in particular, if there are two nearby eigenvalues, small perturbations in the matrix can lead to large perturbations in the eigenvectors).

Any references are appreciated!


texts:
There are $N$ types of jobs. For each $i$, we have to schedule $T/D_i$ jobs of type $i$ in $T$ timeslots. We know that $\sum_{i=1}^N 1/(D_i+1) = 1$. For each type $i$, the distance between two consecutive jobs of type $i$ should be greater than $D_i$. This is the separation constraint.

Is there any related literature for this scheduling problem? Specifically, what is the hardness of the above scheduling problem?

EDIT: I found that the pinwheel scheduling is similar to this problem where the constraint is type $i$ job appears at least once in every $(D_i+1)$ timeslots with $\sum_{i=1}^N 1/(D_i+1) < 1$. However, a pinwheel schedule does not necessarily satisfy the Separation constraint in this case.


texts: A least sized partition of a set under a distance metric

texts:
What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows:

Input:

A set $S=\{s_1,\ldots,s_n\}$, where the elements $s_i$ are of some type $T$.
A distance metric $D:T\rightarrow [0, \infty)$.
A radius $r:[0, \infty)$

Output: A partition $S_1,\ldots,S_m$ of $S$ such that

$S_i\cap S_j=\emptyset, i\neq j$ and
$S=\cup_{i=1}^m S_i$ and
$D(s,t) \leq r$, $s,t \in S_i$ and
There is no other partition with the same properties of size $m^{\prime} < m$.

NOTE: I am saying "a partition" not "the partition", because there may be multiple partitions of least size for the same set of points.  For example consider $2 n$ points on a large circle where the points are spaced such that each pair of points is distance $r$ apart.  In this case there are $2 n-1$ distinct least-sized partitions of minimum size $n$.

NOTE: The following algorithm will produce a partition with desired properties except that it is not guaranteed to be least size:

$i=1$
While $|S| > 0$:

Choose $e \in S$ and set $S:=S-\{e\}$
$S_i=\{x\in S: D(e,x) \leq r\}$
Set $S:=S \setminus S_i$
Set $i:=i+1$

NOTE: It has been suggested that this is an NP-hard problem, but the above partial solution is $O(n^2)$.

NOTE: This problem is an abstraction of this geographic problem.


texts: Problems that are hard w.r.t UGC-hardness of VERTEX COVER

texts: Are there any problems $P$ such that an $\alpha$-approximation for $P$ (for soem choice of $\alpha$) would imply a better than 2-approximation for VERTEX COVER, which would be hard via the UGC ?


texts: Can a polynomial sized arithmetic ciruits perform integer division?

texts: Can we perform integer division with a polynomial size arithmetic circuit over $\mathbb{Q}$ that takes as input the numerator and denominator?


texts:
TLDR: Is there a notion of Kleene Algebra for star-free regular expressions?

Kleene Algebras are algebraic structures that are equivalent to regular expressions. A Kleene Algebra is an idempotent semiring (non-commutative multiplication) with an extra unary operation $*$ that satisfies that following equations:
\begin{align}
&1+x\cdot x^* = x^* \\ &1+x^*\cdot x = x^* \\ &z+xy\le y \implies x^*\cdot z\le y \\ &z+yx\le y \implies z\cdot x^*\le y
\end{align}
where $x\le y$ means there exists $z$ such that $x+z=y$. Equivalence with regular expressions formally means, given regular expressions $r_1$ and $r_2$, $\mathcal{L}(r_1)=\mathcal{L}(r_2)$ iff we can prove $r_1=r_2$ using the axioms of Kleene Algebra.

Star-free regular expressions are regular expressions without the Kleene star but with the ability to take complements i.e. $$r_1,r_2::= \emptyset\mid a,b,c\in A\mid r_1\cup r_2\mid r_1\cap r_2\mid r_1\cdot r_2\mid (r_1)^c$$ where $A$ is the set of alphabets. Observe that complementation restores some Kleene star powers but not all: $A^*=(\emptyset)^c$ while $(aa)^*$ has no star-free form.

I was wondering how to tweak Kleene Algebra so that we capture exactly star-free expressions. While coming up with equation templates for the complementation operation the challenge is to get an equation for $(r_1\cdot r_2)^c$ because the rest of the interleaving of operations is taken care of by De Morgan's laws. Also, since Kleene Algebras do not explicitly talk about the alphabet set, I guess $a^c$ should be considered a normal form.


texts: Is there a problem which is provably not parallelizable?

texts:
Possible Duplicate:
  Limits to Parallel Computing

A friend just asked me, if for every problem that takes time t on one processor, solving it on two processors will take t/2. Obviously, this is not known in the general case.

Is there a counter examples to this? Meaning, is there a problem that is provably "hard to parallel"?


texts:
In the element distinctness problem, one has query access to an arbitrary multiset of $n$ elements and must decide whether they are all distinct.
From a property testing point of view, the question is:

Given parameter $\varepsilon > 0$ and query access to $f\colon[n] \to [n]$, distinguish with probability $2/3$ between (i) $f$ is a bijection (all elements are distinct), and (ii) $|f([n])| < (1-\varepsilon) n$ (the list has less than $(1-\varepsilon) n$ distinct elements).

This question was first studied in [1], and its query complexity is known to be $\Theta(\sqrt{n/\varepsilon})$ (see also the lecture notes [2,3]).
I am wondering if the following generalization has been studied:

Given parameter $\varepsilon > 0$ and query access to $f\colon[m] \to [n]$ such that $r := \frac{m}{n} \in\mathbb{N}$, distinguish with probability $2/3$ between
(i) $|f^{-1}(\{i\})| = r$ for all $i\in[n]$ , and
(ii) at least $\varepsilon m$ values of $f$ must be changed for it to satisfy (i)

(the element distinctness problem is the specific case $r=1$)

[1] F. Ergün, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan, Spot checkers, Journal of Computer and System Science 60 (2000), 717–751.
[2] P. Beame, Introduction to Sublinear Algorithms (Lecture 1), 2014. https://courses.cs.washington.edu/courses/cse522/14sp/lectures/lect01.pdf
[3] R. Krautgamer, Seminar on Sublinear Time Algorithms (Lecture 5, scribed by Anat Ganor), 2010. http://www.wisdom.weizmann.ac.il/~robi/teaching/2010b-SeminarSublinearAlgs/scribe5.pdf


texts:
What are the known limits of the decidability of the comparison of growth rate of functions from $\mathbb{N} \to \mathbb{N}$? I am here thinking of the decidability of questions like "Is $x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$?" or "Is $2^{\lg^* x} \in O(\lg \lg x)$?".

If we restrict the functions to be polynomials (expressed in the usual manner), then this isn't hard. See also Cantor normal form.

How large can we make the class of functions before comparison becomes undecidable? Can we extend it to the functions used in a typical undergraduate algorithms class?

As Joshua Grochow explains in the comments, I'm interested really in the set of expressions, not the functions themselves. So, for instance, I'd be interested in decision procedures that could compare "$1$" and "$2$", even if they can't compare "$\ln e$" and "$n^{(\ln n)^{-1}}$".

Possibly related question: "Is the theory of asymptotic bounds finitely axiomatizable?"


texts: List of NP-hard problems, where there is active research in practical heuristics

texts:
I am looking for list of NP-hard optimization problems, where there is active research in practical heuristic for solving them and there are common benchmarks, which people try to beat.

Examples include:
Phylogenetic tree reconstruction (heuristic for example here)
Travelling salesman (not so active, but LKH is quite well known)

More specifically, I am looking for areas of research, where people really care about resulting cost (like TSP or phylogeny mentioned above).
E.g. finding decision tree is not a thing I am looking for, since very few people care about resulting tree height.


texts: Determine if a structure is a model of an inductively defined predicate

texts:
My setting is first-order logic. As an example, consider an inductive definition of a linked list:

  $List(l)$ = $Null(l)$  $\vee~(Node(l) \wedge \exists sublist.   List(sublist) \wedge next(l,sublist))$

This is straightforward, a list is a node connected to a sublist. Consider the following structure:

  $Node(A)$, $Node(B)$, $Node(C)$, $Not\_A\_Node(D)$
  $next(A,B)$, $next(B,C)$, $next(C,D)$
  where $A, B, C, D$ are constants.

How do I determine if $A$ is a list? If there is no numerical operator in the predicate, this is very similar to parsing context-free grammar, and I can use either bottom up or top down algorithm. But how to do in the general case?

I'm asking for an automatic method.

If this is not a research-level question, please move it to an appropriate site. Thank you.

@Alessander Botti Benevides: Thanks for your reply. The first equation is the definition. FOL with inductive definitions is described, for example, in this paper:

Cyclic Proofs for First-Order Logic with Inductive Definitions.James Brotherston. TABLEAUX 2005.
http://www0.cs.ucl.ac.uk/staff/J.Brotherston/TABLEAUX05/cyclic_proofs_folind.pdf


texts: Surprising algorithms for counting problems

texts:
There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples include:

Counting perfect matchings in a planar graph (the FKT algorithm), which is the basis for how holographic algorithms work.
 Counting spanning trees in a graph (via Kirchhoff's matrix tree theorem).

A key step in both of these examples is reducing the counting problem to computing the determinant of a certain matrix. A determinant is itself, of course, a sum of exponentially many things, yet can surprisingly be computed in polynomial time.

My question is: are there any "surprisingly efficient" exact and deterministic algorithms known for counting problems which do not reduce to computing a determinant?


texts:
I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to translate one quantity in this paper in terms of computer science.

inf-entropy rate, $\underline{H}(X)$, of an arbitrary source is defined (Definition 3 in the paper) as the largest real number $\alpha$ (including $\infty$) that satisfies
$$\lim_{n\to\infty}P\{x^n:~\frac{1}{n}\log\frac{1}{P_{X^n}(x^n)}\leq \alpha-\epsilon\}=0,$$ for all $\epsilon>0$.

Comparing this quantity with the definition of min-entropy, we can say that for  i.i.d sources $\underline{H}(X)=H_{\infty}(X)$.

On the other hand, it is obvious that for all stationary and ergodic sources, the Shannon-McMillan theorem leads us to conclude that $\underline{H}(X)=\lim_{n\to\infty}\frac{1}{n}H(X^n)$ as mentioned in expression (2) in the paper.

Since i.i.d sources are a special class of stationary and ergodic sources for which $\lim_{n\to\infty}\frac{1}{n}H(X^n)=H(X)$,  from above, we conclude that for any i.i.d sources, $H_{\infty}(X)=H(X)$ which is clearly not true in general. [This is only true when the source is assumed to be uniform too].
So there must be a mistake somewhere in the above argument. Could you please let me know where is the mistake?


texts: Is compiler for dependent type much harder than an intepreter?

texts:
I have been learning something about implementing dependent types, like this tutorial, but most of them is implementing interpreters. My question is, it seems that implementing a compiler for dependent type is much harder than a compiler, because you can really evaluate the the dependent type arguments for type checking.

So

Is my naive impression right?
If it is right, any example / resources about implementing a statically checked language supporting dependent type?


texts:
Possible Duplicate:
  Are there languages that are not in RE nor CO-RE?

Let $ALL$ be the language of all decision problems. My question is, is there a language that is neither recognizable or complement-recognizable? If such a language exists, I believe it would be very interesting to study it (if it is possible!).


texts: Can the theory of Bidimensionality be applied to weighted instances of a problem?

texts:
So my understanding of bidimensionality is you are assured the problem solution is about O(k^2) so you can pay O(k) purely to reduce the instance to one of bounded treewidth.  As far as I know, this breaks down in the weighted case since the O(k^2) in your final solution could all be very low value.
Has there been work done in applying bidimensionality to weighted problems?


texts: Complexity of finding primes in arithmetic progression

texts: By the Green-Tao theorem the prime numbers contain arbitrarily long arithmetic progressions. What is the computational complexity of the search problem in which the input is a natural number k encoded in binary and the output can be any arithmetic progression of primes with k terms? If this is unknown then please provide upper and lower bounds.


texts: Can we verify satisfiability of first order statements via saturation in sub-exponential time?

texts:
In first order logic, we can prove satisfiability several ways: Finite model generation, truthful monadic abstractions, and also saturation. With finite model generation techniques, we can verify the model directly. With saturation we saturate the search space, running out of inferences, thus proving that a model exists.

How can we verify satisfiability demonstrated through saturation without rerunning the entire search, which might take quite a long time? Satisfiability demonstrated through saturation might be an infinite model, so model generation may not be sufficient.


texts: What is the best approximation and exact algorithm for vertex cover on cubic graphs?

texts: "Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.


texts: Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?

texts:
Underlying motivation for the question: if someone showed that $\text{P}=\text{NP}$ but the algorithm thus produced for, e.g., $3\text{-SAT}$, runs in time $\Omega(n^G)$ where $G$ is Graham's number, this would have no practical consequences whatsoever -- because $G$ is so large that it can't even be written down other than as a computation, so that already for $n=2$ an algorithm that uses that many steps is 'fiction'.
On the flip-side, if the exponent proved to be, say, $2$, that would turn everything upside down. That world would be truly bizarre.
Surely it must be known that the exponent must be $>2$. But what is in fact known?


texts: Why is shifting bits different from shifting qubits?

texts:
In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a series of quantum SWAP gates, which are composed of three CNOT gates respectively; the shifting contributes to the total circuit complexity.

So where does the difference come from? Is it due to the physical implementation of qubits?


texts:
We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a regular tree grammar (Chapter 2). Both formalisms hold close resemblances to the well-known string analogues.

  Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

Obviously there are tree languages such that the height of a tree is linear in its size; and in the book Analytic Combinatorics it is shown e.g. that binary trees of size $n$ have average height $2\sqrt{ \pi n}$. If I understand Proposition VII.16 (p.537) of the mentioned book correctly, then there is a wide subset of regular tree languages that have average height of $\Theta(\sqrt{n})$, namely those in which the tree language is also a simple variety of trees fulfilling some extra conditions.

So I was wondering whether there is a regular tree language showing a different average height or if there is a true dichotomy for regular tree languages.

Note: This question has been asked before on Computer Science, yet it has been unanswered for more than three months. I would like to repost it here because the question is too old to migrate and because there is still an interest in the question. Here is a link to the original post.


texts: What are natural examples of non-relativizable proofs?

texts:
As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).

Virtually all proofs seem to be relativizable, though.

What are good examples of non relativizable proofs, of the sort that a P=NP/P≠NP proof would need to be, that are not trivial or contrived?

(I am not a recursion theorist, so please pardon the lack of citations.)

[EDIT: better mathoverflow post]


texts:
This is a very basic question on $s$-$t$-connectivity in directed graphs. As a baseline, using DFS (or BFS), one can solve the problem on a graph $G=(V,E)$ in $O(n+m)$ time and $O(n)$ space, where $n=|V|$ and $m=|E|$.
However, I have seen mentioned in several places that DFS/BFS let you solve the problem in $O(n)$ time and space. For instance:

Two basic results on the complexity of $\mathsf{STCONN}$ exist for over 20 years. The first follows from the discovery of the very efficient algorithms for graph traversal, BFS (Breadth-First Search) and DFS (Depth-First Search), which use only linear time and space in $n$, the number of vertices.
Theorem 4. $\mathsf{STCONN}\in\mathrm{TISP}(n,n)$.

from [1]. How does that work? (Sorry if this question is trivial...) I would have thought maybe this followed from taking $n$ as the input size (not the number of vertices), but the text before does contradict this interpretation.

[1] Avi Wigderson.
The Complexity of Graph Connectivity. MFCS 1992: 112-132


texts: Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor

texts: Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ ||x_v - x_u|| \geq C$ otherwise, for some constant $C > 1$?


texts: What are the consequences if $W[i]=W[i-1]$?

texts: $FPT=W[1]$ does not collapse the $W$ hierarchy however falsifies $ETH$ belief. Is there non-trivial consequence if $W[i]=W[i-1]$ and any other consequence at $W[1]$?


texts: Isomorphic graph embeddings in the Euclidean Space

texts:
Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, where $\Delta(i, j)$ is the shortest path length between $i$ and $j$ in $G$?
I have been testing a few counterexamples for which these isometric embeddings in $\ell_2$ fail to exist (for example, the 4-cycle), but in this case they work.


texts: Hardness of node partitioning under shortest path constraint

texts:
Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in R$ (negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less) distinctive values to $l(i)$ such that
$$l(j) \leq l(i) + w(i,j),\quad \forall (i,j) \in E ?$$
Notice that when $k=|V|$, this problem is easily solvable by Shortest path algorithm (Bellman-Ford). But what's the hardness is this problem for $k < |V|$?


texts: Algorithm for extensional equality in combinator calculus

texts:
I'm dealing with combinator calculus, using the $S$ and $K$ combinators as a basis. Sometimes my code generates expressions that define equivalent functions, such as
$$
(S\, K\, K) \qquad\text{and}\qquad (S\, K\, (S\, (S\, S)\, K )),
$$
which both represent the identity function, but one of them is needlessly more complicated than the other.

"Extensional equality" is the terminology used when we consider two expressions to be equal if they represent the same function in this way. I would like to know whether there is an algorithm to determine whether two expressions are in fact extensionally equal. That is, can I determine in general whether two expressions represent the same mapping?

I suspect the answer might be "no", since it feels like this is the sort of thing that should be undecidable. On the other hand, it's straightforward to determine in the case above, since the expressions $(S\, K\, K)\, x$ and $(S\, K\, (S\, (S\, S)\, K ))\, x$ both evaluate to $x$, and I'm new enough to this stuff not to trust my intuition that this can't be generalised.

I note that there is a similar question about programs in general rather than the combinator calculus, which seems to confirm my intuition that this is undecidable. There is also plenty of discussion of this issue in the context of the (untyped) lambda calculus, in which $\eta$-conversion plays a pivotal role. However, I would like to know specifically how to think about this in terms of combinator calculus.


texts: Finding the smallest DFA that separates two words without using brute force search?

texts:
Given two strings x and y, I want to build a minimum size DFA that accepts x and rejects y.  One way to do this is brute force search.  You enumerate DFA's starting with the smallest.  You try each DFA until you find one that accepts x and rejects y.

I want to know if there is any other known way of finding or building a minimum size DFA that accepts x and rejects y.  In other words, can we beat brute force search?

More Detail:

(1) I really do want an algorithm to find a minimum size DFA, not a near minimum size DFA.

(2) I don't just want to know how large or small the minimum DFA is.

(3) Right here, I'm only focused on the case were you have two strings x and y.

Edit:

Additional information for the interested reader:

Suppose $x$ and $y$ are binary strings of length at most $n$.  It is a known result that there is a DFA that accepts $x$ and rejects $y$ with at most $\sqrt{n}$ states.  Notice that there are about $n^{\sqrt{n}}$ DFA's with a binary alphabet and at most $\sqrt{n}$ states.  Therefore, the brute force approach wouldn't require us to enumerate through more than $n^{\sqrt{n}}$ DFA's.  It follows that the brute force approach couldn't take much more than $n^{\sqrt{n}}$ time.

Slides that I found helpful: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf


texts:
While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post:

  If, for every $n$, there exists a relation of the form
  $$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$
  where $m = poly(n)$, and each of the $a_k$, $b_k$ and $c_k$ are $poly(n)$ in bit length, then factoring has polynomial sized circuits.

In other words, the $(2^n)!$, which has an exponential number of bits, can potentially be represented efficiently.

I have a few questions:

Could someone provide a proof of the above relation, tell me the name and/or provide any references?
If I were to give you $n$, $m$ and each of the $a_k$, $b_k$ and $c_k$, could you provide me a polynomial time algorithm to check the validity of the relation (i.e. is it in $NP$)?


texts: Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)

texts:
What are some examples of problems with quasi-polynomial time ($QP$) algorithms that could conceivably be in $P$. In other words, they are in $QP$ for no obvious reason other than no one has found a polynomial-time algorithm?

This question is motivated by the recent graph isomorphism result (which is a valid answer to this question)

Some non-examples are

Finding a clique of size $\log^{100} n$ in a graph
Finding a path of size $\log^{100} n$ in a graph
Solving k-sum for $k=\log^{100} n$
Minimum dominating set in a tournament

Any of these problems being in $P$ would violate the exponential time hypothesis (ETH).


texts: I have always heard that transversality is a sufficient, not a necessary condition for fault-tolerance in quantum computation. However, I have never seen any examples of non-transversal fault tolerant gates. Does anyone know of any?


texts: Is this variation of the "sequencing with release times and deadlines" problem NP-complete?

texts:
The following problem is known to be NP-complete. It can be found in pages 236 and 70 of Garey & Johnson. In this book this problem is known either as sequencing with release times and deadlines or as sequencing within intervals.

INSTANCE: Set T of tasks and, for each task $t\in T$, a length $l(t)\in Z^+$, a release time $r(t)\in Z_0^+$, and a deadline $d(t)\in Z^+$.

QUESTION: Is there a one-processor schedule for T that satisfies the release time constraints and meets all the deadlines, i.e., a one-to-one function $\sigma:T\rightarrow Z_0^+$, with $\sigma(t)>\sigma(t')$ implying $\sigma(t)\geq \sigma(t')+l(t')$, such that, for all $t\in T$, $\sigma(t)\geq r(t)$ and $\sigma(t) + l(t)\leq d(t)$?

Now suppose that all the tasks have the same length, and that the
length is not necessarily an integer, that is, $l(t)=l$ for all $t\in
T$, for some positive rational number $l$. Moreover, let $\sigma:T\rightarrow R^+$ instead of $\sigma:T\rightarrow Z_0^+$. Under these modifications, does the
problem remain NP-complete?


texts: Minkowski decomposition of lattice point cloud

texts:
Given two point clouds $A,B\subset\mathbb Z^d$, let $A\oplus B$ be their Minkowski sum, defined as the set $\{ a + b : a\in A, b\in B \}$.

Is there any known result for the following problem?

  Given a point cloud $S\subset\mathbb Z^d$, are there two point clouds $A$ and $B$, none of them reduced to a single point, such that $A\oplus B = S$?

I am in particular interested in the case $d=2$.

A related result is the following: Given a convex set of points¹ $S\subset\mathbb Z^2$, it is $\mathsf{NP}$-hard to decide whether it can be written as the sum of two convex sets $A$ and $B$ [1]. As far as I can tell, this does not imply a hardness result for the above problem since the equality is on the convex hulls only, not on the point clouds. In the terminology I used above, in this problem is only required that $A\oplus B\subset S$. The problem on point clouds may well be easier (not $\mathsf{NP}$-hard in particular) since it is much more constrained.

[1] Gao, S., & Lauder, A. G. (2001). Decomposition of polytopes and polynomials. Discrete & Computational Geometry, 26(1), 89-104.

¹ A subset $S\subset\mathbb Z^d$ is said convex if all points of $S$ lie on the boundary of the convex hull of $S$.


texts: Any fast algorithm for minimum cost feedback arc set problem?

texts:
In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set.

If each edge is associated with a weight $w$, the minimum cost feedback arc set problem is to find a $F$ such that $W(F)$ is minimum.

It is well-known that minimum feedback arc set problem is NP-hard, and so does minimum cost feedback arc set problem. I wonder if anyone knows any approximate algorithm that performs well, and any properties of the weight function that can yield a fast solver.


texts: Complexity of counting weighted cycles in planar graphs?

texts:
Assume G is a weighted planar graph, nodes and edges in G are weighted, and K is a given constant.
A is a decision problem with following description:

  Does G contain a cycle with total
  weight K ?

What is the complexity of the counting version of A (#A)? (i.e the complexity of counting all cycles with total weight K)


texts:
Firstly, I admit that my question is just something very blurred but I hope someone please give me some documents to read.

The execution of a program $P$ can be considered as a sequence of state transitions $State \to State $ (this sequence should be finite if the program halts). By that way we get execution traces of program. Now, we may note that these traces (denoted as a set $T$) are generated by a static structure, that is the syntax of $P$. So we receive the first constraint: the set $T$ can not be arbitrary, instead $T$ must be result of some static rewriting rules applied on the static syntax of program.

Continue this way, if $P$ is a self-modifying program, roughly speaking $P$ can firstly generate other programs $Q_{1}, Q_{2}, \dotsc$, and these programs, at their turns, will generate other traces $T_{1},T_{2}, \dotsc$, so $T = T_{1} \cup T_{2} \cup \dotsc$. And we receive the second constraint: the set $T$ must be result of some static rewriting rules applying on some static rewriting rules applying on the static syntax of programs.

We can continue this construction to some level (may be there exists a limit ?). But a similar view I get is in the high order category theory where there exist morphisms between morphisms, and morphisms between morphisms between morphisms, etc.

So my question is: Do exist some reseaches on that or my thinking is just a stupid nonsense thing ?


texts: Multiple subset sum where subsets have complementary cardinality

texts:
$\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem:

Input: $a_1,\dots,a_n,b\in \mathbb Z$, with distinct $a_i$ and $k\in\Bbb Z^+$.

Output: $k$ $\mbox{ }\underline{not\mbox{ }necessarily\mbox{ }disjoint}$ subsets of $a_i$s of sizes $n_1,\dots,n_k$ satisfying $\sum_{i=1}^kn_i=n$ such that each subset sums to $b$.

(1) Is $\mathsf{EkCSS}$ $NP$-complete?

(2) If we replace requiring $k$ subsets by requiring $\lceil\log^cn\rceil$ subsets for some fixed $c\in\Bbb R^+$ does the problem remain NP complete?

(3) Is $\mathsf{EkCSS-Diff}\mbox{ }$ $NP$-complete where $\mathsf{EkCSS-Diff}$ is same as $\mathsf{EkCSS}$ but with added condition $n_i\neq n_j\forall i\neq j$ (different subset sizes)?


texts: What is the most "unbalanced" vector between two given vectors of numbers?

texts:
Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ the product ordering on $\mathbb{R}_+^m$. That is, $\leq_m$ is the partial ordering on $\mathbb{R}_+^m$ defined for all $V_1, V_2 \in \mathbb{R}_+^m$ as $V_1 \leq_m V_2$ if and only if for every $i \in \{1, \dots, m\}$, $V_1(i) \leq V_2(i)$, where $\leq$ is the standard ordering over real numbers. Lastly, given a vector $V = (V(1), \dots, V(m)) \in \mathbb{R}^m$ we denote $d(V)$ the "unbalance degree" of $V$ defined as $d(V) = \sum_{i=1}^m{|V(i) - \mathrm{avg}(V)|}$ where $\mathrm{avg}(V) = \frac1m \sum_{i=1}^m{V(i)}$. Intuitively, $d(V)$ represents the Manhattan distance between $V$ and the "average line" $\{(x_1, \dots, x_m) \in \mathbb{R}_+^m \mid x_1 = \dots = x_m\}$.

My problem is as follows: given two vectors $V, V' \in \mathbb{R}^m_+$ such that $V \leq_m V'$, I would like to characterize a vector from $\mathrm{argmax}_{V \leq W \leq V'}\,d(W)$. Intuititvely, such a vector is one of the most "unbalanced" ones between $V$ and $V'$. For instance, if $V = (0, 0, 0, 0, 0)$ and $V' = (4, 10, 2, 10, 4)$, such a vector is $W = (0, 10, 0, 10, 0)$, with $d(W) = 24$.

My conjecture is as follows. Let $avg(V, V') = \frac{1}{2m}{\sum_{i=1}^m{V(i) + V'(i)}}$. We build the vector $W$ for every $k \in \{1, \dots, m\}$ as follows:
$$W(k) = \left\lbrace\begin{array}{ll}
V(k) & \mbox{ if } (\tfrac12\big(V(k) + V'(k)\big) < \mathrm{avg}(V, V')),\\
V'(k) & \mbox{ if } (\tfrac12\big(V(k) + V'(k)\big) > \mathrm{avg}(V, V')).\\
\end{array}\right.$$
We define the remaining components of $W$ (i.e., the $W(k)$ such that $\tfrac12\big(V(k) + V'(k)\big) = \mathrm{avg}(V, V'))$) as follows. Let $K = \{k \in \{1, \dots, m\} \mid \tfrac12\big(V(k) + V'(k)\big) = \mathrm{avg}(V, V'))\}$ and denote the elements of $K$ as $\{k_1, \dots, k_n\}$. Then $\forall k_i \in K$,
$$W(k_i) = \left\lbrace\begin{array}{ll}
V(k_i) & \mbox{ if $i$ is an odd number},\\
V'(k_i) & \mbox{otherwise.}
\end{array}\right.$$

So far, I could just prove that there is a vector $W \in \mathrm{argmax}_{V \leq W \leq V'}\,d(W)$ such that for every $k \in \{1, \dots, m\}$, $W(k) \in \{V(k), V'(k)\}$. But this leaves a search space of size $2^m$, and does not provide me a polytime algorithm to solve the problem. Proving the conjecture above would do so.


texts: Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$

texts:
How can I solve the following recurrence relation?
$$ f(n) = f(n-1) + f(n - \log n)$$


texts: Cooperative Pathfinding to minimize global costs

texts:
There are some algorithms and methods around, that allow cooperative pathfinding. Unfortunately they all seem to aim at avoiding collisions or conflicts between entities.

I'm looking for an algorithm that allows agents to explicitly join their paths to go some part of the way together if that minimizes the overall costs, regardless of individual costs (e.g. using the wind shadow of another car)

Is there any research going on in this area that I'm not aware of, or are there even algorithms around that solve such problems?


texts: Complexity of Smoothed $\ell_0$ algorithm

texts: I wanted to compute the complexity of a smoothed $\ell_0$ algorithm in BigO notation. The algorithm can be found here. Can anybody help me in this regard?


texts: Equality Theorems with Type Theoretic Proof

texts:
I am investigating how I might be able to translate even commonplace equalities/ inequalities via the so-called Curry-Howard Correspondance - from a generic, set theoretic plus AOC foundation - into a decidable type theoretic language.

To my understanding, a constructivist foundation would require that an inequality could be proven only by exhibiting, say, a $n:\mathbb{N}$ such that $a + n = b$ to prove that $a \leq b$ for $a, b \in \mathbb{Z}$.

This is indeed the example of a "dependent pair type" on Wiki, which represents the first-order theorem:

$a \leq b \iff \Sigma\mathbb{N}(\lambda n \to a + n = b)$

But what exactly is going on here? How are we allowed to put a function from $n$ to a proposition, $a + n = b)$ into our type formula? If you see this post also, the first answer has an "if then else" conditional in their type formula!

Moreover, if wanted to wanted to prove an equality $a = b$ where $a$ and $b$ are mathematical terms like polynomials, there would not be any model $n$ to choice from as above - so how would we do it? Usually, in a regular undergraduate mathematics course, we might try a proof by contradiction. Maybe try showing that we any inhabitants of $a$ and $b$ will be such that $ a - b = 0$?


texts: Number of minimal DFAs of size at most $m$?

texts:
Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$.  Let $f(m)$ denote the number of different such minimal DFAs.

Can we find a closed-form formula for $f(m)$?

Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs (as suggested in the comments). In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}\cdot m\cdot2^m = 2^m\cdot m^{2m+1}$.

We can generalize to an arbitrary alphabet $\Sigma$: the bound becomes $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$.

But we bounded here arbitrary DFAs and I'm interested in bounding the number of minimal DFAs. Thus, it looks like this bound could be tighter... Does someone have a better estimate?

I would appreciate if possible, some papers related to this problem or a proof/counter-example.


texts: What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?

texts:
My understanding of these classes is a really fuzzy. The more I am trying to read the more I am getting confused. Can anyone help me understand the relationship between these classes. More precisely, is $\mathsf{MaxSNP} = \mathsf{APX}$  or $\mathsf{MaxSNP} \subset\mathsf{APX}$?

Thanks a lot in advance. :)


texts: We do not know yet whether the 2-sided error of $BPP$ allows more computing power than the one sided error of $RP$. In view of derandomization results, the conjectured answer is no, since both classes are conjectured to collapse into $P$. However, not having a proof of that yet, I wonder if there are any results that at least bring $BPP$ closer to $RP$. For example, is there any condition that is known to imply $BPP=RP\cup co-RP$, or $BPP=P^{RP}$, or something similar, but is not known to imply $BPP=RP$?


texts:
https://link.springer.com/article/10.1007/s00153-013-0351-x gives seven reductions $m,c,d,p,btt(1),\ell,tt$.

What does norm $1$ mean in $btt(1)$?
Is there illustrative examples that help understand from hierarchy between $PP$ and $PSPACE$ the different reductions?
Which is the standard reduction existence or non-existence that we care when we prove class inclusions or should prove to separate classes?


texts:
Probably the most common recursion scheme is the catamorphism, or fold.  This is a recursion that takes a data type and "deconstructs" it into something else.  For example, we can calculate the length of a list using a fold (with Haskell syntax):

length :: [a] -> Int
length xs = foldr 0 (+1) xs

One property of all folds that I've seen is that they look at all elements of the data type.  But is there work formalizing recursion schemes that do not look at all elements?  That is, they prune some of them away.

If the type of foldr :: (a -> b -> b) -> b -> t a -> b, then the pruning fold would look something like prunefold :: (???) -> (a -> b -> b) -> b -> t a -> b, where ??? is the pruning rule.  I can imagine many different possible forms of these pruning rules just for folds, and I imagine other recursion schemes would have even more.

Motivating example 1:  We could search a binary search tree using a fold.  This fold would perform a depth first search.  But this is very inefficient.  Instead, we would prefer to have a "pruning rule" that on each iteration removes removes half the tree.  This pruning fold gives us the same answer, but reduces the complexity from $O(n)$ to $O(\log n)$.

Motivating example 2:  We can express $\pi$ as a sum over an infinite sequence.  A standard fold over this sequence would never terminate.  But we could use a pruning rule to stop our fold after a certain amount of accuracy has been reached.  When used on an infinite data structure, the pruning fold is strictly more powerful.


texts:
What are good papers/books to better understand the power of Modular Decomposition and its properties?

I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that it is possible to find a Modular Decomposition of a graph in linear time. Is there are an relatively simple algorithm for that? What about a not so efficient but simpler algorithm?


texts: Can Hoare logic be used when objects are created or deleted?

texts:
Hoare logic can be used for proving program correctness (e.g. for deriving correctness statements for the whole program from the statements for the individual commands or constructions; good summary is http://www.cis.upenn.edu/~bcpierce/sf/Hoare.html). The question is - is there any line of research where Hoare-style reasoning can be made for programs that creates and deletes objects.

One thought can be that this reasoning can be simulated by defining large pool of objects which have (for the purposes of correctness analysis) additional state attribute with values from the enumeration {not-created, created, destroyed}. But I guess that better approach should exist.

Are there any references or keywords for furher search into this matter.


texts: Least fixed point logic is efficiently $\operatorname{P}$-bounded for $\operatorname{P} \Leftrightarrow L_\leq$ is a logic for $\operatorname{P}$

texts:
A least-fixed point (LFP) formula is $\leq m$-invariant iff f.a. structrues $\mathcal{A}$ with $|A| \leq m$ and all orderings $<_1,<_2$ on $A$

$$(\mathcal{A},<_1) \models_{LFP} \varphi \Leftrightarrow (\mathcal{A},<_2) \models_{LFP} \varphi.$$

The logic $L_\leq$ is defined such that the modelling-relation is

$$ \mathcal{A} \models_{L_\leq} \varphi \Leftrightarrow \varphi \textrm{ is $\leq |A|$-invariant and } (\mathcal{A},<)\models_{LFP}\varphi \textrm{ for some} <.$$

A logic $L$ is efficiently $\operatorname{P}$-bounded for $\operatorname{P}$ if

for each $Q \in \operatorname{P}$ there is a $\varphi \in L$ which axiomatizes $Q$
for each $\varphi \in L$ there is polynomial $p$ such that the modelling
relation $\mathcal{A} \models_L \varphi$ can be decided by an algorithm in
$\leq p(\|\mathcal{A}\|)$ steps

A known result is that LFP is an efficiently $\operatorname{P}$-bound logic for $\operatorname{P}$ on the class of ordered structures. A paper states that one can easily deduce from the result that $L_\leq$ is a logic for $\operatorname{P}$. Any ideas how?


texts: Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

texts:
The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers.
Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence from S, then it sorts every 0-1 sequence and the size of $S$ is polynomial in $n$?

For example, if $S$ consists of all sequences where there are at most $2$ runs (intervals) of 1's, then is there a sorting network N and a sequence that is not ordered by N if all members of $S$ are ordered by N?

Answer: As can be seen from the answer and the comments to it, the answer is that for every unsorted string there is a sorting network that sorts every other string.
A simple proof for this is the following.
Let the string $s=s_1\ldots s_n$ be such that $s_i=0$ for ever $i<k$ and $s_k=1$.
Since $s$ is unsorted, after sorting $s_k$ should be $0$.
Compare $k$ with every $i$ for which $s_i=1$.
Then compare every pair $(i,j)$ such that $i\ne k$ and $j\ne k$ many times.
This leaves the whole string sorted, except possibly for $s_k$, which is unsorted for $s$, and for certain other strings that have more $1$'s than $s$.
Now compare $s_k$ for $i=n$ downto $1$ except for the place where $s_k$ should go in $s$.
This will sort everything but $s$.

Update: I wonder what happens if we restrict the depth of the network to $O(\log n)$.


texts: Running time of Jacobi vs Golub-Kahan for SVD

texts:
For an $m \times n$ matrix, what is the running time for computing the Singular Value Decomposition (SVD for short) via

Jacobi's method, and
Golub-Kahan?

The source I read mentions that Jacobi's method is slow,
but I can't find a table of big-Oh running times of the various SVD algorithms anywhere.


texts: Computational Complexity of the Helpmate problem in Chess

texts:
It is well known that Chess is EXPTIME-Complete.

I am interested in the related "Helpmate" problem. Given an $N$ by $N$ chessboard, is there any sequence of at most $k$ moves that leads to Black's checkmate? To clarify, both players are cooperating to end the game in Black's checkmate.

I could not find any literature discussing the computational complexity of the problem, perhaps I am not searching for the right terms.


texts: Shortest string in the intersection of a context-free language and a regular language

texts:
For a language $X$, define $ss(X) = \min_{x\in X} |x|$, the length of the shortest string in $X$. For simplicity, we define $ss(\emptyset)=0$.
Let $L$ be a context-free language generated by a context-free grammar with $k$ non-terminals. (assuming all context-free grammars are in Chomsky normal form.)
Let $R$ be a regular language recognized by an NFA of $n$ states.

  What is $ss(L\cap R)$, the length of the shortest string in $L\cap R$?

A naive upper bound is $2^{kn^2}$: find a context-free grammar for $L\cap R$ with $kn^2$ non-terminals.

Motivation: Answer to the above question can lead to a better bound for the following problem.

Let $L$ be a fixed context-free language. Let $\mathcal{R}_n$ to be all the set of all regular languages that can be recognized by an NFA of $n$ states.

Define $f_L(n) = \max_{R\in \mathcal{R}_n} ss(L\cap R)$.

  What can we say about the asymptotics of $f_L(n)$?

Using the naive bound, we know $f_L(n) = O(2^{n^2})$.


texts: How to prove deg(f) = n iff the parity imbalance of f is non-zero?

texts:
Not sure if the notation I'm using here is standard or not. I'm going over class notes and I'm stumped over an exercise given: Show that $deg(f) = n \iff PI(f) \neq 0$.

Here $f$ is a boolean function on $n$ variables. $PI(f) = \sum\limits_{x \in f^{-1}(0)} (-1)^{w(x)}$. $w(x)$ is the number of bits = 1 in the input $x$. $deg(f)$ is the minimum degree of any polynomial representation of $f$.

This implies a sufficient condition that $f$ is evasive is $PI(f) \neq 0$. Thank you in advance for your help.


texts: Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

texts: It is well known that the NP-Complete Problem called Subset Sum has a FPTAS. I was wondering if there existed an PSPACE Complete problem which also has a FPTAS? Thanks in advance.


texts:
I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7.
The issue is that, for the case when 4 points lying on a straight line with alternating signs (like - + - +), I don't see why a triangle could separate the points. Where am I making mistake?

[1] http://www.igi.tugraz.at/lehre/CI/SS08/tutorials/VC_examples/VC_examples.pdf


texts: How long does it take at most for $k$ boolean variables to map back to themselves with a positive disjunctive update rule?

texts:
I have a vector of boolean variables $v=(x_1,\dots,x_k)$. In each step each variable is updated according to a positive disjunction like so:

$x_1 \leftarrow x_i \vee \dots \vee x_j$
$\dots$
$x_k \leftarrow x_m \vee \dots \vee x_n$

This produces a sequence of vectors $\underline{v} = v_1,v_2\dots$. My question is, how long does it take for $\underline{v}$ to reach a cycle, in terms of $k$, for arbitrary $v_1$, that is:
Let $v$ be a $k$-ary boolean vector. Then $f(v)$ denotes the update function for  according to those rules. We say $v'$ is in a cycle from $v$ if there is an $n>0$ and $m \geq 0$ such that $f^{(m)}=f^{(m+n)}$. We define the smallest time to reach a cycle as the smallest sum $m+n$ for which the equality holds.
The question is: What is an upper bound for the smallest time to reach a cycle in terms of $k$ that holds for all possible starting vectors $v_1$ and all possible update functions $f$.

My idea was to represent the update rules as a dependency graph and look at cycles to form rules such as if $x_i$ is true in $v_y$  and is in a cycle of length $n$, then it will also be true in $v_{y+n}$.
But the best lower bound I could do so far is to construct an example where for even $k=2l$ I construct two cycles of length $l$ and $l+1$ with one common node and start with $v_1$ having exactly one true node. The common node is true every $l$ or $l+1$ steps (depending on in which cycle the first true node was). Since $gcd(l,l+1)=1$, eventually all nodes in the other cycle will be true as well. For this, the common nude must be true $l+1$ or $l$ times, respectively. This yields $O(k^2)$ steps until all nodes are true (and then $\underline{v}$ is trivially cyclic).
Unfortunately, I did not get any upper bound except for the obvious $2^k+1$ since each $v_i$ can only assume one of $2^k$ values.

I am not necessarily looking for an exact upper bound if that turns out to be hard, it'd also be sufficient for me to give the upper bound in $O$-notation, or even just show whether the upper bound is polynomial or exponential.
Further, I'm also interested in and extension to the 3-valued case (with 3-valued Kleene disjunction).


texts:
consider the problem: given a graph and a number of vertices $n$ less than the vertices in the graph, and a distance $d$. find a set of $n$ vertices such that all vertices of the graph are within $d$ distance of the $n$ vertices (measured in edge count of the shortest path). in a sense the $n$ vertices are "hubs" of the graph. (there may be other constraints on their selection.) suspect this problem may arise in a variety of guises. am not nec. looking for an exact solution.

  looking for the contexts this arises (applications) & recent literature/survey(s) on this problem, finding the "natural" "hubs" of a graph.

possibly somewhat related is finding/adding a few edges to yield "good" hubs (hub sets that are small relative to the vertices they "reach").


texts: Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?

texts:
Consider the following problem:

  Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a
  partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, and such that $\max_i w(V_i)$ is
  minimized, where $w(V_i)$ is the total weight of the vertices in
  $V_i$.

It can be easily seen that this problem is NP-complete. For hardness, note that we can solve Partition by using a complete graph.

Questions: Does this problem have a standard name? Are there any papers that study this problem, or maybe slight variations of it? Is the problem still hard for sparse graphs? I am particularly interested in references that could lead to an implementation with good performance in practice.


texts: How can you encode natural numbers operations on interaction combinators?

texts: The church-encoding for natural numbers is a natural mean of implementing addition, multiplication and so on on the lambda calculus. Interaction nets are said to be an alternative universal computation system, yet, nothing is published as to how one could encode simple data structures and algorithms on the interaction nets directly. What are the natural encodings of numbers and numeric algorithms on interaction combinators?


texts: Compressing grammars by introducing ambiguity and left-recursion

texts:
This is a reference request. What is known about the following questions?

Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a
new grammar $G'$ which also accepts $L$, but may introduce left
recursion and ambiguity.

Which algorithms have been investigated that produce such $G'$ from $G$?
By how    much can $G'$ be more succinct than
$G$ (for any reasonable notion of succinctness)?

Context. There has been a great deal of work on making grammars
parsable in practise. This involved removing ambiguity and (relevant
only for some form of parsing) left-recursion. Many notions of normal
form have been invented form this purpose, with parsers that can
handle these NFs. However, making grammars digestible by parsers also
makes them  less readable by humans. I'm    interested in going the other
way: How to make machine-parsable grammars more readable by giving up
on machine parsability (or at least making parsing harder).


texts: Computational complexity in quantitative finance

texts:
Predicting the stock market is hard! Can TCS make this sentiment more formal?

Recently I have started thinking a little bit about finance, and was wondering how knowledge of TCS could help. Hedge funds and investment firms seems to use algorithmic trading, machine learning, and AI all the time, but TCS results seem to be few. In particular, I only know two papers:

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge, Computational Complexity and Information Asymmetry in Financial Products, 2009.

Philip Z. Maymin, Markets are efficient if and only if P = NP, 2011.

The first paper shows that derivatives can amplify the cost of informational asymmetry (instead of the desired goal of reducing it) for computationally-bounded agents. The second paper challenges the popular belief of efficient markets by showing that market efficiency can be used to solve NP-hard problems.
Are there any books/surveys or seminal papers on related ideas? Especially things related to the difficulty of predicting or approximating markets or trading optimally (or close to optimally) in such markets?
A slightly more meta question: why does there seem to be an abscence of papers on this? Is there no interest, or is that all the interested parties become quants that are hiden behind no-publication agreements?
Related question
Algorithmic lens in the social sciences
What is the Complexity Classification of Portfolio Theory in Financial Economics?


texts:
This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves.

To be more precise, let's say a problem has gap classes $A,B$ (with $A\subseteq B$, not uniquely defined) if $A$ is a maximal class for which we can prove it is $A$-hard, and $B$ is a minimal known upper bound, i.e. we have an algorithm in $B$ solving the problem. This means if we end up finding out that the problem is $C$-complete with $A\subseteq C\subseteq B$, it will not impact complexity theory in general, as opposed to finding a $P$ algorithm for a $NP$-complete problem.

I am not interested in problems with $A\subseteq P$ and $B=NP$, because it is already the object of this question.

I am looking for examples of problems with gap classes that are as far as possible. To limit the scope and precise the question, I am especially interested in problems with $A\subseteq P$ and $B\supseteq EXPTIME$, meaning both membership in $P$ and $EXPTIME$-completeness are coherent with current knowledge, without making known classes collapse (say classes from this list).


texts: Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$?

texts:
I am trying to either prove or refute the claim mentioned in the title.
Any ideas ?


texts: Asymmetry in Property Testing Definition

texts:
Property Testing refers to the problem of making a small number of queries to determine whether $x$ is in some language $L$ or whether it is far away from being in $L$.

More precisely we want to distinguish
1)  $x \in L$
2)  $x$ epsilon-far from every $y \in L$.

Here, epsilon-far is generally taken to mean hamming distance.

I don't quite understand why property testing has this asymmetric definition, i.e. why don't we want 1) to be  "$x$ epsilon-close to some $y \in L$"


texts: Problem with a group as complexity parameter?

texts:
I am currently studying a complexity problem related to symmetries, and am considering a study of the parameterized complexity of the problem.

In theory, any part of the input can be fixed as a parameter, but in practice it seems like parameters are almost always integers.
Some problems use a graph as a parameter, such as the testing whether H is a minor of G (polynomial when H is fixed, hence fixed parameter tractable with H as a parameter).

My question is: do you know any study of the complexity of a problem parameterized by a group?

Candidates could be classical group-related problems, such as coset intersection problem or hidden subgroup problem, but I have not found such parameterized complexity study for them.


texts: Fully linear time regular expression matching

texts:
Is there an $O(n+m)$ algorithm to check whether a size $n$ regular expression matches a size $m$ string, assuming a fixed size alphabet if that matters?

The standard NFA algorithm is $O(nm)$ worst case.  Groz et al. achieve linear time for a variety of regular expression classes, but not all.  Are there any better results?

Groz, B., Maneth, S., & Staworko, S. (2012, May). Deterministic regular expressions in linear time.


texts: What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

texts:
Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem

I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the Gale-Shapley algorithm. However, if we are given only $n$ , the number of men/women, we ask the following question - Can we construct a preference list that gives the maximum number of stable marriages? What is the upper bound on such a number?


texts: Finding smallest context free grammar that generates a set of sets

texts:
Are there any results known about the size of smallest context free grammar that generates a set of sets?

That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ and I want to find the smallest context free grammar $G$ whose language $L$ has the property that $A \in S \Leftrightarrow (\exists x \in L~\forall l \in \Sigma~[l \in x \Leftrightarrow l \in A])$.

For instance, if $\Sigma =\{a,b,c,d\}$ and $S=\{\{d,a,c,b\},\{b,c,a\},\{a,b\},\{a\},\{\}\}$, I can have following grammar $G$ of size 14 which corresponds to the given $S$:
$$
\begin{array}{l}
G \rightarrow ``dacb"\\
G \rightarrow ``bca"\\
G \rightarrow ``ab"\\
G \rightarrow ``a"\\
G \rightarrow \lambda
\end{array}
$$

However, I can also use the fact that $S$ is a set and have the following smaller grammar $G'$ of size 13 which corresponds to representing $S$ as $``\{\{a,b,c,d\},\{a,b,c\},\{a,b\},\{a\}\}"$
$$
\begin{array}{l}
G' \rightarrow aA\\
A \rightarrow bB\\
A \rightarrow \lambda\\
B \rightarrow cd\\
B \rightarrow c\\
B \rightarrow \lambda
\end{array}
$$

I am interested in the following questions:

Has this problem been studied somewhere? In this regard, do we know the complexity of this problem? If it happens to be computationally complex, are there any approximation algorithms? What about good heuristics?
Has problems similar to this been studied before? For example, instead of using context free grammars, use set theoretic operations such as union and intersection or maybe use some other type of grammar (maybe more restricted than CFGs?).

I am interested in all results that use the underlying assumption of wanting to represent a set (i.e., order is irrelevant). I know that, in the compression literature, there are works on optimal arithmetical encodings of sets. However, I cannot see any direct translation from those results to this domain where we are interested in finding a short grammar.


texts: Algorithm to determine function equality on the simply typed lambda calculus?

texts: We know that beta-equality of simply typed lambda-terms is decidable. Given M,N:σ→τ, is it decidable whether for all X:σ, MX $≃_β$ NX?


texts: Why it's impossible to declare an induction principle for Church numerals

texts:
Imagine, we defined natural numbers in dependently typed lambda calculus as Church numerals. They might be defined in the following way:

SimpleNat = (R : Set) → R → (R → R) → R

zero : SimpleNat
zero = λ R z _ → z

suc : SimpleNat → SimpleNat
suc sn = λ R z s → s (sn R z s)

SimpleNatRec : (R : Set) → R → (R → R) → SimpleNat → R
SimpleNatRec R z s sn = sn R z s

However, it seems that we can't define Church numerals with the following type of Induction principle:

NatInd : (C : Nat -> Set) -> (C zero) -> ((n : Nat) -> C n -> C (suc n)) -> (n : Nat) -> (C n)

Why is it so? How can I prove this? It seems that the problem is with defining a type for Nat which becomes recursive. Is it possible to amend lambda calculus to allow this?


texts: When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?

texts:
I started reading Avi Wigderson's paper $\mathcal{P}$, $\mathcal{NP}$ and Mathematics – a Computational Complexity Perspective (link).

(Notation: $\{0, 1\}^\ast$ is the set of all finite binary sequences, and $\{0, 1\}_n^\ast$ is the set of all finite binary sequences of length at most $n$.)

In page 7, he defines the complexity class $\mathcal{P}$: A function $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$ if there is an algorithm (i.e. a deterministic Turing machine) that computes $f$, and also a constant $c > 0$ such that the number of steps it takes to compute $f(w)$ for any $w \in \{0, 1\}_n^\ast$ is $O(n^c)$.

Immediately after that he says we that we are going to restrict our attention to the boolean functions $f : \Sigma^\ast \to \{0, 1\}$, since "a function with a long output can be viewed as a sequence of Boolean functions, one for each output bit."

I guess he here intends to say something like this: $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$ if and only if the function $f_i : \{0, 1\}^\ast \to \{0, 1\}$ corresponding to the $i$th output bit is in $\mathcal{P}$ for all $i$.

I find this a bit confusing.

For starters, we are looking at the $i$th output bit, which belongs to $\{0, 1\}$, and we do not have a third symbol to be interpretted as "this bit is empty". This is assuming, of course, that sequences like $0$ and $000\cdots0$ are different. Anyways...

If $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$, then all of its $i$th bit functions are in $\mathcal{P}$ (forgetting about the empty bit problem for now). For any $w$ of length $\leq n$, we compute $f(w)$ in $O(n^c)$ steps, and extract the $i$th bit in $O(i)$ steps, so the bound for $f_i$ is $O(n + i)$.

We can actually bound the $i$s that will produce an output. The Turing machine that computes $f(w)$ will do at most $O(n^c)$ steps, and so the output will be of length $O(n^c)$. Thus $i$ is bounded above by $O(n^c)$.

For the other direction... Here is what I have thought about: Let $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ be such that each of its $f_i$ functions are in $\mathcal{P}$. There is nothing saying their complexity have a uniform bound on their polynomial growth, that is, the time complexity for $f_i$ can be $O(n^{c_i})$ with no bound on the $c_i$, or the number of functions that will produce an output (for the time it will take to put all those bits side by side; that still counts, I think).

Any how, so why can this paper focus on complexity for boolean functions only?

EDIT 1: I just noticed something else: In the definition of $\mathcal{NP}$ (definition 2.3), the verifier function $V_C$ is a function $\{0, 1\}^\ast \times \{0, 1\}^\ast \to \{0, 1\}$ not $\{0, 1\}^\ast \to \{0, 1\}$. I can think of ways to make this work (like encoding $(x, y)$ as an element of $\{0, 1\}^\ast$. For instance, $(x, y) \mapsto 1111110xy = 1^{|x|}0xy$, where the number of $1$s gives the length of $x$. The length of the encoding is $2|x| + |y| + 1 \leq |x|^k + 2|x| + 1$, so we are still fine.)

EDIT 2: Thinking about it some more, the verifier function is a relation $V_C \subseteq \{0, 1\}^\ast \times \{0, 1\}^\ast$ (satisfying the conditions that make it a function). The set $\{0, 1\}^\ast \times \{0, 1\}^\ast$ can be encoded as the subset $C_{\{0, 1\}^\ast \times \{0, 1\}^\ast} = \{1^{|x|}0xy \mid x, y \in \{0, 1\}^\ast\}$, and the indicator function $1_{C_{\{0, 1\}^\ast \times \{0, 1\}^\ast}} : \{0, 1\}^\ast \to \{0, 1\}$ computes the output in linear time. (It exactly includes all the strings of the form $1^n0z$, with $n \geq 0$, and $|z| \geq n$.) A Turing machine can extract $x$ and $y$ from the valid strings belonging to $C_{\{0, 1\}^\ast \times \{0, 1\}^\ast}$ in polynomial time, and follow that with whatever (polynomial) procedure that computes the verifier function. Anyways, the $\mathcal{NP}$ class can be defined building on a definition of the $\mathcal{P}$ class that only involves $\{0, 1\}^\ast \to \{0, 1\}$ functions.


texts: Algorithm for approximating convex bodies by a convex hull of ellipsoids

texts:
I am working in the field of structural engineering and I would like to find an efficient algorithm to construct an approximation (in the Hausdorff metric) of a convex body $K$ by the convex hull of $n$ ellipsoids, for some fixed $n$.  Currently I am only working in dimensions 2 and 3.

My first idea was to work in the dual space using the support function $h_K$ of $K$, which I can compute for a sample of $M$ points on the unit sphere $S_d$, and to minimize the discrete error between $h_K$ and the support function of the approximating set in the $l^{\infty}$-norm.

Does anybody have another idea or some references to give me?  I was unable to find any related work on this subject.


texts: Formal Methods Applied to Role-Based Security (RBAC)

texts:
I wonder if someone could direct me to a basic introduction to formal methods applied to role-based security.  I'm particularly interested in the question of formal verification and the kind of mathematical abstractions that would appropriately address confidentiality and / or conflicts of interest that arise from overlapping roles in a SSO (single sign-on) system.  Thanks much in advance.

PS I'm asking this question in parallel w/ conducting my own literature search.


texts: The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying assignments $F$ has. Which are the best lower bounds on #SAT?


texts: Geometric Intuition behind Locally testable codes

texts:
Conventional coding theory provides a good geometric picture behind linear error correction codes in terms of Hamming distance. What additional geometric requirement one should add to make a code locally decodable?

  In other words what channel model does locally decodable code try to solve? Where does it fit in Shannon theory?


texts: Problems complete for non-deterministic PSPACE

texts: We know that PSPACE = NPSPACE by savitch's theorem , but before that was proved , what problems were known to be complete for NPSPACE ?


texts: How long does it take to find a short cycle in a random graph?

texts:
Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges.  With very high probability, $G$ has many $4$-cycles.  Our goal is to output any one of these $4$-cycles as quickly as possible.

Supposing we have access to $G$ in adjacency list form, we can succeed with constant probability in $O(\sqrt{n})$ time as follows: pick any node $v$ and start generating random $2$-paths starting from $v$; once we find two distinct $2$-paths that share an endpoint, we are done.  There are $n$ possible endpoints, and by the birthday paradox we will succeed with constant probability after discovering about $\sqrt{n}$ of them.

Can we do better?  In particular, is a constant-time algorithm that succeeds with constant probability possible?


texts: Is this homework problem on T-joins wrong?

texts: In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.


texts: How do I store data with a query that's a approximated ?

texts:
I'm trying to find a way to store my data with fast access (better than O(n)).

My database consists of data (4096 byte strings) that represents some information about some items.
The problem is, that the query is never exact. I get one Item, and then need to find the closest match using a function F(a,b).

just an example:

1234
3456
6466
F(a,b) = return % of similar digits

GetClosest(1233,F) = 1234

The problem is that F(a,b) is a complicated algorithm, (not a proper metric).

What I have now is just go over the whole database to search for the best match.
Is there a kind of tree or other cluster database type that can give me faster finding complexity ?

More information:

F gives back a similarity value in %percentage. where 100% is a perfect match.


texts: Introductory resources on Computational Learning Theory

texts:
Recently I've been reading a decent number of CoLT papers. Although I don't struggle with the individual papers (at least not more than I usually struggle with other theory papers), I don't feel I have a good broad grasp of the field as a whole.
Is there a standard text, surveys, or lecture notes for introducing CoLT at the graduate level?
I have a basic Theory A background, but no specific knowledge of Machine Learning or Statistics. I am mostly interested in things like PAC-learning and learning automata, and less interested in things like Bayesian inference and VC theory.
Related questions

Resource / book for recent advances in statistical learning theory


texts:
The definition of Ramsey numbers is the following:

Let $R(a,b)$ be a positive number such that every graph of order at least $R(a,b)$ contains either a clique on $a$ vertices or a stable set on $b$ vertices.

I am working on some extension of Ramsey Numbers. While the study has some theoretical interest, it would be important to know the motivation of these numbers. More specifically I am wondering the (theoretical or practical) applications of Ramsey numbers. For instance, are there any solution methodology for a real life problem that uses Ramsey numbers? Or similarly, are there any proofs of some theorems based on Ramsey numbers?


texts: An upper bound for chi-square divergence in terms of KL divergence for general alphabets

texts:
In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ defined over a general alphabet $\mathcal{X}$, if $P\ll Q$, then
$$\chi ^2(P||Q):=\int_{\mathcal{X}}\Big(\frac{dP}{dQ}\Big)^2dQ$$ and
$$D(P||Q):=\int_{\mathcal{X}}dP\log\frac{dP}{dQ}.$$

I am looking for an upper bound of $\chi^2(P||Q)$ in terms of $D(P||Q)$ which works wven if $\mathcal{X}$ is uncountable.
What I need is a special case where $P=P_{XY}$ and $Q=P_X\times P_Y$, for two random variables with joint and product distributions are $P_{XY}$ and $P_X\times P_Y$, respectively. Noticing that in this case KL divergence is equal to the mutual information , I need an upper bound of chi-square divergence in terms of mutual information.


texts: What is the exact communication complexity of subtree disjointness?

texts:
A classic textbook example for communication complexity is when A and B both receive a subtree of a an $n$-node tree (that they both know), and they need to output whether their subtrees are disjoint or not. The textbook solution usually gives an algorithm with $2\log_2 n$ bits of communication. In Lovasz-Saks, however, there is a better algorithm, with $\log_2 n+\log_2 \log_2 n$ bits of communication. Where is the truth between this and the trivial $\log_2 n$ lower bound?

A natural idea is to consider the rank of the communication matrix, but this is $2n-1$ for any tree; the vertices and edges generate every subtree.


texts: Batch membership testing for convex polyhedron specified in vertex representation

texts:
I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the convex shape.  Currently I just use an open source linear programming solver for each point independently with a constant objective function.

However this is quite slow even in 100 dimensions.  Is there a way to use the fact that all the query points are known in advance to speed the process up?


texts: Reference for Dyck languages being $\mathsf{TC}_0$-complete

texts:
Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar
$$
S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon
$$
over the set of symbols $\{(_1,\ldots,(_k,)_1,\ldots,)_k\}$.  Intuitively Dyck languages are the languages of balanced parentheses of $k$ different kind.  For example, $(\,[\,]\,)\,(\,)$ is in $\mathsf{Dyck}(2)$ but $(\,[\,)\,]$ is not.

In the paper

  Dynamic Algorithms for the Dyck Languages by Frandsen, Husfeldt, Miltersen, Rauhe, and Skyum, 1995,

it is claimed that the following result is folklore:

  $\mathsf{Dyck}(k)$ is $\mathsf{TC}_0$-complete under $\mathsf{AC}_0$ reductions.

Is there any reference known for the above claim?  In particular, I'm looking for any results that shows at least one of the following:

$\mathsf{Dyck}(k)$ is in $\mathsf{TC}_0$ for arbitrary $k$.
$\mathsf{Dyck}(k)$ is $\mathsf{TC}_0$-hard for arbitrary $k$.

The closest paper I can find is

  Bi-Lipschitz Bijection between the Boolean Cube
  and the Hamming Ball, by Benjamini, Cohen, and Shinkar, 2013

which redirects me to the paper Log space recognition and translation of parenthesis languages by Lynch who proved that $\mathsf{Dyck}(1)$ (that is, normal balanced parentheses) is in $\mathsf{TC_0}$.

Any related papers are welcomed as well.  Thanks!


texts:
Assume we have computed the Pagerank of the vertices of a given graph. Then, remove a vertex from this graph, with all its edges.
How to efficiently compute the Pagerank of remaining vertices in the new graph?
Would it help to know that we remove the vertex with highest Pagerank?
I see work on edge removals in the literature, but updating after vertex removal may be faster than updating after removal of each of its edges, in particular in the the highest-Pagerank removal case.


texts: Motivation for Developing Shortest Path Simplex Algorithms

texts:
I'm reading Efficient Shortest Path Simplex Algorithms by Donald Goldfarb, Jianxiu Hao and Shen-Roan Kai who considered  "the specialization of the primal simplex algorithm to the problem of finding a tree of directed shortest paths from a given node to all other nodes in a network of n nodes or finding a directed cycle of negative length. Two efficient variants of this shortest path simplex algorithm are analyzed and shown to require at most $(n − 1)(n − 2)/2$ pivots and $O(n^3)$ time."

I'm trying to find motivation for this article and wonder isn't Bellman-Ford algorithm good enough? It works in $O(nm)$ time which and good for the type of graph which the problem above algorithm deals with.


texts: Difference between weak duality and strong duality?

texts:
For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different:

Weak  duality:
If $\bar{x}$ is a feasible solution to $(P)$ and $\bar{y}$ is a feasible solution to $(D)$, then:

$c^T \bar{x} \le b^T\bar{y}$
if equality holds in the above inequality, then $\bar{x}$ is an optimal solution to $(P)$ and $\bar{y}$ is an optimal solution to $(D)$.

Strong duality:
If there exists an optimal solution $x'$ for $(P)$, then there exists an optimal solution $y'$ for $(D)$ and the value of $x'$ in $(P)$ equals the value of $y'$ in $(D)$.

Are these two statements not saying the same thing? In other words, isn't the second statement (2.) in definition of Weak duality saying the same thing as strong duality?

Let's say we are given an LP $(P)$ and we find a dual $(D)$. Then can the same dual be used to deduce either strong duality or weak duality?


texts:
We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs.

Is this the main reason for the difficulty of computing the exponential function, or is exponentiation inherently difficult to compute, independently of this consideration?

  What is the complexity of the bit graph of the exponential function?
  $$\{\langle x,y,i \rangle \mid x,y,i\in\mathbb{N} \text{ and the $i$-th bit of $x^y$ is $1$} \}$$


texts: Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

texts:
The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as follows based on the detailed proof given in Section 1.5 of The Graph Isomorphism Problem - Its Structural Complexity.

Prove that the graph automorphism problem is Turing-reducible to the graph isomorphism problem.
Prove that the graph automorphism problem has a polynomial time computable or-function.
Prove that the graph isomorphism problem has both polynomial time computable and- and or-functions.
Combining the previous results, it may be argued that the graph automorphism problem is Karp-reducible to the graph isomorphism problem.

My question is whether similar reduciblity can be inferred for the problems under hidden subgroup representations (HSP). Let me define those representations.

Graph isomorphism as a hidden subgroup problem

Let the $2 n$ vertex graph $\Gamma = \Gamma_1 \sqcup \Gamma_2$ be the disjoint union of the two graphs $\Gamma_1$ and $\Gamma_2$ such that $Aut \left(\Gamma_1\right) = Aut \left(\Gamma_2\right) = \left\{e\right\}$ (a limited version). A map $\varphi : S_{2n} \to \text{Mat}\left(\mathbb{C}, N \right)$ from the group $S_{2n}$ is said to have hidden subgroup structure if there exists a subgroup $H_\varphi$ of $S_{2n}$, called a hidden subgroup, an injection $\ell_\varphi : S_{2n}/H \to \text{Mat}\left(\mathbb{C}, N \right)$, called a hidden injection, such that the diagram

is a commutative diagram, where $S_{2n}/H_{\varphi}$ denotes the collection of right cosets of $H_\varphi$ in $S_{2n}$, and where $\nu : S_{2n}/H_\varphi$ is the natural map of $S_{2n}$ onto $S_{2n}/H_\varphi$. We refer to the group $S_{2n}$ as the ambient group and to the set $\text{Mat}\left(\mathbb{C}, N \right)$ as the target set.

The hidden subgroup version of the graph isomorphism problem is to determine a hidden subgroup $H$ of $S_{2n}$ with the promise that $H$ is either trivial or $|H| = 2$.

Graph automorphism as a hidden subgroup problem

For a graph $\Gamma$ with $n$ vertices, a map $\varphi : S_{n} \to \text{Mat}\left(\mathbb{C}, N \right)$ from the group $S_{n}$ is said to have hidden subgroup structure if there exists a subgroup $\text{Aut}\left(\Gamma\right)$ of $S_{n}$, called a hidden subgroup, an injection $\ell_\varphi : S_{n}/\text{Aut}\left(\Gamma\right) \to \text{Mat}\left(\mathbb{C}, N \right)$, called a hidden injection, such that for each $g \in \text{Aut}\left(\Gamma\right)$, $g \left(\Gamma\right) = \Gamma$ and, the diagram

is commutative, where $S_{n}/\text{Aut}\left(\Gamma\right)$ denotes the collection of right cosets of $\text{Aut}\left(\Gamma\right)$ in $S_{n}$, and where $\nu : S_{n}/\text{Aut}\left(\Gamma\right)$ is the natural map of $S_{n}$ onto $S_{n}/\text{Aut}\left(\Gamma\right)$. We refer to the group $S_{n}$ as the ambient group and to the set $\text{Mat}\left(\mathbb{C}, N \right)$ as the target set.

The hidden subgroup version of the graph automorphism problem is to determine a hidden subgroup $\text{Aut}\left(\Gamma\right)$ of $S_{n}$ with the promise that $\text{Aut}\left(\Gamma\right)$ is either of trivial or non-trivial order depending on the type of $\Gamma$.

My questions:

I think it can be trivially shown that the hidden subgroup representation of the graph automorphism problem is Turing-reducible to the graph isomorphism problem by giving two input graphs as the original graph and the candidate automorphism of the original graph.

If I am correct, the remaining question is whether there is a Karp-reduction for the hidden subgroup representation. If there is, how it can be shown.


texts: Time complexity of exponentiating s-sparse matrices

texts:
Could someone suggest me a reference which discusses the time complexity of algorithms meant for exponentiating (finding $e^A$ approximately given $A$) s-sparse matrices, along with their error rates?

P.S: I'm mostly interested in Hermitian matrices $A$.


texts: Why go to theoretical computer science/research?

texts:
I'm currently starting on the university [computer science] and there we have lot of opportunities to begin with researching. Before finding this website, I had no intention to go on this way [I wanted to work with AI, probably game dev.], but now I can [or I need] to make a choice.

Can you convince me to join on this "world"? What "segments" I can follow? Is there anything about what kinds of topics a computer scientist or researcher works on?


texts: Which complexity class does this problem belong to?

texts:
Consider the following problem $\mathcal{P}$.

Instance: A Boolean formula $F$ of $n$ Boolean variables ($x_1,...,x_n$) and $m$ Boolean parameters ($b_1,...,b_m$) where $0 \leq m \leq n$.

Problem: Find an assignment $b_1^*,...,b_m^*$ to the parameters $b_1,...,b_m$ such that the number of satisfying assignments to the variables $x_1,...,x_n$ of $F(b_1/b_1^*,...,b_m/b_m^*)$ is minimum.

For example, $F = \{((x_2 \lor x_3) \leftrightarrow x_1) \lor (x_1 \leftrightarrow b_1 \land (x_2 \lor x_3) \leftrightarrow \neg b_1)\} \land \{((x_1 \land \neg x_2) \leftrightarrow x_2) \lor (x_2 \leftrightarrow b_2 \land (x_1 \land \neg x_2) \leftrightarrow \neg b_2)\} \land \{x_1 \leftrightarrow x_3\}$ where $n = 3$ and $m = 2$.

If $(b_1^*,b_2^*) = (0,0)$, then the number of satisfying assignments of $F(b_1/b_1^*,b_2/b_2^*)$ is 2.

If $(b_1^*,b_2^*) = (0,1)$, then the number of satisfying assignments of $F(b_1/b_1^*,b_1/b_2^*)$ is 3.

Here, I consider the constructive version $\mathcal{P}_C$ of $\mathcal{P}$ (i.e., the output of $\mathcal{P}_C$ includes the optimal assignment to $b_1, ..., b_m$ and the minimum number of assignments to $x_1, ..., x_n$). When $m = 0$, $\mathcal{P}_C$ is equivalent to #SAT, which is known as #P-complete. Thus, $\mathcal{P}_C$ is #P-hard. However, it is insufficient to conclude that $\mathcal{P}_C$ is #P-complete.

Which complexity class does this problem belong to (#P or other one)? If it does not belong to #P, please give me a proof.


texts:
Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(n^{3+\epsilon})$ [1]. What is the current state of research on this problem? Is anything more recent than the references in [2] known?

[1] Almost tight upper bounds for lower envelopes in higher dimensions.

[2] http://cs.smith.edu/~orourke/TOPP/P3.html


texts: Largest "non-disturbing" subset in a graph

texts:
The definition:

  The subset of vertices in a graph is called "non-disturbing" if any two vertices from this subset could be connected by a path not passing through other vertices of this subset.

Informally speaking, any two members must have a way to speak to each other without disturbing other members.
And we want to put as many members in a graph as we could.

My question is:
Is an algorithm known for building largest non-disturbing subset of a graph?

I'm especially interested in solving this task for n-dimensional hypercube (having 2^n vertices).
n is from 1 to 64.
By paper-and-pencil approach I could find solutions for small n:
for n=1 we could have 2 members,
for n=2 we could have 3 members,
for n=3 we could have 5 members,
for n=4 we could have 10 members.

But I doubt that, for example, the case n=16 would be brute-forcible.


texts: Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials?

texts:
Arora and Barak define NP-completeness as the following:

"We say that a language $A \subseteq \{0, 1\}^∗$
is polynomial-time Karp reducible to a language
$B \subseteq \{0, 1\}^∗$
denoted by
$A \leq_p B$ if there is a polynomial-time computable function $f : \{0, 1\}^∗ \rightarrow \{0, 1\}^*$
such
that for every $x \in \{0, 1\}^∗$, $x \in A$ if and only if $f(x) \in B$.
We say that B is NP-hard if A $\leq_p$ B for every $A \in NP$. We say that B is
NP-complete if B is NP-hard and $B \in NP$."

However, something about this is not clear to me: if B is NP-hard, does that mean for all languages $L\in NP$, there is a single fixed polynomial $q$ such that the associated function $f$ is computable in time $q(n)$? Or does it mean for each language $L\in NP$, the function $f$ is computable in time $q_L$, where $q_L$ is a polynomial depending on the language. These polynomials $q_L$ can be arbitrarily large.


texts:
Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula where you need to run over all conjugacy classes of the symmetric group $S_n$ and the number of conjugacy classes in $S_n$ is the number of partitions of the number $n$ known to behave like $\exp (\sqrt n )$.  (There is a famous approximation for the partition function by Hardy and Ramanujan and subsequent expansions.)

Question 1: Is there a better algorithm? Can you improve the number of steps below $\exp (\sqrt n)$?

(Actually, I would be interested also by a different algorithm even if not better.)

While at it:

Question 2 (updated):  What is the smallest number of arithmetic operations for an algorithm to count the number of partitions of an integer $n$?

(I asked originally about a better than $\exp (\sqrt n)$ time algorithm for counting the number of partitions of an integer n, but Sasho indicated an $O(n^{3/2}$ algorithm.)

Question 3: Since Questions 1 and 2 are questions with a "tiny input" (a single integer $n$)  is computational complexity theory adequate to ask and offer useful answers (reductions etc.) to these (and similar) question?

Question 4: How much better can you do if you want only to approximate the number of isomorphism types by Polya theory or by other means?

Question 5: What is the complexity of sampling precisely or approximately isomorphism types of graphs with $n$ vertices?

Question 6: What is the complexity of questions 1,4,5  if instead of dealing with all graphs on $n$ vertices we deal with subgraphs of an input graph $G$ with $n$ vertices. (This makes these problems ordinary "big input" problems. Here, I am not aware of a $\exp (\sqrt n$) algorithm.

Question 7: Are these problems related in some way to the graph isomorphism problem?


texts: Explicit mu-recursive expression for Ackerman function

texts:
Can you please point out how to build Ackerman function (actually I'm interested in a version proposed by Rózsa Péter and Raphael Robinson) via standard mu-recursive operators? I tried original papers by Péter and Robinson, but Péter's paper use a language different from English and Robinson's papers “Recursion and Double Recursion” and “Primitive Recursive Functions” also don't help: first of them seems more relevant, but is uses so called double recursion operator to define Ackerman function, so in this case explicit definition of the operator in mu-recursive terms is seeked.

Most closely to the answer goes P. Smith in “An introduction to Godel's theorems” (CUP, 2007) (29.4 The Ackermann-Peter function is μ-recursive), but he comes up with the following: “making the argument watertight is pretty tedious though not difficult. There’s nothing to be learnt from spelling out the details here: so we won’t.”

I also tried Rózsa Péter's book “Recursive functions” (1967, Academic press). There are plenty of variants for recursion operators given there. Usually one reduces to other. I believe that there is a type of recursion operator which fit for definition of Ackerman function and sequence of steps which reduce it to primitive redursion and minimisation operators, but I found myself unable to investigate the whole way down.


texts: looking for notable applications of ASP (Answer Set Programming) in TCS

texts:
a recent difficult question of interest to the group[1] by GB has possibly led to verification of a new graph property by dspyz, by use of Answer Set Programming/ASP. via sophisticated logic principles/algorithms remarkably this software can verify a complex property of graphs apparently without enumerating all isomorphisms. there does not seem to be much prior ref to this software & logic/theorem proving research on tcs.se.

  looking for notable papers that use ASP from a TCS pov to investigate important problems in the area.

even better would be anything that relates it to inductive proofs of graph properties in automated theorem proving.[5] (some misc refs [2-4] to the software utilized are included below.)

[1] Transitive feedback arc set (TFAS): NP-complete?
[2] Potassco: The Potsdam Answer Set Solving Collection Gebser et al
[3] Potassco/sourceforge
[4] ASP tools users guide Gebser et al
[5] techniques or examples of analyzing a series of graphs, tcs.se


texts: Terminology about computation and Finite algebra

texts:
I am looking for the name of something that may have one.

A finite algebra $\mathcal{A} = (E, \{f_1, f_2, \ldots, f_k\})$ is a non-empty set $E$ together with some functions $f_i$ from $E^{r_i} \to E$ where $r_i$ is a fixed integer (arity).

An $n$-term is a term on $n$ variables $x_1, \ldots, x_n$ over a finite algebra $\mathcal A$. A term is defined as usual by induction:

Any element of $E$ and the variables $x_1,\ldots, x_n$ are terms
If $t_1, \ldots, t_{r_i}$ are terms, then $f_i(t_1,\ldots, t_{r_i})$ is also a term.

An $n$-term $t$ computes a function $[t]\colon E^n \to E$ in an obvious way.

Terminology question: How do we call finite algebras such that for every function $f\colon E^n\to E$, there exists a term $t$ such that $[t] = f$?

Famous example:
 $$(\{0, 1\}, \{\land, \lor, \lnot\})$$

Famous co-example:
 $$(\{0, 1\}, \{\land, \lor\})$$


texts: Practically Good Algorithms of a Very Low Computational Complexity Class

texts:
I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties:

1) Solving the problems in $\cal A$ exactly or even approximately is computationally quite hard as a function of the input size $n$.    (What I have especially in mind is that it is P-complete, or as hard as solving linear equations, etc. but examples where approximating $\cal A$ is in another CC class are also welcome.)

2) For a fixed $t$ the algorithms in $P_t$ are computationally easy. (Here I am thinking about bounded depth circuits of various kind, maybe also $NC^1$ or $NC$.)

3) The relation between $t$ and $n$ is such that $P_t$ is a practically good algorithm  (at least in some interesting regime for the input) for approximating solutions for problems in $\cal A$. Perhaps even coming close to our best available algorithms for approximating algorithm for the class $\cal A$ in some interesting regime.

So another way to put it: Are there practically good algorithms for approximately solving linear equations, computing determinants, linear programming, etc which are asymptotically in a very low computational complexity class - say bounded-depth computation?

The algorithmic question can be a decision problem, an optimization problem,  a sampling problem, or a problem of some other kind. (My motivating example came from a sampling problem.)


texts: Determining the Class of a given Cellular Automata structure

texts:
Is it possible to write an algorithm that can determine the class of a given cellular automata structure ? (ie. Wolfram's 4 Classes)

Thank you

Ricky


texts: What is the "right" definition of upper and lower bounds?

texts:
Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.

So, what is the lower bound of the problem? The way I understood it is just the lower bound of $f(n)$. But we know that $f(n) = \Omega(n^2)$ implies that there exists constant $k$, $n_0$ such that for all $n > n_0$, $f(n) > kn^2$, which is not true. Thus it seems that we can only say $f(n) = \Omega(n)$.
But usually, we will call the problem has a lower bound of $\Omega(n^2)$, right?
Assuming that $g(n) = \Omega(n^2)$, which means that there exists constant $k$, $n_0$ such that for all $n > n_0$, $g(n) > kn^2$. Let's also assume a problem has running time $g(n)$. If we can reduce this problem for all the primes $n$ to another problem (with same input size), can we say the running time of the other problem has a lower bound of $\Omega(n^2)$?


texts: What's the point of stack judgement in CBPV?

texts:
Call-by-push-value (CBPV) introduces two main families of types, values and computations, and their corresponding judgements. However, in some extensions/variants/adaptation of CBPV, there is a third judgement: stacks. What is the purpose of this judgement? Why it was not present in the original CBPV? What do we gain when we introduce them?

The kind of extensions I am talking about are for example Levy's CBPV with stacks, or Egger et al.'s Enriched Effect Calculus, or the calculus in Ahman et al.'s Dependent Types and Fibred Computational Effects.


texts: P vs NP: Instructive example of when Brute Force search can be avoided

texts:
To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately understandable and the trick should neither be too easy nor too hard.

The best I've come up with so far is

SUBSET_PRODUCT_IS_ZERO

The problem is easy to understand (given a set of integers, can a subset with product 0 be formed?), but the trick is too easy (check if 0 is among the given numbers, i.e. it's not necessary to look at a lot of subsets).

Any suggestions?


texts: What can I do to supplement my theoretical undergraduate CS curriculum so that I can increase my value in industry & academia?

texts:
As most well-known universities are, my university also has a theoretical-based CS curriculum where the classes either teach straight-up theory, or teach you how to implement systems rather how to use them effectively.

I originally came into CS hoping for knowledge about how the world works (in a practical sense) so that I'd be able to see opportunities & advantages in every corner (if you know what I mean). So I was hoping that I could streamline what I'm learning in my courses to optimize it toward this goal.

I need some suggestions on what skills or knowledge I should accumulate before I graduate and apply for graduate school, or get a job in industry (hopefully more than just programming). Basically, I'm looking for a good direction.