texts:
In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment:

  I think we should distinguish between major open problems that are viewed as fundamental  problems, like $ P\neq NP $, and major open problems which will constitute a technical breakthrough, if solved, but are not necessarily as fundamental, e.g., exponential lower bounds on $ AC^0(6) $ circuits (i.e., $ AC^0+\mod 6 $ gates). So we should possibly open a new community wiki entitled "open problems in the frontiers of TCS", or the like.

Since Iddo did not start the thread, I thought I'll start this thread.

Often the main open problems of fields are known to researchers working in related fields, but the point at which current research is stuck is unknown to outsiders. The quoted example is a good one. As an outsider, it is clear that one of the biggest problems in circuit complexity is to show that NP requires super-polynomial size circuits. But outsiders may not be aware that the current point at which we are stuck is trying to prove exponential lower bounds for AC0 circuits with mod 6 gates. (Of course there could be other circuit complexity problems of similar difficulty which would describe where we are stuck. This is not unique.)
Another example is to show time-space lower bounds for SAT better than n1.801.

This thread is for examples like this. Since it is hard to characterize such problems, I'll just give some examples of properties that such problems possess:

Will often not be the big open problems of the field, but will be a big breakthrough if solved.
Usually not unbelievably hard, in the sense that if someone told you that the problem was solved yesterday, this would not be too hard to believe.
These problems will also often have numbers or constants that are not fundamental, but they arise because this happens to be where we are stuck.
The problem at the frontiers of a particular field will keep changing from time to time, as opposed to the biggest problem in the field, which will remain the same for many many years.
Often these problems are the easiest problems that are still open. For example we don't have exponential lower bounds for AC1 either, but since $AC^0$[6] is included in that class, it is formally easier to show lower bounds for $AC^0$[6], and thus that is at the current frontier of circuit complexity.

Please post one example per answer; standard big-list and CW conventions apply. If someone can explain what types of problems we're looking for better than I have, please feel free to edit this post and make appropriate changes.

EDIT: Kaveh suggested that answers also include an explanation as to why a given problem is at the frontier. For example, why are we looking for lower bounds against AC0[6] and not AC0[3]? The answer is that we do have lower bounds against AC0[3]. But then the obvious question is why do those methods fail for AC0[6]. It would be nice if answers could explain this too.


texts: Is it known whether SPACE(n) (the class of languages recognized by deterministic TMs with linear space) is a proper subset of E (the class of languages recognized by deterministic TMs in time 2^O(n))?


texts: Problem in BPP but not known to be in RP or co-RP

texts: Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?


texts:
In short my question is what are all known explicit constructions of asymptotically good codes over finite alphabet?

In more details: A sequence of codes codes $C_i: F^{k_i}\rightarrow F^{n_i}$ with distances $d_i$ is asymptotically good iff exists constants $R,\delta$ such that
 $\frac{k_i}{n_i}\geq R, \frac{d_i}{n_i}\geq \delta$.
My question is what are all known ways to construct such asymptotically good codes.
(Note the question is about finite alphabets)

I can give two examples:

1) Goppa AG codes: http://en.wikipedia.org/wiki/Goppa_code

2) Expander codes: http://en.wikipedia.org/wiki/Expander_code

3) Justesen codes:  http://en.wikipedia.org/wiki/Justesen_code

I would like to know an other examples of asymptotically good codes.


texts:
We know that $\mathsf{PP}$ is equal in power to $\#\mathsf{P}$ in the sense that $\mathsf{P^{PP}} = \mathsf{P}^{\#\mathsf{P}}$ (see the Complexity Zoo entry). The similar question about $\mathsf{\oplus P}$'s power is not known.

We can think of $\mathsf{PP}$ as giving the most significant bit of the number of solutions and $\mathsf{\oplus P}$ as giving the least significant bit. This question is about the underlying reason for their difference. Lets use $\#M$ to denote the number of solutions for $M$ on a given input $x$, i.e. $\#M = \{y : (x,y)\in M\}$.

For two given formulas $f$ and $g$, we can easily create formulas such that the number of their solutions will be $\#f+1$, $\#f + \#g$, $\#f \cdot \#g$, and $\#f \mod 2$. Is the problem about finding a formula which has $\#f \ / \ 2$ solutions?

If this is the case, has there been any work in this area? What is the state of the art?


texts:
I have been attempting to show that this problem is $NP$-complete but haven't been successful.  I wonder if anyone has a suggestion for a problem I could reduce to it.

$CALLS$: Suppose we have nodes $\{0, \ldots, n - 1\}$, with undirected edges between $(i \mod n, i + 1 \mod n)$ for all $i$.  Furthermore, suppose we have a set $C$ of calls, which are the form $(i \mod n, j \mod n)$, and an integer $K$.  The problem is to determine whether it is possible to schedule the set of calls (to schedule a call, one decides whether to go clockwise around the circle or counterclockwise) such that the maximum load (i.e. number of calls going through a given edge) is $\le K$.

I have been able to show that if we assign each call a weight the problem is $NP$-complete by reducing $PARTITION$ to it.  However, I haven't been able to reduce any $NP$-complete problem to unweighted $CALLS$.


texts: Intuition behind nested positivity and counterexamples

texts:
I'm looking at the nested positivity conditions for inductive types stated in the Coq manual. First off, are there any other references (not necessarily for Coq, but in dependent type theories generally) for the nested positivity conditions and how they come about? I've found older papers like Dybjer's Inductive Families and Coquand and Paulin's Inductively Defined Types, but I believe these only mention the strict positivity condition, and newer papers like the pCuIC one and A Comprehensible Guide to CIC don't mention nested positivity either.
Now, I'm trying to gain an intuitive understanding of why nested positivity is required. In essence, nested positivity states that when defining a constructor C for some inductive type $D$, if the type of an argument to $C$ is something like $I ~ \vec{p} ~ \vec{t}$, then $D$ can only appear strictly positively in $\vec{p}$, and only if $I \neq D$. I understand that allowing $D$ in negative positions of $\vec{p}$ basically allows for proofs of $(D \to \bot) \to \bot$, and allowing $D$ in other positive positions essentially allows for double negation elimination (and some inconsistency stuff with impredicative Prop). What I don't understand are these:

Why can't $D$ appear strictly positively in $\vec{p}$ if $I = D$ (either as constructor argument or return type)? For instance, for a constructor $C$ of an inductive type $D ~ (A: \textrm{Type}): \textrm{Type}$ (with $A$ as the sole parameter), why is $C: D ~ (D ~ A) \to D ~ A$ disallowed?
EDIT: Not only is this accepted in Agda 2.6.1.2, $C: D ~ (D ~ A \to \bot) \to D ~ A$ is also accepted, which seems suspicious to me.

Why can $D$ otherwise appear strictly positively in the parameters $\vec{p}$, but not in the indices $\vec{t}$? Consider for instance the (rather silly) constructor $C: (D =_{\textrm{Type}} D) \to D$ for the inductive type $D: \textrm{Type}$, where $=$ is the usual equality type.
EDIT: It turns out this doesn't type check in Agda for unrelated universe level reasons, so consider instead the following which Agda rejects for positivity reasons:
data Box : (A : Set) → Set where
  box : (A : Set) → Box A

data D : Set where
  C : Box D → D

This is accepted by Agda if A is instead a parameter, as expected from the nested positivity rules.

I'm particularly interested in finding examples where violating nested positivity conditions (specifically these two I've listed) causes inconsistencies and proofs of $\bot$, which personally would be easier to understand than arguments about monotonicity.


texts:
One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper Determinant Versus Permanent and in one paragraph he claims the reverse problem is easy.

  It is easy to see that the determinant of a matrix $X$ can be expressed as the permanent of a related matrix $Xˆ$ whose entries are 0, 1, or $x_{i,j}$ s and which is of size $O(n)$ (set up entries of Xˆ such that det $Xˆ$ = det $X$ and the product corresponding to every permutation that has an even cycle is zero).

First of all, I don't think 0, 1, and $x_{i,j}$ variables are enough because we would be missing negative terms. But even if we allowed -1 and $-x_{i,j}$ variables as well, I don't see why the growth in size can be made linear. Could someone please explain the construction to me?


texts: A decision problem which is not known to be in PH but will be in P if P=NP

texts:
Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, the answer to this question turned out to be “yes” in a way which I had not expected at all.  First I thought that they did not answer the question I had wanted to ask, but after some thinking, these constructions answer at least one of the questions I wanted to ask, that is, “Is there any way to prove a conditional result ‘P=NP ⇒ L∈P’ without proving the unconditional result L∈PH?”  Thanks, Ravi and Scott!

Is there a decision problem L such that the following conditions are both satisfied?

L is not known to be in the polynomial hierarchy.
It is known that P=NP will imply L∈P.

An artificial example is as good as a natural one.  Also, although I use the letter “L,” it can be a promise problem instead of a language if it helps.

Background.  If we know that a decision problem L is in the polynomial hierarchy, then we know that “P=NP ⇒ L∈P.”  The intent of the question is to ask whether the converse holds.  If a language L satisfying the above two conditions exists, then it can be thought of as an evidence that the converse fails.

The question has been motivated by Joe Fitzsimons’s interesting comment to my answer to Walter Bishop’s question “Consequences of #P = FP.”


texts: Why did Caml become OCaml? (or, why use objects in F#?)

texts:
I have been programming in F# for a decade and in that time I have found that when I am working within the purely functional aspects, ie. the ML lambdas, tuples, generics, etc, that everything is beautiful and consistent, and development proceeds at an order of magnitude faster than in, say, C# or Java.

However, as soon as I start using objects, with class hierarchies, constructors, polymorphism, etc, I find that I am repeatedly stopping to think about how to do things in the language, and that, overall, the development and thought process is about the same as in C#. There are some advantages to using F#, but not as significant as with functional programming.

So, the only reason I have used objects in F# is when I am forced to, namely to work within a pre-existing object oriented "framework". I have done this with ASP.NET MVC, Windows Store Apps (Win 8.1), and Android. (And, quite successfully after some initial pain).

My questions are:

Did Caml become OCaml primarily to be able to interface with
imperative OO languages, rather than because OO really improved the
language?
Could I advise budding F# programmers to avoid the OO features until
they need to interface with or extend an OO framework?

As an aside, I mention that in my early days with F# I posted a question in an F# forum asking whether I should prefer the functional or OO style of programming, and the answer was emphatic:"Prefer the functional!". Since then, I've come to ask why use the OO at all?


texts:
I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of edges in a single move and Runaway can move from a current vertex to an adjacent vertex (cutting an edge means that corresponding vertices became not adjacent). Runaway starts at vertex $s$ and wants to make it into vertex $t \neq s$; Police wants to interfere her. Police move first.

Let the game cost for Police be equal to the number of cutted edges. An $s-t$ minimal cut size is an obvious upper bound for this value, but sometimes Police can do better. For example, consider a $K_{n,2}$ graph ($n > 2$) where $s$ and $t$ both belong to the smaller (second) part. Minimal cut between $s$ and $t$ equals $n$, though cutting only 2 edges is enough (Police cuts empty set on her first move hence forcing Runaway to move away from $s$, then she cuts 2 edges adjacent to Runaway's location). Efficient computation of that cost seems to be an interesting problem.

I came up with a clumsy (still polynomial-time) algorithm which basically does loads of min-cut computations on $G$ subgraphs for this (however I'm not completely sure in the correctness). I wonder if it is a known problem or not, maybe there is some elegant solution? Please provide any related info.


texts: Finding appropriate spanning tree of connected bipartite graph

texts:
I got this as a sub-problem while working on a research problem connected to index coding. Can someone please give me directions as to how to approach this problem?

Problem: We have a connected undirected bipartite graph $G=(U,V,E)$. Let $|U| = m$ and the degree of $i$th node in U be $a_i$. Consider a spanning tree of $G$ and let the degree of $i$th node in $U$ be $b_i$ in the spanning tree (so $b_i \le a_i$). I am interested in finding the spanning tree that minimizes $max_{i=1,2,...,m} (a_i-b_i)$. I am interested in getting directions about how to design an algorithm for it.


texts: Is the Fermat-Weber problem $\mathsf{NP}$-hard?

texts:
Given a set of $n$ points in a Euclidean space, the Fermat-Weber problem asks to find a center that minimizes the sum of distances of points to that center.
There are iterative algorithms known for this problem like Weiszfeld's algorithm and BMM algorithm, but they only find an approximate solution for the problem.
Moreover, no closed form expression is known for this problem yet. Moreover, Chandrajit Bajaj (link) proved that there is no exact algorithm for the problem under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction of kth roots.
I couldn't properly understand this model of computation. However, I want to ask a fairly straightforward question: "Is Fermat-Weber problem $\mathsf{NP}$-hard?" or "showing its $\mathsf{NP}$-hardness is still an open problem?". To prove $\mathsf{NP}$-hardness, it is required to show a reduction from an $\mathsf{NP}$-complete problem to this problem. But I could not find any such reduction in the literature. Please help.

Note: The question has been asked before on MathOverflow(link). But it does not contain any correct answer even in the comments.


texts: Multi-armed bandit problems where more than one arm can be selected?

texts: I want to know if there are any references in the literature on  multi-armed bandit problem where in one round, you can select $k > 1$ arms.


texts: What is the Complexity Classification of Portfolio Theory in Financial Economics?

texts:
As you will all know, there is ongoing fall out from the Financial Crisis of 2008. I was thinking about how complexity theory fitted into all this, when I realised I did not know the basic complexity classes relating to Financial Economics.

So my question is what is the complexity classification (if any) of Markowitz's Portfolio Theory in general and the CAPM model in particular? Also, any comments relating to how complexity theory relates to the Financial Crisis would be welcome!


texts: k-uniform k-partite hypergraph matching in polynomial time

texts:
I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers users here may provide. Please note that I have also asked this question on Mathoverflow.

It is well known that for $k\geq 3$ finding the matching number of a $k$-uniform $k$-partite hypergraph is NP hard in general. Are there subclasses of these hypergraphs for which the problem is solvable in polynomial time?


texts: What are the most recent developments in small-depth quantum circuits?

texts:
Back in 2005, Scott Aaronson posted a list of 10 "semi-grand" challenges for quantum computing theory which contained the following challenge:

  The power of small-depth quantum circuits. Is $BQP = BPP^{BQNC}$? In other words, can the "quantum" part of any quantum algorithm be compressed to polylog(n) depth, provided we're willing to do polynomial-time classical postprocessing? (This is known to be true for Shor's algorithm.) If so, building a general-purpose quantum computer would be much easier than is generally believed! Incidentally, it's not hard to give an oracle separation between $BQP$ and $BPP^{BQNC}$, but the question is whether there's any concrete function "instantiating" such an oracle.

I am currently searching for  a Ph.D. project and this is the kind of stuff that interests me. I would certainly like to contribute to solving this problem, if it is still open. That is why I would like to know some of the recent developments on this. Is this still an open problem? What contributions were made in the last decade?


texts: BQNC and Abelian Hidden Subgroup Problem

texts:
We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous.

Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$?
In particular is Discrete Logarithm in $BQNC$ or at least in $BPP^{BQNC}$ and is there any reference which explicitly relates Discrete Logarithm and $BQNC$?

If not what is it that makes integer factorization special?


texts: Can Isorecursive types capture mutually recursive data types?

texts:
I've been reading TAPL, and reached the section on recursive types. I understand the type operator $\mu$. For example, the two type expressions are equivalent

NatList = {nil: Unit, cons: (Nat, NatList)}

and
$$ \mu X. 1 + \text{Nat} \times X $$

I'm confused how I would, using the $\mu$ operator, describe mutually recursive types such as

Forest = List<Tree>
Tree = (Value, Forest)

Obviously the type above can be reduced to a single type

Tree = (Value, List<Tree>)

But is there any way to write this using type-theoretic notation? Specifically I am wondering how the isorecursive operations fold and unfold operate on mutually recursive types, since I feel like unfold would have to expand both the definition of Tree and of Forest.


texts:
Consider the classic Knapsack optimization problem (KP):

Given $p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$, compute a solution $I\subseteq \{1,\dots,n\}$, such that $\sum_{i\in I} w_i \leq B$ and $\sum_{i\in I}p_i$ is maximum.

The textbook proof of NP-hardness reduces from the subset-sum problem and results in special KP instances that have $w_i=p_i$.

Question: Are there other (i.e., not containing the above) NP-hard instance classes of the KP known? Especially instances where more than one $\frac{p_i}{w_i}$ ratio can be present?


texts:
We know $\oplus P^{\oplus P}=\oplus P$, $PP^{\oplus P}\subseteq P^{PP}$ and $NP\subseteq PP$.

Is $\oplus P^{PP}=PP$?
Why is it difficult to show $NP^{NP}\subseteq PP$?
What is the smallest known class $\mathcal C$ such that $PP\subseteq \oplus P^\mathcal C$ holds? Is there any class smaller than $PP$?


texts: Shortest formula for an n-term monotone CNF

texts:
A monotone CNF formula with m terms on n variables ($x_1,\ldots,x_n$) is a formula of the form $f(x_1,\ldots,x_n) = \bigwedge C_i$, where each $C_i$ is an OR of some subset of the variables $x_1,\ldots,x_n$, and $i$ ranges from $1$ to $m$.

For example, $(x_1 \vee x_3 \vee x_4) \wedge (x_2 \vee x_4)$ is a monotone CNF formula with 2 terms on 4 variables.

I'm looking for the shortest formula (not necessarily monotone, not necessarily CNF, any formula will do!) on the same set of variables that represents the same function as a given monotone CNF formula on n variables with n terms. (Note that the number of terms and variables is the same.)

One obvious way to construct a formula is to expand out the given CNF definition, which will give us a formula of size $O(n^2)$. (Let's define the size of a formula to be the length of the formula when it is written down as a string.) I want to know if this is the most efficient general construction or if for every n-term monotone CNF there exists a formula of size $o(n^2)$.

I just want to know whether this is possible, I'm not really interested in an algorithm. If this is not possible, a function that serves as a counterexample would be great. Pointers to where I can find an answer in the literature are also appreciated.

EDIT: I'm adding an example to make thins clearer.

Say the input formula is $f = (x_1 \vee x_2) \wedge (x_1 \vee x_3) \wedge \ldots \wedge (x_1 \vee x_n)$. This is a monotone CNF formula. A shorter formula which represents the same function is the following: $x_1 \vee (x_2 \wedge x_3 \wedge \ldots \wedge x_n)$.


texts: Is there a standard definition of resolution for arbitrary clauses?

texts:
Knuth defines in [1] a resolution operator for arbitrary clauses which sets $C = C' \diamond C'' = (C' \lor C'')$ when there is no literal $x$ such that $x \in C'$ and $\neg x \in C''$. I skimmed over [2], [3] and [4] and could not find any references to this particular style.
Why is this definition sensible for general clauses? How is it different from, say, defining $C = C' \diamond C'' = \top$, a tautology, in such case?

[1] Knuth, TAOCP, Volume 4 Fascicle 6, Satisfiability
[2] https://en.wikipedia.org/wiki/Resolution_(logic)
[3] Buss, Samuel R. (ed.), Handbook of proof theory, Studies in Logic and the Foundations of Mathematics. 137. Amsterdam: Elsevier. 811 p. (1998). ZBL0898.03001.
[4] Krajíček, Jan, Proof complexity,  ZBL07044161.


texts: What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?

texts: The complexity class BQP corresponds to polynomial time quantum subroutines taking in classical inputs and spitting out a probabilistic classical output. Quantum advice modifies that to include copies of some predetermined quantum advice states but with classical inputs as usual. What is the complexity class for polynomial time quantum subroutines taking in arbitrary quantum states as inputs, with one copy only due to no cloning, and spitting out quantum states as an output?


texts:
The below-given problem is in black box setting means input is given by set of generators.

Given an abelian $p$-group $A$ and two matrices $U_1$ and $U_2$ in $R(A)$ such that the order of $U_1$ and $U_2$ are coprime with $p$, output an element $U \in R(A)$ such that $UU_1=U_2U$ if such an element exists.

$R(A)$ denotes the set of all automorphisms of $A$.

The brute force way seems to give a $\Theta(|A|^{\log |A|})$ bound.

Question: Is the above problem solvable in the polynomial time?


texts: How high are the higher types that appear in practice?

texts:
This is admittedly a rather naively put and vague question, and I'm not sure how much more specific I want or can make it, but I'll try.

By "practice" I mean surely in actual programming practice (of which I embarrassingly don't know much), but also in mathematical practice, whenever certain higher-type objects are employed as examples or counterexamples within arguments.

By the "height" of a type, I don't mean to include the obvious and natural arbitrariness involved in objects like, say, the fixpoint functional (in fact, in the spirit of the question, I would prefer to understand this as a type $2$ object "up to parameter types", so to speak). A better example of what I mean would be the well-known (from mathematical practice, at least) fan functional, of type $((\mathbb{N} \to \mathbb{B}) \to \mathbb{N}) \to \mathbb{N}$, given by
$$
\lambda f. \mu m. \forall_{\alpha, \beta}
\left(
\forall_{n < m} \alpha(n) = \beta(n) \to f(\alpha) = f(\beta)
\right) \ ,
$$
where $f : (\mathbb{N} \to \mathbb{B}) \to \mathbb{N}$ and $\alpha, \beta : \mathbb{N} \to \mathbb{B}$.

My questions: Are there any objects of yet higher type than $3$ (possibly "up to parameter types") that are naturally used in the literature? In practice?


texts: Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

texts:
Peter Shor commented on this post:

years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar.

What can we say about the distribution/thermodynamics of $A$ w.r.t. $B$ if we know that $A \le_M B$ (there is a reduction from $B$ to $A$), or if we know that $A, B \in C$ where $C$ is some complexity class ($P$, $NP$, co-$NP$, etc.)?

What can we say on the thermodynamics if there isn't a reduction from $A$ to $B$, or given their complexity classes?

I am not sure if it is a wicked idea to use complexity theory whose main concern is the worst-case scenarios while discussing thermodynamics, or statistical physics, whose general aim is to characterize phase transitions and describe the average case (principle of maximum entropy). Here is somehow a related work that states "NP problems" in terms of an Ising model.


texts: Resources (books, etc) to learn about concurrency theory

texts:
I want to know more about concurrency theory from a formal/mathematical point of view, I know there are a lot of computer science branches that relates to concurrency theory like process algebra, Petri nets, Actor model, CSP, etc.

But I don't know about classic books on that topics, and also I would like to know in which order it's better to study, I'm new to this field, I have some basic knowledge on λ-calculus and Turing machines theory.

What resources do you recommend to begin with this theory?


texts: Are there non-trivial MIP protocols with initially-independent verifiers?

texts:
My impression is that for standard constructions of MIP ("Multiple Independent Prover") protocols, the verifiers must have shared randomness.  What happens if the verifiers are

also independent until the interactions have all finished?  (i.e., Each independent

prover interacts with a different independent verifier and then the transcripts

of the interactions get sent to the final verifier, which either accepts or rejects.)

More Formally:  What is known about the power of MIP protocols in which,

for each prover, the computation of what (if anything) the verifier sends

does not use anything about the partial transcripts for the other provers
and
the randomness strings used for the verifier's interactions

with different provers are independent of each other

?
By this paper, the public coin minimal-interaction version of that collapses to AM.


texts: How difficult is it to work on mathematics problems as a computer science graduate student?

texts:
I am interested in problems typically tackled in theoretical computer science departments as well as seperate problems found in mathematics departments. Both would be more proof based. Is it easy to move from one to the other?

Example: Say I would like to work on proofs under the theory of computation (on the CS side) as well as geometric and topological proofs coming from problems in particle theory (maybe more on the mathematical physics side). Should I be in TCS or a math department, or would I be free enough to move around? Might I have more room to move in a mathematics department versus a TCS department?


texts: Communication complexity of Independent Set game?

texts:
Consider the following communication game.

Independent Set game

Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$.
Alice receives a set $X$ of edges, each edge being a pair of distinct vertices from $[n]$, and Bob receives a set $Y$ of edges.
Alice and Bob must communicate to determine whether the graph $([n],X \cup Y)$ contains an independent set with $r$ vertices.
Let IS$_{n,r}(X,Y) = 1$ if there is such a set, and IS$_{n,r}(X,Y) = 0$ otherwise.

There is a simple nondeterministic protocol to confirm that IS$_{n,r}(X,Y) = 1$; Alice nondeterministically chooses an $r$-vertex set $I$ that forms an independent set in her graph $([n],X)$ and sends Bob a description of this set using at most $r(1+\log n)$ bits.
Bob responds with 1 if $I$ is an independent set in $([n],Y)$ also; otherwise he responds with 0.
On the other hand, there is a fooling set of pairs of sets $(V,V)$ such that $([n],V)$ is a graph formed by $r$ disconnected vertices adjoined to a complete graph with $n-r$ vertices.
This 1-fooling set contains $\binom{n}{r}$ such fooling pairs, so the nondeterministic communication complexity of $\text{IS}_{n,r}$ is at least $\Omega(r\log n)$.
It follows that the simple protocol is optimal up to a small constant factor.

My question is:

  Is there a large 0-fooling set for IS$_{n,r}$?

If not, is there an efficient deterministic protocol?

I would also be interested in pointers to the literature if this problem is known.
The closest I have found is the Clique vs. Independent Set game of Yannakakis but this did not seem useful here.


texts: Can we prove weak normalization for System F by induction on a transfinite ordinal

texts:
Weak normalization for the simple typed lambda calculus can be proved (Turing) by induction on $\omega^2$. An extended lambda calculus with recursors on natural numbers (Gentzen) has a weak normalization strategy by induction on $\epsilon_0$.

What about System F (or weaker)? Is there a weak normalization proof in this style? If not, can it be done at all?


texts:
It is said that "All finite languages are regular".

But the Pumping Lemma says that,

if a language is regular
one can find a 'large-enough' word w such that it can be decomposed into w = xyz such that FOR ALL i >= 0 the word with a pumped up y^i is also in the language.

But doesn't that state that "every regular language is infinite" since one can always infinitely (i in N) pump the word up and it will be still in the language?

So why are the finite languages regular and how are they fulfill the pumping lemma?


texts:
In an earlier question I proposed a definition of associativity for ternary relations generalizing the usual notion for composition laws. I'm still not sure whether this definition makes sense, but if so this leads to some interesting algebraic questions. In particular, what parts of "semigroup theory" can be extended to that setting, if any?

Consider such a relation $\cal{R}$ over $X$. Similar to semigroup theory, we can give the following definitions:

a set $S \subseteq X$ is a "substructure" if $a,b \in S$ and $\cal{R}(a,b,c)$ holds imply that $c \in S$;
a set $L \subseteq X$ is a "left ideal" if $a \in L, b \in X$ and $\cal{R}(a,b,c)$ holds imply that $c \in L$;
a set $R \subseteq X$ is a "right ideal" if $a \in X, b \in R$ and $\cal{R}(a,b,c)$ holds imply that $c \in R$;
given a substructure $S$, we can define an order relation $\leq_S$ such that for any $a,a' \in X$, $a \leq_S a'$ iff for every $b \in S,c \in X$, $\cal{R}(a,b,c)$ implies $\cal{R}(a',b,c)$. We can also define an equivalence relation $\equiv_S$ as $\leq_S \cap \geq_S$.

This leads to some natural questions: (i) what are the conditions on $S$ such that $\cal{R} / \equiv_S$ behaves as a substructure? (ii) how do chains of ideals behave with respect to inclusion? (iii) are there some possible generalizations of the isomorphism theorems? (iv) are there some connections with automata and possible extensions of Krohn-Rhodes theory?

This is probably pie in the sky though, as I don't even have any concrete example of such a structure...


texts:
Let us have a "shuffle algorithm":

for i in range(len(vec)):
     swap(vec[i], vec[rand()%len(vec)])

Why the reshuffles we get using this algoritm for a number of times turn out to be biased (unequal)?


texts:
Consider a digraph $G=(V,A)$ with each arc weighted by either $+1$ or $-1$. A path is called a zero-sum path, if and only if all the arcs in its first half have weight $+1$, and all the arcs in the second half have weight $-1$.

Example: The path $p= +1,+1,+1,-1,-1,-1$ is a zero sum path. However, neither the path $p=+1,-1,+1,+1,-1,-1$ nor the path $p=-1,+1,+1,+1,-1,-1$ is a zero-sum path.

The problem is to preprocess the graph, such that one can answer the following query in constant time: "Is there a zero-sum path between two given nodes $u$ and $v$?"

Given a digraph with $n$ nodes and $m$ edges, the problem could be solved by a Floyd-Warshall-style algorithm in $O(mn)$ time. My question is, whether there exists any better algorithm for solving this problem? Are there any references related to this problem?


texts: What arithmetical theorems can plain $\lambda \Pi$ reason about?

texts:
I've read that System F cannot state or prove theorems of the First Order Theory of Arithmetic. I assume this is because we lack dependent types, so we cannot explicitly express $\forall n:\mathbb{N}.P(n)$ as an inhabitable type. Thus, $\lambda\Pi$/LF seems promising despite its lacking expressivity of functions.

My question concerns whether it is even possible to encode proofs of arithmetic in $\lambda\Pi$. I am assuming there would need to be some sense of equality, perhaps a type only inhabited when two terms are $\beta\eta$-equivalent. Some sense of induction seems necessary also. I'm not convinced that such things wouldn't require additional inference rules to the theory.

At a minimum, I'm interested in being able to encode statements like "$\forall x \forall y. x + y = y + x$", or "$\forall x\exists y.x<y\land\textrm{prime}(y)$", and I don't know if these can even be encoded as types.

Can theorems of arithmetic be encoded and proved in plain $\lambda\Pi$? If not, what's required?


texts:
General Question

  Does the space hierarchy theorem generalize to non-uniform
  computation?

Here are a few more specific questions:

Is $L/poly \subsetneq PSPACE/poly$?
For all space constructible functions $f(n)$, is $DSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly$?
For what functions $h(n)$ is it known that: for all space constructible $f(n)$, $DSPACE(o(f(n)))/h(n) \subsetneq DSPACE(f(n))/h(n)$?


texts: Graph isomorphism problem with invertible adjacency matrices

texts:
This question is supplementary to the question asked here.

One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows.

  Given a permutation $\pi$ of a finite set $V$, form its cycle graph
  $G$ as follows: the vertex set is $V$ and the edges are pairs $(v,w)$
  for which $\pi(v)=w$. (This is a simple directed graph.) The adjacency
  matrix will in fact be the permutation matrix corresponding to $\pi$,
  which is invertible.

Let's consider a class of graph isomorphism problems where it is promised that both of the input graphs will be from the class defined above.

Can the graph isomorphism problems from this class be solved efficiently?


texts: When does randomization stops helping within PSPACE

texts:
It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE.

It is famously unknown whether P=BPP, but it is known that $BPP\subseteq \Sigma_2\cap \Pi_2$.

Thus, it is possible (while conjectured to be false) that adding probability to P adds expressive power.

My question is whether we know (or have evidence of) the border between P and PSPACE where adding randomization no longer adds power.

Specifically,

  Are there any problems that are known to be in $BP\Sigma_i$ (resp. $BP\Pi_i$) that are not known to be in $\Sigma_i$ (resp. $\Pi_i$)? And similarly for $BPPH$ v.s. $PH$?


texts: Research problems in communication complexity

texts:
There have been many open challenges questions in this forum.

For instance,

Research and open challenges in Programming Language Theory
What are current open problems in compiler theory?
Outstanding conjectures and open problems in (algorithmic) game theory?
Open problems on the frontiers of TCS
Open problems related to Graph isomorphism

What are some of research avenues, areas available within communication complexity? What are some of most interesting open problems?

Some famous open problems AFAIK are status of log-rank conjecture, status of $\mathsf{IP}^{}\notin\mathsf{PH}^{cc}$, status of examples of natural problems in $\mathsf{NP}_k^{cc}$,$\mathsf{coNP}_k^{cc}$.

What are some of lesser known open problems or areas that are not yet mature within communication complexity or areas that have made new progress but much more needs to be done?

Are there any problems relating other areas such as circuit complexity, machine learning etc?

AFAIK communication complexity is more about finding bounds that about algorithms. Are there any problems with number theoretic, algebraic, geometric flavor or more generally in an algorithmic flavor?

More generally what would be some areas a newly entered person should focus energy to select a problem to work on (comm complexity field does not have many hearsay research topics as other traditional areas in mainstream theory CS with direct real world applications)?


texts: What is the problem in "closest pair problem" if all points share the same x-coordinate

texts:
The closest pair of points problem deals with the task to find a pair of points with the global minimum distance. There is a problem, when all points share the same x-coordinate, or at least a large number of points.

I just don't know why, I heard the running time becomes $n^2$

What about it? What is the problem, since the proof for the algorithm shows, that at max. 8 points can reside in the $2 \delta \times \delta$ area.


texts: Does BQP contain any NP-Complete problem?

texts:
From the Wikipedia documentation, "the suspected relationship of BQP to other problem spaces" diagram suggests no intersection between NP-complete problems and BQP.

Has this been demonstrated or not?


texts: second order regularisation on a neurofuzzy network with Bernstein basis functions

texts:
We're trying to build a neural network that uses a neurofuzzy approach. Our reference is the book Adaptive Modelling, Estimation and Fusion from Data: A Neurofuzzy Approach by Chris Harris, Xia Hong, and Qiang Gan.

We're trying to compute the second order regularisation, which becomes a problem of finding a matrix K, which is related to the prior, is maybe called the smoother matrix, and "represents the square of the sum of the curvature evaluated at the centre of the basis functions". The Hessian is equal to

    H = beta*A(transpose)*A + alpha*K

where A is a matrix from the basis functions and K is the matrix we're having trouble with. alpha/beta is the regularisation coefficient.

All the resources I've come across suggest that K can be computed from the centres of the basis functions, except our basis functions are Bernstein polynomials, which are not radial basis functions.

Does anyone have any insight into how to compute K? Does anyone know of any examples of computing K when the basis functions aren't radial?

Thank you so much


texts:
I'm looking for a term-frequency analysis structure which is more efficient than a hash table in terms of worst-case performance and speed in practice. I specifically care about the operations insert and delete.

Some alternatives might be

VList
Radix tree
beap
soft heap
2-3 heap
Brodal queue
Binary heap
Threaded binary trees
Ctries

  Is there research using other data structures for the problem of gathering term-frequency statistics from a large corpus?


texts:
I have a recursive algorithm in which the time for each step depends on the time for smaller steps. Essentially a structure is built at steps 1, 2, ..., n which must be searched at larger heights:

$$
T(n)=T(n-1)+(1+o(1))\log(T(n-1))
$$

(yes, the larger the time searching the more data is added to the structure!)

It seems 'obvious' that $T(n)\approx n\log n,$ but can this be proved? In particular:
$$
T(n)\stackrel{?}{=}n\log n+o(n\log n)
$$

Better bounds on the error term would be great. I believe the error is $\omega(n).$


texts: How to mechanically derive the recursor of a type from its constructors?

texts:
In Martin-Löf Dependent Type Theory a type is commonly prescribed by how to construct its canonical terms and how to show that its canonical terms are definitionally equal. This means that the definition of a type contains no explicit information at all about its recursor / induction principle and how it should behave.

Am I right to suppose that, given the constructors of a type,
we already have an implicit characterization of its recursor / induction principle – in the sense that there exists an algorithm that mechanically derives the recursor / induction principle of this type?

If this is correct I would like to know:

How such an algorithm look like? (References are fine)
How is this all related to Gentzen’s inversion principles?


texts: Switching lemma for polynomials over $\mathbb{F}_2$

texts:
Suppose $f$ is in $\mathbb{F}_2[x_1,...,x_n]$ with total degree $d$.

  Q. Is there any kind of switching lemma or restriction lemma in which by applying the lemma on $f$ we can reduce the total degree of $f$ in a good way?


texts: Existence of long induced paths in expander graphs

texts:
Let's say that a graph family $\mathcal{F}$ has long induced paths if there is a constant $\epsilon > 0$ such that every graph $G$ in $\mathcal{F}$ contains an induced path on $|V(G)|^{\epsilon}$ vertices. I am interested in properties of graph families that ensure the existence of long induced paths. In particular, I am currently wondering whether constant-degree expanders have long induced paths. Here is what I know.

Random graphs with constant average degree (in the Erdős–Rényi model) have long (even linear-size) induced paths with high probability; see for example Suen's article.
Unique-neighbor expander graphs (as defined by Alon and Copalbo) have large induced trees. In fact, any maximal induced tree is large in such graphs.

Given these two facts I would expect that contant-degree expanders have long induced paths. However, I was unable to find any concrete results. Any insights are much appreciated.


texts: Famous computer science results which correctness is uncertain?

texts:
I am asking the following: which of the 'famous' computer science results have been thoroughly checked, and for which ones is the correctness still uncertain?

I understand that some proofs are hard to check due to their length, intricacy or technicality, and in some cases an elementary proof was found after the first published one (such as Dinur's proof of the PCP theorem). Apparently, some of the longest proofs in CS are the SPGT by Chudnovsky et al., and the Graph Minors series of papers by Robertson-Seymour, and I understand that there is an ongoing effort to simplify the latter.

The same question applies to mathematics where there are some very long proofs, such as the CFSG, which correctness is debated by experts: see List of long proofs.


texts: Oracles for sub-exponential circuit complexity of $\Sigma_2 EXP$

texts:
Couldn't find this one anywhere...

It's an open problem whether $\Sigma_2 EXP$ problems have exponential-size circuit complexity. Is there an oracle relative to which $\Sigma_2 EXP$ has $2^{o(n)}$ size circuits? $2^{n^{o(1)}}$ size?

Such an oracle exists for the class$MAEXP$; this was shown by Buhrman, Fortnow, and Thierauf.


texts: What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

texts:
In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the problem of checking whether AB = C has a randomized $O(n^2)$ time algorithm.

This is interesting because the fastest known algorithm for multiplying matrices is slower than this, so checking if AB = C is faster than computing C.

I want to know what is the most general algebraic structure over which matrix product verification still has an $O(n^2)$ time (randomized) algorithm. Since the original algorithm works over all fields, I guess it works over all integral domains too.

The best answer I could find to this question was in Subcubic Equivalences Between Path, Matrix, and Triangle Problems, where they say "matrix product verification over rings can be done in $O(n^2)$ randomized time [BK95]." ([BK95]: M. Blum and S. Kannan.  Designing programs that check their work. J. ACM, 42(1):269–291, 1995.)

First, are rings the most general structure on which this problem has an $O(n^2)$ randomized algorithm? Second, I couldn't see how the results of [BK95] show an $O(n^2)$ time algorithm over all rings. Can someone explain how that works?


texts: Maximum cliques of the transitive closure of a chordal DAG

texts:
Let $G=(V,A)$ be a directed acyclic graph, for which the underlying
undirected graph is chordal (so that every induced cycle in the
underlying undirected graph is a triangle).
It is known that in a chordal graph the number of maximum cliques
is linearly bounded in the number $|V|$ of vertices.
Let $G'=(V,A')$ be the transitive closure of $G$, so that for
every directed path $p= (v_i,\ldots,v_j)$ from $v_i$ to $v_j$
in $G$, there exists a directed edge $(v_i,v_j)$ in $A'$.

Question: Is there any polynomial/linear bound on the number
of maximum cliques in the undirected graph that underlies $G'$?


texts: So the two-dimensional reversible cellular automaton Critters (which you can simulate online at https://dmishin.github.io/js-revca/index.html#) on the Torus does not seem to follow the second law of thermodynamics. For example, if a $10\times 10$ block in the torus is filled with random data and the cells outside of this $10\times 10$ block are all zero, then there is a good chance that after several million generations on a $256\times 256$ grid, one can see the cellular automaton return to its original state. Why is the Poincare recurrence time for the reversible cellular automata Critters so small in this case? The rule Critters is universal for reversible computation, and it exhibits chaotic behavior that one would expect in a reversible cellular automaton. Therefore, one would expect that after running the cellular automaton for enough generations, the entropy would constantly increase and hence one would need to wait a very long time (much longer than several million generations) to observe the Poincare recurrence. Is there any explanation for this phenomenon? Are there other chaotic, reversible, universal cellular automata of dimension 2 that exhibit this phenomenon?


texts: Proof for Kolmogorov complexity is uncomputable using reductions

texts: I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, but there should be a proof by reducing from something like the Halting Problem, or Post's Correspondence Problem.


texts: Would derandomizing the reduction from SAT to Unique SAT imply $NP$ and $coNP$ are in $\oplus P$?

texts:
The Unambiguous SAT problem (USAT) is to determine whether a
given formula has a satisfying assignment, when we are
guaranteed that it has at most one satisfying assignment.

By a theorem Valiant-Vazirani there is probabilistic
reduction from 3SAT to USAT. Given 3SAT formula $\phi$,
over $n$ variables, the algorithm produces $n+2$ formulas
$\phi_i$ with the properties:  if $\phi$ is UNSAT, all $\phi_i$
are UNSAT. Otherwise the probability that $\phi_i$ has exactly
one solution is $\ge \frac18$.

$\oplus P$ is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd.

Since USAT has zero or one solution, $\oplus P$ solves USAT.

  Would derandomizing the reduction SAT to USAT imply $NP$ and $coNP$ are in  $\oplus P$?

This looks plausible to me, though Wikipedia claims
"there is a relativized universe (see oracle machine) where P = ⊕P ≠ NP = PP = EXPTIME" and $P^{\oplus P}$ is not known to even contain $NP$.

Even it can't be derandomized the reduction to USAT appears
very good in practice given $\oplus P$ oracle.


texts: Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

texts:
Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?

I know it is NP-complete for the class of planar graphs of maximum degree 3 (see the Garey and Johnson book), as well as for bipartite graphs of maximum degree 3 (see M. Chlebík and J. Chlebíková, "Approximation hardness of dominating set problems in bounded degree graphs"), but could not find the combination of the two in the literature.


texts: Nondeterministic communication complexity of set disjointness?

texts:
In the two-party setting, bounds of $\Theta(n)$ bits are known for deterministic and bounded-error randomized protocols for $\text{DISJ}_n$.
(Here $\text{DISJ}_n$ is the $n$-element set disjointness function; the parties are each given $n$-bit Boolean vectors $x$ and $y$, and have to decide whether there is some index $i$ so that $x_i = y_i = 1$.)

In contrast, for nondeterministic protocols in the two-party setting, the best lower bound I've been able to find in the literature is $\Omega(n^{1/2})$ bits: Alexander A. Sherstov, Communication Lower Bounds Using Directional Derivatives, JACM 2014, doi:10.1145/2629334 (preprint).
A large gap remains between this and the trivial upper bound of $n+1$ bits.

Sherstov's bound is for multiparty protocols.

  Is a better lower bound known for the 2-party case?

Here follows a simple (folklore?) argument that $\Omega(n/\log n)$ bits are required; I am looking for a reference for this so I can cite it, or ideally a stronger $\omega(n/\log n)$ bound.

A standard result (e.g. Theorem 2.11 in the Kushilevitz/Nisan textbook) is that $$D(f) \le O(N^0(f)N^1(f)),$$ where $N^1(f)$ is the nondeterministic communication complexity of $f$ and $N^0(f)$ is the co-nondeterministic communication complexity.
For $f = \text{DISJ}_n$ it is easy to see that $N^0(f) = O(\log n)$, by guessing the index of a common element.
Hence there are constants $C_1,C_2,C_3$ such that for all sufficiently large $n$,
$$C_1 n \le D(f) \le C_2 N^0(f)N^1(f) \le C_2 C_3(\log n)N^1(f).$$
Hence $N^1(f) \ge \Omega(n/\log n)$.


texts: Can the mutual information of a "cell" be negative?

texts:
Please forgive me if this is not the right Stack Exchange (I also posted it at Cross Validated).  Please also forgive me for inventing terms.

For discrete random variables X and Y, the mutual information of X and Y can be defined as follows:
$I(X;Y) = \sum_{y \in Y} \sum_{x \in X}
                 p(x,y) \log{ \left( \frac{p(x,y)}{p_1(x)\,p_2(y)}
                              \right) }, \,\!$

I will define the mutual information of a "cell" $x_0$ to be:
$CI(x_0,Y) = \sum_{y \in Y} p(x_0,y) \log{ \left( \frac{p(x_0,y)}{p_1(x_0)\,p_2(y)}
                              \right) }, \,\!$

I'm not sure if this quantity goes by another name.  Essentially I'm restricting focus to a single state of variable X (and then the full MI can be calculated by summing all the cell MIs).

My question: is it guaranteed that $CI(x_0,Y) \ge 0$?  We know $I(X;Y)\ge0$ and we know that the pointwise mutual information can be negative.  I feel like CI should be nonnegative and that I might be missing some obvious proof.


texts:
The diff procedure can be generalized to operate on objects other than strings.
For instance, I imagine that computational geometry asks questions like: "Given two volumes, and allowed only the operations of union and subtraction of volumes, what (shortest) sequence of operations transforms the first volume into the second?"

Seems like to generalize diff beyond strings requires three things:
1) a space of objects on which to operate (these are strings in classic diff, but could be anything like surfaces, volumes, etc).
2) for any object, a decomposition of that object into components, along with an operation -, such that OBJECT1 - COMPONENT := OBJECT2. (e.g. "abcdef" - "de" := "abcf")
3) a binary operation of addition such that OBJECT1 + OBJECT2 = OBJECT3 ("abc" + "def" = "abcdef"). Also, closure under this property.

My questions:
Q1) Can you point me to any concrete incarnations of diff outside the string domain? For instance, what's the name of the computational geometry problem I described in the first paragraph? I'm sure there's extensive literature on this but I just don't know what to google.
Q2) Is there an algebraic structure which fits the structure of generalized diff?


texts:
My initial problem is geometric, but I've reformulated it to a graph:

In the graph above I need to find the set of minimal simple cycles that form the whole graph. The initial problem was to separate the complex figure into the minimal closed regions. In the graph formulation I assume that is suffices to find the set of cycles that represents the whole graph with minimal number of edges in every cycle.

Every vertex is connected to at least two other vertices, i.e. there are no "hanging" vertices. The possible graphs are planar and bridgeless. However, in general the graph may contain multiple connected components (if this is a serious restriction - ignore it). The graph can be considered as both weighted and unweighted, but I think it's better to consider it as unweighted if the goal is to find the cycle basis of minimal closed regions. The graphs in question either have one planar embedding or multiple "equivalent" planar embeddings (e.g. consider the example graph: the parallel edges can be moved, but the simple closed loops will remain the same).

There is some ambiguity possible because of the parallel edges between some pairs of vertices. These multiple solutions are OK if they are equally valid.

I've read in http://en.wikipedia.org/wiki/Spanning_tree about fundamental cycles, but I'm not quite sure that finding the fundamental cycles will solve the problem for every case.

P.S.: See also this question https://stackoverflow.com/questions/13111236/how-to-detect-minimal-cycles-in-a-graph - it contains mine problem formulation, but no real solution. It would really be nice to give more hints than google. And https://stackoverflow.com/questions/16782898/algorithm-for-finding-minimal-cycles-in-a-graph contains some suggestions but without any serious justification.

P.P.S.: Crossposting on CS.SE was removed (the question was deleted), but this question can still be moved to CS.SE if it's better fits there. Sorry for this misunderstanding.


texts:
I've seen that the preferred way to specify the semantics of a concurrent language is to use a process calculus (e.g. pi calculus, join calculus). But in the paper presenting the F# asynchronous programming model the authors have a different approach: they first perform a CPS conversion to a core language, and then, define the semantics in terms of a transition system in which states are tuples of the form (A, Q, P), where A is the set of active computations, Q is the set of queued computations, and P is the set of pending computations--i.e. Waiting for an event. Each computation is of the form e@ctx, where ctx is a label corresponding to a synchronization context. Finally, they give transition rules for reduction (which uses the reduction rule of the core language), suspension of computations waiting on events, activation of computations (i.e. moving computations from Q to A), and event signaling.

I was wondering if this is an acceptable (i.e. accurate enough) way of specifying the semantics of a concurrent language.

EDIT: can anyone point me to papers that use a similar approach to the one taken in the F# paper?

Thanks.


texts:
Diagonally dominant matrices are known to be positive semidefinite (PSD). What are some other families of (symmetric) matrices which are known to be PSD?
Given an arbitrary matrix A, the positivstellensatz or 'sum of squares' machinery can be used as a tool towards showing that A is PSD. What are other simpler methods/tools that can be used towards proving that a matrix is PSD?


texts: complexity of finding a cycle with total weight k in a graph when you know no hamiltonian cycle in graph satisfies the given weight k

texts:
Assume a weighted graph G and a positive value k are given, and you are looking for the complexity of finding a cycle with total weight k; beside you know that no Hamiltonian cycle in G has total weight k. (G is an arbitrary weighted graph, beside you know no hamiltonian cycle would satisfy the total weight k)

1-can someone use reduction from knapsack to conclude that the complexity of finding a cycle with total weight k In G is NP-com? (I guess no!)
2-Is there any idea about the complexity of finding a cycle in G with total weight k when you know no Hamiltonian cycle in G convinces total weight k?


texts: Using Baire Category to analyze the efficiency of the Simplex Method

texts:
I read from  the wiki page of the Simplex Algorithm that we can "use Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the simplex algorithm in a polynomial number of steps."
It looks exciting, but there is no reference on the wiki page and I can't find a reference either. Could you please give me a reference?


texts: Is it possible to create a machine learning classifier to generate Mock interfaces for systems testing?

texts:
I'm investigating whether it is feasible to be able to learn a system interface by watching network traffic (assuming the usual problems are solved e.g. encryption etc)

I haven't been able to find any literature on this - but there might be a cross-discipline piece of work which could assist.

The main purpose here would be to allow complex enterprise systems to be refactored independently. A simple replay of data doesn't always work because we want to learn the request-response interface - though e.g. something like a market trade having multiple fills is an example of very complex orchestration that might make the whole thing unpractical.


texts: Is deterministic pseudorandomness possibly stronger than randomness in parallel?

texts:
Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a different name).  Define the class DBPNC similarly, except that all processes have random access into a random stream of bits fixed at algorithm startup.

In other words, each process in BPNC has access to a distinct random source, while DBPNC algorithms have a shared perfectly random counter mode generator.

Do we know whether BPNC = DBPNC?


texts: Is it decidable whether the output length of a transducer is bounded by the input length?

texts:
The transducers considered here are those Wikipedia calls finite state transducers.  The behavior of a transducer $T$, that is, the relation it computes, is written $[T]$: a word $y$ is an output for $x$ iff $x[T]y$.

Question: Is the following problem decidable:

  Given: A transducer $T$ and a regular language $L$
  Decide: Does it hold that $\forall x \in L$, $\forall y$ a word, $x[T]y$ implies that $|y| \leq |x|$?

I'm looking for nontrivial analysis/solvable subcases, reduction to known problems and/or related refs. (right now not even sure it is decidable in general...?)

Motivation: this problem was inspired by analysis/inquiry into automated theorem proving of number theoretic problems in general and a highly-studied one, Collatz conjecture, in particular.


texts:
Fix $c\geq1$.

Input is a $m$ vertex complete graph with edges assigned $a_1,\dots,a_{\frac{m(m-1)}2}\in\Bbb Z$ in some order.

Is it $\mathsf{NP}$-complete to decide if there is a perfect matching of zero-sum for cases:

(A) $|a_i|\leq m^{\frac1c}$

(B) $|a_i|\leq\log^{c}m$?

I looked at the literature for perfect matching and subset sum and could not find this version.

The closest was minimum weight perfect matching which has a polynomial time algorithm as in http://www.math.uwaterloo.ca/~bico/papers/match_ijoc.pdf which however in this case does not work.

It also seems like restricted version of subset sum and so the complexity is not obvious because of size of $|a_i|$.

Update: Including case C.

(C) What if $a_i$ needs roughly $m^\alpha$ bits for some fixed $\alpha>0$?


texts: Implicit Non-deterministic Buchi determinization

texts:
I am doing implicit Buchi determination for LTL logic in hardware where the combinational logic represents the set of states.

But instead of using acceptance states, I am using final state (as in NFA). Using this approach it seems that I can synthesize all co-safety  and safety properties.

Is my assumption wrong?

In their paper "Model-checking for safety properties" Orna kupferman and vardi prove that finite alternating automata which is obtained by redefining the set of accepting states as empty states can monitor all the informative prefixes for safety, co-sfety properties. So in my algorithm I construct Buchi automata for LTL property(negation) and define the accepatnce set as the empty set(unconditionally accepting state) in it.   So my question can be reframed as "Is the assumption that the definition of acceptance set as empty in alternating automaton is equivalent to defining acceptance set in Buchi automata as empty and hence the Buchi automata recognizes all the prefixes recognized by finite alternating automata"?
Thanks for all the suggestions and reply.***


texts: I'm not a theoretical computer scientist. I'm a stable homotopy theorist using $\infty$-categories. I've seen applications of category theory and topos theory to theoretical computer science, and I was wondering if there was any way one could use $\infty$-categories (and preferably for me, stable homotopy theory) in theoretical computer science. I think HoTT mught be one such application, but I may very well be wrong because I know close to nothing about HoTT. (So I also don't know how HoTT is used in TCS.)


texts: Hook length formuli and their invariance properties?

texts:
Let $P = (V,\leq_P)$ be a poset, and for each $x \in V$ let $x^P = \{ y \in V : x \leq_P y \}$. A well-known property of certain posets (forests, Young diagrams) is the existence of a simple hook length formula counting their linear extensions - while the problem is $\# P$-hard in general. To make this notion precise, we say that $P$ has a hook length formula if there exists a function $h : V \rightarrow \mathbb{N}$ such that for every $x \in V$, the number of extensions of $P | x^P$ is equal to:

  L(x) = $\frac{|x^P|!}{\prod_{y \geq_P x} h(y)}$.

It can be seen that this property is preserved by some natural operations: parallel composition, adjonction of a minimal or maximal element. This immediately implies the Knuth hook formula for forests, although it has a number of different proofs (including some of algorithmic nature).

I'd like to know if there are examples of other operations preserving/breaking the existence of a hook length formula, in particular is it possible to define a gluing operation extending the above adjonction operation?


texts: Where can I find a copy of Guy Jacobson's thesis "Succinct Static Data Structures"?

texts:
I'm looking for a copy of Guy Jacobson's PhD thesis: http://dl.acm.org/citation.cfm?id=915547 but I couldn't find it so far. Does anybody know where can I access it ? I really need it.

Thanks in advance.


texts: Is there a P-complete language X such that succinct-X is in P?

texts:
I came across a paper called "A Note on Succinct Representation of Graphs".  It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\mbox{succinct-X}$ is $\mathrm{EXP}$-hard.

This made me wonder if the theorem fails for more complicated kinds of reductions.  This led me to the following.

  My Question

  Are there any problems $X$ such that $X$ is $\mathrm{P}$-complete
  under logspace reductions and $\mbox{succinct-X}$ is in $\mathrm{P}$?

Additional Questions:

(1) If this is an open problem, then what are the implications if such an $X$ existed?

(2) If this is an open problem, is it still open is we weaken the requirement to $\mbox{succinct-X}$ in $PH$?

(3) It seems that such an $X$ would also satisfy that $X$ is $\mathrm{P}$-hard under logspace reductions, but not $\mathrm{P}$-hard under projections.  Are such problems known to exist?

(4) I might be mistaken, but I think that I have a construction for such an $X$ assuming that $NP = L$.  Would this be interesting?

Note: I'm still learning about projections so please let me know if I made any mistakes.  Thank you!


texts: Transactional partially-ordered message queuing

texts:
I'm having a really hard time finding a solution to a practical programming problem, and I think raw CS might have an answer.

The requirement is for a familiar message queue for which there are multiple message Generators and multiple message Consumers.  Generators enqueue messages into a queue within the scope of an transaction.  Consumers dequeue messages within the scope of a transaction, and process the message successfully, removing it from the queue, or fail and roll back the transaction in which case the message remains on the queue.  The message may be left on the queue by the Consumer in an altered state - decrementing a retry-count, for example.

Adding to this the concept of a Sequence or Conversation - a partial ordering within the set of all messages in the queue.  Messages which are part of a Sequence are to be consumed in-order.  Sequences are unordered amongst Sequences.

Generators do not block other Generators unless the messages being enqueued are for the same Sequence.  Generators never block Consumers.  Consumers never block Generators.  And Consumers never block other Consumers.  That is, Enqueue() may block, Dequeue() never blocks.  Generators Enqueue a message exactly once.  Consumers successfully process each message exactly once.

It'd be nice if the implementation doesn't leave too much trash data around, but as long as old data can eventually be trimmed, that's fine.

It seems like this scenario should be possible, yet I cannot find or design correct rules on a common platform.  SQL Service Broker might match all of these criteria, but if it does, how does it?

Is such a protocol provably impossible?  If not, how might it be done/what properties must the underlying storage platform have to support it?


texts: Can chess simulate a Universal Turing Machine?

texts:
I am looking to get a definite answer to title question.

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (ie the simplest game) that is needed for a chess-like game to be turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations).

Is there any piece we can add to the game to prove it turing complete?


texts: Binary search generalizations for posets?

texts:
Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.

EDIT: I'm interested in minimizing the number of evaluations of P.

What algorithms do there exist for this problem and what properties and additional operations do they require on S?

What about important special cases, such as:

 S is a linear order - then regular binary search works, as long as you have a "find middle" operation
 S is a lattice
 S is a subset lattice
 S is a multiset lattice
 ...

The two latter cases seem particularly important e.g. for experiment design - you have a set of boolean or real parameters, and you wish to find the smallest possible combination of them that reproduces a particular pattern (e.g. a failing test).


texts: How to efficiently find a loop between two nodes in a directed graph?

texts: Given two nodes in a directed graph, how can I find a loop (if exists) that pass these two nodes? The loop cannot pass a node more than once. And if there isn't such a loop, how to efficiently determines it?


texts: Hitting set of pairwise intersecting families

texts:
A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$.
The problem to find a minimum hitting set of a given family is NP-hard in general,
since it generalizes the vertex cover problem. Now my question is:

  Does the hitting set problem remain NP-hard when the elements of $\mathcal{S}$ pairwise intersect?

I am also interested in the approximation hardness (or tractability) of this problem.


texts:
What is "the best" algorithm to find the densest subgraph of size k?

i.e. a subgraph of size k with the maximum number of edges inside for an unweighted and undirected graph.

For fixed k, the straightforward brute-force algorithm takes $O(n^k)$ time with n the number of nodes. I'm looking for something, like $O(2^kn)$ or so. Maybe using a recursive algorithm or dynamic programming.


texts: Physical realization of nonlinear operators for quantum computers.

texts:
I have read in a paper where nonlinear operators for quantum computers implies the solving of problems in #P time. See http://arxiv.org/pdf/quant-ph/9801041 .
What would be the simplest realization of this? Could you limit its power to solve easy problems in #P Also is this equiavlent to $PostBQP$ or any other complexity class?


texts: algorithm to find a point among n points in plane to minimize the sum of distances

texts:
I have an algorithm problem here. It is different from the normal Fermat Point problem or Geometric Median problem.

Given a set of $n$ points in the plane, I need to find which one can minimize the sum of distances to the rest of $n-1$ points.

Ideally I'd like to have an algorithm for any distance; but giving a nice solution for the usual Euclidean distance is also fine.

Is there any algorithm you know of run less than $O(n^2)$?

Thank you.


texts:
I am looking for a reference (not a proof, that I can do) to the following extension of Chernoff.

Let $X_1,..,X_n$ be Boolean random variables, not necessarily independent.
Instead, it is guaranteed that $Pr(X_i=1|C)<p$ for each $i$ and every event $C$ that only depends on $\{X_j|j\neq i\}$.

Naturally, I want an upper bound on $\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$.

Thanks in advance!


texts:
I'm looking for the correct name of geometric structures obtained as follows.

2-structures: A collection $X$ of triangles is a $2$-structure. If $X$ is a $2$-structure and $Y$ is obtained from $X$ by gluing two free edges belonging to triangles in $X$, then $Y$ is a $2$-structure.

3-structures: A collection $X$ of tetrahedra is a $3$-structure. If $X$ is a $3$-structure and $Y$ is obtained from $X$ by gluing two free triangles belonging to tetrahedra in $X$, then $Y$ is a $3$-structure.

k-structures: A collection $X$ of $k$-simplices is a $k$-structure. If $X$ is a $k$-structure and $Y$ is obtained from $X$ by gluing two free (k-1)-simplices belonging to $k$-simplices in $X$, then $Y$ is a $(k-1)$-structure.

Alternatively, a $k$-structure can be non-inductively defined as a homogeneous simplicial k-complex $X$, satisfying the following conditions.

The intersection of any two k-simplices in X is either empty or a (k-1) simplex.
Each (k-1)-simplex is the intersection of at most two $k$-simplices in $X$.

Question: What is the correct name for $k$-structures?


texts: Using the extra power of the negative adversary method

texts:
The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that hindered the adversary method:

The property testing barrier: if all 0-instances are $\epsilon$-far from all 1-instances then the adversary method cannot prove a lower bound better than $\Omega(1/\epsilon)$.
The certificate complexity barrier: if $C_b(f)$ is the certificate complexity of $b$-instances then the adversary method cannot prove a lower bound better than $\sqrt{C_0(f)C_1(f)}$ where

In the original $ADV^\pm$ paper the authors construct an example function for which their method overcomes both barriers. However, I have not see examples of any natural problems where this has yielded new lower bounds.

  Can you provide any references where the negative adversary method was used to achieve a lower bound that the original method could not attain?

The biggest interest for me, is in property testing. Currently there are very few lower bounds on property testing, in fact I only know two (CFMdW2010, ACL2011), that both use the polynomial method (the first by reduction from the collision problem which was originally lower bounded by polynomial method). We know that there are properties that require $\Theta(f(n))$ quantum queries to check, for any computable $f(n) \in O(n)$ (by combining the results in BNFR2002 and GKNR2009). Why is so hard to use the negative adversary method to prove $\Omega(f(n))$ lower bounds on them?


texts: For a random oracle R, does BPP equal the set of computable languages in P^R?

texts:
Well, the title pretty much says it all.  The interesting question above was asked by commenter Jay on my blog (see here and here).  I'm guessing both that the answer is yes and that there's a relatively simple proof, but I couldn't see it offhand.  (Very roughly, though, one could try to show that, if a language in $P^R$ were not in $BPP$, then it must have infinite algorithmic mutual information with $R$, in which case it wouldn't be computable.  Also, note that one direction is trivial: the computable languages in $P^R$ certainly contain $BPP$.)

Note that I'm not asking about the class AlmostP, which consists of those languages that are in $P^R$ for almost every $R$ (and is well-known to equal $BPP$).  In this question, we first fix $R$, then look at the set of computable languages in $P^R$.  On the other hand, one could try to show that, if a language in $P^R$ is computable, even for a fixed random oracle $R$, then in fact that language must be in $AlmostP$.

A closely-related question is whether, with probability 1 over a random oracle $R$, we have

$ AM = NP^R \cap Computable.$

If so, then we get the following interesting consequence: if $P=NP$, then with probability 1 over a random oracle $R$, the only languages that witness the oracle separation $P^R \ne NP^R$ are uncomputable languages.


texts: What algorithms/reading matter would you recommend on resolving transactions / read-write locks?

texts:
A simplified classical database transaction can be viewed as:

reading M items
performing some calculation based on those reads
writing some N results based on these calculations, which may include the elements originally read.

When performing these transactions (concurrently) the ACID properties need to be maintained.

Exactly the same requirements (N updates based on M reads transactionally) exist in other non-DBMS concurrent systems.

I'm interested in finding out what algorithms exist for performing/resolving these transactions, and what the relative strengths and weaknesses of these algorithms are. Could you recommend some reading? This could be books or online references/tutorials.

Clarification:

So for example, a naive algorithm might be each transaction taking a single global lock, in effect forcing single threading and removing concurrency. A slightly more complicated algorithm would be individual item read/write locks, with an ordering to avoid deadlock). Etc, etc. Is there a good source documenting various algorithms for solving this problem. Even an answer which only pointed to a single algorithm with it's strength and weaknesses would be useful.


texts: Can you explain an intuition behind Coherent Spaces?

texts:
Linear Logic is interpreted using Coherent spaces, and they feature prominently in Girard's papers. I know all the three main ways to formally define them, and they don't really pose any problem to use and prove stuff about, but I just can't understand what they mean.

It really feels like there is some kind of a way to understand them. First of all, there're some examples about them which use functions on booleans (like at a wiki somewhere). And it hints at something interesting and meaningful behind the formal definition. However, bool is a very simple coherent space, with no clique of size > 1. Can someone elaborate?

Another thing Girard says somewhere that every point of a coherent space represents a specific "sequence of questions/answers", with two points being coherent if they "bifurcate negatively (i.e., on different questions)", and incoherent if they bifurcate on different answers[1]. It seems like an easy to grasp idea but I just can't invent an example so it means I don't really get it...

Could someone please help me with that?

[1] J-Y Girard, The phantom of transparency. URL: http://iml.univ-mrs.fr/~girard/longo1.pdf


texts:
What are some examples problems with a direct proof that they are in $\mathsf{IP}$, other than Graph Non-Isomphism?

I have been looking for a while, but no luck so far.


texts: Computational Complexity of the Divisor summatory function

texts:
The divisor function $d(n)$, is the number of $(a,b)\in\mathbb {N^+}^2$ such that $a\times b =n$.
For example, $d(2)=2$ because $2=1\times 2=2\times 1$ and d(6)=4 because $6=1\times 6=2\times 3=3\times 2=6\times 1$.

The divisor summatory function is defined by :
$$D(n)=\sum_{i=1}^n d(i)$$

This is sequence A006218 in OEIS.

Does anyone know the best time complexity algorithm to compute this function ? Are they any results published on the computational complexity of this function ?


texts: Clarification needed on an algorithm for $\epsilon$-net construction for the column space of PSD matrices

texts:
I found an algorithm for constructing an $\epsilon$-net for a positive semidefine matrix $A\in[-1,1]^{n\times n}$ which has $rank(A)=d$, described in the paper

  The approximate rank of a matrix and its algorithmic applications

by Alon et al. The main problem is to approximate the quadratic form $x^TAy$, where $x,y\in \Delta_n:=\{x\in R^n:\|x\|_1=1,x\geq0\}$ and $A$ is a positive semidefinite matrix, so it can be written in the form $A=BB^T$ for a matrix $B\in R^{n \times d}$. The authors give an algorithm that constructs a $\frac{\epsilon}{\sqrt[]d}$-net for $A$ with respect to the $\|\|_{\infty}$ norm. It's description can be found in the proof of Theorem 3.1 of the paper.

It seems to be unclear how many samples this algorithm requires and by its description, I hesitatingly deduce that it works with just one sample from $\Delta_n$. Is my conclusion correct and if it is, why?


texts:
I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd cover" if for any graph vertex, v, at least one vertex in the odd cover is an odd distance from v. The distance between two vertices is the minimum number of edges that connects them.

This question is related to the Exactly 1 in 3 Satisfiability problem so I am mostly interested in triangular graphs. I would be interested in anything that can be said about independent sets that are odd covers. Has anyone seen anything similar? For example, is it NP-Hard to prove a graph has no independent set that is an odd cover? This is an example of an independent set that is an odd cover:

a-b-d
|/ \|
c   e
|\ /|
f-g-h

Odd cover: {a, d, f, h}

This corresponds to the X3SAT instance (a,b,c) (b,d,e) (c,f,g) (e,g,h). Any satisfying assignment will be a maximum weight independent set where the weight of a vertex is its degree. Of the seven satisfying assignments, only {a, d, f, h} is an odd cover.

I asked this question on SE and go no responses.

An odd cover means any vertex in the graph is an odd distance from at least one vertex in the odd cover. In my example:

Vertex - Vertex in Odd Cover
a - h
b - a
c - a
d - f
e - d
f - d
g - f
h - a

This is related to the X3SAT problem. Any satisfying assignment will be a maximum weight independent set, but only some of the solutions will also be odd covers. For example, {b,g} is a maximum weight independent set but is not an odd cover. Adding the clauses in the comments gives us (a,b,c)(b,d,e)(c,f,g)(e,g,h)(a,i,j)(j,k,l)(l,m,n). This has a maximum weight independent odd cover: {a,d,f,h,k,m}. A straight chain of triangles like (a,b,c)(c,d,e)(e,f,g)(g,h,i) can not have an odd cover.


texts: I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?


texts: Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

texts:
In a paper titled "On Deniability in the Common Reference String and Random Oracle Model," Rafael Pass writes:

  We note that when proving security according to the standard zero-knowledge definition in the RO [Random Oracle] model, the simulator has two advantages over a plain model simulator, namely,

  The simulator can see what values parties query the oracle on.
  The simulator can answer these queries in whatever way it chooses as long as the answers "look" OK.

The first technique, namely the ability to "monitor" queries to the RO, is very common in all papers referring to the concept of zero-knowledge in the RO model.

Now, consider the definition of black-box zero-knowledge (PPT stands for probabilistic, polynomial-time Turing machine):

$\exists$ a PPT simulator $S$, such that $\forall$ (possibly cheating) PPT verifier $V^*$, $\forall$ common input $x\in L$, and $\forall$ randomness $r$, the following are indistinguishable:

the view of $V^*$ while interacting with the prover $P$ on input $x$ and using randomness $r$;
the output of $S$ on inputs $x$ and $r$, when $S$ is given black-box access to $V^*$.

Here, I want to exhibit a cheating verifier $V'$, whose job is to exhaust any simulator which tries to monitor RO queries:

Let $S$ be the simulator guaranteed by the existential quantifier in the definition of black-box zero-knowledge, and let $q(|x|)$ be a polynomial which upper-bounds the running time of $S$ on input $x$. Assume that $S$ tries to monitor the queries of $V^*$ to the RO.

Now, consider a cheating $V'$, which first queries the RO for $q(|x|)+1$ times (on arbitrary inputs of its choice), and then acts arbitrarily maliciously.

Obviously, $V'$ exhausts the simulator $S$. A simple way for $S$ is to reject such malicious behavior, yet that way, a distinguisher can easily distinguish the real interaction from the simulated one. (Since in the real interaction, the prover $P$ cannot monitor $V'$'s queries, and thus won't reject based on the mere fact that $V'$ is querying too much.)

  What is the workaround for the above problem?

Edit:

A good source for studying ZK in the RO model is:

Martin Gagné, A Study of the Random Oracle Model, Ph.D. Thesis, University of California, Davis, 2008, 109 pages. Available on ProQuest: http://gradworks.umi.com/33/36/3336254.html

Particularly, it gives definitions of black-box ZK in the RO Model in section 3.3 (page 20), attributed to Yung and Zhao:

Moti Yung and Yunlei Zhao. Interactive Zero-Knowledge with Restricted Random Oracles.  In Theory of Cryptography - TCC 2006, LNCS 3876, pp. 21-40, 2006.


texts: Array partitioning with limitations on partition size

texts:
Consider an array of bytes.

I want to partition the array, such that the following two conditions hold:

The number of bytes within each partition (except perhaps the last one) is between L and U, inclusive. Here, L is much smaller than U.
Given a sub-array (i.e. consecutive bytes) of the main array, partition boundaries within the sub-array can be detected.

Example:

Let the array of bytes be:

Let L = 2 and U = 4.

The following partitioning satisfies requirement 1 (red lines depict partition boundaries). Notice that the size of all partitions is between L and U inclusive.

To explain requirement 2, assume that the following sub-array is given:

An algorithm satisfying requirement 2 should be able to correctly identify partition boundaries:

PS: An idea which only satisfies the second requirement is called winnowing. It uses a sliding window over the bytes, computes some fingerprint in each window, and then uses another sliding window (the "winnowing" window) over fingerprints, and then selects the boundary to be the byte corresponding to the fingerprint which satisfies some property in each winnowing window.

Edit: If no such algorithm exists, we can think of some relaxations. The one that best fits my case changes requirement 1 as follows:

Let p(n) be the fraction of partitions of length n. We want p(n) to follow some bell-shaped distribution with mean $\mu$ and standard deviation $\sigma$. This way, I can reduce $\sigma$ to concentrate the partition lengths around $\mu$.


texts:
I think this should be a famous problem but I could not find its name.

I have $n$ jobs with size $s_i$ that are offered at time $t_i$ and $k$ machines.
How can I assign jobs to machines to minimize the maximum finish time.

I know that when the offering times $t_i$s are equal, this is a partition problem as it balances the jobs over machines. Also I know that there are approximation algorithms for that.

Is there any greedy algorithm (with approximation bound) for this generalized version?


texts:
I'm interested in a slight generalisation of DFA. As usual we have state-set $Q$, finite alphabet $\Sigma$, a $\Sigma^*$-action defined on $Q$ by $\delta : Q\times\Sigma\rightarrow Q$, and initial state $q_0$; but instead of the usual terminal set, we take a family $(T_i)_{i\in 1..n}$ of subsets of $Q$. A Multi-language DFA $M$ is then the tuple

$(Q, \Sigma, \delta, q_0, (T_i))$

and $L \subseteq \Sigma^*$ is recognised by $M$ iff $L = \{s\in\Sigma^*|q_0s\in T_i\}$ for some $i\in 1..n$ . Define $(L_i(M))_{i\in 1..n}$ to be the family of languages recognised by M, if you like.

Okay, now for my question: given a family of regular languages $(L_i)_{i\in 1..n}$ , I want to find the minimal Multi-language DFA $M$ as described above such that $L_i = L_i(M)$ for all $i\in 1..n$ , that is, such that $|Q|$ is minimised over all such machines. My question is, are there any known efficient ways of doing this, perhaps analogous to standard DFA minimisation theory? Conversely, is there any evidence that this problem might be hard?


texts: Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

texts:
Quite similar to my previously posted question. This time however, the graph is undirected.

Given

An undirected graph $G$ with no multiple-edges or loops,
A source vertex $s$,
A target vertex $t$,
Maximal path length $l$,

I am looking for $G'$ - A subgraph of $G$ that contains any vertex and any edge in $G$ (and only those), that are part of at least one simple path from $s$ to $t$ with length $\leq l$.

Notes:

I don't need to enumerate the paths.
I'm looking for an efficient algorithm (both time and memory), as I need to execute it over very large graphs (10^8 vertexes, 10^9 edges).


texts:
Today Ryan Williams posted an article on the arXiv (previously appeared in SIGACT News) containing a less technical version of his recent ACC lower bound technique.

My question is not about the technique itself (of course worthy of immense praise), but it's about the style of the paper.
In the abstract, he writes:

  The proof will be described from the perspective of someone trying to
  discover it.

Awesome!
In the Background section he adds:

  This article is a discussion about how to discover the proof – a
  casual tour around it. Not all details will be given, but you will see
  where all the pieces came from, and how they ﬁt together. The path
  will be littered with my own biased intuitions about complexity theory
  – what I think should and shouldn’t be true, and why. Much of this
  intuition may well be wrong; however I can say it has led me in a
  productive direction on at least one occasion.

This is amazing and it's the first time that I have seen it. I have always wondered why authors of paper don't write how they got to the proof, including the failed approaches they tried before getting to the track that led the solution. When I saw Ryan's paper on the arXiv, I felt very motivated to read it.
I consider it a revolutionary paper from this point of view. Most of the time the only thing you can do with a paper is verifying its correctness.

The question is the following:

are you aware of other papers in TCS where a breakthrough result is presented in a "casual tour" rather than a series of technical lemmas?

I am talking about publications in journals, not blog posts or technical reports.

Also, I tagged it as big-list, with the hope that it will actually be.


texts: PTAS Algorithm for K-Clustering when Distance Computation is Costly

texts:
Can anyone throw any light on any PTAS algorithm that I can apply for K-Clustering algorithm when the distance computation between the clustering points is costly.

In details, I have a set of N points and I have a customized distance metric between them. I want to compute a set of k clusters such that the cluster centers are far apart while among the clusters the points are very close. This customized distance metric is costly to calculate and hence I would like them to be calculated as less as it can possibly be.

I can give more clarification if required.

[EDIT] So the distance metric I have defined is $D(x,y) = 1 - \rho(x,y)$ where $\rho(x,y)$ is the Pearson Correlation Coefficient between points $x$ and $y$ ( $x$ and $y$ are data sets in themselves). Obviously to compute all such Pearson Correlations Coefficient when the number of data-points is 1000 (each set $x$ has another 1000 or so values within themselves) or so can be very expensive computationally.


texts: Consider the logic whose $\tau$-sentences are the sentences in $IFP(\tau \cup \{<\})$, and the satisfaction relation is given by $\mathfrak{A} \models^* \phi$ if $(\mathfrak{A}, <)  \models \phi$ for every ordering $<$ of $\mathfrak{A}$. Why does this logic not capture PTIME? I suppose that it is because a machine cannot quickly determine whether whether all linear orderings satisfy the sentence, but is there a formal proof of this?


texts: Finding most informative feature subsets given dataset, clustering algorithm and gold standard partition

texts:
I have an $n \times m$ matrix of data $\mathbf{D}$ as well as a $k$-partition $P$ of $n$ indices each representing a row in a dataset. Assuming an arbitrary clustering algorithm $A$, I would like to find a subset $F$ of $\{1,\ldots, m\}$, representing indices of the columns of $D$, such that applying $A$ to only the columns indexed by $F$, an $n \times |F|$ matrix, minimizes the average variation of information (VI) between $P$ and the output of $A$. Another way of saying this is that I would like to be able to find the subspace on which $\mathbf{D}$ is most informative about $P$.

(That the metric is VI or that the statistic taken over multiple runs is an average is not necessarily important. I'm looking for a general solution, but if a solution that specifies either the metric or the clustering algorithm exists, I'd be interested.)

Attempting to build the distribution of (normalized) variation of information values by brute force is not practical since the number of possible subsets of $\{1,\ldots, m\}$ is the Stirling number (of the second kind) $S(m, 2)$, which obviously gets monstrous as $m$ gets to any interesting size.


texts: $\ell_p$-norm preserving Turing machines

texts:
Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine.

For people working in complexity theory going to quantum complexity a great introductory text is Fortnow's paper which link was posted by Joshua Grochow here. In that paper, the quantum Turing machine is presented as a generalized probabilistic Turing machine. Basically, the probabilistic machine have a state $s$ normalized under the $\ell_1$-norm, i.e. $\parallel s\parallel_1=1$. The time evolution of the machine is given by the application of a stochastic matrix $P$ such that $\parallel Ps\parallel_1=1$, i.e. $P$ preserves the $\ell_1$-norm. So the state at time $t$ is $P^ts$ (the notation may not be precise because the left or right multiplication of $P$ depends on if $s$ is a row or column vector or the rows or columns of $P$ are the subspaces preserving the norm). So in this sense the probabilistic Turing machine is a $\ell_1$-norm preserving machine denoted $M^{\ell_1}$.

Then a quantum Turing machine can be seen as having a state $s$ with $\parallel s\parallel_2=1$ and unitary matrix $P$ (that preserves $\ell_2$-norms) such that $P^ts$ is the state at time $t$ where $\parallel P^ts\parallel_2=1$. This is a $\ell_2$-norm preserving machine denoted $M^{\ell_2}$.

Let in general a $\ell_p$-norm preserving machine be denoted by $M^{\ell_p}$.

So my questions are:

(1) What's the power of $\ell_p$-norm preserving machines for finite $p$? More formally, can we prove that for any given $p$ and $q$, if $q>p$ then there exists a language $L$ and machine $M^{\ell_q}$ such that $M^{\ell_q}$ efficiently decides $L$ and there is no machine $M^{\ell_p}$ that efficiently decides $L$. For example, this could be a generalization of the question, is $NP \subseteq BQP$?.

(2) What about $p=\infty$? Here the maximum value of the components of the state vector is 1.

(3) These questions goes beyond unitarity so it is not expected to agree with quantum mechanics. In general, what happens with computation if you relax the unitarity restriction on operations? There are works about allowing non-linear operators (see Aaronson 2005).

(4) Maybe the most important, is it universal? I think this is clear, because for particular cases it is universal. But what happens with universality when $p=\infty$?


texts: Finding simple fixed length paths in directed graphs

texts: Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?


texts:
I see in certain places "lifting computation" or "lifting" mentioned. I haven't been able to accurately define for myself what is meant by that.

This usually comes up in computer science context. Any ideas what it means?


texts: Communication complexity for deciding associativity

texts:
Let $S=${$0,...,n-1$} and $\circ : S \times S \rightarrow S$. I want to compute the communication complexity of deciding whether $\circ$ is associative.

The model is the following. $\circ$ is given as a matrix $M$. Alice (resp. Bob) is given half the entries of the matrix at random (same for Bob). I want to compute the worst case number of entries that Alice must send to Bob so that Bob can decide on the associativity of $\circ$.

In fact, it is simple to reduce the problem of deciding the equality of two bit strings of size $\Omega(n)$ to the problem of deciding the associativity of $\circ$ over $S$. This means that the communication complexity of the associativity is lower bounded by $\Omega(n)$. However, I suspect that this LB is not tight. Being defined on an input of size $n^{2}$, I would have prefer to find a communication complexity of $\Omega(n^{2})$.

Is there a known result on this problem ? Is the answer is $n^{2}$ for an obvious reason I am not seeing ?


texts:
In the classical λσ calculus of explicit substitutions, there is the following rewrite rule:

(a[s])[t]  ==>  a[s ∘ t]

where a[s] denotes the application of substitution s to term a.

This seems backward/counterintuitive to me: if we consider substitutions as sorts of functions, then (a[s])[t] can be thought of as t(s(a)), which we could write as (t ∘ s)(a) aka a[t ∘ s] and not a[s ∘ t].

What is the reasoning behind this notation?


texts: Does there exist an ontology for algorithms?

texts:
It appears that algorithmic complexity theory has already figured out Kolmogorov complexity, when applied to representations of programs themselves, can already serve as a solid theoretical metric of enumeration and comparison for programs, given a common basis language.

Does there exist an online database that attempts to enumerate algorithms similar to the Human Genome Project according to a basis encoding or language?


texts:
A straight line program with division is very powerful https://rjlipton.wordpress.com/2012/10/16/one-mans-floor-is-another-mans-ceiling/.

Is it possible to reduce a straight line program with $\sqrt{~}$ allowed to one in which $\sqrt{~}$ not allowed without increasing the program size too much?


texts: Does there exist the idea of "RP-complete", like NP-complete?

texts:
NP-hardness and NP-completeness play an important role in complexity theory.
My question is, does there exist a language $L$ in RP
to which any language $M$ in RP can be reduced in polynomial time?
We can say that such a language $L$ is "RP-complete", if exists, but I cannot find any information about this idea. Can anyone tell me about it, please?