texts:
I have N elements and need to find the maximum of these elements. At each time tick, exactly one of the N elements is updated and I need to determine the new max element (more specifically, the index of the max element). How can I do this by accessing as little "state" as possible?

The naive approach is to store all N elements and in each tick read the N elements and determine the max element. Here the amount of "state" accessed corresponds to N elements.

Is it possible to determine the max element by maintaining lesser state -- specifically state that grows sub-linearly as N increases? Essentially I do not want to make a pass on the entire set of N elements. Assume N is a fixed number.

It seems like this problem has the flavor of data streaming algorithms like the count(-min) sketch. We have N buckets -- items being streamed in update the count of one of these N buckets -- and wish to perform some query on these N buckets with sub-linear space usage.

I understand how sketches can be used to query the value of the Nth bucket, but do not understand if it can be extended to obtain an estimate for the max value (and specifically, the index of the max element). The heavy hitters problem outputs items above a certain frequency, but I am interested only in the item with the maximum frequency.

Am I over-thinking this problem? Is there a far simpler solution?


texts: On the need for a self-correcting function in the PCP theorem

texts:
Original proof of the PCP theorem, uses self-correction property of linear functions.
Assume we have $f: \{0,1\}^n \rightarrow \{0,1\}$, a function or table of values,
that is $(1-\delta)$-close to some linear function $L$.
Using $f$ we would like to compute $L(x)$ for any desired $x$ with high accuracy. Such a
procedure is called a self-correction procedure since a small amount of errors in the table $f$ can be corrected using probes only to $f$ to provide access to a noise-free version of the linear function L.

Procedure $\text{SelfCorr}(f,x)$ is:

Select $y\in\{0,1\}^n$ uniformly at random.
Return $f(x+y)−f(y)$

One can prove if $f$ is $\delta$-close to a linear function $L$ for some $\delta<1/4$, then for any $x\in\{0,1\}^n$ the above procedure $\text{SelfCorr}(f,x)$ computes $L(x)$ with probability at least $1−2\delta$.

My question is: Why we don't probe $f$ at $x$ directly. By this way, error of procedure is at most $\delta$ (that is better than $2\delta$ error of $\text{SelfCorr}(f,x)$)?


texts: How short can reversible representations of the n-bit primes be?

texts:
For $\: 1 < n \:$ and $\: n^{o(1)} < \sigma \leq n \:$, $\:$ how small can $L$ be for there to be for there to be an

efficiently computable (deterministic) function $\;\; f \: : \: \{0\hspace{.01 in},\hspace{-0.03 in}1\}^L \: \to \: \{n\text{-bit primes}\} \cup \{\perp\} \;\;$  and

an efficiently computable randomized algorithm $g$ from $\: \{n\text{-bit primes}\} \:$ to $\: \{0\hspace{.01 in},\hspace{-0.03 in}1\}^L \:$ such that,

for $\: U\in \{0\hspace{.01 in},\hspace{-0.03 in}1\}^L \:$ and $\: p\in \{n\text{-bit primes}\} \:$ uniformly distributed, the statistical distance

between $\:\langle U\hspace{-0.02 in},\hspace{.01 in}f(\hspace{.005 in}U\hspace{.01 in})\rangle\:$ and $\:\langle \hspace{.005 in}g(\hspace{.03 in}p)\hspace{.01 in},p\rangle\:$ is less than $\hspace{.03 in}2^{-\sigma}$ ? $\;$ (Everything is parametrized by $n$.)

This is relevant to cryptography, when using a common random string to specify a prime.

The best I can come up with is, have $p$ be the largest prime such that $\: $$p\hspace{.01 in}\#$$\:< 2^n \:$, use the

Chinese Remainder Theorem and a greedy algorithm to sample from the numbers in $\: \left[2^{n-1},2^n\right) \:$

all of whose non-$1$ factors are larger than $p$, and then test them for primality.

(When one finds a prime, output it. $\:$ If one runs out of randomness instead, then output $\perp$.)


texts: Conservative Approximation of Kleene-Mycroft Iteration for Polymorphic Recursion?

texts:
To perform type inference in the presence of polymorphic recursion, one can use a Kleene-Mycroft iteration to compute the principal type of an expression. To type $\mathsf{fix}\ f\ldotp e$, we define $F(\sigma)$ as the principal type of $e$ under the assumption that $f : \sigma$. We can then define $\sigma_0 = \forall a \ldotp a$ and $\sigma_{i+1} = F(\sigma_i)$, until we reach a fixed-point $\sigma_k$. This $\sigma_k$ is then the principal type of $\mathsf{fix}\ f\ldotp e$.

There are two key issues with this:

Inference with polymorphic recursion is undecidable, so this iteration may not always reach a fixed-point.
The approximation at each stage of the iteration is not sound: if we quit after $j<k$ iterations, not only will $\sigma_j$ not be the principal type of $\mathsf{fix}\ f\ldotp e$, but it will not be a type of $\mathsf{fix}\ f\ldotp e$ at all, since we made too strong of an assumption about the type of $f$ when checking $e$.

I'm wondering if there's a standard way to soundly approximate polymorphic recursion: that is, to iterate some number of times, and afterwards, obtain a type that is possibly less general than the principal type, but that is nevertheless a valid typing of $\mathsf{fix}\ f\ldotp e$.

For example, one can imagine the Hindley-Milner approximation, where we type $e$ under the assumption that $f$ has a monomorphic type, as being the 0-ary approximation. We may fail to find a typing for an expression that requires polymorphic recursion, but if we find a type, we know that it is a valid typing of the expression.

Does such an approximation exist?


texts: Natural candidates for the hierarchy inside NPI

texts:
Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems conjectured to be $\mathsf{NPI}$ here.

Ladner's theorem tells us that if $\mathsf{NP}\neq\mathsf{P}$ then there is an infinite hierarchy of $\mathsf{NPI}$ problems, i.e. there are $\mathsf{NPI}$ problems which are harder than other $\mathsf{NPI}$ problems.

  I am looking for candidates of such problems, i.e. I am interested in pairs of problems
  - $A,B \in \mathsf{NP}$,
  - $A$ and $B$ are conjectured to be $\mathsf{NPI}$,
  - $A$ is known to reduce to $B$,
  - but there are no known reductions from $B$ to $A$.

Even better if there are arguments for supporting these, e.g. there are results that $B$ does not reduce to $A$ assuming some conjectures in complexity theory or cryptography.

Are there any natural examples of such problems?

Example: Graph Isomorphism problem and Integer Factorization problem are conjectured to be in $\mathsf{NPI}$ and there are argument supporting these conjectures. Are there any decision problems harder than these two but not known to be $\mathsf{NP}$-hard?


texts: Prove algorithm non-existence: keep order of items with single item modification

texts:
On Stackoverflow, user asked a question about a data structure that would allow to keep an ordering for a set of items, with the condition of limited memory and only one item can be modified at a single operation. My feeling is that such an algorithm does NOT exist, but have no clue how to prove that.
First I tried to formalize the OPs requirements on the algorithm:

The data structure keeps an order of given item set, i.e. one of n! permutations.
Now the hard part comes. Not sure how to formalize that single item modification. We perhaps need to assume that the data structure keeps one of O(n) possible values for each item. This matches both the numbering algorithms linked list algorithms mentioned in the OPs question, and many more (tree data structures etc.).
Then say we have function f(data structure) that will return the order (permutation) of all the items.
Then suppose we have an operation which is a function data_structure_after = op(data_structure_before) that will just change the position of one existing item relatively to the other items. During the operation, only value of one item can be changed.

We want to prove that such algorithm doesn't exist.
I got totally stuck here. It is totally clear why the numbering solution in the OPs question will not work, because it will break if you for example have items A, B, and C and keep putting the last item between the first two. It is also clear that linked list solution will break on the single item modifictaion requirement. But to prove non-existence, we must use much more general approach!
Maybe somehow start from the fact that f has O(n^n) input values and n! output values, and during each operation input values can only change for one item, thus O(n) possible changes, has to produce n changes at the output, so if we imagine this as a graph we have limitations of the number of edges going from each vertex... maybe use graph theory here. Then construct some infinite row of operations as a contra example that will either break on the single item modification requirement (like the linked list solution) or on the O(n) requirement for the set of item values (like the numbering solution).
This was the basic idea but I am totally clueless how to actually perform the proof.


texts: Regularity of language with finite number of right derivatives

texts:
I found this statement listed as a theorem in a textbook:

  If L ⊆ Σ∗ is any language, then L is regular iff it has finitely many right derivatives. Furthermore, if L is regular, then all its right derivatives are regular and their number is equal to the number of states of the minimal DFA’s for L.*

Unfortunately, no proof was provided. Why is this statement true?


texts: Efficiently computing propagation values for only a few positions in a grid

texts:
Consider a matrix filled with some nodes containing positive integers ("starts"), some nodes marked as a wall, and the rest of the nodes given a value of infinity.

The propogation rule is simple: For each node, check if any of its 4 neighbors' values are greater than the current node's value plus one. If so, set their value to this node's value plus one. If that neighbor is a wall, don't modify it's value (walls are always infinity). Repeat until no more propagation occur.

Given $O(1)$ nodes, is it possible to compute their final propagation values in asymtotically less than $O(nm)$ time?

Edit:

Formally, consider the following simple rule for propagation: Given a matrix $M \in \mathbb{N}^{n\times m}$, and set of starts $S \subset \{(x, y, val) \in \mathbb{N}^3 | x<n, y<m\}$:

Set all elements in the matrix to $\infty$, then $\forall s \in S, M(s_x, s_y) = s_{val}$. Assume WLOG that there aren't more than one $s \in S$ for each $(x, y)$.
For every $(x, y)$ such that $M(x, y) \neq \infty$, set all surrounding nodes $M(x + 1, y)$, $M(x - 1, y)$, $M(x, y + 1)$, $M(x, y - 1)$ that have values greater than $M(x, y) + 1$ to $M(x, y) + 1$. (if that surrounding node is not in the matrix, ignore it)
Repeat 2 until the grid is full and no more propagation can occur.

I am interested in computing the resulting value for $O(1)$ goal nodes in asymptotically less time then the $O(nm)$ time it takes to propagate outwards.

If there is only one start, call this start $s$, and the resulting $M(x,y)$ for any node can simply be found with the modified Manhattan distance $M(x,y)=|s_x−x|+|s_y−y|+s_{val}$ which takes $O(1)$ time.

If there is more than one start, $M(x,y)=\min\limits_{s \in S} |s_x−x|+|s_y−y|+s_{val}$, so the resulting $M(x, y)$ can be found in $O(|S|)$ time. This can be improved to $O(log(|S|))$ if $S$ are prepossessed into a quadtree beforehand, but this is only helpful is $|S|$ is less then our number of goal nodes.

That piece is trivial though. So next, consider if we augment the problem with walls that don't allow any propagation through them. Formally, walls $W \subset \{(x, y) \in \mathbb{N}^2 | x<n, y<m\}$ that don't allow their value to be modified in step 2.

With walls, is it possible to compute the value of any $O(1)$ goal nodes in asymptotically less than $O(nm)$ time?


texts: Why is $\{0,1\}^n$ referred to as the Boolean hypercube?

texts: I used to view it just as a set of bit strings of length $n$. What does it mean for it to be the Boolean hypercube? Does viewing it from the hypercube perspective give a useful insight in a certain context?


texts: How is the complexity of PCA $O(\min(p^3,n^3))$?

texts:
I've been reading a paper on Sparse PCA, which is:
http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf

And it states that, if you have $n$ data points, each represented with $p$ features, then, the complexity of PCA is $O(\min(p^3,n^3))$.

Can someone please explain how/why?


texts: Find optimal room from which to visit all other rooms in a rectangular floorplan

texts:
Suppose we have an orthogonal polygon with holes (all walls are axis-parallel).  All vertices can be on integer coordinates, if that helps.  Partition the polygon into rectangular rooms.  I would like to find the best room to start from, to visit all the rooms (rectangles). There's a limitation on my movement: in any room, I can only leave by two directions, say north and west. (Here best means there would only be one source in the plane dual graph with directed edges showing how to walk from room to room. If more than one source is required, I wish to minimize them.)

I have been looking at art gallery problems, and at VLSI papers on building rectilinear floorplans from network flows, and they are all tantalizingly close but far.  Can anyone provide suggestions so I can focus my search/proof construction?

EDIT to fix problem pointed out by Peter Taylor.  I can choose two directions per room. (probably they need to be adjacent, so NE is ok but NS is not.)  If I enter one room northward, I am automatically choosing South as one of thst new room's directions. (so only two in or out directions per room)  If I choose a  direction, and there are multiple rooms adjacent in that direction, I can enter all of them (and all of them then have the reverse direction assigned as one of their two directions), so the naive greedy approach would be to choose the direction that maximizes the number of rooms I can enter at that stage. I hope this is now complete, and understandable.


texts: Given a Boolean formula, does there exist a small circuit that computes a satisfying assignment?

texts:
The 3-SAT problem can be defined as follows:

  3-SAT

  Input: A 3-CNF formula $\phi$ of size $m$ with $n$ variables.

  Question: Does there exist a variable assignment that satisfies $\phi$?

Consider the following parameterized problem that is a variantion of 3-SAT:

  CVA: Compressed variable assignment problem

  Input: A number $k$ and a 3-CNF formula $\phi$ of size $m$ with $n$ variables.

  Question: Does there exist a circuit $C$ of size at most $k\log(n)$ that computes a variable assignment that satisfies $\phi$?

Note: By circuit size, I mean the number of bits in the circuit's binary encoding where the circuits have bounded fan-in.

Below I will share some questions and results about the CVA problem.

Question 1: Do you happen to have any references to this problem or know of any related variants of SAT?

Question 2: How quickly can we solve the CVA problem in terms of parameters $m$, $n$, and $k$?

  The brute force approach for solving this problem is to enumerate all
  circuits of size $k\log(n)$ and compute their corresponding
  assignments.  For each assignment, we check if it satisfies $\phi$.
  This should take roughly $m \cdot n^k \cdot k\log(n)$ time.

Question 3: What is the parameterized complexity of this problem?  How does it relate to other parameterized problems, the $W$ hierarchy, and other complexity classes?

  It's worth noticing that the CVA problem is harder than a
  variation of the minimum circuit size problem found here:
  Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$

  In particular, given a number $k$ and a bit string $x$, we can build a
  trivial 1-SAT formula $\phi$ that is only satisfied by $x$.  Then, $x$
  can be computed by a circuit of size $k\log(n)$ if and only if $\phi$
  has a satisfying assignment that can be computed by a circuit of size
  at most $k \log(n)$.

Question 4: Does looking at compressible satisfying assignments have any practical significance?  Has anyone ever measured the compression ratio of satisfying assignments for a collection of SAT instances that have come up in practice?


texts: Sample complexity for learning Boltzmann Distribution parameters

texts:
I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision.
Suppose that there are $N$ possible states of the world, with the probability of state $i$ being observed equal to
$$Pr(i | \theta) = \frac{e^{-\theta_i}}{ \sum_{i=1}^N e^{-\theta_i}}.$$
I don't know what the values of $\{\theta_i\}_{i=1}^N$ are, but I can sample independent observations from the set $\{1,\dots,N\}$ of possible states of the world, distributed according to the distribution $Pr(i)$ given above.
Let's say I draw $m$ observations $X_1,...,X_m \in \{1,...,N\}$, and define  the maximum likelihood estimator
$$\widehat{\theta} = \arg \max_{\theta'}  \sum_{j=1}^m  \log Pr(X_j | \theta)$$
When $m \to \infty$, then  $\widehat{\theta} = \theta$. However, I'm not sure how many samples $m$ I would need to ensure that the estimate $\widehat{\theta}$ is probably approximately correct. That is, how large does $m$ need to be in terms of $\epsilon,N,\delta$ to ensure that   $Pr ( \| \widehat{\theta} - \theta \|_{\infty} > \epsilon ) < \delta$?


texts:
We have a set of bit sequences of length $L$ with only $K$ known bits and $L-K$ gaps.
We want to store them in a data structure in a way that given a new bit sequence $x$ of length $L$, with $L$ known bits, we can efficiently search and retrieve the elements in the data structure that are sub-strings of $x$. What data structure and search method do you recommend?

for example, $L=5$, $K=3$, and data=${1.10., 11..0, 10..1, 01.1., 101..}$
given $x=10101$, following elements are returned: ${1.10., 10..1, 101..}$

In a more realistic example, we expect L=15, K=7, |data|=100,000, our priority is search time, however, the data structure (/index) size should be reasonable too (lets say smaller than 1GB)

This question was originally asked at math.stackexchange: link

EDIT: We are also interested in the more general case where data elements re nucleotide sequences (using alphabet {${A,C,G,T}$} instead of binary sequences). The main difference in that case is that number of all sequences of length L, will be $4^{L}$ instead of $2^{L}$ for binary.


texts:
I am reading a paper which is mainly about Dobrushin's contraction coefficient and its generalization. In page 27, the following is defined:
Consider an arbitrary, non-negative, convex function $\psi:\mathbb{R}\mapsto \mathbb{R}$ with $\psi(0)<1$. Then for an integrable random variable $X$
$$||X||_{\psi}:=\inf \{c>0:~\mathbb{E}[\psi(\frac{X}{c})]\leq 1\}.$$

Then letting $\psi^*$ be the convex conjugate of $\psi$, we can write the following for arbitrary random variables $X$ and $Y$ by Young's inequality:
$$XY\leq \psi(X)+\psi^*(Y)$$ and hence,
$$\mathbb{E}[XY]\leq 2||X||_{\psi}||Y||_{\psi^*}.$$

First of all, in the typical definition of Orlicz norm, it is assumed that $\psi(0)=0$ and also $\psi$ is non-decreasing. Why are those properties removed here?

Secondly, the last inequality is not clear to me. Can anybody proivde a hint on how to show that?


texts:
Background

I was looking for a formulation of 'free sets' and 'independent sets' from linear algebra that would extend to groups. This question was considered here but I couldn't find a satisfactory definition in the literature so I'd like to suggest the following simple approach. Let $G$ be a finite group, and for each $x \in G$ let $o(x)$ denote its order, i.e. the smallest positive integer $p$ such that $x^p = 1_G$.

Core definitions

Let $X = \{x_1,\ldots,x_k\}$ be a $k$-subset of $G$ and let $A_k = \{a_1,\ldots,a_k\}$ be the $k$-letter alphabet. Let $\Sigma_k$ denote the free monoid generated by $A_k$, and let $\Pi_k = \prod_{i \in [k]} \mathbb{Z}_{o(x_i)}$ viewed as an abelian group. Consider the homomorphism $\phi_k : \Sigma_k \rightarrow G$ that maps each $a_i$ to $x_i$, and consider the homomorphism $\psi_k : \Sigma_k \rightarrow \Pi_k$ defined by $(\psi_k(w))_i = |w|_{a_i}$. We can then give the following definitions:

(1) $X$ is a 'generating set' of $G$ if $\phi_k$ is surjective;

(2) $X$ is a 'free set' of $G$ if there exists an homomorphism $\eta_k : Im(\phi_k) \rightarrow \Pi_k$ such that $\psi_k = \eta_k \circ \phi_k$.

We observe that some properties from linear algebra carry over to this setting. For instance, any superset of a generating set is also generating, and any subset of a free set is also free. We may then define a 'free generating set' of $G$ the obvious way. Note that such a set may not exist, but when $G$ does admit a fgs we may define $rank(G)$ as the cardinality of this set.

Basic remarks

Similar to linear algebra, it turns out that two fgs always have the same cardinality. Here is a proof sketch for a special case. Suppose for contradiction that $G$ had two fgs $X,Y$ with $k = |X| < |Y| = l$, and suppose for simplicity that each element of $X \cup Y$ has the same order $p$. Consider the surjective mapping $\phi_k : \Sigma_k \rightarrow G$ obtained from $X$, and the surjective mapping $\phi_l : \Sigma_l \rightarrow G$ obtained from $Y$. As $Y$ is free, we obtain an homomorphism $\eta_l$ by (2).

Given an element $x_i \in X$, there is a word $w_i \in \Sigma_l$ such that $\phi_l(w_i) = y_i$. Define the $k \times l$-matrix $M$ by $M_{i,j} = \eta_l(x_i)[j] = |w_i|_{a_j} \mod p$. For every $z \in G$, we can then write $\eta_l(z)$ as a combination of the column vectors of $M$. It follows that the image of the $\eta_l$ must be included in the subspace spanned by $M$ and thus has size at most $p^k$; therefore $\eta_l$ cannot be surjective contradicting the assumption that $Y$ is free.

Some examples follow. For a finite abelian group $G$, we know that it is isomorphic to a product $\mathbb{Z}_{n_1} \times \ldots \times \mathbb{Z}_{n_k}$ and then $rank(G) = k$. For the permutation group $S_n$, it can be seen that $rank(S_n) = n-1$ as the transpositions form a free generating set; indeed, for a permutation $\pi \in S_n$ we can define a tuple $\eta(\pi) = (s_1,\ldots,s_{n-1}) \in \mathbb{Z}_2^{n-1}$, where $s_i = 0$ if $\pi(i) < \pi(i+1)$ and $s_i = 1$ otherwise. More generally, if $G \subseteq S_n$ is a permutation group, I conjecture that a free generating set can be obtained by the Schreier-Sims algorithm.

Questions

is it possible to adapt the above proof to handle distinct orders? if so, what part of linear algebra carries over to this setting?
if we can compute the rank for permutation groups as suggested above, are there other, presumably infinite, groups for which this is doable efficiently?
are there any algorithmic applications of this notion to problems involving graphs or permutations?


texts: Algorithms for factorization using the decision version

texts: Are there any practical algorithms for integer factorization that work by solving the decision version of the problem $\log N$ times to isolate a factor? Or is the decision version of only theoretical interest?


texts: Correlation between noise resilience and output distribution of Boolean circuits

texts:
Given a randomly generated AND/OR tree (and negations), we can calculate the probability that the circuit will represent a specific Boolean function up to 3 input literals. Starting from 4 (or at least 5) literals, the system of equations becomes too complex to compute, and it's even questionable whether the output distribution of Boolean functions can be reliably approximated. See D. Gardy, Random Boolean Expressions, chapter 3.4.3.

Another line of research deals with the question of how robust Boolean circuits are in the presence of noise or faulty gates. See P. Gács, A. Gál, Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates and A. Mozeika, D. Saad, On reliable computation by noisy random Boolean formulas who explicitly consider random Boolean formulas.

My question is if there is correlation between the probability/frequency of a certain Boolean function and the resilience of a given generating circuit (formula) against noise. In other words, can we estimate (or at least get some bounds on) the probability of a function from the circuit's noise resilience which we could try to measure by causing arbitrary perturbations to gates and see how the resulting function reacts?

My intuition is that circuits representing simple Boolean functions with high probability such as the tautology TRUE or the output of a single literal will tolerate higher noise levels since those circuits have a higher "density" in the space of all possible circuits of a given size.


texts:
After reading this question and David's answer I thought a more general question asking for tips would be useful. So

  how can authors make (and write) a paper stronger?


texts: Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?

texts:
Let's say I had an optimization problem

$$ \min_{x \in D} f(x) $$

Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist.

Imagine I had a polynomial time algorithm that - given $f$ - could provide me with an interval for the optimal objective function value $f^*$ using finite numbers $LBD$ and $UBD$ where $LBD < f^* \leq UBD$.

Could I use this to show that the $\epsilon$-evaluation problem can be solved in polynomial time? Here the $\epsilon$-evaluation problem is a problem that for any $\epsilon > 0$ finds a real number $z$ such that $f^* \leq z \leq f^* + \epsilon$.

For the purposes of this problem, we can assume that I have a computer that can store real numbers and perform exact elementary operations with them.


texts: Deciding if a language induced by a Presburger formula is context-free

texts:
Is the following problem decidable?

  Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ over alphabet $\{a_1, a_2, \dots, a_n\}$ is context-free.

For example, this covers asking if languages such as $\{a^i b^j c^{i+j}\}$, $\{a^i b^j c^i d^j\}$, $\{a^n b^n c^n\}$, $\{a^i b^j c^k: i\neq j, j \neq k, i \neq k\}$ are context-free.


texts: Advances towards proving the Held-Karp conjecture for TSP

texts:
I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture.

The Held-Karp relaxation is conjectured to have an integrality gap of $\frac{4}{3}$ for symmetric TSP.

There have been some recent advances in proving this conjecture. Among these include the 4/3 conjecture for metric TSP was proved for cubic and subcubic graphs by Boyd et. al. http://arxiv.org/pdf/1107.1052v1.pdf.

Furthermore, for the class of graphs that are degree-3 bounded and are claw-free, the Held-Karp relaxation yields a 4/3 approximation ratio as proven by Momke et. al. : http://arxiv.org/abs/1104.3090.

Then, Qian et.al. (http://arxiv.org/abs/1107.1630) proved that for a special case of graphs with all edges have cost $1$ or $2$, there exists a bound of 10/9.

I would very much appreciate if anyone with more expertise in this research topic would point out other recent research advances in proving the Held-Karp conjecture. Links and/or titles to research papers would be very helpful.


texts: A possible application of TCS to EE: disruption-resistant circuits

texts:
Consider the following problem. We're given a circuit $C$ with $n$ binary inputs and $n$ binary outputs, computing some boolean function $f_C : \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$. We assume for simplicity that $C$ only contains binary AND/OR gates, except for the output gates that can be OR gates of unbounded fan-in. We want to ensure that $C$ is 'disruption-resistant' in the sense that modifying a small number of gates does not change the output. Formally, fix an integer $k$ and a circuit $C$. Call a '$k$-disruption' of $C$ a circuit $C'$ obtained from $C$ by modifying $k$ gates, except for output gates. Say that $C$ is '$k$-resistant' if, for any $k$-disruption $C'$ of $C$, it holds that $f_{C'} = f_C$, i.e. the two circuits compute the same function.

Consider the function $\chi_k : \mathbb{Z}_2^k \rightarrow \mathbb{Z}_2^k$ such that $\chi_k(x) = y$ with $y_j = 1 \Leftrightarrow \sum_{i = 1}^{k} x_i \geq j$. Given two tuples $u,v \in \mathbb{Z}_2^k$, say that $v$ is an $l$-perturbation of $u$ if $d_H(u,v) \leq l$. Consider the following question: given $l < k$, can we find a circuit $X_{k,l}$ such that for each $k$-disruption $C$ of $X_{k,l}$, for each $u \in \mathbb{Z}_2^k$, there is an $l$-perturbation $v$ of $u$ such that $f_C(u) = \chi_k(v)$? That is to say, $C$ would count the one-entries of $u$ up to some additive error $l$.

Suppose that we can find such a circuit $X_{4k,k}$ for any integer $k$. We can then solve the first problem using replication as follows. Take $4k$ copies $C_1,\ldots,C_{4k}$ of the given circuit $C$, and let gate $g_{i,j}$ be the $j$th output gate of $C_i$. For each $j \in [n]$, insert a copy of the circuit $X_{4k,k}$ with input connected to the gates $g_{1,j},\ldots,g_{4k,j}$, and with output gates labeled by $h_{1,j},\ldots,h_{4k,j}$. Finally, let the output gate for the $i$th bit be an OR of the outputs $h_{2k-1,i},\ldots,h_{4k,i}$. Let $\Gamma$ denote the resulting circuit. It is then easy to see that for any $k$-disruption $C'$ of $\Gamma$, there are at least $3k$ circuits $C_i$ that are not affected. Thus, if we consider a fixed input $x$, for each $i$th output bit the following holds: if the gates $g_{1,i},\ldots,g_{4k,i}$ evaluate to a constant tuple $t$ in $\Gamma$ and to a tuple $t'$ in $C'$, then $t'$ is a $k$-perturbation of $t$, and by definition of the circuit $X_{4k,k}$ it then computes a value $\chi_k(t'')$ with $t''$ a $2k$-perturbation of $t$. As this circuit has $4k$ outputs it follows that taking the OR of the last $2k+1$ values yields the desired result.

It it thus desirable to construct a circuit $X_{k,l}$ fullfilling the above requirements. I'm working on it but I welcome ideas or advice you may have.


texts: LogSpace reductions vs. PTime reductons for defining PSpace-completeness

texts:
Continuing https://cs.stackexchange.com/questions/90527/is-every-pspace-complete-problem-complete-with-respect-to-logspace-reductions : earlier, PSPACE-completeness was defined via logspace reductions (e.g., cf. http://www.cs.cornell.edu/~kozen/Papers/LowerBounds.pdf), whereas it is defined via ptime reductions nowadays (e.g., cf. https://en.wikipedia.org/wiki/PSPACE).

Why has it changed? Is it just because the folks after Dexter Kozen got too lazy even to say that one can go the extra mile to show that their reductions are actually logspace, let alone actually going that extra mile? Or is there a deeper, technical reason?

Crosspost: http://cs.stackexchange.com/questions/115921/logspace-reductions-vs-ptime-reductons-for-defining-pspace-completeness


texts: Graphs with minimal-size induced subgraphs

texts:
I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is $d$-regular if every vertex of $G$ occurs in exactly $d$ edges. For $W \subseteq V$ a subset of vertices of $G$, I write $G|_W$ the induced subgraph of $G$ by $W$: its vertex set is $W$ and its edge set is the restriction of $E$ to $W$, i.e., the edges of $G$ whose endpoints are both in $W$.

Given a graph $G$, I am interested in the function $f_G$ from $\{0, \ldots, \text{n}(G)\}$ to $\mathbb{N}$ defined by:

$$f_G(k) := \max_{W \subseteq V \text{ such that } |W| = k} \text{m}(G|_W).$$

Informally, $f_G(k)$ is the maximal number of edges in an induced subgraph of $k$ vertices of $G$. Of course, it is NP-hard to compute $f_G$ given $G$, because of a straightforward reduction from the clique problem (we have $f_G(k) = {k \choose 2}$ if and only if $G$ contains a $k$-clique), but I'm just interested in the function, not in computing it. Does this function have a name, or does it relate to known concepts in graph theory? In particular I'm interested in regular graphs where this function grows as slowly as possible: specifically let's define the following for any $n, d \in \mathbb{N}$ and $0 \leq k \leq n$:

$$g(n, k, d) := \min_{G~d\text{-regular such that } \text{n}(G) = n} f_G(k)$$

Informally, this is the lowest value of $f_G(k)$ for a $d$-regular graph with $n$ vertices and $m$ edges. Is anything known about the behavior of this function $g$?

One specific angle under which $g$ seems to have been studied is that of finding the values for which $g(n, k, d) = k-1$ (i.e., the lowest value we can reasonably hope for): this holds iff there exists a $d$-regular graph on $n$ vertices with girth greater than $k$. This subcase is already challenging because it is open to determine exactly for which values such a graph exists; but the asymptotics are known. I wonder if anything is known more generally about the function $g$, e.g., when fixing $d$, if $k$ is some $\Omega(\log n)$, then we may have $g(n, k, d) > k-1$, but can we still bound the value of $g$ somehow?


texts: When does "X is NP-complete" imply "#X is #P-complete"?

texts:
Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version.

Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"?

Of course the existence of a parsimonious reduction is one such condition, but this is obvious and the only such condition of which I am aware.  The ultimate goal would be to show that no condition is needed.

Formally speaking, one should start with the counting problem #$X$ defined by a function $f : \{0,1\}^* \to \mathbb{N}$ and then define the decision problem $X$ on an input string $s$ as $f(s) \ne 0$?


texts: Does the existence of PH-complete problems relativize?

texts:
The Baker-Gill-Solovay result showed that the P = NP question does not relativize, in the sense that no relativizing proof (insensitive to the presence of an oracle) can possibly settle the P = NP question.

My question is:  Is there a similar result for the question, "Does there exist a PH-complete problem?"  An answer in the negative to this question would imply P != NP; an answer in the affirmative would be unlikely but interesting because it would mean that PH collapses to some level.

I'm not sure, but I suspect that a TQBF oracle would lead PH to be equal to PSPACE, and thus to have a complete problem.  In addition to being uncertain regarding this, I am curious as to whether or not there is an oracle relative to which PH provably does not have a complete problem.

-Philip


texts: How do I figure out how to combine simpler quantum gates to create the gate I want?

texts:
I want to create other quantum gates from the basic building blocks of a universal quantum gate set. I've been playing with IBM's quantum computing interface for that.

I wanted to create a Toffoli gate, which I managed to in the end, but part of it was by trial and error. I want to create some other gates now, and I want to avoid the long arduous process of trial and error.

Is there a better way?

Is there also a way to how to construct the gate from the minimum number of gates necessary?

I'm going to add my work on the Toffoli here for anyone to see / critique.

% Matlab / Octave code
q=[1 0];
X=[0 1;1 0];
Y=[0 -1i; 1i 0];
Z=[1 0;0 -1];
H=[1 1;1 -1]/sqrt(2);
S = [1 0;0 1i];
St = [1 0;0 -1i];
C = [1 0 0 0;0 1 0 0; 0 0 0 1; 0 0 1 0];
Cgap = [1 0 0 0 0 0 0 0; 0 1 0 0 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 1 0];
T = [1 0; 0 exp(pi*1i/4)];
Tt = [1 0; 0 exp(-pi*1i/4)];
I = eye(2);
I2 = eye(4);
I3 = eye(8);

CS = kron(T,Tt)*C*kron(Tt,Tt)*C*kron(T,S);
CSt = kron(Tt,St)*C*kron(T,T)*C*kron(Tt,T);
CgapS = kron(T,kron(I,Tt))*Cgap*kron(Tt,kron(I,Tt))*Cgap*kron(T,kron(I,S));

Toffoli = kron(I2,H)*kron(I,CS)*kron(C,I)*kron(I,CSt)*kron(C,I)*CgapS*kron(I2, H)

Toffoli gate program using IBM's Quantum Experience (the two X gates on the very left are used to set the values of the qubits to 1; they can be removed to run the gate with 0 values):

The way I figured it out was I found some lecture notes with the gate expressed as seven building blocks, but I didn't have some of the blocks, so I constructed those by trial and error. Here's the pdf:
https://inst.eecs.berkeley.edu/~cs191/fa07/lectures/lecture9_fa07.pdf


texts: If machine learning techniques keep improving, what's the role of algorithmics in the future?

texts:
Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would be great, but then what would be the role of traditional algorithmics in such a future?

Here by "traditional algorithmics" I refer to the usual process that we follow in TCS: formalise a well-defined computational problem, design algorithms for solving the problem, and prove formal performance guarantees.

Now what are the application areas in which we must use traditional algorithm design and analysis also in the future, and it is highly unlikely that any advances of machine learning will make traditional algorithmics mostly irrelevant?

At first this may seem like a silly question: Of course we will need to be able to do sorting, searching, indexing, etc. also in the future! Of course we will need to be able to do Fourier transforms efficiently, multiply large matrices, find shortest paths, solve linear optimisation problems!

But then again, once you start looking deeper at the applications in which we traditionally use the algorithms that we design, it is not at all clear that the traditional algorithm design and analysis is the right answer to such problems: In applications related to search, usually we are interested in finding something that is a close match for a human being in some vague ill-defined sense (e.g. semantic similarity), not something that is optimal in some mathematical sense (e.g. minimum edit distance). In applications related to route planning, usually we are interested in finding routes that are good based on examples (e.g. other people prefer it), not routes that are optimal in some mathematical sense (e.g. shortest distance or cheapest price). And once you have some vague, ill-defined human component in the picture, it might be the case that we are better off trying to teach the computer to produce good answers based on examples, instead of trying to let a TCS researcher to come up with a formal computational problem that we can tackle by means of traditional algorithm design and analysis.

So what are the application areas (preferably real and direct industrial applications) in which it is absolutely clear that what we have been doing in algorithmics in past is also going to be the right way (and the only possible way) of making progress in the future?

Algorithms that are used as subroutines in machine learning techniques looks like an obvious future-proof candidate, but this heavily depend on the particular machine learning technique that we use, and as we have seen in the past ten years or so, this might rapidly change.


texts: reference request: deciding validity of higher-order quantified boolean formulas is not Kalmar-elementary

texts:
$\newcommand\iddots{⋰}$In "A simple proof of a theorem of Statman" (TCS 1992), Harry Mairson gives a simple proof of Statman's result that deciding $\beta\eta$-equality of terms in simply typed lambda calculus is not elementary recursive, i.e., cannot be done in time $O(2^{\iddots^{2^n}})$ for any finite tower of exponentials.  It's a nice proof, that works by showing how to encode arbitrary formulas of what Mairson calls "higher-order type theory" as simply typed terms, such that a formula is valid iff the corresponding term evaluates to the Church boolean $true = \lambda x.\lambda y.x$.  The phrase "higher-order type theory" sounds ambiguous to me, so for the purpose of this post I will just call these higher-order quantified boolean formulas (HOQBF) — please let me know if there is a more standard terminology.

HOQBF can be seen as a generalization of QBF, where quantifiers can range not just over the set of booleans $\mathbb{B} = \{ \mathbf{true}, \mathbf{false} \}$, but over sets of booleans $P(\mathbb{B})$, sets of sets of booleans $P(P(\mathbb{B}))$, and so on.  In other words, the language of formulas is
$$
F ::= \forall x^k.F \mid \exists x^k.F  \mid F\wedge F \mid F \vee F \mid \neg F \mid x^k \in y^{k+1}
$$
where the $k$ are natural numbers, and where variables $x^k$ are interpreted as ranging over $P^k(\mathbb{B})$.  (Again, is there a standard name for such formulas?)

Mairson cites

A. R. Meyer. The inherent computational complexity of theories of ordered sets. Proceedings of the International Congress of Mathematicians, 1974.

for the result that deciding formulas of HOQBF requires nonelementary time.  I checked that paper, and unless I'm overlooking something it doesn't contain a direct proof of this result.  I'm not 100% sure it contains a statement of it either...what looks most relevant is the theorem on page 4, which cites a list of results that various decision problems are nonelementary, including "7. The theory of pure finite types [M. Fischer and Meyer, FM75]".  Naturally, the bibliography includes the line

  [FM75] Fischer, M.J. and A.R. Meyer, (1975), in preparation.

and I can't find much evidence that such a paper ever surfaced.

I do believe the claim that deciding HOQBF requires nonelementary time, and moreover Mairson's paper also gives a separate encoding of Turing machines in simply typed lambda calculus, which computes the result of running the machine for any tower of exponential steps — so I suppose it might be possible to complete the circle and try to reduce the problem of deciding $\beta\eta$-equality of simply typed lambda terms back to HOQBF. Still, it would be nice to know if there is a classical reference for this result.

Question: Is there a reference for the result that deciding HOQBF requires nonelementary time? (Side question: Is there a standard name for HOQBF?)

Update (June 17): So I finally went ahead and looked at Statman's original paper, and it seems that Mairson got his citation from there!  Statman begins by defining these formulas, which he calls "$\Omega$-sentences", then states the result that deciding whether they are true is non-elementary. This is listed as "Proposition 1 (Fischer and Meyer, Statman)", stated without proof, but with a citation to the Meyer survey paper (conference version) and the specific item "7" of the theorem I had in mind (which cites the [FM75] paper I have been unable to locate). Since Meyer is actually listed as the handling editor for Statman's paper, I'm beginning to suspect that there may not exist a more canonical reference for this...


texts: Big-O bounds on the k-th largest element of iid Gaussians

texts:
I'm interested in the following problem. Let $X_1, \dots, X_n$ be iid samples with a $N(0,1)$ distribution. Let $X_{[k]}$ be the $k$-th largest element of $\{X_1, \dots, X_n\}$, so e.g. $X_{[1]} = \max_i X_i$.

Are there simple big-O bounds on $X_{[k]}$ for, say, all $k < n/2$? I know that $X_{[1]} = O(\sqrt{\log{n}})$ (see here), and more generally, $X_{[c]} = O(\sqrt{\log{n}})$ for constant $c$ (see here). But what about $X_{[\log{n}]}$ or $X_{[n/4]}$, for example?

My motivation is that I want to calculate $\sum_{i=1}^k E[X_{[i]}]$ for various values of $k$.

Thanks!


texts: Asymptotic complexity of sorting using k-comparisons

texts:
Sorting using 2-elements comparisons has an asymptotic worst-case complexity of $n \log_2(n)$ (reached by mergesort, heapsort, binary insertion, ford-johnson at least), which is optimal.

If we sort using comparisons that sort k elements as building blocks, the information theoretic lower bound is $n \log_{k!}(n)$.
We can easily reach $n \log_k(n)$ with k-ary insertion.

Question: Where is the optimal complexity between $n \log_k(n)$ and $n \log_{k!}(n)$ ?

Appropriate refs would be appreciated too.

Edit : because it wasn't clear :

I'm interested about the complexity in $n$, with $k=O(1)$. It has the asymptotic behavior of $\alpha n\log_2(n)$ with $\alpha \in [\frac{1}{\log_2(k)},\frac{1}{\log_2(k!)}]$, and i'd like more precision about $\alpha$.


texts: Best approximations of Minimum Dominating Sets in chordal graphs

texts:
I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime here ?
The problem was shown to be $W[1]$-hard for the natural parametrization by Liu and Song in 2009.


texts: Transition Diagram of a Universal Turing Machine

texts:
I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram?

I need this as a reference, so preferably a book or a published article. I don't want anything strange, just a standard Turing Machine with one tape that computes the Universal Turing Machine. The tape will contain a Turing machine and an input string. The rest of the tape is filled with blank.

I would prefer historic references.


texts: Two DFA intersection emptiness connections to SETH & L vs P

texts:
(re "fine grained complexity") Wehar has proved that

  Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false.

does anyone see any particular key proof difficulty, challenge, implication etc in the inverse of that? ie

  if two DFA intersection emptiness is $\Omega(n^2)$ then SETH is true?

this two DFA intersection emptiness problem seems like a key problem to analyze/ resolve because Wehar has also shown that solving the intersection problem for $k$ DFA's in $n^{o(k)}$ time → $NL \subsetneq P$. (are there any other known problems like that? which relate L,P,NP,ExpTime?) the problem also seems similar to an old important problem complete for ExpSpace analyzed by Meyer/ Stockmeyer, "emptiness of regular expressions with squaring."

also, what is known on the best lower space bounds on this problem? (will regard partial answers on these presumably hard questions as ok.)


texts: A partition problem in which some numbers may be cut

texts:
In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard.

However, assume that we are allowed to designate one of the numbers to be a "soft number" that can be cut it into an arbitrary number of pieces, where different pieces may be put into different subsets.
Then the problem becomes easy: just arrange all numbers on a line in an arbitrary order, and cut the line into two sub-lines with the same sum.

  QUESTION: Suppose we are given some numbers whose sum is $3s$, and have to decide whether they can be partitioned into three subsets whose sum is $s$, while using at most one soft number. What is the complexity of this problem?

If we are allowed to use two soft numbers, then the problem is again easy - we can solve it by arranging the numbers on a line as above.
If we are allowed to use zero soft numbers, then the problem is obviously hard - it is at least as hard as the problem of partitioning into two subsets.
If we are allowed to use one soft number, my guess is that the problem should still be hard, and we can somehow reduce to it from the standard partition problem, but I could not find the right reduction. So, is it easy or hard?

Another question: in case the problem is indeed NP-hard, can it be solved in pseudo-polynomial time like the two-subset partition problem?


texts: When are all facets rank facets? (for independence system polyhedra)

texts:
Consider an independence system $(E,\mathcal{I})$, and the corresponding polytope:

$P(E,\mathcal{I}):=\operatorname{conv.hull}\{ x^S ~|~S\in \mathcal{I}\}$

where $x^S \in \{0,1\}^E$ denotes the characteristic vector of $S$. A rank inequality has the form $\sum_{i \in S} x_i \le r(S)$, where $S\subseteq E$ and $r(S):=\max\{ |A| : A \subseteq S,~ A \in \mathcal{I}  \}$. Let's say that the nonnegativity bounds $-x_i \le 0,~i \in E$ are trivial.

(1) When is it true that all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities?

It is known, for example, that if $(E,\mathcal{I})$ is a matroid, or the intersection of two matroids, then all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities.

(2) Does the converse hold, i.e., if all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities, then $(E,\mathcal{I})$ can be written as the intersection of two matroids?


texts: Concerning decidability of a problem on real numbers

texts:
This question is an outgrowth of a certain maths problem I've been thinking about.

Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer and it returns you an integer back (for example: given input $n$ the oracle representing $r$ returns integer $k$ such that $k/n \leq r < (k+1)/n$; but it can be any other oracle complying to the aforementioned rule).

Now, given two oracles like that you can't decide if they represent equivalent numbers (if the numbers are equal the algorithm won't halt in 'most' cases). So you are given another oracle that takes two real-number oracles as input and tells if they represent equal numbers.

Given two real numbers $r$ and $s$ represented by such oracles plus the oracle that tells us if two real numbers are equal is it possible to decide if $s = qr + p$, where $q$ and $p$ are rational?

Please provide a formal proof (or at least an idea that can be easily formalized into a proof).

Update: There is a problem with the oracle comparing two real numbers - see comments. Intuitively what I want is the answer to the following question: is deciding that two real numbers belong to the equivalence class defined by $s=qr+p$ harder than deciding if they are equal. I'll close this question and restate it.


texts: Complexity of counting matchings in a bipartite graph

texts:
I might be missing something obvious but I can't find references about the complexity of counting matchings (not perfect matchings) in bipartite graphs. Here is the formal problem:

Input: a bipartite graph $G = (U, V, E)$ with $E \subseteq U \times V$
Output: the number of matchings of $G$, where a matchings is a subset $F \subseteq E$ such that there is no $v \in U \sqcup V$ that occurs in two edges of $F$.

What is the complexity of this problem? Is it #P-hard?

It is well-known that counting perfect matchings on bipartite graphs is #P-hard, and it is known that counting matchings of arbitrary graphs (or even planar 3-regular graphs) is #P-hard by this paper, but I didn't find anything about counting non-perfect matchings on bipartite graphs.


texts: Infinitely large but locally finite computation problems

texts:
This question is inspired by a comment Jukka Suomela made on another question.

  What are examples of infinitely large but locally finite computation problems (and algorithms)?

In other words, what are examples of computations that halt in finite time, in which each Turing Machine reads and processes only finite data, but altogether the computation solves an infinite-size problem if there are infinitely-many Turing machines networked together?


texts: Minimizing a monotone submodular function under a cardinality constraint

texts:
I would like to know what the status of the following question is:

  Given query access to a non-decreasing, non-negative submodular function $f\colon 2^{[n]} \to \mathbb{R}$ and a parameter $0 \leq m\leq n$, minimize $f(x)$ subject to the cardinality constraint $\lvert x\rvert \geq m$.

I am in particular interested in the query complexity of the problem as a function of $n$ and $m$. Without the cardinality constraint, this can be done efficiently in strongly polynomial time (so a fortiori with polynomial query complexity); without the monotonicity, this becomes NP-Hard (I assume this gives little hope in terms of number of queries?).

But now, does the monotonicity buy us anything? And, if not, what about throwing the assumption that $m=n-o(n)$ — would that help?

I'm at a loss about where to look — any answer, pointer, or reference would be welcome.

Note: at the end of the day, what I am actually given is approximate query access to $f$ — i.e., blackbox access to a randomized algorithm that returns w.h.p. a good additive approximation of $f(x)$ for any point $x$. I'm not sure this fundamentally changes the problem, though, and in any case the exact version seems like a good place to start. (But if the approximate version had been considered in the literature, this would make my day.)


texts: Reference request: DFA linear-time minimization

texts:
What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time?
Here’s what I’ve been able to find so far:

The acyclic case has been solved. So any acyclic DFA can be minimized in $O(n)$ time by the Revuz algorithm [2].
As for cyclic automata, an automaton that is a simple cycle can be minimized in $O(n)$ time. A simple cyclic automaton has an underlying graph which is a cycle, and in particular, has states that can be named $1,2,3,…n$ and the only transitions allowed are $1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 4, …, i \rightarrow i+1,…, n \rightarrow 1$.  This is from Almeida and Zeitoun [1], who reference a result in Lemma 4.2 of their paper saying that the primitive root of a string can be found in $O(n)$ time.

Is this the state of the art, or can more complicated automata be minimized in $O(n)$ time?
[1] J. Almeida and M. Zeitoun. Description and analysis of a bottom-up DFA minimization algorithm. Inform. Process. Lett., 107(2):52–59, 2008.
[2] D. Revuz. Minimisation of acyclic deterministic automata in linear time. Theoret. Comput. Sci., 92:181–189, 1992.


texts: Find min-weight simple path assuming no negative simple cycles

texts:
A simple path is a path that doesn't revisit a node. A simple cycle is a cycle that doesn't revisit an edge. You are given an undirected graph G which may contain edges of negative weight but which will not contain any simple cycles of negative weight. Is there an efficient algorithm for finding the minimum weight simple path between any two nodes of G?
Notes:

Without the no-negative-simple-cycle constraint, this problem is NP-Hard.

The reason I'm interested in this problem is because the weight of the min-weight simple path should be a good estimate of the "safety level" of the syndrome extracted during quantum error correction. In this case the edges of the graph correspond to physical error mechanisms, the negative edges are the physical errors that are part of the extracted syndrome, the no-negative-cycles property is guaranteed by the fact that the syndrome extraction would have used any such cycle to produce a better syndrome, and a simple path between two particular nodes can be multiplied into a syndrome to get a different syndrome that disagrees about the logical correction to make.

I initially thought that the Bellman-Ford algorithm would work, after tweaking it so that each node refused to backtrack to its current predecessor. However, this can create deadlock situations where the optimal solution is to detour through multiple beneficial regions but the local greedy checks can't see past the initial cost of entering into a beneficial region. For example, in the graph below where you're trying to path from left to right, the optimal solution is to move vertically through almost all the negative edges (in red). Bellman-Ford can fail to find this solution, depending on the order in which the search progresses:


texts: Lower bounds for formulae sizes for addition

texts:
I am interested in the conversion of  $\sum_{i=1}^n x_i = y$ to 3-CNF.  Here $x_i$ is a binary 0/1 variable and $y$ is some positive integer. There are a number of practical methods for doing this, some of which are in this answer.  What is known about the minimum possible size however?

Define a function $f(n,y)$ as the minimum size of a logical formula which is equivalent to the question: does $\sum_{i=1}^n x_i = y$? What is known about  $f(n,y)$?   Is the exact value of $f(n,y)$ known for small values $n$ and $y$?

EDIT Kaveh has formalized my intended question in the final part of his answer. From there we learn that finding any lower bound might be hard. I am still interested to know what the best upper bounds are, especially for small problem sizes.


texts: Approximating max degree $3$ perfect matching count?

texts:
We do not have a deterministic constant factor approximation scheme for general $n\times n$ $0/1$ permanent.

What is the best factor in deterministic approximation schemes if we only care counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?


texts: About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

texts:
What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective?
Are there any necessary conditions that we know of that the objective, algorithm and the oracle have to satisfy to get convergence?

For example : I would be very interested to know of proofs which do not need to assume that the objective has bounded gradients (or that the function is upperbounded). These look very rare to satisfy in usual learning situations!  (What are natural non-convex learning situations which have bounded gradient losses?)

I am not considering methods like NSVRG which allow the algorithm to compute the exact gradients sometimes. I am specifically looking at algorithms where the gradient oracle is the only oracle being invoked and it is necessarily always noisy.


texts: High probability events without low probability coordinates

texts:
Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small constant $\delta$. Let $E \subseteq \rm{Supp}(X)$ be an event in the support of $X$ such that $\Pr[X \in E] \ge 1 - \varepsilon$, where $\varepsilon$ is an arbitrarily small constant.

We say that a pair $(i,\sigma)$ is a low probability coordinate of $E$ if $\Pr[X \in E | X_i = \sigma] \le \varepsilon$. We say that a string $x \in \Sigma^n$ contains a low probability coordinate of $E$ if $(i, x_i)$ is a low probability coordinate of $E$ for some $i$.

In general, some strings in $E$ may contain low probability coordinates of $E$. The question is can we always find a high probability event $E' \subseteq E$ such that no string in $E'$ contains a low probability coordinate of $E'$ (and not of $E$).

Thanks!


texts: Complexity of union (computational geometry)

texts:
I'm courrently rading "Computational Geometry" from Mark de Berg, Otfried Cheong,
Marc van Kreveld, Mark Overmars and found the following theorem 13.9.

  Let $S$ be a collection of convex polygonal pseudodiscs with n
  edges in total. Then the complexity of their union is at most $2n$.

I'm not really sure what this should mean (this might be a a language barrier). First I thought that this would be the time complexity, but I'm now pretty much unsure about this.


texts:
$\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)$: Given an integer $\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}$ in binary output the $j$th binary digit of the $i$th base-$q$ digit (where $q$ is not necessarily a prime).
$\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)=j\mbox{ th bit of }y_i\mbox{ in }\sum_{i'=0}^{m-1}q^{i'}y_{i'+1}=\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}$ where $y_{i'}\in\{0,1,\dots,q-1\}$ at every $i'\in\{1,\dots,m\}$
and $m=\lceil\log_q\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}\rceil$.

Is $\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)\in\mathsf{uniformTC^0}$ or at least $\mathsf{non-uniformTC^0}$?


texts: Boolean circuit for efficient array indexing

texts:
Suppose that I have an array $\{a_i\}$ of $n$ elements, each $k$ bits wide, and an array $\{b_i\}$ of $n$ elements, each $\lceil\log_2n\rceil\le k$ bits wide. I need a boolean circuit which will compute an array $\{c_i\}$, where $c_i=a_{b_i}$. I'm interested in a circuit with as few gates (with fan-in of 2) as possible.

There is a trivial solution with $O(kn^2)$ gates. Also, if it is known that $\{b_i\}$ is a permutation, it is possible to use a sorting network to solve the problem with only $O(kn\log n)$ gates, but with a large constant factor. I don't know how to extend this solution to the general case. Also, a circuit can do more that a sorting network, so it could potentially be more efficient.


texts: Can we partition NP-complete problem into finite number of polynomially solvable problems?

texts:
Let $\Pi$ be NP-complete problem.
Can we partition set of instances of $\Pi$ into finite number of subsets (subproblems) each of which is polynomially solvable (and not necessarily polynomially recognizable)?
For example, $\Pi$ is NP-complete for graphs with maximal degree $\Delta=3$, but polynomially solvable for cubic and graphs with $\Delta=2$?

I have obtained two answers on my question: "trivially yes" (by Peter Shor and mikero) and no, unless $P=NP$ (by Sadeq Dousti and Antonio E. Porreca). I'm curious why such easy question gets such contradicting answers (not taking into account the reason that I have formulated it ambiguously). So the question is:
how to formulate two questions such that for each of them corresponding answers would hold.

The last edition of this question has been answered in full by Peter Shor on Math.SE here.
Here is the answer:

"There are two different possible questions here. When you ask for the solution of an NP-complete problem, you can either (a) require the computer to give you a witness in the "yes" cases or (b) just require the computer to give you the answer."


texts: Time/Space Requirements of Verifying or Falsifying a First-Order Statement

texts: Though L.Berman proved that the problem of verifying or falsifying any first-order statement about real numbers that uses addition and comparison but not multiplication is in EXPSPACE.  Has it been shown how much time or space you would nee to verify or falsify any first-order statement about real numbers that uses addition comparison AND multiplication?


texts: Are randomly generated infinite patterns computable?

texts:
Fix a prefix-free universal Turing machine $U$. Consider the following random process*. The state of the process is a bit-string $s$, initialized with the empty string (say). Suppose the value of the string on step $n$ is $s_n$. At the next step, we randomly generate a program $A$ using $U$, like in the definition of Chaitin's constant $\Omega$**. If $A$ doesn't halt we discard it and generate a new program. If it halts with output $t$ and $s_n$ is not a prefix of $t$ we also discard it and generate a new program. If $s_n$ is a prefix of $t$, we update the state according to $s_{n+1}:=t$. Note that $s_n$ is a prefix of $s_{n+1}$ i.e. at each step the string gets appended

Allowing the process to continue indefinitely, we get an infinite bit-string $s_{\infty}$. The question:

  What is the probability $p$ that $s_{\infty}$ is computable? Is $p > 0$?

Of course $p$ a priori depends on $U$ but my intuition is that if it vanishes for some $U$ it vanishes for all, for approximately the same reason Kolmogorov complexity only weakly depends on $U$

*This process is closely related to the concept of Solomonoff induction

**This is done as follows. We generate an infinite sequence of bits $a$ by flipping a coin an infinite number of times. Since $U$ is prefix-free, there is a unique prefix $A$ of $a$ which is a valid program for $U$


texts: Ultimate Jedi Challenge - Multiarmed Bandit / Reinforcment Learning / advanced AI problem

texts:
(This is an attempt to reformulate this question more concisely.)

Context

You are a Jedi master who wants to prepare a training program (online-algorithm) for his apprentice, "Luke". Luke needs to practice several (10-20) abilities. You can train Luke by preparing challenges, each connected to one ability.

The outcome of each challenge is binary: Luke succeeds (1) or Luke fails (0). If Luke fails a challenge in an ability, you give him a lecture that you can assume will improve his chance of succeeding in next challenge in this ability.

You have a limited number (~50) of challenges to use before Luke has to take a test. However, if Luke fails at some challenge during practice you receive extra challenges. The goal of your training program is to maximize the outcome of the test. The test is a set of (about 20-25) challenges uniformly distributed between abilities.

Problem definition

Consider a problem of probing a set $P = \{p_0,...,p_n\}$ of $N$ independent processes which resemble human learning (practice makes perfect). At each time the program chooses one process $i$ to probe, denoted by the action $U(t)$, and receives an information of the current, binary state $S_i(t)$ of that process. The probability of $S_i(t)$ = 1 is defined by
$$
 p(S_i(t) = 1) = g_i(c_i(t))
$$
 Where $g_i$ is a non-decreasing function and $c_i(t)$ describes how many times proces $p_i$ was probed so far. We can assume $g_i$ ressembles the learning curve, but each $g_i$ can have an arbitraty offset at $t_0$ ie:

 Knowing that the amount of remaining probing action is given by
$$
h(t+1) = \begin{cases}
            h(t)-1\,, &\text{ if $i \in U(t)$ and $S_i(t) = 1$;} \\
            h(t)-1+f(h(t))\,, &\text{ otherwise,}
\end{cases}
$$
where the function $f$ is one of the input variables — propose a probing policy which maximizes a testing function $q$ that will evaluate the state of all processes when there are no more remaining probes, namely:
$$q(t_{stop}) = \sum_{i = 0}^{N}S_i(t_{stop}),$$
where $t_{stop}$ is such that $h(t_{stop}) = 0$.

My ideas of approaching this problem

We can try to model this problem in at least two ways:

As a special case of Non-Bayesian Binary Restless Multi-armed Bandit (RMBA) with Non-Identical Arms (some reading one, two, three) meaning :

Restless - reward probability evolves over time
Non-Bayesian - underlying Markov transitions are not known
Non-Identical Arms - each arm is an independent Markov process
We would assume that the algorithm receives a reward each time it probes a process that will return 0 (Luke fails a challenge).
I would start by adopting some policy similar to $\epsilon$-greedy.

As a case for Reinforcement Learning .

I'm just starting to familiarize myself with these areas of research so I can't provide any insight here, although according to my initial reading it seems very promising. I will update the question once I learn anything meaningful.

Question

What would you recommend as the best references for this problem, or closely related problems? I'm interested primarily in approaches which are not just theoretically feasible, but which would be effective in practise.

Can you suggest a policy that would be effective with these constraints? I am especially interested in good ways to update the belief vector.


texts: Polygon within polygon generalization problem

texts:
I would like to apologize to all the posts below. Picked the wrong forum to post this in originally. However rather than make this a complete waste I've reworked the question to be a true "Theoretical Computer Science" problem.

Problem: Create an algorithm that takes a set of n ordered points in a 2D plane that form the contour of a simple polygon A that may or may not be concave and creates a new polygon B with m points such that:

all points in A are contained within B
3 <= m < n
B is the polygon in the set of all Bs with the smallest area
B must be a simple polygon (i.e. no self-intersections).
The input to the algorithm is polygon A and "m".
Coincidence of segments in B with segments in A are allowed.

Some example inputs and expected outputs:

If A is a square and m is 3 then B would be the triangle with the smallest surface area that contains A.
If A is a hexagon and m is 4 then B would be a quadrilateral with the smallest surface area that contains A.

Good luck to everyone who tries this problem out. I can promise you this will be very hard especially now that the solution must be optimal.


texts:
Let x be random variables with mean zero and variance 1.
Let n be natural number, t>0, C>0.
Let also $P(x^2\geq n)\geq C/(n^t)$.
Show, if $t\geq4$, then $P(x^2\geq n)\leq C/(n^2)$.

I got so fare, that with $t\geq 4$,
$\frac{C}{n^t}\leq \frac{C}{n^2}\leq P(x^2\geq n)\leq \frac{Ex^4}{n^2}$. But how to find bound on $Ex^4$?


texts: Complexity of finding a second solution given a correct solution to an NP-complete problem

texts:
I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem.  More precisely, I'm interested in any problems of the following form:

Given a solution $S$ to an instance $I$ of an NP-complete problem, is there a solution $S' \neq S$ to $I$?

Any examples of problems of this sort, both NP-complete and not, or general work, or even a what this sort of problem is called (so I can properly do my own searching) would be appreciated.

Another question addresses this issue specifically as pertaining to SAT.

I hope I'm not asking something really basic; there don't seem to be any examples in Garey and Johnson of this kind of thing.

Thanks
Mark C.


texts: Paradigms for complexity analysis of algorithms

texts:
Worst-case and average case analysis are well-known measures for the complexity of an algorithm. Recently smoothed analysis has emerged as another paradigm to explain why some algorithms which are exponential in the worst-case work so well in practice, for instance the simplex algorithm.

My question is - are there any other paradigms to measure the complexity of an algorithm? I'm particularly interested in ones that attempt to explain why some algorithms which have bad worst-case complexity work well in practice.


texts: When to apply soft constraints evaluation functions in genetic algorithms?

texts:
As stated in the question, say i created a random population of 100 timetables. 1 % of these timetables are valid. Then, if I apply the soft constraints evaluation functions on the 1% valid timetables, the population will have few outstanding finesses like below:

population = 5;

finesses = { 0.121,0.115,0.117,0.855,0.145} , the one in bold is an outstanding fitness and has the soft constraints evaluation functions applied on it. i have two hard constraints and three soft constraints and i use the weighted average to calculate overall fitness like this: (0.05)*h1+(0.05)*h2+(0.3)*s1+(0.3)*s2+(0.3)*s3

the question is:
Is this approach correct ?

someone suggested that i should treat soft and hard constraints the same, but if i do how can one soft constraints evaluate an invalid timetable!?


texts: Complexity Classes for Cases Other Than "Worst Case"

texts:
Do we have complexity classes with respect to, say, average-case complexity? For instance, is there a (named) complexity class for problems which take expected polynomial time to decide?

Another question considers the best case complexity, exemplified below:

Is there a class of (natural) problems whose decision requires at least exponential time?

To clarify, consider some EXP-complete language $L$. Obviously, not all instances of $L$ require exponential time: There are instances which can be decided even in polynomial time. So, the best case complexity of $L$ is not exponential time.

EDIT: Since several ambiguities arose, I want to try to clarify it even more. By "best case" complexity, I mean a complexity class whose problems' complexity is lower bounded by some function. For instance, define BestE as the class of languages which cannot be decided in time less than a some linear exponential. Symbolically, let $M$ denote an arbitrary Turing machine, and $c$, $n_0$, and $n$ be natural numbers:

$L \in \mathbf{BestE} \Leftrightarrow$
$\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

where $T(M(x))$ denotes the times it takes before $M$ halts on input $x$.

I accept that defining such class of problems is very odd, since we are requiring that, every Turing machine $M$, regardless of its power, cannot decide the language in time less than some linear exponential.

Yet notice that the polynomial-time counterpart (BestP) is natural, since every Turing machine requires time $|x|$ to at least read its input.

PS: Maybe, instead of quantifying as "for all Turing machine $M$," we have to limit it to some pre-specified class of Turing machines, such as polynomial-time Turing machines. That way, we can define classes like $\mathbf{Best(n^2)}$, which is the class of languages requiring at least quadratic time to be decided on polynomial-time Turing machines.

PS2: One can also consider the circuit-complexity counterpart, in which we consider the least circuit size/depth to decide a language.


texts: Is there any hidden subgroup of a symmetric group which can be efficiently determined?

texts: There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum algorithm to find a hidden subgroup in a symmetric group even when the structure of the hidden subgroup is heavily restricted (e.g. the hidden subgroup could be a very special direct or semidirect product)?


texts: Approximate counting with non-uniform sampler

texts: Suppose we have a predicate $\phi:\{0,1\}^n\to \{0, 1\}$ corresponding to a self-reducible problem and a FPAUS that can approximately sample from a distribution $p$ such that $\|p-u\|_{L_1}\leq \delta$, where $u$ is the uniform distribution of $\phi^{-1}(1)$. Is it possible to get an approximation of the number of solutions $|\phi^{-1}(1)|$ within a relative error of $\varepsilon$ for an arbitrary $\varepsilon>0$ ignoring the time complexity ? Or is the lowest $\varepsilon$ we can hope for bounded by (a function of) $\delta$ ?


texts: Machine learning algorithms on hypergrap models

texts:
Graphical models are a very useful tool with many applications,
whereby a joint distribution of a set of random variables is modeled
using only pairwise dependencies between the variables, and
two variables with a direct causal relationship are connected by an edge,
which is associated with their joint distribution.

It makes sense to extend this by looking at "hypergraphical models",
where we allow direct causal relationships involving say up to $d$ variables, and
the hyperedges connecting them are associated with a $d$-way joint distribution.

I want to know if such models have been studied, and in case they are
is there a good survey or reference to learn more about the research that
on belief propagation type algorithms on them?


texts: Strong seeded randomness extractors with low entropy loss

texts:
I would like to implement a strong seeded randomness extractor for flat sources as a part of my project.

Most of the literature on seeded extractors is concentrated on minimizing seed length. However, low entropy loss is crucial for my construction. What are the known extractors with minimal entropy loss? How efficient is the extractor in practice?

Is there a lower bound on the entropy loss for strong seeded extractors?

Are there any implementations of extractors that I can use off the shelf?


texts: Database query languages for efficient queries

texts:
It seems that in popular query languages for relational databases, it is possible to create queries that will require a lot of resources to answer. In practice, database admins manage this by limiting the amount of memory per query, and checking for any long-running queries if there is a slowdown in the database. This seems rather ad-hoc, is there a TCS solution to this?

  Are there query languages that can
  only implement efficient queries?

If there are no such languages, is there a theoretical reason for this?

Some reasons why I might expect these sort of things to exist or atleast make sense:

we have programming languages that are specifically designed to only implement efficient computations (usually by having some restrictive logic in their type system)
popular query languages (such as SQL) are already inspired by logic, so it does not seem as a stretch for database users to consider more restrictive logics.
a non-malicious database user already tries to prepare queries that execute quickly, so we should expect these more restrictive query languages to only hamper malicious users.

This question is inspired by the intersection of two previous questions:

Programming languages for efficient computation

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


texts: Fully dynamic algorithms for strong components of a directed graph

texts:
I'm faced with the problem of maintaining the strong components of a directed graph under insertions/deletions of edges and vertices.

As noted in one of the answers to a closely-related question here, the literature in this area is rather fragmented and hard for a newcomer such as myself to approach.

For example, the paper by Holm et al. appears to focus on undirected graphs, and it's unclear to me whether any of their results can be adapted to work with digraphs.  Other papers I've found focus on either the incremental or decremental cases, rather than the fully-dynamic case.

My need arises in a real-world software engineering scenario, so I would actually be fine with an approach that yields no worst-case asymptotic advantage over the naive idea of running an SCC algorithm from scratch for each update, so long as it performs well in practice.

I'd prefer not to reinvent the wheel, but I also don't have endless hours to wade through the literature, so hopefully someone here can save me some time.

Thanks in advance!


texts: Is there a non-deterministic linear time algorithm for CNF-SAT?

texts:
The decision problem CNF-SAT can be described as follows:

Input: A boolean formula $\phi$ in conjunctive normal form.

Question: Does there exist a variable assignment that satisfies $\phi$?

I'm considering several different approaches for solving CNF-SAT with a non-deterministic two-tape Turing machine.

I believe that there is an NTM that solves CNF-SAT in $n \cdot \texttt{poly}(\log(n))$ steps.

Question: Is there an NTM that solves CNF-SAT in $O(n)$ steps?

Any relevant references are appreciated even if they only provide near linear time non-deterministic approaches.


texts: Minimum feedback arc set for dense directed graph

texts:
This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\tilde{A} = L + D + U$, for (strictly) lower triangular, diagonal, and (strictly) upper triangular pieces, respectively, I minimize $\|U\|/\|L\|$ in some norm (Frobenius, $\ell^2$,...). In some cases, $A$ may be a DAG (with self-loops on the diagonal), and so a topological sort would yield $\|U\| = 0$. In other cases, $A$ is symmetric, so regardless of $P$, we should always have $\|U\|/\|L\| = 1$. To solve this exactly I believe is NP-hard, but I just need a reasonable approximation that is cheap to compute (at least as cheap as computing direct $A^{-1}$, preferably much cheaper).
This is essentially a minimum feedback arc set problem, but approximating the FAS problem is typically posed by eliminating cycles. Here, $A$ is usually going to be dense/fully connected. Broadly, my question is if using FAS approximation algorithms makes sense on a fully connected graph, if certain methods may make more sense than others, or if there is a different/better way to pose this problem?


texts: Complexity of converting a boolean circuit to a boolean formula

texts: Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime algorithm for this problem?


texts: How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?

texts:
In Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In this paper it is showed that no hidden subgroup algorithm can distinguish the trivial subgroup from an order-$2$ subgroup consisting of $\frac{n}{2}$ disjoint transpositions when the group is a symmetric group $S_n$.

My question:

How the hardness of the hidden subgroup problem changes when the order of the subgroup grows beyond $2$?
Is induction the ideal way to derive it?

My effort:

I am confused how to approach this problem. Should we find the element in the hidden subgroup with with largest absolute value of its character? If we can determine the value, would it be useful?


texts: Applications of representation theory of the symmetric group

texts:
Inspired by this question and in particular the final paragraph of Or's answer, I have the following question:

  Do you know of any applications of the representation theory of the symmetric group in TCS?

The symmetric group $S_n$ is the group of all permutations of $\{1, \ldots, n\}$ with group operation composition. A representation of $S_n$ is a homomorphism from $S_n$ to the general linear group of invertible $n \times n$ complex matrices. A representation acts on $\mathbb{C}^n$ by matrix multiplication. An irreducible representation of $S_n$ is an action that leaves no proper subspace of $\mathbb{C}^n$ invariant. Irreducible representations of finite groups allow one to define a Fourier transform over non-abelian groups. This Fourier transform shares some of the nice properties of the discrete Fourier transform over cyclic/abelian groups. For example convolution becomes pointwise multiplication in the Fourier basis.

The representation theory of the symmetric group is beautifully combinatorial. Each irreducible representation of $S_n$ corresponds to an integer partition of $n$. Has this structure and/or the Fourier transform over the symmetric group found any application in TCS?


texts: What is the advantage of a transformation matrix in perspective projection?

texts:
I was messing around with perspective projection. And it got me wondering whether using a perspective transformation matrix is the most efficient way. Because I also came up with another method which seems to need about the same amount of calculations:

Given:

The position of the "camera" $\vec{O}$.
The normalized vector $\vec{n}$ in the direction in which the camera
is looking (normal of the plane on which the points will be
projected).
Vectors $\vec{X}$ and $\vec{Y}$ which determine the orientation of
the projection. Both should lie in the projection plane and together with $\vec{n}$        should span an orthonormal basis in the $\mathbb{R}^3$.
The shortest distance from the camera to projection plane $h$
The point $\vec{P}$ which needs to be projected.

$\vec{\Delta}=\vec{P}-\vec{O}$
with $\vec{\Delta}$ the relative coordinates of $\vec{P}$ with respect to $\vec{O}$.

$\vec{\alpha}=h\left(\frac{\vec{\Delta}}{\vec{\Delta}\cdot\vec{n}}-\vec{n}\right)$

$x=\vec{\alpha}\cdot\vec{X}$

$y=\vec{\alpha}\cdot\vec{Y}$

Or do methods, which use transformation matrices, use eigen-value/vectors to reduce the amount of calculations?


texts: What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?

texts:
In [1] it is stated that

  "It remains an open question as to whether every function in $\#P$ has $TC^0$ circuits (although it is at least known that not all $\#P$ functions have DLogTime-uniform $TC^0$ circuits)."

$TC^0$ circuits generated by DLogTime functions does not contain $\#P$.
We don't know if $TC^0$ circuits generated by arbitrary functions does not contain $\#P$.

Is there anything known about the cases in between these two?
E.g. is it known if $TC^0$ circuits generated by $L$ does not contain $\#P$?

[1] Agarwal, Allender, and Datta, "On $TC^0$, $AC^0$, and Arithmetic Circuits"


texts: Time complexity of alternation free quantified linear program with no free variables and only existential quantifications

texts:
We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program.

I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications and no alternations.

  Can we always solve programs of type $$\exists x_1\in\mathbb R^{n_1}\dots\exists x_t\in\mathbb R^{n_t}$$$$ A_1[x_1,x_2]^T\leq b_1\wedge\dots\wedge A_{t-1}[x_{t-1},x_t]^T\leq b_{t-1}$$
  and
  $$\exists x_1\in\mathbb R^{n_1}\dots\exists x_t\in\mathbb R^{n_t}$$$$ A_1[x_1,x_2]^T\leq b_1\wedge A_2[x_1,x_2,x_3]^T\leq b_2\wedge\dots\wedge A_{t-1}[x_1,\dots,x_{t-1},x_t]^T\leq b_{t-1}$$
   in time $\mathsf{poly}(t,\sum_{i=1}^t(m_i+n_i))$ where $A_i$ are matrices in $\mathbb R^{m_i\times n_i}$ and $b_i$ are vectors in $\mathbb R^{m_i}$ by collapsing the quantifications into one single big $\exists$ quantifier and considering as a standard linear program and solving via standard linear programming techniques?

  Or is it possible there are scenarios where the program would require time $$\big(\sum_{i=1}^t(m_i+n_i)\big)^{2^{O(t)}}\mathsf{poly}(t,\sum_{i=1}^t(m_i+n_i))$$ (which is the complexity if we use Fourier Motzkin elimination according to https://www3.risc.jku.at/projects/intas/Timisoara/Presentations/German/Grman.pdf if we have alternating quantifiers and perhaps no free variables)?

Related:https://mathoverflow.net/questions/343396/quantifier-elimination-with-no-free-variables-and-real-polyhedral-inequalities

In this introductory blog post https://cstheory.blogoverflow.com/2011/11/something-you-should-know-about-quantifier-elimination-part-i/ it is mentioned in the very last line that "I do not know if a doubly exponential lower bound is known for the decision problem when there are no free variables".

I want to know if this comment applies to scenarios of no alternations.


texts: What research is being done in classical complexity theory?

texts:
As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as Savitch's $\textrm{NTIME}[S]\subset\textrm{DTIME}[S^2]$ and the famous PPST result that $\textrm{DTIME}[T]\neq\textrm{NTIME}[T]$?

Is there any new research that I am unaware of with the goal of developing a deeper theory of complexity that could one day solve problems $P$ vs $NP$, just as the theory of modular forms was developed to solve problems like Fermat's last theorem in number theory? And if not is it simply that we have run out of ideas to prove theorems like this, or have we turned to other measures of complexity for different reasons?


texts: Results in denotational semantics from model theory?

texts:
Denotational semantics interpret the theories of various lambda calculi in various (set-theoretic, domain-theoretic, category-theoretic, game...) models. Let $T$ be the theory of one such lambda calculus $\lambda_?$. If I understand correctly, a denotational semantics for $\lambda_?$ is thus just a model for $T$.

The question here is, have applying the tools and methods of model theory to denotational semantics yielded useful results. For example, what does the Löwenheim–Skolem theorem tell us about the denotational semantics of various lambda calculi?


texts: Bipartite vertex cover with a Very Important Vertex

texts:
I know that I can find the minimum vertex cover of a bipartite graph by first finding the maximum matching and then using Konig's Theorem to turn this matching into a vertex cover of the same order.

The result obtained is only one of what could be many valid vertex covers. In the following graph, {A,B}, {C,D}, and {B,C} are all valid covers. Applying the Konig method yields the cover {A,B}.*

(A)=====(C)
       /
     /
   /
(B)=====(D)

How would you check for the existence of a minimum vertex cover that includes a given important vertex, say, vertex D?

My first guess is to flip the graph and find another minimum vertex cover. In the above case, this would yield {C,D}. If neither solution contains the important vertex, it's not part of any minimum cover.  However, I haven't been able to prove this to myself.

*A little elaboration: edge AC and BD form the matching. In the algorithm described above, you start by treating the graph asymmetrically, labeling the sides L (left) and R (right). Initially, all L and none of the R vertices are part of the vertex cover. Now build a new set T of vertices by traversing according to the following rule: Start at the exposed vertices (not part of any matching) on the left side, travel right along all unmatched edges, then travel left along all matched edges, continuing back and forth until path termination. All visited vertices are added to set T.  Set T is subtracted from L and added to R to produce the vertex cover solution. In the example graph, there is NO traversal, since there are no exposed vertices on the left side.


texts: What does a tangible Quantum-Gate look like?

texts:
I'v read published books, articles and papers about Quantum-Computing.

I found that all the materials I've seen are, instead of describing quantum gate from basic physics to abstraction, trying hard to avoid talking about the implementation details of quantum-gates.

I firstly questioned myself: Am I searching in the wrong area where only formal mathematics are concerned?

But I found those papers and books do have explained ion-traps, optical-switches and even laser-fibre in great detail.

When it comes to quantum-gates they claimed to have used in their research, only matrices, equations, formulations and black-box components are shown.

We all know about the unitaries and matrix computation. But if you print a quantum-gate matrix operator on an A4-paper, that ain't going to do anything when photons or electrons are thrown to it.

So, does anyone know what is a quantum gate, concretely so that I can know:

Is Quantum Gate a device using magnetic field to do element arithmetics?
Is Quantum Gate a device using laser-beam?
Is Quantum Gate a device using metal wire?
When scientists happily multiply eigenstates by observables, do electrons collide in the gate when "multiplied"?

Thanks in advance.


texts: Efficient randomness reduction using k-wise independence

texts:
Consider a randomized algorithm with runtime $n$, which succeeds with high probability. The algorithm uses $O(n)$ uniformly random bits.

Now it is given that we can replace these uniformly random bits by $k$-wise independent bits, where $k$ depends on $n$ (say $k = \sqrt{n}$). Can we then reduce the number of random bits to $\tilde{O}(k)$ while keeping a runtime $\tilde{O}(n)$?

Clearly we could use k-wise independent bit generators (such as a random polynomial). However, naively implementing this would cost $\tilde{O}(k)$ steps per call, potentially increasing the runtime to $\tilde{O}(n k)$.


texts: Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

texts:
Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct?

Also on topic: where else (on the internet) is its correctness being discussed?

Note: the focus of this question text has changed over time. See question comments for details.


texts:
My understanding is that, more often than not, when people use domain theory for higher-type computability or the denotational semantics of functional programming languages, they tend to prefer flat domains to interpret base types.

These are obviously simpler to handle than non-flat ones, a fact that is reflected both on theoretical issues, since reasoning about properties of the model can become quite a combinatorial task, as well as on issues phrased in a more applied parlance, like, say, strictness analysis. My understanding is also that there are things that one can pull out in non-flat domains that are simply not doable in the flat ones, perhaps the most trivial example being the injectivity of constructors.

But, I feel that my understanding is still quite uninformed and shallow.

My questions: Why prefer flat domains? Why prefer non-flat domains? What are examples of things (theoretical or practical) that can be done in one setting but not, or not yet, in the other? Is there a reference with an account on such a comparison?

EDIT (25/11/14): I added explicit mention of the base types, after the discussion with babou and Damiano Mazza below.


texts:
I’m curious whether there is any work on the variant of the Travelling Salesman Problem where a subset of the nodes must be visited in a particular order. I haven’t found anything with searches or in survey articles, but that may just mean I haven’t found the right search terms or the right surveys.

If there are $n$ nodes in the graph, and a list $a_1, \dots, a_k$ of nodes that must be visited in that order, I can transform the problem to an instance of ATSP with $2k(n-k)+k$ nodes. The result is asymmetric even if the original edge-weights were symmetric, so we lose another factor of $2$ if we want to reduce it to a symmetric instance. I would be interested to know if there is a more efficient reduction.

Edited to add: On further reflection I think I can improve the reduction to $k(n-k)+k$ nodes.


texts:
I have to implement an algorithm that solves the multi-selection problem.
The multiselection problem is:

  Given a set S of n elements drawn from a linearly ordered set, and a set $K = {k_{1}, >k_{2},...,k_{r}}$ of positive integers between 1 and n, the multiselection problem is to >select the $k_{i}th$ smallest element for all values of i, $1 \le i \le r$

I need to solve the average case on $ \theta(n log p) $.
I've found a paper that implements the solution I need, but it assumes that there are no repeated numbers on the set S. The problem is that I can't assume that and I don't know how to adapt the algorithm of that paper to support repeated numbers.
The paper is here: http://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf
and the algorithm is on the second page. Any tips are welcome!


texts: Is SAT with two "opposite" solutions NP-hard?

texts:
Here is a variant of the SAT problem in which a satisfying assignment must have additional properties.
Input: A 3-CNF formula $f$ with variables $x_{1\dots k}$.
Output:
For an assignment $S$ of $x_{1\dots k}$, let $\overline S$ be defined such that $x_i=true$ in $\overline S$ if and only if $x_i=false$ in $S$.
Is there an assignment $S$ such that both $f(S)$ and $f(\overline S)$ hold?

Is this problem still NP-hard?

Examples:

$f=(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor \neg x_3)\land(x_1\lor \neg x_2\lor x_3)\land(x_1\lor \neg x_2\lor \neg x_3)$
This requires $x_1=true$ in $S$, but then $x_1=false$ in $\overline S$, so $f(S)$ and $f(\overline S)$ cannot simultaneously hold.
$f=(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor \neg x_3)\land(x_1\lor \neg x_2\lor x_3)$
$S=\{x_1:true,~x_2:false,~x_3:false\}$
$\overline S=\{x_1:false,~x_2:true,~x_3:true\}$
Then both $f(S)$ and $f(\overline S)$ hold.


texts: Directed tree decompositions on subtrees of DAGs

texts: Given a DAG, is the arboreal decomposition of the DAG with the guarantee that given a node $x$, $v$ such that $x$ is reachable from $v$ are in the subtree of $x$? If not, is there a similar decomposition that achieves this?


texts:
Where can I find an introduction to probabilistic automata and what they recognize (certain functions from words to $[0,1]$)? Is there a standard term for such functions which are recognized by probabilistic automata, analogous to "regular languages" for what deterministic finite automata (DFAs) recognize?

I'm looking for something which approaches it analogously to studying basic questions on DFAs and regular languages, such as expressiveness, closure, and decidability properties.

This and this don't quite seem to be what I'm looking for.


texts: What exactly is Lawler's modification to Yen's algorithm and how does it work?

texts:
I recently read about Yen's algorithm, I understand the algorithm and it seems correct, however Wikipedia mentions that there exists "Lawler's modification" to the algorithm, which is described as basically caching all previous Dijkstra calls for the similar spur graphs. I have some questions about it:

According to the original research paper, the algorithm speeds up Yen's algorithm to $O(k \cdot n^3)$, but the Yen's algorithm described by Wikipedia is already of that complexity.
The original research paper actually seemingly contains 5 modifications to the original algorithm, although Wikipedia only describes one of them, what is going on here?
How does the mentioned modification in Wikipedia modify the runtime of the algorithm, according to me, the worst case time complexity is the same, or at most improved by constant time.
The last line of the Wikipedia description states "To perform this operation for $A^k$, a record is needed to identify the node where $A^{k-1}$ branched from $A^{k-2}$ ", but why? Can't we use the cached Dijkstra call from $A^{k-2}$ as well? Why is that bad? Since $B$(from pseudocode) is sorted and length of spur path + root path is increasing, it should never cause a problem? Maybe we are somehow missing testing out a root path + spur path, but it's un-intuitive to me how/why only the modification causes that(and why that wouldn't affect the original algorithm as well).

It would also be nice to get a commented and well tested implementation of the algorithm with the modification for reference, maybe that would make the modification clearer.


texts: How many instances of 3-SAT are satisfiable?

texts:
Consider the 3-SAT problem on n variables.  The number of possible distinct clauses is:

$$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$$

The number of problem instances is the number of all subsets of the set of possible clauses: $I = 2^C$.  Trivially, for each $n \ge 3$, there exist at least one satisfiable instance and one unsatisfiable instance.
Is it possible to calculate, or at least estimate, the number of satisfiable instance for any given n?