texts:
While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual append  operation used on deletion algorithms for immutable data structures, but I'm still wondering if there's a better approach I wasn't able to find, or even some minimum complexity boundary on such an operation?

Just to be clear, I'm talking about an algorithm that, given a red&black tree and two boundaries, will produce a new red&black tree with all the elements of the first tree that belong within those boundaries.

Of course, an upper bound for the complexity would be the complexity of traversing one tree and constructing the other by adding elements.


texts:
Theoretical computer science has provided some examples of "the price of abstraction."  The two most prominent are for Gaussian elimination and sorting.  Namely:

It is known that Gaussian elimination is optimal for, say, computing the determinant if you restrict operations to rows and columns as a whole [1].  Obviously Strassen's algorithm does not obey that restriction, and it is asymptotically better than Gaussian elimination.
In sorting, if you treat the elements of the list as black boxes that can only be compared and moved around, then we have the standard $n \log n$ information-theoretic lower bound.  Yet fusion trees beat this bound by, as far as I understand it, clever use of multiplication.

  Are there other examples of the price of abstraction?

To be a bit more formal, I'm looking for examples where a lower bound is known unconditionally in some weak model of computation, but is known to be violated in a stronger model.  Furthermore, the weakness of the weak model should come in the form of an abstraction, which admittedly is a subjective notion.  For example, I do not consider the restriction to monotone circuits to be an abstraction.  Hopefully the two examples above make clear what I'm looking for.

[1]  KLYUYEV, V.V., and N. I. KOKOVKIN-SHcHERBAK: On the minimization of the
number of arithmetic operations for the solution of linear algebraic systems of
equations. Translation by G. I. TEE: Technical Report CS 24, June t4, t965,
Computer Science Dept., Stanford University.


texts:
The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time.
Does it hold in some way if the space is limited asymptotically?
How does $\textrm{DTISP}(g(n), O(s(n)))$ relate to $\textrm{DTISP}(f(n), O(s(n)))$ if $\frac{f}{g}$ grows fast enough?

I am especially interested in the case that $s(n) = n$, $g(n) = n^3$ and $f(n) = 2^n$.

In particular, I considered the following language:
$ L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w)  \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps}, $ $ k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \} $

However, $L_k$ could be decided in $n^3$ steps by using $(k+1)n \in O(n)$ space.

Without limiting $M$ to four tape symbols and thus allowing to compress $O(n)$ cells into $n$ cells, we get space issues when simulating an $M$ with too many tape symbols. In this case, the language is not in $\text{DSPACE}(O(n))$ anymore. The same happens when setting $k = h(|w|)$ for some $h$ that can be computed fast enough.

This question is basically a rephrase of my question here.

Edit Summary:
Changed $\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$ to $\textrm{DTISP}(f(n), s(n))$, however, I think the intersection is also worth to think about.


texts: I've been reading and learning about SAT solvers this week. If they can solve problems with thousands of variable quickly haven't we practically solved ANY problem that can be reduced to it, including the TSP problem? Or does it only work quickly for special cases?


texts: Does NP-completeness/hardness have to be constructive?

texts:
Is there any $L\in {\bf NP}$ with the following properties:

It is known that $L\in {\bf P}$ implies ${\bf P}={\bf NP}$.
There is no (known) polynomial time Turing reduction of $SAT$ (or some other ${\bf NP}$-complete problem) to $L$.

In other words, if a polynomial time algorithm for $L$ implies the collapse of ${\bf NP}$ into ${\bf P}$, then  is it necessary that this "general hardness" of $L$ for ${\bf NP}$ must be somehow $constructive$, in the sense that, say, $SAT$ must be reducible to $L$ via some specific reduction?


texts:
I want to know what is the best known lower time complexity of Succinct-CVP?
The succinct version of many P-complete problems are EXP-complete and Succinct-CVP is EXP-complete too (It is because of the local reductions). If we expand the circuit then we have an $2^n$ size CVP which
is decidable in time $2^n$. I searched a lot to find a better algorithm for this problem I was looking for $2^{n/{\log^5 n}}$ time algorithm but I can't even find an algorithm with time complexity of $2^{n/3}$. So I want to know is there any research around this problem or a better algorithm?
Succinct-CVP: given a circuit $D(y_1,y_2,...,y_n)$ that is a succinct description of a circuit $C(x_1,x_2,...,x_n)$ of size at most $2^n$ and an input $a \in \{0,1\}^n$, Compute the value $C(a)$.


texts: Most efficient way to convert an $\text{AC}^0$ circuit to a circuit  (of any depth) with gate fanout 1

texts:
EDIT (Aug 22, 2011):

I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts of the original question that are no longer relevant. (Thanks to Stasys Jukna and Ryan O'Donnell for partially answering the original question!)

Background:

Given an AC0 circuit with depth k and size S, there exists another AC0 circuit computing the same function with depth k and size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. In other words, the circuit looks like a tree (except at the inputs, since the inputs may fanout to more than one gate). One way to do this is by duplicating all the gates that have fanout > 1 until all gates have fanout = 1.

 But is this the most efficient way to convert AC0 circuits to AC0 circuits with fanout 1? I read the following in Lecture 14 of Ryan O'Donnell's course notes:

  Suppose C is any depth-k circuit of size S which computes Parity. It
  is an exercise to show that C can be converted into a leveled  depth-k
  circuit, where the levels alternate AND and OR gates, the inputs wires
  are the 2n literals, and each gate has fan-out 1 (i.e., it’s a tree) —
  and the size increases to at most $(2kS)^2 \leq O(S^4)$.

  Footnote: Actually, this is a slightly tricky exercise. It’s easier if
  you only have to get size $O(S^k)$, which is almost the same for our
  purposes if you think of k as a “constant”.

Does this mean there is a way to take any depth k AC0 circuit of size S and convert it to an AC0 circuit with fanout 1, depth k and size $(2kS)^2$? If so, how is this done and is this the best-known method?

Original Question:

  Given an AC0 circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to an AC0 circuit of depth k and gate fanout 1? Are there any lower bounds known for this?

Newer, simpler question:

This question is a relaxation of the original one where I don't insist that the resultant circuit be constant depth. As explained above, there is a way to convert an AC0 circuit with depth k, size S into a circuit with size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. Is there a better construction?

  Given an AC0 circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to a circuit of any depth with gate fanout 1?


texts: The number of rooted ordered trees of max-out degree $k$

texts:
An ordered tree (also known as ordinal tree and plane tree) is a rooted tree in which the children of each node are ordered. It is known that the number of the ordered tree with $n$ edges is the $n$'the Catalan number $C_n$.

I am interested in the number of ordered trees in which the number of children of each node is at most $k$ (possibly less than $k$) for some small parameter $k$ (I am particularly interested in the case of $k=4$).

The special case of ordered trees with $k=2$ is called 0-1-2 trees (each node has 0, 1, or 2 children). It is known that the number of such trees with $n$ edges is the $n$'th Motzkin number $M_n$.
For $k>2$, the number of ordered trees should lie between $M_n$ and $C_n$. We know $\log_2(M_n) = 1.585 n - o(n)$ and $\log_2(C_n) = 2n - o(n)$. I am interested in the constant behind $n$ for $k=4$.


texts: Converting Kuroda normal form rules to the Penttonen normal form

texts:
Let us say we have some abstract context-sensitive grammar in the Kuroda normal form, which is where all production rules are of the form:

$AB\rightarrow CD$ or

$A\rightarrow BC$ or

$A\rightarrow B$ or

$A\rightarrow a$

There is also the one-sided normal form or the Penttonen normal form for context-sensitive grammars (described in the same wikipedia article), which is where all rules are of the form:

$AB\rightarrow AD$ or

$A\rightarrow BC$ or

$A\rightarrow a$

Question: how to generally convert a rule of the Kuroda normal form $AB\rightarrow CD$ into bunch of rules in the Pentonnen normal form?
In particular I am stuck with understanding how to deal with an intermediate rule of the form $AZ\rightarrow WZ$.


texts:
I am looking for an easy example of two transition systems that are LTL equivalent, but not trace equivalent.

I have read the proof of Trace Equivalence being finer than LTL Equivalence in the book "Principles of Model Checking" (Baier/Katoen) but I'm not sure I really understand it. I am unable to picture it, is there maybe a simple example that can visualize the difference?


texts: I have a rather naive question on LU factorization which probably should be easy to answer. Say I have a matrix with entries only from $\{0,1\}$. When can we expect to get an LU factorization of such a matrix(whenever it exists) with entries $(a)$ from integers? $(b)$ from $\{-1,0,+1\}$?


texts: Deciding reachability under iterated independent polynomial mapping

texts:
For any $1\leq i\leq m$, $f_i: \mathbb{Q}\rightarrow \mathbb{Q}$ is a polynomial mapping over $x_i$, where $\mathbb{Q}$ is the set of rationals. For $\vec{a}_0=(a_1, \cdots, a_m)\in \mathbb{Q}^m$, we define $\vec{y}_n=(f_1^n(a_1), f_2^n(a_2), \cdots, f_m^n(a_m))$, where $f_i^n$ represents the $n$-fold composition of $f_i$, i.e., $f_i(f_i(\cdots(\cdot)))$. The problem is to decide, given $f_i,\vec{a},\vec{c},d$, whether there exists some $n\geq 0$ such that $\vec{c}\cdot \vec{y}_n=d$, i.e., $\vec{y}_n$ lies in the hyperplane given by $\vec{c}\cdot \vec{y}=d$.

Is this problem decidable?  I conjecture it is not. What I know is that even for $m=2$ and each $f_i$ being linear, the problem is undecidable if $f_i$ were defined over $(x_1, \cdots, x_m)$. However, here coordinates are independent so the undecidability does not seem to be straightforward.


texts:
Meyer's theorem is one of the classical results about collapse of the polynomial hierarchy such as famous Karp Lipton's theorem, and states that $EXP \subseteq P/poly \Rightarrow EXP = \Sigma_{2}^{p} $.  A proof outline is as follows:

Let $L \in EXP $ and let $M$ be a one tape TM deciding $L$ in time $2^{n^{C}}$.  Consider the computation tableau for $M$, and assume each position $(i,t)$ encodes as a string $z_{i,t}$ the content all cell at time $t$, whether the head of the tape scanning cell $i$ at time $t$, and if it is, records the internal state $q$ of the TM.

Now consider the language about computational historical tableau of $M$.
Let $L_{M} = \{ \langle x,i,t,z\rangle | \text{on input } x \text{  we have  } z_{i,t} = z \text{  for  } M  \}.$

By simulation $M$ we have $L_{M} \in EXP \subseteq P/poly$. If using polynomial size circuits for $L_{M}$ we can construct a polynomial-size multi-output circuit $C$ such that $C(\langle x,i,t\rangle)=z$ then we get a characterization with two quantifiers $L_{M} = \exists C \in \{0,1\}^{poly(n)},\forall i ,t\in  \{0,1\}^{poly(n)},C(\langle x,i,t\rangle)$ follow from  $C(\langle x,i-1,t-1\rangle),C(\langle x,i,t-1\rangle),C(\langle x,i-1,t-1\rangle) \wedge C(\langle x,1,2^{n^{C}}\rangle) $ is the accepting state by the transition function of the TM.

Question:

  In this proof, I am not sure about the construction of multi-output circuit. Can anyone  give a concrete way of doing this construction?


texts: Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$

texts:
Let $H$ be a maximum induced interval subgraph of a graph $G=(V,E)$.  If $n=|V|$， then what is the smallest number of $V(H)$?

The number is at most $3n/4$： consider a set of disjoint $4$-holes.

Can it be smaller?


texts:
How hard is the Set Cover problem if the number of elements is bounded
by some function (e.g, $\log n$) where $n$ is the size of the problem instance. Formally,

Let $\mathcal{U}=\{e_1, \cdots, e_m\}$ and $\mathcal{F} = \{S_1, \cdots, S_n\}$
where $S_i \subseteq \mathcal{U}$ and $m = O(\log n)$. How hard is it to decide the following problem

\begin{align*}
         \text{SET-COVER'}=\{<\mathcal{U}, \mathcal{F}, k>:
         &\text{ there exists at most $k$ subsets }\\
         &\text{ $S_{i_1}, \cdots, S_{i_k}\in \mathcal{F}$ that cover $\mathcal{U}$}
         \}.
\end{align*}

What if $m=O(\sqrt{n})$?

Any result based on well known conjectures (e.g., Unique Games, ETH) is good.

Edit 1: A motivation for this problem is finding out when the problem gets hard as $m$ increases. Clearly, the problem is in P if $m=O(1)$ and NP-hard if $m=O(n)$. What is the threshold for the NP-hardness of the problem?

Edit 2 : There exists a trivial algorithm to decide it in time $O(n^{m})$ (which enumerates all subsets of size $m$ of $\mathcal{F}$). Therefore, the problem is not NP-hard if $m=O(\log{n})$ since ETH implies that there is no algorithm in time $O(2^{n^{o(1)}})$ for any NP-hard problem (where $n$ is the size of the NP-hard problem).


texts: FPT algorithm for Partial k-tree Isomorphism

texts:
H.L. Bodlander in Polynomial algorithms for graph isomorphism and chromatic index on partial $k$-trees given a polynomial time algorithm for graph isomorphism when $k$ is constant.

Is there any FPT algorithm for partial $k$-tree isomorphism.


texts: Dynamic Upper Envelope of lines in the plane

texts:
There are easy algorithms to calculate the upper envelope of an arrangement of lines in the plane. See e.g. section 2.3 in the survey
Davenport-Schinzel sequences and their geometric applications.

Are there any known algorithms / data structures for the dynamic version of the same problem? That is, we want to maintain the upper envelope of a set of lines in the plane under the following operations:

insert$(\ell$): adds line $\ell$ to the set
delete$(\ell)$: removes line $\ell$ from the set
query$(x)$: return the line with $x$ coordinate in the upper envelope. In other words, return the line in the set which is first hit by a vertical downward ray from the point $(x, \infty)$.


texts: Simple question on complexity models w.r.t linear algebra

texts: For any matrix $B$, there are matrices $X$ and $Y$ such that the product $XBY$ is a diagonal matrix. Suppose $B$ is an $n \times n$ non-singular matrix with $b$-bit integer entries and no repeated eigenvalues. What is the worst-case bit complexity of $X$ and $Y$ as a function of $b$ and $n$ (say when you fix an approximation error for the diagonal matrix as a function of $n$ and $b$)? Also what is the complexity of computing $X$ and $Y$?


texts: Translation of Counter-free automata into Linear Temporal Logic

texts:
There is a well-known equivalence between counter-free automata and Linear Temporal Logic (which is cited for example by [1]). However, I cannot find a concrete way to obtain an LTL formula from a counter-free automaton.
Is there any reference that shows such a translation?
[1] Wolfgang Thomas, Safety- and Liveness-properties in Propositional Temporal Logic: Characterisation and Decidability, Mathematical Problems in Computation Theory, Volume 21, 1988


texts:
In the Haussdorf approximation of a convex object $C$ (and in much core-set work), the standard approach is to take an $\epsilon$-net on the enclosing hyper-sphere, then project it down to $C*(1 + \epsilon)$, where $C*(1+ \epsilon)$ is defined as $C$ projected outwards normally by an $\epsilon$ factor. I have a basic understanding of the proofs, but I'm trying to visualize why the hypersphere is really necessary. If you take an $\epsilon$-net on the surface of $C*(1+\epsilon)$ itself, would that not suffice? If there is an immediately obvious reason it would not work, I'd appreciate the clarification :).

Note: The $\epsilon$-net here is defined as a collection of equally spaced points on given surface.


texts: “Overflow” in Extended Euclidean Algorithm

texts:
Sorry if I'm mistaken with the place to ask the question (maybe I should go to stackoverflow.com/mathoverflow.net?).

I wonder if there is a proof that when evaluating extended Euclidean algorithm the Bézout's coefficients (that is s and t in identity as + bt = gcd(a, b)) will not exceed some reasonable values (depending on a, b, I guess). In particular implementation on some general-purpose programming language I'm interested in overflow correctness of the program.

To be precise I can mention that I use Victor Shoup's description of the algorithm (4.2 in his book “A Computational Introduction to  Number Theory and Algebra” freely available from his homepage).


texts: DFA intersection algorithm for special cases

texts:
I'm interested in efficient algorithms for DFA intersection for special cases. Namely, when the DFAs to intersect obey a certain structure and/or operates on limited alphabet. Is there any source where I can find algorithms such cases?

In order to not make the question too broad, the following structure is of particular interest: all the DFAs to intersect operate in the binary alphabet (0|1), they can also use don't care symbols. Moreover, all the states have only one transition except for at most K special states, which have only two transitions (and these transitions are always 0 or 1, but no don't care). K is an integer, less than 10 for practical purposes. Also, they have a single accepting state. Additionally, it is known that the intersection is ALWAYS a DFA in form of "strip", i.e., no branches as in the following image:

EDIT: Perhaps the description of the constraint on the input DFAs is not very clear. I will try to improve it in this paragraph. You have as input T DFAs. Each of these DFAs operates only on the binary alphabet. Each of them has at most N states. For each DFA, each of its states is one of the following:

1) the accepting state (it is only one and there's no transition from it to any other state)

2) a state with two transitions (0 and 1) to the same target state (the majority of the states is of this kind)

3) a state with two transitions (0 and 1) to different target states (at most K of this kind)

It is guaranteed that there's only one accepting state and that there are at most K states of type (3) in each input DFA. It is also guaranteed that the intersection DFA of all the input DFAs is a "strip" (as described above), of size less than N.

EDIT2: Some additional constraints, as requested by D.W. in the comments:

The input DFAs are DAGs.
The input DFAs are "levelled", following the D.W. definition in the comments. Namely, you can assign different integers to every state in such a way that every transitions goes from an integer u to an integer v, such that u + 1 = v.
The number of accepting states for each input DFA, doesn't exceed K.

Any ideas? Thanks.


texts: Computing the convex hull of lattice points

texts:
Consider a set of $n$ points in $\mathbb Z^2$. It is known that their convex hull can be computed in time $O(n\log n)$, or even $O(n\log h)$ where $h$ is the number of points in the convex hull. These bounds are in given (for instance) in the model of algebraic decision trees.

What is the bit-complexity of computing the convex hull of $n$ points in $\mathbb Z^2$, whose both coordinates are bounded in absolute value by $M$?

I am interested on the one hand in the dependence of the complexity in $M$, and on the other hand in the possible gain in complexity one obtains using the fact that the input points have integer coordinates. In my problem, I see $M$ as a large parameter, that is $\log(M)$ has the same order of magnitude as $n$.

Note that I am especially interested in the problem with the additional requirement that the points on the convex hull have to be listed in the order of the (say) counterclockwise rotation, beginning for instance at the leftmost point.

I am also interested in the same questions in higher dimensions.


texts: Can anyone suggest a good and recent survey on counting problems and/or problems that are #P.


texts: Generation of unlabeled acyclic digraphs

texts:
I'm looking for an algorithm to efficiently generate all unlabeled acyclic digraphs of a given order.  (By "unlabeled" I mean that no two of the generated digraphs should be isomorphic.)
Thanks

Edit: removed the word "enumeration" from title; I made the original title "Enumeration/generation of unlabeled acyclic digraphs" in a misguided effort to increase the number of possible answers; I had conjectured, incorrectly, that enumeration algorithms could be easily adapted to generate all the enumerated digraphs; now I realize this conjecture is wrong, hence the edited title emphasizes that I'm interested in an algorithm for generating (and not just enumerating) unlabeled acyclic digraphs.


texts: What techniques are used for proving algorithms optimal?

texts:
Possible Duplicate:
  Problems that can be used to show polynomial time hardness results

Given a polynomial time algorithm, what techniques are known for proving that an algorithm is optimal?  E.g., given an algorithm for solving, say, REACH (a P-complete problem), what are good techniques for proving that the algorithm runs with optimal complexity, assuming of course that it does and that its complexity is known.

In case that was unclear, I'll restate my question briefly:  Given a polynomial time algorithm that decides a language or computes a function, how can one prove that the algorithm's worst-case complexity cannot be improved upon with a "better" algorithm?

Edit:  By "better" what I mean is that, e.g., if a particular algorithm has been established to run in O(n^4), there does not exist any algorithm with O(n^3) complexity that solves the same problem.

Thank you,

Philip


texts: Recent progress in permutation groups algorithms?

texts:
I am interested in algorithms for finite groups as implemented in the GAP package. It seems that all known algorithms in this field deal with permutation groups/matrix groups; two fundamental ones are Schreier-Sims [1970] and Butler [1979], see e.g. 'Algorithms for Permutation groups' by Alice Niemeyer as a possible reference (?)

Hence, I was wondering whether there had been significant progress in the field in the last 50 years. I've seen that user NisaiVloot asked some questions about braid groups that may constitute an interesting extension of known results about permutation groups, though it's unclear to me what is the current state of research in this field as the mathematics/algorithmics communities seem somewhat out-of-sync nowadays.


texts: Why not include private randomness in internal communication information definition?

texts:
I am using https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf as a reference.

This isn't exactly a research question but I can't find a good place to ask it.

Suppose we have $f:X\times Y \to Z$, $u$ a distribution on $X\times Y$, and $\delta >0$.

Now consider communication protocols that allow both public and private randomness- this means a distribution (the public randomness) on a set of computation trees, each node of which has a player's name, and two edges outgoing marked by $0,1$, and the node gets as info the private randomness of that player; the leafs have no player's name, and instead just contain the output of the protocol (an element of $Z$).

If $\prod$ is a protocol computing $f$ with at most $\delta$ error (the probabiliy space is over both inputs, public and private randomness), we let abuse of notation use $\prod$ as a random variable of a string of what they players said in addition to the public randomness (to clarify, it's a pair ($R,T$) where $R$ is the public random and $T$ the transcript). We can define its external information complexity to be $I_{u,\delta}(X,Y;\prod)$.

We also define the internal information complexity to be

$I(X;\prod|Y)+I(Y;\prod|X)$, intuitively the first summand should be what player $B$ (who got $Y$) learns about $X$, and similiarly for the second.

What confuses me is shouldn't we also condition on the private randomness here?

I.e $I(X;\prod|Y,PR(Y))+I(Y;\prod|X,PR(X))$


texts:
Who introduced the idea of recursion?
Can someone explain where it came from and how it impacted computer science?


texts: Detecting/Locating endpoints of a bridge-like structure in images using Graph Theory

texts:
I have asked similar questions on stackoverflow; as i couldn't post the very same question in this part of stackexchange.  However, i would still like to receive recommendations / advice from this side of stackexchange, so forgive me and correct me if this is not the right place to ask such question.

The image can be seen here!

Problem Scenario

I have a set of images that look like what you see on the left hand column as shown in the above picture.  What I am trying to detect/locate is actually the two endpoints that are shown on the right hand column in the above picture.  It's quite like locating the "two ends points" of the 'bridge'.

I sincerely would like to seek for your advice and recommendation to achieve such goals.  I have applied some basic morphological operations; however, either im doing it wrong or those basic morpological operations aren't working in this scenario.  (i have tried making it into skeletons; however, once the skeletons are formed, I can't seem to detect the cross with 3 edges).

Also, would Graph Theory be applicable in this case?  If so, how do i detect the end points using Graph Theory?

Thanks very much.

Edits

It looks like the original sets of images cannot be completely generalized like what i'd previously drawn.

i have attached the latest updates to this question. Below is a more detailed representation that includes the original segmented regions and the corresponding images that'd undergone a "thinning" morphological operation. Again, the left side is the originally segmented region; while on the right would be the points to be detected.


texts: Has anyone classified the (non-quantum) complexity of the hidden subgroup problem for finite Abelian groups? Is it known to be in any classical (not quantum) complexity classes?


texts: Deciding whether an NC${}^0_3$ circuit computes a permutation or not

texts:
I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered.

A Boolean circuit is called an NC0k circuit if each output gate syntactically depends on at most k input gates.  (We say that an output gate g syntactically depends on an input gate g′ when there is a directed path from g′ to g in the circuit as viewed as a directed acyclic graph.)

In the aforementioned question, QiCheng asked about the complexity of the following problem, where k is a constant:

Instance: An NC0k circuit with n-bit input and n-bit output.
Question: Does the given circuit compute a permutation on {0, 1}n? In other words, is the function computed by the circuit a bijection from {0, 1}n to {0, 1}n?

As Kaveh commented on that question, it is easy to see that the problem is in coNP.  In an answer, I showed that the problem is coNP-complete for k=5 and that it is in P for k=2.

  Question.  What is the complexity for k=3?

Clarification on May 29, 2013: “A permutation on {0, 1}n” means a bijective mapping from {0, 1}n to itself.  In other words, the problem asks whether every n-bit string is the output of the given circuit for some n-bit input string.


texts:
What should you do when you see a question raised in public, say here on stack-exchange, that you know the answer to, because you are looking into as part of current research project?

For example, I see a TCS.SX question that I know the answer to, because I worked on the problem recently.  I haven't finished writing up the results yet and am trying to get a few more results to make an acceptable paper.

Should I contact the asker personally?  Claim credit publicly by publishing answer on the site?  What should I do?


texts: Oblivious Turing Machine emulation lower bound

texts:
Is there a proof that the emulation of a Turing machine on an oblivious Turing machine can't be done in less than $\mathcal{O}\left(m\log m\right)$ where $m$ is the number of steps the Turing machine uses? Or is this just an upper bound?

In the paper of Paul Vitányi about relativized oblivious Turing machines, Vitányi claims

  "They [Pippenger and Fischer, 1979] showed that this result cannot be improved in general, since there is a language L wich is recognized by a 1-tape real-time Turing machine $M$, and any oblivious Turing machine $M'$ recognizing $L$ must use at least an order $O(n \log n)$ steps".

This should state $O(m \log m)$ as an absolute bound. However I don't find any proof of this in

Pippenger, Nicholas; Fischer, Michael J., Relations among complexity measures, J. Assoc. Comput. Mach. 26, 361-381 (1979). ZBL0405.68041.

Any ideas?
Furthermore, what is the space complexity of this emulation? As far as I know the conversion to a universal Turing machine only doubles the tape length. Can I assume that the space complexity is $\mathcal{O}\left(l\right)$ with $l$ the space complexity of the original Turing machine?


texts: Approximating distributions from samples

texts:
One claim I find in many papers about identity testing, and closeness testing is that any distribution over $[n]$ can be approximated to within $\ell_1$ distance $\epsilon$ in $O\left(\frac{n}{\epsilon^2}\right)$ samples.

I do not seem to be able to find a proof of this anywhere. On trying to prove it, I seem to be able to prove it if I assume that there exists $\delta>0$, such that, $\min_{i \in [n]} P_i > \delta$, where $P$ is the true distribution. However, I do not seem to be able to prove it in the general case.

My attempt at a proof is the following:

Let $P$ be any distribution over $[n]$. Let $X_1,X_2,\cdots,X_{\frac{n}{\epsilon^2}}$ be iid samples of $P$. Let $m=c\frac{n}{\epsilon^2}$. Define $C_i$, $1 \leq i \leq n$, as

$$C_i= \sum_{j=1}^{m} 1(X_j=i).$$

We note that $\mathbb{E}[C_i]= mP_i$.

Further from Chernoff bounding, we get that,

$$P[C_i > (1+\epsilon)mP_i] \leq \exp(-\epsilon^2 \frac{mP_i}{3})= \exp(-\frac{cnP_i}{3}).$$

Similarly,
$$P[C_i < (1-\epsilon)mP_i] \leq \exp(-\frac{cnP_i}{2}).$$

Thus defining $\hat{P}_i= \frac{C_i}{m}$, and $\hat{P}=(\hat{P}_1,\cdots,\hat{P}_n)$, by union bounding, we get that with probability at least $1-\sum_{i=1}^n 2\exp(- \frac{cnP_i}{3})$, we have that $||\hat{P}-P||_1 \leq \epsilon$. This gives a proof of the claim as long as there exists $\delta>0$, such that, $\min_{i \in [n]} P_i > \delta$ (as the probability can be made arbitrarily close to 1 by increasing the constant).

However, I do not know how I can generalise this result to the general case. I'd appreciate any help with respect to this.


texts: Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

texts:
We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$
where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), and ${\mathsf {NPI}}$ contains the  ${\mathsf {NP}}$-intermediate ones. Assuming ${\mathsf P}\neq  {\mathsf {NP}}$, both ${\mathsf {NPC}}$ and  ${\mathsf {NPI}}$ are known nonempty.

There is, however, a kind of strange asymmetry between ${\mathsf {NPC}}$ and  ${\mathsf {NPI}}$. Under the hypothesis ${\mathsf P}\neq  {\mathsf {NP}}$, we know not only that both sets are nonempty, but we also have plenty of natural problems that are provably in ${\mathsf {NPC}}$. On the other hand, to my knowledge, there is not a single natural  problem that has been proven to fall in ${\mathsf {NPI}}$, under the same ${\mathsf P}\neq  {\mathsf {NP}}$ hypothesis.

Note:  Even though there are quite a few natural candidates for ${\mathsf {NPI}}$ status,  none of them has been  proven to be in ${\mathsf {NPI}}$ under the ${\mathsf P}\neq  {\mathsf {NP}}$ hypothesis, as far as I know. The highly artificial construction provided by Ladner's Theorem does not qualify for a natural problem.

Thus, assuming ${\mathsf P}\neq  {\mathsf {NP}}$, the set ${\mathsf {NPC}}$ is teeming with natural examples, while for ${\mathsf {NPI}}$ we do not know even a single natural problem that is guaranteed to fall in the set under the same hypothesis. What could explain this strange asymmetry? Why is ${\mathsf {NPI}}$ so "thin" in this informal sense?


texts: Find the optimal way to use combinations of summands to get the most sum with a limited number of summands

texts:
I have a bit of a problem, I have a set of sums that add up to X, like so:

A: $i + j + k = X$

B: $t + z = X$

C: $z + z = X$

D: $j + j + k + k = X$

I have a limited number of summands so for example I have: 12 of $i$, 35 of $z$, 12 of $j$, and 18 of $k$, 21 of $t$.

What I need is an algorithm that will determine the best way to use those combinations so that I end up with the most complete sums of $X$

So in the example above using:

17 of combination $C$, 1 of combination $B$, and 12 of combination $A$, total 30 sums of $X$, 72 summands used

is worse then using:

21 of combination $B$, 7 of combination $C$, and 6 of combination $D$, total 34 sums of $X$, 80 summands used

EDIT:

To further explain:

using 21 of combination $B$ will "spend" 21 $t$ and 21 $z$ leaving us with: 12 of $i$, 14 of $z$, 12 of $j$, 18 of $k$, 0 of $t$

using 7 of combination $C$ will "spend" 14 of $z$ (because it uses 2 summands of $z$ to be achieved) leaving us with: 12 of $i$, 0 of $z$, 12 of $j$, 18 of $k$, 0 of $t$

using 6 of combination $D$ will spend 12 of $j$ and 12 of $k$ (because it uses both of them twice) leaving us with: 12 of $i$, 0 of $z$, 0 of $j$, 6 of $k$, 0 of $t$

we can no longer make combinations that will add up to $X$ thus the algorithm is concluded.


texts: Can $\mathsf{P}^{\#\mathsf{P}}$ be described in terms of a non-deterministic (alternating) Turing machine?

texts: Can the $\mathsf{P}^{\#\mathsf{P}}$ (= $\mathsf{P}^{\mathsf{PP}}$) class be described in terms of a non-deterministic Turing machine (in particular, an alternating Turing machine)? And would a $\mathsf{P}^{\#\mathsf{P}}$ machine be equivalent in computational power to any non-deterministic Turing machine? I suppose it should be because $\mathsf{P}^{\#\mathsf{P}}$ lies in between $\mathsf{PSPACE}$ and $\mathsf{PH}$ as per this, and both $\mathsf{PSPACE}$ and $\mathsf{PH}$ are describable in terms of alternating Turing machines. However, I could not find any description of $\mathsf{P}^{\#\mathsf{P}}$ or $\mathsf{P}^{\mathsf{PP}}$ in terms of alternating Turing machines, so far.


texts: Parametricity and projective eliminations for dependent records

texts:
It's well-known that in System F, you can encode binary products with the type
$$
A \times B \triangleq \forall\alpha.\; (A \to B \to \alpha) \to \alpha
$$
You can then define projection functions $\pi_1 : A \times B \to A$ and $\pi_2 : A \times B \to B$.

This isn't so surprising, even though the natural reading of the F type is of a pair with a
let-style elimination $\mathsf{let}\;(x,y) = p \;\mathsf{in}\; e$, because the two kinds of pair
are interderivable in intuitionistic logic.

Now, in a dependent type theory with impredicative quantification, you
can follow the same pattern to encode a dependent record type $\Sigma x:A.\; B[x]$ as
$$
\Sigma x:A.\;B[x] \triangleq \forall\alpha.\; (\Pi x:A.\; B[x] \to \alpha) \to \alpha
$$
But in this case, there isn't a simple way of defining the projective eliminators
$\pi_1 : \Sigma x:A.\;B[x] \to A$ and $\pi_2 : \Pi p:(\Sigma x:A.\;B[x]).\; B[\pi_1\,p]$.

However, if the type theory is parametric, you can use parametricity to show that $\pi_2$ is definable. This appears to be known --- see, for example, this Agda development by Dan Doel in which he derives it without comment --- but I can't seem to find a reference for this fact.

Does anyone know a reference for the fact that parametricity allows defining projective eliminations for dependent types?

EDIT: The closest thing I've found so far is this 2001 paper by Herman Geuvers, Induction is not derivable in second order dependent type theory, in which he proves that you can't do it without parametricity.


texts: Converting a Truth Table into k-CNF formula of Minimal Size in Linear Time

texts:
Let $T$ be a truth table of a boolean function $f$ on $n$ input bits.
More concretely $T$ could be a list of length $2^n$ such that $T[i] = f(bin(i))$, where $bin(i)$ is the binary representation of the integer $i$.

Now suppose that $T$ is the truth table of a function that has a small $k$-CNF representation, say a $k$-CNF representation with $O(n)$ clauses. Is there an algorithm that computes a $k$-CNF representation of $T$ with $O(n)$ clauses in time $O(2^n)$, i.e. linear in the size of the truth table? The algorithm does not necessarily have to choose the minimum sized representation, but it can't be more than a constant factor larger.

Naively, it is possible to convert $T$ into a CNF by the standard method (negate all zero inputs and and make these clauses) and it is possible to convert a CNF to a $k$-CNF, also by standard methods, but it is not clear that this method gives good guarantees on the size of the resulting $k$-CNF.

I apologize that I have not thought more about the solution before asking. I just want to make sure that the solution is not trivial (or unlikely based on complexity theoretic assumptions).


texts: Major open problems on polynomial kernel (non) existence

texts:
We are not able to settle the (non-)existence of a polynomial kernel for a parameterized combinatorial NP-complete problem (we also tried to apply some recent lower bound techniques to prove the non-existence of a polynomial kernel under reasonable complexity-theoretic assumptions). So we are searching for major open problems that could be used in a parameter-preserving reduction to "underline its hardness".

What are major parameterized NP-complete problems for which it is unknown if they have a polynomial kernel ? Is there a survey/technical report on the subject?

An example could be ODD CYCLE TRANSVERSAL (OCT), the task of making an undirected graph bipartite by deleting as few vertices as possible, parameterized by the number of allowed vertex deletions (though Stefan Kratsch and Magnus Wahlström recently showed a randomized polynomial kernel for OCT)


texts: Recommendation for a good book on first order logic w.r.t inductive logic programming

texts: I have had 10 days to read up on Computational Logic but the books I am following are only succeeding in confusing me. I find most of text's ( Niehuys-Cheng & de Wolf 1997, De Raedt 2008, Lloyd 1987 ) very wordy. None of them provide will worked out examples for, say, SLD-resolution. So I was wondering if anyone knows of a good book with nice examples which explain first order logic in an intuitive manner ? Thanks in advance.


texts: Advances in complexity by studying particular problems

texts:
When we are trying to figure out in which complexity class a problem lies, we usually try simultaneously to come up with the best algorithm for it, together with the best hardness reduction, until (ideally) they both match the same known complexity class.

Imagine we show that the problem is $A$-hard, and lies in $B$, and $B\subseteq A$ is known but $A=B$ is an open problem in complexity theory. Then it is very likely that we made an error, and we will focus on trying to find it. If there is no error, this is a proof of $A=B$.

I'm curious whether it actually happened, that advances in complexity theory were made this way ? I.e. were open problems on equality of classes solved by trying to find out the exact complexity of a particular problem ? It would be a nice example of serendipity (sort of) for computer scientists.

Notice that the "opposite" happened often: new complexity classes were created to describe the complexity of a particular problem, when it could not be matched to known classes, for instance Graph Isomorphism.


texts: Approximating non-trivial graph automorphism?

texts:
Graph automorphism is a permutation of graph nodes that induces a bijection on the edge set $E$. Formally, It is a permutation $f$ of nodes such  $(u,v)\in E$ iff $(f(u),f(v))\in E$

Define an violated edge for some permutation as an edge that is mapped to non-edge or an edge whose preimage is non-edge.

Input: A non-rigid graph $G(V, E)$

Problem: Find a (non-identity) permutation that minimizes the numbers of violated edges.

  What is the complexity of finding a (non-identity) permutation with minimum number of violated edges? Is the problem hard for graphs with bounded maximum degree $k$ (under some complexity assumption)? For instance, Is it hard for cubic graphs?

Motivation: The problem is a relaxation of graph automorphism problem (GA). The input graph may have non-trivial automorphism (e.g. non-rigid graph). How difficult is it to find an approximate automorphism (closet permutation)?

Edit April 22

A rigid (asymmetric) graph has only trivial automorphism. A non-rigid graph has some (limited) symmetry and I'd like to understand the complexity of approximating its symmetry.


texts: Reference request: a more complete "faster factorization into coprimes"

texts:
Some months ago, before the advent of "CS-Theory", I asked a question on MathOverflow about efficiently factoring an integer N into coprime factors n1 and n2, where n1 is a multiple of a given a factor d of N.

One of the answers pointed me to Dan Bernstein's website, which has notes on obtaining a coprime base for a set of integers (and algorithms which work in more general settings than integers). For a set S of integers, a coprime base cb(S) is a set of integers which are coprime to one another, such that each element of S factors (uniquely) as a product of elements of cb(S). Bernstein's site has

An article dating from 1998, about constructing a coprime base in "essentially linear time", which is to say time  n log (n)O(1)  (where n is the number of input bits, or equivalently the logarithm of the product of the input set) and;
A draft manuscript from 2004 (which announces its own preliminariness), on "faster factorization into coprimes", which gives a sketch of how to compute a coprime base in time  n log (n)2+o(1) .

After a search for a "more complete" version of the second, or follow-up work by others, I was unable to find much more than links to one or the other of these articles, and slide-show presentations which again point to these articles.

Question. Has there been any more development of the ideas of "Faster factorization into coprimes" — possibly by different authors — into a finished article with the run-time as described above? Or is this accepted by the community as essentially complete?

(Edit: as I've now noted in the comments, Dan Bernstein himself says that he has not yet finished his results. But I'm still interested in finished results by others with comparable run-times, possibly for special cases, but only over the integers.)


texts: Why were Finite Automata and Turing Machines created?

texts:
It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed independently of each other. So 'what' were the founding reasons of each of them? Why were they developed? What questions were each of the mathematical models aiming to answer?

I'm aware of TMs being created for answering the Entscheidungsproblem proposed by David Hilbert and it's leading to answer questions as to what is computable and what isn't. Then what about FAs? On another question an answer pointed me to a paper talking about nerve nets and Kleene's papers (both of which I hadn't read before. I didn't even know FAs were traced back to nerve nets.) So what was it that FAs were trying to answer at that time that wasn't answerable by TMs or was too cumbersome to do so? (I don't really know what nerve nets are and what FAs have to do with them. Perhaps the answer lies there?)

Reason for question: ToC is usually taught in a progression from D/N-FAs to PDAs to TMs but all of them were independently created, decades apart. The logical progression subconsciously implies a chronological sequence of 'discovery' but that isn't true and am trying to understanding their genesis better, out of curiosity. It'd be great to have the 'intentions/needs' of creating both of them in one place to better my understanding of the same. I'd also like to use this as a teaching aid if possible for the undergrads who fail to understand the essence of ToC


texts: Is there any non-trivial approximation algorithm for a variant of betweenness problem: namely, we want to minimize the number of unsatisfied triples rather than to maximize the number of satisfied ones?


texts:
Is it possible to convert a string to a unique number.

Similar to any hashing algorithm (MD5, SHA-1 and SHA-2), I want to compute a unique integer value for an arbitrary length string, which should be collusion resistant, hard to invert, and easy to compute.

Can you name the technique to compute it, so that I can dig into the theory of it.


texts:
Given a multivariate cubic equation $f(\vec{x})$ over reals where all coefficients of $f$ are integers, and a hyper-rectangle $B=\bigwedge_i x_i\in[a_i, b_i]$ where $a_i, b_i$ are constant integers, the problem is to check whether $f$ has a zero in $B$.

What’s the complexity of this problem?

Obviously, it is in PSPACE; more precisely, it is a special case of the existential theory of the reals, hence it is in the class $\exists\mathbb R$. A related problem (denoted here as 4FEAS), viz. to check whether a quartic equation with integer coefficients (even without constraints in $B$) has a real zero is $\exists\mathbb R$-complete. Likewise, checking whether a set of quadratic (or cubic) equations has a common zero is $\exists\mathbb R$-complete. On the other hand, if one drops the constraint of $B$, a zero exists trivially if the cubic equation is nondegenerate. Hence, an obvious question is, can we reduce 4FEAS to the current problem?

A variant of 4FEAS with real coefficients is $\mathrm{NP}_\mathbb R$-complete in the Blum–Shub–Smale model, but this question is about the Boolean Turing model, not BSS.

A related question is here: Checking whether two quadratic equations have a common zero


texts: Current research topics in tree automata

texts:
What are current research topics connected with tree automata?
I'm particularly interested with connection between automatas, logics and databases.
Kind regards,
XYZ


texts: Max cut problem between two connected subgraphs

texts:
Let $G$ be a connected graph.

Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known about this, e.g. complexity, approximation, randomized algorithms, etc.?

The situation without connectedness is MAX-CUT. The situation when only $A$ is required to be connected has been studied here: https://arxiv.org/abs/1507.00648

I'm also interested in the case when $A$ and $B$ are required to be of roughly equal size.


texts:
everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to collect such problems?

I've already found a related question about NP-hard problems on trees.


texts: Which algorithm can do a stable in-place binary partition with only O(N) moves?

texts:
I'm trying to understand this paper: Stable minimum space partitioning
in linear time.
It seems that a critical part of the claim is that

Algorithm B sorts stably a bit-array of size n in
O(nlog2n) time and constant extra space, but makes only O(n) moves.

However, the paper doesn't describe the algorithm, but only references another paper which I don't have access to.   I can find several ways to do the sort within the time bounds, but I'm having trouble finding one that guarantees O(N) moves without also requiring more than constant space.
The reference is to "Stable in situ sorting and minimum data movement" by J.I. MUNRO, V. RAMAN, et al. Googling reveals that that pair has also published several papers on related topics, including "Fast stable in-place sorting with O(n) data moves. Algorithmica 16, 151–160." So I think it is a real technique (at least in theory). But I've been unable to figure out how to create a working version.
What is this Algorithm B? In other words, given
boolean Predicate(Item* a);  //returns result of testing *a for some condition

is there a function B(Item* a, size_t N); which stably sorts a using Predicate as the sort key in O(N lg N) time, and performs only O(N) writes to a?
I asked this on StackOverflow, I haven't got any good responses.


texts: For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

texts:
The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows:

Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$.
Question: Does there exist $k$-pairwise vertex-disjoint paths $P_1,\ldots,P_k$, such that $P_i$ goes from $s_i$ to $t_i$?

The problem, for general $k$, is known to be NP-complete even for planar graphs of max degree 3.
That said, $2$-$\text{DPP}$ admits a nearly linear algorithm for general undirected graphs.
Is there anything known for any higher value of $k$ (assuming fixed $k$ value)? What about $k=3$?


texts: Rapidly mixing Markov chains on 3-colorings of a cycle

texts:
The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a 5-cycle: there are 30 3-colorings, but only 15 of them can be reached by single-vertex recoloring steps. More generally, it can be shown not to mix for 3-colorings of an n-cycle unless n=4.

The Kempe chain or Wang-Swendsen-Kotecký dynamics is only a little more complicated: at each step one chooses a random vertex v and a random color c, but then one finds the subgraph induced by two of the colors (c and the color of v) and swaps these colors within the component containing v. It is not hard to see that, unlike the Glauber dynamics, all 3-colorings of a cycle can be reached.

Is the Wang-Swendsen-Kotecký dynamics rapidly mixing on 3-colorings of an n-vertex cycle graph?

I know of the results e.g. by Molloy (STOC 2002) that Glauber is rapidly mixing when the number of colors is at least 1.489 times the degree (true here) and the graph to be colored has high girth (also true), but they also require that the degree be at least logarithmic in the size of the graph (not true for cycle graphs), so they don't seem to apply.


texts: Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?

texts:
Let $M$ be a probabilistic Turing machine with a unary input $n$ whose
space is bounded by a polynomial in $n$ and
its output is a distribution $D$ over binary strings.
Note that the number of random bits that $M$ can use can be exponential in $n$.

Can $D$ be "approximated" by
a probabilistic polynomial space-bounded Turing machine
which uses only a polynomial number of random bits?

More formally,

  Let $M$ be a TM with space bound $s$.
  Is there a probabilistic Turing machine $N$ using poly(s) space and random bits with the following property:
  $$\forall k<s \ \left(Pr[M = x] > 2^{-k} \implies
Pr[N = x] > 2^{-k - O(\log s)} \right)$$


texts: Correctness of AKS algorithm for shortest vector problem

texts:
Short question

In the end of section 1 of Regev's notes about the AKS algorithm for SVP, why is the following true?

  for each such $i$,$y_i− x_i$ remains $w$ with probability $1/2$ or otherwise becomes one of $w+v$ or $w−v$.

Extended question

AKS finds a shortest non-zero vector of any $n$-dimensional Euclidean lattice $\Lambda$ in time $2^{O(n)}$.

Actually, it is a randomized algorithm and the output is correct with very high probability, say $1 - 2^{\Omega(n)}$.

Although the intuition about why the output is correct with high probability is simple, the proof is rather technical and it basically goes like this:

The algorithm samples a set of vectors $x_1, ..., x_N$ in the beginning. To each of those vectors, one lattice point is associated (the number of lattice points is much smaller than $N$, so a lot of $x_i$ maps to same lattice point). To prove that the algorithm works (with overwhelming probability) you substitute the sampling method so that if $x_i$ is in a specific region $C_1$, then it is replaced by $x_i + v$, if it it lies in another specific (symmetric) region $C_2$, then it is replaced by $x_i - v$, or it continues to be $x_i$ otherwise, where $v$ is a shortest vector.

Then, the goal is to show that for at least one pair of vectors $x_i$ and $x_j$ that map to a same $w \in \Lambda$, we have $x_i \in C_1 \cup C_2$ and $x_j \not \in C_1 \cup C_2$, so that the difference of the associated lattice points become $(w \pm v)  - w = \pm v$, which is a shortest vector.

But I don't understand the analysis of the probabilities involved in this step. Since the vectors $x_i$ considered in the end of section 1 of Regev's notes are all points in $C_1 \cup C_2$, all of them should be "flipped" around $v$, then $w$ would never remain $w$.


texts: The complexity of sampling (approximately) the Fourier transform of a Boolean function

texts:
One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P.

Here and below when I talk about sampling the Fourier transform I mean choosing x according to $|\hat f(x)|^2$. (Normalized if necessary and approximately).

Can we describe the complexity class, that we can call P-FOURIER SAMPLING, of approximate sampling Boolean functions of P? Are there problems which are complete for this class?

Given a class X of Boolean functions what can be said about the the computational complexity, that we can refer to as SAMPLING-X of approximating sampling the Fourier transform of functions in X. (I suppose that if X is BQP then X-SAMPLING is still within the power of quantum computers.)

What are the examples of X where SAMPLING-X is in P? Are there interesting examples where SAMPLING-X is NP-hard?

There are several variants of this problem that can also be interesting.
On the Fourier side, rather than approximate-sample we can talk about a decision problem enabled (probabilistically) by approximate sampling. On the primal side, we can start with a class X of probability distributions and ask what is the relation between the ability to approximately sample a distribution D in X and approximately sample the (normalized) Fourier transform.

In short, what is known about this question.

Update: Martin Schwarz pointed out that if all the Fourier coefficients themselves are concentrated only on a polynomial number of entries then it is possible in BPP to approximate these large coefficients (and thus also to approximately sample.) This goes back to Goldreich-Levin, and Kushilevitz-Mansour. Are there interesting classes of functions where there is a probabilistic polynomial algorithm for approximately sampling the Fourier side, where the Fourier coefficients are spread over more than polynomially many coefficients?

Added Later: Let me mention a few concrete problems.

1) How hard is it to approximately sample the Fourier transform of Boolean functions in P.

a) One question that Scott Aaronson mentioned in a comment below is to show that this is not in BPP. Or something weaker along the lines that if this task is in BPP some collapse is happening.  (Scot Conjectures that this is the case.)

b) Another question is to show that this task is hard with respect to some quantum-based complexity class. E.g, to show that if you can perform this task you can solve decision problems in BPP assisted with log-depth quantum computers, or something like that.

2) What are classes of Boolean functions such that approximately sampling their Fourler transform is in P. What we know is that this is the case when the Fourier coefficients are concentrated on polynomial many coefficients, but this seems very restricted.

3) Is there some complexity class X high up in the PH that an X-machine can approximately sample the Fourier transform of every function that an X-machine can compute.

4) I was especially interested in the problem of sampling the Fourier transform of the crossing event for percolation on an n by n hexagonal grid.


texts: Lambda-Calculus terms that reduce to themselves

texts:
In my continuing quest to try to learn lambda calculus, Hindley & Seldin's "Lambda-Calculus and Combinators an Introduction" mentions the following paper (by Bruce Lercher) which proves that the only reducible expression that is the same (modulo alpha conversion) to itself is: $(\lambda x.xx)(\lambda x.xx)$.

While I believe the result, I do not follow the argument at all.

It is quite short (less than one paragraph).  Any explanations would be most welcome.

Thanks,

Charlie


texts:
I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching".

Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that the weight is given by a profit function $p:{V\choose 2}\to \mathbb N$. Given a matching $M$, denote by $M(v)$ the profit of the edge $v$ is matched with.

A matching $M$ is a fair matching iff, for any two vertices $u,v\in V$:
$$(\forall w\in V:\ \  p(\{w,v\})\geq p(\{w,u\}))\to M(v)\geq M(u)$$

That is, if for any vertex $w\in V$, matching $w$ to a vertex $v$ gives higher profit than matching it to a vertex $u$, a fair matching must suffice $M(v)\geq M(u)$.

  Can we find a maximum weight fair matching efficiently?

An interesting case is when the graph is bipartite and the fairness only applies to one side, that is assume that $G=(L\cup R,L\times R)$, and we are given a profit function $p:L\times R\to \mathbb N$.

A Fair Bipartite Matching is a matching in $G$ such that for any two vertices $u,v\in L$:
$$(\forall w\in R:\ \  p(\{v,w\})\geq p(\{u,w\}))\to M(v)\geq M(u)$$

  How fast can we find a maximum weight fair bipartite matching?

The motivation for this problem comes from the bipartite special case.
Assume you have $n$ workers and $m$ tasks, and worker $i$ can produce $p_{i,j}$ profit from work $j$. To problem here is to design a reasonable (in a sense workers will not feel "ripped-off''), while maximizing the total payoffs. (There is a tradeoff here between the power of the assignment mechanism and the social benefit).

If we define the social-welfare (or the factory profit) of the assignment of workers to jobs as the sum of profits.

Looking at different scenarios for the power of the job assigner, we get the following results:

If we are allowed to assign any worker to any job, we can optimize the factory efficiently (just find a maximal-weight matching).
If every worker chooses a task on his own, assuming that his work will be selected (only a single work can be selected for each job) should he be the most qualified worker that chose the task, workers will converge into the ''greedy'' equilibrium. The reason is that the worker that could earn the most ($i=\mbox{argmax}_i \max_j p_{i,j}$) will choose the most profitable job, and so on. By the approximation rate of the greedy algorithm for matching, this should give a 2-approximation of the maximal social-welfare possible.

I'm looking for something in-between. Let's assume we could assign workers to jobs, but have to promise them that no "less-qualified" worker earns more than them.

  How can we find a maximal weight matching promising "fairness" to employees efficiently?


texts:
Let $A,B\in\mathbb{F}^{n\times n}$ be two $n\times n$ matrices over
the underlying field $\mathbb{F}$. In addition, $A$ is guaranteed
to be a symmetric matrix, i.e, $A=A^{T}$. We assume complexity measure to be the number of field operations over $\mathbb{F}$. Now consider at the following problem:-

  Given $A,B$ and $AB$ as input, can we compute $AB^{T}$ in $o(n^{\omega})$ time?

Here $\omega$ is the exponent of matrix multiplication. Note that $AB^{T}=A^{T}B^{T}=(BA)^{T}$.
Thus computing $BA$ in $o(n^{\omega})$ time is also enough.


texts:
Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v) > \frac{\epsilon}{2}n$. A simple uniform sampling of edges between $v$ and the other vertices, together with the Chernoff bound, tells us that we need $\Theta\left(1 / \epsilon^2 \right)$ samples in order to decide with high probability which is the case.

Now consider a (seemingly) easier problem: under the same settings, decide whether $\mathrm{deg}(v) < \epsilon^2 n$ or $\mathrm{deg}(v) > \epsilon n$. Again the Chernoff bound tells us that we need $\Theta\left(1 / \epsilon^2 \right)$ samples in order to decide with high probability which is the case. Same goes for deciding whether $\mathrm{deg}(v) < \epsilon^c n$ or $\mathrm{deg}(v) > \epsilon n$ for $c$ as large as we want.

This is somewhat counter intuitive to me, as loosely speaking, if $\mathrm{deg}(v) > \epsilon n$, and we sample $\Theta(1/\epsilon)$ edges, we can expect to catch at least one edge with a constant probability - as opposed to the case that $\mathrm{deg}(v) < \epsilon^2 n$, wherein if we only sample $\Theta(1/\epsilon)$ edges, we can expect to catch at least one edge with a probability that is proportional to $\epsilon$.

Is it really the case that number of samples needed to decide whether $\mathrm{deg}(v) < \epsilon^c n$ or $\mathrm{deg}(v) > \epsilon n$ is asymptotically the same for every $c$, or is there a stronger concentration of measure bound that shows we can use less than $\Theta\left(1 / \epsilon^2 \right)$ samples?


texts: Analysis of variables of varying numbers

texts:
I work with amino acid sequences and I want to use a self-made model to tell me something about it, let's call it f(seq). Now I want to know the contribution of every position in the sequence onto the model. E.q. My question is what is the importance/effect of amino acid A occurring at position I in the sequence with respect to the model?

How do I visualize something like that?

I want to use my model also on several sequences of differing lengths. Somehow this throws a monkey wrench into my plans of using a neural net...

My question is simple yet I did not find anything about it. Pointers would be appreciated. Or any comment you might have. This whole idea of mine is pretty unfinished and I don't really know yet what I want. So feel free to criticize, I will update the question accordingly.


texts: Recommendations for References on undecidability of First Order Logic

texts: I am currently reading Computability and Logic by Boolos Burgess Geoffrey for the proof on "undecidability of first order logic". however, I find the notations a bit confusing. Can anyone recommend any resource website link/ video lecture or a book perhaps which will help me understand the proof of undecidability of first order logic? I am a CS student so, I do not want a completely mathematical /philosophical proof. I came across plenty of those on the web.


texts: Shortest simple path with minimum edge cost minus node reward

texts:
I have a directed graph which has cycles.
Each edge has a nonnegative weight and each vertex has a nonnegative reward.

Given two vertices s and t, I need to find a simple path (a path with no repeated vertices) from s to t which minimizes

(sum of edge weights on the path) - (sum of vertex rewards covered by the path).

One can surely absorb node reward into edge weight like this post, but then the edge weight can become negative and negative cycles can emerge.  As a result, the shortest simple path, if posed in such a general setting, is NP-hard (eg this post).

However, some hints from submodular analysis suggest this problem is not NP-hard. Can we find an efficient algorithm?

Many thanks in advance.

Follow-up:

Please see this post for a "proof" which gave me the (wrong) hint.


texts: Number of accepting path of a non deterministic automaton

texts:
I have a question that seems to me really natural and have probably already been studied. But keyword search on this site or google does not seems to help me to find any relevent paper.

I have got a finite non deterministic automaton $A$ over an alphabet $\alpha$ without epsilon-transition.

What can I tell about the number of different path the automaton could take for accepting a word ? In particular, I want to know if this number is bounded, or if for every $c$ I can find a word $w_c$ that is accepted in at least $c$ different way by the automaton.

Right now, I can find some necessary, and some sufficient condition, but not any necessary and sufficient condition, for the number to be unbounded

By clarity, I'll define the way I cound the number of accepting path. Let $w\in\alpha^*$ and $q$ a state, I can define the number of path to $q$ by inuction on $|w|$ by $N(\epsilon,q)=1$ if $q\in I$ else $0$, where $I$ is the set of initial state and $F$ of final state. $N(ws,q)=\sum_{q'\in Q\atop \delta(q',s)=q}N(w,q')$.

Then the number of path is $\sum_{q \in F}N(w,q)$.


texts: Can one find good distance-2-separators in planar graphs?

texts:
It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph.

However, it seems that this specific approach does not lead to a PTAS for the MINIMUM DOMINATING SET problem (MDS), whereas other approaches do, see E. D. Demaine and M. Hajiaghayi: Approximation Schemes for Planar Graph Problems (1983, 1984; Baker).

In T. Nieberg and J. Hurink: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs (also accessible here), the authors define the notion of 2-separated sets, that is, a collection of subsets of vertices of a graph such that two vertices from different sets are at distance at least two from each other.
If a graph admits such a set (with additional suitable properties), they prove that MDS admits a PTAS. This is the case for unit disk graphs for example.

This notion is really similar to the technique of recursive separators in planar graphs, except for the distance-2 requirement. So my question:

Do good (in the sens of usual separators) "distance-2-separators" exist in planar graphs, and if yes, can we compute them efficiently?


texts: Practical/heuristic algorithm for multi set-cover

texts:
Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ number of times using minimum number of sets from $\mathcal{C}$. (When $k=1$, the problem reduces to min-set cover).

Are there any heuristics out there with 'good' performance on 'real' data for $n=1000$ and $|\mathcal{C}| = 1000$?


texts: Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

texts:
The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the Complexity Zoo for definitions. An alternative definition defines $\mathsf{W}[t]$ using weighted Fagin definability for $\Pi_t$-formulas of first-order logic, see the textbook by Flum and Grohe.

For the lowest classes $\mathsf{W}[1]$ and $\mathsf{W}[2]$, many natural complete problems are known, e.g. Clique and Independent Set are complete for $\mathsf{W}[1]$ , and Dominating Set and Hitting Set are complete for $\mathsf{W}[2]$, where each of these problems is defined as the corresponding well-known $\mathsf{NP}$-complete problem with the size of the required solution set as the parameter.

Are there any known natural complete problems for classes higher up in the $\mathsf{W}$-hierarchy, in particular for $\mathsf{W}[3]$ and $\mathsf{W}[4]$?


texts:
There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively.

In the traditional loyd shapeley algorithm for $n$ men and $n$ women, given randomly generated preference lists its expected that the average place of a man's wife will be $\log n$ and the expected place of a woman's husband will be $\frac{n}{\log n}$ on their preference lists (after pairing).

We can look at the pair $\left( \log n , \frac{n}{\log n} \right)$  and ask, given unlimited computing resources what is the smallest possible $d(n)$ for which we can guarantee that a stable matching of $n$ men and $n$ women with uniform randomly generated preference lists both have expected place of their partner equal to: $\left(d(n), d(n) \right)$?

Trivially  $d(n) \le \frac{n}{\log n}$ but i'm curious how much lower $d(n)$ has been bounded by current research.


texts: Quadratic Binary Optimization formulation of Steiner Tree problem

texts:
can someone point out to me a solution or give advice on how to formulate as efficiently as possible in terms of number of bits the minimum Steiner tree problem as a 0-1 quadratic optimization problem?

Edit [Context]: I am trying to find useful applications of quantum optimization (which attacks 0-1 quadratic unconstrained problems) and I thought that the minimum Steiner tree problem was a great starting point.


texts:
Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it must be possible to insert leaves as well as internal nodes. Deletion is not needed. $M$ can only grow by adding new vertices as they are inserted into $V$ (no existing vertices of $V$ will be added to $M$ at a later point in time).

I need an algorithm that given any vertex $v \in V$ (not necessarily in $M$), it will find the nearest ancestor $u \in M$ of $v$, with space preferably being not worse than linear in $|V|$ and/or $|M|$ and time being somewhat logarithmic in $|M|$. Also the updates should be efficient.

This is known as the Marked Ancestor Problem [1] and also goes under the names of two-dimensional range searching and union-find problems. The problem with [1] is that for once it doesn't support insertion of internal nodes, and also it is extremely abstract and I definitely can't derive an algorithm and an implementation from it.

Also in my case, a solution involving Informative Labeling [2] would be highly desirable.

[1] S. Alstrup, T. Husfeldt and T. Rauhe, Marked Ancestor Problems. focs, pp.534, 39th Annual Symposium on Foundations of Computer Science, 1998
[2] D. Peleg, Informative labeling schemes for graphs. Mathematical Foundations of Computer Science, pp. 579--588, 2000

Here is another approach, maybe it can be "fixed": I can maintain versions of the tree which are linearized by a total order, one using pre-order traversal, the other using post-order traversal, using an approach developed by Dietz [3]. With these two lists I can query in $O(1)$ whether a vertex $u$ is an ancestor of another vertex $v$ in the tree ($u$ must be left of $v$ in the pre-order list and right of $v$ in the post-order list). If I could organize my vertices $M$ in a way that I can find the nearest ancestor of $v$ in logarithmic or polylogarithmic time, the problem is solved. Right now I can just go through all elements of $M$ and collect the nearest ancestor (closest to $v$ in the lists) in $O(|M|)$...

[3] P. Dietz, Maintaining order in a linked list. Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 122--127, 1982


texts: Approximation for accumulative set cover

texts:
Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\\{1,\ldots,m\\}$, I want to maximize  the quantity
\begin{equation}
\sum_{k=1}^m\left\lvert\bigcup_{i=1}^k S_{\pi(i)} \right\rvert.
\end{equation}
This problem is NP-complete as it contains Exact cover by 3-sets as a special case: Suppose $n$ is divisible by 3, say $n=3n'$, and all sets $S_i$ have size 3. Then the upper bound
\begin{equation}
3(1+2+\cdots+n')+(m-n')n
\end{equation}
can be achieved if and only if $U$ can be covered by $n'$ of the 3-sets. I'm interested in the hardness of approximation. For instance, can the hardness of approximation for set cover be used to say something about the above problem?


texts: Linear ordering of bipartite tournament graphs

texts:
I have an ordered bipartite graph such that every node of the first node set is connected to every node in the second node set by an edge of a given direction (i.e., a so-called bipartite tournament graph). The direction of a given subset of the edges may be reversed, the direction of the others not.

I want to determine a minimal set of edges which are reversible and which need to be reversed such that the graph becomes acyclic.

Does anyone know an integer programming formulation for this?


texts: Why is the first step in the Lovasz-Vempala convex volume algorithm correct?

texts:
I've been reading about convex volume estimation, and have found the paper "Simulated Annealing in Convex Bodies and an $O^{*}(n^4)$ Volume Algorithm" by Lovasz and Vempala, which can be read here.

The algorithm provided relies the standard multi-phase monte-carlo technique of producing a series of values, the first of which is easy to compute, the remainder estimatable by random variables, and then combining each of these variables in some way to produce an estimate of the volume. This particular technique involves extruding an $n$-dimensional shape into an $n+1$-dimensional pencil, and estimating the volume of that pencil. The pencil is defined as the intersection of a cylinder over the convex body and a cone. Let $K$ be the convex body, and

$$
C = \{{\bf x} \in \mathbb{R}^{n+1} | x_0 > 0, \; \sum^n_{i=1}x_i^2 \leqslant x_0^2\}
$$
The pencil, $K'$, is defined:
$$
K' = ([0,2D] \times K) \cap C
$$

By assumption, $K$ contains the unit ball, so the set of points in $K'$ with $x_0<1$ is exactly the $n+1$-dimensional hypercone with height $1$ and whose base is the $n$-ball of radius $1$. This cone is referred to as $C_B$. We also denote by $\pi_n$ the volume of the unit n-ball. The estimates of the volume of the pencil are provided using the following function:

$$
Z(a) = \int_{K'} e^{-ax_0} d{\bf x}
$$

For a sufficiently small value of $a$, $Z(a)$ can be shown to be a good estimate for the volume of $K'$. For $a \geqslant 2n$, it is claimed that $Z(a)$ is close to the above integral taken over the entire cone $C$. We know that $K' \subseteq C$ from its definition, hence

$$
Z(a) = \int_{K'} e^{-ax_0} d{\bf x} \leqslant \int_{C} e^{-ax_0} d{\bf x} = \int_0^\infty e^{-at}t^n \pi_n dt = n! \pi_n a^{-(n+1)}
$$

We know also that $C_B \subseteq K'$, hence

$$
Z(a) \geqslant \int_{C_B} e^{-ax_0} d{\bf x} = \int_0^1 e^{-at}t^n \pi_n dt
$$

At this point, I can no longer follow the paper's reasoning. It is stated that

$$
\int_0^1 e^{-at}t^n \pi_n dt > (1-\varepsilon) \int_0^\infty e^{-at}t^n \pi_n dt
$$

No bounds are specified on $\varepsilon$. Indeed, our estimation algorithm should be able to take an arbitrarily small value of $\varepsilon$. The integrand, hovever, is non-negative across its domain of integration, so it must be the case that

$$
\int_0^1 e^{-at}t^n \pi_n dt \leqslant \int_0^\infty e^{-at}t^n \pi_n dt
$$

Surely, then, the inequality in $\varepsilon$ would only hold for a sufficiently large value of $\varepsilon$, rather than for an arbitrarily small one. Further, stating that $a\geqslant 2n$ gives no information about a relationship between $\varepsilon$ and $a$. How is it even possible to reach the conclusion from the premise in this case? Further still, an independent talk on the algorithm found here suggests instead that the inequality only holds for $a>6n$, rather than $a>2n$. The paper states that this is true by standard computation, so I do feel that I must be missing something here, but I cannot tell what.

I've emailed both of the authors at the email addresses I can find for them, and haven't received any response from them, so hopefully someone from here can help.


texts:
It seems that many results in complexity hold assuming PH doesn't collapse to the second or third levels.  At these low levels, I have some intuition about the collapse not occurring since additional quantifiers seem to add power not already inherent in the lower levels, but higher levels escape my understanding.

Basically, are there any known results that separate levels of PH assuming other complexity theoretic separations?  Is there any intuition that PH doesn't collapse to some finite level other than its generalization from P vs. NP and logical hierarchies?


texts: Deciding whether DCFG is visibly pushdown

texts:
Is the following problem decidable?
If so, what's the best algorithm known?

Instance: a deterministic pushdown automaton $A$
Question: Does there exist (i) some partition of the alphabet into push, pop, and level symbols and (ii) a visibly pushdown automaton that recognizes the language accepted by $A$?


texts: expected number of edges for fixed min cut

texts:
It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges.

Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ follows a particular random graph model? Or if it is bipartite?


texts:
I would like to know whether the following problem can be decided in $\mathsf{NL}$ (nondeterministic logspace):

Given a directed graph $G$ with two distinguished vertices $s$ and $t$, is there a unique path from $s$ to $t$ in $G$?

I feel that it is likely to be in $\mathsf{NL}$ since we can decide both if there is a $s$-$t$-path and if there is no such path. Yet, counting the number of such paths is $\mathsf{\sharp P}$-hard (Valiant, 1979).

So my questions: Do you have references about this? Is it obvious that it is in $\mathsf{NL}$? Or that it is not in $\mathsf{NL}$?


texts: Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?


texts: What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

texts: What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good approximation algorithms for long standing open questions related to NP-hard optimization problems.


texts: Find a function that combines a set of integers and outputs an integer. This output can be used to deduce the absence of any integer in the set.

texts:
Lets say that I have 50 events that generate some unique number (you are free to choose the number, but they should all fit in a 32 bit variable). I want to combine those numbers into a single number(32 bit), which can be used to find the absence of an event (i.e. a number).

If it was just ~10 events, I could have just used prime numbers and multiplied them, but multiplying first 50 primes results in 1.9x10^91 (which will not fit in a 32 bit variable).

Can anyone think of a better way to do this?


texts: Most efficient algorithm to search an unsorted array with a very precise data structure

texts:
(I apologize in advance if this question sounds a bit practical, but I suspect it might have an interesting theoretical aspect.)

I have a (large) array of data, not completely sorted, but with which has a very precise structure, defined as follows.

The array has a length that is a (very large) power of 4.

The data is such that:

if the array is split in 4 parts - all of the same number of elements - then in each part the first element is the Minimum of this part, and the last element is the Maximum of this part (minimum < maximum).
if we take any one of these parts and, within it, we repeat the subdivision in 4 equal parts, the above fact holds always again for each of the new parts, all the way down, until we arrive at the smallest part, of size 4 elements.

(in other words a sort of "fractal" arrangement, we might perhaps say (?)).

Question:

I need to search this array for a given specific value.

What would be the most efficient algorithm to perform the search, given the above structure
And what is the best complexity I should expect for this task

(I would also like to know if this sort of problem is well known and has a name and there are additional pointers I can read read. Thank you)


texts: Evidence of non P-hard problems that require polynomial space?

texts:
It is admitted that a $\mathsf{P}$-complete problem requires polynomial space and thus cannot be efficiently parallelized. One purpose of these problems is that they can be used to 'defeat' an (untrustworthy?) adversary with massively parallel computing abilities (e.g. cluster computing) : assuming that we have access to a sequential computer with higher clockrate than the adversary's, we may hope to solve a $\mathsf{P}$-complete problem faster than him due to its intrinsic sequentiality.

However, there are some polynomial problems which precise space complexity is unknown. Prominent examples come from computational biology problems, with typical examples being the sequence and tree alignment problems (such as LCS/MAST which are usually solved by dynamic programming). While not believed to be $\mathsf{P}$-complete, the only 'speedups' known for these problems use variants of DP (such as sparse dynamic programming) and do not lend themselves to parallelisation.

Whence the following question: is there any theoretical evidence of polynomial problems outside of ($\mathsf{P-complete} \cup Dspace(n^{o(1)})$)?

(NOTE ADDED: I suspect that the above mentioned problems are in $NC_2$, so they're not a good illustration of my point; I'll look for other examples.)


texts: Is there a relationship between relational algebra/calculus and category theory?

texts:
I am aware of at least two different theoretical approaches for understanding relational databases: Codd's relational algebra/calculus, and category theory.

Is there any relationship between these two approaches? Are they in some sense equivalent? Is there any introductory work explaining how both of these frameworks explain relational databases?

Background:
A while ago I read David Spivak's Category Theory for Scientists which spent quite some time discussing how category theory could be applied to understand the theory of relational databases. However, having little personal experience about what relational databases are or why they are useful, at the time I did not fully appreciate the depths of insight found in the book.

However, recently I have been learning about SQL queries and two R packages for data manipulation: dplyr and data.table. SQL can apparently express much of the ideas of Codd's relational algebra/calculus/model, but not all. Moreover, the author of dplyr, Hadley Wickham, has stated explicitly that his philosophy underlying the package is based on Codd's work on relational algebra, and the basic commands of data.table map fairly well to commands in SQL and dplyr.

I also know that category theory influences a lot of programmers using functional programming languages like Haskell. However, I am not really aware of there being any use of functional programming for data manipulation or data science, besides Hadley Wickham's purrr package for R, the fact that Apache Spark is written in Scala, and technologies related to MapReduce.

All of this sort of suggests to me that there should be some sort of relationship between category theory and Codd's relational algebra/calculus, but I have never heard of anyone making such a connection explicit or explain how it underlies the design decisions in popular data manipulation and relational database technologies. So I also suspect I could be entirely wrong.

EDIT: Apparently David Spivak has worked on a "functorial query language (FQL)". This sounds like it might be an application of such a theoretical connection, provided it exists.

Note: I am not sure if "relational-structures" is the appropriate tag for discussion of relational databases or relational algebra/calculus. This Wikipedia article suggests they might be connected, but ultimately I don't know what the phrase "relational structure" means. Please feel free to re-tag.


texts: Complexity of generating a pseudo-Boolean function

texts:
A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to
$\mathbb{R}$.

Following is a pseudo-Boolean function.

$$s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - s_1 s_5 - s_3 s_5 +
 s_2 s_4 + s_2 + s_4 - s_1 - s_2 + 3 s_1 s_2$$

Here, $s_i$'s are the Boolean variables taking values from $\{0, 1\}$. It has two solutions for the global minima, $01101$ and $10101$.

I would like to know what is the best known algorithm to generate a pseudo-Boolean function from a given list of solutions.


texts: Finding largest subgraph that contains a given edge and admits a cycle cover

texts:
I am wondering whether there exists a fast algorithm for the following problem.

  Given a digraph $G$ possibly with loops (that is edges that begin and
  end at the same vertex) and the choice of an edge $e \in G$, what is
  the largest (in terms of number of vertices) subgraph of $G$ that
  contains $e$ and admits a vertex disjoint cycle cover.

ps: sorry for the crosspost, but I originally posted at at stackoverflow and was directed here for a possibly more appropriate crowd...


texts: linear programming with non-integer constraints

texts:
Suppose we have a linear progamming about vertex packing of a hypergraph (V,E), with size $n = \sum_{e \in E} |e|$. We introduce a variable $x_v$ for each vertex $v \in V$. The fractional version is stated as follows:

$$\max \  \sum_{v \in V} x_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$s.t. \ \sum_{v: v \in e} x_v \le 1, \forall e \in E$$
$$ x_v \ge 0, \forall v \in V$$

We have anonther version of this LP with non-integer constraints as follows:

$$\max \sum_{v \in V} x_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$s.t. \ \sum_{v: v \in e} x_v \le 1, \forall e \in E$$
$$x_v \in \{0, \log_N 2, \log_N 3, \cdots,  1\}, \forall v \in V$$

Let the optimal solution for these two LPs as $OPT_1$ and $OPT_2$.

Is there any good upper bound for $N^{OPT_1}/N^{OPT_2}$ in terms of n and N?

Or: Assume $N = \Theta(n^n)$. Is it possible to bound $N^{OPT_1}/N^{OPT_2} \le c$ for some constant c?


texts: What is the major difference between PP and RP?

texts:
So according to complexity zoo, the definition of RP is:

The class of decision problems solvable by an NP machine such that
1.If the answer is 'yes,' at least 1/2 of computation paths accept.
2.If the answer is 'no,' all computation paths reject.

and the definition of PP is:

The class of decision problems solvable by an NP machine such that
1.If the answer is 'yes' then at least 1/2 of computation paths accept.
2.If the answer is 'no' then less than 1/2 of computation paths accept.

So the only difference is the behaviour of the machine when the answer is 'no'.
And in Papadimitriou for RP:

There is no easy way to tell whether a machine always
halts with a certified output. We informally call such classes semantic
classes

So isn't it also not possible to tell whether a PP machine will always halt with a certified output? Also, don't both PP and RP accept by majority?


texts: Complexity of minimising polynomial formula size

texts:
Let $f(x_1,\dots,x_n)$ be a degree $d$ polynomial in $n$ variables over $\mathbb{F}_2$, where $d$ is constant (say 2 or 3). I would like to find the smallest formula for $f$, where "formula" and "formula size" are defined in the obvious way (eg. the smallest formula for the polynomial $x_1 x_2 + x_1 x_3$ is $x_1(x_2+x_3)$).

What is the complexity of this problem - is it NP-hard? Does the complexity depend on $d$?

[ More formally, a formula (aka "arithmetic formula") is a rooted binary tree, each of whose leaves is labelled with either an input variable or the constant 1. All the other vertices of the tree are labelled with $+$ or $\times$. The size of the formula is the number of leaves used. The formula computes a polynomial recursively: $+$ vertices compute the sum of their children over $\mathbb{F}_2$, $\times$ vertices compute the product. ]


texts: What kind of reinforcement learning is MENACE?

texts:
The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description:

  ...an interesting machine for playing tic-tac-toe. It was made
  entirely out of matchboxes, each one of which had a tic tac toe
  position on the top. Inside was a collection of colored beads. Each
  color specified a possible legal move for the position on top. The
  idea was that you’d play a game by drawing these beads from the
  appropriate box, and making the appropriate move. At the end of the
  game, you’d remove the bead from the last box that sent you along the
  losing path. Eventually, all the losing moves get removed, and the
  machine plays perfect tic-tac-toe. Gardner showed how this same idea
  could be used to create a matchbox computer to play hexapawn, a simple
  game played with six pawns on a 3×3 board.

My question is: what kind of algorithm is this, in modern parlance? Is it policy iteration? Q-learning? Or sooething else? I am a bit new to the subject and can't figure it out for sure.


texts: Applications of Theoretical Computer Science in Information Theory

texts:
Inspired by this question:
Information Theory used to prove neat combinatorial statements?

Are there any nice applications of theoretical computer science in information theory (the other way has nice applications such as use of coding theory/Kolmogorov complexity in TCS)


texts: Confusion in 2012 paper by Austrin and Håstad regarding hardness of approximating GLST

texts:
The paper in question is "On the Usefulness of Predicates", Per Austrin, Johan Håstad (arXiv:1204.5662 [cs.CC]).

On page 13, Example 8.2 they define a predicate $P$ which is $GLST$ with an additional accepting predicate of all $1$'s. The claim is that this predicate can be shown approximation resistant with Theorem 8.3, which requires that $P$ accept all strings $x_1 x_2 x_3 x_4$ such that $\prod_1 ^3 x_i = -1$ and $x_3 = -x_4$.

In particular, $P$ should accept $(1,1,-1,1)$ but the definition of $GLST$ provided requires that $x_2 \ne x_4$.


texts: Variant of Toda's theorem for intermediate levels of the polynomial hierarchy

texts:
Is there a version of Toda's theorem for intermediate levels of the polynomial hierarchy ? More precisely, is there any variant of the Toda's theorem that states:

Let $\# wSAT$ be the number of satisfying assignments to a boolean formula, where $(\log_2 n)^w$ variables (out of $n$) are assigned to TRUE.

  $\bigcup_{i=1}^k \Sigma^P_k \subseteq P^{\# wSAT}$ ?

If something of this form is known, a reference would greatly help.


texts:
Data for the problem:

2D grid(lattice) of size NxN
n nodes placed on the grid:node_1,node_2,…node_n
Each of nodes contain some data:

a.   node_i is presented by 3 parameters (x_i,y_i,t_i)

b.       x_i and y_i represent the coordinates on the grid

c.       t_i represent the time when the node`s data  is ready
Given a node_(n+1) and t_(n+1)  I should find x_(n+1) and y_(n+1):
Such that, if  we define l_i  = (x_(n+1)-x_i) +( y_(n+1)-y_i) ,
For  every 1<=i<=n the will take place t_i + l_i <= t_(n+1)
If the above is impossible the max( t_(n+1) – (t_i + l_i)) should be minimized

For example please take a look for the following examples when n = 2

Node_1 :x_1 = 0,y_1 = 0,t_1 =1

Node_2 :x_2 = 4,y_2= 3,t_2 = 4

Node_2 :x_3 =?,y_3 = ?,t_3 = 6

-> x_3 = 3?,y_3= 2

Node_1 :x_1 = 0,y_1 = 0,t_1 =0

Node_2 :x_2 = 4,y_2= 4,t_2 = 0

Node_2 :x_3 =?,y_3 = ?,t_3 = 4

-> x_3 = 2?,y_3= 2

I need general algortithm for finding x_(n+1) and y_(n+1).Does anyone have some clue how to solve such a problem.
Thank you.


texts:
Does the MIP* = RE result algebrize?  (It doesn’t relativize, as noted here.)

If it doesn’t algebrize, is there a more complicated similar notion that it does satisfy?


texts: Divide-and-conquer approach for hierarchical clustering

texts:
I have a huge data set (33K), each represented as a bit-vector of 275-dimensions. Basically my data set can be represented as a $33000 \times 275$ matrix. I want to cluster these bit-vectors. I have tried single link hierarchical clustering on a small data set, $3000 \times 275$, and the result is promising.

I know that single link hierarchical clustering algorithm is not scalable as the time complexity is $O(n^2)$. I am planning to apply a divide-and-conquer approach, i.e., divide the dataset into chunks of equal size and cluster each chunks individually and finally merge the clustered chunks based on distance (if: $d(C_1,C_2)< t$; then: merge $C_1$ and $C_2$).

The time complexity for my new approach is $O(p) + O(pq)$, where $p$ is the number of chunks and $q$ the average number of clusters in each chunk. Note: I assume that when hierarchical clustering is applied, each chuck will take same amount of time and its constant for all chunks, thus $O(n^2)$ will become $O(1)$.

I want to know, whether the above mentioned clustering approach is feasible and efficient. Or is there any logic flaws in applying divide-and-conquer approach for clustering.


texts:
Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's.

What's so special about MOD_m gates?

They allow one to simulate arithmetic over any ring Z_m.
Before Ryan's result, throwing MOD_m gates to the mix gave the first class for which the known lower bounds did not work.

Is there any other natural reason to study MOD_m gates?


texts: Weighted graph as average of many unweighted graphs

texts:
I have a measure $L(G)$ that is only valid for unweighted graphs because is based on discrete distributions and can't be extended to weighted graphs.

My idea is that if I consider a weighted graph as the average of many unweighted graphs, in the sense that every weighted edge is the average over a set of edges and non-edges (1 or 0 weights), then I can express the weighted counter part of that measure as a weighted average of the measure on the set of all unweighted graphs.

For example, I can see every edge in the weighted graph as the average of the edge (present or not) in a set of $N$ unweighted graphs.
In this sense I can generate a set of $N$ unweighted graphs by a random procedure that produces graphs that have on average the same number of edges and exactly the same vertex set. Then the weighted measure will just be the weighted average of the measure on the set on unweighted graphs.

Is this option already known in some literature?


texts: I want to prepare a small presentation with some of the most important results in Counting complexity, continue with recent ones and finish with some interdisciplinary results ,probably with other complexity theory areas. I have some thoughts already. Any paper propositions that should definitively be in?


texts: Deciding functionality of transducers over infinite words

texts:
Given a finite state transducer defining a rational relation over infinite words, it is known to be decidable whether or not the relation is a function, i.e. whether each infinite input word is related to at most one infinite output word. This is detailed in a paper by Gire: Two Decidability Problems for Infinite Words. Unfortunately, I cannot find the full text of the paper anywhere. The basic idea seems to be to form the composition of the transducer with its inverse $T \circ T^{-1}$ and check if the resulting transducer is a restriction of the identity function. Note that the inverse of a transducer $T$ is $T$ with input and output word swapped for each transition.

I am looking for details of the decision procedure. Do you have any references or a short description of the algorithm?