texts: Alternate notion of complexity based on gap between brute-force and the best algorithm?

texts:
Typically, efficient algorithms have a polynomial runtime and an exponentially-large solution space.  This means that the problem must be easy in two senses: first, the problem can be solved in a polynomial number of steps, and second, the solution space must be very structured because the runtime is only polylogarithmic in the number of possible solutions.

However, sometimes these two notions diverge, and a problem is easy only in the first sense.  For instance, a common technique in approximation algorithms and parameterized complexity is (roughly) to prove that the solution space can actually be restricted to a much smaller size than the naive definition and then use brute-force to find the best answer in this restricted space.  If we can a priori restrict ourselves to, say, n^3 possible answers, but we still need to check each one, then in some sense such problems are still "hard" in that there's no better algorithm than brute-force.

Conversely, if we have a problem with a doubly-exponential number of possible answers, but we can solve it in only exponential time, then I'd like to say that such a problem is "easy" ("structured" may be a better word) since runtime is only log of the solution space size.

Does anyone know of any papers that consider something like hardness based on the gap between an efficient algorithm and brute-force or hardness relative to the size of the solution space?


texts: Proof systems induced by NP-complete problems

texts: Satisfiability is the fundamental NP-complete problem. Cook-Reckhow theorem states that the existence of a propositional proof system that admits polynomial size proofs for all tautologies implies that NP=coNP. In principle, every NP-complete problem can encode Satisfiability problem. It seems to me that we should be able systematically generate a proof system from any NP-complete problem. The aim is that this may give new insights into proving proof complexity lower bounds. I am looking for references.


texts: How does the Multiplicative Weights Update method maximize entropy?

texts:
"The Multiplicative Weights Update (MWU) method is known to maximize both utility and entropy". This is a comment by C. Papadimitriou on MWU. I understand that MWU maximizes utility as it solves linear programming, for example.

The question is how MWU maximizes entropy? Can you give some example/information on this point?


texts: "Natural" decidable problems known not to be in NP.

texts:
Every time I teach NP-Completeness, students ask "are there any problems that are known to not belong to NP?"

How would you answer?  I usually give them an undecidable problem as an example, but this often doesn't turn out well: (a) if I give them the Halting Problem they think it's some dumb corner case, and (b) if I give them Diophantine Equations they don't see why it's not in NP (you can check solutions in poly-time... just plug them in!  I have a hard time disabusing them of this approach.)

I'd like to give them something like QBF as an example, but there is no proven separation.

Suggestions?


texts:
I'm studying type theory (mostly Coq) and often encounter the term "large elimination", usually when talking about type universes hierarchy consistency, for example:

  impredicative polymorphism + excluded middle + large elimination => false

While I have an intuitive understanding of what it means, I wasn't been able to find or construct a more formal definition of what precisely is "large elimination".

In my understanding, large elimination is when a term t : T is eliminated (destructed) to get a value of type D, where D depends on the value of t.

For example, if vec_bool : nat -> Type is a type constructor for the boolean list of a fixed size with data constructors

nil  : vec_bool 0
cons : forall n:nat, bool -> vec_bool n -> vec_bool (S n)

the following recursive definition performs a large elimination on n:

Fixpoint construct_false_list (n:nat) : vec_bool n :=
   match n with
   | 0      => nil
   | Succ m => cons m false (construct_false_list m)
   end.

Is my understanding correct, or am I missing something?


texts: Dynamic connectivity with known history, for maximal connected component span

texts:
Consider a graph in which edges are added and removed over time. Define the span of a connected component as the product of its number of vertices and the longest duration for which it remains a connected component.
I am interested in finding the maximal connected component span.
In the example below, there are three connected components over time (blue rectangles): $\{a,b,c\}$ from time $0$ time to $5$; $\{d,e\}$ on the same time interval, and $\{a,b,c,d,e\}$ from $5$ to $10$. They have span $15$, $10$ and $25$, respectively, hence the wanted result is $25$.

Dynamic connectivity algorithms make it possible to compute the connected components over time, and so they provide a solution to the above problem. They typically need polylog time per edge addition or removal, with complex data structures.
Is there a faster way to compute the maximal connected component span?
In particular, suppose we know the dynamics in advance: we have, for each edge, the list of times at which it is added and removed. Therefore, we do not have to process edge additions and removals in chronological order. Does this make the above problem simpler?


texts: Spectral gap for random bipartite regular graphs

texts:
For a graph $G$, let its Laplacian be $\Delta =I − D^{−1/2}AD^{−1/2}$, where
$A$ is the adjacency matrix, $I$ is the  identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm interested in the spectral gap of
$G$, i.e. the first nonzero eigenvalue of $\Delta$, denoted by $\lambda_2(G)$.

Is it true that a randomly chosen (with uniform distribution) $d$-regular bipartite graph on $(n,n)$ vertices (with multiple edges allowed) has, with probability approaching $1$ as $n \to \infty$, $\lambda_2$ arbitrarily close to
$1$ (i.e. $d$ is fixed and we may take it large enough so that asymptotically most graphs will have $\lambda_2 > 1 - \epsilon$, where $\epsilon$ depends on $d$)?

If yes, is there a reference for this fact?

Proofs of expanding properties for random regular graphs which I have found in the literature usually give the probability only bounded from below by a constant, i. e. $1/2$, although I imagine that actually  almost all bipartite random graphs have good spectral gap.

Note: by $d$-regular bipartite graph I mean a graph in which each vertex (on the left and on the right) has degree $d$.


texts: Array-like data structure with O(1) worst-case concatenate/join?

texts:
I am looking for a data structure $D$ which supports the following operations
(preferably a (binary) tree-like structure):

$D$ is indexed, i.e.
there is a mapping from $\{1, \ldots, n\}$ to items in $D$,
where $n$ is the size of $D$ (the number of items in $D$).
$k$-th item in $D$ can be accessed in $\mathcal{O}(\lg n)$ worst-case (non-amortized).
The operation should not modify the data structure,
it should be completely "read-only"
(e.g. no finger searches are allowed).
(Once the pointer to the $k$-th item is obtained,
further changes should be supported in $O(1)$
without modification to the state of the data structure apart from the actual stored item (e.g. if it is a tree-like data structure, this means no rotation is allowed).
two instanced $D$ and $D'$ can be merged in time $\mathcal{O}(1)$ worst-case (non-amortized). Destruction of $D$ and $D'$ is fine.
The result should contains the union of the elements;
those that come $D$ retain their indices,
while indices of those coming from $D'$ get incremented by the size of $D$,
e.g. if we are merging
$D=\{ 1 \to x_1, 2 \to x_2 \}$ with
$D'=\{ 1 \to y_1, 2 \to y_2, 3 \to y_3 \}$
we should get
$\{ 1 \to x_1, 2 \to x_2, 3 \to y_1, 4 \to y_2, 5 \to y_3 \}$.

In essence, this data structure should have the properties of
the fast-mergeable array/vector with asymptotically slower random-access,
but extremely fast merge/concatenation ($\mathcal{O}(1)$).
It would also be cool if elements could be listed in order in linear time.

I would be mostly interested in the references to existing work / papers
which describe such a data structure or algorithm on an existing data structure.


texts: The Overfull conjecture in graph theory and $coNP$

texts:
I am not good at complexity, but got a possible
relation between a plausible conjecture in graph
theory and $coNP$.

Graph $G$ is Class 1 if it can be edge colored
with $\Delta(G)$ colors, otherwise it is Class 2 and
can be edge colored with $\Delta(G) + 1$ colors.

The Overfull conjecture (OC)
asserts

  A graph G with $\Delta (G) \geq n/3$ is class 2 if and only if it has an overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$.

Assume OC and $\Delta (G) \geq n/3$.

This means that we have short certificate if $G$ is Class 1
or Class 2.

For Class 1 the certificate is $\Delta(G)$ edge coloring finding it is in $NP$.

For Class 2 the certificate is overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$ and finding it is in $NP$.

This means there are no $coNP$-hard problems in this case.

There is a reduction from SAT to edge coloring
$3$-regular graphs. Encoding unsatisfiable CNF
to edge coloring is UNSAT and UNSAT is in $coNP$.

  Question:  Does the overfull conjecture and reduction
  from SAT to edge coloring $G$ with $\Delta (G) \geq n/3$
  imply $NP=coNP$?

According to a paper
edge coloring is NP-complete (possibly minor abuse of terminology) for
$r$-regular graphs for any fixed $r \ge 3$ and it gives reduction
of $G$ to $r$-regular $G'$.

Positive answer might help for counterexample to the
overfull conjecture.

$\Delta(G)$ is the maximum degree and $n$ is the number of
vertices.

EDIT Special cases of OC are proven.

According to Overfull Conjecture for Graphs with High Minimum Degree,
Michael Plantholt:

  we show that any (not necessarily regular) graph $G$ of even order $n$ that has sufficiently high minimum degree $\delta(G) \ge (\sqrt{7}/3) n$  has chromatic index equal to its maximum degree providing that $G$ does not contain an
  "overfull" subgraph, that is, a subgraph which trivially forces the chromatic
  index to be more than the maximum degree. This result thus verifies the
  Overfull Conjecture for graphs of even order and sufficiently high minimum
  degree.

EDIT 2
This paper p.2
might be related since it claims unless $NP=ZPP$, one can't
approximate $\chi'(L^k(G))$ where $L^k(G)$ is the $k-th$ power of
the line graph of $G$. (might be wrong on this since $\chi'$ is either
$\Delta$ or $\Delta+1$).


texts: Publishing by showing falsity of existing results

texts:
Is it valid to publish a minor result related to computer science complexity theory and classes that disproves and falsifies an existing result?
Would that be a valid and respectable endeavor?


texts: Why do we need a sphere to graphically represent a qubit?

texts:
Bloch sphere is a common visualisation of possible qubit values, but I fail to understand why do we need a sphere to represent them. Assuming we want to represent the single qubit a|0> + b|1> theoretically we know both a and b coefficients may be complex. However, we also know that the global phase factor is insignificant (we treat two unit vectors related by a global phase as equivalent) so we may treat a or b to be a real number. Wouldn't a circle be enogh to represent a qubit then (like taking axis y away from the original Bloch sphere)?

I feel like I am missing something simple (or some basic information I should know), any suggested read or explanation would be appreciated. Thank you in advance.


texts:
Let $G$ be a group, $g ∈_R G, x ∈_R Z_q$, and  $e: G \times G \rightarrow G_T$ be a bilinear paring.

Then, given $g, g^x$, is it still hard to compute $g^{x^2}$?

1. In other words is Square Diffie-Hellman hard in Bilinear Groups?

I am trying to look for references that have used this problem or a reduction which proves this is hard.

[I am aware of a variant of this called the Flexible Square Diffie-Hellman  [Laguillaumie et al], which asks to compute $(h,h^x,h^{x^2})$ given $g^x$.]

2. What about the decisional version of the same problem?


texts:
Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices in $S$. Finding minimum weight Steiner Tree is called Minimum Steiner Tree Problem. This problem and many of its variants are known to be NP-Complete.

I thought about this variant where we dont need to connect all vertices in $S$. That is, along with the input, we are also given a natural number $k$, such that $k<|S|$. Now, find a minimum weight connected subgraph which connects at least $|S|-k$ vertices in $S$.

Notice that when $k$=0, this is the usual Steiner Tree Problem and when $k=|S|-2$, it is Shortest path problem. Is this problem NP-Complete for any arbitrary $k$?

I do not know whether this question already exists (quite possible considering the number of variants of Steiner Tree Problem). I did a brief search and I couldnt find anything related to this problem.


texts: Positive cut algorithm on bipartite graphs with negative weights

texts:
Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If it is needed, we can presume that such cut exists (but sum of all weights may be negative).

If not, is there such an algorithm when two nodes on the opposite sides of such cut are already provided?

I am aware that this might be a duplicate of this question. I went through the given articles, but I am not sure if they answer my question. For example, I do not understand what the approximation performance means in the context of negative weights. If all but one cut have non-positive values, does that mean that the approximation algorithm will find that single positive solution (because only for that solution the performance condition is met)?


texts: Multidimensional Knapsack W[1]-hard when parameterized by dimension

texts:
Under Multidimensional knapsack STRONGLY NP-complete it was discussed that the Multidimensional Knapsack problem is strongly NP-hard.

Within this discussion the question whether the problem is W[1]-hard when parameterized by dimension d was mentioned, but not finally answered. Is the problem solved?

And: Is there any known xp-algorithm for multidimensional knapsack w.r.t. parameter dimension?


texts: If for every non-terminal in a cs-grammar there exists an obligatory rule, does this alter the language of derivable strings

texts:
I am reading Chomsky's article Three models for the description of language, one of the earliest papers where context-free and context-sensitive grammars are mentioned. Essentially what he calls Phrase-structure-grammars in his article is nowadays called context-sensitive grammars. On page 118 he then introduces proper grammars:

  [...] The grammar can also be simplified very greatly if we order the rules and require that they be applied in sequence (beginning again with the first rule after applying the final rule of the sequence), and if we distinguish between obligatory rules which must be applied when we reach them in the sequence and optional rules wich may or may not be applied. [...]

  It seems reasonable to require for significance some guarantee that the grammar will actually generate a large number of sentences in a limited amount of time; more specifically, that it be impossible to run through the sequence of rules vacuously (applying no rule) unless the last line of the derivation under construction is a terminal string. We can meet this requirement by posing certain conditions on the occurrence of obligatory rules in the sequence of rules. We define a proper grammar as a system $[\Sigma, Q]$, where $\Sigma$ is a set of initial strings and $Q$ a sequence of rules $X_i \to Y_i$ [...] with the additional conditional that for each $i$ there must be at least one $j$ such that $X_i = X_j$ and $X_j \to Y_j$ is an obligatory rule.
  [...]
  Let $D(G)$ be the set of derivations producible from a phrase structure grammar $G$, whether proper or not. Let $D_F = \{ D(G) \mid G \mbox{ is a $[\Sigma, F]$ grammar}\}$ and $D_Q = \{D(G) \mid G \mbox{ is a proper grammars} \}$. Then
  $$
 \mbox{$D_F$ and $D_Q$ are incomparable; i.e., $D_F\not\subseteq D_Q$ and $D_Q \not\subseteq D_F$}.
$$

Where by a derivation he means every derivable string, even if they contain non-terminal symbols. And a $[\Sigma, F]$ grammar is a usual context-sensitive grammar with no restriction on rule application.

I do not understand why they are incomparable. For example if I have a (possibly non proper) grammar $G$ and make all rules obligatory, then certainly every derivation in $G$ applies in each step one obligatory rule, hence every derivation in $G$ is also a derivation in the proper variant of $G$, and as the other direction is clear both generate exactly the same set of derivable strings, hence $D_F \subseteq D_Q$???? Conversely I also cannot think of a set of string derivable by a proper grammar, for which there certainly exists no usual grammar?


texts: For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

texts:
It is well known that the following problem is PSPACE-complete:

Given regular expression $\beta$, does $L(\beta) = \Sigma^*$?

What about determining equivalence to other (fixed) regular expressions $\alpha$?

Given regular expression $\beta$, does $L(\beta) = L(\alpha)$?

The following is known:

For $\alpha = (0+1)^*$, the problem is PSPACE-complete

For $\alpha = \emptyset$, or more generally $\alpha$ that describes a finite set, the problem is decidable in polynomial time.

It also seems likely to me that the problem is in P if $\alpha$ is a unary language.
So my questions are:

For which $\alpha$ is the above decision problem PSPACE-complete? Is there a complete characterization?
Are there any $\alpha$ for which the decision problem has some intermediate complexity (like NP-complete)?


texts: Complexity of iterative least squares regression

texts:
Given a set of points $P = \{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) \}$ one can use least squares method to fit a polynomial to $P$.
In particular I am interested in linear and quadratic regression.

I am not familiar with the literature, but it seems a fit to $P$ can be computed in $O(n)$ time,
(the degree of the polynomial is considered a constant).

Is there any algorithms for updating these polynomials as one point is added to or removed from P without recomputing the whole polynomial?

Edit:
I found this implementation:
http://algs4.cs.princeton.edu/14analysis/LinearRegression.java.html
Which easily can be modified to dynamically update a linear regression in constant time.

I still wonder how to do quadratic regression but I will try to mimic the technique I found for linear regression.


texts:
In a problem I am currently working on, an extension of the noise operator arises naturally, and I was curious whether there has been prior work. First let me revise the basic noise operator $T_{\varepsilon}$ on real-valued Boolean functions. Given a function $f: \{0,1\}^n \to \mathbb{R}$ and $\varepsilon$, $p$ s.t $0 \leq \varepsilon \leq 1$, $\varepsilon = 1 - 2p$,
we define $T_{\varepsilon} \to \mathbb{R}$ as
$T_{\varepsilon} f(x) = E_{y \sim \mu_p} [f(x+y)]$

$\mu_p$ is the distribution on $y$ obtained by setting each bit of a $n$-bit vector to be $1$ independently with probability $p$ and $0$ otherwise. Equivalently, we can think of this process as flipping each bit of $x$ with independent probability $p$. Now this noise operator has many useful properties, including being multiplicative $T_{\varepsilon_1} T_{\varepsilon_2} =
T_{\varepsilon_1 \varepsilon_2}$ and having nice eigenvalues and eigenvectors($T_{\varepsilon}(\chi_S) = \varepsilon^{|S|} \chi_S$ where $\chi_S$ belongs to the parity basis).

Let me now define my extension of $T_\varepsilon$, which I denote as $R_{(p_1,p_2)}$.  $R_{(p_1,p_2)} \to \mathbb{R}$ is given by $R_{(p_1,p_2)} f(x) = E_{y \sim \mu_{p,x}} [f(x+y)]$. But here our distribution $\mu_{p,x}$ is such that we flip the $1$ bits of $x$ to $0$ with probability $p_1$ and $0$ bits of $x$ to $1$ with probability $p_2$. ( $\mu_{p,x}$ is now clearly a distribution dependent on the $x$ where the function is evaluated, and if $p_1 = p_2$ then $R_{(p_1,p_2)}$ reduces to the 'regular' noise operator.)

I was wondering, has this operator $R_{(p_1,p_2)}$ already been well-studied somewhere in the literature? Or are the basic properties of it obvious? I am just starting with Boolean analysis, so this might be straightforward to someone more familiar with the theory than I am. In particular I am interested in if the eigenvectors and eigenvalues have some nice characterization, or whether there is any multiplicative property.


texts: What is mathematical difference between "random" and "unique"?

texts:
Once in a while when a question like "how I get good random numbers" is asked the suggested approach is to just generate an UUID. UUID looks like a random number and it is designed in such way that UUIDs likely never repeat - it is unique.

What is mathematical difference between "unique" and "random"? Why exactly should UUID not be used as a random number - for example as a cryptographic key?


texts: research on systematically attacking multiple instances of undecidable problems

texts:
this question is inspired by a recent popular question [1] on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint.

there are at least some papers of a type that attack multiple instances of undecidable problems. each instance of the general problem is not known a priori to be decidable or undecidable, and the paper describes strategies/techniques for identifying/sorting some into decidable cases, and provides algorithms which decide the problem if it is found to be among the decidable cases.

  what are papers of this genre, systematically attacking multiple instances of undecidable problems?

[1] A simple problem whose decidability is not known / Reyzin, tcs.se


texts:
I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems.
The problem is:
Start with a set of points $S$ and a target partition of that set $P$.
Let $\mathcal{P}$ be a set of partitions of $S$ not including $P$
The problem is to “cover” $P$ using the minimal number of partitions from $\mathcal{P}$
To make this more formal, a subset of the set of partitions $\tilde{\mathcal{P}}\subset \mathcal{P}$ covers $P$ if the meet of $\tilde{\mathcal{P}}$ (the coarsest partition finer than all partitions in $\tilde{\mathcal{P}}$) is finer than $P$.
Example
For example, suppose the target partition is $P=\big\{\{1,2\},\{3\},\{4\},\{5,6\}\big\}$ and $\mathcal{P}=\Big\{\big\{\{1\},\{2,3,4,5,6\}\big\};\big\{\{1,2,3\},\{4,5,6\}\big\};\big\{\{1,2\},\{3,4\}\{5,6\}\big\}\Big\}$
We only need two partitions from $\mathcal{P}$ to cover this. The meet of $\Big\{\big\{\{1,2,3\},\{4,5,6\}\big\};\big\{\{1,2\},\{3,4\}\{5,6\}\big\}\Big\}$ is $P$ and this is the minimal way to cover $P$ from $\mathcal{P}$.
What I’ve tried:
I have tried to map my problem into a set covering problem with no luck. I got hung up with the meet operation operating differently than the union in set covering.


texts: Lower bounds for minimum variance estimators in limited space

texts: Cramer-Rao,  Rao-Blackwell and Lehmann-Scheffé, all give you ways to prove that a statistical  estimator has the lowest variance possible. Is there any CS related work on the minimum variance estimator with limited space?  In other words, a variance/space tradeoff theorem.


texts:
Here is my problem:
I have an undirected graph (with loops). We have k different classes of vertices in the graph. You can think of class 1 vertex being colored green, class 2 vertices colored red and so on. There is also a special class of vertices colored white (more later).

Now, the user will specify a source vertex, a destination vertex, and a sequence of distinct vertex classes (non-white) eg.

We are given source vertex 10, destination vertex 40, and a sequence:
red->blue->black.

We have to find the shortest path such that the path starts from vertex 10, touches 1 red vertex followed by 1 blue and 1 black vertex and then reaches vertex 40. The path, however, can have as many white vertices as needed. It can also traverse a white vertex twice.

So a solution can be:
10->20(white)->35(red)->21(white)->22(white)->30(blue)->34(black)->40

Incorrect:

10->20(white)->30(blue)->21(white)->22(white)->35(red)->34(black)->40 (goes to blue before red)


texts: What is the complexity of vertex cover on k-partite graphs?

texts:
Given a k-partite graph which is already partitioned into k parts,
what is the complexity of finding a vertex cover of minimum size?

I guess that it's NP-hard, but couldn't yet prove it or find reference for it.
I'm also interested in the dependence on k.


texts: Voronoi partitioning on the 2nd and 3rd closest: how many pieces?

texts:
Where order-$k$ Voronoi diagrams partition according to the $k$ closest sites
(de Berg et al.
p. 169),
consider partitioning on the 2nd and 3rd closest —
call these [2,3]-Voronoi partitions.
Each cell is tagged with a set (unordered) of 2 sites $\{ p_i, p_j \}$.
Some pictures with Nsite = 5 random sites in the plane:

How does the number of cells in a [2,3]-Voronoi diagram vary with Nsite
and dimension $d$ in $\mathbb{R}^d$ ?

Added 18 Dec: some numbers from Monte Carlo
(despite "avoid experiment not backed up by a little theory"):

1-2-Voronoi 2d  3d  4d
----------------------
nsite  5:    7   9   9
nsite 10:   20  29  40
nsite 20:   44  79 139

2-3-Voronoi 2d  3d  4d
----------------------
nsite  5:   15  28  28
nsite 10:   57 129 246
nsite 20:  136 359 740


texts: Programmatic higher inductive/inductive-inductive types with equalities between equalities

texts: I can think of practical HITs in verified software that capture some form of alpha equivalence, context equivalence or the example which defines well-typed syntax of type theory from Signatures and Induction principles for HIITs. Now I am trying to think of one which also includes higher equalities, i.e. non-trivial equality of these equalities? Can someone point me to interesting examples where higher equalities play crucial role or at least improve reasoning? Actual examples of both HITs and HIITs with non-trivial higher equalities with applications to programming are what I am looking for.


texts:
Possible Duplicate:
  Finding a prime greater than a given bound

Question

Does there exist

a polynomial $q$
and a deterministic polynomial time algorithm $A$

such that for all sufficiently large $n$, we have:

$A(n)$ outputs a prime $p$ s.t. $n \leq p \leq q(n)$. (Note $n$ is stored in binary, so $A$ must run in $poly(\log n)$ time.)

Context

Suppose that for some derandomization task we need to be able to construct primes. This rules out the "guess a random number + check" approach since we can't use randomness.

Known

We have deterministic construction of irreducible polynomials: http://www.sciencedirect.com/science/article/pii/S074771718471025X
We also have deterministic primality checking: http://en.wikipedia.org/wiki/AKS_primality_test
By http://en.wikipedia.org/wiki/Bertrand_postulate there is a prime between $n$ and $2n-2$, but we can't check all $n$ numbers in $poly(\log n)$ time.
By http://en.wikipedia.org/wiki/Prime_number_theorem we know that $\pi(x) \sim \frac{x}{\ln x}$, but it's not clear that this implies there is a prime between $n$ and $n+O(\log n)$.


texts:
How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?  A polynomial time nondeterministic algorithm would immediately imply this because $P \neq EXPTIME$ but no one believes $NP = EXPTIME$.  If I've done the algebra right (see below) the time hierarchy theorem would still give the $P \neq NP$ implication for $O(2^n/f(n))$ running times for any superpolynomial $f(\cdot)$, but for all I know there are complete problems with efficient reductions that allow slower algorithms to give the result.  Are there EXPTIME-complete problems where we know something like $2^n/n$ or $2^n/n^2$ with nondeterminism is enough?

Clarification of the "algebra": $P = NP$ implies $EXPTIME=NEXPTIME$ by a padding argument, so a nondeterministic $2^n/f(n)$ algorithm for an EXPTIME-complete problem would also be one for a NEXPTIME-complete problem.  For superpolynomial $f(\cdot)$ this would contradict the nondeterministic time hierarchy theorem since we could reduce using some $L \in$ NTIME$(2^n)$.


texts: Complexity of Determining Linear Separability

texts:
Be $X := \{x_1,...,x_N\}$ and $Y := \{y_1,...,y_N\}$ subsets of $\mathbb{R}^d$.

What is/are the most efficient existing algorithm/s for determining whether X and Y are linearly separable and what is its/their computational complexity (O notation and P/LP/NP)?


texts: Why colon to denote that a value belongs to a type?

texts:
Pierce (2002) introduces the typing relation on page 92 by writing:

  The typing relation for arithmetic expressions, written "t : T", is defined by
  a set of inference rules assigning types to terms

and the footnote says The symbol $\in$ is often used instead of :. My question is simply why type theorists prefer to use : over $\in$? If a type $T$ is a set of values then it makes perfect sense to write $t \in T$, no new notation needed.

Is this similar to how some cs writers prefer $3n^2 = O(n^2)$ even thought it is abuse of notation and should be written $3n^2 \in O(n^2)$?


texts: Terminology for games with incomplete information and no prior beliefs

texts:
Can anyone please tell me what is the term used for games with incomplete information and there are no prior beliefs about other players' private information.

For example, let $ v_i(a_i,\theta_i) $ be the utility function of the player $ i $ and $ a_i $ be decided for each player some how. $ \theta_i $ be the private information for player $ i $. Player $ i $ has no belief (no knowledge of probability distribution) about others' private information except that it is a real number. Few authors call such games to be pre-Bayesian games. But there seems to be no standard. It would be great if any one can let me know this. Thanks!


texts:
While it is trivial to prove contraposition

∀ A B: Prop, (A → B) → (~B → ~A)

using Coq, is it equally trivial to prove the reversed form:

∀ A B: Prop, (~A → ~B) → (B → A)

? In particular, is it doable without using any additional axioms, e.g. from classical logic?


texts: Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?

texts:
If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether the equation is always true.  We can similarly decide if a single polynomial inequation is always true over $\mathbb{C}$, since $p(z_1,\ldots,z_n) \ne 0$ for all $z_i$ iff the polynomial is a nonzero constant.

Does the simplicity of randomized checking extend to any systems of multivariate polynomial equations?  In particular, is there a simple algorithm for deciding whether
$$p(z_1,\ldots,z_n) = 0 \implies q(z_1,\dots,z_n) = 0$$
where $p,q$ are straight line programs over $\mathbb{C}$ with integer coefficients?  I'm fairly sure randomness does not provide simple algorithms if we go to arbitrary systems of equations and inequations, but I'm curious where the boundary is between easy and hard.


texts: How do top researchers keep track new results in datastructures

texts: Is there any twitter or some feed,which constantly sends new results which are being published to your mail.


texts:
As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this case correspond to edges of $K_n$.
It is know (Razborov, Alon-Boppana)
that, for $3\leq k\leq n/2$, this function requires monotone
circuits of size about $n^k$.

But what if we take one fixed graph $G\subseteq K_n$, and consider
the monotone boolean function $CLIQUE(G,k)$, which takes a subset $S\subseteq [n]$ of vertices, and outputs $1$ iff some $k$ vertices in $S$ form a clique in $G$. Variables in this case correspond to vertices of $K_n$, and the function is just the standard clique function but restricted to the spanning subgraphs of one fixed graph $G$.

1. Does there exist $n$-vertex graphs $G$ for which  $CLIQUE(G,k)$ requires monotone
circuits of size larger than $n^{O(\log n)}$? I guess - NO.

2. Is $CLIQUE(G_n,k)$ an NP-hard problem for some sequence of graphs
$(G_n\colon n=1,2\ldots)$? I guess - NO.

Note that if $C_1,\ldots,C_r$ are all maximal cliques in $G$, then  $CLIQUE(G,k)$
can be computed as an OR of $r$ threshold-$k$ functions, the $i$-th of
which tests whether $|S_a\cap C_i|\geq k$. Thus, if $r=poly(n)$, then the entire
circuit is of polynomial size. But what about graphs with an
exponential number of maximal cliques? (A clique is maximal it no
vertex can be added to it.)

It is possible to "embed" $CLIQUE(m,k)$ into $CLIQUE(H,k)$ for a particular
graph $H$ on $n=2^m$ vertices. In particular, Bollobas and Thomason (1981) have shown that,
if $H$ is a Hadamard graph whose vertices
are subsets of $[m]$, and two vertices $u$ and $v$ are adjacent iff $|u\cap v|$ is
even, then $H$ contains an isomorphic copy of every graph $G$ on $m$ vertices.
Can this fact be combined with Razborov´s lower bound (of about $m^k$)
for $CLIQUE(m,k)$ to conclude that  $CLIQUE(H,k)$ requires monotone circuits
of size about $m^k$?  A potential problem here is that, even though the graph $H$ "contains" all $m$-vertex graphs, these graphs are not on the same set of vertices.
And Razborov's argument rquires that positive and negative inputs
($k$-cliques and complements of complete $(k-1)$-partite graphs) are
graphs on the same set of vertices. Moreover, all positive inputs ($k$-cliques)
are just isomorphic copies of one and the same fixed $k$-clique.

3. Any ideas? Has anybody seen such type of problems being considered?
I mean, decision problems for subgraphs of a fixed graph. Or, say,
the SAT problem for sub-CNFs of one fixed
(satisfiable) CNF (obtained by removing some literals)?

Motivation: Problems of this kind are related to the complexity of combinatorial optimization algorithms. But they seem to be interesting in themself.
Why should we seek for algorithms that are efficient on all graphs? In reality, we
are usually interested in the properties of small pieces of one (large) graph
(network of streets in a country, or facebook, or the like).

Remark 1: If the graph $G=(L\cup R,E)$ is bipartite, then the vertex-edge incidence matrix of the inequalities $x_u+x_v\leq 1$ for all $(u,v)\not\in E$ is totally unimodular, and one can solve the clique problem on induced subgraphs of $G$ via linear programming. Thus, for bipartite graphs $G$, $CLIQUE(G,k)$ has a small (albeit  non-monotone) circuit.

Remark 2: An indication, that in the case of bipartite graphs $G$, the answer to Question 1 "should" indeed be NO is that then the following monotone Karchmer-Wigderson game on $G$ needs only $O(\log n)$ bits of communication. Let
$k$ be the largest number of vertices in a complete bipartite subgraph of $G$.
Alice gets a set $A$ of red nodes, Bob a set $B$ of blue nodes such that $|A|+|B|>k$. The goal is to find a non-edge between $A$ and $B$.


texts: Simple question about pseudorandom generator

texts:
I am stuck on the following question related to pseudorandom generator and any help would be appreciated.

  Let $G:\{0,1\}^k \to \{0,1\}^{k+1}$ be a pseudorandom generator. Define $G':\{0,1\}^{2k}  \to \{0,1\}^{2k+2}$ by $G'(x_1x_2)=G(x_1)G(x_2)$ where $x_1, x_2 \in \{0,1\}^k$.

  Prove that $G'$ is not a pseudorandom generator in general.

I don't think it is necessary (and feasible) to find a counter-example $G'$ since it requires us to find a pseudorandom generator $G$, (which means we will have proved the existence of pseudorandom if we can find such $G$) so normally how can we tackle this kind of problem?

Thank you very much in advance. :)


texts:
Beck's theorem is a classical result in discrete geometry which describes about the geometry of points in the plane. The result states that a finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a single line, and one where a large number of lines are needed to connect all the points.

Formally, the statement of the theorem is as follows:

Theorem: Let $S$ be a set of $n$ points in the plane. If at most $(n-k)$ points lie on any line for some $0 \leq k < n-2$, then there exist $\Omega(nk)$ lines determined by the points of $S$.

Now, my question is that if the generalization/variation of the above result is known in the case of higher dimension $(dim\geq 3)$?


texts: The description from Wikipedia mentions that it is #P-Complete to compute, but there are methods.  What is a layman's explanation to this?


texts: Is there any online lecture series that covers "Computational Complexity: A Modern Approach"?

texts: I am trying to cover the Computational Complexity :A Modern approach by Boaz Borak and Sanjeev Arora. Are there any nice lecture series that cover this material ?


texts: In which paper did Alonzo Church first describe Church encoding? I can't find any articles that actually cite the paper, but I am interested in reading it.


texts: Parallel algorithms to color interval graphs

texts:
Several NP-hard graph problems get easy if we consider interval graphs. There is a greedy algorithm to color optimally an interval graph. Just sort the intervals according their left endpoints and color each interval with the last freed color.

Every coloring algorithm especially every efficient parallel algorithm I see, use the endpoints of intervals to get an optimal coloring. With "efficient parallel" I mean that the problem is in the complexity class NC.

There is a possibility to use only the structure of the graph to color the interval graph but this uses a maximum matching in a bipartite graph which isn't known to be in NC.

Is there any efficient parallel algorithm that doesn't use the endpoints of the intervals and just uses the structure of the graph to color an interval graph?


texts: Graph problems with good characterization but not known to be in $P$

texts:
A decision problem has good characterization if it is in $NP \cap coNP$. Many natural graph problems have good characterizations. For instance, Kuratuwski's Theorem gives good characterization of planar graphs. Konig's Theorem gives good characterization of bipartite graphs. Tutte's Theorem gives good characterization of graphs that have perfect matching. Euler's Theorem gives good characterization of Eulerian graphs. All these recognition problems have polynomial-time algorithms.

Is there a natural graph problem that has good characterization but not known to be in $P$? A pointer to a survey of such problems would be appreciated.


texts: Wouldn't the calculus of constructions with linear types be a simple functional core that is consistent and expressive?

texts:
I have recently asked if there is a simple functional core that is consistent and expressive. In another question, cody pointed out that this is an open problem to have a language that is:

Consistent/Normalizing
Can express all the type families from Coq (or even Agda)
Allows for a simple expression of recursion over these families
Simple or has a small number of core constructions (Π,Σ,μΠ,Σ,μ).

Now, suppose we take the elementary affine logic and extend it with dependent types and fix. It is easy to prove that language is consistent and normalizing as a consequence of EAL. It can, I believe, express all the type families from Coq, with lambda-encodings and since it has fix. A simple expression of recursive algorithms is possible with church-encodings for iteration and scott-encodings for matching. And it is obviously simple, as it only has ∀, ! and let. Moreover, such language would have the very comforting property that it can be reduced optimally using the abstract fragment of Lamping's algorithm.

All things considered, such language looks like a perfect candidate for the role of a small functional core that serves as an universal code-interchange format, as proposed by Gabriel. Is my suspicion correct, or is there any problem with this reasoning?


texts: Is there an algorithm for finding the maximal edge weight over all spanning trees?

texts:
Let $G = (V,E)$ with a weight function $w(e)$ for $e \in E$.

Let $T$ be the set of minimal spanning trees of $G$.

I am interested in finding $\min_{t \in T} \max_{e \in t} w(e)$, where $t$ ranges over minimal spanning trees.

This is the minimally heaviest edge in all minimal spanning trees.

Is there an algorithm for finding this value? What if I am interested in finding this value approximately, without exploring the whole graph (because the graph is quite large)? Is there a sampling or an approximate algorithm in this case?


texts: Has there been work on formal Semantics for linear algebra?

texts:
Could I get some references on formal semantics for a calculus on linear algebra that helps you study matrix or tensor based programming languages? I am looking for anything that encompasses linear or multilinear algebra objects and operations as first class constructs.

I remember seeing something on it a while ago but I can't seem to find that paper or any other reference on the subject. If there is any specific terminology that would help me search for it better it would also be appreciated.


texts: Efficient algorithm to find overlapping circles of various sizes

texts:
I have a collection of N circles in the plane with various position and radius. Circles move around according to one force and become bound to each other once they overlap.
I need a fast way to determine if a circle is overlapped/overlaps another, to determine the circle's equations of motion during a time step.
Once circles have overlapped, they are bound, so it's easy to remember that relationship.
The problem is to evaluate when circles overlap for the first time.
Think of cheerios floating on milk.

Obviously I have thought of using a KDTree or a Delaunay Triangulation, but these only take into account the circle centers, not their radius, so the closest circle in a DT Trianle isn't necessarily overlapping, while another might be.

I've read somewhere that a MWVD might work, but I don't understand how that would work.
D Eppstein has a couple of papers out on Mobius Transformations, and that too is over my head, but it looks like it's related.
Can anyone point me in the right direction ?

Thanks.


texts:
My question is a bit generic, so I'm making up a nice story to justify it. Bear with me if it's not realistic ;-)

Story

Mr. X, the head of the computer security department at a big company, is a bit paranoid: he requires that all employees change their passwords once a month, in order to minimise the risks of identity or information theft. Moreover, he does not trust the employees to be able to come up with secure passwords.

Therefore, every month, he generates new passwords using a piece of software he wrote, and gives them to the employees so that they can log in again. But besides being paranoid, Mr. X is also a bit lazy: the passwords he generates all follow some pattern, and the algorithm used to allow people to log in only checks that the password "looks okay" according to that rule, and that it is not in the "expired list".

Unfortunately, his pretentious behaviour made a lot of people bitter, and one of them, Mr. Y, decides to prove him that he can crack his passwords. So, one night, he collects a few of them, and starts trying to design a learning algorithm for generating valid passwords, using his personal computer to verify them.

Question

The oracle used by Mr. Y is a bit strange, in that it tells him "the truth, but not the whole truth" (hence the "taciturn" adjective). More precisely: Mr. Y will know that a password is valid when his computer accepts it, but when a password is rejected, Mr. Y will not know whether or not it could have been valid: the password may be rejected because it does not correspond to some pattern, but it may also be rejected because it used to be valid but no longer is, according to Mr. X's "change once a month"-rule.

So, will Mr. Y ever be able to come up with anything in that setting? Or can we claim/prove that Mr. X's passwords are inherently unpredictable (as defined in the PAC learning setting, but maybe this concept exists in other frameworks)?


texts:
Consider the following problem:

Input: A binary string $w$.
Output: $|w|$ as a binary number.

Is it possible to compute this
in $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$
(or equivalently in $\mathsf{AltTime}(O(1),O(\lg n))$ or $\mathsf{FO}$)?


texts: Is there any connection between Interactive proofs and learning theory?


texts: Algorithm to merge two incomplete sequences of symbols (strings) into a complete one

texts:
I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution.

Let's say we have two ordered lists of symbols (strings):

A = "foobarquuz123foo"
B = "foobar456quuzfoo"

my goal is to have an algorithm that merges the two incomplete lists into the following, that can be considered completed, having parts from both lists:

C = "foobar456quuz123foo"

As you can see there is no intrinsic "sorting value" associated to the symbols, only their position, which is just a relative measure. Moreover, the symbols might be also repeated in arbitrary points of the strings.

Maybe the algorithm I am looking for might have been used in bioinformatics, for example for DNA or protein sequence alignment, but I am no expert of this.

What would you recommend? Do you have some pointers to algorithms that may solve this problem? I think that someone should already have figured out a solution with upper-bound computational complexity $O(k(n+m))$ where $k$ is a constant and $n$ and $m$ are the lengths of the strings.

I would be very happy to get also suggestions for books that illustrate this and similar problems.


texts: What math courses should I take to prepare for a CS masters or PhD?

texts: I'm a self-taught professional programmer. I am pretty good at it (Ruby, Unix, Clojure, Java, Objective-C), but now I'm thinking of taking it to the next level by maybe applying for a masters or PhD program in CS. What topics in math should I study to prepare for this goal?


texts: Reference Request: soundness in a ZKP achieved by walking along a doubly-stochastic Markov chain?

texts:
Consider the following variant of a zero-knowledge proof that two graphs, $G_1$ and $G_2$, given by adjacency matrices $M_1$ and $M_2$, respectively, are not isomorphic.

Here Peggy the prover wants to show Vicky the verifier that $G_1 \not\cong G_2$, where both $G_1$ and $G_2$ have $n$ vertices.

Peggy and Vicky agree on a small number, say $r$, of generators $\pi_1,\pi_2,\cdots,\pi_r$ of the symmetric group $S_n$ on the $n$ vertices
Vicky (secretly) tosses a fair coin $i\in \{0,1\}$ to determine to which graph $G_i$ she will permute the vertices
Vicky (secretly) chooses $t$ random numbers $g_1,g_2,\cdots,g_t\in[r]$, and applies the (concatenated) permutation $\pi_{g_1}\pi_{g_2}\dots\pi_{g_t}$ to the vertices $M_i$, to generate a new matrix, $M_3$
Vicky presents $M_3$ to Peggy
Peggy must deduce $i$ from $M_3$, that is, she must deduce which of the graphs $G_1$, $G_2$ Vicky chose in step 1

A difference between a standard graph non-isomorphism protocol and the present protocol is in step 3.  That is, conventionally in step 3, Vicky just randomly chooses any old element $\pi\in S_n$ to apply to the graph $G_i$, but in the above protocol in step 3, Vicky walks along the Cayley graph of $S_n$ with generators $\langle\pi_1,\pi_2,\cdots,\pi_r\rangle$ a total of $t$ times.

Notice that because each step of the Markov chain is, by definition, an invertible permutation of the configuration space (the configuration space being the set of all adjacency matrices equivalent to $M_i$), such a walk is a doubly-stochastic Markov chain, meaning each column (resp. row) of the transition matrix sums to $1$.  Thus, after the selected adjacency matrix $M_i$ is properly mixed, the matrix that Vicky will present to Peggy is uniformly distributed over all matrices isomorphic to $G_i$.  Accordingly, if $G_1\cong G_2$, then Peggy would not have better than even chance of deducing $i$, because she will just be given two random matrices isomorphic to $G_i$; hence, the protocol is sound.

A key concern is that we need to make sure that the matrices are properly mixed, that is, that the number of steps $t$ along the Cayley graph is large enough to mix the given graphs to the limiting distribution.  I believe, although I can't prove it for now, that for most generating sets $\{\pi_1,\pi_2,\cdots,\pi_r\}$ of the symmetric group $S_n$, $t$ is probably $O(\log n)$.

But, now to generalize, given any two elements chosen from any discrete configuration space, not just adjacency matrices representing graphs, I think we have a sound zero-knowledge protocol to show that the two elements are not in the same equivalence class, as long as we can construct a fast-mixing doubly-stochastic Markov chain to walk through the configuration space.

  Has such an approach to zero-knowledge proofs using doubly-stochastic Markov chains been studied before?

As one example,  we may apply such a protocol to some problems in discrete robot motion non-equivalence, rather than adjacency matrices of graphs. That is, we can have a sound zero-knowledge protocol that a discrete robot in a particular position cannot be converted to another position, using a fixed set of invertible generators.  Rather than deciding only one element of the symmetric group $S_n$, Vicky must choose a particular path along a Markov chain, where each state is an element of the configuration space and each transition is given by one of the generators of the robot.  After mixing, the test element of the configuration space will be chosen uniformly from all elements of the configuration space in the same equivalence class as the given robot configuration.


texts: I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)

texts:
It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle.

Is there a nice gadget that will, given a graph G, replace all of the crossings
with some planar gadget so that you have a planar graph G' such that

  G has a Ham cycle iff G' has a Ham cycle.

(I'll be happy with variants- like Ham path or directed Ham Cycle or
Directed Ham Path.)


texts: Minimizing a sum of thresholded quadratics

texts:
Let $W_1, \ldots, W_k$ be positive semi-definite matrices, $b_1, \ldots, b_k$ be vectors,  and  $a_1, \ldots a_k$, $c_1, \ldots, c_k$ be scalars. How difficult is it to find an approximate minimum of
$$ f(x) = \sum_{i=1}^k \min(x^T W_i x + b_i^T x + a_i, c_i)$$

The difficulty is that the individual functions $\min(x^T W_i x + b_i^T x + a_i, c_i)$ are not necessarily convex. Moreover, although the individual functions $\min(x^T W_i x + b_i^T x + a_i, c_i)$ are quasiconvex, a numerical experiment suggests that their sum may not be quasiconvex.


texts: Is case analysis on normal forms of lambda terms sufficient to prove parametricity results?

texts:
There are many closed terms of a given type. For instance, both of these terms:

$$ \lambda x . x $$
$$ \lambda x . (\lambda y . y) x $$

have a type of a polymorphic identity function:

$$ \forall X . X \rightarrow X$$

On the other hand, there is only one normalized term of that type i.e: $\lambda x . x$.
Similarly, given the type of Church natural numbers:

$$ \mathtt{Nat} = \forall X . (X \rightarrow X) \rightarrow X \rightarrow X $$

one can argue that all the normal form terms of type $\mathtt{Nat}$ are in the form:

$$\lambda s . \lambda z . s (\ldots (s\; z)) $$

Is there any research that goes along these lines and perhaps formalizes this intuition?

Is this idea correct and strong enough to prove (by case analysis on the normal forms of the terms) 'free theorems' or more general parametricity results?

Clarification: The type system in question is System F


texts:
Consider a language like Brainfuck but without the brackets. At the end of each line (i.e. when "\n" occurs), if the current cell is not 0, then the line is re-executed.

An example of an infinite loop:

+.
// OUTPUT (numbers represent the corresponding ascii characters)
1
2
3
...

Now, would this hypothetical language be Turing-complete? I'd say yes but I'm not sure, since there's no such a goto thing at all, only while-like.


texts: What is the actual time complexity of Gaussian elimination?

texts:
In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time.  While it is obvious that the algorithm uses $O(n^3)$ arithmetic operations, careless implementation can create numbers with exponentially many bits.  As a simple example, suppose we want to diagonalize the following matrix:

$$\begin{bmatrix}
2 & 0 & 0 & \cdots & 0 \\
1 & 2 & 0 & \cdots & 0 \\
1 & 1 & 2 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & 1 & 1 & \cdots & 2 \\
\end{bmatrix}$$

If we use a version of the elimination algorithm without division, which only adds integer multiples of one row to another, and we always pivot on a diagonal entry of the matrix, the output matrix has the vector $(2, 4, 16, 256, \dots, 2^{2^{n-1}})$ along the diagonal.

But what is the actual time complexity of Gaussian elimination?  Most combinatorial optimization authors seem to be happy with “strongly polynomial”, but I'm curious what the polynomial actually is.

A 1967 paper of Jack Edmonds describes a version of Gaussian elimination (“possibly due to Gauss”) that  runs in strongly polynomial time.  Edmonds' key insight is that every entry in every intermediate matrix is the determinant of a minor of the original input matrix.  For an $n\times n$ matrix with $m$-bit integer entries, Edmonds proves that his algorithm requires integers with at most $O(n(m+\log n))$ bits.  Under the “reasonable” assumption that $m=O(\log n)$, Edmonds' algorithm runs in $O(n^5)$ time if we use textbook integer arithmetic, or in $\tilde{O}(n^4)$ time if we use FFT-based multiplication, on a standard integer RAM, which can perform $O(\log n)$-bit arithmetic in constant time.  (Edmonds didn't do this time analysis; he only claimed that his algorithm is “good”.)

Is this still the best analysis known?  Is there a standard reference that gives a better explicit time bound, or at least a better bound on the required precision?

More generally: What is the running time (on the integer RAM) of the fastest algorithm known for solving arbitrary systems of linear equations?


texts: Is there value in a faster soultion for the Halting Problem in a Linear Bounded Automata?

texts:
Sorry for being so informal, but I was thinking a bit about how the Halting Problem is solvable on a LBA but very very slow, in that if you have gone though more states in execution then the total number of states possible, the program would be hanging by the pigeonhole principle. But this has the time complexity of O(2^N).

Well, the idea is instead to think of the machine's execution of code as a linked list of states, having a way to quantify the state in an easily comparable manner, and then make use of the Floyd's cycle-finding algorithm. So you can run two instances of the program to be tested at once, where one instance executes a single instruction, and the other instance will execute two instructions, and compare the states. If the states are ever the same, the program has hung. And if I remember right this would be a much much faster process, being a time complexity of just O(N).

Would using my method be feasible or faster, and is there even any use of coming up with a faster methodology?


texts:
Let $M$ be a binary ($0-1$) matrix of size $n \times m$. We define binary rank of $M$ as the smallest positive integer $r$ for which there exists a product decomposition $M = UV$, where $U$ is $n \times r$ and $V$ is $r \times m$, and all entries of $U$ and $V$ come from $\{0, 1\}$.

My question is that is there known algorithmic way to determine the binary rank of $M$; and Singular value decomposition that support the binary rank. Any reference in this regard would highly help.


texts:
Is the following manuscript publically available?

  Dana Scott, 1969, A theory of computable functions of higher type. Unpublished seminar notes, 7 pages, University of Oxford.

There is a discussion of this paper in section 8.1.2, Types as sets, in Cardone & Hindley, 2006 History of Lambda-calculus and Combinatory Logic; additionally section 10.1, Domain theory, traces back to this manuscript some crucial order-theoretic insights.


texts: Interesting real life problem similar to subsetsum /bin packing problem

texts:
I have a real life scenario, where I need to solve a construction related problem somewhat similar to bin packing problem.The situation is as follows :

I have large number of cable reels/drums (let's say in the order of 10,000 numbers) each having varying lengths (random lengths between 200 meter to 3,000 meter) of cable in it.

I have to cut a large number of cables of different lengths (that randomly varies from 10 meter to 1000 meter).

I want to allocate the cables to these drums with two objectives viz. (a) minimize wastage or minimize total drums used for the whole allocation (b) Maximize the length of waste cables (e.g. instead of wasting two 10 meter cable, when absolutely necessary, I would try to waste one 20 meter) to increase the chance of re-usability.

I have used a dynamic algorithm (similar to solving a subset sum problem) to find the best fit for a specific cable reel/drum and get a fairly good solution.

However, this is not the most optimum solution for the following reasons :

(1) I don't know at the beginning which drum to take first for the allocation. The sequence at which I start allocation vastly affects the overall wastage.

(2) When there are multiple perfect combinations possible for zero wastage for a particular drum, choosing right combination from that for a overall optimization is my challenge.

(3) I end up making zero wastage for a drum, where I should actually keep some deliberate wastage to use up some specific cable, that will lead me to a over all minimized wastage. That means, making zero wastage for a drum is not necessarily the best solution, (especially when the cable lengths are in the order between 300 to 800 meter)

Can anybody please guide me with some ways to improve the situation.


texts: Complexity of computing shortest paths in the plane with polygonal obstacles

texts:
Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon.  The Euclidean shortest path problem is to compute the Euclidean shortest path from $s$ to $t$ that does not intersect the interior of any polygon.  For concreteness, let us assume that the coordinates of $s$ and $t$, and the coordinates of every polygon vertex, are integers.

Can this problem be solved in polynomial time?

Most computational geometers would immediately say yes, of course: John Hershberger and Subhash Suri described an algorithm that computes Euclidean shortest paths in $O(n\log n)$ time, and this time bound is optimal in the algebraic computational tree model.  Unfortunately, Hershberger and Suri's algorithm (and nearly all related algorithms before and since) seems to require exact real arithmetic in the following strong sense.

Call a polygonal path valid if all its interior vertices are obstacle vertices; every Euclidean shortest path is valid.  The length of any valid path is the sum of square roots of integers.  Thus, comparing the lengths of two valid paths requires comparing two sums of square roots, which we don't know how to do in polynomial time.

Moreover, it seems completely plausible that an arbitrary instance of the sum-of-square-roots problem could be reduced to an equivalent Euclidean shortest-path problem.

So: Is there a polynomial-time algorithm to compute Euclidean shortest paths?  Or is the problem NP-hard?  Or sum-of-square-roots-hard?  Or something else?

A few notes:

Shortest paths inside (or outside) one polygon can be computed in $O(n)$ time without any strange numerical issues using the standard funnel algorithm, at least if a triangulation of the polygon is given.
In practice, floating-point arithmetic is sufficient to compute paths that are shortest up to floating-point precision.  I'm only interested in the complexity of the exact problem.
John Canny and John Reif proved that the corresponding problem in 3-space is NP-hard (morally because there may be an exponential number of shortest paths).  Joonsoo Choi, Jürgen Sellen, and Chee-Keng Yap described a polynomial-time approximation scheme.
Simon Kahan and Jack Snoeyink considered similar issues for the related problem of minimum-link paths in a simple polygon.


texts: Is there a closed form equation for the back-propagation equation update in Neural Networks?

texts:
I was trying to understand if there was a way to express the back-propagation equations from neural networks in a better way as to understand them better. I believe the equations can be written in a recursive manner as follows (using the notation from these notes from Andrew Ng):

$$ \delta^{(n_l)}_{i} = \left( \sum^{s_{l+1}}_{j=1} W^{(l)}_{ji} \delta^{(l+1)}_{j} \right) f'(z^{(l)}_{i})$$

I know that some recursions/recurrences have closed form "equations"/solutions. A typical example would be the Fibonacci sequence (or things that use Akra-Bazzi to solve them). I was wondering, because of the similarity to recursion of this equation, does something like that exist for back-propagation equations in Neural Networks? If there is not, does that mean its impossible to get such an equations? I was wondering if there were formal mathematical proofs arguments that might explain the impossibility of such an attempt or any work that has been tried to that goal.

In reality, it seems that the main use of this equation is algorithmically. But I was hoping that having some sort of equation (or even approximation to this recurrence) could help understand back-propagation and neural networks better. Might this require new mathematics to achieve something like this? Or maybe trying to do something like this makes no sense? If so why so?


texts: Eta expansion in the pattern lambda calculus

texts:
Klop, van Oostrom, and de Vrijer have a paper on the lambda calculus with patterns.

http://www.sciencedirect.com/science/article/pii/S0304397508000571

In some sense, a pattern is a tree of variables -- though I am just thinking of it as a nested tuple of variables, for example, ((x,y),z),(t,s)).

In the paper they showed that if the patterns are linear, in the sense that no variable in a pattern is repeated, then the rule

(\p . m) n = m [n/p]

where p is a variable pattern and n is a tuple of terms with the exact same shape as p, is confluent.

I am curious if there are similar developments in the literature for the lambda calculus with patterns and the additional eta rule (expansion, reduction, or just equality).

In particular, by eta, I mean

m = \lambda p . m p

More directly, I am curious what properties such a lambda calculus would have.  For example, is it confluent?

It forces the classifying category to be closed because it forces the property that

m p = n p implies m = n

By using the \xi-rule in between.  But perhaps something could go wrong?


texts:
I would like to formalize some simple properties of planar graphs in the Coq proof assistant.

1) How are planar graphs formalized in the Coq proof assistant? Is there a "standard" definition that is widely used? For instance, a definition that is already in some library for the manipulation of planar graphs?

2) Even better: Is there any inductive definition that is widely used?


texts:
is there a general statement what kinds of problems can be solved more efficiently using quantum computers (quantum gate model only)? do the problems for which an algorithm is known today have a common property?

as far as i understand quantum computing helps with the hidden subgroup problem (shor); grover helps speedup search problems. i have read that quantum algorithms can provide speed-up if you look for a 'global property' of  a function (grover/deutsch).

is there a more concise and correct statement about where quantum computing can help?
is it possible to give an explanation why quantum physics can help there (preferably something deeper that 'interference can be exploited')? and why it possibly will not help for other problems (e.g. for NP-complete problems)?

are there relevant papers that discuss just that?

(sorry, new here. hope that question is appropriate & understandable and there is not too much wrong in my statements...)


texts: What is the best way to find circles that contain a given point (in 2D)?

texts:
Given $n$ circles all with radius $r$ and one point on a 2D plane, what is the best algorithm to find all circles that contain the given point. The circles and the point can change their positions.
The simple approach would be to iterate through each circle and then apply the good old circle equation, that is: check whether the distance between the center of the circle and the point is less than the radius of the circle. One query would be of complexity $O(n)$. Is there a faster algorithm?


texts: Characterisation of the BCIW definable functions

texts:
Given a full model of the simply typed lambda calculus, it's possible to characterise the lambda definable functions as those that are invariant under every "Kripke logical relation". (See  here.)

I was wondering if anyone knows whether it is possible to give a similar characterisation of the functions definable in the $\lambda I$ calculus: the functions definable from $\lambda$ terms without vacuous $\lambda$ abstraction (or equivalently definable from the BCIW combinators).

A natural conjecture is that they are just the functions that are invariant under every "Routley-Meyer logical relation". (A Routley-Meyer frame is the analogue of the Kripke semantics for intuitionistic logic but for relevant logic --- the propositional logic axiomised by the types of the B, C, I and W combinators. World relative logical relations can be defined from them in a completely analogous way.)


texts: Computational complexity of Initial Value Problems of ODEs

texts:
Are there known results on computational complexity of initial value problems of ODEs? As my question may be somewhat vague, I want to mention that I'm mainly interested for results on the computational complexity of one-step methods (Runge-Kutta).

Edit: I forgot to mention that I'am aware of the obvious time complexity results based on the number of function evaluations and the rate of convergence. I'm also aware of the PSPACE-completeness of the solution when the right-side of the equation $y'(t)=f(y(t),t))$ is polynomial-time computable and satisfies the weak Lipschitz condition w.r.t. $y(t)$ (which can be safely assumed in my case). All I want to know is what kind of conditions should an IVP obey to for its solution, $y(t)$, to be computable in polynomial time, if such conditions have beed found.


texts:
Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some constant and $v$ is the number of edges with endpoints are colored the same. As $c$ goes to 0, this reduces to counting proper colorings which is hard for many graphs. When c is 1, every colorings gets the same weight and the problem is trivial. When adjacency matrix of the graph multiplied by $-\log(c)/2$ has spectral radius below $1-\epsilon$, this sum can be approximated by belief propagation with convergence guarantee, so it's easy in practice. It's also easy in theory because a particular computation tree exhibits decay of correlations and hence allows a polynomial time algorithm for guaranteed approximation -- Tetali, (2007)

My question is -- what other properties of the graph make this problem hard for local algorithms? Hard in a sense that only a small range of $c$'s can be addressed.

Edit 09/23: So far I came across two deterministic polynomial approximation algorithms for this class of problem (derivatives of Weitz's STOC2006 paper and of Gamarnik's "cavity expansion" approach to approximate counting), and both approaches depend on the branching factor of self-avoiding walks on the graph. Spectral radius comes up because it's an upper bound on this branching factor. The question is then  -- is it a good estimate? Could we have a sequence of graphs where branching factor of self-avoiding walks is bounded, while branching factor of regular walks grows without bound?

Edit 10/06: This paper by Allan Sly (FOCS 2010) seems relevant...result suggests that branching factor of infinite tree of self-avoiding walks precisely captures the point at which counting becomes hard.

Edit 10/31: Alan Sokal conjectures (p.42 of "The multivariate Tutte polynomia") that a there's an upper bound on the radius of zero-free region of the chromatic polynomial which is linear in terms of maxmaxflow (maximum s-t flow over all pairs s,t). This seems relevant because long-range correlations appear as the number of proper colorings approaches 0.


texts: Online bridge and nonbridge counting (identification)

texts:
I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of edge insertions and deletions for fixed set of vertices?

I have been using the algorithm presented in Schmidt's "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", c.f. ArXiv, which is not online but a linear-time algorithm.

On the other hand I have also played around with a fully-dynamic connectivity algorithm, presented here. The problem here is that albeit the algorithm allows connectivity queries in poly-logarithmic time, to be able to say something about whether an edge is a bridge I actually need to perform a deletion and see if the connectivity changed.

Because my goal is to determine the number of bridges (or non-bridges) online, I would need to perform a deletion process for all bridges... And that can destroy the poly-logarithmic time complexity.

Any ideas?

Many thanks


texts: How much time to recognize palindromes in logarithmic space?

texts:
It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time algorithm uses a copy of the input, and thus also uses a linear space.

Can we recognize palindromes in linear time of a multitape Turing machine, using only  a logarithmic space? More generally, what kind of space-time trade-off is known for palindromes?


texts: How to simulate the quantum measurement of a quantum state in Quantum Image

texts:
I'm trying to implement (simulate) the Novel Enhanced Quantum Representation (NEQR), which is one of the quantum image representation models, but i'm stuck in the measurement part. In other words i don't know how to retrieve the original image from the quantum state.

The image is represented by the following formula (this is the final form after preparation):
$$
\left| \psi \right\rangle = \frac{1}{2^n}
\displaystyle\sum_{Y=0}^{2^n -1} \displaystyle\sum_{X=0}^{2^n-1} \left| f(Y,X) \right\rangle \left| YX \right\rangle
$$

Now, assume that i have a 2 x 2 image and the color of each pixel is 2 bit only, the position -> color cobinations are as follow:

YX -> color
00 -> 11
01 -> 00
10 -> 01
11 -> 00

The image or the final state which is composed of two entangled qubit sequences (color and position) should be a 16 x 1 column vector indexed by binary representation from 0 to 15 (e.g. 0000, 0001, ... 1111) and the value of 0001 will be 1 because color 00 is located in position 01.

The measurement is as follow:

  During image retrieval from the quantum image, every pixel should be recovered
  individually. The following operations have been devised to retrieve pixel from a
  $$ 2^n × 2^n $$  quantum image.

How to perform measurement on the quantum state to retrieve the original image. In other words how to construct the matrix that when i multiply it with the state i retrieve the original image, but how to do that according to Quantum Operations ?

Please help to to solve this issue or guide me to the correct path.
I didn't add all equations because i don't know if that is legal so please look for them in the paper.


texts: Enumerating Planar Graphs of Bounded Treewidth

texts:
I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical and practical results, but mostly practical algorithms that are possible to code and run for as large as possible values of $n$ and $k$ (think $k \leq 5$ and $n \leq 15$). If you already have an answer, ignore the ramblings below.

The following approach works sort of ok for enumerating all non-isomorphic graphs on $n$ vertices and treewidth $\leq k$ (i.e when the planarity constraint is dropped):

(a) Enumerate all non-isomorphic graphs on $n-1$ vertices and treewidth $\leq k$.

(b) For each vertex $G$ on $n-1$ vertices and treewidth $\leq k$, every clique $C$ on $\leq k$ vertices in $G$ and every subset $S$ of edges in $C$, make $G'$ from $G - S$ by adding a new vertex $v$ adjacent to $C$. Add $G'$ to the list ${\cal L}$ of grahs on $n$ vertices and treewidth $\leq k$.

(c) Trim ${\cal L}$ by removing copies of the same graph.

A tempting way to extend this to enumerate planar graphs of treewidth $\leq k$ is to simply filter out the non-planar graphs at every iteration. Unfortunately this fails to generate all planar graphs of treewidth $\leq k$ (for example because it only enumerates $4$-degenerate graphs).

Of course we could enumerate all graphs on $n$ vertices and treewidth $\leq k$ and only then filter out the non-planar ones, but this fails to exploit that most graphs are non-planar and seems very sub-optimal.


texts: Upperbound for max degree of k-tree completion

texts:
Definitions: For a graph $G$, a $k$-tree completion of $G$ is a $k$-tree obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a partial $k$-tree). The least integer $k$ such that $G$ has a $k$-tree completion is called the treewidth of $G$. The maximum degree of a graph $G$ is denoted by $\Delta(G)$.
Question: Suppose that $G$ has a $k$-tree completion.
Is there an upper bound $U$ in terms of $k$ and $\Delta(G)$ such that
there exist a $k$-tree completion $G'$ of $G$ with $\Delta(G')\leq U\,?$
(note: To be explicit, $U$ is a function of $k$ and $\Delta(G)$ )
Context: I have a graph parameter $x(G)$ such that $x(G)\leq \Delta(G)+p$ for every chordal graph $G$ where $p$ is a constant. Using this result, I am trying to give an upper bound for $x(G)$ in general graphs in terms of treewidth of $G$ and $\Delta(G)$.


texts:
This question may not suit to here, but I couldn't find a better place to ask (it was closed in SO).

I find research papers on computer science hard to understand. Of course the subjects are complicated. But after I understand a paper usually I can tell it to someone in simpler terms, and make them understand. If somebody else tells me what is done in that research I understand too.

I think the best example that I can tell here is: I have tried to understand SIFT paper for a long time, and I found a tutorial while googling, in a couple of hours I was ready to implement the algorithm. If I was to understand the algorithm from the paper itself it might have taken a couple of days I think.

My question is: is it only me who finds research papers this hard to understand? If not how do you deal with it? What are your techniques? Can you give tips?


texts: "Exact" (not just the order) computational complexity of eigenvalue decomposition

texts:
Does anyone know what the eigenvalue decomposition of a general n x n complex matrix is? By complexity I mean the number of multiplication operations. I know from another question posted on this site that it is in the "order" of n^3 but I need to know how much is it exactly or at least the coefficient of this n^3.

Also I'd appreciate it if this complexity is for the fastest known algorithm as well if possible.

Thanks.


texts: Complexity of problem that can be solved by exponentially many SATs

texts:
I have two decision problems (function problems, actually) that are closely linked.  The first one consists in finding a variable assignment to $x$ Boolean variables so that a specification $A$ is met.

The whole problem can be reduced to FSAT and vice versa, making it FNP-Complete.

Now there's a second problem related to the first, which is to determine all variable assignments to the $x$ variables, for which $A$ is met.

What is the computational complexity of this problem?

It can be solved by applying SAT $2^x$ (i.e., an exponential number of) times; so that is not a valid reduction.

This is like finding all satisfying assignments to a SAT problem.  Strangely I did not find much on this in Papadimitriou's book.


texts: Self-referentially defined graph structures

texts:
It is possible to define graphs $G$ such that whether an edge exists between two vertices $v_1$ and $v_2$ depends on non-local properties of $G$.

In particular, I am interested in directed graphs where an edge $(v_1, g(v_1, w))$  exists for each leaf vertex $w$ that is reachable from $f(v_1)$. Here, $f$ maps vertices to vertices, $g$ maps pairs of vertices to vertices.

Is there research on data structures and algorithms for working with such self-referentially defined graph structures?


texts: Natural theorems proven only "to high probability"?

texts:
There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing.

Question: Are there any natural mathematical "theorems" where a randomized proof is known but a deterministic proof is not?

By a "randomized proof" of a statement $P$ I mean that

There is a randomized algorithm that takes an input $n > 0$ and if $P$ is false produces a deterministic proof of $\neg P$ with probability at least $1-2^{-n}$.
Someone has run the algorithm for, say, $n = 100$, and not disproved the theorem.

It's easy to generate non-natural statements that fit: just pick a large instance of any problem where only an efficient randomized algorithm is known.  However, although there a lot of mathematical theorems with "lots of numerical evidence", such as the Riemann hypothesis, I don't know of any with rigorous randomized evidence of the above form.


texts: Number of subgraphs with a given number of nodes

texts:
Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$.
The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where
$V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$
Let $k_1 \leq |E_G|$ and $k_2 \leq |V_G|$ be given in input.
I would like to determine the number $k_3$ of edge-induced subgraphs of $G$ having $k_1$ edges and $k_2$ nodes. Clearly, I don't want to enumerate all the (exponentially many) subgraphs of $G$ having $k_1$ edges.

Questions:

Is it possible to determine $k_3$ in time polynomial in $|E_G|$?
What if $G$ is 3-regular?
What if $G$ is 3-regular planar?
What if $G$ is 3-regular planar bipartite?
Which is the best known algorithm to compute $k_3$? $\longleftarrow$ Added on 30/08/2012


texts: What do stronger circuit lower bounds give in terms of derandomization?

texts:
We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.

This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.

Is there any consequence of a stronger derandomization?

Let $a(n)$ be any time constructible superpolynomial.

What does $NTIME(a(n))\not\subseteq P/poly$ give?
What does $DTIME(a(n))\not\subseteq P/poly$ give?

Do these give $BPP\subseteq io-DTIME(poly(n))$ or some thing weaker?


texts: Linear Time Maximum Clearance Computation on a Grid Graph?

texts:
I have a uniform NxN grid with a non-empty subset of vertices marked as obstacles.  My goal is to compute, for each non-obstacle vertex, the "maximum clearance" from the obstacle set.  In other words, the radius of the largest circle center at the vertex not overlapping with any obstacle.  Or the nearest "gas station" for each vertex.  [sorry if there is some standard terminology I should have used]

I would like a linear-time algorithm to compute this.  Can anyone help?

My gut feeling is that it is possible.  I have searched but didn't get a straight answer, but I know the following:

(1) if the distance metric is Manhattan, this can be solved by a simple flooding.

(2) I know a little bit about Level Set, and it may help, but is there something simpler?

(3) I understand Fortune's elegant sweeping algorithm to calculate Voronoi diagram in O(n log n), where n is the number of points.  For my particular application, since the wavefront never contains more than N vertices, the complexity is O(N log N).  The O(log N) is due to updates to a binary tree.  I hope this can be reduced from O(N log N) to O(N) because of the nature of my problem?

I am willing to do this in multiple passes in order to get linear time.  For example, one pass each for N, E, S, W, which hopefully somewhat simplifies Fortune's algorithm.  Also I am not interested in the Voronoi vertices but rather the distances of the grid vertices from the obstacles.

Is this a known, solved problem?  If so, source code or (more detailed) pseudo code?

If not, so far what I have in mind is to do this in two passes (Eastbound sweep and Westbound sweep):

Consider the East-bound sweep, I update one column of N vertices at a time.  There is a set of exactly N "back" vertices (each is assigned an X coordinate, or -infinity if they are out of scope (OOS)) such that a partition is defined by the bisecting lines between immediate non-OOS neighbors (similar to Fortune).  In other words, each non-OOS vertex is given a range [ys, ye] which together partitions [0, N - 1].  I don't maintain a binary tree of non-OOS vertices.  Instead, I always keep them in an array of size N.

When we move to the next column, the partition changes.  The partition is recalculated, and if a vertex's range becomes negative (ys > ye), the vertex is marked as OOS accordingly.  Hopefully, this can be done in O(N) time and hence the total runtime is O(NxN).

Am I going in the right direction?  Actually by spelling it out it already helps a bit :D


texts: Name the graph class: Disjoint union of a clique and an independent set

texts:
Let $G$ be a graph which is the disjoint union of a clique and an independent set, i.e.
$$G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} .$$

The graph class of all such graphs is characterized by the forbidden induced subgraphs set $\mathcal{H} = \{2K_2, P_3\}$ and is thus the intersection of a cluster graph and a split (or threshold) graph.

Does this (very simple) graph class have a name?  I was unable to find the graph class on ISGCI, and the papers I know on the topic (e.g. Editing Simple Graphs and On the clique editing problem) do not refer to the class by a name.

Here is a figure of such a graph:


texts: Logarithmic levels of the polynomial hierarchy (below PSPACE)

texts:
We generally define $PH = \cup_i\Sigma_i^p$ (or various equivalent forms.)  In the same notation we can also define $PSPACE = \cup_c\Sigma_{n^c}^p$--that is, like the polynomial hierarchy, but with a polynomial number of alternations between $\exists$ and $\forall$ quantifiers.

I have never seen, after looking around quite a bit, anyone define a class with more than a constant number of alternations but less than polynomial, say $\Sigma_{\log n}^p$ or even $\Sigma_{(\log n)^c}^i$.  Given how many tiny differences in computational power get exhaustively studied, this confuses me. Is this a named or studied class? If not, is there a good reason why (does it reduce trivially to something else?)

While this may seem arbitrary, I think it's a natural class to consider, in particular if we look at circuit formulations: $PH$ is precisely the class of (uniform) constant-depth, exponential sized, unlimited-fanin circuits, and $PSPACE$ the class of the same circuits of polynomial depth; it seems very natural to consider logarithmic (or polylogarithmic) depth circuits.


texts: What is the best upper bound known for the complexity of computing an optimal prefix free code in the RAM model?

texts:
In the algebraic decision tree, the result is clear: Elmasry and Belal (Verification Of Minimum Redundancy Prefix Codes)'s lower bound shows that the worst case complexity of computing an optimal prefix free code over all possible sequences of $\sigma$ frequencies is $\Theta(\sigma\lg\sigma)$.

In the $\Omega(\lg \sigma)$-word RAM model, combining Van Leeuwen's reduction to sorting (On The Construction Of Huffman Trees) with any $O(\sigma\lg\lg\sigma)$ sorting algorithm in the RAM model yields an upper bound of $O(\sigma(1+\lg\lg\sigma))$, which many people seem to assume to be optimal, probably by analogy with the situation in the algebraic decision tree model. But the only lower bound available is $\Omega(\sigma)$, the cost of reading the frequencies, leaving a gap between the two bounds.

What is the best upper bound known on the asymptotic complexity of computing an optimal prefix free code in the word RAM model? Is it $\Theta(\sigma\lg\lg\sigma)$ or $\Theta(\sigma)$? Or somewhere in between?


texts: Is there an oracle that separates $PH$ from counting classes?

texts: Is there an oracle $A$ for which $P^A =PH^A \neq CH^A = NEXP^A$ holds?


texts: What kind of computational model is the brain?

texts:
I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine).
Another thing that should be a separate question, What would be a perfect computer model be like, is our brain any close to it?
Apology for putting the ideas in a very beginner way, which ofcourse I am.


texts: Dimensionality reduction in machine learning

texts:
This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?).

Dimensionality reduction refers to a collection of techniques that input data and return a lower-dimensional version, with some distortion. PCA and Johnson-Lindenstrauss are the most common examples.

From an algorithmic perspective, the tradeoff is clear: lower dimensionality yields faster runtimes and reduced storage space, but compromises precision. I call this the dimension-distortion tradeoff.

From a statistical/information-theoretic perspective, the situation seems less clear. It is commonly believed that dimensionality reduction (PCA in particular) has a denoising effect and thus should actually improve the performance. On the other hand, dimensionality reduction does discard information, which might cause the performance to degrade. Thus, one must address the statistical question: is the information I'm discarding noise or potentially useful (and even if useful, might the benefits of lower dimension still outweigh the losses)?

There appear to be very few formal analyses of the statistical benefits of dimensionality reduction. One that I'm aware of is in our
ALT'13
 paper (with Gottlieb and Krauthgramer). The setting there is fairly general -- metric spaces.

Are there other formal analyses of the statistical benefits of dimensionality reduction? Perhaps other tradeoffs besides those mentioned above?


texts: Minimizing entropy plus a modular function

texts:
I have a question about whether there are faster algorithms for specific submodular minimization problems.

In particular, I am trying to find a fast algorithm for minimizing the following set function

$$f(S) = - [\sum_{i \in S} \alpha_i \log(\alpha_i) + (1-\sum_{i \in S} \alpha_i) \log(1-\sum_{i \in S} \alpha_i)] + \sum_{i \in S} w_i$$

where $S \subset \{1,...,n\}$, $\{\alpha_i\}_{i=1}^N$ is a vector of positive numbers that add up to 1, and $w_i$ is a set of (possibly negative) weights.

The first term in the function is a submodular function of $S$. The second term is a modular function of $S$. I know there exist algorithms (Fujishige-Wolfe) to minimize a general submodular function. Are there known algorithms to quickly minimize the sum of the entropy of a set and a modular function?


texts:
The containment $NC^1 \subseteq DSPACE[\log{n}]$ is simple and well-known (assuming a reasonable notion of uniformity for $NC^1$) and follows by:

start with an $O(\log{n})$-depth polynomial sized Boolean circuit of fan-in $2$ over $\{\vee, \wedge,\neg\}$
convert it to a formula (i.e. a circuit where all gates have fan-out bounded by 1) with a polynomial blowup in size and maintaining the depth,
run a stack algorithm with an $O(\log{n})$ depth stack with entries which are bits indicating the values of gates that have been evaluated along a path from current node to the output node

Thus the space used is logarithmic in the input completing the proof. Notice, that the entries are single bits because we didn't explicitly need to store the name of the gates along with the value since the circuit is a formula (just storing the name of the current gate suffices since tracing back its ancestor chain and thus the name of the gates whose values we have in the stack, is easy).

In trying to generalize this directly to $NC^i$ circuits ($i > 1$) the second step above does not seem possible (unless the $NC$ hierarchy collapses to $NC^1$). So in order to perform the simulation it seems necessary to remember the name of the gates along the ancestor chain. Notice that instead we could also remember $\log{f}$ bits where $f$ is an upper bound on the fan-out of a gate since this would also uniquely identify the chain of nodes from which the current node is descended from. This impli $NC^i \subseteq DSPACE[\log^{i+1}{n}]$ since the trivial upper bound on $f$ is polynomial.

My question is can we bound $f$ by a constant or through some other means show that $NC^i \subseteq DSPACE[\log^i{n}]$. This answer seems to indicate that this is indeed the case. I am interested in knowing the reference and/or the proof.


texts: Complexity of computing the simplicial width of a graph

texts:
Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:

For every edge $\{v_1,v_2\} \in E$, there exists a node $n$ of $T$ such that $v_1,v_2 \in \lambda(n)$.
For every vertex $v \in V$, the set $\{n \in T \mid v \in \lambda(n)\}$ forms a connected subtree of $T$.

For my purposes (namely, showing the tractability of model-checking for a particular logical fragment), and following my earlier question, I am interested in a restricted kind of tree decompositions, that satisfies an additional condition. I call a simplicial decomposition a tree decomposition $(T,\lambda)$ of $G$ that respects the following additional property:

For every two adjacent nodes $n_1$ and $n_2$ of the tree decomposition $T$, the interface $\lambda(n_1) \cap \lambda(n_2)$ forms a clique in $G$. In other words, for every pair of distinct elements $a,b$ occurring both in $n_1$ and $n_2$, we must have $\{a, b\} \in E$.

As usual, the width of a simplicial decomposition is $max_{n \in T}|\lambda(n)|-1$ and the simplicial width of $G$ is the minimal width of a simplicial decomposition.
Note that, of course, the simplicial width of $G$ is necessarily greater than its treewidth in the usual sense.

My question is to know whether the complexity of the following two problems is known:

computing the simplicial width together with a simplicial decomposition, i.e., given as input an undirected graph $G$, compute the simplicial width $w$ of $G$ and a simplicial decomposition of width $w$;
computing, for a fixed width, a simplicial decomposition of that width, i.e., for a fixed constant $k \in \mathbb{N}$, given as input an undirected graph $G$, computing a simplicial decomposition of width $\leq k$ if one exists, and outputting "no" otherwise.

For the usual notion of treewidth, the known complexities are the following (but they don't give bound for simplicial width):

computing the treewidth of an input graph (even without a decomposition) is NP-complete (open access link);
for any fixed $k \in \mathbb{N}$, computing a tree decomposition of width $\leq k$ can be done in linear time (open access link).

The name of simplicial decomposition is introduced in "Simplicial decompositions of graphs: a survey of applications", Reinhard Diestel, Discrete Mathematics 75 (1-3): 121-144 1989 and is the same as that of "decomposition by clique separators" in "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985. However, it seems that the notion of simplicial width is not studied here. There is a similar notion of clique minimal separator decomposition for which a quadratic bound is known (here and here) but it doesn't seem to be exactly the same problem (I think it minimizes the size of the separators between bags, not the size of the bags).


texts: How much variation is allowed before an algorithm is no longer a quicksort?

texts:
Possible Duplicate:
  When are two algorithms said to be “similar”?

Generic Overview of promblem:
I read somewhere once that a quicksort could be done without recursion in O(1) space overhead.   I thought about it for a while, and then coded a version of quicksort that uses O(1)-space overhead (eg: in-place).  However, since it lacks a lot of the metainformation that quicksort normally has available (beginning and ending of each chunk to recurse down), I had to add a pre-step to "format" the data a specific way so that the rest of the quicksort can correctly determine where each chunk begins and ends.  When discussing this algorithm in StackOverflow chat, R.Martinho speculated that this is no longer a quicksort due to the requirement of the prestep.

Overview of Algorithm:
The general idea is that for each chunk of data, the algorithm picks a pivot P from the chunk (the first in my case), and partitions the data on P into two chunks: data less than P and data greater than P.  It then puts the data in the order of [P][less than P][Greater than P]. (So that it can determine where the partitions begin and end without metadata.)  On the next iteration it can scan until it finds the first two elements out of order, which will be P and one element less than P, and scan until it finds an element greater than P.  It then moves P to the end of the chunk, and performs the algorithm on the chunk of data less than P.  Other than the temporary relocation of P, this is basically how quicksort works.

Deviation of Algorithm from Quicksort:
Since the algorithm needs the data to be in a series of "chunks" of [partition][data between this partition and the previous partition], we have to format the data down the right side until we find the maximum element to get it into this series of chunks, before the rest of the algorithm can run.

This algorithm is quite strange, and I am terrible at explanations, but as proof of concept, here's the a link to my C++ code with a naive quicksort, my inplace quicksort, and stdsort: http://ideone.com/4iCSo  (I acknowledge there's still a lot of optimizing that could be done, and that this algorithm is so slow it is almost completely useless in general)  The meat of the question is: is this algorithm still a quicksort?

I'm not clear on the scope of this site, this question might be better suited to https://cs.stackexchange.com/ or https://stackoverflow.com/.


texts: Stochastic gradient methods and risk of neural nets

texts:
Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv.org/abs/1811.04918 https://arxiv.org/abs/1811.03962, https://arxiv.org/abs/1810.12065, https://arxiv.org/pdf/1810.02054.pdf, https://arxiv.org/abs/1705.04591 and dozens more!

Is the focus on stochastic gradient based methods for this question purely motivated by the fact that this is pretty much the only thing used in practice?

Or is there a fundamental/complexity-theoretic reason why there cant be an algorithm (or its improbably hard to find an algorithm) that does not use stochastic gradients (is maybe deterministic!) and yet minimizes the risk of neural nets as fast as one can using SGD-like methods?


texts: How would proof of the Lindelöf hypothesis improve our understanding of computational complexity classes?

texts:
A recent press release from the Viterbi School of Engineering at USC discussed the proof of the Lindelöf hypothesis by Athanassios Fokas, a visiting professor from the Department of Applied Mathematics and Theoretical Physics at the University of Cambridge.

In the press release, it is noted that the proof has implications for computational complexity theory and quantum computing, but no real details are provided. I've skimmed the paper on arXiv.org, but I don't believe such implications are noted and (unfortunately) mathematical proofs are not my area of expertise.

So, as stated, my question is: How would a proof of the Lindelöf hypothesis improve our understanding of computational complexity classes? I'm especially interested in any refinements that relate to quantum computing (assuming they do in fact exist).


texts: Lookup complexity in augmented interval tree

texts:
If we consider the following problem:
Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (Interval tree). At some point in time later, we get a point,
and are asked to return all intervals covering that point.

What is the complexity of the above lookup operation?

PS : This is not a homework question, but was an interview question.