texts:
I formulated the following problem today while playing with my GPS. Here it is :

Let $G(V,E)$ be a directed graph such that if $e=(u,v) \in E$ then $(v,u) \notin E$, i.e., $G$ is an orientation of the underlying undirected graph. Consider the following operations :

$Flip(u,v)$ : Replace an edge $(u,v)$ with an edge $(v,u)$
$undirect(u,v)$ : Make the edge $(u,v)$ undirected

Let $s,t \in V$ be two special vertices. Consider the following optimization problems :

Min-Flip st-connectivity : Given $G$ and two vertices $s,t$ find the minimum number of edges that need to be flipped to make a directed path from $s$ to $t$.
Min-Flip strong-connectivity : Given $G$ find the minimum number of edges that need to be flipped to make $G$ strongly connected. If it is not possible to make $G$ strongly connected by flipping edges then output NO.
Min-undirect strong-connectivity : Given $G$ find the minimum number of edges that need to be undirected to make $G$ strongly connected.

Note that you are not allowed to add "new" edges. You are only modifying the existing edges using the above operations. Is this problem known in the literature. If so what are the known results ?


texts: What CS theories are absolutely paramount for someone new to TCS to understand?

texts:
First - I'm happy to be a part of this community. Electronics and software engineering are both my passion and my profession, yet I feel as if I'm missing a solid basis in theoretical computer science. This field absolutely fascinates me, and I was pleased to see a Stack Exchange community built around it. So thanks to everyone who contributes.

I'm interested in building well-rounded foundation TCS, but don't know where to start. Of course Turing, etc is very popular, but I'd like some reference from researchers in the field on what theories are critical to have a greater, well rounded understanding of computers, while actually solving real problems. Please include any examples/advice where TCS has helped you solve a specific problem, if applicable.

My questions..

What areas are critical for me to study in mathematics?
What areas are exciting and "hot" in theoretical CS right now?
What areas are incredibly useful to consider for hardware innovation?
What areas are useful when considering software innovation?

If it helps at all I work in IoT as a software/cloud architect, primarily writing ruby/C++, while occasionally working with EE on hardware design. I'm just starting to get into PCB design in my free time.

Thanks again in advance, looking forward to learning!


texts: A mathematical (categorical) description of type classes

texts:
A functional language can be viewed as a category where its objects are types and morphisms functions between them.

How do type classes fit in this model?

I assume we should only consider those implementations that satisfy the constraint that most type-classes have, but that are not expressed in Haskell. For example, we should only consider those implementations of Functor for which fmap id ≡ id and fmap f . fmap g ≡ fmap (f . g).

Or are there any other theoretical foundations for type classes (for example based on typed lambda calculi)?


texts: Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part

texts:
Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ with
$$
 n \cdot \infty = \infty\cdot n = \infty \mbox{ for all $n \ne 0$, }
\qquad
 \infty\cdot \infty = \infty
\qquad
n + \infty = \infty + n = \infty \mbox{ for all $n$, }
\qquad
0\cdot \infty = \infty\cdot 0 = 0
\qquad
\infty + \infty = \infty.
$$

A formal power series is a polynomial if only a finite number of coefficients are non-zero. A formel power series is called rational if it could be built up from polynomials by a finite application of addition (pointwise), multiplication (convolutional product), and the star operatation, which for $f = \sum_{w \in \Sigma^{\ast}} c_w w$ is defined by
$$
 f^{\ast} = 1 + f + f^2 + f^3 + \ldots
$$
where the sum taken over an infinite set $\{ k_i \in \mathcal N \mid i \in I \}$ is defined as $\sup\{ \sum_{j\in J} k_j \mid J\subseteq I \mbox{ finite } \}$, i.e. the supremum of all finite sums, hence the above expression makes sense.

These notions go back to Schützenberger and Eilenburg, where the last one calls these $\mathcal N$-subsets instead of formal power series. Now given $f$ we define
$$
 xf_s := \left\{ \begin{array}{ll}
  \infty & xf = \infty \\
   0     & \mbox{ otherwise.}
\end{array}\right.
$$
the singular part, i.e. all entries whose coefficient is $\infty$ are retained, and
$$
 xf_n := \left\{
  \begin{array}{ll}
    xf & xf \ne \infty \\
    0  & \mbox{ otherwise }
  \end{array}
\right.
$$
the non-singular part, where we retain those entries that do not evaluate to $\infty$. Surely
$$
 f = f_s + f_n
$$
and we have
\begin{align*}
 (f + g)_s & = f_s + g_s \\
 (f g)_s & = f_s g + g_s f.
\end{align*}

Now let $\mathcal C$ be the class of formal power series $f$ such that $f_s$ is rational, then why does the above formula imply that $\mathcal C$ is closed under multiplication?

The argument is taken from Samuel Eilenberg, Automata, Machines, Languages, Volume A to show that for rational $f$, also $f_s$ and $f_n$ are rational, and he uses exactly the above argument. Buf if $f_s$ is rational, and $g$ such that $g_s$ is rational, why should then $f_s g + f g_s$ be rational?


texts: Program transformation using partial functions which preserve partial correctness

texts:
Much work has been done demonstrating that certain program transformations preserve particular properties.  That is, for any program $P$ which has property $\alpha$, show that $P$ transformed under transformation $T$ still has property $\alpha$.

I'm interested in a transformation which replaces every usage of function $f$ in $P$ with partial function $g$, where $g$ is a restriction of $f$ (meaning that $g(x) = y \implies f(x) = y$). It seems intuitively obvious that this transformation, while not necessarily preserving totatlity, preserves partial correctness.  Yet I cannot find a standard proof or reference on this or even mention of this seemingly elemental fact.

Can anyone help me out? A reference, a proof, a different formalism?


texts: Does the order of insertion affect the topology of an R-Tree

texts:
Say I have 2 permutations of the the same set of elements.
I create 2 R-Trees, one for each permutation.
Do I end up with 2 structurally identical R-Trees or not?
PS: My elements are rectangles on a plane.
Edit:
Reformulation of the question: is there an insertion algorithm that reconstructs the same R-Tree regardless of the order of elements in use?


texts: Diophantine equations and complexity classes

texts:
LINEAR DIOPHANTINE EQUATIONS
(given natural numbers $a, b, c$, are there natural numbers $x$ and $y$ such that $ax + by + c = 0$?) are solvable in polynomial time.

QUADRATIC DIOPHANTINE EQUATIONS ($ax^2 + by + c = 0$) are NP-complete (NP-complete decision problems for quadratic polynomials).

General DIOPHANTINE EQUATIONS are undecidable (Davis-Putnam-Robinson-Matiyasevich theorem).

Are there other classes of Diophantine equations (with restrictions on their arguments/variables) that capture other complexity classes (in particular PSPACE) ?


texts: Is there a gap between weak learning and PAC-learning?

texts:
For concreteness lets use the definitions of PAC and weak-learning as in the notes of Avrim Blum (http://www.cs.cmu.edu/~avrim/ML12/lect0208.txt) and also his notes on SQ-Learning (http://www.cs.cmu.edu/~avrim/ML12/lect0321.txt)

It seems to me that the following are true,

That what is difficult to PAC-learn is also difficult to weak learn
If a binary valued/classification concept class has a weak learner then AdaBoost can produce a PAC-learner for it.

My questions are two fold,

But its not clear if one can boost a weak learner for an arbitrary concept class into a PAC learner for the same class. Or what is the best known statement in this direction?
Why is SQDim presented as a measure of hardness of weak learning? Is that a limitation of theory that we cannot get hardness of PAC-learning from SQDim? (..except in the case of binary classification when AdaBoost will lift from weak to PAC..)


texts: Is sorting pairwise distances as hard as sorting arbitrary points?

texts:
If we have $n$ points in $\mathbb{R^d}$, what is the complexity of sorting the $O(n^2)$ pairwise distances?

Clearly the complexity is $\Omega(n^2)$ but is there a reduction to show it is as hard as sorting $n^2$ arbitrarily chosen numbers?

As a concrete sub question, is the complexity $\Theta(n^2\log{n})$ in the comparison model?


texts: If P = NP were true, would quantum computers be useful?

texts:
Suppose that P = NP is true.  Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on the fact that P = NP is true?  How would you characterize the improvement in efficiency that would come about if a quantum computer could be built in a world where P = NP, as opposed to a world in which P != NP?

Here's a made-up example of about what I'm looking for:

  If P != NP, we see that complexity class ABC is equal to quantum complexity class XYZ...but if P = NP, class ABC collapses to related class UVW anyway.

(Motivation:  I am curious about this, and relatively new to quantum computing; please migrate this question if it is insufficiently advanced.)


texts: Proofs obtained only through spectral graph theory

texts:
I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have.

However, I'm curious about a statement that popped up in several sources (for instance over there), which says in essence that some results in graph theory have been proved using spectrum-based techniques only, and that so far, no proof that bypasses those techniques is known.

Unless I skipped that, I don't recall seeing such an example in the literature I've read so far. Do any of you know of examples of such results?


texts: formal languages: what does R-trivial mean?

texts:
What is an R-trivial language? What is an R-trivial monoid?

Context: Formal languages. Afaik, R-trivial languages is a subset of the starfree languages.

I mostly have background in formal languages and automata theory but not so much with the syntactic monoid characterization. So it would be nice to give a basic definition with maybe a small example of such a language.

(In order to support multiple QA-sites because I don't want to have any QA-site stay behind and to have that question also represented there, I have also posted this question on these other sites: stackoverflow.com, math.stackexchange.com, mathoverflow.net. In general I am against cross-posting but in this case, as they all have the same goal to be a complete reference of questions in the specific area, having the question cross posted is the best thing you can do.)


texts: Data structure for updates on intervals and querying number of zeros

texts:
I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$.

$\text{increase}(a,b)$, which increases $t[a],t[a+1],\ldots,t[b]$.
$\text{decrease}(a,b)$, which decreases $t[a],t[a+1],\ldots,t[b]$.
$\text{support}()$, which returns the number of indices $i$ such that $t[i]\neq 0$.

You have the promise that every call to decrease can be matched to a previous call to increase with the same parameters $a,b$. The application I have in mind is a sweepline algorithm to compute in time $O(n\log n)$ the area of the union of n given rectilinear rectangles.

A quad-tree would have size $\Theta(n^2)$, so it is not a solution. Fenwick or Interval trees have the right flavor, but I don't see how to extend them to support the operations above.


texts: Problems to reduce from to prove an $\Omega(n\log n)$ lower bound

texts:
What are the standard problems we can reduce from to prove $\Omega(n\log n)$ lower bounds?

Of course, state problems other than sorting and element distinctness.


texts: Finite-State Automata over a real-valued alphabet

texts:
Consider a finite state set $Q$, with a distinguished start state $s\in Q$, as well as two functions: a transition function $\delta:Q\times\mathbb{R}\to Q$ and a final output function $F:Q\to\mathbb{R}$. The tuple $(Q,s,\delta,F)$ defines a mapping $f:\mathbb{R}^*\to\mathbb{R}$ --- that is, from finite sequences of reals to reals --- in exactly the same way as a classic DFA over a finite alphabet $\Sigma$ defines a mapping
$\Sigma^*\mapsto\{0,1\}$.
Have such DFA analogs over the real alphabet been considered before?


texts: GI-hard graph problem not known to be $NP$-complete

texts:
Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A graph problem $X$ such that $GI <_p^m X$).

  Is there a natural $GI$-hard graph problem that is neither $GI$-equivalent nor known to be $NP$-complete?


texts:
We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$.

What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$?
Is $\mathsf{CFL}$ a proper subset of $\mathsf{NL}$?

Note that $\{0^k1^k2^k \mid 0 \leq k \}$ is not context-free, but in $\mathsf{NL}$.


texts:
It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question is: What are the complexity-theoretic consequences of the existence of one-way functions? For example, OWFs imply that $\mathsf{NP}\ne\mathsf{P}$, $\mathsf{BPP}=\mathsf{P}$, and $\mathsf{CZK}=\mathsf{IP}$. Are there other known consequences? In particular, do OWFs imply that the polynomial hierarchy is infinite?

I'm hoping to better understand the relationship between worst-case and average-case hardness. I'm also interested in results going the other way (i.e. complexity-theoretic results that would imply OWFs).


texts: Directed graph with bounded in-deg can be partitioned in a balanced way

texts:
I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two sets $V_1, V_2$ in a way that for each vertex $v\in V_1$ (and the same for every vertex in $V_2$) , if the vertex $v$ has out-degree $d(v) \geq c(n)$ in $G$, then its out degree in the corresponding subgraph will be between $\frac{1}{3}d(v)$ and $\frac{2}{3}d(v)$.

I suspect that it is the kind of statements which can be proved by the probabilistic method, using the local lemma (since there are some similar theorems proven in this way). However I couldn't figure out how to do that, will be glad for help.
(I have also asked this question in math.stackexchange a while ago, but since this is a research question, I believe this forum is more appropriate).


texts: Ecology and evolution through the algorithmic lens

texts:
The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very discrete nature (see for example SLBS00) and could benefit from a computer science perspective. Yet, I am aware of only a few serious results from TCS that try to touch on specific questions in ecology and evolution. The two directions that spring to mind are:

Livnat, A., Papadimitriou, C., Dusho, J., & Feldman, M.W. [2008] "A mixability theory for the role of sex in evolution" PNAS 105(50): 19803-19808. [pdf]

Valiant, L.G. [2009] "Evolvability" Journal of the ACM 56(1): 3.

The former applies idea from analysis of genetic algorithms to show a qualitative difference between the way sexual and asexual organisms behave in fitness landscapes, and has lead to follow ups that help justify observed modularity. The latter connects evolution and computational learning theory, to try to prove evolvability and impositibility results. It has influenced a small collection of papers, but mostly by other computer scientists.
Are there more results in these veins? Are their other deep/non-trivial applications of theoretical computer science to understanding ecology and evolution as it is studied by biologists?

Notes

I am not interested in general engineering related genetic or evolutionary algorithms results. Although this is a very interesting and exciting part of computer science, its connection to evolution as studied by biologists is often superficial. Sometimes (as in LPDF08) concrete connections are made, but most standard results are not of biological interest, and hence I am not interested in them in this post.

Bioinformatics is a nearby field, but it is also not what I am looking for. Although it can be used to reconstruct things like phylogenetic trees and thus help evolution/ecology, the theoretical CS aspects do not take centre stage. Here, the CS results seem to be mostly to perfect a tool that can be used largely as a black-box from within existing well established theories, and not to build or extend new biological theories.

I prefer results that use modern-ish and non-trivial aspects of computer science to influence biology at a theoretic (but still relevant to biologists) level. As such, I am not that interested in things like Chaitin's metabiology.

Related questions

Provable statements about genetic algorithms

Algorithmic lens in the social sciences

Sources for Algorithmic Evolutionary Game Theory

Computational complexity in quantitative finance


texts: polytime transformation from a graph to a set of binary strings

texts:
$d_H$ denotes the Hamming distance between two binary strings of the same size. The problem is stated as follows.
Given any undirected graph $(V, A)$, does there always exist a one-to-one correspondence $f : V \mapsto \Omega$, $f$ computable in polynomial time,
where $\Omega$ is a set of binary strings of the same size and such that $\exists \alpha > 0$, $\forall v_i, v_j \in V$,
$$d_H(f(v_i), f(v_j)) = \left\lbrace\begin{array}{ll}
\alpha & \mbox{ if } (v_i, v_j) \in A,\\
\mbox{some value strictly greater than $\alpha$,}& \mbox{otherwise.}
\end{array}\right.$$

For instance, if $(V, A)$ is a clique of size $3$, i.e., $V = \{v_1, v_2, v_3\}$ and $A = V \times V$, then such a function $f$ can be defined as follows:
$f(v_1) = 100$, $f(v_2) = 010$, $f(v_3) = 001$. We have $d_H(v_1, v_2) = d_H(v_2, v_3) = d_H(v_1, v_3) = 2$.

As another example, consider a line $(V, A)$ of size $3$, i.e., $V = \{v_1, v_2, v_3\}$ and $A = \{(v_1, v_2), (v_2, v_1), (v_2, v_3), (v_3, v_2)\}$, then such a function $f$ can be defined as follows:
$f(v_1) = 00$, $f(v_2) = 10$, $f(v_3) = 11$. We have $d_H(v_1, v_2) = d_H(v_2, v_3) = 1$ and $d_H(v_1, v_3) = 2$.


texts: Computational complexity and reductions to linear programming

texts:
My question is rather general, but I have not been able to find a satisfactory answer for quite a long time, and I wonder if there has been a research concerning these issues.

I have come over a relatively large number of optimization problems, that can be expressed as a Linear Programming problem, or as an Integer Linear Programming problem. Also decision problems could be expressed as LP or ILP, with a constant objective function (i.e., concerning only (in)feasibility). If a problem can be expressed as LP, then it is certainly in $\mathbf{P}$, since Linear Programming problems can be solved in polynomial time. On the other hand, problems that cannot be expressed as LP, but only as ILP, usually are $\mathbf{NP}$-complete, despite the fact that this is not a valid proof of $\mathbf{NP}$-completeness (there could be a polynomial algorithm not based on LP solving the problem).

So my question is: is there any known relation between the complexity of a problem and it's expressibility in the form of (integer) Linear Programming (except the obvious facts stated in the previous paragraph)? Moreover, I believe that there are inherently nonlinear problems that cannot be expressed in the form of LP nor ILP. Is there some known relation between their complexity and their expressibility in the form of some type of Nonlinear Programming problems? Are there any references dealing with similar problems?

Thank you in advance.


texts: Polynomial speedups with algorithms based on semidefinite programming

texts:
This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time.

I am still puzzling over the actual running time of algorithms that compute the solution of  a semidefinite program (SDP). As Robin pointed out in his comment to the above question, SDPs cannot be solved in polynomial time in general.

It turns out that, if we define our SDP carefully and we impose a condition on how well-bounded the primal feasible region is, we can use the ellipsoid method to give a polynomial bound on the time needed to solve the SDP (see Section 3.2 in L. Lovász, Semidefinite programs and combinatorial optimization).
The bound given there is a generic "polynomial time" and here I am interested in a less coarse bound.

The motivation comes from the comparison of two algorithms used for the quantum separability problem (the actual problem is not relevant here, so don't stop reading classical readers!).
The algorithms are based on a hierarchy of tests that can be cast into SDPs, and each test in the hierarchy is on a larger space, that is, the size of the corresponding SDP is larger.
The two algorithms I want to compare differ in the following tradeoff: in the first one, to find the solution you need to climb more steps of the hierarchy and in the second one the steps of the hierarchy are higher, but you need to climb less of them. It is clear that in the analysis of this tradeoff, a precise running time of the algorithm used to solve the SDP is important. The analysis of these algorithms is done by Navascués et al. in arxiv:0906.2731, where they write:

  ... the time complexity of an SDP with $m$ variables and of matrix size $n$ is $O(m^2 n^2)$ (with a small extra cost coming from an iteration of algorithms).

In another paper, where this approach to the problem was first proposed, the authors give the same bound, but they use the more cautious term "number of arithmetic operations" instead of "time complexity".

My question is two-fold:

Which algorithm/bound are Navascués et al. referring to?
Can I replace the expression "polynomial time" in Lovász with something less coarse (keeping the same assumptions)?


texts: Long-term data encoding, Phoenix Mars DVD

texts:
While browsing I've stumbled over the Phoenix Mars lander

http://en.wikipedia.org/wiki/Phoenix_(spacecraft)#Phoenix_DVD

and it says that the craft contains a DVD with all kinds of information on it.

Now my question would be: If the disc is made to last centuries or even millenia, how would one make sure that the digital information can be decoded in a future when all knowledge about present-day encoding must be assumed long forgotten?

I'm not even talking about building a working DVD player; if all else fails, take a strong microscope and extract the bits the hard way.

It's about, how would I, as a future scientist, interpret the bits such that the original meaning is restored, and how would I know that I've picked the right decoding? "Digital Memory Loss" has been recognized as a major problem already, and it's only been a few decades since we earnestly started producing (and forgetting!) mass quantities of digital information.


texts:
I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc).
I wonder whether someone might have an idea.

I'm looking for an operator T that can be applied to m-variate polynomials over a finite field.
When applied to a polynomial, the operator should yield a polynomial of not much higher degree. The operator should satisfy the following property:
for every m-variate polynomial $F$, and m univariate non-constant polynomials $g_1,...,g_m$, if you know $g_1,...,g_m$ and $F(g_1(t),...,g_m(t))$ for a parameter t, then you can also compute $TF(g_1(t),...,g_m(t))$. The operator should be non-trivial, in the sense that for a fixing $x_1,..,x_m$, the value $F(x_1,...,x_m)$ does not determine the value of $TF(x_1,...,x_m)$.

For $m=1$, the derivative operator gives exactly that:
By the chain rule
$(F(g(t)))' = F'(g(t))\cdot g'(t)$, which implies that
$F'(g(t)) = (F(g(t)))'/g'(t)$.
My question is whether there is an operator that works for general m.


texts: Discovering a graph with minimal oracle queries

texts:
I have a transitive DAG G which is a subgraph of an unknown DAG R.  (The nodes are the same in G and R, but R may have edges not in G.)  I can determine the presence of a given edge in R by an oracle query.

Many natural questions come to mind.  I've found it's often more useful to give several than just one—I wouldn't want to reject the answer I don't yet know is the right one by being over-specific upfront.

What is the minimum query complexity for determining R, in terms of the number of nodes and number of edges in G?
What is the minimum query complexity for proving that G = R if that is the case?
Give an algorithm for determining which edge to query at each step?  Ideally it would have decent (less than exponential... hopefully polynomial) time requirements in addition to minimizing queries.

The algorithms used may be adaptive.

Here's (transitive reduction of) an example of a graph of the sort I'd test.  As a simpler version of #1 or #2, what's the complexity for this graph?
sample graph http://crg4.com/G.png


texts: Efficient flow problem for a complex integer program

texts:
I have a bunch of marbles each with some weight (they can also have negative weights). I want to pick the nodes such that the weight is maximized. The only rule is that if I pick X1 and X2 I have to pick X1,2 as well. Also if I pick X1,X2,X3 then I have to pick not only X1,2 and X2,3 and X1,3 but also X1,2,3. The other thing is that I cannot pick X1,2 unless I pick both X1 and X2.

It is easily solvable by integer programming but I am wondering if there is any network flow solution that is more efficient?

Some clarification:
for every X1 and X2 there is always a X1,2 marble (but may have 0 or negative weight).

The input is just the list of marbles and their weights [(X1:W1), (X2:W2), (X1,2:W1,2),...]

More Updates
Suresh pointed out that the input size is very large and I agree. In the problem that I am solving I only have 4 layers. I mean I have up to X(i,j,k,l) and everything above it with 5 or more subscripts has a weight 0.


texts: Questions on "Improved Sketching of Hamming Distance with Error Correcting" by Porat and Lipsky

texts:
What is the proof of lemma 4.3 in this paper?

http://u.cs.biu.ac.il/~porately/papers/submission_24.pdf

That is, how does it follow from 4.1 and 4.2?

Also, why is the constant 8 necessary? How is it used in a way that 1 wouldn't be enough?

There's an LNCS version too, but it also doesn't spell out the proof. There are slides, but they don't seem to be stand-alone:

www.cs.ucr.edu/~stelo/cpm/cpm07/improved_shetcking_porat.ppt


texts:
In Graphic TSP, you are given an unweighted undirected graph $G$ and the goal is to find a shortest tour in $G$ that visits every vertex at least once. Note that this is NOT same as finding a hamiltonian circuit in $G$. My questions are :

  What is the complexity of Graphic TSP on bounded treewidth graphs ?

Are there any special cases of Graphic TSP with non-trivial polynomial-time algorithms ?


texts: Is integer factorization an NP-complete problem?

texts:
Possible Duplicate:
  What are the consequences of factoring being NP-complete?

What notable reference works have covered this?


texts: Random 3-SAT: What is the consensus experimental range of the threshold?

texts:
The critical ratio of clauses to variables for random 3-SAT is more than 3 and less than 6, and seems to be commonly described as "around 4.2" or "around 4.25".  Mezard, Parisi, and Zecchina prove (in the physics sense) that the critical ratio is 4.256, whereas the first and third authors prove that it is 4.267.

What is the range of values that the critical ratio could possibly take?

The motivation for me asking this question is that if the ratio could be $2+\sqrt{5} \approx 4.236$, then the standard reduction of 3-SAT to NAE-3-SAT (transforming $m$ clauses and $n$ variables into $2m$ clauses and $m+n+1$ variables) gives a ratio of $\phi$, which seems unlikely but would be pretty cool.


texts: Sum of Independent Exponential Random Variables

texts: Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - e^{-x/\lambda_i}$. Let $Z = \sum X_i$. Can we prove bounds of the form $Pr(|Z-\mu_Z|>t) < e^{-t^2/\sum (\lambda_i)^2}$. This follows directly if we use the variance form of chernoff bounds and hence I believe is true , but the bounds that I read require bounded-ness or have some dependence on bounded-ness of the variables. Could someone point to me to a proof of the above ?


texts: On the Bakery Mutual exclusion Algorithm

texts: Lamport's Bakery Algorithm is one of the most elegant algorithms for mutual exclusion. The beauty of it is that it works even when the underlying system only provides a weak form of registers called safe registers. Informally, when a read operation of a safe register is concurrent with a write to the register by another process,  the read may return any value in the domain of the register. I recently read that the Algorithm can be simplified if we want to ensure mutual exclusion with just atomic registers. Atomic registers being those in which a read of the register always returns the latest written value of the register i.e. operations on the register can be linearized. I would expect that the algorithm can be simplified for atomic registers since given reading and writing are atomic, devising a mutual exclusion algorithm must be simpler. I cannot however seem to think of a simplification to the original algorithm for atomic registers.


texts: Why isn't it possible to recover/resume after an Exception?

texts:
I know that Exceptions as a means of flow-control is generally frowned upon.

But in my opinion, Exceptions have little value short of the flow-control aspect - after all, if you didn't want the program to continue, you could just output an error-message an terminate the program.

Exceptions, on the other hand, provide a means of reporting errors "locally", allowing a service/component to fail, and a consumer to handle the failure - and regardless of how you look at that, it is a means of controlling the flow of the program.

So here's my question - over the years, I have frequently wondered, why isn't it possible to resume execution after an exception is thrown?

Now, you wouldn't want to allow any consumer to resume after an Exception thrown by any other component, as that component was probably not designed to resume after a throw-statement, which would lead to unpredictable results.

So let's say there's a supertype of Exception called Interrupt, that allows this behavior. An Interrupt would behave just like an Exception in every respect, except that by throwing an Interrupt, you indicate that the component is ready and able to resume execution after the throw-statement, and that the stack needs to be preserved either until (A) the Interrupt has been handled, or (B) the program exits with an error-message.

Let's say we add a new "resume" statement to the language, to be used inside a traditional "catch" block - if you catch an Interrupt, and issue a "resume" statement, control would return to the point from where the Interrupt was originally thrown, and execution would continue from the next statement.

I've presented this idea in other circles, and I'm met with a lot of resistance, but no clear argument as to why this is not a good idea.

To me, it seems like a natural extension of the idea of exceptions - there are plenty of cases where this could be useful, for example while enumerating a sequence, e.g. in a function that "yields" one result at a time; an unexpected condition could occur while producing one of these results, and you may want the calling code to decide whether or not it makes sense to continue producing more results.

An exception does not allow for that.

Let's say this function throws an interrupt instead - if so, the calling code now has a chance to look at that and decide whether to resume execution (as if the exception never occurred) and produce more results, perhaps log the condition and then resume, or perhaps throw an exception, or perhaps re-throw the interrupt in case it can be handled up-stream.

I'm sure I'm not the first person to have this idea, but I would like to understand why this isn't feasible or why it's not a good idea.

(PS: I'm a programmer, not a scientist, so go easy on me.)


texts:
I am currently trying to find EXPSPACE-complete problems
(mainly to find inspiration for a reduction), and
I am surprised by the small number of results coming up.

So far, I found these, and I have trouble expanding the list:

universality (or other properties) of regular expressions with exponentiation.
problems related to vector addition systems
unobservable games (see for instance this blog)
some fragment of FO-LTL, in On the Computational Complexity of Decidable Fragments of First-Order-Linear Temporal Logics

Do you know other contexts when EXPSPACE-completeness appears naturally?


texts: Collaborative tools for dummies/professors

texts:
Suppose that coauthors from two or more different institutions are writing a paper in latex, and would like to do better than repeatedly emailing drafts back and forth.

They realize they can open for free a dropbox account, share the password, and synch the version of the paper on their computer with the one on dropbox. If two people are simultaneously editing the same section, however, they'll overwrite each other changes.

They have also heard that version-control systems like SVN and Git have tools to merge concurrent changes, which work reasonably well. The documentation of these products, however, is rather hard to read, and it is more focused on how to undo changes and how to manage different "branches" rather than on the basic needs of coauthors writing a paper.

Is there a simple step-by-step exposition on how to use a version-control system in this setup:

 central repository
 local copies
 "smart" merge
 no branches

?

Of the standard version-control systems, which one is the easiest to use? (We are talking theoretical computer science professors here.)

Are there even simpler tools that  only do synch with smart merge, without version control?

Conversely, do people who use version-control systems to even write a single-authored paper really feel that the unlimited-undo capability is worth the extra complexity?


texts:
Preamble

Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than the latter, but Goldwasser and Sipser showed that they have the same power (with respect to language recognition). Hence, in this post, I'll used the two concepts interchangeably.

Let $IP[k]$ be the class of languages admitting an interactive proof system with $k$ rounds. Babai proved that $IP[O(1)] \subseteq \Pi_2^P$. (A relativizable result.)

At first, it was not know whether unbounded number of rounds can increase the power of IP. In particular, it was shown to have contradictory relativizations: Fortnow and Sipser showed that for some oracle $A$, it holds that $coNP^A \not\subset IP[poly]^A$. (Therefore, relative to $A$, $IP[poly]$ is not a superclass of $PH$.)

On the other hand, the following paper:

Aiello, W., Goldwasser, S., and Hastad, J. 1986. On the power of interaction. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (October 27 - 29, 1986). SFCS. IEEE Computer Society, Washington, DC, 368-379. DOI= http://dx.doi.org/10.1109/SFCS.1986.36

shows that, for some oracle $B$, we have $IP[poly]^B \not\subset PH^B$. (Therefore, $IP[poly]^B \neq IP[O(1)]^B$ since as stated above, the latter is a subclass of $\Pi_2^{P,B}$.)

The Question

The paper by Aiello, Goldwaseer, and Hastad (cited above) states:

  The techniques employed are extensions of the techniques for proving lower bounds on small depth circuits used in [FSS], [Y] and [H1].

where [FSS], [Y] and [H1] are:

[FSS] Furst M., Saxe J. and Sipser M., "Parity, Circuits, and the Polynomial Time Hierarchy," Proceedings 22nd Annual IEEE Symposium on Foundations of Computer Science, 1981, 260-270.

[Y] Yao A. "Separating the Polynomial-Time Hierarchy by Oracles," Proceedings of 6th Annual IEEE Symposium on Foundations of Computer Science, 1985, 1-10.

[H1] Hastad J. "Almost optimal lower bounds for small depth circuits," Proceedings of 18th Annual ACM Symposium on Theory of Computing, 1986, 6-20.

I found the papers very old and extremely hard to follow. I read Chapter 14 of Arora & Barak's book, yet apparently it does not cover everything I need.

  What references on "Circuit Lower Bounds" do you suggest?

(I specially need survey-like references; those which are newer and do not need a lot of expertise are more preferable.)


texts:
It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, Nishizeki, and Saito, J. Inform. Proc. 1980) or to test whether a Hamiltonian cycle exists in a 4-regular graph, even when it is the graph formed by an arrangement of Jordan curves (Iwamoto and Toussaint, IPL 1994).

For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?

The particular case I am interested in is 6-regular graphs, with the additional condition that the graph have an odd number of vertices. If this case could be shown to be NP-complete (or polynomial) it would have impact in a graph drawing problem described in http://arxiv.org/abs/1009.0579 . The "odd number of vertices" condition is because what I really want to know is, for 6-regular graphs, whether the graph contains either a Hamiltonian cycle or a bipartite 2-factor; but having an odd number of vertices eliminates the possibility of a bipartite 2-factor leaving only the possibility of a Hamiltonian cycle.


texts: Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al

texts:
Trying to understand a paper titled KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation by M.Elad, et al;
my take of section IV.C. detailed description of KSVD, is that we have an objectiove function which we wish to minimize with respect to two variables, D (which is called the dictionary) and X (the coefficient matrix.
$$\min_{X,D} \{||Y-DX||_F^2\} \quad \textrm{  subject to} \quad \forall i, ||x_i||\leq T_0$$
One method of doing this is to divide it to two stages, sparse coding and dictionary update. In the sparse coding stage, we assume D is fixed and solve the above problem w.r.t X using a pursuit algorithm. Then we must update the dictionary to better fit our data using the coefficient matrix from previous stage.  In the update stage, we keep both X and D fixed and only one column of D and its corresponding row in X remains in question. After simplifying the objective function and decomposing the multiplication DX to the sum of k rank-1 matrices, one might suggest to use svd. But that would ruin the sparsity of X, so wee need to set constraints. At this point, the authors define some variables and use them for setting constraints. The problem is, I don't understand what is meant by this statement:

examples that use the atom $d_k$,i.e. those where $x_T^{k} (i)$ is
nonzero.

Any clarifications would be appreciated.


texts: Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix?


texts:
One of the most practical consequences of the "Curry-Howard-Lambek" correspondence is that the syntax of many lambda-calucli/logics can be used to perform constructions in a sufficiently structured category.

For instance, Synthetic Differential Geometry has models in topoi that contain and embedding of the category of smooth manifolds, so you can use higher-order logic to construct smooth functions and solve differential equations.

As another example, in this paper, they notice that "step-indexing" is really just working with presheaves over the naturals (another topos), so you can use the syntax of higher order logic to define step-indexed logical relations without the tedious manipulation of steps.

Finally, Andrej Bauer shows in this MO question that you can do a lot with the "internal language" of the topos of graphs.

My question is, has anyone realized this vision literally in a theorem prover?
For instance, if I show that a category I care about is Cartesian Closed, I could then move to "internal mode" where I write lambda-calculus syntax (with some model-specific axioms) and then can move back to "external mode" and manipulate them as objects in my model?

In the extreme I would even want topos theory and higher-order logic, so I could write my step-indexed logical relations without steps, or teach classical mechanics with a theorem prover using SDG. This seems to me to be a very powerful idea as someone could implement extensional dependent type theory once and provide nice tooling and then use it with wildly different applications as described above.


texts: Descriptive Complexity characterzation of BPP

texts: We know of descriptive complexity characterizations of classes such as P, and NP, which use First Order logic, and operators. Does BPP have a characterization under descriptive complexity, too(any reference known?)?


texts: Are there good implementations for easy subclasses of NP-hard graph problems

texts:
Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource on graph classes http://www.graphclasses.org).
How can I know if G belong to some of these classes? Do I need to read and code algorithms from each paper to check it? Or there exists already an implementation for most of these algorithms?

Thanks in advance.

Edit: Maybe it is too broad my question but in some sense I want to know if someone is trying to code all these theoretic algorithms.
As a reformulation of my question: Does exist some project with the goal of unify all this theoretical knowledge in practical application (real code implementation)?


texts: When can convex optimization be considered to be exactly solvable?

texts:
If one is trying to find the global minima of a convex function using gradient descent then one will get a run-time which is a function of $\epsilon >0$ where $\epsilon$ measures the accuracy of the solution. Here apart from the error coming due to the finiteness of the run-time we are also getting an error from the machine precision.

But I guess this is not the situation when say one is using an LP solver to solve a LP which we can consider to be giving us an ``exact" answer in polynomial time. Such solvers would typically use some pivoting rule based simplex method. Here the only source of $\epsilon$ is I guess the machine precision and not algorithmic.

What is the mathematically rigorous way to distinguish between the above two situations?
If we were to say use gradient descent to solve a LP then can there be a sense in which we could say that it might work "faster" than calling a LP solver?


texts: Hardness of approximation without the PCP theorem

texts: An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any case where the hardness of approximation result was first proved using the PCP theorem, i.e., the result was not known before, but later a more direct proof was found that does not depend on PCP? In other words, is there any case where PCP appeared necessary first, but later it could be eliminated?


texts: Determine the minimum number of coin-weighings

texts:
In the paper On two problems of information theory,  Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.

More formally:

  The false coins have a smaller weight than the right coins; the
  weights $a$ and $b < a$ of both the right and false coins are known. A
  scale is given by means of which any number $\leq n$ of coins can be
  weighed together. Thus if we select an arbitrary subset of the coins
  and put them together on the scale, then the scale shows us the total
  weight of these coins, from which it is easy to compute the number of
  false coins among those weighed. The question is what is the minimal
  number, $A(n)$ of weighings by means of which the right and false coins
  can be separated?

The trivial lower bound they initially provide is:

$n / \log_2 (n + 1)$.

This isn't hard to see why through various information-theoretic or combinatorial arguments. The problem is how to construct such sets to do these weighings? Are there algorithms that utilize a constructive proof to achieve these lower bounds without relying on randomness? Are there randomized algorithms that achieve these bounds?


texts:
I'm a grad student in math with a solid background in logic. I've taken a year-long graduate course in logic together with graduate courses on finite model theory and another on forcing and set theory. Most CS texts seem to assume only a very modest background in logic, which mostly covers basics of propositional logic and first-order logic.

I'd like to get some pointers on where to go for CS applications where heavier material from logic is being used. One interest of mine would be type theory and formal methods in general. Could anyone suggest some good readings past the introductory books on model checking and programming languages?


texts: Random unbalanced bipartite graphs are good small set expanders

texts:
My question is about small set expansion properties of random unbalanced bipartite graphs.

Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$ an $(n,m,d,\delta)$-expander if the graph has $n$ left vertices, $m$ right vertices, every left vertex has degree $d$, and for every subset $S$ of left vertices having size at most $\delta n$, we have $|\mathcal{N}(S)|>0.75 d|S|$. Here $\mathcal{N}(S)$ denotes the set of neighbours of $S$.

Consider a random $d$-left regular graph, where the neighbourhood of each left vertex $i$ is a random subset $V_i$ of $d$ vertices on the right, and the $V_i$'s are chosen independently of each other. For small $\delta$ independent of $n$, and $d=O(\log(1/\delta))$ and $m=O(n\delta\log (1/\delta))$, a random $d$-left regular graph is an $(n,m,d,\delta)$-expander with high probability for sufficiently large $n$. We can prove this by computing $Pr[\mathcal{N}(S)\subset T]$ for $S,T$ with $|T|=0.75 d|S|-1$ and then taking a union bound over possible $S,T$ pairs.

If we force $d$ to be a constant independent of $n$, and $m$ to grow linearly with $n$ while having $m<n$, what are the best parameters we can hope for (in the sense of having small $d$ and $m$)? Is the above existence result order-optimal? If we are also interested in obtaining the best constants (and not just order optimality), what is known?

Also, is there a different proof/proof technique of existence of $(n,O(n\delta\log(1/\delta)), O(\log(1/\delta)),\delta)$ expanders? I tried to compute the expected size of the neighbourhood of $S$ and concentrate it using Chernoff-type bounds, but the parameters so obtained are worse.


texts: (False?) proof for computability of a function?

texts:
Consider $f(n)$, a function that returns 1 iff $n$ zeros appear consecutively in $\pi$. Now someone gave me a proof that $f(n)$ is computable:

  Either for all n, $0^n$ appears in $\pi$, or there is a m s.t. $0^m$ appears in $\pi$ and $0^{m+1}$ does not.
  For the first possibility $f(n) := 1$; For the second one $f(n) := 1$ iff $n \leq m$, 0 otherwise.

The author claims that this proves computability of $f(n)$, as there exists an algorithm to compute it.

Is this proof correct?


texts: SAT formula specifying that exactly $k$ of $N$ boolean variables are active using less than $N$-choose-$k$ terms

texts:
Is there a way to express the condition that exactly $k$ of $N$ boolean variables are active without writing a disjunction of $N$-choose-$k$ terms, i.e., all possible configurations of the $N$ variables where exactly $k$ are active? Is the same true for specifying that at least $K$ of the $N$ boolean variables are active?

I'm aware that this is a problem dealt with in theoretical computer science but I couldn't find any references.


texts:
In the classic Network Flows: Theory, Algorithms, and Applications book (pages 80/81) the flow decomposition theorem is stated as follows:

Every nonnegative arc flow x can be represented as a path and cycle flow (though not necessarily uniquely) with the following two properties:
(a) Every directed path with positive flow connects a deficit node to an excess node
(b) At most n+m paths and cycles have nonzero flow; out of these at most m cycles have nonzero flow with m the number of edges and n the number of nodes in the graph

My question is, if the theorem can be formulated more strongly modifying point b as follows:

(b) At most m paths and cycles have nonzero flow

My question arises as going through the lecture nodes of a more modern optimization course at Stanford, I find the flow decomposition theorem formulated exactly with this "stronger" assertion (page 58 with proof here or a similar theorem here).
Going through the proofs in the lecture nodes and the book, I find the stronger formulation justified. Especially in Network Flows: Theory, Algorithms, and Applications the following argument is given for their m+n bound on paths:

Now observe that each time we identify a directed path, we reduce the excess/deficit of some node to zero or the flow on some arc to zero;

As I understand it, reducing the excess/deficit of some node to zero implies setting the flow on some arc to zero, as the excess/deficit flow of a node has to go/come over an arc whose flow is now set to zero. This however would imply bounding the number of paths with m instead of n+m, as each construction of a flow-path would remove one edge and not one edge or node from the graph.
Have I misunderstood the proof and are the lecture nodes from Stanford wrong? Do you know other books which one could possible cite for the stronger version of the flow decomposition theorem?
Thank you!
Note: In this question with the very promising title, a different question has been asked. It took the theorem from one of the aforementioned Stanford notes, and in the answers the correctness of it was discussed albeit for different reasons.


texts: Is it possible to simulate a regular expression using a single stack?

texts:
I understand that a regular expression can be converted to an equivalent DFA which can then be simulated. However, is it possible to simulate the regular expression directly with the aid of a stack ? I believe that by pushing the alphabets onto a stack and expanding any composite expression such as (r1.r2) into its constituent expressions one can parse against the regular expression but I am unable to figure out how to deal with the | operator . As an example of what I am thinking consider the following regular expression :

a.b.(c.d)*.e

The string abe can be parsed against the regular expression in the following way using a stack:

Stack:             alphabet action
|e|(c.d)*|b|a      a        match: pop off the stack
|e|(c.d)*|b        b        match: pop off the stack
|e|(c.d)*          e        composite element , expand
|e|(c.d)*|d|c      e        no match , but expanding from a composite under kleene closure , pop off
     ^
|e|(c.d)*|d        e        no match , but expanding from a composite under kleene closure , pop off
     ^
|e|(c.d)*          e        stack top not an alphabet, pop off
|e                 e        match : pop off from stack


texts: Numerical accuracy of superpositions in quantum computers

texts:
I am new to the topic of quantum computers (though I am very familiar with both quantum and computers, and I have studied Shor's paper about his eponymous algorithm at some point). Still, I have the following question, which pertains to the practical realizability of quantum computers and is probably related to qubit error correction:

To set up the question, note that classical computers are typically built on the principle that information is best encoded digitally, e.g. by two discrete bits 0 and 1. Every now and then, however, somebody claims that analog computing is better, where information is encoded in a continuous quantity $a \in [0,1]$, e.g. a voltage between $0V$ and $1V$. If this quantity were an exact real number, then it is well known that we could solve many problems really fast. However, such schemes do not work in practice, because continuous quantities are always subject to measurement error and do not allow arbitrary precision.

Quantum computers, on the other hand, rely on the principle that information is encoded in qubits $|0\rangle$, $|1\rangle$ and arbitrary superpositions thereof, like $0.6|0\rangle + 0.8|1\rangle$. In light of the above remark about analog computers, the appearance of arbitrary precision real numbers in the superposition raises a red flag. Of course, typical models of quantum computation account for this problem by allowing only a fixed (select) set of universal gates (e.g. the Hadamard gate and a few others). Then, the precision required in the coefficients of the superposition need not be larger than the number of gates used in the computation.

However, this still leaves open the question of what happens if we increase the number of gates. Then, the precision needed to represent the coefficients of the superposition will also increase. But due to unavoidable random fluctuations, it seems inevitable to me that an intermediate calculation might use slightly inaccurate results, e.g. one qubit may take the value $0.0447|0\rangle + 0.999|1\rangle$ instead of $1.0|1\rangle$ as desired. Further manipulations with gates may distort the end result drastically.

  How can I make sure that errors in intermediate qubit results do not propagate?

The problem I perceive is that the precision per qubit superposition is fixed, and may at some point be too low to accommodate more gates, very similar to the problem of precision of an analog computer.

Apologies if this is a standard question in a misguided disguise, this has probably been answered already. I would appreciate any pointer.

EDIT: Let me try to reformulate my question. Consider the following model of computation: Just like with a quantum computer, each qubit is a superposition $a|0\rangle + b|1\rangle$. However, we now postulate that the computer has only finite precision, i.e. that the superposition coefficients $a$,$b$ must be contained in a discrete set of values, for example $a,b,\in \{0.1,0.2,\dots,1.0\}$. This is equivalent to a "rounding error", where each unitary operation "rounds" the coefficients to the ones from the discrete set of values. Clearly, this model of computation is entirely classical, as each qubit can only take a finite number of superpositions, which we can encode by a classical bit string.

  How do quantum computers go beyond the "finite precision coefficients" while avoiding the "analog computers with infinite precision are too powerful" problem?


texts: Are there any cases where quantum has given insight for classical algorithms?

texts: To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum algorithms?


texts:
There are two well-known mapping reducibilities: polytime and logspace. In both cases, the length of the output string can be at most polynomial in the length of a given input string. If we allow to use more space (super-logspace), then the length of the output string can be super-polynomial.

Therefore, it seems interesting to me to ask whether this blow-up helps us to reduce some difficult problems to some easier problems when using super-logspace $ \left(\omega(\log n) \right) $. I am not interested in the "cheap" tricks such as padding.

More generally, is there any literature on super-logspace (or super-polynomial) mapping reducibility?

DEFINITION

Language $ \mathtt{A} $ is $s(n)$-space mapping reducible to language $ \mathtt{B} $, shown as $ \mathtt{A} \le_{m}^{s} \mathtt{B} $, if there exists a $ s(n) $-space DTM $ \mathcal{D} $ outputting $ f_{\mathcal{D}} (w) $ for a given input $ w $ such that

\begin{equation*}
 w \in \mathtt{A} \mbox{ if and only if } f_{\mathcal{D}} (w) \in \mathtt{B},
\end{equation*}

where $ \mathcal{D} $ has a two-way read-only input tape, a two-way read/write work tape, and a one-way write-only output tape.

UPDATE:
I have found an answer to my own question. But, I am still interested in further results.


texts: The complexity of recognizing optimal set systems for the V-C dimension

texts:
The Vapnik-Chervonenkis dimension of a set system $(X,\mathcal S)$ with ground set $X$ is the maximum size of a set $X'\subseteq X$ such that for each subset $X'_i\subseteq X'$, there is a set $S_i\in\mathcal S$ with $S_i\cap X'=X'_i$.

The following decision problem is then natural:

  VC DIMENSION
  Input: a set system $(X,\mathcal S)$ and an integer $k$.
  Task: decide whether the VC dimension of $(X,\mathcal S)$ is at least $k$.

Since there are $2^{|X'|}$ subsets of $X'$, we have $|X'|\leq\log_2(|\mathcal S|)$, and hence VC DIMENSION can be solved in time $O\binom{|X|}{\log_2(|\mathcal S|)}$. For the hardness side, VC DIMENSION is LOGNP-hard (see here). However, I wonder whether something is known for the following specific case:

  My question: what is the complexity of deciding whether a given set system $(X,\mathcal S)$ has VC dimension exactly $\log_2(|\mathcal S|)$?


texts: Examples for derandomization via small sample spaces

texts:
I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises.

I'm trying the technique of "Derandomization" for some algorithms, and I find some samples using the derandomization via small sample spaces and feel very interested.

To deepen the impression on derandomization via small sample space, I want to see more papers using that.


texts:
What is the recommended citation style for use with CS (and related) publications?

I tried looking at submissions at http://arxiv.org/archive/cs but all of them seem to use different citation styles.

I'm doing an academic project and I'm writing a project report for the same. So, is there a (possibly 'standard') citation style that is preferred over other citation styles (such as those listed at  http://en.wikipedia.org/wiki/Wikipedia:Citing_Wikipedia#Examples) for CS publications (like research papers, project reports, books, presentations etc.)?
Or, is it a matter of personal choice/preference (and sticking to it forever)?


texts: Regular expressions of prefixes/suffixes

texts:
It is well-known that star-free regular expressions, which are defined by the grammar

$r::= a \mid r \cdot r \mid r \cup r \mid \neg r \mid \varepsilon \mid \emptyset$

where $a$ belongs to a finite alphabet $\Sigma$ and $\varepsilon$ is the empty string,
have their language-emptiness problem which is non-elementary (more precisely, tower-complete), being negation the "difficult case".

However, what can we say about the same problem for this kind of regular expressions?

$r::= a \mid r \cdot \Sigma^+ \mid \Sigma^+\cdot r \mid r \cup r \mid \neg r \mid\varepsilon \mid \emptyset$

Here, we still have negation, and still no Kleene star, as $\Sigma^+$ can be "rewritten" as $\neg(\emptyset \cup \varepsilon)$, but concatenation is weakened: in fact, $r \cdot \Sigma^+$ and $\Sigma^+\cdot r$ represent right-/left-extensions of $r$ with any (non-empty) string.

Does anybody know the complexity of this problem? Is it elementary? Do you know similar problems/connected literature?
Thanks.


texts: What is the curve of "search vs. insert"

texts:
Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time.

With this oracle for comparison, we can consider two data structures, of nodes, holding numbers, and pointers to each other:

Unordered Linked List:
Insertion $O(1)$
Search $O(n)$

Balanced Binary Tree: Insertion $O(\log n)$ , Search $O(\log n)$

My question, do there exist data structures that carry an intermediary of running times between these? For example assuming that search takes $O(\sqrt{n})$ time what is the fastest insertion time, (does there exist a structure that supports $O(1)  \ \text{insert}$ or something more exotic such as $O(\log \log \log n)$)

The most general form of the question can be stated as:

Assuming insertion $O(\omega(n))$ , then how can we bound search time $s(\omega(n))$, and vice versa in the comparison model?

Conjecture

The tightest bound one can have is

Search:   $O( \frac{n}{\alpha(n)} + \log \alpha(n) ) $

Insert:  $ O (\log \alpha (n)) $

For choice of $\alpha(n)$ lying asymptotically between $O(1) ... O(n)$


texts: Genetic Algorithm to Draw a Graph? Position assignment problem

texts:
I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large).

I have a directed graph (a flow-chart) that I would like to visualize on 2-D plane in a way that it is very clear, understandable and easy to read by human-eye. Therefore; I will be assigning (x,y) positions to each vertex. I'm thinking of solving this problem using simulated annealing, genetic algorithms, or any such method you can suggest

Input: A graph G = (V,E)
Output: A set of assignments, {(xi, yi) for each vi in V}. In other words, each vertex will be assigned a position (x, y) where the coordinates are all integers and >= 0.

These are the criteria that I will use to judge a solution (I welcome any suggestions):

Number of intersecting edges should be minimal,
All edges flow in one direction (i.e from left to right),
High angular resolution (the smallest angle formed by two edges
incident on the same vertex),
Small area - least important.

Furthermore; I have an initial configuration (assignment of positions to vertices), made by hand. It is very messy and that's why I'm trying to automate the process.

My questions are,

How wise would it be to go with local search techniques? How likely
would it produce a desired outcome?
And what should I start with? Simulated annealing, genetic algorithms
or something else?
Should I seed randomly at the beginning or use the initial
configuration to start with?
Or, if you already know of a similar implementation/pseudo-code/thing, please point me to it.

Any help will be greatly appreciated. Thanks.


texts:
Main/General Question

Let $L$ be a language. Define the languages $L_i$ with $L_0 = L$ and
$$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$$
for $i \geq 1$. Consider $\hat{L} = \bigcup L_i$. So, we repeatedly "embed" $L$ into itself to obtain $\hat{L}$.

Has $\hat{L}$ been studied? Does it have a name?

Examples/Motivation

As requested in the comments by here are some examples to better illustrate what $\hat{L}$ is. Then since no one (so far) seems to have seen this notion I will discuss my motivation for looking at it.

Klaus Draeger beat me to adding examples. I'll put those examples from the comments here for increased visibility since they are good examples.

If $L$ is a unary language, then $\hat{L} = L^+$ (and hence is regular).

If $L = {ab}$, then $\hat{L}$ is the Dyck language.

Here is a alternative way to think of $\hat{L}$. Given a language $L$ over an alphabet $A$ we play the following game. We take any $w \in A^*$ the try to reduce $w$ to the empty string $\epsilon$ by repeatedly removing subwords that are in $L$. (Here we need to by a little careful how we treat the empty string itself to make sure that this is equivalent to the definition above, but this is morally correct.)

Originally I came the define $\hat{L}$ by considering deleting powers in words. Take $L = \{w^3 : w \in A^*\}$ to be the language of cubes over the binary alphabet $A = \{a,b\}$. Then $aaabaabaabbabab \in \hat{L}$ and we can consider the following "$L$-deletion"

$$a(aabaabaab)babab \to ababab \to \epsilon.$$

Observe not all deletions will work

$$(aaa)baabaabbabab \to baabaabbabab$$

and we are stuck with a cube-free word. So, there is another notation of "strongly $L$-deletable" which in general does not coincide with $\hat{L}$.

One final example, if $L$ in the language of squares over the binary alphabet $A = \{a,b\}$, then $\hat{L}$ is the strings with both an even number of $a$'s and an even number of $b$'s. Clearly this condition is necessary. One way to see it is sufficient is to consider deleting squares and recall every binary word of length 4 or great has a square. Here $\hat{L}$ is regular.

For larger alphabets this type of argument fails since there are arbitrarily long square-free words. With alphabets of size $k \geq 3$ I can show $\hat{L}$ is not regular using Myhill-Nerode and the fact there are arbitrarily long square-free words, but I have not been able to say much more. I was hoping looking at it in this more abstract way could shed some light on the situation (and this more abstract definition seems interesting in its own right).


texts: Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?

texts:
I need to use the following well-known result in my paper:

  Let $X$ be a set of $n$ points in $\mathbb{R}^d$. Then $(X,\ell_2^d)$ embeds isometrically in $\ell_p^\binom{n}{2}$ for all $p \geq 1$.

What is the best reference to cite for this? I found a result which is nearly identical (but doesn't include the $\binom{n}{2}$ dimension bound) in some lecture notes from Michel Goemans, but I'm (a) unsure if I can cite lecture notes in a scientific publication, and (b) still in need of an $O(n^k)$ bound on the dimension.


texts: Why is it so difficult for a computer to prove something?

texts:
This may be considered a stupid question. I am not a computer science major (and I'm not a mathematics major yet, either), so please excuse me if you think that the following questions display some major erroneous assumptions.

While there are plans to formalize Fermat's Last Theorem (see this presentation), I have never read or heard that a computer can prove even a "simple" theorem like Pythagoras'.

Why not? What is (/are) the main difficulty(/ies) behind establishing a fully autonomous proof by a computer, aided only by some "built-in axioms"?

A second question I would like to ask is the following: Why are we able to formalize many proofs, while it is currently impossible for a computer to prove a theorem on its own? Why is that "harder" ?


texts: What Lecture Notes Should Everyone Read?

texts:
There has been several questions with the same scheme as this one:

What papers should everyone read
What books should everyone read
What are the recent TCS books whose drafts are available online
what videos should everybody watch

I was reluctant to post yet another one, but Jeff Erickson's lecture notes on algorithms changed my mind. I thought: Oh my! All these years and I haven't seen these excellent notes!

So, I thought there might be other great lecture notes, which are really worth reading. So, for each computer science subfield (data structures, algorithms, theory of computation, computational complexity, cryptography, etc.), recommend the superb lecture notes of your choice, and say why you think it excels.

One simple rule to keep it tidy: One answer per each subfield. (This will be a community wiki, so you can edit existing answers, and add your recommendation.)


texts: Poly-time Algorithm for Non-Linear Optimization

texts:
As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this notion.

Let $\vec{x}^T Q\vec{y} \geq \vec{d}$ be a system of multilinear constraints ,where $\vec{x},\vec{y} \in \mathbb{R}_{+}^n$

Question:
Under some limitations on the matrix $Q$, can the task of minimizing(maximizing) a function $f(\vec{x},\vec{y})$, be solved within poly-time ,or is there any case where this optimization is NP-hard ?


texts:
Arora and Barak's book presents factoring as the following problem:

$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$

They add, further in Chapter 2, that removing the fact that $p$ is prime makes this problem NP-complete, although this is not linked to the difficulty of factoring numbers.  It looks there can be a reduction from SUBSETSUM, but I got stuck finding it.  Any better luck around here?

EDIT March 1st: The bounty is for $NP$-completeness proof using deterministic Karp (or Cook) reduction.


texts:
For any language $L$ over $\Sigma^*$, define
$$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$$
In words, $L_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $xy\in L$.

An exercise in Sipser's book asks to show that $L_{1/2}$ is regular whenever $L$ is. I have seen two distinct solutions, and both involve an exponential blow-up of states.

Question: can anyone construct a family of languages $\{L_n\}$ such that the canonical automaton for $(L_n)_{1/2}$ is significantly (say, exponentially) larger than that for $L$? My best efforts so far only increase the state size by $+1$!


texts: Dynamic shortest path data structure for DAG

texts:
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.

I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed vertex $s$ to a fixed vertex $t$ in $G$.


texts: How are real numbers specified in computation?

texts: This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real numbers are specified as input.  E.g., when it's stated that LDT has certain polynomial lower bounds, how are the real numbers specified when they are treated as input?


texts: Closest Vector Problem with sparse basis and target vector

texts:
The Closest Vector Problem (and related problems) is random self-reducible and in general is NP-Hard, making it a useful tool in cryptography research and post-quantum public key crypto. For a variety of reasons (e.g. key size, protocol speed) it might be interesting to consider CVP instances where the vectors are sparse. In fact, in solving an algorithmic problem that has come up separately from cryptographic research, I have encountered what I am currently modeling as a sparse CVP problem.

Suppose we have a high dimensional (N >> 0) closest vector problem where each of the basis vectors and the target vector all have low (log N) support. What is known in the literature in this case? Does the problem become harder, by the compactness of the input? Does the sparsity of the vectors enable solutions to be found or approximated more quickly in the limit? A rudimentary literature search was not able to find relevant papers.

So, really two questions:

What is known of this problem?
Is there a canonical name for this problem?


texts: Graph that maximizes minimum hitting time?

texts:
Let $G$ be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current vertex's neighbors uniformly at random. The expected hitting time for a vertex $v$ is the time it takes, on average, for the walk to reach $v$.

For what family of graphs is the minimum of all expected hitting times as large as it can be?


texts: How to compute the disagreement between hypotheses

texts:
Given a class of hypothesis $\mathcal{H}$ representing the set of all consistent hypotheses with the examples seen so far, how to compute the region of uncertainty? The region of uncertainty is defined as all points where there are two or more hypotheses disagree on its labelling.

I am representing $\mathcal{H}$ as two hypotheses: most specific (MS) and most general (MG) (as described here ). $\mathcal{H}$ consists of these two and anything in between. Clearly, enumerating all possible hypotheses is infeasible due to the size of $\mathcal{H}$. To put it in one word, how to compute disagreements in practice?

EDIT:

sorry for not being specific. I am trying to learn a graphical model similar to bayesian networks but instead of probabilities I have order relation.

I have a set of variables $V=\{v_1,v_2,...,v_n\}$ where each variable has a set of possible values (its domain). $V$ defines an outcome space $\mathcal{O}$ (the set of all possible assignments over $V$ from their domain values). For example, if $A=\{1,2\}$ and $B=\{3,4\}$ we have $\mathcal{O}=\{(1,3),(1,4),(2,3),(2,4)\}$. The input space $X$ is the set of all pairs of outcomes from $\mathcal{O}$. Each example $x$ consist of pairs of outcomes $a$,$b\in \mathcal{O}$ (denoted as $x[a]$,$x[b]$ respectively). The target function is a strict order relation $\succ$ over $\mathcal{O}$. I am adopting the active learning paradigm. I first choose $\mathcal{U}$ unlabelled examples, then ask the oracle to label an example $x\in \mathcal{U}$. $h(x)=+$ if $x[a]$ is better than $x[b]$ otherwise $-$. The hypothesis class $\mathcal{H}$ is the set of all possible strict (partial/total) orders consistent with the examples seen so far.  My main concern is how to select representative hypotheses from $\mathcal{H}$


texts: theorems for universal set of quantum gates for SU(d)

texts:
It seems that there is a theorem that for prime dimension d, the set of Clifford gates and one non-Clifford gate together forms a universal set of quantum gates for SU(d). It also seems that for a universal set of gates, there is a requirement of a gate using which can provide non-trivial rotation by an irrational multiple of Pi. Does this imply that using any non-Clifford gate for prime d, one can construct such a gate ? Also, it probably does not follow directly that the non-Clifford gate used to get such a non-trivial rotation itself has irrational eigenvalues but it seems that is usually the case- for example, the qubit T gate and qudit versions of it.

Is there any similar theorem as mentioned above, for composite d ? It seems that if one finds a gate using which one can construct a non-trivial rotation by an irrational multiple of Pi, that should be enough to have universal set of gates even for composite d. Is it obvious that such a gate has to be non-Clifford ?


texts: Reasoning about NP hardness of optimization problems with closed form functions as input

texts:
(This may not be a research level question per se. I can delete this question if the community thinks this way too)

I am trying to understand how to reason about hardness of optimization problems when the input contains closed form functions. In my problem, I have buyer revenue curves as I put in closed form and I have to find an optimal output curve that maximizes revenue (the exact details are not important). On one hand, I can use the oft used tricks of discretizing and getting $(1+\epsilon)$-approximation FPTAS, I am not sure how to reason about NP hardness of these type of problems. One approach would be to show the hardness of the discrete version of the problem. While this works great since it is a special case of the continuous version but does not give the whole picture since the continuous function may also be differentiable (or double differentiable) which may have a huge impact on the answer.

Is there a general framework or hardness reduction techniques that work on closed form functions as input?


texts: What is a minimum vertex separator as in this definition?

texts:
In a research paper the following definition appears that I'm not able to understand completely.

Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, no parallel-edges.
Let $\{ u, v\} \in \binom{V}{2}$ be a vertex pair over the set of all vertices pairs. Let $\textrm{Sep}(u, v)$ be a minimum $u-v$ vertex separator in $G$ if $\{u, v\} \notin E$ or in $G' = (V,E \setminus \{u,v\}) $ otherwise.

It is difficult for me to figure out what this definition imply.

In particular can $\textrm{Sep}(u,v)$ be an empty set?


texts: Yao's Minimax Principle on Monte Carlo Algorithms

texts:
The celebrated Yao's Minimax Principle states the relation between distributional complexity and randomized complexity. Let $P$ be a problem with a finite set $\mathcal{X}$ of inputs and a finite set $\mathcal{A}$ of deterministic algorithm to solve $P$.
Also let $\mathcal{D}$ denote the input distribution and let $\mathcal{R}$ denote the probability distribution on $\mathcal{A}$.
Then the principle states
$$\min_{A\in\mathcal{A}}\quad\mathbb{E} cost(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost(\mathcal{R},x) \quad\quad\text{for all $\mathcal{D}$ and $\mathcal{R}$}.$$
This proof directly follows from von Neumann's minimax theorem for zero-sum games.

Mostly Yao's principle deals with Las Vegas algorithms only, but it can be generalized to Monte Carlo algorithms as follows.
$$\frac12 \min_{A\in\mathcal{A}}\quad\mathbb{E} cost_{2\epsilon}(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost_{\epsilon}(\mathcal{R},x)\quad\quad\text{for all $\mathcal{D}$, $\mathcal{R}$ and $\epsilon\in [0,1/2]$}$$
where $cost_\epsilon(\cdot,\cdot)$ denotes the cost of Monte Carlo algorithms that errs probability at most $\epsilon$.

In Yao's original paper, the relation for Monte Carlo algorithms is given at Theorem 3 without proof. Any hint for proving it?


texts: Characterizing the set of problems solvable via network flow

texts:
What are some ways to prove that a certain problem cannot be solved using Network Flow (NF)?

One way is to prove the problem is NP-hard.
But NF has substantial structure -- is there some symmetry or invariant that all solutions must satisfy in order to be solvable with NF?

I'm interested in any necessary or sufficient conditions that a problem should satisfy in order to be solvable using NF.


texts:
Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev:

  Let $X$ be a random variable, and let $Y = g(X)$ where $g(\cdot)$ is a random process. Assume the existence of a procedure $f$ that given $y = g(x)$ can reconstruct $x$ with probability $p$. Then
  $$ I(X; Y) \ge pH(X) − H(p)$$

In other words, if I can reconstruct, there's a lot of mutual information in the system.

Is there a "converse" to Fano's inequality: something of the form

  "Given a channel with sufficient mutual information, there is a procedure to reconstruct input from output with error that depends on the mutual information"

It would be too much to expect that this procedure would also be efficient, but it would also be interesting to see (natural) examples where the reconstruction exists but must be inefficient.


texts:
The complexity of the Unknotting problem is known to be in $\mathrm{NP} \cap\mathrm{co\text-NP}$, see references:

 The Computational Complexity of Knot Problems.
Knottedness is in NP, modulo GRH. .
Unknotting is in $\mathrm{AM}\cap\mathrm{co\text-AM} $.

Some even believe the problem to be in $P$, but to relax the ptime constraints, due to (maybe) either the cost, or diagram of the knot. It maybe there exists an Arthur-Merlin type protocol for unknottedness. This could lead to possibly interesting applications too. Also, if Unknottedness is $\mathrm{NP}$ -complete then the polynomial hierarchy collapses.
But  by relaxing the ptime constraints to a quasipolynomial one leads one to quasipolynomial time algorithm for Unknotting. Is there any such quasipolynomial time algorithm for Unknotting?
What (if any) would be the implications of such a quasipolynomial algorithm be to other conjectures such as GRH(?), ETH, or even SETH?


texts:
There is a symmetric sparse matrix with large front. This matrix is created from graph. Element with position $(i,j)$ is not zero if nodes $i$ and $j$ are connected.
What algorithms can be used for re-enumerating graph nodes to create matrix with lesser front?
I have only one option - the Cuthill-McKee algorithm. Is there anything else?

Thanks in advance.


texts: Submitting other people's work to the arXiv

texts:
This is a soft question aimed at establishing what people think is the professional best-practise for submitting unoriginal work on the arXiv.

There is a draft of an article [1] by Robert Szelepcsényi, at his webspace at the University of Chicago, apparently written more than a decade ago during his graduate studies. The work seems to be  correct, modulo some very minor errors, and contains a result that I would like to refer to, independently of what the University of Chicago intends to do with that webspace. It seems to be available only at that single location; and there doesn't seem to be any publicly available works which duplicate his results.

Partly for the sake of ensuring its correctness, I have taken it upon myself to write notes recapitulating the results and motivations of that draft, acknowledging that it is essentially a recapitulation of [1], and which hopefully smooths over some of the roughness present in the existing draft. I can certainly put these notes online on webspace of my own, but at present the arXiv seems to be the most responsible place to submit this draft for future reference.

Question.

Assuming correct attribution, and granted that these results are not widely available otherwise, is there any particular reason that I should not submit my draft of Szelepcsényi's results on the arXiv?

[1] Logspace MOD Classes with Composite Moduli (Preliminary Version) — Postscript File


texts: Halting problem, uncomputable sets: common mathematical proof?

texts:
It is known that with a countable set of algorithms (characterised by a Gödel number), we cannot compute (build a binary algorithm which checks belonging) all subsets of N.

A proof could be summarized as: if we could, then the set of all subsets of N would be countable (we could associate to each subset the Gödel number of the algorithm which computes it). As this is false, it proves the result.

This is a proof I like as it shows that the problem is equivalent to the subsets of N not being countable.

Now I'd like to prove that the halting problem is not solvable using only this same result (uncountability of N subsets), because I guess those are very close problem. Is it possible to prove it this way ?


texts: Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

texts:
I was reading this paper, about the complexity of decision problems for
reversal bounded counter machines.
I got to Theorem 1 on Page 6.
The theorem shows that there's a log-space NTM which can determine if a non deterministic reversal-bounded counter machine is empty or not.
(A log-space NTM can be converted into a polynomial time DTM).
The proof shows that, for input machine represented as a string of length $n$,
with $m$ counters, that $O(m\log n)$ space is required.
Here's where I get lost. The paper says that, since $m$ is fixed, we can consider
the machine to take $O(\log n)$ space.
Does this mean that the algorithm is only uses log-space if $m$ is fixed? Would the corresponding deterministic algorithm then be exponential in terms of $m$?


texts: Separating DAGs using separators consisting of lists of nodes and all ancestors

texts: Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$. I want to find a set of lists $\mathcal{J}$ such that removing all vertices in $\mathcal{J}$ from $G$ results in disjoint subgraphs where each subgraph has at most $O(1)$ vertices. Has anyone seen an algorithm in any work that solves this problem and finds a minimum number of lists in $\mathcal{J}$ efficiently? It also seems to me that there exists a $\mathcal{J}$ for any DAG $G$ that has size $O(\log n)$ always. This seems like a question that should be closely related to finding balanced separators but I haven't seen anything yet in this literature regarding this specific or a closely related problem.


texts: Complexity results about locally bipartite graphs

texts:
A graph is locally bipartite if the open neighborhood of
every vertex induces a bipartite graph.
(According to searches the same name might be used for
something else related to surfaces).

  Which NP-hard for general graphs problems become polynomial
  for locally bipartite graphs and which remain NP-hard?

Especially interested in clique and coloring.

  Are there inclusions between locally bipartite and other
  graph classes?

Added According to a paper they are also called "almost bipartite" and their complements
are generalized line graphs which are claw free.


texts: Is longest common subsequence with bounded occurrences NP-complete?

texts:
The general longest common subsequence problem (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has m zeros and n ones, where m and n are constants?

I asked this question on cs.stackexchange and was told, "The problem probably remains NP-complete." However, I was unsuccessful in showing a reduction from the original LCS problem.


texts: I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be Neil Immerman's book, but this is already quite old. Seems like this line of research is dead. Is this the case? If so, why?


texts: How can you build a coinductive memoization table for recursive functions over binary trees?

texts:
The StreamMemo library for Coq illustrates how to memoize a function f : nat -> A over the natural numbers.  In particular when f (S n) = g (f n), the imemo_make shares the computation of recursive calls.

Suppose instead of natural numbers, we want to memoize recursive functions over binary trees:

Inductive binTree : Set :=
| Leaf : binTree
| Branch : binTree -> binTree -> binTree.

Suppose we have a function f : binTree -> A that is structurally recursive, meaning that there is a function g : A -> A -> A such that f (Branch x y) = g (f x) (f y).  How do we build a similar memo table for f in Coq such that the recursive computations are shared?

In Haskell, it is not too hard to build such a memo table (see MemoTrie for example) and tie-the-knot.  Clearly such memo tables are productive.  How can we arrange things to convince a dependently typed language to accept such knot tying is productive?

Although I've specified the problem in Coq, I wouldd be happy with an answer in Agda or any other dependently typed language as well.


texts: Polynomial method for complexity results

texts:
Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee the existence of a solution, or the number of solutions to the polynomials. They have been used to solve problems like restricted sumsets or zero-sum problems, and some of the theorems in this area can be proved only by such methods.

To me the non-constructive manner of these methods are truly amazing, and I'm curious about that how we can apply these methods to prove any interesting inclusions and separations of complexity classes (even if the result can be solved by other methods).

  Are there any complexity results known that one can prove them by polynomial methods?


texts:
We have number of non-isomorphic graphs given in http://planetmath.org/enumeratinggraphs

Over an alphabet $q$ how many non-isomorphic $[n,k,d]_q$ codes are possible particularly in the special case of $d=n-k+1$ (MDS case)?

The paper here provides number of non-isomorphic $[n,k]_2$ codes without restricting distance.

My question has distance restriction.


texts:
The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads:

  Clearly, maintaining $\epsilon$-approximate counts till a range of $N$ necessitates $\Omega(\log \log N)$ bits. Indeed,
  the cardinalities should be located in an exponential scale,
  $1$, $(1+\epsilon)$, $(1+\epsilon)^2$, …, $(1+\epsilon)^L=N$, which comprises $\log_{(1+\epsilon)} N$ intervals, necessitating at least $\log_2 \log_{(1+\epsilon)} N$ bits of information to
  be represented.

It also says the optimality result comes from the combination of the previous fact and a bound by Chassaing & Gerin "for a wide class of algorithms based on order statistics".

How do the authors go from "approximating the number of unique elements in a set" to "maintaining $\epsilon$-approximate counts till a range of $N$"?
What is the link between the two results and what exactly is meant by combining the two?
I could only find an asymptotic bound in the paper they mention, but the HyperLogLog paper authors say that they are within 4% of the optimal bound. What have I missed?
If the bound by Chassaing & Gerin is only about a algorithms that are based on order statistics, what proves that there isn't an algorithm based on something else that performs better?


texts: Algorithmic distinctions between random and pseudorandom.

texts:
Given a specific pseudo random number generator (e.g. Mersenne twister) $r()$ and a true random number generator $q()$ is there an algorithm $f(x,y)$ such that:

$f(r(),r()) = 1$ almost always.
$f(q(),q()) = 0$ almost always.

It should be noted that $f()$ stores no state, it only takes the return values of two consecutive calls as its parameter: we can also consider the case of a vector of $n$ calls as input.

"almost always" may be interpreted quite liberally, it could return this result with $> 2/3$ probability or the long term average could tend towards this limit.

I would also appreciate any insight on the same question for an unknown pseudo-random number generator (i.e. an arbitrary Turing machine) as $r()$. Thanks very much!


texts: Reference request for a $\Delta_2^P$ satisfiability problem

texts:
I am looking for the name and a reference for a $\Delta_2^P$-complete problem that looks like the following

Input:
A collection of CNF formulas $\phi_i(x_1^i, x_2^i,\dots, x_m^i, z_1, z_2, \dots, z_{i-1})$ for $1 \leq i \leq n$ where the $x_j^i$ are free variables and the $z_i$ variables are bound, and the value of $z_i$ is true if $\phi_i$ is satisfiable and false if $\phi_i$ is unsatisfiable.
Output: Whether $\phi_n$ is satisfiable.

I looked at https://cs.stackexchange.com/questions/14251/which-problems-are-hard-for-pnp and at https://mathoverflow.net/questions/2218/characterize-pnp-a-k-a-delta-2p but couldn't find what I'm looking for. I believe I came across a paper mentioning a problem defined similarly to the one above a couple months ago, but I don't remember which paper was listing it. I am not 100% sure about my recollection of the problem definition and this is one of the reasons behind this reference request.


texts:
As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the determinant.

The question I had after skimming through the GCT Papers: Would this immediately imply $P \neq NP$, or is it merely a major step towards this goal?


texts: Is bounded-error probabilistic computation sensitive to transition types?

texts:
In the unbounded-error case, it is known that both realtime quantum and probabilistic finite automata can recognize some uncomputable languages if they are allowed to use arbitrary real numbers in their transitions (Rabin, 1963; Yakaryilmaz and Say, 2011).

In the bounded-error case, we have a similar result for poly-time quantum Turing machines as well, i.e. the cardinality of $ \mathsf{BQP}_{\mathbb{C}}  $ is uncountable (Adleman et. al., 1997).

My question is whether any bounded-error probabilistic space (time) class defined with unrestricted real numbers contains an uncomputable (or a recursive enumerable) language.

It is also known that (Watrous, 2003) if we restrict ourselves to algebraic numbers ($\mathbb{A}$), for any space-constructable function $ s(n) \in \Omega(\log n) $,
\begin{equation}
\mathsf{PrQSPACE}_{\mathbb{A}}(s) \subseteq \mathsf{DSPACE}(s^2),
\end{equation}
where $\mathsf{PrQSPACE}$ stand for unbounded-error quantum space.

Any partial answer (for the case of bounded-error probabilistic computation using non-algebraic transitions) violating this upper bound would also be nice.


texts: Is there a P-complete problem on diophantine equations?

texts: In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem.  I believe that deciding if a quadratic diophantine equation has any solution is NP-complete. Does there exist a further restriction on the equations involved that yields a P-complete problem?


texts:
We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$).

The task is to approximately cover $L$ with translated, rotated and flipped copies of $S$ without pairwise intersections, i.e. find the optimal number of replicas $N^*$ and respective group operations (a finite set) $\mathbf{a}^*$

$ \textbf{a}^*, N^* = \mathop{\arg \max}_{\textbf{a}, N} \sum\limits_i^N \mu(s_i)$

s.t. $ \bigcap\limits_i^N s_i = \emptyset $,

with  $s_i = a_i(S) \in L$ being the application of the $i$th group operation to $S$, and $\mu(s_i) = \mu(S)$ the measure of $S$ e.g.

* * *
  *

could approximate $L:=\{(i,j)\,|\,0 \leq i \leq 3,\, 0\leq j \leq 4 \}$ in the above sense as follows:

* . . *
* * * *
* . . *
. * . .
* * * .

or

* * * *
* * * *
* . * *
. * . *
* * * .

etc.

I am thinking that some form of hierarchical rejection sampling should do. However my question is:

Is this a known algorithm, and if so, could someone point me to some references?

(In fact, I am pretty sure this is a special case of some well-known algorithm, I'm just not sure how to represent it. NB: I'm not a CS by education and this is not a homework problem)

Thank you in advance


texts: Maximum flow for all edges in an undirected graph

texts:
I was wondering if the following problem has been studied in the past, and what are some of the best ways people can come up with to solve it:

Let $G=(V,E)$ be an undirected graph, which we use as a flow network with edge capacities $c(e)=1$ for all $e \in E$.
For all edges $e = \{u,v\} \in E$, we would like to calculate the maximum flow between $u,v$.

Let $t_{mstf}$ be the time it takes to calculate a maximum s-t flow and $t_{mf}$ be the time it takes to calculate a maximum flow.
We can solve the problem above naively in $\mathcal{O}(|E| \cdot t_{mstf})$ time.
We can also do it by building a Gomory-Hu tree in $\mathcal{O}(|V| \cdot t_{mf})$ time and then an additional $\mathcal{O}(|E||V|)$ steps to get shortest paths along the tree.

Can we do any better?


texts:
$L\neq DSPACE[\omega(\log n)]$ is known.
Is $UL\neq DSPACE[\omega(\log n)]$ and $UL\neq PSPACE$ known?


texts:
I would like to ask if there is a name for the class of multifunctions, each of which can be computed by a probabilistic polytime Turing machine $M$ satisfying the following two conditions:

$M$ returns a correct output of the function with high probability
$M$ can either return a correct answer or "don't know", and never return an incorrect answer.

Note that although this sounds like $\mathsf{ZPP}$, it is not since $\mathsf{ZPP}$ is the class of predicates, and not multifunctions. I really appreciate any pointer to the right sources.


texts: Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$

texts:
Let $\Sigma$ be a finite alphabet.
A trivial finite automaton can accept the language $L_1 = \{w\;|\;w\in \Sigma^*\}$. A simple pushdown automaton can accept the language
$L_2 = \{ww^R\;|;w\in \Sigma^*\}$ where $w^R$ is the reverse of $w$, i.e.,
the string obtained from $w$ by reading it backwards.

What is the simplest non-universal machine model which accepts the language $L_3 = \{ww^Rw\;|\;w\in \Sigma^*\}$? Note that $L_3$ can be easily accepted by a queue automaton, but queue automata are universal.
Are there well studied classes of non-universal automata accepting non-context free languages?


texts: What relations has different bounds for NP?

texts:
this is my first question here so I hope I've done everything correctly.

I know that if someone finds a polynomial solution to any of the famous NP problems, all of them has one (polynomial solution).

Does this hold for say a k^n solution (and if, must they all have the same exponent) ?

And my real question, is there some relation among NP problems in the sense that say one solution is n! then another can't be (n²)! or is that (the n²) 'eaten up' by the "!" ?

Please point me in the right direction if you can.

Thanks for your time and I hope my question is clear enough.