texts: Is there significance to the ratio of the time it takes to locate a problem's solution over the time it takes to verify the solution?

texts: I believe I have found a problem, the solution to which can be verified in 0 time (the solution can only be located in non-zero time, however).  As a result, the ratio of the time required to locate a solution to the problem over the time required to verify its solution is infinite.  I was wondering if this ratio generally has significance in computer science.


texts:
In our CS class, we have a question about the computational power of PDA's (Push Down Automaton).  A 0-PDA (PDA with no stacks) is equivalent to an NFA (Non-deteministic Finite Automaton), while a 1-PDA (the standard PDA) is equivalent to a CFG (Context Free Grammar).

However, a 2-PDA (PDA with 2 stacks) is more powerful (recognises more languages) than a 1-PDA, because it is not limited to pushing and popping on 1 stack only, but can also use the second stack.

The problem that I have is that I don't know how to prove the greater power of the 2-PDA.  My first thought was that a 2-PDA would be equivalent to a Turing Machine, but then I realised that it still wouldn't quite provide arbitrary access to the stack.

How would I go about proving that a 2-PDA is more powerful than a 1-PDA?

(Could someone with enough rep please tag this as homeworkpda - thanks)


texts: Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

texts:
I recently came across a strange concept and was wondering if this was a known / named concept in the realm of CS.

The concept is that you evaluate some computation or logical circuit that takes in N number of binary inputs and gives an output. (and if doing multiple of these in parallel it could then be N inputs to M outputs)

You can then change your mind after the fact about the values of the binary inputs you want the algorithm to have evaluated and essentially re-interpret the result of the original equation to get the answer for those different inputs.

The benefit here would be that if there was some complex and lengthy computation, that you could do it once, and then just re-interpret the result to get the answer of that same algorithm for different inputs.

It sounds strange I know, but are there any existing methods for this, or terminology at least?

Example:

As an example let's say you calculated a function $f(x) = x * 8$ for $x=5$ in a specific way that gave you a resulting bit string.  When an operation was done on the bit string, which was a function of the inputs (say, XOR against a number which was the function of the inputs for example), that the value came out to be 40.

But then, you say "OK but what would it be for $f(6)$?".  Since 6 is different than 5, the XOR constant changes, but you can use that new XOR constant against the result you already got from the previous calculations, to get the new correct answer of 48.

The decoding process is the same regardless of the algorithm/function being evaluated.  It is a function of the inputs, and has nothing to do with the details of the function itself (so isn't iterative computation).

it almost seems a little related to a karnaugh map, in that you get something boiled down to the results of the algorithm, no matter how complex the steps were to get to that result originally.


texts: Check whether a point is a vertex of Minkowski sum of polytopes

texts:
Given $n$ polytopes

$$\begin{align*}
P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\
P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq b_2\}\\
\vdots\\
P_n&=\{(f^n_1(\vec{x}_2), \cdots, f^n_m(\vec{x}_2))\mid A_n\vec{x}_n\leq b_n\}\\
\end{align*}$$
where $f$'s are affine mappings. Namely, they are of the form $\vec{c}\cdot \vec{x} +d$. (We note that each $P_i$ is a polytope because it is an affine projection of the polytope $A_i\vec{x}_i\leq b_i$.)

We assume that any $\vec{x}_i$ and $\vec{x}_j$ are disjoint.

We can form the Minkowski sum of $P_i$'s, i.e., $P=\sum_{i=1}^n P_i$.

Given $n$ points $\vec{y}_1, \cdots, \vec{y}_n$, decide whether for all $1\leq i\leq n$
$\vec{y}_i$ is a vertex of $P_i$ and $\sum_{i=1}^n \vec{y}_i$ is a vertex of $P$?

The question is inspired by the recent question. I am particularly interested in the complexity.


texts: Approximation Ratio of Local search for $k-$center problem

texts:
In the $k-$center problem, you're given $V$ points in Eucledian space, and you're asked to get a subset $C\subset V, |C|=k$ such that $\max _{v\in V}d(v, Closest-Center(C,v))$ is minimized.

Now I am aware of the greedy $2-$Approximation where you start with a random center, $C=\{c_1\}$. Then at each step, add the point furthest from $C$ iteratively until $|C|=k$

However, my question is about the local search approach. Namely, start with a set of random $k$ centers $C=\{c_1, ..., c_k\}$, then at each step, for every $(c_i, v), \forall v\in V-C, \forall c_i\in C$, check if $C-\{c_i\}+\{v\}$ improves the cost. There are $O(nk)$ such pairs, and it takes $O(n)$ time for each pair to compute it's cost for a total time of $O(n^2k)$ per iteration. Repeat this until your $k$ centers don't change after $I$ iterations (Where $I$ is trivially $O(n^k)$ ).

My question is, once the algorithm terminates, does the local search guarantee any approcimation ratio on the maximum distance? Is there any literature on this? I read in a paper that in the $k-$median problem, this approach would give a $5-$approximation.


texts:
I am doing some literature review on Graph isomorphism problem. Most of papers which I am reading are written by E.M Luks and Laszlo Babai.
These papers uses the high level knowledge of group theory and complexity theory.
As I am new to this field many of the things are not clear to me.

Can some one suggest me a way to learn ideas and techniques which are presented in these papers so that I can come up with some other ideas.

Thank you so much


texts: Have imperative programs been defined like this?

texts:
Possibly improper definition $\;$ An imperative program is a labeled directed graph, with every vertices labeled by a command and every edge labeled by a predicate.

Denote an edge labeled by predicate $p$ from $x$ to $y$ by $(x, p, y)$,

Two consecutive steps are expressed as $(x, \top, y)$. "Goto" is also expressed in this way.
A binary branch is expressed as $\{(x, p, y), (x, \neg p, z)\}$.

As can be easily noticed, "command" is not defined. I do not know what that should be, but it should be as weak as possible.

Have imperative programs been defined like that?

I also think a mathematical definition could help me go further understanding the space of imperative programs.


texts:
I am a bit rusty on optimization algorithms and need an advice. This is my problem:

I have n images (with width and height) that must be printed on a planar surface at a defined point (x,y).

Then I have k printers that can move along y but are fixed on x. The planar surface run under them in only one direction.
The difference with a normal printer is that once a one starts to print an image it must finish it before being able to move again on the y axis to print something else or to make space for its neighbor printer.

These printers have dimensions as well and are mounted on racks. I can have maximum 2 racks and each rack can mount up to 2 printers.
Printers on the same rack cannot overlap.

The best solution, if exists, is a feasible one (all prints can be printed) that minimize the travel of the printers.

I made a naive algorithm that generate all the combinations and test them all, looking for the best. It works, but it is exponential both in time and RAM occupancy.

The RAM usage is due to the generation of the list of all the possible combinations, I store them into a matrix of (k^n x n) elements where each element h=(i,j) indicate the index of the printer that will print the j print.
In the case of 12 images and 4 printers I have a matrix of 4^12 x 12 elements

Can you advice me on the best approach that I should follow to get an algorithm that find a sub-optimal feasible solution in less time and using less RAM?

Thanks in advance


texts: Is there a name for "physical things out of which one can build a Turing machine"?

texts:
One of the amazing things about computer science is that the physical implementation is in some sense "irrelevant".
People have successfully built computers out of several different substrates -- relays, vacuum tubes, discrete transistors, etc.
People may soon succeed in building Turing-complete computers out of non-linear optical materials, various biomolecules, and a few other substrates.
In principle, it seems possible to build a billiard-ball computer.

However, the physical substrate is not completely irrelevant.
People have found that certain sets of components -- in particular,
diode-resistor logic --
are "incomplete": no matter how many of them you connect to a power supply and to each other, there are certain very simple things that it cannot do.
(The diode-resistor logic can implement AND, OR, but fails to implement NOT).
Also, certain ways of connecting components -- in particular, single-layer perceptrons -- are "incomplete": there are certain very simple things that they cannot do.
(A single-layer perceptron can implement AND, OR, NOT, but fails to implement XOR).

Is there a less-awkward phrase for "physical things out of which one can build a Turing machine"?
Or for the opposite, "physical things that, no matter how many of them one has, cannot form a Turing machine"?

For a while I used the phrase "functionally complete set" or "universal set of gates" -- or, when speaking to mathematicians, "physical things that can implement a functionally complete set" -- but I've been told that isn't quite correct.
Some sets of components can implement a functionally complete set;
and yet it is not possible to build a Turing-complete machine entirely out of these components.
For example, light bulbs and manually-operated 4-way light switches can implement a functionally complete set (AND, OR, NOT, XOR, etc.);
and yet it is not possible to build a Turing-complete machine entirely out of light switches and light bulbs, since the (electrical or optical) output of one cannot be fed into the (mechanically rotating) input of the next.

related: Is there an official name for a notion of "reusably universal"? and Is there a name for “chips out of which one can build a CPU”?


texts: Satisfiability of circuits with infinite input

texts:
As we all know, satisfiability of Boolean circuits is NP-complete.

I am wondering if there are any studies of circuits with infinite inputs?
That is, suppose the input is from the set $\{0,1\}^\omega$ (countable sequences of $0,1$).

Another model I am interested in is arithmetic circuits, specifically with the gates $\min\{x,y\},1-x$, and $\frac12 x+\frac12 y$, with inputs in $[0,1]^\omega$.

The first observation is that if the circuits are finite with bounded fan-in, then this is equivalent to the model with finite inputs. So we must consider infinite circuits, or at least infinite fan-in.

Clearly, the satisfiability problem in general will be undecidable, since we can encode the behavior of a TM with an infinite circuit.

However, there are circuit classes for which the problem is interesting. For example, we can require our gates to represent the temporal operators of $LTL$ (where we have a finite depth circuit with infinite fan-in), which makes the satisfiability problem PSPACE complete

Are there other known models with interesting results?


texts:
I read about the strong exponential time hypothesis, which states (as far as I understand) that SAT problem cannot be solved in running time $O(2^{\epsilon n})$ for any $\epsilon < 1$, where $n$ is the number of variables in the formula.

However, for other NPC problems, it is known that such algorithms exist (for example, Hamiltonian cycle).

My question is as follows: it is possible to create a polynomial reduction from Hamiltonian cycle to SAT - proving that Hamiltonian cycle is "harder" than SAT (this is how we were proven that Hamiltonian cycle is NPC). This allegedly imply that when given a SAT instance, I can use the reduction and the Hamiltonian cycle algorithm to achieve exponential algorithm with smaller exponent, in contrast to SETH. Clearly I miss something here.

Regardless of this question:  are there any current research efforts towards progress in this problem?


texts: Example of non-disk bounding planarly nested sequences of cycles

texts:
I am trying to find an example for the Theorem 5.1 of the paper "Combinatorial Local Planarity and the Width of Graph Embeddings" that can be found at http://www.fmf.uni-lj.si/~mohar/Reprints/1992/BM91_CJM44_Mohar_GraphEmbeddings.pdf. Given G(V,E) minimally embeddable on an orientable surface $\Sigma_g$ of genus $g \geq 2$. Suppose that $C_1,C_2,\ldots, C_k$ be a planarly nested sequence (defined below) and $k\leq g$. I am trying to construct an example for graphs of genus $g \geq 2$ and $ k = g$ in which none of $C_1,C_2,\ldots, C_k$ bounds disks.

Definition: A sequence of disjoint cycles $C_1,C_2, \ldots, C_k$ is planarly nested if each cycle $C_i (1 \leq i \leq k)$ has a relative $C_i$ component $H_i$ such that $H_1 \supset H_2 \supset \ldots \supset H_k$ and the graph obtained from $G$ by contracting to a single vertex all edges in the relative component $H_k$, except it feet, is planar.

A relative $C$-component for a cycle $C$ is an edge $e \in E(G)\backslash E(C)$ with both endpoint in $C$, or a connected component of $V(G) - V(C)$ together with all edges between this component and $C$. Edge of a $C$-component $R$ having an endpoint in $C$ is a foot of $R$.

Here is an example of two relatives $C$-component $H_1$ and $H_2$ of G.


texts:
Assume we are given an arbitrary undirected graph $G = (V, E)$ where $|V| = n$. We are also given real numbers $x_e \in [0, 1]$ for each $e \in E$. These numbers satisfy the following constraint:

\begin{equation}
\sum_{e \in E(N, \bar N)} x_e \leq c
\end{equation}

for each neighborhood $N$, and for some fixed constant $c$ ($c$ may be given as part of the input. The crucial point is that it independent of $n$). A "neighborhood" is a $k$-hop neighborhood of any vertex, for any $k$. A $k$-hop neighborhood of a vertex $v$ is the set of all vertices that can be reached from $v$ using $k$ or less edges.
$E(A, B)$ denotes the edges between sets $A$ and $B$, $E(N, \bar N)$ is thus the set of edges crossing the cut defined by $N$.

I am interested in (randomized?) rounding $x_e$ that will give me a binary solution that is of approximately the same size and satisfies the constraints approximately.

In other words, how can I round $x_e$ to binary $x'_e$ such that $\sum_{e \in E} x'_e = \Omega(\sum_{e\in E} x_e)$ and

\begin{equation}
\sum_{e \in E(N, \bar N)} x'_e \leq O(c)
\end{equation}
for each neighborhood $N$.

Randomized rounding seems to give only $\sum_{e \in E(N, \bar N)} x'_e \leq O(\log n)$ since we need to union bound over polynomially many neighborhoods.


texts: Lower bound on probability of getting two close points in a sample of $n$ points

texts:
Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| <B]>p$ for some $B,p$, where $|u-v|$ is the L1 distance of the vectors.

$S\subseteq D$ is obtained by sampling $n$ elements uniformly from $D$. Give a lower bound, as tight as possible, on $P\equiv Pr_{S\leftarrow U_D}[\exists u,v\in S:|u-v|<B]$. The bound can depend on the $k$, which should be thought of as a small constant, i.e., $k<<|D|$.

Specifically, the bound has to be tighter than the following trivial one: $P\ge 1-(1-p)^{n/2}$. This is obtained by dividing the $n$ points to $n/2$ pairs that are sampled independently. Then, $1-P$, the probability that $\forall u,v\in S:|u-v|\ge B$, is at least as low as the probability that none of these pairs will have distance lower than $B$. Since these events are independent, we get $1-P\le (1-p)^{n/2}\Rightarrow P\ge 1-(1-p)^{n/2}$.

Intuitively, since $S$ has $\frac{n^2}{2}=O(n^2)$ pairs of points, each corresponding with a possible "closeness" event, we would expect to get something like $P\ge 1-(1-p)^{O(n^2)}$, following a similar calculation to the above. However, without event independence this not easy to show (and possibly not true).

We are thus looking for a bound $C$ s.t. $P\ge C, C=1-(1-p)^{\omega (n)}$. Or to show that it does not exist. $C$ can be a function of the constant $k$.


texts: Complexity of counting integer roots of multivariate polynomials in a polyhedron?

texts: Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials  in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total degree fixed and we only look at integer roots in a bounded polyhedron?


texts: When does adding edges decrease the cover time of a graph?

texts:
When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$.  However, this is not the case.  The path graph $P_n$ has cover time $C(P_n) = \Theta(n^2)$ while the ($\frac{n}{2}$, $\frac{n}{2}$)-lollipop graph $L_{\frac{n}{2}, \frac{n}{2}}$ has cover time $C(L_{\frac{n}{2}, \frac{n}{2}}) = \Theta(n^3)$.  Eventually adding edges does decrease the cover time because the complete graph $K_n$ has cover time $C(K_n) = \Theta(n \log n)$ by analogy to the coupon collector problem.
Under what assumptions though would the supposed intuition hold true?  Specifically, what about vertex transitivity?

Let $G$ be a vertex-transitive graph with $n$ vertices.  Consider any vertex-transitive graph $G^+$ obtained from $G$ by adding edges (i.e. both $G$ and $G^+$ are vertex transitive and $G$ is a spanning subgraph of $G^+$).
Is it the case that $C(G^+) \le C(G)$?


texts: Task Multithreading analysis for a Divide and Conquer algorithm

texts:
Suppose an algorithm that receive an input array of $n$ elements and it performs a task over each element. All tasks are independent and take $O(k)$ each (being $k$ a variable). Since all tasks are independent this is a fully parallelizable problem.

I have a basic algorithm that uses the Divide and Conquer technique. It receive the input array $A$ and if $|A| > 1$ then it spawn a new thread to process the first half of $A$, and recursively call itself to process the second half. This recursions stops when the function is called with a single element, in which case it runs a series of steps that takes $O(k)$.

I´m using the Dynamic Multithreading model (Introduction to Algorithms, chapter 27) to analyze this algorithm. So, I have an execution graph with n "leafs", representing the basic cases ($|A| = 1$), and it needs $O(n)$ "internal nodes" to divide the work until it reaches the leafs. Given that the longest path has length $O(\log n)$ with a constant cost for each internal node, then the total cost will be $T_\infty = O(\log (n) + k)$ (which is the span). I also can get other measures like the total work $T_1 = O(n + kn)$, and the parallelism $\frac{T_1}{T_\infty} = \frac{n + nk}{k + \log n}$.

Another performance measure of interest is the speedup, which is defined as $\frac{T_1}{T_p}$ (where p is the number of processors used to compute $T_p$).

Finally my question is how do I get $T_p$ (analytically) so I can calculate the speedup?
I cannot simply divide $T_1/p$ since in the first levels of the graph/tree I won't be using all the processors.

Is there any more elegant expression for this than simply dividing the height of the tree before and after $\log p$?


texts: Is the convex combination of two potential games a potential game?

texts:
My question: is the set of potential games closed under convex combinations?

An n player game with action set $A = A_1 \times \ldots \times A_n$ and payoff functions $u_i$ is called an exact potential game if there exists a potential function $\Phi$ such that:
$$\forall_{a\in A} \forall_{a_{i},b_{i}\in A_{i}} \Phi(b_{i},a_{-i})-\Phi(a_{i},a_{-i}) = u_{i}(b_{i},a_{-i})-u_{i}(a_{i},a_{-i})$$

A game is a general (ordinal) potential game if there exists a potential function $\Phi$ such that:
$$\forall_{a\in A} \forall_{a_{i},b_{i}\in A_{i}} sgn(\Phi(b_{i},a_{-i})-\Phi(a_{i},a_{-i})) = sgn(u_{i}(b_{i},a_{-i})-u_{i}(a_{i},a_{-i}))$$

Say that we have two games on the same action set, with utility functions $u_i$ and $u'_i$ respectively, for each player $i$. For any $0 \leq p \leq 1$, there is a convex combination of these two games, again on the same action set, where the utility function for each player $i$ is now $u^p_i(\cdot) = (1-p)u_i(\cdot) + pu'_i(\cdot)$.

Clearly, the convex combination of two exact potential games is also an exact potential game: just take the same convex combination of the two potential functions.

But is it possible to have two (general) potential games such that their convex combination is not a potential game?


texts: How to Create Mission Critical Software?

texts:
I am self learning formal methods. I heard that formal methods is used (and usually only used) to create mission critical software (such as nuclear reactor controller, aircraft flight controller, space probe controller). That's why I am interested to learn it :p

However, after learning formal methods (especially LTL, CTL and their siblings), I feel that they can only be used to verify the correctness of the specification (safety, liveness, fairness, etc).

But then how to verify that the software (not only the specification) is indeed correct?

Disclaimer: I am a 90% idiot when it comes to theoretical computer science. So please be merciful while answering.


texts: Can relativization results be used to prove sentences formally independent?

texts:
Is it possible to demonstrate that a sentence must be formally independent based on the fact that it is non-relativizing?  In other words, are there examples of sentences in computability/complexity theory where it can be demonstrated both a)  that all proofs that resolve the question of whether or not two classes are equal must relativize, and b)  that there are no relativizing proofs that can be used in such a resolution?

I think that results satisfying part b would be easier to come by.  Another way to ask this question is:  Has there ever been a sentence in computability or complexity theory where it can be demonstrated that the equality or inequality must be established through the use of (and only through the use of) relativizing techniques?  An example of this would be interesting to me.

Thanks; an answer to either version of this question would be very interesting to me.

-Philip


texts: How to translate the axiom schema of induction by Curry-Howard?

texts:
I'm trying to understand the Curry-Howard correspondence. I am comfortable with it for propositional logic, but get confused when $\forall, \exists$ quantifiers come in the picture.

The axiom schema of induction (in second-order logic) is  $\forall P. \left[(P(0) \implies \forall k\in \mathbb N. (P(k)\implies P(k+1)))\implies \forall n\in \mathbb N. P(n)\right]$.

To my understanding, via Curry-Howard every statement gets translated to a type. Proving a statement means showing that the type is inhabited. For example, +, = are dependent types taking two parameters of type nat; every $\forall k\in A$ gets translated into a dependent product $\prod_{k::A}$. So the axiom schema should become something like
$
\left[\prod_{P::?} \left((P\, 0) \rightarrow \left(\prod_{k::\mathbb N} (P \, k)\rightarrow P \, (+\, k\, 1) \right)\right)\right]\rightarrow \prod_{n::\mathbb N}(P \,n)
$

A difficulty arises when translating $\forall P$: what is the type of $P$? The problem is that, in order for the above to make sense, $(P\, k)$ is supposed to be a type for all $k::\mathbb N$ (so we are allowed to say $(P\, 0) \rightarrow \cdots$, for instance). So $P$ seems to me like a (dependent) type constructor taking a nat as parameter. But then we are taking a product over $P$, so we must be able to treat $P$ as an element of a type! The problem seems to boil down to, are type constructors themselves of some type? Can we write this statement without having to refer to such a type? Perhaps higher-order logic translates to higher-order type theory, but I do not know the latter. References would also be appreciated.


texts: Fastest known algorithm for finding simple paths through given set of vertices

texts:
For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing
all elements of $S$. What if we require the path to be as short as possible ?


texts: Mixing properties of random walks on graphs

texts:
I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs.

One of the main ideas of the paper is that random walks on graphs can be used to find sets with small isoperimetric ratio.  The principle seems to be as follows: if a vertex $v$ is well connected to a neighborhood of a vertex $u$, then a random walk starting at $u$ will visit $v$ more often than you would expect from looking at the degree of $v$ alone.

This principle is made precise and quantitative via various mixing estimates in the paper.  I want to ask about one specific mixing result (Lemma 4 of secton 6), though my question may apply to the others as well.  First, the notation:

$S$ is a set of vertices in an undirected graph $G$
$W$ is the lazy random walk matrix of $G$: $W = \frac{1}{2}(I + D^{-1}A)$ where $D$ is the degree matrix and $A$ is the adjacency matrix
$pr_u$ is a personalized PageRank vector associated to a vertex $u$ with parameter $c$; it is the unique solution to the equation
$$pr_u = c \chi_u + (1-c)pr_u W$$
where $\chi_u$ is the characteristic function of $u$
$\pi$ is the function defined on the vertex set of $G$ which assigns to each vertex $v$ the degree of $v$ divided by $vol(G)$.
$\gamma_u$ is the smallest isoperimetric ratio obtained by a sweep over $pr_u$ (see section 4 of the paper)

The mixing result is:
$$\left| \frac{pr_u(S) - \pi(S)}{1 - \pi(S)} \right| \leq 1 - (1-c)^k + \sqrt{\frac{vol(S)}{d_u}}\left(1 - \frac{\gamma_u^2}{8}\right)(1-c)^k$$

One of the key steps in the proof of this mixing result is the estimate:
$$f(x) \leq c + (1-c)fW(x)$$
where $f = \frac{pr_u - \pi}{1 - \pi}$ and $0 \leq x \leq vol(G)/2$ (see section 4 for the definition).  However, this estimate is not proved in the paper, and I have serious doubts that it is true (which I can share if desired).

  First question: Can anyone prove this estimate, or confirm that it is incorrect?

However, I believe I can prove the estimate for $f = pr_u$.  Moreover, I think that this is enough to prove the mixing lemma with $pr_u(S)$ instead of $\frac{pr_u(S) - \pi(S)}{1 - \pi(S)}$ on the left-hand side, and this in turn is enough to prove Theorem 4 in section 6 (with a different constant, though I think the constant in the paper is wrong either way).  But I am suspicious of this because it seems inconsistent in spirit with a variety of other results (including two other mixing results in the paper).

  Second question: Can anyone explain why $\frac{pr_u - \pi}{1 - \pi}$ instead of just $pr_u$ in the statement of Lemma 4 is necessary (either to prove Lemma 4 or Theorem 3)?

This question is already very long, so I will keep this edit brief.  In an effort to understand what is going on, I looked at the corresponding results for random walks rather than PageRank vectors (Lemma 3 and Theorem 2 in the paper above).  Again, everything seems to work out without the need for the distribution $\pi$.  Lemma 3 is the estimate:
$$|f_k(S)| \leq \sqrt{\frac{vol(S)}{d_u}} \left(1-\frac{\beta_k^2}{8}\right)^k$$
where $f_k = \chi_u W^k - \pi$.

Again, let us replace $f_k$ with simply $\chi_u W^k$.  If $u \in S$ then $f_0(S) = 1$ and the right-hand side is $\sqrt{\frac{vol(S)}{d_u}} \geq 1$.  If $u \notin S$ then $f_0(S) = 0$ and the right-hand side is nonnegative.  The inductive step only uses the fact that $f_{k+1} = f_k W$, which is still true.  As far as I can tell the proof of Theorem 2 still works exactly the same way without $\pi$ (as long as Lemma 3 is true), so I again don't see why it is there.


texts: Forbidden subgraph characterisation of interval graphs

texts:
A graph is an interval graph iff it is chordal and asteroidal triple free.
An interval graph is proper interval graph iff it is $K_{1,3}$ free.

However i googled intensely to find a minimal set of forbidden subgraphs for proper interval graphs,but in vain.

My question is : What are the minimal set of forbidden subgraphs for proper interval graphs ?
Any link to journal/paper is welcome.


texts: In communication complexity one important object is the combinatorial retangle. Given a $0-1$ square matrix $M$, do their exist permutations $\sigma,\pi$ such that $\sigma M\pi$ consists of only geometric rectangles? That is all the combinatorial rectangles are geometrically connected?


texts: Mastery-based grading for Theory of Computation

texts:
I would be interested to learn of anyone's experience using mastery-based (or "mastery-level") grading in a Theory of Computation course.
Usually this requires—at a minimum— a detailed taxonomy of competencies, and what it means to
demonstrate mastery of each competency.


texts: Could any one enumerate some applications of enumerative combinatorics and Ramsey theory in TCS?

texts:
The combinatorics, needless to say, is very closely related to TCS. But I found it hard to find the applications of enumerative combinatorics or Ramsey theory.

Or rather than being applied to TCS, the enumerative combinatorics or Ramsey theory is related to TCS because we use TCS techs and algorithms to tackle their problems.

I dont know very deep theory works, so please treat it easy.


texts:
Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices).

What is the best time lower bound it is known?

Another question is whether the decision version of this eigenvalue problem is known to be in $L$.


texts: Is it possible to have a 4-coloring for a non-planar graph ?

texts:
I have been working on this thread Grid $k$-coloring without monochromatic rectangles, and I am aware that the four color theorem implies that all planar graphs are four colorable.

The question is whether this is a necessary condition as well, i.e. whether having a proof that a graph is not planar implies it is not four colorable ?


texts: Is Eulerian Path (or Eulerian Cycle) definable in Monadic Second Order Logic?

texts:
Does there exist a monadic second order logic formula which is satisfied by a graph if and only if it has an Eulerian path (or Eulerian cycle).

I am looking for properties of graphs which are polynomial time testable but cannot be defined in MSO. I am more inclined to examples of properties from standard textbooks as it is meant for a CS (engineering) crowd and not a CS theory crowd.


texts: The complexity of checking whether two CNF have the same number of solutions

texts:
Given two CNF, if they have the same number of assignments to make them true, answer "Yes", otherwise answer "No".

It is easy to see it is in $P^{\#P}$, since if we know the exact numbers of solutions to these two CNF, we just campare them and answer "Yes" or "No".

What is the complexity of this problem?


texts: Claw finding using quantum walk: superposition for Szegedy's framework

texts:
Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper:
Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices of $J_F$ and $J_g$. Let $(F, G)$ be a vertex of the product of the Johnsons graphs. Two vertices in the graph product are conected if: $F$ is adjacent with $F'$ and if $G$ is adjacent with $G'$.

On page 5 the superposition created in order to apply Szegedy's framework is described as:
$|\psi_0\rangle = \frac{1}{\sqrt{\binom{N}{l}\binom{M}{l}l (N-l) m(M-m)}} \otimes |F, G, L_{F, G} \rangle | F', G', L_{F', G'} \rangle$

Taken the nominator of the Amplitude: That would be all possibilities to connect any two vertices in the graph $J_f \times J_g$. The algorithm processes connected vertices in each ''step''.

Question:
Is the above assumption of the nominator coorect? If so, why is it not sufficient to create a superposition over all connected vertices in the graph $J_f \times J_g$?

I do see that on a quantum level the ''few more connected vertices'' do not have much of an impact on the running time, but does it have some kind of impact on the algorithm?


texts:
Following on from a previous question,

  what are the best current space lower bounds for SAT?

With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses a binary worktape alphabet.
A constant additive term is unavoidable since a TM can use internal states to simulate any fixed number of worktape cells.
However, I am interested in controlling the multiplicative constant that is often left implicit:
the usual setup allows arbitrary constant compression via larger alphabets so the multiplicative constant is not relevant there, but with a fixed alphabet it should be possible to take it into account.

For instance, SAT requires more than $\log\log n + c$ space; if not then this space upper bound would lead to a time upper bound of $n^{1+o(1)}$ by simulation, and thereby the combined $n^{1.801+o(1)}$ space-time lower bound for SAT would be violated (see the linked question).  It also seems possible to improve this argument to argue that SAT requires at least $\delta\log n + c$ space for some small positive $\delta$ that is something like $0.801/C$, where $C$ is the constant exponent in simulation of a space-bounded TM by a time-bounded TM.

Unfortunately $C$ is usually quite large (and certainly at least 2 in the usual simulation, where the tapes of a TM are first encoded on a single tape via a larger alphabet).  Such bounds with $\delta \ll 1$ are rather weak, and I would be especially interested in a space lower bound of $\log n + c$.
An unconditional time lower bound of $\Omega(n^d)$ steps, for some large enough constant $d > 1$, would imply such a space lower bound via simulation.  However, time lower bounds of $\Omega(n^d)$ for $d>1$ are not currently known, let alone for large $d$.

Put differently, I'm looking for something that would be a consequence of superlinear time lower bounds for SAT, but which might be possible to obtain more directly.


texts:
What algorithm can we use to find all integer roots of a polynomial $f(x)$ with integer coefficients?

I observe that Sage can find the roots within a few seconds even when all coefficients of $f(x)$ are very large.  How is it able to do that?


texts:
Suppose you are given a collection of $n$ balls in $\mathbb{R}^d$, and you want to preprocess them in such a way that you can later query them to find all spheres which contain any test point.

What efficient solutions are known for this problem?

The trivial answer is to just do a linear scan over all the spheres, which takes no preprocessing time but requires an overhead of $O(n)$ per query.

In 1D you can solve the problem using an interval tree, giving $O(\log(n) + k)$ query time with $O(n \log(n))$ preprocessing and $O(n)$ space, but it isn't clear to me that this generalizes.

I suspect there should be some sort of reduction here, since I can't seem to find any discussion of this problem in the literature which leads to me to think that it is trivial (though I am probably searching for the wrong terms).

There is a reduction to metric range searching in hyperbolic geometry with the signature $(+++ ... -)$, but I don't know how to do hyperbolic range searching efficiently (so it isn't much help).

If this question turns out to be too easy, you can also consider the situation where the set of balls is dynamic.


texts: Streaming algorithms suitable for undergrad course

texts:
I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course.

Good choices should probably satisfy the following requirements:

Solve a problem that is useful in practice or easy to motivate, or alternatively, illustrate techniques that are beautiful or useful.
Be suitable for presentation in an undergraduate algorithms course.  This means the algorithm and analysis can't be too complex.  Also they shouldn't require too much heavy probability theory to analyze (sadly, this rules out many beautiful algorithms).

What would be a good candidate?

One beautiful algorithm is the deterministic algorithm to find an element that occurs with frequency at least 50% (if any such element exists), using $O(1)$ space; or its generalization, find all items that occur with frequency at least $1/k$, using $O(k)$ space.  Are there any others that would be an excellent choice for an undergraduate course?


texts: Minimum cut on a directed graph with negative term

texts:
Suppose we are given a directed Graph $G=(V,E)$ and there is a nonnegative weight $w(u,v)$ is defined for the edge from $u$ to $v$. The task is to partition vertices to $A$ and $B$ (partition means $V = A \cup B$ and $A \cap B = \emptyset$) such that the following value is minimized:
$$\Sigma_{u \in A, v\in B} w(u,v) - \Sigma_{u \in B, v \in A} w(u,v)$$
Here the difference with the classic notion of min-cut is the presence of the negative term. Otherwise, a max-flow algorithm between a pair of vertices would have been the answer. Can this problem also be formulated in a flow framework?

Besides that, is the best way to do max-flow on all possible pair of nodes, or there is a smarter way to do it?


texts: Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

texts:
In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these $\epsilon$ moves aren't allowed, and the stack can only be modified once after each symbol read, are the resulting automata equal to power to DPDAs?

There may be something trivial I am missing with regards to using the powerset of $\Gamma$ as your new $\Gamma$, allowing you to "compress" $\epsilon$ moves into the equivalent automaton without them, similar to how you can compress $\epsilon$ moves in a DFA. Just it seems that such a conversion is not as trivial as for DFAs, and I'm not sure it's even possible.

So are the two equivalent in power? I'm just asking because everyone seems to assume that DPDAs have $\epsilon$ moves and I'm wondering why that assumption exists, since it seems like a more complex model.


texts: Optimal insertion times in insertion-only data structures beyond Bentley-Saxe

texts:
The Bentley-Saxe trick allows us to go from a static decomposable problem to a problem admitting insertions, where the insertion time is off the optimal time by a factor of $\log n$.

Is this tight ? Or alternately, is there a more restricted subclass for which you can get insertion time $P(n)/n$ (amortized or worst-case) even if $P(n) = O(n\log n)$ ? Here, $P(n)$ is the time to compute the result statically.


texts: Graph automorphism with prescribed values

texts:
Consider a graph $G$ with vertices labeled $1,...,n$ and edge weights $w_{ij}$. Recall an automorphism of G is a permutation $\sigma$ of the vertex labels such that $w_{\sigma(i),\sigma(j)}=w_{ij}$ for all $i$ and $j$.

Fix vertices $i_0$ and $i_1$. I am interested in finding approximate automorphisms of $G$ that carry $i_0$ to $i_1$. More precisely, consider the problem of finding a permutation $\sigma$ with the properties that:

$\sigma(i_0)=i_1$
$\sigma$ is an approximate automorphism in the sense that $\sum_{i<j} (w_{ij}-w_{\sigma(i),\sigma(j)})^2$ (or some similar measure) is small

Question: What is known about this problem in terms of algorithms/complexity?  I would also appreciate pointers to any appropriate literature. (Obviously there are many papers on graph automorphism problems, but I was unable to find anything on this specific problem.)


texts: Add edges to a DAG to maximize increase in number of connected vertices

texts:
Let $G$ be a Directed Acyclic Graph.

$$C(G) = \bigl|\{(u,v):u,v\in V(G),v \text{ reachable from } u\}\bigr|$$

Goal is to add $k$ edges in a DAG such that for the new $G'$, $C(G')$ is maximized.

My idea is as follows. DAG is given so, we can assume that it is bipartite graphs with $S$ called source and $T$ will be called as sinks. $(|S||T|)^{k}$ time algorithm seems working as per my calculation. A vertex is called as source if all edges it have are outgoing and a vertex is called sink if all edges it have are incoming.

What is the fastest algorithm for this problem?


texts: Constant Depth Circuit Computing Threshold Function

texts:
One of the most basic result in circuit complexity is the constnat depth cirdcuit lower bound computing PARITY function using the switching lemma.

Another popular function MAJORITY has also lower bound $exp (\Omega (n^{1/(d-1)}))$ and matching upper bound $exp (O (n^{2/(d-1)}))$.

My question is about upper bound of Threshold function which is a natural generalization of majority function.

The formal definition of the threshold function is the following one.

DEFINITION:

$THR(x_{1},...,x_{n})=
  \begin{cases}
    1 & a_{1}x_{1}+\cdots +a_{n}x_{n} \geq t \\
    0 & otherwise
  \end{cases}
$

We assume that each weight $a_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$

QUESTION1:
The depth $d$ circuit with unbounded fanin AND OR NOT gates to compute the above function has size $2^{n^{\epsilon}}$ ?

Where $\epsilon $ can depend on $d$ like $2^{n^{1/100d}}$ .

QUESTION2

Can we $\textit{relax}$ the assumption that   $a_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$ ?

For example, even if we assume that  $a_{i} \in \mathbb{R}$ is at most $2^{2^{O(n)}}$ and give the strong power of each threshold gate, does uppwer bounds  $2^{n^{\epsilon}}$  holds ?


texts: Sources for Algorithmic Evolutionary Game Theory

texts:
I use the title term in a very loose sense.

There is a significant amount of work on evolutionary game theory, including its mathematical foundations. I was recommended "Evolutionary Games and Population Dynamics" but haven't delved into it yet.

There is also a significant amount of work on algorithmic game theory, which is a popular topic on this site.

What I'd like to see is work that makes computational complexity or convergence statements about certain evolutionary dynamics.

Examples (phrased very loosely):

Given a population and an evolutionary scheme, can we give a probabilistic regret bound for the long-term population optimality (compared to the best individual produced?). This seems to relate strongly to ensembles of experts and bandit problems. What about in nonstationary settings?
Given a set of populations of different species that interact in their environment, playing pretty much any sort of multi-player game, what statements can we make about the eventual stability of their strategies or strategy distributions, given their evolutionary strategies.
In any sort of environment with many "niches" (an overbroad way of phrasing it, I understand), either in terms of direct relationship with the environment or in terms of relationships with other species, what statements can we make about how populations will distribute across these niches.
Any problem I haven't asked but should - I'm coming at this with little AGT, TCS, Genetic Algorithms, evolutionary game theory or population biology background; I'm asking my questions from an optimization/machine learning/stats point of view, which may be the wrong one or incomplete.


texts: 3 dimensional matching shortest solution NP-hard?

texts:
We have array of arbitrary number of elements - 3d vectors with positive integers components - for example

let a=[ [0,1,2], [1,0,2], [1,1,1], [1,2,0 ], [2,0,1 ], [2,1,0 ] ];

And we want to remove elements from that list, which have duplicate value on i-th index with other elements. This problem can have more than one solution:

solution with 3 elements: [0,1,2],[1,2,0],[2,0,1]
solution with 2 elements: [1,0,2],[2,1,0]

As you can see, the solution has this property that each solution element have unique value on i-th index (numbers on i-th position never duplicate) and if we add any other element from array a to that solution we loose this property.

Optimalization: from this wiki aricle I know that finding longest solution is NP-hard problem - but what about finding the shortest solution? Does exists algorithm which not use brute-force to find shortest solution (shortest 3-d matching)?

Here is interactive visualisation in javascript (works in browser, I put it also in wiki article). Here is implementation for find any solution in javascript.


texts: Does bit commitment yield oblivious transfer in the information-theoretic security model?

texts:
Suppose you have two arbitrarily powerful participants who don't trust each other. They have access to bit commitment (e.g., sealed envelopes containing data that one player can hand to the other but that can't be opened until the first player gives the second a key). Can you use this to build an oblivious transfer protocol. Is this true even if the players agree to open all the envelopes at the end to detect cheating (e.g., after the poker hand is played, everybody agrees to reveal their cards)?

I assume that you can't get oblivious transfer out of bit commitment, because oblivious transfer is cryptographically universal, and I can't find any references that say bit commitment is, but is there a proof somewhere that you can't do it?

Finally, has anybody looked at the problem if the players are quantum?


texts: Calculating a fast matrix vector product between vector of reals and a 0-1 matrix

texts:
Given:
 some vector $R=(r_1...r_l)$ - real numbers,
 and a set of distinct vectors with $0$ or $1$ coordinates
  $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\
  V_2=(c_{2,1} ... c_{2,l}),\\
   .....\\
  V_n=(c_{n,1} ... c_{n,l})\end{array}$$
  each $c_{i,j}$ are $0$ or $1$.
  $n\lt 2^l$ is some number. (For example in my case: $n=2^{10}, l=20$).

 Problem:
I need to calculate inner products $ (R, V_i) $ - how to do this in the fastest way ?
I mean how to organize calculations such that number of additions will be the smallest ?
The point is that some vectors have same subsequences of 1 and 0,
so I do not need to calculate several times such pieces.

Background: $V_i$ is fixed once and forever, "R" is coming every "millisecond".

Example:
    $V_1 = (1, 1 , 0 , 1)$
    $V_2 = (1, 1 , 1 , 1)$

Algorithm:

x = r_1+r_2+r_4
y= x+r_3

So $(R, V_1) = x$ ; $(R, V_2) = y$;  required only 3 additions, instead of naively seen $5=2+3$.


texts: maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph

texts:
Has this problem been studied before?

Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the minimum spanning tree of the subgraph induced by S. Has this problem been studied before? Is it NP-hard? Thanks a lot.


texts: The maximum number of induced cycles in a simple directed graph

texts:
Is the maximum number of induced circuits in a simple directed graph known?

I tried the family of graphs suggested by David and the number of induced cycles is seems to be exactly

$3^{n/3} + \frac{n}{3}$

*tested up to n=51 (for each n multiple of 3).


texts:
Let $B$ be the unit ball of $\mathbb{R}^d$. Suppose that $x_1,\ldots,x_n$ are vectors in $B$ with labels $y_i\in\{-1,1\}$. We say that $w\in B$ separates this labeled set with margin $\gamma$ if $y_i(w\cdot x_i)\ge\gamma$ for all $i\in[n]$.
Let $\gamma_0>0$ be the largest possible margin on a given labeled set, achieved by the vector $w_0\in B$.
Suppose now that $x_i'$ is an $\varepsilon$-perturbed version of $x_i$, namely $||x_i-x_i'||\le\varepsilon<\gamma_0^2$. The perturbed data set is still linearly separable (Theorem 13 here
https://www.jmlr.org/papers/v10/kontorovich09a.html
). Let $\gamma_1$ be the maximum margin achievable on the perturbed dataset, achieved by the vector $w_1\in B$.
Question: What is known about $||w_0-w_1||$? Can a bound of $O(\varepsilon)$ be proven?


texts: What is the evidence for average case separation between EXP and NEXP?

texts:
There is significant evidence from cryptography that there exist NP-complete problems that are hard in the average case (meaning that e.g. $AvgP \nsupseteq DistNP$). Namely, we have candidate one-way functions and candidate pseudorandom generators.

Is there similar evidence for an average case analogue of the separation between EXP and NEXP?

EDIT: I have the outline of the argument implying the above separation but the conclusion seems too strong so I suspect there is an error somewhere. The separation between $EXP$ and $NEXP$ corresponds to the separation between $P$ and $NP \cap TALLY$ via unary encoding. Given a language $L \in TALLY$ we can construct the language $L':=\lbrace x | 1^{|x|} \in L \rbrace$. However, it seems that the existence of a heuristic algorithm for $L'$ wrt the uniform distribution implies that $L \in BPP$. Hence, $BPP \nsupseteq NP \cap SPARSE$ implies $HeurP \nsupseteq DistNP$. However, if such a simple average-case to worst-case reduction existed I would probably have encountered it in the literature by now, so I must have got something wrong. What is going on?


texts: Techniques for showing intermediate status between $\mathsf{NP \cap coNP}$ and coNP-completeness

texts:
Inspired by Suresh's post, for a new problem in $\mathsf{coNP}$, whose true proof complexity is intermediate between $\mathsf{NP \cap coNP}$ and being coNP-complete, I am interested in methods which show that it is probably hard to prove the existence of good characterization.

  What techniques and methods do exist to show that a $coNP$ problem might not have good characterization?


texts: When does BPP with a biased coin equal standard BPP?

texts:
Let a probabilistic Turing machine have access to an unfair coin that comes up heads with probability $p$ (flips are independent). Define $BPP_p$ as the class of languages recognizable by such a machine in polynomial time. It is a standard exercise to prove that:

A) If $p$ is rational or even $BPP$-computable then $BPP_p=BPP$. (By $BPP$-computable I mean: there is a randomized polynomial algorithm that being fed $n$ in unary returns w.h.p. the binary rational with denominator $2^n$ that lies within $2^{-n-1}$ of $p$.)

B) For some uncomputable $p$ the class $BPP_p$ contains an undecidable language and hence is larger than $BPP$. Such values of $p$ form a dense set in $(0,1)$.

My question is the following: what happens in between? Is there a criterion for $BPP_p=BPP$? In particular:

1) Do uncomputable in $BPP$ probabilities $p$ exist such that $BPP_p=BPP$? (They may be computable in some higher classes).

2) Is $BPP_p$ wider than $BPP$ for all uncomputable $p$? (The parameters in question are those whose binary expansion contains very long sequences of zeros and/or ones. In this case computing bits by random sampling may take very long, even uncomputable time, and the problem cannot be rescaled to polynomial time. Sometimes the difficulty can be overcome by another base of expansion, but certain $p$ may fool all bases).


texts: A variation on discrepancy involving random graphs

texts:
Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$.  The number of $+1$s that we have to assign is exactly $s$ (hence the number of $−1$s is $n−s$.) Given a configuration $\sigma$, we look at each node $i$ and sum the values assigned to its neighbors, call this $\xi_i(\sigma)$. We then count the number of nodes for which $\xi_i(\sigma)$ is nonnegative:
$$N(\sigma):=\sum_{i=1}^n 1\{\xi_i(\sigma) \ge 0\}.$$
The question is: what is the configuration $\sigma$ that maximizes $N(\sigma)$? More importantly, can we give a bound on $(\max N)/n$ in terms of $s/n$. I am wondering if this problem looks familiar to anyone, or if it can be reduced to some known problem in graph theory. If it helps, the graph can be assumed to be random of Erdős-Renyi type (say, G(n,p) with edge probability $p ~  (\log n)/n$, i.e. average degree growing as $\log n$). The main instrest is in the case where $s/n \in (0,1/2)$.


texts:
The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have exponential size lower-bounds for monotone Boolean circuits.

  What do we know about monotone arithmetic circuits?
  Do we have similar good lower-bounds for them?
  If not, what is the essential difference that doesn't allow us to get similar lower-bounds for monotone arithmetic circuits?

The question is inspired by comments on this question.


texts: Complexity of DFA intersection in this specific case?

texts:
In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible languages. I am curious if this weakens the lower complexity bound.

With an alphabet $\Sigma$, for the $i$th language, I have set $A_i \subseteq \Sigma$ and another set $B_i \subseteq \Sigma$. The $i$th language $L_i$ consists of strings containing any number of symbols in $A_i$, followed by one symbol in $B_i$, followed by any number of symbols in $\Sigma$. I would like to find a DFA that recognizes $L = L_1 \cap L_2 \cap ... \cap L_n$.

Do these restrictions on the input languages eliminate the exponential lower bound?


texts:
Given a point on a plane A, I want to be able to map to a corresponding point on plane B. I have a set of N corresponding pairs of reference points between the two planes, however, the overall mapping is not a simple affine transform (no homographies for me).

Things I have tried:

For a given point, find the three closest reference points in plane
A, compute barrycentric coordinates of that triangle, and then apply
that transform to the corresponding reference points in plane B. How
it failed: sometimes the three closest points were nearly collinear,
so errors were huge. Also, there was no consistency in the mapping
when crossing borders. It was very "jittery."
Compute all possible triangles given the N reference points (N^3).
    Order them by size. For the given point, find the smallest triangle
    that it's in. This fixes the linearly of the points problem, but was
    still extremely jittery and slow.
Start with a triangulated plane A. Iterate through the reference
    points, adding each one to the reference plane. Every time you add a
    point it exists in at least one triangle. Break that triangle into
    three triangles using the new reference point as a vertex. You end
    up with plane A triangulated so you can map from plane A to plane B
    with ease. Issues: You can prove that every triangle will have a
    point that is on the edge of the planes. This results in huge errors
    if your reference points are far from the edge of the planes.

I feel like this should be a fairly standard problem. Are there standard algorithms/libraries for this?


texts:
My question is a bit vague. I have been wondering if (and how), we can apply the notion of treewidth to packing problems in graphs.

I would be happy with any insights or references of past research work on this (assuming their is some relation). Thanks.


texts:
What is the tree-width of the graph $G = (V_1 \cup V_2 \cup \dotsb V_n, E)$ where  the connected components of an induced subgraph of any neighboring set of vertices (i.e. $G[V_i \cup V_j], i = j - 1$) are complete bipartite graphs? Here is an example.

It is clear the entire graph $G$ is bipartite, and showing the tree-width of bipartite graphs is $\mathcal{NP}$-Hard in general, but I was curious if this added enough structure to the problem to make it tractable. For instance, we can easily find the largest bipartite clique just by finding a vertex with maximum degree, then finding its neighbors (and their predecessors).


texts: Stochastic Gradient Descent with integer arithmetics

texts:
Most implementations of stochastic gradient descent (SGD) rely on floating points.
Is there implementations using infinite or finite precision integer arithmetics ?


texts:
Given a set S = {si : {zj : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of S?

As per @JeffE's comment below, there are edge cases of exponential output complexity, so the time-efficient measure of complexity should probably be a function of the output length as opposed to |S|. In that case the goal is low order polynomial complexity as a function of the output length and max(|si|), the latter of which affects the complexity of intersection operations.

For background, I am dealing with several versions of this problem, some larger than others. In the smallest one |S| ≈ 1,000, |si| ≈ 10,000 and the values are zip codes.

Tiny example for clarity:

Input: S = {{},{1},{2,3},{3,4,5,6,7,8,9,10}}
Output: {{},{1},{2,3},{3,4,5,6,7,8,9,10},{3}}

|S| = 4 and there are 24 = 16 subsets of S.
However, there are only five unique sets of subset intersections. The first four are the members of S themselves. The fifth is {3}. The empty set is already a member of S. All other 10 subset intersections produce empty sets also.


texts:
Are there any relation between order-sorted algebra (OSA) and grammars (context-free grammar in particular)?

If I'm not mistaken, according to [1], there is an equivalence between order-sorted and many-sorted algebra (MSA) (they are the same up to an isomorphism), and hence the question may be reformulated between MSA and
grammars.

[1] Goguen, Joseph A., and Jose Meseguer. Order-sorted algebra. Oxford University. Computing Laboratory. Programming Research Group, 1989.


texts:
In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there?

If there is no such analogy, why is randomness in the resource bounded case special? Any references will be great.


texts: How can an inherited attribute be simulated using a synthesized attribute?

texts: Is it possible to simulate an inherited attribute using a synthesized attribute? For example, can the inherited attribute SYMTAB used in normal code generation modules be simulated using a synthesized attribute? If yes, what are the changes proposed to the existing attribute grammar? If not, why not?


texts:
Savitch gave a deterministic algorithm to solve st-connectivity using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is a major open problem whether st-connectivity can be solved by a deterministic algorithm in polynomial time and $O({\log}^2{n})$ space i.e., whether $NL \subseteq SC^2$. $RL$, which lies between $L$ and $NL$, is known be in $SC^2$. Hence reachability in directed graphs with polynomial mixing-time is in $SC^2$.

I am looking for special cases of st-connectivity (that are not known to be in $L$) that have $SC^2$ algorithms. Is anything known about planar graphs, planar DAGs ?
 Note that st-connectivity in DAGs remains NL-complete.


texts:
I am looking for a reference to the fact that if NP is included in BPP then NP is equal to RP. See for instance these links:

https://cs.stackexchange.com/q/80509
http://www.inf.ed.ac.uk/teaching/courses/cmc/cw3_solns.pdf
https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf

I know that this is folklore, but I'd still like to cite something that is published and where this would be properly proved.


texts:
Given a directed graph $G = (V,E)$ and two vertices $s,t \in V$. A pair of simple paths $p_1,p_2$ from $s$ to $t$ is edge disjoint if they don't share an edge.

Using max flow, it is easy to decide if there is a pair of edge disjoint paths from $s$ to $t$. Now, is there a polynomial time delay algorithm to enumerate all pairs of edge disjoint path from $s$ to $t$?


texts: Partitioning a matrix into equal-sized regions: finding the maximum

texts:
I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that:

each element has value in the range $[0, \frac 1 j]$, $j <= p$, $j$ is given,
the sum of all elements in the matrix is 1.

The matrix is partitioned into $j$ axis-parallel non-overlapping rectangles. Each matrix cell with positive value is covered by exactly one rectangle. Whereas, each matrix cell with value 0 is covered by at most one rectangle. For each region, we sum the values inside it and obtain $region\_sum_i$, $i = 1..j$. We are given an optimal partitioning algorithm whose objective is to minimize the maximum $region\_sum_i$. The algorithm is Recursive Slice-and-Dice: Binary Space Partitions from Slice and Dice : A Simple, Improved Approximate Tiling Recipe. I need this algorithm due to the support for don't care regions and a general version of tiling problem. This is a DRTILE problem, but I translate this to RTILE using binary search.

The problem is to find an upper bound on $region\_sum_i$ for the optimal solution under worst-case input with given constraints. I need this as I am doing competitive analysis.

I appreciate any help! Many thanks!


texts: Monotone circuit complexity of matroids?

texts:
Call a monotone boolean function $f$ a matroid function if its minterms are bases of some matroid.
I am interested in monotone circuit complexity of such functions, even when we "tie hands" of these circuits as follows.

Take a monotone boolean circuit and replace Or gates by Sum gates, and And gates by Product gates. The resulting monotone arithmetic circuit will (syntactically) produce some multivariate polynomial. Say that a circuit is read-$r$ times circuit if every variable in this produced polynomial has degree at most $r$.
So let $B_r(f)$ denote the minimum number of gates in a read-$r$ times monotone circuit computing $f$, and $B(f)$ be the minimum of $B_r(f)$ over all $r\geq 1$.

Question: Are there explicit matroid functions $f$ known
with $B_r(f)$ large? At least for $r=1$.

Motivation: Every monotone boolean function $f$ defines a natural minimization problem: given an assignment of nonnegative weights to the variables, compute the minimum weight of a minterm of $f$; the weight of a minterm is the sum of weights of its variables.
One can show that $B_r(f)$ is a lower bound on the number of operations used by any "pure" dynamic programming algorithm approximating the minimization problem on $f$
within the factor $r$; a DP algorithm is "pure" if it can be implemented as $(\min,+)$ circuit.

Now, keep our hats: by Edmonds-Rado theorem, for every matroid function $f$, the minimization  problem on $f$ can be solved by the standard greedy algorithm, even exactly, for all input weightings! So, the measure $B_r(f)$ reflects the approximation weakness of pure DP algorithms when compared with greedy algorithms.

It is known that there are at least $2^{2^n/n^{3/2}}$ matroid functions; see  Knuth 1974. So,
matroid functions of $n$ variables with $B(f)\geq 2^n/n^2$ exist. (Clearly, even non-monotone circuit complexity of some such function is exponential.)

My question is whether we know explicit examples, at least for $B_r(f)$ with bounded $r$.  Of course, we have several lower bounds for monotone circuits, even for unbounded $r$. But do any of them works also for matroid functions? Note that for $r=1$, the hands of circuits are extremely tied: boolean functions computed at inputs of an And gate cannot then share a common variable. So, at least for $r=1$, we don't need the entire power of Razborov's method of approximations:lower bounds for read-once monotone circuits should come much easier.

[ADDED 16.04.2016] I just realized that the case $r=1$ is indeed easy. If a boolean function $f$ is homogeneous (all minterms have the same cardinality) then $B_1(f)$ is at least the monotone arithmetic $(+,\times)$ circuit complexity of $f$. [Read-once circuits cannot use the idempotence $x^2=x$.] Let now $h$ be the spanning tree function: minterms are spanning trees of $K_n$. This is a  matroid function (graphic matroid).
Jerrum and Snir have shown that the $(+,\times)$ complexity of $h$, and hence, also $B_1(h)$  is exponential in $n$.
On the other hand, as a boolean function, $h$ is just the graph connectivity function CONN, and a well-known pure DP algorithm of Floyd-Warshall yields $B(h)=O(n^3)$. So, my question actually asks what happens for $r>1$, the first interesting case being $r=2$.


texts: Fastest known algorithm to enumerate k-cliques in a graph for fixed k

texts:
Is the best known algorithm for finding all $k$-cliques in a graph with $n$ nodes, for a fixed $k$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ?
The time-complexity of the proposed algorithm is $O(n^k / (\epsilon \log n)^{k-1})$ with $O(n^\epsilon)$ space, for all $\epsilon > 0$. Please let me know if there are more efficient algorithms to enumerate all $k$-cliques in a graph.


texts:
Is there any programming language theory describing foreign function interfaces (FFI) and multiple language bindings?

I have asked some implementation issues on stackoverflow, which is not suitable here. But I would like to ask from this site's view and see what I could possibly get from here.

Really appreciate your reply!

Thanks to Dave Clarke for his reply on meta！


texts:
Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph).

But what about the reverse problem?  Given $n$ eigenvalues, can one (efficiently) find a graph that has this spectra?

I suspect that in general this is hard to do (and might be equivalent to GI) but what if you relax some of the conditions a bit?  What if you make conditions that there is no multiplicity of eigenvalues?  What about allowing graphs that have "close" spectra by some distance metric?

Any references or ideas would be welcome.

EDIT:

As Suresh points out, if you allow undirected weighted graphs with self loops, this problem becomes pretty trivial.  I was hoping to get answers on the set of undirected, unweighted simple graphs but I would be happy with simple unweighted directed graphs as well.


texts: Finding a simple dual of a simple graph in some surface

texts:
Given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph embedding as vertices and adding an edge between two vertices for every side the corresponding faces have in common in the original graph.

Here's my problem. Given a simple graph $G$, I need to find another simple graph $G'$ such that there exists a surface $S$ and a cellular embedding of $G$ on $S$ such that $G'$ is the dual of this embedding of $G$. Some simple graphs $G$ do not have simple duals on any surface (for example, a simple path; see JɛﬀE's comment). On the other hand, I think that for some simple graphs $G$, there can be many possible simple duals $G'$, depending on the surface and the embedding chosen.

Question: Given a simple graph $G$, give a method that finds a simple dual graph $G'$, if it exists.

None of the embeddings is required to be of minimum genus. The graphs are assumed to be connected.


texts: Finding the minimum number of coordinates to change to get a vector inside a subspace

texts:
Let $\mathbb F$ be a field (ex. a finite field, or the reals), $A$ a $m\times n$ matrix over $\mathbb F$, and $x\in \mathbb F^n$ a vector. I'm interested in finding the smallest number of coordinates I need to change in $x$ to order to have $Ax=\mathbb 0$.

What would be an algorithm to find this, or alternatively, an intractability result (ex. NP-completeness)?

Note: I am thinking of this in the context of matrix rigidity.


texts: Number of vertices present in all maximum matchings

texts:
Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible.

Is there a solution beside the obvious remove each vertex and find the maximum matching to see it reduces?


texts:
I am studying the Advanced Data Structures material and I'd like to implement the Ordered-file maintenance data structure. I have few questions in order to start.

The papers rely on a static view, where the data structure already contains elements, but I need to start from scratch. The data structure partitions an array of $N$ (circa) elements into chunks of $\log N$ elements, and each chunk is ordered. When inserting, I need to choose a chunk and insert into a blank spot, if I fill the chunk, I need to move and possibly reorder elements based on density in a binary tree fashion.

At the beginning how many chunks do I have? I suppose one.
When the array is full according to the target density, do I need to grow the array and how? I suppose yes, always by a power of two (number of chunks).
Is there a possibility that a tree is impossible to rearrange according to the density? I hope not.
Is there any source code that I can take a loot at?
When $N$ changes do I need to change the chunk size accordingly? I think so.

Thanks!


texts: Problems which are solvable using Linear Programming

texts: Can anyone share a link to a good survey/book about the different problem types for which we have a linear programming based solution for, as well as the related techniques?


texts: Forbidden minors for bounded genus graphs

texts:
It is well known that $K_5$ and $K_{3,3}$ are forbidden minors for planar graphs. There are hundreds of forbidden minors for graphs embeddable on a torus. The number of forbidden minors for graphs embeddable on surface of genus g is an exponential function of g. My question is as follows :

  Is there an explicit graph $G_t$ on t vertices (which is not a complete graph) such that $G_t$ is a forbidden minor for graphs embeddable on surface of genus g, where t is a function of g ?

EDIT : I realized that the following theorem is known :

  For every surface Σ there exists an integer r such that $K_{3,r}$ does not embed in Σ.

So, I am looking for $G_t$ that is not complete graph, not a complete bipartite graph.


texts: Common false beliefs in theoretical computer science

texts:
EDIT AT 10/12/08:

I'll try to modified the question so it may interest more people to share their opinions. We NEED your contributions!

This post is inspired by the one in MO: Examples of common false beliefs in mathematics. Big lists sometimes generate a massive number of answers the qualities of which are hard to control, but after the success of the related post on MO I am convinced that it would be helpful to list a bunch of common false beliefs in TCS.

Still, since the site is designed for answering research level questions, examples like $\mathsf{NP}$ stands for non-polynomial time should be not on the list. Meanwhile, we do want some examples that may not be hard, but without thinking in details it looks reasonable as well. We want the examples to be educational, and usually appears when studying the subject at the first time.

  What are some (non-trivial) examples of common false beliefs in theoretical computer science, that appear to people who are studying in this area?

To be precise, we want examples different from surprising results and counterintuitive results in TCS; these kinds of results make people hard to believe, but they are TRUE. Here we are asking for surprising examples that people may think it is true at the first glance, but after a deeper thought the fault within is exposed.

As an example of proper answers on the list, this one comes from the field of algorithms and graph-theory:

For an $n$-node graph $G$, a $k$-edge separator $S$ is a subset of edges of size $k$, where the nodes of $G \setminus S$ can be partition into two non-adjacent parts, each consists of at most $3n/4$ nodes. We have the following "lemma":

  A tree has a 1-edge separator.

Right?


texts: Implication of Exponential Time Hypothesis falseness?

texts:
The proof that Exponential Time Hypothesis (ETH) is true, would imply that P!=NP among other implications (like solvability of SAT in sub-exponential time is not possible in the worst case).

But, if proven that ETH is false, how would it impact the Complexity Hierarchy and what would be the implications of the proof. Results, that immediately follow from the ETH falseness (based on our current knowledge)?


texts: Can we compute encodings of binary strings under arbitrary permutation groups?

texts: Given a permutation group $G \leq S_n$, can you construct non-uniformly a circuit computing a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log|\{0, 1\}^n/G_n|)}$ with size $O_n(\frac{|\{0, 1\}^n / G_n|}{log|\{0, 1\}^n/G_n|})$ such that the fibers of $f$ are the orbits of $\{0, 1\}^n$ under $G$?


texts: Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size

texts:
In a related question I've defined a class of graph problems which are verifiable using a time related only on the size of the witness:

$EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in $poly(k)$ time$\}$, i.e. independent of $|V|,|E|$.

You can assume that the verifier has random access to the graph adjacency matrix in $O(1)$ time.

Examples for $EasyVer$ problems will be $VC, Clique, IS$ and $Steiner Tree$.

Also, many packing and problems, $triangle-packing$, $k-path-packing$, or in general $H-packing$ for a graph $H$ with constant treewidth, are all in $EasyVer$.

Problems which aren't in (i.e. require more extensive interaction with the input) are also easily found: $VC, DominatingSet, FVS$(Feedback Vertex Set).

In order to get a sense of how $EasyVer$ relates to known complexity classes it would be useful to have a list of problem it contains.

Which other NP-complete problem (or even better, problem classes) can be verified in $poly(k)$ time, where $k$ is the size of the problem witness?


texts:
It is known (see "Counting curves and their projections" (free version) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of $\mathbb{F}_q$-rational points on a curve in sparse representation is $\mathsf{\# P}$ complete. Note that the degree of such curve can be exponentially large since sparse representation allows it.

But assume that the degree of a curve is not greater than some polynomial. Can we find the number of $\mathbb{F}_q$-rational points of this curve by using, say, constant iterations of Arthur-Merlin protocol?


texts:
Consider the following empty intersection problem:

INPUT: a ground set $[n]:=\{1, \ldots, n\}$; a set family $S_1, \ldots, S_m$ s.t. $S_i\subseteq [n]$ for every $1\leq i\leq m$
TASK: on query $X\subseteq [n]$ decide whether there exists $1\leq i\leq m$ s.t. $S_i\cap X = \emptyset$.
TASKbis: on batch queries $X_1, \ldots, X_k\subseteq [n]$ decide whether $S_i\cap X_j=\emptyset$ for each $i,j$.

I'm in deep search for references about this problem, both TASK as well as the batched version TASKbis: fast algorithms (sequential, parallel, randomized, any other model is appreciated), also complexity lower bounds or other characterizations...

Observe that we can impose special values of $m$, for example consider $m=n^2$, or similar ...


texts: How would you define a set of 'fundamental operations' over an object?

texts:
I'm writing an implementation for a common array structure.

As you would find already familiar, an array is an ordered data structure that you can transform with different (hopefully self-explained) operations like:

set object at index
insert object(s) starting at index i
remove object(s) starting at index i
splice
push
pop
shift
unshift
clear

And then you could intuitively see that you could just code a set of 'fundamental operations' from where you could construct all the other ones. For instance, you could use splice to emulate the behavior of all other operations but you could also use insert and remove to construct all of them.

My question is, then, how would you define those 'fundamental operations'?

Is splice a construct of insert and remove, therefore insert and remove being fundamental?

Or are insert and remove special cases of splice, therefore splice being the fundamental operation for the whole group?

Is there some theory or field of CS that deals with these things?

P.S. Sorry if I'm making a lot of mistakes when presenting the question. I don't know about the correct language for this and have never studied this stuff formally. I hope that I explained myself correctly.


texts: Has there been any result which does not have any Natural Proofs?

texts:
Alexander Razborov and Steven Rudich's Natural Proofs result is one of the major barriers against proving circuit lower bounds. The paper is almost 20 years old (it was published in 1994).

Has there been any result that has avoided the natural proofs' barrier? More formally, has there been any result where the concept of natural proofs makes sense and we provably know that there cannot be a natural proof for the result?


texts:
The uniform version (the version which we normally see) of deciding whether a CFG (Context Free Grammar) is ambiguous is undecidable. But here I'd like to know something about the non-uniform version of this problem. That means, we just pick one CFG instead of considering all CFGs.

It's true (and trivial) that there is a Turing Machine M which can decide whether a fixed CFG G is ambiguous or not. M just needs to blindly output True or False according to the fact, i.e., whether G is actually ambiguous or not.

However, this is a non-constructive solution. It tells you the answer but doesn't provide with a proof. This is something like God's knowledge.

There is always a proof of ambiguity for any ambiguous CFG. This problem is recursively enumerable. But it's negation (i.e. proof of unambiguity) isn't. However, we can still find ways to prove unambiguity (for example, for very simple grammars like S -> a).

The relationship between the uniform and non-uniform version of this problem is that:

The uniform version tells you it's impossible to solve the problem for all instances.
The non-uniform version tries to tackle each instance based on it's unique characheristics.

If we let the whole problem space (here it's the space of all instances of valid CFGs) be S, and the space of solvable instances (those come with a proof) w.r.t. ambiguity be T, what's the relationship between the size of S and T? (Note that both S and T have an infinite cardinality.)


texts: What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?

texts:
In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$.

$KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey and Fellows in their book give definition as

These two definitions do not seem to be entirely consistent.

We know $W[P]=FPT\implies W[1]=FPT$.

We also know this puts $KSUM$ is $FPT$.

Does it mean $KSUM$ is $FPT$ at a fixed $K$ and independent of length of integer inputs or can it also imply some asymptotic $FPT$ result where $K$ depends non-trivially on number of input integers and length of input integers?

I looked for this information in Grohe's or Downey's book and I am unable to find this information and could someone weight in on this subtlety? That is we might have an algorithm for $KSUM$ that is $FPT$ if input integers have only $O(polylog(n))$ bits each. However if input bitlength is polynomial in $n$ or exponential in $K$ then the $FPT$ algorithm complexity might not be of shape $O(f(K)\cdot poly(n))$. This could still be $FPT$ under Downey's definition. Would such an algorithm still be considered $FPT$ for $KSUM$ as well? It should be but from the working definitions of $FPT$ for $KSUM$ in literature this is unclear.
Is it consistent $W[P]=FPT$ while $KSUM$ is not $FPT$ at bounded or fixed $K$?


texts:
Possible Duplicate:
  Polynomial-time algorithms with huge exponent/constant

In many texts you find statements like 'The class P characterizes the problems that are efficiently solvable. Even though $n^{100}$ algorithms are in P, these don't occur in practice'.

Today I came across a $n^{120}$ algorithm for a problem where, apparently, no better algorithm is known: Recognizing Map Graphs Reference.

Then there are algorithms with huge constants like the graph minor algorithm.

Do you know of any other problems where the best known algorithm is polynomial, but terribly impractical?


texts: Characterizing the exponential savings in active learning

texts:
Let $H$ be a hypothesis class with VC dimension $d$. In supervised learning, we need almost $O(\frac{d}{\epsilon})$ random labelled examples to return a hypothesis within $\epsilon$ from the target (separable case).

Active learning potential lies in its exponential saving in terms of the number of queries required compared to the supervised learning. This big saving in known for some structures ( for example learning threshold functions requires $O(\frac{1}{\epsilon})$ examples while we can achieve the same goal with $log \frac{1}{\epsilon}$ in active learning ).

What characterizes this exponential reduction in general? Are there certain properties such that if $H$ satisfies them then active learning would help?


texts: Is there any relationship of hardness between the two problems?

texts:
Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D.

Consider the problem P1: With D as input, computes $(x^*,y^*)=argmax_{(x,y)}F(x,y|D)$ where x and y are two sets of variables.

Another problem P2: With y and D as input, computes $x^*=argmax_xF(x|y,D)$.

If we know P2 is NP-hard, can we infer the hardness of P1? Is P1 also NP-hard?


texts: Modeling objects (OOP) in dependent type theory

texts:
I am interested in modeling objects, from object oriented programming, in dependent type theory. As a possible application, I would like to have a model where I can describe different features of imperative programming languages.

I could only find one Paper on modeling objects in dependent type theory, which is:
Object-oriented programming in dependent type theory by A. Setzer (2006)

Are there further references on the topic that I missed and perhaps are there more recent ones?

Is there perhaps an implementation (i.e. proof) available for a theorem prover, like Coq or Agda?


texts: Canonical way of coloring graphs (individualization) for isomorphism purpose

texts:
Stefan Kratsch and Pascal Schweitzer in their paper
Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs
give a characterization of graphs on which
Graph Isomorphism is solvable in polynomial time (Theorem 4, page 8).

I have a problem understanding the outline of the proof for Theorem 4 and
therefore the proofs of the different cases itself.
The main idea is to construct colored graphs of bounded color valence
for which the problem is solvable in polynomial time according to Theorem 5.

For creating such graphs one tries to find a canonical coloring.
One such method is called individualization.

As this method is just described as:

  We guess an ordered set of vertices of constant size,
  color the vertices in this set with singleton colors, and then
  color the remaining vertices according to their adjacencies to
  the vertices in the ordered set.

and not further specified in the following proofs.

I have two questions:

How exactly is this coloring done?
What exactly is a canonical coloring?


texts: Data structure for getting all matches of a prefix from a large list of strings

texts:
Suppose I have a very long list of strings (millions of them), ordered by importance. For example:

...
barracudas
oftwalj
velasp
offso
skenep
vitriolic
offscre
...

What is an appropriate data structure for storing this data to make it efficient to obtain all matches of any prefix? For example, I may want to search for the prefix of, which should return oftwalj, offso, offscre, etc. in the order of importance.

Things I have used in the past to solve this problem:

Linear search - eventually became too slow as the list became very large.
Storing the data in a simple hash table, where the key is the prefix, and the value is the list of words matching the prefix together with their "importance score" - this works, but the space requirement is high.


texts: Number of permutations which have the same Kendall-Tau distance

texts:
Input: The number of elements $m$ and an (positive) integer distance $d$.
Ouput: The number of permutations of $m$ elements which have Kendall-Tau distance $d$ from a fixed permutation.

I think there should be a closed formula. Does anybody know a good reference?


texts: Maintaining order in a list in $AC^0$ in $O(1)$ time

texts:
The order maintenance problem (or "maintaining order in a list") is to support the operations:

singleton: creates a list with one item, returns a pointer to it
insertAfter: given a pointer to an item, inserts a new item after it, returning a pointer to the new item
delete: given a pointer to an item, removes it from its list
minPointer: given two pointers to items in the same list, returns the one closer to the front of the list

I am aware of three solutions to this problem that perform all operations in $O(1)$ amortized time. They all use multiplication.

Athanasios K. Tsakalidis: Maintaining order in a generalized linked list
Dietz, P., D. Sleator, Two algorithms for maintaining order in a list
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito, “Two Simplified Algorithms for Maintaining Order in a List”

Can order be maintained in a list in $O(1)$ amortized time without using any arithmetic operations not in $AC^0$?


texts: Counting the Number of Simple Paths in Undirected Graph

texts:
How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths.

Recall that a simple path is a path with no cycles, so I'm talking about counting the number of paths with no cycle.


texts: What is the initialization time of a link-cut tree?

texts:
Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two trees in the forest into one, while operation cut divide a tree in the forest into two trees.)

Several applications are known by using link-cut trees, and here I'm particularly interested in Goodrich's separator decomposition, which given a $n$-node plane graph $G$ one can obtain a corresponding binary tree where nodes are subgraphs of $G$, and the children of a node $H$ are the subgraphs of $H$ divided by the separator on $H$. Such a decomposition can be easily constructed in $O(n \log n)$ time (since a separator can be found in $O(n)$ time, and since the separator divides the graph so balanced, after $O(\log n)$ level of separations the leaves of the tree are of size $O(1)$). The main contribution of Goodrich is that he can construct such a decomposition in time $O(n)$, by maintaining and reusing the data structures used for finding separators in each level.

One of the data structures being used in the construction, is indeed the link-cut tree. In page 7 of the paper by Goodrich, he claimed that the initialization of the link-cut tree can be done in time $O(n)$. While I go through all the papers cited there, it seems to me that if we construct a link-cut tree via operation link, it takes time $O(n \log n)$ in total.

  Do I misunderstand something? Can the initialization of a link-cut tree be done in time $O(n)$?


texts: A continuum version of the 1D k-means clustering problem: constant factor approximations

texts:
Modify the k-means clustering problem in 1D by assuming that, instead of a finite number of observations, we must classify into $K$ clusters a continuum of observations, distributed on the unit interval $[0, 1]$ according to some cumulative probability density function $F$. Has this modification been studied?
Here is my specific question: The clustering problem can be reduced to the problem of finding $(a_1, a_2, ..., a_{K-1})$ such that the quadratic loss function is minimized? One can characterise these optimal (OPT) thresholds with first-order conditions (which do not admit an explicit solution). One can also think of the intuitive approximation (APX) that would set the thresholds at $a_1=F(1/K), a_2=F(2/K), ..., a_{K-1}=F((K-1)/K))$. One can bound the quadratic loss under APX. (The bound is $1/(4K^2)$.) One could also guess that APX is a constant factor approximation of OPT. Has this approximation been proved?


texts:
Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$.  (See "Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis")

Are there known consequences of the existence of sparse complete sets for other complexity classes?  In particular, if there is a sparse $P$-complete set under logspace many-one reductions, does that imply $P = L$?


texts: When was the dynamic array first used as an example for amortized analysis?

texts:
I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it seems like it is a classic example.

I've been looking and can't seem to find a reference to it. Does anyone know when the example was first used?


texts: non-malleable commitment and security parameters

texts:
Although it is not clear, it appears that definition 5 of this paper,

page 10 of this paper, and page 6 of this paper, each assume

that the honest parties will all use the same security parameter.

  Are there any known constructions of concurrent non-malleable
  commitment that do not assume a common security parameter?

(If I'm wrong about the first sentence in this post, then

one of those three papers might be such a construction.)

I notice that, by rounding to a value of the form $2^\left(2^n\right)\hspace{-0.02 in}$,$\:$ one can assume without

loss of generality that at most $\:O\hspace{.01 in}(1)\:$ different security parameters will be used.


texts: Is Scott's reduction sound for $\mathrm{FO}^2$ with equality?

texts:
As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the fact that any sentence in $\mathrm{FO^2}$ can be reduced to Scott's Normal form in polynomial time. The Scott's Normal form is given as
$$\forall x \forall y \alpha(x,y) \land \bigwedge_{i=1}^{m} \forall x \exists y \beta_{i}(x,y) $$
Now, they also say that proving decidability for scott's reduction only proves decidability for $\mathrm{FO}^2$, and then they discuss scott's class for $\mathrm{FO}^2$ with equality.
My question: Is Scott's reduction sound for $\mathrm{FO}^2$ with equality, i.e every sentence can be reduced to the form presented above, where $\alpha$ and $\beta_i$ are all binary predicates, it is not obvious to me from there discussion?


texts: anything hinting that EXPTIME $\subseteqq$ PSPACE?

texts: Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？


texts: I don't quite understand why almost all SAT solvers use CNF instead of DNF. It seems to me that solving SAT is easier using DNF. After all, you just have to scan through the set of implicants and check whether one of them contains not both a variable and its negation. For CNF, there's no simple procedure like this.


texts: Mutual information and entropy to prove minimal Relevance Maximum Dependency

texts:
I'm reading through a paper on feature selection: Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance,and in-Redundancy
 but I'm unable to understand parts of the proof presented in section 2.3 where they are using information theory to prove that Max-Dependency is equivalent to the algorithm they present (mRMR).

I don't follow how they derive the equality for minimal redundancy...

... from ...

... and ...

(There is a similar step for the maximal relevance term which I also don't grasp)

My best understanding of what they are doing is that the entropy for each individual feature is found in the summation of the H(x_i) terms, and then the mutual information between all features is subtracted out in the J term, and that this is done (some how) through the chain rule, and then collection of the mutual information terms?

I don't have a strong back ground in information theory - so this is mostly conjecture. Hopefully some one with a stronger information theoretic background could elucidate this. Thanks.


texts: Difficulty of graph coloring and independent set?

texts:
Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable.

Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-COLORABILITY or K-INDEPENDENT SET?
Is there a deterministic reduction from GRAPH-3-COLORABILITY to UNAMBIGUOUS-GRAPH-3-COLORABILITY or K-INDEPENDENT SET to UNMAMBIGUOUS-K-INDEPENDENT SET?


texts: Uniformity vs. nonuniformity in algebraic complexity theory

texts:
I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes.  In this sense, nonuniform computational models can be thought of as a secondary device in complexity theory, the main interest being the uniform model.

However, in algebraic complexity, the situation seems to have been the other way around.  Algebraic nonuniform models including algebraic circuits were studied long before the uniform Blum-Shub-Smale machines were introduced.  I am confused about this; since nonuniformity preceded uniformity in the algebraic setting, something about nonuniformity should have been unsatisfactory.  But what was wrong with straight-line programs?

I'd be grateful if you could tell me why uniformity in algebraic complexity theory can be preferable.

EDIT: I realized that uniformity helps if you are discussing computability of algebraic problems.


texts:
I am an undergraduate student of Computer Science and am very interested in learning the theoretical part of it all.

Unfortunately, none of the subjects we have in our UG program give us an insight of theoretical part of Computer Science.
We do have the subjects Automata and Graph Theory, but our syllabus is very limited.

I have been looking for resources to learn the theory of computer science from the base up, for quite some time now.
I have already tried reading papers, completed MOOCs.

Somehow, I am always dissatisfied with the material. It is either too complicated (I don't even understand the notation used) or too trivial (teaching bits and bytes).

Could someone please provide me with some resources to learn theoretical computer science.
If possible, sort it in the order in which I should read it, so that the majority of prerequisites of the nth entry in the list, are covered in the preceding n-1 entries.

Please keep in mind:

I am really interested in learning it.
I have a decent background in programming, and have worked with several programming languages.
This is not a What videos/papers/books should everyone watch/read question. I am simply looking for some introductory resources, which are neither too obvious, nor too complicated.

I have had 3 semesters of College level Maths.
Also, I have studied the material provided by ocw.mit.edu, for the courses: 18.03, 18.062J and 18.400J mentioned at http://math.mit.edu/academics/undergrad/major/course18C/

Thanks a lot.


texts: Shortest s-t path when is allowed to ignore k weights

texts:
Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed to ignore the weight (i.e. set to $0$) of at most $k$ edges on the path?

An $O(kn\log(kn)+km)$ homework-level solution will be copy the graph $k$ times and use dijkstra. But is there any better algorithm (or lower bound)?


texts: Determining the convexity of a set on $S^n$

texts:
While pondering a problem on separating objects in $R^n$ by hyperplanes, I came across the following puzzle:

Suppose we are given a convex subset of $S^n$ which we call $M$.

For each point $p \in S^n$, let $C(p)$ define the great circle obtained by considering the point $p$ as the north pole and $C(p)$ as the equator. (If we imagine $p$ to correspond to a unit vector $v(p)$ in the obvious manner, then $C(p)$ corresponds to the set of all unit vectors orthogonal to $v(p)$).

Now, define the set $X = \{x \in S^n$ s.t $C(x) \cap M \neq \phi \}$

Is $X$ necessarily convex? The above definition is equivalent to saying that $X$ is the set of all unit vectors orthogonal to at least one unit vector in $M$.

Edit: Sasho has clarified in his answer that $X$ need not be necessarily convex. I am wondering if we may say something weaker about the topology of $X$. I will conjecture that $X$ would be decomposable into $2$ separate convex components?