texts: Expected size of the min-cut, under edge perturbations

texts:
Suppose we have a graph $G(V, E)$.
Assume that the min-cut of this graph is given $C=(A/B)$ and denote the size of the cut with $|C|$.

Create a random modification of the graph:

Drop each existing edge with probability $\alpha$.
Add edges between the node-pairs that don't already have an edge with probability $\beta$.

Is it possible to say something about the expected size of the min-cut in the modified graph? (possibly under some extra assumptions)


texts: Isomorphism Problems with Unknown Single-Exponential Algorithms

texts:
Isomorphism problems come in several variants:

Group isomorphism can be solved in time $n^{O(\log n)}$
Graph isomorphism can be solved in time $n^{\log^{O(1)} n}$
Isomorphism of linear codes can be solved in time $2^{O(n)}$ ...

Where for each $n$ we assume that an isomorphism is a permutation of the set $\{1,...,n\}$. Is there a well studied variant of isomorphism problem that is known to be solvable in time $2^{O(n\log n)}$ but not in time $2^{O(n)}$?

Obs: Note that $n!\cdot n^{O(1)} = 2^{O(n\log n)}$ is roughly the time necessary to test all permutations.


texts:
I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic.

What's the reason for this?
Are there any related problems, that get better attention?

The Happynet problem is related to minimizing the energy in a Hopfield net.

The problem is defined as follows: Given a graph $G = (V,E)$ and edge weights $w: E \to \mathbb{Z}$, find a function $s: V \to \{-1,1\}$ such that for all $v \in V$, the sum $$\sum_{u: \{v,u\} \in E} s(v)s(u)w(\{u,v\})$$
is non-negative.

Put otherwise, the task is to find a cut in an edge-weighted graph $G$ such that for each node $v$ the total weight of cut-edges incident to $v$ is at most as large as the total weight of non-cut-edges incident to $v$.

Curiously, a feasible solution always exists. However, it seems that no polynomial-time algorithm is known for solving the problem. For more information, see e.g. Giannakos and Pottie (2005).


texts: Valiant's theorem says that computing the permanent of an $n\times n$ matrix is #P-hard. Is the problem of determining if a permanent is 0 any easier? This arises in the context of sequence A006063 in the OEIS, where membership is determined by the sign (0 or nonzero) of a certain permanent. (A solution to the restricted problem would be enough for me.)


texts: How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

texts:
I have these two problems:

Problem 1 (Dual bin packing problem)

Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin has capacity $W$.

Question: Find the maximum number of items that can be packed into the $k$ bins such that each bin $j$ has a set of items of weights no more than $W$.

Problem 2 (Knapsack problem)

Instance: A set of $n$ items where each item $i$ has weight $w_i$. One bin of capacity $W$.

Question: Find the maximum number of items that can be packed into the bin such that it has a set of items of weights no more than $W$.

Now given a set of items $\{w_1, \ldots, w_n\}$ and a set of $k$ bins.

If we apply the following algorithm for dual bin packing problem :

S = set of items
for each bin j do
    Solve the knapsack problem on bin j and save the result on OPT[j]
    \\ OPT[j] is the set of items packed into bin j.
    Update S by removing the items in OPT[j]
    \\ S = S - OPT[j]
    if S is empty do
        break

How can the output of this algorithm compared to the optimal solution of the dual bin packing problem?

My attempt is:

Let us denote by $OPT_b$ the optimal value of problem 1. That is, $OPT_b$ is the maximum number of items that are packed into the $k$ bins. Moreover, let us denote by $OPT_j$ the optimal number of items that are packed into bin $j$ by solving problem 2 on bin $j$. That is $OPT_j$ is the optimal value of problem 2 when applied to bin $j$. In other words, the output of the algorithm, denoted $ALG$, is equal to $\sum_{j=1}^{k}OPT_j$.

We have
$$
OPT_b \geq ALG,
$$
because, otherwise, $ALG$ will be greater than $OPT_b$ which contradicts the optimality of $OPT_b$. But can we prove the other inequality?
More probably, it is not possible to obtain the other inequality. Hence, we can argue that it could be true, sometimes, that
$$
OPT_b > ALG.
$$

So can we give a bound on $ALG$ like $$ALG\geq \rho OPT_b,$$ for some $\rho$?


texts: What is the computational complexity of the PageRank problem?

texts:
I was just wondering what the complexity of the PageRank problem is.  A description can be found here:  http://en.wikipedia.org/wiki/PageRank .  (I am referring to the problem that is solved by the PageRank algorithm, i.e., the question of how one should reasonably distribute "ranking" throughout a graph in a way that is consistent with the model presented in the article I've linked to.)

I've always been curious as to whether or not there is a deterministic polynomial time algorithm that can do as well as the actual PageRank algorithm that Google uses.

It's clear to me that the problem is FNP at worst, as it's easy to verify if a given "arrangement" of rankings for a series of nodes is consistent and valid.  I'm not sure beyond that, though.  Is it NP-hard?  I cannot think of which NP-complete problem would reduce to it.

Thank you,

Philip


texts: Is unary $\Pi_2$-SUBSETSUM coNP-complete?

texts:
Consider the following problem:

for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation

define is it true that

for every $S \subseteq \{1, ..., 2n \}$ such that $|S|=n$ there exists $H \subseteq S$ such that

$$\sum_{i \in H} a_i = A. $$

This problem belongs to coNP. Indeed, for fixed $S$ we can define the existence of required $H$ in polynomial time since there exists a pseudo-polynomial algorithm for SUBSET-SUM.

Question: Is this problem coNP-complete?

UPD I have understood that a hardness result about this problem would give a partial  answer to Stefan Szeider's question that he asked in his paper Monadic Second Order Logic on Graphs with Local Cardinality Constraints.

At this paper the author generalized Courcelle’s theorem by the following way:

  We consider problems of the following form:  Given a graph $G$ and for each vertexv of $G$ set $\alpha(v)$ of non-negative integers.  The question is whether there exists a set $S$ of vertices or edges of $G$ that
  (i) satisfies a fixed MSO-expressible property, and
  (ii)  for  each  vertex $v$ of $G$,  the  number  of  vertices  in $S$ adjacent  to $v$ plus  the number of edges in $S$ incident with $v$ belongs to the set $\alpha(v)$. We call such a problem an MSO problem for graphs with local cardinality constraints,or MSO-LCC problem, for short.

The main result of the paper is the following theorem.

  Theorem For every constant $k \ge 1$, every MSO-LCC problem can be solved in polynomial time for graphs of treewidth at most $k$.

It is natural to consider more general question.

  We consider the more general class of Q-MSO-LCC problems where cardinality constraints are applied to second-order variablesthat are arbitrarily quantified (not just existentially as for MSO-LCC problems). We show,  however,  that there exist Q-MSO-LCC problems that are already NP-hard for graphs of treewidth $2$.

However, the example of an NP-hard problem that can be expressed as Q-MSO-LCC requires two alternations of quantifies. We do not know an example of NP-hard problem that can be expressed as Q-MSO-LCC problem with one alternation of quantifies.

I claim that  unary $\Pi_2$-SUBSETSUM can be expressed as Q-MSO-LCC problem with one alternation of quantifies.  For given $a_1, a_2, a_3,..., a_{2n}$ and
$A$
consider the graph with $a_1, a_2, a_3,..., a_{2n} + 2n + 2$ vertices:

Now let $X_1$ be a set of vertices that is some subset of vertices of
the second (children of $R$) and the third levels with the following
property: If a vertex $v$ of the second level belongs to $X_1$ then all
children of $v$ belong to $X_1$. We require that $X_1$ contains $n$ vertices
of the second level (so, $R$ has $n$ neighborhoods in $X_1$).

Let $X_2$ be some subset of $X_1$ with the same property: if a vertex $v$ of
the second level belongs to $X_2$ then all children of $v$ belong to $X_2$.
We require that $X_2$ contains $A$ vertices of the third level (so, $T$
has $A$ neighborhoods in $X_2$).

I claim that $(a_1,..., a_{2n}, A)$ belongs to $\Pi_2$-unary-subsetsum iff
for all $X_1$ there exists $X_2$ with all properties written above.


texts: Why is the Toffoli Gate named after Toffoli?

texts:
I was reading the following paper:

Rolf Landauer, Irreversibility and Heat Generation in the Computing Process,  IBM Journal of Research and Development, Volume 5, Issue 3, July 1961.

On page 4, Landauer gives a construction for a $3$-bit reversible gate. Though his argument for logical irreversibility turned out to be wrong, the gate is the same as the Toffoli gate.

Seeing as this paper was published in 1961, way before Toffoli's paper (circa 1980) which gave the Toffoli gate, I am curious as to why the gate is named after Toffoli and not Landauer.


texts: Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K

texts:
I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known.

The intuition for the problem is I have two islands and a set of possible locations I can build bridges between those islands. I want to determine a minimum cost set of bridges to build such that it takes a short amount of time (no longer than $K$ hours) to travel from any point on the first island to any point on the second island.

To put this into a graph context: We are given two connected components $A$ and $B$ and a set of edges $\{e\}$ with cost $c_e$ required to add them to the graph. I want to find the minimum cost set of edges that connects $A$ and $B$ such that the maximum unweighted distance between any any two nodes between the components is at most $K$.

More precisely:

Let $x_e = 1$ if we choose to add edge $e$ and $0$ otherwise

Let $G' = A \cup B \cup \{e \mid x_e = 1\}$ be the graph augmented with the edges that we added.

Let $dist(G, u, v)$ be the length of the shorted path between $u$ and $v$ in graph $G$.

minimize $\sum_{e} x_e c_e$ such that

$ dist(G', u, v) < K\quad \forall u, v \in A \times B$


texts: Why are regular languages called "regular"?

texts:
Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages.

I suppose that, in the beginning, the adjective "regular" has been used to differentiate that type of languages from other "non-regular" or somehow abnormal languages. If so, what where these other types, and what was their non-regularity?


texts: Transitioning from quantum to classical random walks on the line

texts:
Quick version

Are there models of decoherence for the quantum walk on the line such that we can tune the walk to spread as $\Theta(t^k)$ for any $1/2 \leq k \leq 1$?

Motivation
Classical random walks are useful in algorithm design, and quantum random walks have proven useful for making a number of cool quantum algorithm (sometimes with provable exponential speed-ups). Thus, it is important to understand the difference between quantum and classical random walks. Sometimes, the easiest way to do this is to consider toy models, such as walks on the line.
There is a physics motivation as well: it is interesting to know how quantum mechanics scales to classical mechanics. But this is not very relevant to cstheory.
My personal motivation is completely orthogonal: I am trying to match some experimental data with a model that transitions smoothly from quantum to classical and is relatively intuitive.
Background
When considering quantum and classical walks on the integer line, a key difference is that the standard deviation (of the position distribution) of the quantum walk goes as $\Theta(t)$ and classical ones as $\Theta({t^{1/2}})$ where $t$ is the number of steps for a discrete model, or time in a continuous model. Note that this is not restricted to the line, and for many graphs you will see a similar quadratic relationship between the quantum and classical mixing time, I consider the restricted case of the line since I think it is easier to analyze.
As we introduce decoherence to a quantum walk (either through measurement or noise) the walk starts to behave more classically. In fact, for most measurements, we just end up with a classical walk that spreads as $\Theta(t^{1/2})$ if viewed from the right timescale. For other forms of decoherence (such as dephasing the coin, or introducing imperfections in the line) there is usually a sharp threshold below which the walk behaves quantumly (spread as $\Theta(t)$) and above which the walk starts to be classical (spread as $\Theta(t^{1/2})$). In fact, this scaling has even been suggested as the definition of a quantum walk.

Long version of question
Are there models of decoherence for a random walk on the line, such that as we vary the amount of decoherence we can achieve a standard deviation in position that scales as $\Theta(t^k)$ for any $1/2 \leq k \leq 1$? Alternatively for other graphs with a gap in mixing or hitting time, is there forms of decoherence so that we can have the mixing/hitting/standard deviation that goes as $f(t)$ for any $f \in \Sigma(g(t))$ and $f \in O(h(t))$ where $g(t)$ is the classical mixing/hitting/STD and $h(t)$ is the pure quantum. If this is not possible then is there a deeper reason why we see this sort of one-or-the-other behavior?


texts: Complexity of checking if AB intersects C

texts:
Let $A,B,C$ be subsets of a nonabelian group $G$,
and assume we know the structure of $G$ "fairly well"
(e.g., $G = S_n$ or $A_n$).
Assume that group operations take $O(1)$ time.

Is it possible to check whether $AB \cap C \ne \emptyset$ in $o(|A| |B| + |C|)$ time
(ideally quasilinear)?

Motivation:
A quasilinear time algorithm would produce
a roughly $O(|G|^{1/3})$ time algorithm for shortest paths in certain Cayley graphs
(if they are expanders).


texts: Dichotomy of the spectra of directed graphs

texts:
Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known:

It is known that a directed graph $G = (V,E)$ has an adjacency matrix $A(G)$ whose eigenvalues are binary $\{0,1\}$ if $G$ is a-cyclic.
This follows by sorting the vertices into strongly connected components: this fixes an enumeration of the vertices $v_1,.., v_n$ such that the permuted Laplacian according to this ordering is upper-triangular with $0/1$ entries.

But what is known if $G$ is the other extreme end - i.e. $G$ is a strongly-connected graph on $n$ vertices - meaning that there is a directed path between any pair of vertices.

Generally, one would need to compute the characteristic polynomial of $A(G)$ and compute its roots.
Despite $A(G)$ being a $\{0,1\}$ matrix this seems like a daunting task.
In particular, the roots of this polynomial are in general complex numbers.

The Perron-Frobenius theorem implies that at least the top eigenvalue is real and simple, but does not reveal information about the rest of the eigenvalues.

However, what if we're interested only in very weak bounds of the following form:

$\textbf{Conjecture: Dichotomy of eigenvalues}$:
Let $G$ be a directed graph on $n$ vertices.
Then either all eigenvalues of $A_G$ are real, or there exists at least one eigenvalue $\lambda$ such that $im(\lambda)\geq 1/poly(n)$.

Do such bounds follow trivially from known theorems?
Alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component?


texts:
I am trying to find references on algorithms for graphs of bounded bandwidth, in the same way as it is done with treewidth for instance.
I could only find research related to  computing the bandwidth, or properties of this measure, but not using it as assumption for better algorithms.

Also, I am very interested in a generalization of bandwidth in higher dimensions. For instance this paper studies 2-dimensional bandwidth, but considering only the $L^1$ and $L^\infty$ norms on $\mathbb N\times \mathbb N$, whereas I am more interested in the euclidean norm $L^2$. It seems natural to consider graphs of $n$-dimensional bandwidth for euclidean norm. Formally, the $n$-dimensional bandwidth of a graph $G=(V,E)$ is defined as :
$$\min_{\alpha} ~\max_{(x,y)\in E}||\alpha(x)-\alpha(y)||_2$$
where $\alpha$ ranges over injective functions $V\to \mathbb N^n$.

This is pretty natural, for instance graphs coming from discretizations of real-life systems following differential equations would likely have bounded bandwidth. Indeed, if an edge takes you to the state of the system at the next time instant, it can not be too far from your current state if the time step is small enough and the system evolves continuously. It seems that this special structure could be used to design better algorithms (in particular for solving games on these graphs), but I could not find anything on this kind of graphs.


texts: Is there a common mathematical symbology for collections?

texts:
Preface: So, it was suggested in 'Programmers' that I ask this over here.

I am being asked to define several of my algorithms in mathematical terms to describe my work to a customer. I trying to determine if anybody knows whether common operators for collections like sequences, lists, tuples, etc have been defined. If so, is there a good reference that I could be pointed to. Thanks. I am interested in the actual symbols used. I am wondering if the following would make sense or be appropiate to anybody.

Given two sequences (or strings):

S = (A, B, C) and T = (A, D, H)

In my mind, the intersection of these sequences would look like S ∩ T = (A) and the union of these sequences would be S ∪ T = (A, B, C, A, D, H)


texts: What does consistency mean for "computational theories" corresponding to inductive types?

texts:
I am currently reading the book by Luo on computation and reasoning. In the book he contrasts inductive types considered as computational theories with axiomatic theories widespread in "standard" mathematics.

However, if we have axiomatic theories, then they can be inconsistent. It seems to be impossible with inductive types. But why this is so?

P.S. As far as I understand from an answer to my previous question "Correctness" of type theory we can create an inductively defined set and consistency of the type theory + inductive type will be equivalent to the consistency of set theory. Am I right?


texts: What is the space complexity of CTL model checking?

texts:
What is the space complexity of the CTL model checking algorithm via labeling without fairness (see e.g. Model Checking by Clarke at al Section 4.1 or Principles of Model Checking by Baier et al Section 6.4) that has time complexity $O(\mathit{propertyFormulaSize} \cdot (\mathit{numberOfStates} + \mathit{numberOfTransitions}))$?

Is there a citable reference?

Details

Is the space complexity of this algorithm $\Theta(\mathit{numberOfStates} \cdot (\mathit{propertyFormulaSize} + \mathit{numberOfTransitions}))$ or smaller, e.g. $\Theta(\mathit{numberOfStates} \cdot (\mathit{propertyFormulaSize} + \mathit{ld}(\mathit{numberOfTransitions})))$ by smartly iterating over the transitions without storing them while sustaining time complexity $O(\mathit{propertyFormulaSize} \cdot (\mathit{numberOfStates} + \mathit{numberOfTransitions}))$?


texts: Shortest distance problem with length as functions of time

texts:
Motivation

The other day, I was travelling around the city with public transport and I made up an interesting graph problem modelling the problem of finding the shortest-time connection between two places.

We all know the classical "Shortest path problem": Given a directed graph $G=(V,E)$ with edge-lengths $w_e\in\mathbb{R}_0^+,\,e\in E$ and two vertices $s,t\in V$, find the the shortest path between $s$ and $t$ (i.e., the path minimizing the total edge-length). Assuming non-negative edge-lengths, there are various algorithms and the problem is easy.

This is a good model for the case that we are walking, for example. The vertices are crossroads in our network of roads and each edge has fixed length -- in meters, for instance. Another possible interpretation of the edge-weights $w_e$ is the time that it takes us to go from one of its vertices to the other. This is the interpretation that interests me now.

Problem

I now want to model the following situation. I want to travel from point A to point B in a city via public transport and minimize time. The public transport network can be easily modelled as a directed graph as you would expect. The interesting part are the edge-weights (that model time) -- public transport (buses, for instance) leave only in certain intervals, which are different for every stop (vertex in graph). In other words -- the edge-weights are not constant, they change depending on the time we want to use the edge.

How to model this situation: We have a directed graph $G=(V,E)$ and an edge-weight function $w\colon E\times \mathbb{R}_0^+\rightarrow\mathbb{R}_0^+$ that takes time as its argument and returns time that it takes to use the edge in our path. For example, if the bus from vertex $v$ to vertex $u$ leaves at $t=10$ and it takes $5$ time and we arrive at vertex $v$ at $t=8$, then $w(vu,8)=7$ is the edge-weight. Clearly, $w(vu,10)=5$.

It is slightly tricky to define total weight of path, but we can do it recursively. Let $P=v_1v_2\ldots v_{k-1} v_k$ be a directed path. If $k=1$ then $w(P)=0$. Otherwise, $w(P)=w(P')+w(v_{k-1}v_k,w(P'))$, where $P'$ is the sub-path of $P$ without $v_k$. This is a natural definition corresponding to the real-world situation.

We can now study the problem under various assumptions on the function $w$. The natural assumption is
$$w(e,t)\leq w(e,t+\Delta)+\Delta \text{ for all }e\in E,\Delta\geq 0,$$
which models "waiting for $\Delta$ time".

If the function "behaves nicely" it may be possible to reduce this problem to the classical Shortest path problem. But we could ask what happens when the weight-functions get wild. And what if we drop the assumption on waiting?

Questions

My questions are the following.

Has this problem been asked before? It seems kind of natural.
Is there any research on it? It seems to me that there are various subproblems to be asked and studied -- mainly regarding the properties of the weight-function.
Can we reduce this problem (possibly under some assumptions) to the classical shortest path problem?


texts:
Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time?

sameCycle($\pi,x,y$): determines whether $x$ and $y$ belong to the same permutation cycle;
transpose($\pi,x,y$): replaces $\pi$ by the composition $(xy)\pi$ of the transposition $(xy)$ with $\pi$.

This can be viewed as a special case of the fully-dynamic graph connectivity problem in which the connected components are always cycles. Therefore it admits such a data structure, but one may hope that the cycle structure makes the problem easier and/or faster.


texts: Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

texts:
An "algorithm" for calculating $ax+b$ would take the steps

Calculate $a$ times $x$
Calculate $b$ plus the result of previous line.

But if the values of $a$ and $b$ are known, can we create a more efficient algorithm for the task?

Of course, when $a = 1$, I can optimize the previous algorithm by simply skipping the first step, and when $b = 0$, an optimization would be to skip step 2. But is there always an optimization that I can do?

More formally

Let $originalAlgorithm$ be the two-step algorithm above. What I want is a meta-algorithm, $M$ that
$$
M(a,b) = optimizedAlgorithm
$$
and, of course,
$$
optimizedAlgorithm(x) = originalAlgorithm(x) = ax+b
$$
but $optimizedAlgorithm$ is more time-efficient than $originalAlgorithm$.


texts: How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

texts:
Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA).

A NFA is called unambiguous if every word $w\in \Sigma^*$ has at most one accepting path.

This means $DFA\subset UFA\subset NFA$.

Known related automaton results:

  NFA minimization is PSPACE-Complete.
  NFA minimization over finite languages is DP-Hard.
  UFA minimization is NP-Complete.
  There exists NFAs which are exponentially smaller than minimal DFAs.
  (Also - there exists UFAs which are exponentially smaller than minimal DFAs - R B).

The question is: can we find a regular language $L$ such that the there exists a NFA accepting $L$ which is exponentially smaller (state-wise) than the minimal UFA for $L$?
Can this happen for a finite language?

I believe such (finite) $L$ exists, but my proof currently relies on the Exponential Time Hypothesis to hold, and was wondering if someone has a proof which doesn't rely on it.

Also, can someone characterize the set of languages for which such size difference exist?

EDIT: @Shaull gave a nice link to a paper dealing with infinite language. Does anyone know a similar result for a finite language?


texts:
I am considering the language of all satisfiable propositional logic formulae, SAT (to ensure that this has a finite alphabet, we would encode propositional letters in some suitable way [edit: the replies pointed out that the answer to the question may not be robust under varying encodings, so one needs to be more specific -- see my conclusions below]). My simple question is

  Is SAT a context-free language?

My first guess was that today's (early 2017) answer should be "Nobody knows, since this relates to unresolved questions in complexity theory." However, this is not really true (see answer below), though not completely false either. Here is a short summary of things we know (starting with some obvious things).

SAT is not regular (because even the syntax of propositional logic is not regular, due to matching parentheses)
SAT is context-sensitive (it is not hard to give an LBA for it)
SAT is NP-complete (Cook/Levin), and in particular decided by nondeterministic TMs in polynomial time.
SAT can also be recognized by one-way nondeterministic stack automata (1-NSA) (see W. C. Rounds, Complexity of recognition in intermediate Level languages, Switching and Automata Theory, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5)
The word problem for context-free languages has its own complexity class $\textbf{CFL}$ (see https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cfl)
$\textbf{CFL}\subseteq\textbf{LOGCFL}\subseteq\textbf{AC}^{\textbf{1}}$, where $\textbf{LOGCFL}$ is the class of problems logspace reducible to $\textbf{CFL}$ (see https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#logcfl). It is known that $\textbf{NL}\subseteq\textbf{LOGCFL}$.
It is not known whether $\textbf{NL}\subsetneq\textbf{NP}$ or $\textbf{NL}=\textbf{NP}$ (in fact, even $\textbf{NC}^{\textbf{1}}\subsetneq\textbf{PH}$ is open; I think I got this from S. Arora, B. Barak: Computational Complexity: A Modern Approach; Cambridge University Press 2009). Hence, there cannot be any $\textbf{NP}$-complete problem that is known to not be in $\textbf{LOGCFL}$. Hence, it must be unknown if SAT is in $\textbf{LOGCFL}$.

However, this last point still leaves the possibility that SAT is known to not be in $\textbf{CFL}$. In general, I could not find much about the relationship of $\textbf{CFL}$ to the $\textbf{NC}$ hierarchy that might help to clarify the epistemic status of my question.

Remark (after seeing some initial answers): I am not expecting the formula to be in conjunctive normal form (this will not make a difference to the essence of the answer, and usually arguments still apply since a CNF is also a formula. But the claim that the constant-number-of-variables version of the problem is regular fails, since one needs parentheses for syntax.).

Conclusion: Contrary to my complexity-theory inspired guess, one can show directly that SAT is not context-free. The situation therefore is:

It is known that SAT is not context-free (in other words: SAT is not in $\textbf{CFL}$), under the assumption that one uses a "direct" encoding of formulae where propositional variables are identified by binary numbers (and some further symbols are used for operators and separators).
It is not know if SAT is in $\textbf{LOGCFL}$, but "most experts think" that it is not, since this would imply $\textbf{P}=\textbf{NP}$. This also means that it is unknown if other "reasonable" encodings of SAT are context-free (assuming that we would consider logspace an acceptable encoding effort for an NP-hard problem).

Note that these two points do not imply $\textbf{CFL}\subsetneq\textbf{LOGCFL}$. This can be shown directly by showing that there are languages in $\textbf{L}$ (hence in $\textbf{LOGCFL}$) that are not context-free (e.g., $a^nb^nc^n$).


texts: Runtime of Tucker's algorithm for generating a Eulerian circuit

texts:
What is the time complexity of Tucker's algorithm for generating a Eulerian circuit?
The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an arbitrary 2-regular detachment of the graph and then generates a Eulerian circuit.

I couldn't find any reference that says, for example, how the algorithm constructs an arbitrary 2-regular detachment of the graph, what data structures it uses, what the time complexity is, and so on. Any ideas?


texts: Rebalancing balanced binary search tree when decreasing all keys to the right of a path?

texts:
Given a balanced binary search tree, suppose I have an operation decrease-right-keys(k, s) that operates as follows: when I call this operation on a tree $T$, I decrease all keys by $s$ in the right subtrees along the path created by searching for $k$.

For example, suppose I call decrease-right-keys(1, 3). I would search for $1$. Along the search path, I would decrease the key of every element of every right subtree along this path by $3$.

My question is, is there a way to create a balanced binary search tree with this operation operating in $O(\log{n})$ time or $O(\log{n})$ amortized time? I realize that I can't actually decrease all keys in all the right subtrees because that would require $O(n)$ time potentially. But maybe there's a way to implement the operation without having to physically decrease all the keys?


texts: When is a non-unitary quantum system only theoretical?

texts:
Suppose we construct a non-unitary quantum system α in hilbert space. It entails that this system would have no direct parallel in quantum circuitry as it is a requirement that all quantum gates are unitary and therefore the function constructed from them is also unitary. But does this mean that we cannot practically implement α?

A potential parallel is found in the simulation of classical computations on a quantum computer, achieved by simulating an information-destroying NAND gate using an information-preserving Toffoli gate. If a non-unitary quantum system was such because it implemented a 'quantum NAND gate', it would be possible to redesign it as a unitary system using a Toffoli gate. It is not clear to me (and I cannot immediately find literature on this) if there are clearly defined bounds on what non-unitary operations can be simulated using unitary equivalents.

Is there a clearly defined subset of non-unitary quantum systems where α is practically implementable? Is it, perhaps, universal?


texts:
Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$
Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$


texts: Maximal munch rule issue for lexers: is detection decidable?

texts:
Edit: I realise that one of my problems is that I don't have a clear definition of my problem, which makes the question of whether it is detectable hard to answer.

I'm therefore already happy with any reference in which this particular problem is discussed at all - I haven't found any such reference myself, and with any luck, I can derive a good definition of my problem from that, which will hopefully lead to a solution.

Original:

Suppose we have this lexical definition:

X := a*
Y := a

and this context-free grammar:

S := X Y

and we use any lexer and parser combination to generate a recogniser for this language, in which the lexer uses the 'maximal munch' or 'longest match first' rule.

The specification might seem to be trivially equivalent to the regular expression "$a$+", but it isn't: in fact, it recognises no strings at all. The reason is that $X$ 'eats' all the $a$ characters present in the input because of 'maximal munch', leaving none for $Y$ to consume, so the parser always rejects the input.

I'd like to know if it is decidable if such a problem is present in a given lexer and parser specification.

Note that this is decidable if only a single token is the culprit. Let $L_T$ be the language generated by some token (= regular expression) $T$, and let $L_R$ be the language generated by the 'follow' language of this token, that is, the language of all strings that are postfixes of the occurrence of $T$ in the specification. In the example above, $T=X=a^*$ and $R=Y=a$, though in general, $R$ will be a lot more complicated.

The problem can then be formulated as (where $+\!\!\!\!+\,$ denotes concatenation):

$(L_T +\!\!\!\!+\, L_R) \cap L_T \neq \emptyset$

If this intersection is nonempty, then $T$ will eat up the match made by $R$. As $L_T$ is regular, this is decidable. (note that a better, less stringent rule might be that $L_T +\!\!\!\!+\, L_R$ is not a subset of $L_T$, I'm not sure)

Unfortunately, grammars like $a b a^* b^* a b$ (split into 6 tokens) do not accept the string $abab$, and here no single token is the culprit, so the above method doesn't work.

Searching the web turned up nothing, not even that anyone else has ever noticed this problem, although I might just be using the wrong keywords. This surprised me somewhat, so chances are I'm either wrong or this is never a problem in practice.

I stumbled upon the above problem when toying with modularised parsing, but the above problem isn't specific at all for modularised parsing (though it can more easily become a problem if someone forgets to declare whitespace somewhere, in which case I'd like to warn the user, hence the above question).


texts: Can a natural graph problem be universally hard?

texts:
Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to  any  polynomial-time recognizable graph class? To avoid degenerated cases, let us consider only  dense  graph classes, in which   the number of non-isomorphic $\leq n$-vertex graphs grows exponentially with $n$.

 Notes:

(1) Both a "yes" or a "no" answer would be quite interesting. If the answer is yes, then we would have a natural  $\mathsf{NP}$-complete graph property that could be called  universally hard,  because it preserves hardness even when  restricted to any reasonable graph class.  If the answer is no, it would mean that every natural $\mathsf{NP}$-complete graph property can be made easy on some nontrivial graph class.

(2) It is important to consider only polynomial-time recognizable graph classes, to exclude that the hardness of the property is simply shifted to the class.
For example, 3-COLORABILITY becomes trivial when restricted  to 3-colorable graphs.


texts: Factoring Cartesian bitwise join of bit vectors

texts:
(This question has been substantially revised in an attempt to word it clearly.)

I am wondering if anyone has seen this problem. Let $[n] = \{1,\ldots,n\}$ for an integer $n$. Consider two finite multisets of bitstrings, $$ A=\{a_i\}_{i\in[r]} \quad\text{and} \quad B=\{b_j\}_{j\in[s]} \;,$$ where each $a_i \in \{0, 1\}^n$ and each $b_j \in \{0, 1\}^n$. We may compute from this a "Cartesian bitwise join" $C$, which is also a multiset of bitstrings $C= \{c_{i,j}\}_{(i,j) \in [r] \times [s]}$ for size $|C| = |A| \cdot |B| = rs$, where
$$ c_{i,j} = a_i \vee b_j$$ where "$\vee$" is bitwise-OR.

Question. If you are given such a multi-set $C$, without any particular indexing, can you find multi-sets $A$ and $B$ of which $C$ is the Cartesian bit-wise join? Equivalently: given a sequence $C = (c_k)_{k\in[m]}$ consisting of bitstrings in $\{0,1\}^n$, can you find sequences $A = (a_i)_{i\in[r]}$ and $B = (b_j)_{j\in[s]}$ such that $m = rs$, and a bijection $\varphi: [r] \times [s] \to [m]$, such that $$c_{\varphi(i,j)} = a_i \vee b_j$$ for all $(i,j) \in [r] \times [s]$?

This problem is equivalent to the following problem. Consider the ring $R$ whose elements are strings in $\{0,1\}^n$, where addition is done bit-wise by the operation $x + y = x \oplus y \oplus 1$ (where $\oplus$ is parity) with $1^n$ being the identity, and multiplication is the bit-wise OR with $0^n$ being the identity. For some particular ordering of the elements of $A$, we may present $A$ as an element of $R^r$, and similarly present $B$ as an element of $R^s$.
The Cartesian bitwise join corresponds to the outer product of $A$ and $B$,
$$ C \;=\; A B^\top \;=\; \begin{bmatrix} a_1 \vee b_1 & a_1 \vee b_2 &\cdots& a_1 \vee b_s \\
a_2 \vee b_1 & a_2 \vee b_2 & \cdots & a_2 \vee b_s \\
\vdots & \vdots & & \vdots \\
a_r \vee b_1 & a_r \vee b_2 & \cdots & a_r \vee b_s
\end{bmatrix}\;,$$
except interpreted as a multiset rather than a matrix (that is, the elements of $C$ are not assigned to particular coefficients of an $r \times s$ matrix). Given a multiset $C$ with composite cardinality $m \in \mathbb N$, can its elements be mapped to coefficients of an $r \times s$ array (such that $m = rs$) which is an outer product of the above form?

(By interchanging 0s and 1s in all of the bitstrings, we may replace the bit-wise OR "$\vee$" with the bit-wise AND "$\wedge$", in which case we may take $R$ to be the ring whose elements are strings in $\{0,1\}^n$, where addition is as vectors over $\mathbb Z_2$, and multiplication is the bit-wise AND. )

One may consider additional constraints on this problem, such as minimum Hamming weight of the bitstrings in $A$ and $B$ (in the Cartesian join formulation). We certainly require that $A,B \ne \{0^n\}$ to prevent a trivial solution.

This problem arises in an EE & complexity theory context. I am looking for other cases or analysis of it.
The problem is somewhat analogous to factoring but does not seem to have a unique factorization.
Note that bitvectors can be naturally modelled as hypergraphs so maybe something from that theory is applicable. I did research hypergraph products but that theory does not seem to apply directly. The problem translates to finding two hypergraphs $H'$ and $H''$ given a hypergraph $H$, such that the $H$ can be formed by taking all pairwise unions of edges in $H'$ and $H''$.


texts: Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets)

texts:
I have already asked this question in StackOverflow (open bounty closing on Aug 25th).

Let's say I have some finite sets: A, B, ..., K

I also have A1, A2, ... An, which are subsets of A; B1, B2, ... Bn, which are subsets of B, etc.

Let's say S is the cartesian product A x B x ... x K

and Sn is the cartesian product of An x Bn x ... x Kn

Is there an algorithm to efficiently determine if the union of all Sn is equivalent to S?

Some pointers to literature where I can study this problem are greatly appreciated.


texts: A question about combinatorial design in Nisan-Wigderson Generator

texts:
Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that:

$\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$.
$\forall i \neq j \in [m]$, $|S_i \cap S_j| \le a$.

For example, it is known that such designs exist for $a = \log m$, $\ell = C\log m$ and $d = O(C^2\log m)$. I am interested (in general) in such kind of settings of parameters: where you can generate a large number ($m$ in total) of small sets (each of size $O(\log m)$) over a small universe ($O(\log m)$ items in total), and with a small pairwise intersection ($\log m$).

My question concerns with the behavior of intersections. Specifically, fix any $S_t$ in the system to consider. Consider the sets before it, $S_1,\dots,S_{t-1}$. Start with $S_1$ and find the maximal $i$ such that $|\left(\bigcup_{j=1}^i S_j\right) \cap S_t| \le a$. Let $S_1,\dots,S_i$ be the first chunk you find. Then you repeat this process starting at $S_{i+1}$ (find the second chunk). Let the total number of chunks you identify this way be $k$ (so $k$ is in general a function of $t$ and the set system).

Now, do we know anything about upper bounding $k$? (over all choices of $t$, say). The intuition is that, at least on average, it should not be the case that $k$ can always reach ${\ell \choose a}$. Do we know anything about constructing an $(\ell, a)$-design (with the above settings of parameters in general) so that one can bound $k$ in the worst-case?

Thanks in advance for any help!


texts: Average case or beyond worse case analysis for non-convex optimization procedures?

texts:
I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature.

It is known that global optimization of non-convex functions is NP-hard in general (1). However, it seems for some large classes of structured non-convex optimization problems e.g.,, matrix factorization (2), there are no spurious local minima (all minima are global, and Fermat's optimality condition is sufficient for global minimality). I believe there are many more examples of this that have recently been proved.

Here are my questions:

What are the known regularity conditions under which we know that indeed non-convex global optimization (or even escaping saddle points to obtain global minima) is possible? References are appreciated.
Are there beyond worse case/smoothed analysis or even average-case results in non-convex optimization that show an algorithm (say for example, the gradient method, or a stochastic/accelerated/noise-perturbed version of it) usually optimizes non-convex functions to epsilon-approximate local/global optimality? Essentially just like the simplex method "usually" takes polynomial time (3), is there an equivalent result available for non-convex optimzation? (Informally, this would show that the hardness is 'concentrated' in 'pathological' functions)
Are there results that show, for example, that 'easy to optimize' non-convex functions are dense in some larger space of non-convex functions? A result like this would show that non-convex functions are 'close' (in some metric put on the space) to easy-to-optimize functions. I'm not sure if this is a well posed question or not, also unsure if it is interesting. The reason this seems like a fruitful question is we have recently seen papers on functions that are 'locally-strongly convex' or 'strongly non-convex' with second derivative matrices (hessians) that are 'approximately' PSD. It seems that this type of result could be extended to a more quantitative description of how many functions are not 'approximately locally convex'/easy-to-optimize.

With all questions listed above, any pointers to key papers/reviews would be extremely appreciated!

Citations:

(1) Avrim L Blum and Ronald L Rivest. Training a 3-node neural network is NP-complete. Neural
Networks, 5(1):117–127, 1992.

(2) Rong Ge, Jason Lee, and Tengyu Ma. Matrix Completion has No Spurious Local Minimum.

(3) Spielman, D. A., & Teng, S.-H. (2004). Smoothed analysis of algorithms: Why the simplex
algorithm usually takes polynomial time. Journal of the ACM, 51, 385–463.


texts: Finding a cellular automaton that reproduces a finite-sized spacetime patch with reduced coloration

texts:
Note: This question is an extension of: Computational complexity of finding a (1D deterministic) CA that achieves a desired spacetime history "patch" after $t$ iterations, which Marzio De Biasi took time to answer in a very nice manner.

Let $S$ be a spacetime patch (http://www.wolframscience.com/nksonline/page-960b-text) with $n$-colors corresponding to a one-dimensional deterministic cellular automata $(Q,\sigma)$.  I generate a reduced coloring spacetime patch $S_r$ by partitioning the $n$ colors in $S$ into subsets, and then repainting $S$ s.t. any two colors in the same subset will now have the same color.  For example, $S$ could have cells colored {Red, Green, Yellow, Blue}, but to generate $S_r$, we form the subsets {{Red}, {Green, Yellow, Blue}}, and repaint the Red cells WHITE, and the Green/Yellow/Blue cells BLACK.

Next, I tell you the value of $n$, i.e. the original number of colors in $S$, I explain how the colors were partitioned into subsets, and I define the strictly local communication rules between cells (e.g. I could say that communication between cells defined by a 3-neighbor von Neumann relation).  However, I only provide you the reduced coloration spacetime patch $S_r$.

Your task is to come up with an $n$-color $k$-state one-dimensional deterministic CA that accurately generates $S_r$ after some color partitioning and repainting procedure that (a) could be the same as the one I describe, or (b) could be something novel.  What is the computational complexity of your task?

My intuition says that this problem should become impractical to solve in the worst-case as the number of colors increases to somewhere between $n = 10$ to $100$, and where we have spacetime patches that sample a sufficiently large fraction of possible CA states.  Here, there should be a combinatoric explosion in the number of possible color assignments to the monochromatic neighborhoods in $S_r$.

Admittedly this could be wrong, but if it is the case, it isn't clear to me what complexity class this problem should fall into.  Is it NP-complete but not PSPACE complete, for example?

For an example of what I'm trying to do, here's a deterministic one-dimensional CA with $n = 3$ colors initiating from random initial conditions:

http://www.wolframalpha.com/input/?i=CA+3-color%2C+range+1%2C+rule+4594122302107
(5th "sub-box" down)

Now imagine I repaint the cells in the spacetime patch shown in the above link, e.g. by taking the {0, 1, 2} colors, making the subsets {{0, 1}, {2}}, and then painting the 0 and 1 cells WHITE and the 2 cells BLACK.  Call this repainted spacetime patch $S_r$.  I then ask you to come up with an $n=3$ color CA that can reproduce the provided spacetime patch $S_r$ by running the CA for an appropriate number of iterations $t$ to generate a spacetime patch of the right size, and then performing a recoloration as you see fit.

You might be able to do the above without needing $n = 3$ colors.  If so, that's fantastic.  But in the worst case, you'll run into trouble, because we're restricting long-range communication between cells (i.e. cells can only communicate with their nearest-neighbors) so you'll encounter situations where there aren't enough states to get away with fewer colors.

Said differently, the number of global configurations for a deterministic one-dimensional CA is at most $n^j$ (or $n^j \times$ (number of possible CA rules) for all possible $n$-color 1D cellular automata) where $j$ is the number of cells in CA's initial state.  The total number of global configurations, the vast majority unreachable by the $n$-color CA, is $n^{(j*t)}$ where $j \times t$ is the size of the spacetime patch.  So more colors mean more possible CA configurations for the same size initial input, and thus, the repainted  $S_r$ could easily correspond to a global configuration that can't be reached by a CA with fewer than the number of colors used to generate the spacetime patch $S$ prior to the repainting procedure.


texts: Does ${\bf L} \neq {\bf NL}$ imply ${\bf P} \neq {\bf NP}$?

texts:
This question is inspired by this question Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

We do know that ${\bf L}$ could equal ${\bf NL}$ and at the same time ${\bf P}$ could be different from ${\bf NP}$. I was wondering whether or not the inequality between ${\bf L}$ and ${\bf NL}$ imply inequality between ${\bf P}$ and ${\bf NP}$. Or we just simply do not know...


texts: Evidence that Graph Isomorphism problem is not $NP$-complete

texts:
Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph Isomorphism can not be $NP$-complete unless the polynomial hierarchy [1] collapses to the second level. Also, the counting[2] version of GI is polynomial-time Turing equivalent to its decision version which does not hold for any known $NP$-complete problem. The counting version of $NP$-complete problems seems to have much higher complexity. Finally, the lowness result [3] of GI with respect to $PP$ ($PP^{GI}=PP$) is not known to hold for any $NP$-complete problem. The lowness result of GI has been improved to $SPP^{GI}=SPP$ after Arvind and Kurur proved that GI is in $SPP$ [4].

  What other (recent) results can provide further evidence that GI can not be $NP$-complete?

I posted the question on Mathoverflow without getting an answer.

[1]: Uwe Schöning, "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124

[2]: R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131–132

[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity 2 (4): 301–330

[4]: V. Arvind and P. Kurur. Graph isomorphism is in SPP, ECCC TR02-037, 2002.


texts: Other applications of Karger-Stein branching amplification?

texts:
I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class.  This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don't know  any other applications of the main technique.  (So it's hard to assign homework that drives the point home.)

Karger and Stein's algorithm is a refinement of an earlier algorithm of Karger, which iteratively contracts random edges until the graph has only two vertices; this simple algorithm runs in $O(n^2)$ time and returns a minimum cut with probability $\Omega(1/n^2)$, where $n$ is the number of vertices in the input graph.  The refined "Recursive Contraction Algorithm" iteratively contracts random edges until the number of vertices drops from $n$ to $n/\sqrt{2}$, recursively calls itself twice on the remaining graph, and returns the smaller of the two resulting cuts.  A straightforward implementation of the refined algorithm runs in $O(n^2\log n)$ time and returns a minimum cut with probability $\Omega(1/\log n)$.  (There are more efficient implementations of these algorithms, and better randomized algorithms.)

What other randomized algorithms use similar branching amplification techniques?  I'm especially interested in examples that don't (obviously) involve graph cuts.


texts: Circuit complexity and statistical tests

texts:
A few years ago, I took a class on complexity theory from Steven Rudich, and I remember him giving an interesting lecture connecting statistical tests (as found in statistics departments!) with circuit complexity. I remember him claiming something vaguely like: you could use circuits to abstractly characterize what a statistical test was, and that there were fundamental limits on what sorts of patterns statistical tests could identify.

Unfortunately, I remember neither precisely what his claim was, nor even enough keywords to let me Google for it. Does anyone know what he could have meant, and supply me with some references?

(My apologies for the vagueness of this question: if I knew enough to ask precisely, I wouldn't need to ask!)


texts: Is graph isomorphism in UP ${\cap}$ coUP?

texts: Is graph isomorphism (the decision problem) in $\mathsf{UP}\cap \mathsf{coUP}$? Here $\mathsf{UP}$ is the class of decision problems accepted by an unambiguous Turing machine (see the complexity zoo).


texts: What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution?

texts: I know that in the general case it isn't efficient. However, I'm wondering if there are any good techniques in the quadratic case over the reals, specifically if there is a polynomial time solution.


texts: Distinguishing a biased coin with a small set of tests

texts:
Say we have a "coin" $f : [n] \to \{\pm 1\}$ so that either $f$ is balanced, or $f$ is $\epsilon$-far from being balanced.

It's a classic result that sampling $O(1/\epsilon^2)$ random points of $f$ are enough to determine if $f$ is biased. That is, if $\mathcal{F} = \binom{[n]}{O(1/\epsilon^2)}$ is the collection of all subsets of size $O(1/\epsilon^2)$, then with probability at least $2/3$ over a random choice of a set $S$ from $\mathcal{F}$, the bias of $S$ will be within $\epsilon/2$ of the true bias of $f$ (correctly determining if $f$ is balanced/unbalanced).

Are there smaller families $\mathcal{F}$ that have the same property? For example, is it possible to find a collection of poly($n, 1/\epsilon)$ sets where 2/3 of the sets have bias close to the bias of $f$, for any $f$ either balanced or $\epsilon$-far from balanced?


texts: What is the complexity of this submatrix selection problem?

texts:
We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks.
We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum of entries of sub matrix is maximized.

What is the complexity of this problem?

What is the complexity of this problem if there is an unique maximum?


texts: On simultaneous embeddings with different vertex sets

texts:
The topic of simultaneous embeddings of planar graphs is a common sight in the recent graph drawing literature. A recent survey of the topic is given by Bläsius, Kobourov and Ritter. I am interested in the case of Simultaneous Embeddings with Fixed Edges (SEFE), which is the following problem:

Input: Two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$, sharing a common subgraph $G=(V=V_1 \cap V_2, E=E_1 \cap E_2)$.

Problem: Do there exist planar embeddings of $G_1$ and $G_2$ such that the vertices and the edges of $G$ are mapped to the same vertices and Jordan arcs in both embeddings (i.e., do there exist two embeddings which agree on $G$).

The complexity of SEFE is an open problem.

According to the aforementioned survey, this problem can be solved in linear time when the intersection graph $G$ is a star, as it can be reduced to a variant of $2$-page embedding, for which an algorithm is known. However, looking at the corresponding paper, the input is slightly different: the vertex sets of $G_1$ and $G_2$ are assumed to be the same. Without this assumption, neither the reduction nor the corresponding algorithm seem to adapt (at least the definition of splitters should be modified).

Hence my questions:

Maybe I am missing something obvious: In general for the SEFE problem, is there an easy way to reduce the case of $V_1 \neq V_2$ to the equal vertex set case? (obviously one can just add copies of the exclusive vertices of $V_1$ to $V_2$ and vice versa, but this changes a lot the structure and the connectivity of the intersection graph, which is critical for most algorithms)
If not, is a polynomial-time algorithm known to solve the SEFE problem when the intersection graph is a star but the vertex sets are different?


texts: Does every regular language contains a strictly locally testable language?

texts: Let $L$ be an infinite regular language, then does there exists a strictly locally testable  infinite language $P$ such that $P \subseteq L$?


texts: Is it possible to use arbitrary fixpoint values on EAL without losing strong normalization?

texts: From this question, the answerer states EAL-based languages can use arbitrary fixpoint types without losing strong normalization, because their normalization (and complexity) properties comes from linear types and the stratification of terms. I wonder, though, if the same can be done for value-level fixed-points; i.e., is it possible to express things such as infinite lists without losing strong normalization? If one could mechanically restrict the unrolling of fix in the same style that duplication is restricted by let and boxes, then, I believe, that could be doable. Is it?


texts: Finding maximum number of disjoint set covers

texts: Let $U = [1..n]$ be the universe of $n$ elements and $C$ be a  collection of subsets of $U$, $C= S_1, \dots, S_m$, where $S_i \subset U$. Then the problem is to find as many partitions of $C$, such that each partition covers the universe U. The hardness results can be  derived for this problem, but are there any approximation algorithms known for this ? I gather that the geometric version of this problem has some approximation algorithms, but is there any thing known in the general case ?


texts: Complexity of validity of first-order logic over finite words with bounded quantifier alternation?

texts:
I'm concerned with the validity problem for sentences of first-order logic over finite words, i.e. $FO[\le]$ interpreted over finite subsets of $\mathbb{N}$. AFAIK it should be nonelementary.

However, I'm looking at the complexity of the levels of the alternation hierarchy, i.e., $\Sigma_n$ and $\Pi_n$ fragments of $FO[\le]$. For example, the satisfiability problem for Bernays-Schönfinkel formulae, those of the form $\exists^*\forall^*\phi$, a.k.a. $\Sigma_2$-formulae, is in general $\mathsf{NEXPTIME}$-complete, and this should hold also on words, is this correct? But then what is the complexity of satisfiability/validity for $\Sigma_n$-formulae for a fixed $n$?

I've found a lot of papers and surveys about the expressibility problem for these fragments, that is, to decide whether a given language can be expressed in a given fragment, but nothing on the computational complexity of the validity/satisfiability problem. I'm feeling like I'm missing something very trivial or commonly known.

Can you give me any reference?


texts: Is adiabatic quantum computing as powerful as the circuit model?

texts:
Much of the quantum computing literature focuses on the circuit model. Adiabatic quantum computing is not based on applying a sequence of unitary operators, but on changing a time-dependent Hamiltonian. I am looking for insight into any of the following.

Is adiabatic quantum computing as powerful as the circuit model, or is it inherently less powerful?
Are there complexity classes specifically related to adiabatic computing as opposed to the circuit model?
How does one quantitatively measure the power of adiabatic computing versus the power of the circuit model?


texts: Characterizing closure under expansion/reduction for big-step semantics?

texts:
Two common ways of formulating operational semantics for programming languages based on lambda-calculus are big-step and small-step semantics.

In a big step semantics, you give a relation $e \Downarrow v$ which directly relates an expression to the value it computes.
In a small-step semantics, you give a transition relation $e \mapsto e'$ which does one step of evaluation, and you get to a value by iterating the transition relation. $e \mapsto^{*} v$.

These two relations are equivalent, in the sense that $e \Downarrow v$ if and only if $e \mapsto^{*} v$.

However, some things are easier to define one way or another. For example, we can say that a set of terms $R \subseteq \mathrm{Exp}$ is closed under expansion if it satisfies the property that:
$$\forall e \in R, e' \in \mathrm{Exp}.\;e' \mapsto e \;\mathrm{implies}\; e' \in R$$

Likewise, a set $R$ is closed under reduction if if satisfies:

$$\forall e \in R, e' \in \mathrm{Exp}.\;e \mapsto e' \;\mathrm{implies}\; e' \in R$$

It's not immediately obvious to me how to formulate expansion or contraction in terms of a big-step semantics. Does anyone know how?


texts:
Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$.

I am interested in the following problem:

Given $x_1,\dots,x_n \in \{0,1\}^d$ and $y_1,\dots,y_n \in \{0,1\}^d$, I want to determine whether there exists $i,j$ such that $x_i \le y_j$.

How efficiently can this be solved?  Pairwise comparison requires $\Theta(n^2)$ comparisons.  Can we find a more efficient algorithm?

I would be fine with assuming that the $x$'s and $y$'s come from some reasonable distribution and evaluating using the expected running time, if that helps.  We can assume $d$ is small compared to $n$.

Equivalent statement of the problem: Given sets $S_1,\dots,S_n$ and $T_1,\dots,T_n$, determine whether there exists $i,j$ such that $S_i \subseteq T_j$, where all sets are over the universe $\{1,2,\dots,d\}$.


texts: Algebraic effects and handlers, dynamic effects

texts:
What exactly are dynamic effects? What does it mean to dynamically create an effect?

In a language with algebraic effects and handlers (such as Eff or Koka) one could already do different operations based on runtime information, for example:

if x > 10 then
  get ()
else
  put 10

In this case the actual operation done will only be known at runtime. But in the Frank paper ("Do be do be do") they talk about dynamic effects in the sense of ML-style references. In what sense are references a dynamic effect that cannot be done in Eff (without resources) or Koka? Also why were resources removed again from Eff?


texts: For efficient algorithm on "minimization" knapsack problem

texts:
Suppose there are two arrays of positive numbers, $a[\cdot]$ and $b[\cdot]$, and value $B>0$. How to pick a set of indexes $I$, so that

$\sum_{i\in{I}}{b[i]}\geq{B}$

To minimize $\sum_{i\in{I}}{a[i]}$

I know this problem sounds like knapsack problem, but the objective is really to minimise, not maximise. Does this make a difference if I want to seek a polynomial-time, approximate algorithm?


texts: Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size

texts:
I'm looking for an efficient/simple (even if not necessarily cryptographically strong) algorithm for implementing pseudorandom permutations with domain cardinality other than a power of 2.  (FWIW, the domain cardinality I'm interested in at the moment is $900,000$.)

All the algorithms I've found for doing this aim for cryptographic strength, and tend to be relatively slow and intricate.

One exception to the last point, arguably, is the standard Feistel network algorithm, which is at least fairly simple.  Unfortunately, AFAICT, this algorithm works only for permutations with domain size $2^{2m}$, with $m\in\mathbb{Z}^+$.

(I've found some generalizations of Feistel networks to arbitrary domain sizes, but they all aim for cryptographic strength, at the expense of performance (and simplicity).)


texts: minimizing makespan for related machines

texts:
Any reference is appreciated.

There are $n$ jobs and $m$ machines, machines has speeds and jobs have processing times. It takes $p_j/s_i$ units of time for machine $i$ with speed $s_i$ to process job $j$ with processing requirement $p_j$. The objective is to find a non-preemptive schedule to minimize the makespan of the schedule.

Chandra Chekuri and Michael Bender studied it under constraint: "precedence constraints between jobs are given in the form of a partial order" at CB.

I am looking for reference of the problem without precedence constraints. Shmoys, Wein, and Williamson SWH showed a 2-approximation algorithm.

Is there any other result?


texts: Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

texts:
Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always positive.
We are given an arithmetic formula(arithmetic circuit with outdegree 1) of size $n$, over $X$ with gates $+$ and $\cdot$. There are no constant terms.

The time to evaluate a gate with input $x$ and $y$ is $O(|x|+|y|)$.

Is it possible to evaluate the formula in $O(m\log n)$ time? where $m$ is the total length of the input.


texts:
Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was http://en.wikipedia.org/wiki/FNP_(complexity)

However, that isn't sufficient for me to understand what that class actually means. For example, what should the FNP version of the decision version of the Hamiltonian Cycle Problem be?


texts: How Much Computing Power would be Required to Fully Simulate a Cubic Meter?

texts:
Imagine you want to simulate a cubic meter down to the particle. By following the Standard Model and other basic physical equations, how much computing power would be required to do this, in say, a day?

Would a quantum computer help you in this task? Could you somehow directly simulate the particles?

Thanks


texts:
Is there a documented way to compute knots? (circumferences embedded in a 3-dimensional Euclidean space).

I mean, a datatype to represent them, and an algorithm to determine if two instances of the datatype represent the same knot.

If the answer is positive, what about the complexity of that problem?


texts: Maximizing strictly increasing convex function

texts:
Let the objective be to maximize the sum of $f_i(x_i)$ where all $f_i$ are strictly increasing convex functions. Maximizing a convex function is hard as a local maximum might not be a global one. However for the special case described above, since $f_i$ are strictly increasing, from what I understand, the local maximum should be the global one.

If so, are there any special techniques that can optimize the objective (or maybe a piecewise approximation of it) subject to linear inequality constraints quickly?

Thanks


texts:
I recently came across the following problem which seems to fall in the context of graph rewriting problems:

Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(A_1,B_1),\ldots,(A_k,B_k)$ where both $A_i$ and $B_i$ are subgraphs of the complete graph with vertex set $V$ and $A_i$ is isomorphic to $B_i$ for $i=1,\ldots,k$.

Question:  Is there a sequence $a_1,\ldots,a_n$ such that successively replacing the subgraphs $A_{a_i}$ with $B_{a_i}$ in $G_{i-1}$ (where $G_0=G$) to obtain $G_i$ yields a graph $G_n$ with $e_0 \in E(G_n)$.

Note that one can only replace $A_{a_i}$ with $B_{a_i}$ in $G_{i-1}$ if $E(A_{a_i}) \subseteq E(G_{i-1})$.

Is anything about the complexity of this problem known (in particular is it NP-hard?).


texts:
I have difficulties finding a good definition of two embeddings of a (planar) graph in the plane being equivalent.
Intuitively I mean by equivalent that the embeddings look the same up to homeomorphism of the faces.

The only definition I found was:

Two embeddings of a graph are equivalent if for each vertex all
incident edges have the same circular clockwise order in both embeddings.

But this is not strong enough to match my intuitive view, since this notion of equivalence allows connected components to be arbitrarily contained in each other.


texts: Independent Node Degree in Undirected Graphs

texts:
Let $G=(V,E)$ be an undirected graph. The independent node degree $d^i(v)$ of a node $v$ is the maximum size of a set of independent neighbors of $v$. Denote by $\Delta^i(G) = \max \{d^i(v) \mid v \in V\}$. Obviously $\Delta^i(G) \le \alpha(G)$, where $\alpha(G)$ is the independence number of $G$.

Examples: $\Delta^i(G)=1$ for complete graphs. $\Delta^i(G)\le 5$ for unit disc graphs. $\Delta^i(G)=n-1$ for a star graph with $n$ nodes.

My questions:

What natural graph classes have $\Delta^i(G)\in O(1)$?
What is known about the distribution of $d^i(v)$ in random graphs?
For dense graphs the expected value of the independent node degree should be small. Are there any quantitative results? E.g. relating $m/n$ with $\Delta^i(G)$?


texts:
The only first-principles "proof" that a problem is NP-complete I encountered is from Introduction to algorithms, and deals with the circuit-satisfiability problem. According to the authors, many details in the proof are omitted.

What is the simplest first-principles proof that a problem is NP-complete that thoroughly presents all the technical details?


texts:
Sorting is in $\mathsf{NP}$. Given a sorted list, it is trivial to check sortedness in linear time.

Is there any evidence sorting of elements from an ordered gcd domain(eg: $\Bbb Z$) cannot be done in linear time using $\{\times,+,-,\bmod\}$ operations in unit cost RAM model where ring operations can be performed on arbitrarily large words in unit time?

I am thinking of using only $!=0$ comparison using modulo operations. If $x>y$, then $x\bmod y\neq x$. If $x<y$, then $x\bmod y=x$ holds. So using $x-y==0$ followed by $x - (x\bmod y)==0$ will tell if $x<y$. I do not wish to have bit operations. I want more like $\mathsf{BSS}$ model.

Let me clarify my sorting problem further.

Say I have been given list of $n$ different integers $a_0,\dots,a_n$ with each $a_i\in(0,2^m-1)$. I can write down the list in a long integer form $$G=a_0+a_12^m+\dots+a_n2^{nm}$$

There is an unique permutation $\sigma\in S_{n+1}$ such
$$N=a_{\sigma(0)}+a_{\sigma(1)}2^m+\dots+a_{\sigma(n)}2^{nm}$$ is minimum.

How many ring operations (with $\bmod$) would it take in worst case for converting integer $G$ to $N$?


texts: Finding a path between two given vertices that maximises the product of weights

texts:
I have a graph-problem which seems to be not very exotic but I do not know its proper name.

As given in the heading I am looking for a path between two given vertices that maximises the product of weights along the path, were all weights are in [0,1].

Coverstory is that vertices are states and weights denote the probability of a transition along that edge. Since the probabilities are independent, the product is the probability that this path will happen.

Any help with this would be appreciated especially the name of the problem or related google keywords, possible transformations into well known problems and/or an intuition about its complexity.

Thanks!


texts:
Given a connected graph $G =(V_1,V_2,E)$, such that there are no edges among the vertices in set $V_1$, however the other set $V_2$ can have edges in itself. There is actually a restriction for $V_2$, which is that we cannot remove any vertex in $V_2$ such that graph $G$ is still connected. Therefore a minimality constraint is there for $V_2$. Is there a standard name for this graph?

The need for it is because im writing a manuscript which includes a result on such graphs and i need to refer this graph with some name. So, i was wondering if there was some name for it. Obviously i couldn't find it. Any other suggestion/comment is also appreciated.


texts:
My question is inspired by this one.  I define 2.5-coloring to be the parameterized problem

Instance: an integer j and an n-vertex non-empty simple graph G

Parameter: integer k

Output: if there is a 3-coloring of G in which at least one of

the colors is used at most  min($\hspace{.03 in}$j,k)  times then YES else NO

.
Since j is part of the input and the only involvement of k is via   min($\hspace{.03 in}$j,k) ,  increasing k

cannot make 2.5-coloring easier.     Even for k=0, that problem is logspace-complete.

For k in nΩ(1), that problem is NP-hard by enlarging 3-coloring instances.

By applying Reingold's result to the bipartite double cover of the subgraph induced by the

non-guessed vertices, 2.5-coloring is in   GC ( max(k$\cdot \hspace{-0.02 in}\lceil \log_2(n)\hspace{-0.02 in}\rceil \hspace{-0.03 in}$,n) , DSPACE(O(log(n))) ) ,

since the verifier has two-way access to the alleged proof.

  Is anything else known about the complexity of 2.5-coloring?

In particular, I'd accept any non-trivial consequence of any answer to any of the following,

since I do not expect anyone to manage to outright answer any of them:

Is 2.5-coloring in  coNTIME$\left(\hspace{-0.02 in}n^{o(k)}\hspace{-0.04 in}\right)\hspace{-0.07 in}\big/\hspace{-0.04 in}$$n^{o(k)}$ ?     Is 2.5-coloring in rational-uniform ACC0?

Is 2.5-coloring with k in no(1) hard for rational-uniform TC0?

Is there a function g in ω(log) such that 2.5-coloring with k in no(1) is GC(g(n),AC0)-hard?

Is 2.5-coloring with k in no(1) hard for  GC ( k$\cdot$O(log(n)) , DSPACE(O(log(n))) ) ?

What about the "infinitely-often" versions of any of those questions,

i.e., for pairs k,n such that k is in no(1) and is arbitrarily large?


texts: Which results make quantum space interesting?

texts:
Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation?

I know many interesting results for quantum computation with sublogarithmic space bounds and various kind of quantum automata models.

On the other hand, it was shown that unbounded-error probabilistic and quantum space are equivalent for any space constructable $ s(n) \in \Omega(\log(n)) $ (Watrous, 1999 and 2003).

I wonder whether there are some specific results making quantum space interesting (by excluding sublogarithmic-space and automata models).

(I am aware of this entry: Quantum analogues of SPACE complexity classes.)


texts:
Hi. I have a problem but not sure if there is some literature on it or whether it has a standard name. Please let me know some reference from where I can begin.

Given undirected graph along with some pairs of nodes $s_i$ and $t_i$, we want to connect as many pairs in the graph as possible such that paths are edge disjoint.

Please comment on approximation and hardness results if any.


texts:
How many cycles $C_k$ $(k \geq 3)$ are there in a $n $ vertex graph such that graph doesn't have any cycle $C_m$ $(m>k)$.

For example $n=5$, $k=3$, then graph will have at most two $C_3$'s so that $G$ will not have any $C_k (k > 3).$

I am thinking that there are $O(n)$ cycles will be there satisfying above conditions.

Can some one help me out.


texts: Hardness of approximating acyclic chromatic number

texts:
I have some doubts on the inapproximability result for acyclic coloring presented in the paper New acyclic and star coloring algorithms with application to computing Hessians. They claim that there exist an $\epsilon>0$ such that acyclic coloring cannot be approximated within $O(n^\epsilon)$ unless $\textsf{P=NP}$. It is proved by means of a reduction from Coloring.

Given an instance $G$ of Coloring, an graph $H$ is constructed by replacing each edge $e=uv$ of $G$ by $\Delta=\Delta(G)$ parallel edges and subdividing them exactly once. The construction has the following properties. They prove that for all $p$ in $3\leq p\leq \Delta$, $\chi(G)\leq p \iff \chi_s(H)\leq p$. From this, and the result Chromatic number is NP-hard to approximate within $O(n^\epsilon)$ for some $\epsilon>0$, they conclude that Acyclic chromatic number is NP-hard to approximate within $O(n^\epsilon)$ for some $\epsilon>0$.

(In the above paragraph, $\Delta(G)$ denotes the maximum degree of $G$ ).

What type of reduction is this? I am assuming it is the basic type gap-preserving reduction presented in Vazirani's book (see quote below).

The details of the gap-preserving reduction are not clear to me. I think it is proved using a gap-preserving reduction.(Disclaimer: I don't know whether they are using some specific type of approximation preserving reduction such as L-reduction).
This is my best guess on the reduction. Clearly,
$\chi(G)\leq 3 \implies \chi_s(H)\leq 3$,
$\chi(G)>\Delta \implies \chi_s(H)>\Delta$

Let me recall definition for gap-preserving reduction from Vazirani's book here (slightly modified to fit this context).

  A gap-preserving reduction from minimization problem A to minimization problem B with parameters $f,\alpha,g,\beta$ maps an instance $x$ of A to an instance $y$ of B such that
  $\bullet\ $ the mapping is poly. time computable,
  $\bullet\ $ $OPT\leq f(x) \implies OPT\leq g(y)$, and
  $\bullet\ $ $OPT>\alpha(|x|)\  f(x) \implies OPT>\beta(|y|)\ g(y)$.

(Also for all $x$ and $y$, $\alpha(|x|)>1$ and $\beta(|y|)>1$. OPT refers to optimal value for problem A when used on left side, and problem B when used on right side.)

Here, it seems $f_A=f_B=3$ and $\alpha(|x|)=\beta(|y|)=\Delta/3$. But, here $|x|=n+m$ and $|y|=(n+\Delta m)+2\Delta m$ (where $n=$ #vertices in $G$, and $m=$ #edges in $G$). But then, functions $\alpha$ and $\beta$ cannot be defined like this!

What are the correct functions $f,g,\alpha,\beta$ implicit in the inpproximability proof of the paper?


texts: How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0?

texts:
Given an undirected graph $G=(V,E)$ devise an algorithm that will check whether its edges can be directed in such a way that the vertices of the resulting directed graph will all have indegree higher than $0$. For any edge $\{u,v\}∈E$ only one direction can be chosen: $(u,v)$ or $(v,u)$.

I'm quite new to graphs and graph algorithms so I was wondering if I'm on the right track:

I think the key to the solution is to determine whether the graph is acyclic.

In order to do that we can use BFS algorithm on the graph by coloring layer $i$ in red, layer $i+1$ in blue and again $i+2$ in red and so forth. If at the end of the algorithm we have an edge which connects two nodes of same color that the graph is cyclic.

If the graph is acyclic this means that no matter how we choose the directions if we use topological sorting there will always be a node without an incoming edge, which means that such graphs cannot become directed graphs of indegree higher than $0$ as requested.

Intuitively I think if we have a cyclic graph then our algorithm should be able to turn it into directed with all nodes of indegree higher than $0$ but I'm not sure how to prove this. Maybe like this:

Suppose we choose a graph component with one cycle (circle). We then remove an edge from the circle. Now the component becomes acyclic and using topological sorting we'll have one node without an incoming edge. So now put back the previously removed edge to that node and all the requested conditions hold (the graph is directed and all nodes have at least one incoming edge).


texts: Algorithms and structural complexity theory

texts:
Many important results in computational complexity theory, and in particular "structural" complexity theory, have the interesting property that they can be understood as fundamentally following (as I see it...) from algorithmic results giving an efficient algorithm or communication protocol for some problem. These include the following:

IP = PSPACE follows from a space-efficient recursive algorithm simulating interactive protocols, and an efficient interactive protocol for evaluating totally quantified boolean formulae. In fact any complexity class equality A=B can be seen as following from two efficient algorithms (an algorithm for problems in A which is efficient with respect to B, and vice versa).

Proving NP-completeness of some problem is just finding an efficient algorithm to reduce an NP-complete problem to it.

The (arguably!) crucial ingredient in the Time Hierarchy Theorem is an efficient universal simulation of Turing machines.

The recent result of Ryan Williams that ACC $\not \supset$ NEXP is based on an efficient algorithm to solve circuit satisfiability for ACC circuits.

The PCP Theorem is that efficient gap amplification is possible for constraint satisfaction problems.

etc., etc.

My question (which is possibly hopelessly vague!) is as follows: Are there any important results in structural complexity theory (as distinct from "meta-results" like the relativisation barrier) which are not known to have a natural interpretation in terms of efficient algorithms (or communication protocols)?


texts: How to automatically generate indexes and preaggregations from queries

texts:
This question might be a little ill-specified, but the idea I want to explore is:

User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-only database table)
The schema for the data is specified

Using this input, what data structures need to be generated to "efficiently" query the table? The program would read the input data and then generate a bunch of indexess/pre-aggregations so that the queries will be ultra fast.

For a really simple example, say I have a table of logs:

(URL, IP address, user agent, response code)

And I input a queries like:

select * where URL = http://foo

Then it should know to automatically generate an index on the URL field.

If I also specify:

select count(*) from table group by IP_address desc limit 20

or however you specify the 20 most common IP addresses, then it should also generate some pre-aggregation that is efficient (think of having 100 million rows).

I'm sure I am not specifying the problem completely, but I found some papers that seem related, i.e. http://scholar.google.com/scholar?cluster=1230153639822613926&hl=en&as_sdt=0,5

Looking for more references in this area. This is a computer science/algorithm question; I'm not looking for ways implement to implement this with MySQL or anything like that. Thanks.


texts: What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?

texts: As title says what happens to other complexity classes if all $\#P$ (Sharp-P) problems have polynomial-time algorithms? What happens to PSPACE?


texts: Applications of TCS to classical mathematics?

texts:
We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.).

  What are some examples of when it has gone the other way around?

Here are some I know of (and also to give a flavor of the type of results I'm asking about):

Cubical foams (Guy Kindler, Ryan O'Donnell, Anup Rao, and Avi Wigderson: Spherical Cubes and Rounding in High Dimensions, FOCS 2008)
The Geometric Complexity Theory Program.  (Although this is technically an application of algebraic geometry and representation theory to TCS, they were led to introduce new quantum groups and new purely algebro-geometric and representation-theoretic ideas in their pursuit of P vs NP.)
Work on metric embeddings inspired by approximation algorithms and inapproximability results

I am in particular not looking for applications of TCS to logic (finite model theory, proof theory, etc.) unless they are particularly surprising -- the relationship between TCS and logic is too close and standard and historical for the purposes of this question.


texts: Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?

texts: If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave.  Clearly in the worst case you cannot upper bound $\textbf{E}[f(x)]$ in terms of $f(\textbf{E}[x])$ for a convex $f$, but is there a bound that goes in this direction if $f$ is convex but "not too convex"?  Is there some standard bound that  gives conditions on a convex function $f$ (and possibly the distribution as well, if necessary) that would allow you to conclude that $\textbf{E}[f(x)] \le \varphi(f)f(\textbf{E}[x])$, where $\varphi(f)$ is some function of the curvature/degree of convexity of $f$?  Something akin to a Lipschitz condition, perhaps?


texts: Problems that are easy on unweighted graphs, but hard for weighted graphs

texts:
Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some  examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), max flow, min cut, max matching, optimum arborescence, certain densest subgraph problems, max disjoint directed cuts, max clique in certain graph classes, max independent set in certain graph classes, various max disjoint path problems,  etc.

There are, however, some (although probably significantly fewer) problems that are solvable in polynomial time in the unweighted case, but become hard (or have open status) in the weighted case. Here are two examples:

Given the $n$-vertex complete graph, and an integer $k\geq 1$, find a spanning $k$-connected subgraph with the minimum possible number of edges. This is solvable in polynomial time, using a theorem of F. Harary, which tells the structure of the optimal graphs. On the other hand, if the edges are weighted, then finding the minimum weight $k$-connected spanning subgraph is $NP$-hard.
A recent (Dec 2012) paper of S. Chechik, M.P. Johnson, M. Parter, and D. Peleg (see
http://arxiv.org/pdf/1212.6176v1.pdf) considers, among other things, a path problem they call Minimum Exposure Path. Here one looks for a path between two specified nodes, such that the number of nodes on the path, plus the number of nodes that have a neighbor  on the path is minimum. They prove that in bounded degree graphs this can be solved in polynomial time for the unweighted case, but becomes $NP$-hard in the weighted case, even with degree bound 4. (Note: The reference was found as an answer to the question What is the complexity of this path problem?)

What are some other interesting problems of this nature, that is, when switching to the weighted version causes a "complexity jump?"


texts: Under what conditions does an Integer Programming problem run in polynomial time?

texts:
Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in polynomial time ($(mn)^c$ arithmetic operations on $(mn)^c$ sized words suffices).

Supposing we have the promise that the number of feasible solutions is polynomial then under what conditions can the problem be solved in polynomial time using Kannan's and Barnivok's algorithm (other than total unimodularity)?


texts: Is there research on algorithmic design patterns?

texts:
From what I've seen in the majority of algorithms publications, the focus of research is mainly towards improving the solutions to algorithmic problems in terms of efficiency or optimality in the case of approximation algorithms. My interest and hence my question is towards the generalization rather than improvement of algorithms, that is finding common ideas,techniques,optimization tricks that underlie the design or analysis process of algorithms and data structures. Examples of such patterns would be: lazy propagation in data structures, sqrt decomposition, incremental (sweep like) algorithms, smaller to larger merging (as in union by rank)...etc.

I am aware that these techniques would be explained when used in a specific instance of an algorithm, but the focus would still be on the algorithm rather than the design technique.

I appreciate if someone can provide guidance on where to look for such research and whether design techniques are valid as a research point.


texts: Proper PAC learning of 2-DNF under uniform distribution

texts:
What is the state of art result about query complexity of proper PAC learning 2-DNF formulas with sample queries and under uniform distribution? Or any non-trivial bound on it?

Because I am not familiar at all with learning theory and this question is motivated by a different field, the answer might be obvious. I checked the book by Kearns and Vazirani, but they don't seem to consider this setting explicitly.

upd. Although the main parameter of interest is query complexity, running time is also important. If possible, running time should preferably be roughly the same as query complexity or at most polynomial.

upd. Appendix B (top of the page 18) of the paper "Learning Submodular Functions" by Balcan and Harvey mentions that "It is well known that 2-DNFs are efﬁciently
PAC-learnable." However, they don't mention, whether this result is for proper learning or give any reference.


texts: VC Dimension generalized to discrete, non-binary, unordered domains?

texts: VC dimension is a measure of the complexity of classes of functions $f:X\rightarrow \{0,1\}$ that is closely tied to sample complexity. Fat shattering dimension is a generalization suited to richer ordered domains: i.e. $f:X\rightarrow \mathbb{R}$. Is there a standard generalization of VC-dimension suited to functions with discrete, unordered domains? i.e. $f:X\rightarrow K$ where $K$ is a finite set with no ordering on it.


texts: Real world applications of quantum computing (except for security)

texts:
Let's assume that we have built an universal quantum computer.

Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it?

I am interested in both:

problems currently unsolvable for a practical entry,
problems which currently are being resolved, but a significant speedup would greatly improve their usability.


texts: What's the constant coefficient of the Coppersmith-Winograd algorithm?

texts: Every source I can find just says "too big to be practical."


texts: Understanding Dudley Chaining Argument for Rademacher Bound

texts:
I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know why anyone would think to make this argument. Can someone please explain why? (An example of the chaining argument: http://www.cs.cornell.edu/~sridharan/dudley.pdf.)

For context:

The following covering number bound makes some sense to me:
$$
  \texttt{Rad}(\mathcal{A} \circ x) \leq \inf_{\epsilon > 0} \{ \epsilon + \text{const} \times \sqrt{\log \texttt{CoveringNumber}(\mathcal{A}, ||\cdot{}||_{1, x}, \epsilon)} \}
$$
where $x = x_1, \dots, x_n$ and $||a||_{1, x} = \left(\frac 1n \sum_{i=1}^n |a(x_i)|^p \right)^{1/p}$ for $a \in \mathcal{A}$ and $\mathcal{A}$ is a set of algorithms/hypotheses. I think of the right hand side as counting equivalence classes of $\mathcal{A}$ under "predictions on $\mathcal{X}$ are $\epsilon$-close in $||\cdot{}||_{1, x}$". Intuitively, the more of these there are, the more "different" predictions $\mathcal{A}$ can express on the training set $x$ and hence $\mathcal{A}$ is more "complex".


texts: Place of tree-adjoining grammars in the hierarchy of tree grammars

texts:
As tree-adjoining grammars operate with trees, I suppose they can be considered as a kind of tree grammars. If this assumption is correct, I'm wondering: where should we place them in the tree grammar hierarchy?

By the tree grammar hierarchy I mean one which is similar to the Chomsky hierarchy of word grammars, e.g. as on this figure taken from

  Matsuda K., Mu SC., Hu Z., Takeichi M. (2010) A Grammar-Based Approach
  to Invertible Programs. In: Gordon A.D. (eds) Programming Languages
  and Systems. ESOP 2010. Lecture Notes in Computer Science, vol 6012.
  Springer, Berlin, Heidelberg


texts: Effect of different graph operations at algebraic connectivity of graph laplacian?

texts:
The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. The magnitude of this value reflects how well connected the overall graph is.

for an example, "adding self-loops" does not change laplacian eigenvalues (specially  algebraic connectivity) of graph.
Because, laplacian(G)= D-A is invariant with respect to adding self-loops.

My question is:

Does anyone has studied effect of different operations (such as edge contraction) on spectrum of laplacian?
do you know good references?

Remark: the exact definition of the algebraic connectivity depends on the type of Laplacian used.  For this question I prefer to use Fan Chung definition in SPECTRAL GRAPH THEORY. In this book Fan Chung has uesed a rescaled version of the Laplacian, eliminating the dependence on the number of vertices.


texts: Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I need the same for polytopes that their facets are parallel to the coordinate axises.


texts:
This is a somewhat frivolous question that popped up in my head after reading the various responses to "What's the “smallest” complexity class for which a superlinear circuit bound is known?".

Answers refer to $\mathsf{S_2 P}$, and when I looked at the zoo entry for it, I discovered this:

  $\mathsf{S_2-EXP•P^{NP}}$: Don't Ask

  One of the caged classes of the
  Complexity Zoo.

  Has been implicated in a collapse
  scandal involving $\mathsf{AM}[\text{polylog}]$, $\mathsf{coNP}$,
  and $\mathsf{EH}$

So now I'm intrigued. What's a caged complexity class, and what's the juicy scandal here :) ? The zoo has no references to clarify.


texts: n irrational number whose digits are pseudo-random: conceptual mismatch?

texts:
Are there irrational numbers whose digits are considered pseudo-random?

Both concepts seem to be mismatched as a pseudo-random number generator typically is periodic and therefore generates a rational sequence whereas as irrational numbers are not periodic.

This follows from the question if a pseudo-random number generator is necessarily periodic. It can be expressed as a Turing machine which itself cannot compute reals other than by recursively enumerating them. If effectively, there exists such an irrational number, then there are pseudo-random number generators, in theory, that are non-periodic.


texts: Given PSPACE $\ne$ EXP, is there a non-PSPACE-hard language in EXP - PSPACE?

texts:
Let me state the problem again:

  Suppose PSPACE $\ne$ EXP. Is there a language in EXP - PSPACE that is not PSPACE-hard?

Context

I have a problem that's in EXP. Currently I don't think it's in PSPACE. Besides proving it's EXP-complete, what else can I do? Since it seem not to be in PSPACE, I start to think it's PSPACE-hard. But is this necessary? That's why I asked this question.

Actually I have a related question, that is, given PSPACE $\ne$ EXP, whether there is a language in EXP - PSPACE that is not EXP-hard. A yes answer to the main question will imply a yes answer to this question. I think answering this question will also help me somehow.


texts: Are there Conservation Laws in Complexity Theory?

texts:
Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems.

Or take primality. It is easier to show composites in NP than primes in NP (which required Pratt) and eventually in P. Why did it have to display this asymmetry at all?

I know Hilbert, need for creativity, proofs are in NP etc. But that has not stopped me from having a queasy feeling that there is more to this than meets the eye.

Is there a quantifiable notion of "work" and is there a "conservation law" in complexity theory? That shows, for example, that even though CVP and LP are both P-complete, they hide their complexities at "different places" -- one in the reduction (Is CVP simple because all the work is done in the reduction?) and the other in expressibility of the language.

Anyone else queasy as well and with some insights? Or do we shrug and say/accept that this is the nature of computation?

This is my first question to the forum: fingers crossed.

Edit: CVP is Circuit Value Problem and LP is Linear Programming.  Thanks Sadeq, for pointing out a confusion.


texts: Function which detects rotation of bit string

texts:
Consider a function $F: \mathbb{F}_2^d \to \mathbb{Z}^n = (f_1,\ldots,f_n)$ with the property that if $y \in \mathbb{F}_2^d$ is a rotation of $x \in \mathbb{F}_2^d$, i.e. $y$ is $x$ permuted by an element of the cyclic group generated by $(1 \ 2 \ldots d)$, then F(x)=F(y), and the additional constraint that $f_i$ is of the form

$
f_i(x) = \sum\limits_{j=1}^d \alpha_jx_j
$.

There are obvious examples of such functions, for instance $F(x) = \sum\limits_{1}^d x_i$. For any $x \in \mathbb{F}_2^d$ and $\pi \in S_d$, $F(x)=F(\pi x)$. We say that such a function is fixed under $S_d$. However, as you might expect from my initial explanation, I am interested in such a function which is fixed strictly under rotations, that is for any permutation $\pi$ which is not a rotation, then $F(x) \neq F(\pi x)$, or at least fixed under rotations and not fixed under all of $S_d$.

Do such functions exist? I am having difficulty finding any example which is not the one I gave above.


texts: What is the state of the art in online voting?

texts: Is there a cryptographic protocol which, at least in theory (and under standard cryptographic assumptions) enables people to securely vote from their homes? I could see how the various problems might be addressed (such as: preventing people from voting twice, producing proof that the vote was registered while revealing no information about who the vote was for) except for one: preventing coercion (that is making sure that the voter isn't being bribed or otherwise forced to vote a certain way). This seems to be impossible, in principle, without the voter being physically present at a voting center with overseers watching, but maybe I'm not sufficiently thinking outside the box?..


texts: Favorable graph decomposition for dense graphs to solve independent set problem

texts:
I have to solve an independent set problem (ISP) on dense graphs with many cliques. To tackle the problem, I'm considering to use graph decompositions such as tree-, modular decomposition or clique-width k-expression trees.

Are there some decompositions (or other techniques) favorable for my type of graphs?

From what I understand, considering e.g. the tree-decomposition, the ISP can be solved in $\mathcal{O}(n2^k)$ where $n$ is number of vertices of the tree and $k$ the tree-width. Moreover, the tree-width is a measure of how similar a graph is to a tree. From this, I concluded that a graph which is not very similar to tree (maybe just like mine) has a large tree-width and, hence, the tree-decomposition is maybe not a favorable decomposition to solve the ISP.

Is e.g. the clique-width k-expression tree more suitable for my case?