texts: How fine-grained can the time hierarchy theorem be in a reasonable model?

texts:
One version of the sharp or additive space hierarchy theorem is that for Turing machines (and a number of other deterministic sequential computational models) $\mathrm{Space}(f-ω(\log(n+f))) ⊊ \mathrm{Space}(f)$ for space-constructible $f(n)$, where space is measured in bits.

Are there reasonable computational models where we have an analogous sharp version of the time hierarchy theorem: $\mathrm{Time}(f+O(1)) ⊊ \mathrm{Time}(f+O(g))$ for $g$-time-computable $f(n)$ with $g(n)≥\log(n+f(n))$?

Since I already know one (arguably reasonable) class of models with the sharp time hierarchy, I am including it as an answer, but I am still interested in related results, including
- other models with the sharp time hierarchy theorem
- whether this model or other models were studied in literature
- weaker forms of time hierarchy, especially if stronger than $\mathrm{Time}(f) ⊊ \mathrm{Time}((1+ε)f)$
- whether there is a speed-up theorem for Turing machines with a fixed number of binary tapes that would prevent this form of sharp time hierarchy.

Footnotes/References:
* The additive/sharp space hierarchy theorem can proved using "Halting Space-Bounded Computations" by Michael Sipser (1978).  See also "Improved time and space hierarchies of one-tape off-line TMs" by Kazuo Iwama and Chuzo Iwamoto (1998).
* A weak form of additive time hierarchy is discussed in "Computational Models with No Linear Speedup" by Amir Ben-Amram, Niels Christensen, Jakob Grue Simonsen (2012).


texts:
I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book.

We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ where weight of every edge $(u,v) \in E$ is a positive number ($w(u,v)>0$).

Actually it asks to prove that finding the shortest path from $s$ to $t$ is equivalent with finding a max flow $f$ from $s$ to $t$.

$f$ minimizes the amount of $Σ_{(u,v)\in E} f(u,v)w(u,v)$ and has the value of $|f|=1$.

It seems that i am missing something. Can anyone help me with this cause i really hate leaving unsolved exercises when reading a book.

Thanks.


texts: Efficient update of the keys in associative container

texts:
I need to maintain a set $\langle(k_1, v_1), (k_2, v_2), \dots, (k_N, v_N)\rangle$ of key-value pairs subject to the following update operation.  Given two keys $a < b$ and a "shift" value $C$ as input, an update first deletes all pairs whose keys are in the range $[a-C, b-C]$  and then shifts all keys in the range $[a,b]$ downward by $C$.  More explicitly:

Delete every pair $(k_i, v_i)$ such that $a-C \le k_i \le b-C$.
Replace every pair $(k_i, v_i)$ such that $a\le k_i\le b$ with the pair $(k_i-C,v_i)$.

How can I support this update operation efficiently?  I would prefer an algorithm that performs the update "in-place" instead of allocating and deallocating temporary memory.


texts:
I'm reading some lecture notes saying that “fix cannot be defined in the simply typed lambda-calculus” and that “no expression that can lead to non-terminating computations can be typed using only simple types.”

I'm sure more of this will be covered later, but it left me curious: What is needed in a type system to support defining fix? I.e., how can I simply type (in Haskell): fix f = let x = f x in x and get the type (a → a) → a? Also, is this related to needing to write let rec in ML/F#?


texts:
Assume that we have $p$ finite sets ${m_1},{m_2},...,{m_p}$, with known cardinalities
${M_1},{M_2},...,{M_p}$, where $1 \le {M_i} \leq q$ ($i=1,2,...,p$).

Each set contains (distinct) elements, taken from GF($q$) (I am interested in particular in the case where $q$ is a power of $2$). Now, we consider all possible assignments of elements to $\left\{ {{m_i}} \right\}_{i = 1}^p$. It is clear that we have $\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}}
  q \\
  {{M_i}}
\end{array}} \right)} $ such assignments.

For each assignment $A_k$ ($k=1,2...,\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}}
  q \\
  {{M_i}}
\end{array}} \right)} $) we consider all possible combinations of elements from the sets in the assignment, when one element is taken from each set (that is, we have $p$ elements for each combination), and we sum the elements of each combination, using GF($q$) arithmetic. There are $\prod\limits_{i = 1}^p {{M_i}} $ possible combinations/sums for each assignment.

Given the sums $S_{kj}$ ($j=1,2,...,\prod\limits_{i = 1}^p {{M_i}}$) for each assignment $k$, we count the number of distinct elements of GF($q$) among these sums, and we write down this number, $d_k$.

Repeating this process, we end with $\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}}
  q \\
  {{M_i}}
\end{array}} \right)} $ numbers.

As an example, consider the case $q = 4,p = 2,{M_1} = {M_2} = 2$. Possible assignments to $m_1$, as well as for $m_2$ in this case, are:

$$\left\{ {0,1} \right\},\left\{ {0,2} \right\},\left\{ {0,3} \right\},\left\{ {1,2} \right\},\left\{ {1,3} \right\},\left\{ {2,3} \right\}$$

Assume a specific assignment ${m_1} = \left\{ {0,1} \right\},{m_2} = \left\{ {1,2} \right\}$. We have $4$ combinations/sums:

$0 + 1 = 1,0 + 2 = 2,1 + 1 = 0,1 + 2 = 3$ and for this specific assignment the number of distinct elements is $4$.

Another possible assignment is ${m_1} = \left\{ {0,1} \right\},{m_2} = \left\{ {0,1} \right\}$. Now the combinations/sums are $0 + 0 = 1,0 + 1 = 1,1 + 0 = 1,1 + 1 = 0$ and we have $2$ distinct elements. Repeating this, we obtain $\left( {\begin{array}{*{20}{c}}
  4 \\
  2
\end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}}
  4 \\
  2
\end{array}} \right) = 36$ numbers.

Denote by $d$ the random variable that counts the number of distinct elements for each assignment. My question is: what is the probability that $d=n$ ($n=1,2,...,q$)? in other words, given cardinalities ${K_1},{K_2},...,{K_p}$, what is the probability that the number of distinct sums for a randomly chosen assignment equals $n=1,2,...,q$?

I tried to formulate this as the probability that union of $\frac{{\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}}
q\\
{{M_i}}
\end{array}} \right)} }}{{{{\max }_i}\left( {{M_i}} \right)}}$ sets of cardinality ${\max _i}\left( {{M_i}} \right)$ is of size $n$ (this way the probability is zero for $d < {\max _i}\left( {{M_i}} \right)$), but this does not take into account additional properties of GF($q$).

It is interesting to note that in the example above, we have zero probability for $d=3$:
$$\Pr \left( {d = 1} \right) = 0,\Pr \left( {d = 2} \right) = 1/3,\Pr \left( {d = 3} \right) = 0,\Pr \left( {d = 4} \right) = 2/3$$

I also noted that when $M_i=2$ and $q=4$, we have for each $p$: $\Pr \left( {d = 2} \right) = 1/3^{p-1}$.

(This probability distribution was calculated using a computer, computing $d_k$ explicitly for each assignment).


texts:
I'm reading about type inference in chapter 30 of Programming Languages: Application and Interpretation and I'm trying to understand exactly how the occurs check works in an example I came up with.

Constraints generation is presented in this table:

So, given the term λx.x x, we get the following two constraints, as far as I can see:

[λx.x x] = [x] → [x x] (from λ.x x)
[x] = [x] → [x x] (from x x)

Ok, onto the unification algorithm, described in the following manner:

Apart from the use of the word “identifier”, this looks easy enough. (Apparantly the author uses “identifier” since he first assigns a name such as 1⃣  to a term like [λx.x x] – I guess these boxed numbers are identifiers...)

Ok, so our stack of constraints is

{[λx.x x] = [x] → [x x], [x] = [x] → [x x]}

and our set of substitutions is empty. The first constraint can simply be added to the set of substitutions, which is now

{[λx.x x] ↦ [x] → [x x]}

We then replace each occurrence of [λx.x x] with [x] → [x x], but there are none, so our job in this step is done.

In the next step, the remaining constraint gets the same treatment: we simply add it to the set of substitutions, which then becomes

{[λx.x x] ↦ [x] → [x x], [x] ↦ [x] → [x x]}

But our job in this step is not done, we also need to recursively update all occurrences of [x] with [x] → [x x], so we get

{[λx.x x] ↦ [x] → [x x], [x] → [x x] ↦ [x] → [x x]}

Doing this again gives us

{[λx.x x] ↦ [x] → [x x], [x] → [x x] → [x x] ↦ [x] → [x x]}

… and so on, never terminating.

Is this understanding of the problem the “occurs check” solves correct? Is this what would have happened in a type inference algorithm such as Hindley-Milner if there wasn't an explicit occurs check?


texts: What is the computational complexity of sin and cos for floating point inputs?

texts:
What is the computational complexity of the problem

INPUT: $\;\;\;$ integers $x$ and $y \:$ (both in binary)

OUTPUT:

rational approximations to $\: \sin\hspace{-0.03 in}\left(x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y}\hspace{-0.02 in}\right) \:$ and $\: \cos\hspace{-0.03 in}\left(x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y}\hspace{-0.02 in}\right)$

whose absolute errors are each less than $1/\hspace{-0.04 in}\left(2^{\hspace{.02 in}\operatorname{length}(x)}\hspace{-0.05 in}\right)$

?

One could just expand $\: x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y} \:$, $\:$ but that would use at least $\:\left|\hspace{.03 in}y\right|\:$ bits of space.

(I believe most work on the complexity of such functions

only considers their restrictions to compact intervals.)


texts: Are certain problem instances more central than others? Or, what would Martian mathematics look like?

texts:
Motivation: One thing I've wondered about is whether mathematical concepts and problems are what they are simply because of human choices and history, or whether there are certain concepts and problems that are intrinsically important. The problem stated below attempts to crystallize this by asking about circuits that can solve some range of problem instances of some NP problem, and whether they all focus on the same group of instances.

Math: Let $L$ be a fixed language, and $d$ some fixed integer, and let $L_d$ be the subset of $L$ consisting of words of length bounded by $d$. Fix $\epsilon,k$ and consider the set $C$ of circuits of at most $k$ gates which correctly classify at least $\epsilon T$ of all words of length $\leq d$ as in or out of $L_d$, where $T$ is the total number of all words of length $d$ in the alphabet of $L$. I am interested in questions like, for a given word $s$, what is the expected number of circuits in $C$ that correctly classify $s$? What about conditional on there being at least one such circuit? What is the variance? What is the dependence on the various parameters $L,d,k,\epsilon$?

I suspect this kind of question is difficult to answer, but are there any relevant heuristics or conjectures? Can anything be said conditional on standard assumptions?

Edit: The connection between the two parts is supposed to be the following: one of the things mathematicians try to do is create good algorithms for solving problems (I think a lot can be boiled down to this, ultimately), where "good" is some combination of effective and feasible. If all the good algorithms concentrate on the same collection of problem instances, then we might expect that any mathematicians (like the titular Martians) would wind up being able to solve the same kinds of problems. On the other hand, if the distribution is more even, it might just be a matter of taste which instances to focus on. I would also be interested in anyone who has a better idea of what formal problems could capture some of the question in the motivation.


texts: Are there any implementations of a graph crossing algorithm?

texts:
This is much more focused version of this question:

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

Computing the graph-crossing number $cr(G)$ for a simple graph is known to be NP-complete. A quick literature review shows some suggested algorithms for computing if $cr(G)<k$. Are they any active implementations available?

Already checked: SAGE, CGAL_Boost, networkx, graph_tool


texts: Structural normalization algorithm for the simply typed lambda calculus

texts:
I would like to know if there is a (piecewise) structural normalization algorithm for the simply typed lambda calculus. By structural I mean a recursive function that only calls itself on subterms of its argument.
Suppose $T$ is an inductive type of terms, then it doesn't seem like there should be any way to define such a function $\text{nf} :T\to T$ directly, so what I want to know is whether one could define an intermediate inductive type $E$ and structural functions $p : T\to E$ and $r:E\to T$ so that $r\circ p:T\to T$ is the normalization function.
The motivation for this is that proving termination is immediate from the well-foundedness of the inductive types.
Are there any other references or implementations that address this question?


texts: Postselection in geometric complexity theory

texts:
Context: As I understand, in geometric complexity theory, the existence of obstructions serves as a proof-certificate, so to speak, for the nonexistence of an efficient computational circuit for the explicit hard function in the lower bound problem under consideration. Now there are some other assumptions for obstructions that they must be short, easy to verify and easy to construct.

Question: My question is that say I have a problem that I conjecture to be solvable in polynomial time. Then how can I show that there exist no obstruction for this problem, i.e. if no obstructions exist then the problem can be computed efficiently and it is indeed in polynomial time.

Approach: I think, and I may be wrong in this assertion, that showing no obstructions exist can be equivalent to standard reduction of NP problems to other problems whose complexity is yet unknown, in the proof that they themselves are in NP. So then in that case one can, if possible, show that obstructions exist as one tries to reduce an NP problem to the problem under consideration, that way, the reduction is intractable. Also what role does postselection play in all of this? Is it possible to simply postselect on the nonexistence of obstructions? Thanks and pardon the lack of precise statements in my approach and questions.

Just an another example, consider a problem X that we know to be in P. Now let's say we didn't know about that problem being solvable in polynomial time, then is it possible, that one can make the following assertion:

Since no obstructions exist in the computation of X we can say that it is in the class P

From there on, the problem is the easy (computationally) discovery of those obstructions, if even one exists, would show that X is not in polynomial time. However going the other way, i.e. finding that no obstructions exist is a difficult task.


texts: Language/type system closest to Haskell without general recursion

texts:
I've implemented a completely functional DSL, and now I'd like to reason about it.  It would be helpful to be able to compare it to existing languages.

The type system is parametric polymorphic with higher order functions but no dependent types.  The only recursion allowed is structural recursion in the form of a fold over an inductively defined type (including natural numbers).

The way I see it, the language shares its turing-incompleteness and form of recursion with Coq, but shares parametric polymorphism with Haskell.  Is there a more exact comparison to be made?  In particular, I was wondering if System F can be pared down to only support structural recursion, and what that would look like.

Thanks!


texts: Effect of serial repetition on soundness of a PCP, and what is special with 1/2?

texts:
As far as I know, following operations convert a $PCP_{1,s}[O(\log n),O(1)]$ , to a  $PCP_{1,s’}[O(\log n),O(1)]$, with following $s’$ :

By constant number of applications of serial repetition: can get every constant s’>=1/2;
By constant number of applications of parallel repetition: can get every constant s’>0;
By $\theta(\log n)$ number of applications of Dinur’s gap amplification transformation: can get some constant $s’\geq1/2$; (see “Gap Amplification Fails Below 1/2”)

My questions:

Could you please correct me if I have made any mistakes?
What is special with ½ in serial repetition or Dinur’s transformation? why not another constant, like 1/3 or else?
Are such a results true for PCPs with imperfect completeness?

remark:
with $PCP_{c,s}$, I mean PCP with completeness c and soundness error s.


texts: Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?

texts:
Let the variables be $x_1 , x_2 , x_3 ... x_n$.  The distance between two variables is defined as $d(x_a , x_b) = |a-b|$.  The distance between two literals is the distance between the corresponding two variables.

Suppose I have a 3-SAT instance such that for every clause $(x_a , x_b, x_c)$ we have $d(x_a , x_b) \leq N \wedge d(x_a , x_c) \leq N \wedge d(x_b , x_c) \leq N$ for some fixed value $N$.

Conceptually you can picture this as all the literals being physically on a line and all the clauses are incapable of reaching beyond a certain length for physical reasons.

Given this constraint are there any hard instances of 3-SAT? How small can I make the neighborhood and still find hard instances? What if I allow a few clauses to violate the constraint?

By hard I mean a heuristic solver would fall back on the worst case.


texts: Parameterized Complexity of Minimum Type Selection

texts:
Consider the following problem that I call »Minimum Type Selection«:

Input: $k$ sets of bit vectors, each of length $n$ and a number $l$.
Question: Is it possible to pick exactly one bit vector from each of the $k$ sets such that these $k$ bit vectors composed row-wise as a matrix contain at most $l$ distinct columns.

I was able to show that this problem is NP-complete. I now wonder about the parameterized complexity where $k$ is the parameter. For fixed $k$, the problem is trivially in P, implying that the parameterized problem is in XP. What, however, about FPT? Do you have any ideas?


texts: Model of homotopy type theory where propositional & judgmental equality coincide for closed terms

texts:
In intensional Martin-Löf type theory we can prove the metatheorem that two closed terms are propositionally equal iff they are judgmentally equal.
Is there a non-empty model of homotopy type theory where this metatheorem holds?


texts:
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$. We also know that $\mathsf{polyL} \neq \mathsf{P}$ because the latter has complete problems under logarithmic space many-one reductions while the former does not (due to the space hierarchy theorem). In order to understand the relationship between $\mathsf{polyL}$ and $\mathsf{P}$, it may help to first understand the relationship between $\mathsf{L}^2$ and $\mathsf{P}$.

What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

What about the stronger $\mathsf{L}^{k} \subseteq \mathsf{P}$ for $k>2$, or the weaker $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ for $\epsilon > 0$?


texts: Robustness to non-uniform randomness vs. one-sidedness

texts:
Consider any problem where, fixing two (disjoint) subsets $\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$ of the input space, the goal is to obtain a randomized algorithm $D$ which, given a uniformly random bit string $r$, and on input $x\in \{0,1\}^n$, with probability at least $2/3$ over $r$,

outputs $\mathsf{yes}$ if $x\in\mathcal{Y}$;
outputs $\mathsf{no}$ if $x\in\mathcal{N}$.

Call any such $D$ a decider for $(\mathcal{Y},\mathcal{N})$.

(A natural example is property testing.) If further the first item (completeness) holds with probability one, then $D$ is one-sided.

Clearly, if $D$ is one-sided, then (1) holds even if $r$ comes from an arbitrary distribution, possibly chosen adversarially, instead of being uniform.

Let us say a decider for $(\mathcal{Y},\mathcal{N})$ is robust to bad coins if completeness (first item) degrades gracefully as the distribution $R$ of $r$ gets far from uniform. For instance, the probability that completeness holds only goes down linearly, as $2/3-c\operatorname{d_{TV}}(R,U)$ for some $c\in[0,1)$ .

My question is then:

  Is the class of one-sided deciders a strict subset of deciders robust to bad coins? And has this been studied in some form?

(Also, the definition of robustness is quite open.. I went with total variation, but maybe something like min-entropy of $R$ makes more sense?)


texts: Fixed parameter tractable Integer Programming and $FPP$

texts:
Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $NC$? (Update: It is not known)
 What are some examples of problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $P$ complete and problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $NC$? Is there a theory behind such classification? (resolved by Ronald de Haan).


texts: Is subtractive dithering the optimal algorithm for sending a real number using one bit?

texts:
Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner.
We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,1/2]$ that they can use for choosing $X$ and estimating $x$.
Subtractive dithering is an algorithm that sends
$$X =
\begin{cases}
1 & \mbox{if $x+h\ge 1/2$}\\
0 & \mbox{otherwise}
\end{cases}.
$$
In turn, the subtractive receiver estimated $x$ as $\widehat x=X-h$.
It is possible to show that $\widehat x\sim U[x-1/2,x+1/2]$, and thus $\mbox{Var}[\widehat x]=1/12$.

Is there an unbiased algorithm (i.e., with $\mathbb E[\widehat x]=x$) that uses a single bit and has a variance lower than $1/12$ for all $x\in[0,1]$?


texts:
Degree Constrained Minimum Spanning Tree is an NP-hard problem. It differs from Minimum Spanning Tree in that, degree of every vertex should be $\leq$ some degree constrained. This is a well studied problem. I'm trying to recreate experimentation results described in several papers. In addition to check their algorithms against Random graphs, these papers also use modified instances of random graphs to fool known algorithms.

My question is, Where can I find data sets for the following types of graphs :

Misleading Hard Graphs (M-Graphs)1
Structured Hard Graphs (SHRD)2
Random Hard Graphs (R)3
Coordinate Graphs (CRD)4
Symmetric Graphs (SYM)5

Alternatively, is there any package/tools that can generate them?

1. Knowles and Corne, "A New Evolutionary Approach to the Degree Constrained Minimum Spanning Tree Problem"

2. Krishnamoorthy, "Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree"

3. Boldon-Deo-Kumar, "Minimum Weight Degree Constrained Spanning Tree Problem"

4. Volgenant, "A Lagragian Approach to the Degree Constrained Minimum Spanning Tree Problem"

5. Krishnamoorthy, "Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree"


texts: How to find a proper probabilistic formulation given the objective function terms?

texts:
I want to pose a problem as maximisation of MAP probability $P(X,Y|Z)$ and I know which terms I want to have in the objective function. However, I am unable to combine these terms to form a joint probability distribution $P(X,Y,Z)\sim P(X,Y|Z)$. More specifically, $X=x_1...x_t$ and $Y=y_1...y_t$ are hidden variables and $Z=z_1...z_t$ are observations and I want the following terms to appear in the objective function:

$P(z_t|x_t,y_t)$

$P(y_t|y_{t-1})$

$P(x_t|x_{t-1},y_{t-1})$

$P(x_t,y_t)$ or $P(y_t|x_t)$ or $P(x_t|y_t)$ (as $P(x_t)$ and $P(y_t)$ are uniform)

How does one come about deriving the Bayesian network that would describe a probability distribution with these terms? Is there possibly a BN that is specifically suited for this scenario? How should one in general formulate such problems?

Thank you.


texts: Short supersequence for many permutations

texts:
A shortest supersequence $c_n$ of all permutations on $[n]$ has length $\Theta(n^2)$: see this question on Mathoverflow. What if we force $c_n$ to be short? How many permutations can it cover?

Let's define $\#_n(s)$ to be the number of permutations on $[n]$ that are subsequences of $s$. Let $C$ denote an algorithm that reads an integer $n$ and produces a sequence of integers from $[n]$, and has a runtime bounded by $O(n\cdot{\rm polylog}(n))$. The function $f_C(n)=\#_n C(n)$ says how good algorithm $C$ is. Let $f = \sup_C f_C$, with functions ordered by their asymptotic behavior. What is the asymptotic behavior of $f$?

Has this or a similar problem been studied?


texts: Biconnected components of a directed graph?

texts: I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.


texts: Smallest set not included in a collection of sets

texts: Given as input an integer $n$ and a set $S$ of sets of elements of $\{1, ..., n\}$, what is the complexity of finding a set $T$ of elements of $\{1, ..., n\}$ such that $T$ has minimal cardinality and $T$ is included in none of the sets of $S$?


texts: Example of something that’s different for generic and random oracles?

texts:
Let $G$ be a generic oracle in the sense of Cohen / Baire category.
Let $R$ be a random oracle.

Are there complexity classes A and B with
$$\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R$$
or the other way around,
$$\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?}$$

The question was inspired by a comment by Scott Aaronson.


texts: Find index set partition that has large projections

texts:
I have a multiset $S$ of $n$-bit strings.  Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$.  I want to find a partition of $\{1,2,\dots,n\}$ such that the projections onto these index sets all have large multiplicities, but let me explain what I mean by that.

If $I$ is a subset of $\{1,2,\dots,n\}$ (i.e., a set of indices), then let $\rho_I(s)$ denote the projection of string $s$ onto the indices in $I$.  In other words, if $I=\{i_1,i_2,\dots,i_k\}$, then $\rho_I(s)$ is the $k$-bit string $s_{i_1} \, s_{i_2} \, \cdots \, s_{i_k}$.  Also, let $\rho_I(S)$ denote the multiset $\{\rho_I(s) : s \in S\}$.  For instance, if $S=\{01,01,11\}$ and $I=\{2\}$, then $\rho_I(S)=\{1,1,1\}$.

We'll say that an index set $I$ is good if every element $t$ of $T=\rho_I(S)$ has multiplicity at least $m$ in $T$.  In other words, every string in $\rho_I(S)$ has to appear at least $m$ times in $\rho_I(S)$.  Here $m$ is some threshold fixed in advance, e.g., $m=100$.

Suppose we partition the set $\{1,2,\dots,n\}$ into three disjoint sets: $I_1 \cup I_2 \cup I_3 = \{1,2,\dots,n\}$, where $I_1,I_2,I_3$ are mutually disjoint.  We'll say that this partition is good if $I_1$ is good, $I_2$ is good, and $I_3$ is good (in other words, projecting onto each index set yields a multiset where all elements have multiplicity at least $m$).

I want to find an algorithm to compute whether there exists any good partition (and if yes, to output an example of a good partition), given $S$ and $m$.  Can anyone suggest a good algorithm for this?  Or, if this is intractable, I would be satisfied with good heuristics or approximation algorithms.  Or, is it easier if I want to partition $\{1,\dots,n\}$ into two sets $I_1,I_2$?  Does anyone know of any algorithmic techniques that might be relevant, or any connection to problems that have been studied in the literature?

This arises from a practical application I have, where (intuitively) the requirement that all multiplicities of the reduced set be at least $m$ corresponds to a sort of privacy/anonymity/plausible deniability property, and larger values of $m$ correspond to greater anonymity.  Sample parameters for my problem might be something like: $S$ is a multiset with thousands or tens of thousands of strings (counting multiplicity) and hundreds or thousands of unique strings (not counting multiplicity); $m$ is maybe 100 or so; $n$ is maybe 20-200 or so.  References to research papers would be fine.  I hope this kind of question is suitable for this site; if not, let me know and I'd be happy to flag it to have it migrated over to CS.StackExchange.


texts: Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?


texts:
In cost-sensitive classification,
we have a confusion (or cost) matrix
$C$, where $C(i,j)$ is the cost incurred
for predicting label $i$ when nature
specifies $j$. The costs are non-negative,
but no other restriction (such as symmetry) need be imposed. In the classic setting
(PAC and its multiclass generalization),
$C(i,j)=1[i\neq j]$.
The notion of Bayes-consistency carries
over naturally to the cost-sensitive setting. For any joint distribution
$P$
over the instances
$\mathcal{X}$
and labels
$\mathcal{Y}$,
we define the risk of a predictor
$f:\mathcal{X}\to \mathcal{Y}$
as
$$
R(f)=
\mathbb{E}_{(X,Y)\sim P}
C(f(X),Y).
$$
Letting $f^*$ be a minimizer of
$R(\cdot)$ over all measurable $f$,
we define the Bayes-optimal risk as
$R^*:=R(f^*)$.
Question: What is known about Bayes-consistent classification in the cost-sensitive setting? For example,
when $\mathcal{X}$ is a metric space
and $C(i,j)=1[i\neq j]$, various nearest-neighbor methods are known to be strongly Bayes-consistent. Is anything known about other cost matrices?


texts: Is there a survey of the field of quantum automata?

texts:
I'm looking for a survey paper of the important concepts in the field of Quantum Automata. I've found Quantum Automata Theory -- A Review
 by Hirvensalo, but it sounds too succinct to grasp the topic.
Is there a quite comprehensive survey on the topic of Quantum Automata?

Also, could you point me to the essential literature about the topic?


texts: A decision problem related to the problem of counting Hamiltonian cycles

texts: Define a decision problem H as follows. The input of H is a pair (G1,G2) of graphs, and the problem is to verify whether the number of Hamiltonian cycles in G1 is greater than the number of Hamiltonian cycles in G2. Is there a known complexity class C such that H is in C and H is C-hard under many-one reductions? Clearly H is in P^{#P}, and it is possible to prove that H is PP-hard under many-one reductions. But is H in PP? Or is H hard for the class P^{#P} under many-one reductions?


texts: Cover Time of Random Walks with Backtracking on Directed Graphs

texts:
The cover time of a random walk on an undirected graph is the expected time for the walk to visit all vertices of the graph (starting from an arbitrary vertex). It is well known that any connected graph with $n$ vertices has cover time $O(n^3)$.
I'm looking for a similar result, perhaps with a much worse upper bound, for random walks on directed graphs that are connected but not necessarily strongly connected. To guarantee that the walk will be able to visit every vertex without getting stuck in a strongly connected component, we assume the following features.

That the walk starts at a node $v$ that can reach any other vertex in the graph. So we assume that such a vertex exists.
We add a stack to the walk. More precisely, the walk starts at a vertex $v$ and $v$ is the only vertex at the stack. At each time step, given that $v$ is at the top of the stack, the walk either moves to a neighbor $u$ of $v$, and $u$ is added to the top of the stack, or the walk pops $v$ from the top of the stack and moves to the vertex just below it in the stack (a backtrack move). If the stack has at least two vertices, then moving to a neighbour $u$ happens with probability $1/2\delta(v)$, while backtracking happens with probability $1/2$. If $v$ is the only vertex in the stack, then moving to a neighbor $u$ happens with probability $1/\delta(v)$ (no backtracking is allowed).

Questions:

What is the correct name for the type of random walk described above. I'm having a hard time finding references about it, but I'm sure it has been studied somewhere.
Is there any non-trivial upper bound on the cover time for such a walk? In particular, is there an upper bound for directed graphs with constant (or bounded) out-degree graphs?

Obs: I have found some material on random walks on strongly connected graphs (which do not need a stack). There are examples of such graphs with exponential cover time (see this question). But the examples I found have some vertex with very large maximum degree (linear in $n$). Additionally, I have the impression that the addition of a stack may help, reducing the time in the bounded out-degree case (I may be wrong here).


texts:
Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio?

Any research that compares algorithms using smoothed analysis would be interesting (e.g. algorithms that have the same worst-case time complexity).


texts: List of TCS conferences along with important dates

texts: I saw that there is a post with a List of TCS conferences. However, this does not list important dates like conference date, submission deadline etc. Is there any post or website which maintains these information and also keeps it up-to-date?


texts: Is every busy beaver strictly monotonic asymptotically?

texts:
To be specific, let me first define the busy beaver function BB(n)= maximum number of 1's that can be printed on the tape (i.e., the maximum score) by a standard n-state, 2-symbol (0 and 1) Turing machine before halt, starting with an all-zero tape.

My first question maybe trivial: is it true that BB(n+1)>BB(n) for all n?

The claim is true if we define the busy beaver by BB'(n)= maximum number of shifts made by the machine before halt. (This is because we can always keep everything else the same, and change the last shift made by BB'(n), say $\{ 0{q}_{i}1RH\}$, to $\{ 0{q}_{i}1R{q}_{n+1}\}$ and $\{1{q}_{n+1}1RH\}$ to arrive at an (n+1)-state turing machine which has exactly one more shift than BB'(n) before halt.)

Can we show that the strict inequality holds too if we measure by scores?

What about the general case? Is every busy beaver strictly monotonic, for large enough n?


texts:
I have  a large number of long strings, and I need to search them for a given list of words  as fast as reasonably possible. (Neither the strings nor the words are constants)
I learned that I can preprocess the strings that I'm going to be searching for my words by building a suffix array and  an lcp array, and that I should be able to make the searches faster by doing so.
I was wondering, however, if I could preprocess the wordlist in some way as well. It is quite possible that the words will have common parts. I would like to build something like a "word genealogy tree" (or another structure that would achieve the same effect ) where the  substring that can be found in a family of words would be at the top and which would then branch down (for both the prefixes and the suffixes of the ancestor) as the descendants would go.
I imagine that this would allow me to discard whole branches or trees quickly if an ancestral node failed to match.
Could you please direct me to a suitable strategy that would help me achieve my goal (in this or any other reasonably efficient way)?
Note: I can't really make use of much existing code (can make use of ideas, though). I'm pretty much limited to the standard c library.


texts: About the position of side conditions in an inference rule

texts:
Sometimes I see people put side conditions above the inference line as if they were premises of an inference rule.  This feels strange.  My understanding (which may be wrong) is that a side condition belongs to the meta-theory, not to the object-theory: an object-proof of a side condition should not be required and may even not be possible.  So what is the motivation of doing this?  For saving space or for some other deeper reason?

$Update$:

I am no longer quite sure whether a side condition belongs to the meta-theory.  But at least it is outside the object-theory the inference rules describe,that is, the truth of a side condition cannot be derived using the inference rules.

$Update^2$:

Take as an example the rule for typing variables from the simply-typed $\lambda$-calculus.  $(x : T) \in \Gamma$ is a side condition that tests whether the variable $x$ of type $T$ is in the typing context $\Gamma$.  In some presentations, the side condition is put aside, leaving the premises empty to indicate that it is an axiom, though conditional:

$$\frac{}{\Gamma \vdash x : T} (x : T) \in \Gamma$$

while in others, it is put above as if it were a premise:

$$\frac{(x : T) \in \Gamma}{\Gamma \vdash x : T}$$


texts: Is abelian group isomorphism in $\mathsf{AC^0}$?

texts:
An $O(n^2)$ running time algorithm for abelian group isomorphism is easy to see. Later working on this problem in 2003 Vikas improve the result from $O(n^2)$ running time  to $O(n \log n)$. In 2007, Kavitha showed that abelian group isomorphism can be done in linear time i.e. $O(n)$ time.

I know that abelian group isomorphism when groups are given by table representation is in $\mathsf{TC^0}$. Is there any research paper or article which shows that it is in $\mathsf{AC^0}$? I tried to google but get only the result that it is in $\mathsf{TC^0}$.

  Question : Is abelian group isomorphism ( groups given in table representation ) in $\mathsf{AC^0}$


texts: Is analogy between database and probability concepts legitimate?

texts:
In Relational Databases: Tutorial for Statisticians Joe R. Hill casts probability view onto database theory. In Table 1 the author summarized the parallels between the two disciplines, describing relation structure together with three relational algebra operations in probabilistic terms.

I seek clarification on 2 items:

What probability distribution corresponds to empty relation? An intermediate step in Dr.Hill's paper is indicator function -- which is standard trick of thinking about relations in functional terms. My understanding is that the author generalizes {0,1} valued indicator function to probability distribution. There, the 1 valued tuples are assigned not vanishing discrete probabilities (assuming discrete domain), while all the tuples not belonging to relation inherit their 0 indicator function value as probability. My objection is that this would work for nonempty sets of tuples only.
Missing from the parallels is Relational Algebra union operation -- what probability concept is it analogous to? If we take average, then it would fail to honor associativity law.

Edit: Resolved confusion with transformation constraint. Consider a relation

x y
---
1 a
2 a
3 b

honoring FD x->y. One can match it with joint distribution like this

\ |  1   2   3  |
--+-------------+----
a | 1/4 1/4  0  | 1/2
b |  0   0  1/2 | 1/2
--+-------------+----
  | 1/4 1/4 1/2 |  1

Still the analogy is weak: there is well known interpretation of Functional dependencies in terms of entropy.


texts: Can we decide whether a permanent has a unique term?

texts:
Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)}$?

Remarks. One can of course replace the product with a sum, the problem stays the same.

If the matrix can have only 0/1 entries, then we get the Bipartite-UPM problem which is even in NC.

Edit: Deciding whether the smallest term is unique is in P as it is equivalent to the minimum weight matching problem, as pointed out by Neal Young in a (since then removed) comment.

Edit: Similar questions:

In an edge-weighted graph, is there a Hamiltonian-cycle with a unique weight?

If we have a CNF with weights assigned to every variable/satisfying assignmet, is there a unique weight satisfying assignment?

These are of course at least NP-hard. Are these problems equivalent to the original or are they harder?


texts: Quantum polynomial hierarchy vs counting hierarchy

texts:
First of all, I'm kinda surprised that I couldn't find any paper/article defining such hierarchy.

It can be defined as follows:

$\Delta_0^{\mathsf{BQP}}=\Sigma_0^{\mathsf{BQP}}=\Pi_0^{\mathsf{BQP}}=\Delta_1^{\mathsf{BQP}}\mathsf{=BQP}$

$\Delta_k^{\mathsf{BQP}}=\mathsf{BQP}^{\Sigma_{k-1}^{\mathsf{BQP}}}$

$\Sigma_k^{\mathsf{BQP}}=\mathsf{QMA}^{\Sigma_{k-1}^{\mathsf{BQP}}}$

$\Pi_k^{\mathsf{BQP}}=\mathsf{coQMA}^{\Sigma_{k-1}^{\mathsf{BQP}}}$

Is this whole hierarchy known to be contained in some finite level of counting hierarchy like $\mathsf{PH}$ (which is contained in the second level of counting hierarchy, $\mathsf{P^{PP}}$)? If not, are there some expectations on it?


texts: Two color Graph Coloring problem with solution involving BFS

texts:
The question appears in Cormen's Introduction to Algorithms.
There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n+r)-time algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.

One of the solutions I found said the following -
Create a graph G where each vertex represents a wrestler and each edge represents a rivalry. The graph will contain n vertices and r edges. Perform as many BFS's as needed to visit all vertices. Assign all wrestlers whose distance is even to be good guys and all wrestlers whose distance is odd to be bad guys. Then check each edge to verify that it goes between a good guy and a bad guy. This solution would take O(n + r) time for the BFS, O(n) time to designate each wrestler as a good guy or bad guy, and O(r) time to check edges, which is O(n + r) time overall.

Sure this solution works in all the cases I could come up with, and determines whether it is possible to color the graph in this manner or not. But I wish to know how do we formally verify the correctness of this solution? That is to say that, how do we determine if this solution exhausts all possible ways of coloring a graph in the manner asked of in the question, so as to declare whether or not it is possible to divide the graph in such a way.


texts: Computational complexity of polynomial interpolation with k non-zero terms

texts:
I am attempting to find a complexity for computing the order polynomial of partially ordered sets on a special family, and have come across the following problem. Assume we have the following values from a polynomial:
$P(0)...P(n-k)=0$ and $P(n-k+1)...P(n)=y_{n-k+1}...y_n$: what is the complexity of polynomial interpolation in this environment?

Looking at the Lagrange polynomials, the first n+1-k become 0, and the k last follow a simple form:

$L_i = \frac{\Gamma(x+1)\Gamma(i-n)y_i}{\Gamma(x-n)\Gamma(i+1)(x-i)}$

This suggests to me the coefficients for each x should have some nice form. However I'm a bit lost at this point as to the complexity of computing the $L_i$ (which we need k of), perhaps there is a better method?


texts: Exact number of comparisons to compute the median

texts:
Volume III of Knuth's The Art of Computer Programming (chapter 5, verse 3.2) includes the following table listing the exact minimum number of comparisons required to select the $t$th smallest element from an unsorted set of size $n$, for all $1\le t \le n\le 10$.  This table, along with the well-known closed-form expressions $V_1(n) = n-1$ and $V_2(n) = n - 2 + \lceil n/2 \rceil$, represents most of the state of the art as of 1976.

Have any more exact values of $V_t(n)$ been computed in the last 36 years?  I'm particularly interested in exact values of $M(n) = V_{\lceil n/2 \rceil}(n)$, the minimum number of comparisons required to compute the median.

As @MarkusBläser points out, Knuth's table seems to already incorporate more recent results from Bill Gasarch, Wayne Kelly, and Bill Pugh (Finding the ith largest of n for small i,n. SIGACT News 27(2):88-96, 1996.)


texts: (N)DFA with same initial/accepting state(s)

texts:
What is known about the class of languages recognized by finite automata having the same initial and accepting state?  This is a proper subset of the regular languages (since every such language contains the empty string), but how weak is it?  Is there a simple algebraic characterization?

Ditto for languages recognized by non-deterministic automata having the same set of initial and accepting states.


texts: Real representation versus communication complexity

texts: Suppose that Alice and Bob communicate to compute a function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$. Does the minimal degree of a real polynomial/rational representation of $f$ play a role for upper and/or lower bounds on the deterministic, non-deterministic, randomized or quantum communication complexity of computing $f$?


texts: Proving running time upper bounds for algorithms in dependent type theory

texts:
Proof assistants are a valuable tool for verifying
the correctness of proofs of mathematical theorems.

When dealing with proofs of correctness of algorithms,
one is not only interested on showing that the algorithm
indeed works correctly, but also on showing some upper
bound on the execution of the algorithm.

Can proof assistants based on dependent type theory be
used in a natural way to prove upper bounds on the
running time of algorithms (besides of course of
proving their correctness)? What is the standard approach
to do so?

If such assistants are not appropriate, is there some
other kind of proof assistant that can do the job?

Obs: When I say time, I mean the complexity theorist notion
of time, in the sense of number of steps in an idealized RAM machine.
I don't care about formalization of actual hardware and
physical time. Therefore, although Neel Krishnaswami is interesting,
I'm not accepting it because it is far more complicated than what
I'm looking for.


texts:
How could you combine two mealy machines, the first one $M_1$  has as input $\sum_{1}^*$ and as output $\sum_{2}^*$,
the second machine $M_2$ uses the output $\sum_{2}^*$ as the input and outputs $\sum_{3}^*$.
So what is the resulting $M_2◦M_1(w)$ machine, where $w$ is a word from $\sum_{1}^*$?


texts:
Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded graphs?

Update 10/24
It seems to follow Grohe's results that formula that is FPT to test on bounded-treewidth graphs is FPT to test on minor excluded graphs. Now the question is -- how does it relate to tractability of counting satisfying assignments of such formula?

 The above statement is false. MSOL is FPT on bounded tree-width graphs, however 3-colorability is NP-complete on planar graphs which are minor-excluded.


texts:
Say we have two chunks of data $X$ and $Y$, which may be of different sizes, is there a non-trivial function $hash$, and operation $*$, such that:

$$hash(X+Y) = hash(X) * hash(Y)$$

...where $+$ is concatenation, and $*$ is associative (but not necessarily commutative)?

Clearly $hash$ being the identity function, with $*:=+$, satisfies this. However, what if we put usual constraints on $hash$ -- say, its output is always $n$-bits, where $n$ is small -- and $*$ has to be reasonably economical?

My intuition is saying that no such $(hash,*)$ exists, because:

In the general case, there would be a loss of entropy in hashing and I don't believe this can be deterministic.
Merkle trees are a thing, which implies there's no better option.

(n.b., I realise "linear", in the linear algebra sense, isn't the correct word to use here, but for want of a better term!)


texts: Differential Privacy and Randomized Responses for Counting Queries

texts:
I'm trying to understand a basic randomized response mechanism for differential privacy (concrete definition not relevant for the question), but I have some trouble understanding the last step in the calculations.

The randomized response mechanism works as follows:

Let's call $q(x) = \frac{1}{n} \sum_{i=1}^{n}q(x_i)$ a counting query for a database $x$ with $n$ entries $x_i$.
Each $q(x_i)$ maps into ${0,1}$.

Now define a mechanism $M$ that works as follows:

$M(x_1, \dots, x_n) = (y_1, \dots, y_n)$, where each $y_i$ is computed as follows:

$ y_i =
\begin{array}{cc}
  \{ &
    \begin{array}{cc}
      q(x_i) & \textrm{with probability } \frac{1+\epsilon}{2} \\
      \neg q(x_i) & \textrm{with probability } \frac{1-\epsilon}{2}
    \end{array}
\end{array}
$

Now we can use the value of $M$ to estimate the value of the counting query $q(x)$.

The expected value of $y_i$ is $\mathbb{E}[y_i] = \epsilon q(x_i) + \frac{1-\epsilon}{2}$.

Now the bit that I do not understand

By Chernoff bound,

$$ \left| \frac{1}{n}\sum_i\frac{1}{\epsilon} \cdot (y_i - \frac{(1-\epsilon)}{2}) - q(x) \right| \lt \mathcal{O}\left(\frac{1}{\sqrt{n}\cdot\epsilon}\right) $$

I assume they used the additive Chernoff bound $ \Pr[X \gt \mu + \epsilon] \leq e^{-2n\epsilon^2}$.

It's not clear to me how they got the last part, since it's also not exactly clear to me how they apply the Chernoff bound.
In particular how they use the expected value of $y_i$ in combination with $x_i$ and the bound.

Could somebody maybe give me a more detailed calculation of how the last statement was calculated?

Thanks in advance!


texts: Lee metric, Gilbert-Varshamov and Hamming bounds for larger relative distance ranges

texts:
Gardy and Sole provide a Gilbert-Varshamov lower bound and a Hamming upper bound for the Lee metric when the distance between codewords is smaller than the length of the code (captured by $r = \delta n$ where $0 \le \delta \le 0.37$ in the paper).

Is there a reference which provides the corresponding lower/upper bound for ranges above this? At least is there a lower bound (preferably as powerful as the Gilbert-Varshamov bound) and a upper bound(preferably tighter than the Hamming bound) for the case $\frac{2 \delta n + 1}{n} = \frac{n + 1}{n}$, that is $\delta = \frac{1}{2}$?

This is a smaller version of the cross-posting from MO.


texts:
A "sharing graph" is a representation of a $\lambda$-term that modifies an abstract syntax tree by adding edges connecting each variable use to the place where that variable is bound.  They are used in Lamping's "optimal" reduction algorithm to do $\beta$-reduction by local edits, not duplicating any terms until necessary.  My understanding is that this works very directly for linear $\lambda$-calculus (and is more or less a different representation of proof-nets for linear logic with $\multimap$ only), but in the nonlinear case one has to introduce (as with proof-nets) explicit multiplexing (i.e. contraction) nodes and some kind of "level marker" (i.e. the linear $!$ modality).  The initial encoding of a $\lambda$-term as a sharing graph corresponds to the embedding of intuitionistic logic into linear logic as $(P\to Q) = (!P\multimap Q)$, and once the optimal reduction is complete, one then has to perform a "read-back" to obtain an ordinary $\lambda$-term in normal form since not every sharing graph is itself the translation of any $\lambda$-term.  (Please correct me if I said anything wrong.)

Now, linear logic has categorical semantics, depending on the kind of linear logic under consideration.  Intuitionistic linear logic corresponds to symmetric monoidal categories (or multicategories), classical linear logic to linearly distributive categories (or polycategories),  the modality $!$ to a "Seely comonad", etc.  In particular, it seems to me that we could regard sharing graphs (qua proof nets) as the terms in some linear logic, with the rewrites of Lamping's algorithm as axioms, and thereby interpret sharing graphs modulo optimal rewrites into any monoidal category with the appropriate structure and axioms.

My question is whether there is any such monoidal category providing a "semantics of sharing graphs" that performs the read-back into $\lambda$-calculus.  In other words, is read-back defined "inductively" over the structure of sharing graphs in a sufficient sense that it can be characterized by their categorical universal property?  It feels as though some kind of Chu or Int construction might do the trick, perhaps applied to a presheaf model of HOAS, but I haven't been able to make anything come out.

I'm getting to the edge of my linguistic competence here, but I suspect that a related question would be whether Lamping's algorithm can be written in a "normalization by evaluation" style (e.g. if the category performing the read-back consisted only of normal forms).


texts: A balanced generalization of Hall’s theorem

texts:
Let $X$ and $Y$ be sets, and $\mathcal{B}$ be a partition of $X \times Y$. I would like to prove that there exists a distribution $\mathcal{D}$ over $X \times Y$ whose marginal is uniform over $X$, and such that the distribution over $\mathcal{B}$ induced by $\mathcal{D}$ has large entropy(the latter distribution is defined by assigning each $B∈\mathcal{B}$ the total probability mass of the elements of $B$ under $\mathcal{D}$). We can use the following condition:

Consider the bipartite graph $G$ whose sides are $X$ and $\mathcal{B}$, such that for each $(x,y) \in B$ there is an edge $(x,B)$ in $G$ (multiple edges possible). Then, every set of $x$'s of size at least $\frac{3}{4}|X|$ has at least $\frac{1}{100}|B|$ neighbors in G.

I would appreciate it if someone could refer me to a relevant theorem. This question can be viewed in a sense as a generalization of Hall's theorem, where the above condition is a relaxation Hall's condition, and where instead of getting a perfect matching, we get a set of edges whose corresponding subgraph is roughly regular.

Background: The motivation for this questions comes from communication complexity. In the setting of communication complexity, two players, Alice and Bob, get inputs $x$ and $y$ respectively, and interact in order to compute some function $f(x,y)$. Here, each set $B \in \mathcal{B}$ consists of pairs $(x,y)$ that yield the same transcript of communication between Alice and Bob, and I would like to prove that under some condition, one can find a distribution over $X \times Y$ such that Alice gets a uniformly distributed input, and such that the entropy of the transcript under the distribution is large.


texts: How efficiently can one find small subcovers for integer intervals?

texts:
This question is inspired by one of my professors giving out

sequential lecture notes that have a significant amount of overlap :-).

What is known about the following problems?

Given a set of integer intervals whose union is an integer interval, find a subset

with the same union that minimizes the number of intervals in the subset.

Given a set of integer intervals whose union is an integer interval, find a subset with the

same union that minimizes the sum of the cardinalities of the intervals in the subset.


texts:
Given a graph G(V,E) and a vertex v, how do i find all the vertices that are reachable via simple paths ( no vertex on the path repeats) of length exactly k.

Powers of adjacency matrix gives the number of paths between vertices but it includes non simple paths.

Is this problem solvable in polynomial time ? If not are there any known approximation algorithms. Any pointers to literature would be great.


texts:
It's well known that the minimax sample complexity for estimating the bias $p$ of a coin to additive error $\epsilon$ with confidence $\delta$ is
$\Theta(\epsilon^{-2}\log(1/\delta))$. What if we know that $p$ lies in some specified range, say $[p_0-\eta,p_0+\eta]$ -- is the minimax sample complexity known in terms of $p_0$ and $\eta$? Note that $p_0=\eta=1/2$ recovers the general setting as a special case.


texts:
Given $n, k \in \mathbb{N}$, we create a set $S \subseteq \mathbb{Z}_m^k$ by treating it as an $n\times k$ grid and choosing each $S_{ij}$ by sampling from $\mathbb{Z}_m$, such that $P(S_{ij} = z) = p_z$. We'll define the occupant count $o$ to be the total number of non-zero elements from every vector, and we'll call the quantity $o/nk = 1 - \alpha$. We can think of $\alpha$ as the probability, if we were to probe our grid at random, that we would find a zero. I want to constrain my sets to some known $\alpha$ and then have $p_{z\neq 0} = p_{0\neq x\neq z}$. Clearly if $\forall x, y \in \mathbb{Z}_m, p_z = p_x$, this condition is met, but more generally, we can reason that

$\sum_{z \neq 0}p_z + \alpha$ = 1$

$\sum_{z \neq 0}p_z = (n - 1)p_z$

$(n - 1)p_z + \alpha = 1$

$p_z = \frac{1 - \alpha}{n-1}$

Then I can construct a graph $G$ where $V = S$ and the edge relation is defined as:

$E = \{ (x, y) \mid \langle x,y\rangle = 0 \}$

  What I want to know is if we choose uniformly $x, y \in S$, what is
  $P((x, y) \in E)$?

A question I'd be quite willing to hear answered as well is the case when $S = \mathbb{Z}_n^k$.

I suspect that this probability will rise with $n$'s compositeness where $k > n$. It'd be curious if you could compute the number.


texts: The relationship between degree of vertex and size of dominating set

texts: I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has degree $\ge n^k \,(k< 1)$, is it possible to bound the size of dominating set, i.e $O(n^k)$? Could anyone point me out any materials/papers/books related to this problem?


texts:
What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs?  Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am especially interested in inapproximability of 3-SAT.

Let 7/8+ε-3-SAT be 3-SAT with the promise that if 7/8+ε fraction of the clauses are satisfiable, then the instance is satisfiable.  What are the best known reductions of 3-SAT with $n$ clauses to 7/8+ε-3-SAT?  For example, is there a reduction using $O(n \log n)$ clauses? ($O(n)$ clauses is an open problem.)  A reduction in uniform quasilinear size NC?  What is the dependence on $ε$, including when $ε→0$? Is there a known linear size (dependent on $ε$) reduction of (1-ε)-3-SAT to 7/8+ε-3-SAT, and if not, do we have better bounds for (1-ε)-3-SAT?  Even a partial answer would be interesting.

Also, while it would perhaps make the question too broad, I should mention that another important issue here are the constant factors, which due to techniques like the long code are commonly infeasibly large.


texts: Computing parity of a permutation in a streaming-fashion way

texts:
I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of the permutation. The question I'm interested in how much memory a deterministic algorithm should use. Is there any randomized algorithm for the problem?

I know that computing number of inversions in one pass uses $\Theta(n)$ memory. The upper bound can be easily obtained with any BST. The lower bound is presented here: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622

Alas, the proof of the lower bound in the paper can not be extended to the parity case (or it's not so obvious to me).

Also I know that computing parity in a little space with random access to a permutation can be done in $O(n \log n)$ time and $O(\log^2 n)$ memory by deterministic algorithm or in $O(n \log n)$ time and $O(\log n)$ memory by randomized one. See http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256

The main idea is that the parity of a permutation can be computed by formula $sgn(\pi) = (-1)^{n - c}$, where $c$ is the number of cycles and $n$ is the size. The authors make the cycle decomposition of a permutation. So one can easily compute the number of cycles.

Does anybody know an effective algorithm or lower bound on memory for computing parity in the streaming model? Randomized algorithms better than random coin are interesting to me too.


texts:
Let $R(f)$ and $ER(f)$ be the minimum-size for unsat proofs of $f$ in Resolution and Extended Resolution respectively. What's the best bound we have on $D=\min_f (R(f)-ER(f))$ where $f$ belongs to a worst-case family of boolean formulae? Since no superpolynomial lower bounds are known on Extended Resolution, we don't have a good upper bound on $D$, so I'm interested in lower bounds on $D$.

Edit: Clarified question as per Kaveh's answer below


texts:
Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties :

$G'$ is connected. (property $p _1$: connected)
The vertices of $G'$ are divided into two disjoint subsets $S$ and $T$ ($S \cup T = V$).
No pair of nodes in $S$ are neighbors in $G'$. The same applies for $T$. (property $p _2$ bipartite). [Note that they can be neighbors in $G$ - but we then eliminate the edge between them when constructing $G'$]
The nodes in $S$ are degree limited. (property $p _3$ call it outdegree bounded)

The problem seems to be NP-Complete, but I found no solution so far.

Here are some of my observations:

essentially, we are looking for a connected subgraph $G'$ that contains a dominating set $S$ such that every node in $S$ in $G'$ is degree limited to $k$. [and we need to know $S$ too]. [and no pair of nodes in $S$ are neighbors in $G'$]
$G'$ with $p _1$ and $p _2$ is easily obtained with a rooted spanning tree algorithm + 2-coloring of tree.
$G'$ with $p _1$ and $p _3$ is easily obtained with a rooted spanning tree algorithm + every node in the tree points to its parent.
$G'$ with $p_2$ and $p_3$ is trivial, (note that we are looking for any subgraph with the required properties!)
A close problem to this is the bounded degree spanning tree problem [proven to be NP-Complete with a reduction to Hamiltonian path]
I see the problem sometimes as a set cover problem. Find any set cover $C$ + restrict the size of each set in $C$ to at most $k$ while keeping the coverage  and connectivity properties. [I did not know how to use this observation though]

PS:  I am trying to forget it but it always come back to my mind


texts: graphs where vertex coloring is in P but independent set is NP complete

texts: Is there an example of a class of graphs for which the vertex coloring problem is in P but the independent set is problem is NP complete?


texts: "All-different hypergraph coloring" - known problem?

texts: I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently colored. More specifically, I am looking at the case where all X_i are of size k. Is this known in the literature under some name?  I am looking for characterizations of colorable instances and results on complexity (P vs. NP-hard). For example, for k=2, colorable instances correspond to bipartite graphs, and thus the problem can be solved in polynomial time.


texts: How can I limit the total flow for some edges in an directed graph. We know that every edge can have an upper and lower bound solely. But apart from this sole upper and lower bounds for each edge, if I want to put a limitation on the total flow of some selected edges what should I do? The problem is so that I can not define a dummy sink, make edges starting from selected vertexes to the that dummy sink then from there to previously connected vertexes.


texts:
There are some NP-Complete problems ($ \mathsf{SAT} $, $ \mathsf{SUBSETSUM} $, etc.) known to be in $ \mathsf{DSPACE(n)} $. What about the sub-linear spaces?

  Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?


texts:
Disclaimer: I am not a CS theorist.

Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data structures. I first thought that straight up set theoretical bijective morphisms would suffice, but I ran into a wall quite rapidly - those are just encodings and do not capture the computational essence of the data structure.

Is there a more restrictive (but more useful) definition? (Or if not, why?) Is there a canonical definition of category of "constructed data structures"?


texts: Fast Approximation Algorithms for Covering Design

texts:
The covering design problem is as follows: We are given a universe $\mathcal{U}$ of size $n$. By $C(n,k,l)$ we denote the smallest cardinality of any set system $\mathcal{A} \subset 2^\mathcal{U}$ consisting of subsets of $\mathcal{U}$, such that all sets in $\mathcal{A}$ have size at most $l$ and each subset of $\mathcal{U}$ with size $k$ is contained in some set $A \in \mathcal{A}$.

For example, when $k = 2$ and $l = 4$ we are looking for a system of sets $\mathcal{A}$ in which each set has at most size 4 and for each pair of elements in $u_1, u_2 \in \mathcal{U}$ there exists a set $A \in \mathcal{A}$, such that $u_1, u_2 \in A$.

The covering design problem is related to Steiner Systems: In Steiner Systems we add the constraint that each subset of $\mathcal{U}$ of size $k$ is covered by exactly one set of $\mathcal{A}$.

We know that for fixed $k$ and $l$, asymptotically we have
$$C(n,k,l) = O\left( {n \choose k} / {l \choose k} \right),$$
see [A]. Also, we know that a greedy algorithm with running time $O(n^l)$ computes $C(n,k,l)$ exactly [B]. However, this is superpolynomial in the output size $O(n^k)$ if $l = \omega(1)$ and $k$ is fixed. Hence my question:

  Do we known an approximation algorithm for this problem which explicitly constructs a set system $\mathcal{A}$ within some approximation guarantee and has running time polynomial in the output size $O(n^k)$?

I am particulary interested in the case when $k =2$, i.e. when each pair of $\mathcal{U}$ must be contained in a set of $\mathcal{A}$.

In [C], the authors show that a similar problem cannot be approximated better than within a factor $O(\log n)$, unless $P = NP$.

[A] http://www.ccrwest.org/gordon/optimal.pdf
[B] http://arxiv.org/abs/math/9502238
[C] http://www.sciencedirect.com/science/article/pii/S0166218X04001180


texts: Size of CNF Formula for Adjacency in Configuration Graph

texts:
Suppose $M$ is a (non-deterministic) TM that runs in space $S(n)$. Then, the configuration graph $G_{M,x}$ of $M$ on $x$ has size $2^{O(S(n))}$. Arora-Barak (see http://theory.cs.princeton.edu/complexity/book.pdf page 77, claim 4.4) says that there is a CNF formula of size $O(S(n))$ that given $C,C'$ can tell if $C$ and $C'$ are adjacent configurations in $G_{M,x}$.
The proof says to follow the Cook-Levin reduction. Each part remains the same except the part checking the input tape. Depending on the snapshot = (state, symbols at head of tapes) in $C$, it is easy to check if the pointer to input head location is updated correctly (by -1, 0, or +1). What seems to be hard is to ensure that the new symbol at input tape in $C'$ is consistent with the new pointer location. Since the input is of $n$ bits, it seems this information must be reflected in the formula size. Hence, should the formula size be $O(n+S(n))$?
Note that this result is used only in the proof of TQBF being PSPACE-complete, where $S(n) = poly(n)$.


texts: Minimal specification of Martin-Löf type theory

texts:
I'm reading the formal presentation of Martin-Löfs type theory (appendix of the HoTT book). The authors introduce a hierarchy of universes, then $\Pi, \Sigma,+, {\bf 0}, {\bf 1}$ and also $W$-types as well as natural numbers $\mathbb N$ (inductively via $0$ and $succ$). Eventually they add higher inductive types too.

But then I wonder why it's necessary to do $\mathbb N$ in the theory specification. Doesn't ${\bf 1}$ and $+$ and algebraic data types, in the incarnation of having $W$-types, suffice to set it up? E.g. with the initial algebra approach. (Or at least after we pass from MLTT to HoTT have inductive types - after all, the integers $\mathbb Z$ emerge as homotopy group of circle type $\mathbb S$ within the theory.)

Or has it to do with our need to have primitive recursion from the start, which is defined right next to $\mathbb N$ in the presentation? This is an idea which I have because I don't quite know how "definition is defined" in that framework, or how extending the language works, formally. I might add that I recognize that at least an informal notion of numbers and "greater" is used already when the hierarchy of universes is defined.

In case one can spare $\mathbb N$ and the specification is just not minimal, are there other items one could, in principle, drop? E.g. I could imagine $\bf 2$ and then $+$ coming from some combination of $\Pi, \Sigma, {\bf 0}, {\bf 1}$, but I was not able to do it.


texts:
This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different.

We all have favorite papers in our own respective areas of theory. Every once in a while, one finds a paper so astounding (e.g., important, compelling, deceptively simple, etc.) that one wants to share it with everyone. So list these papers here! They don't have to be from theoretical computer science -- anything that you think might appeal to the community is a fine answer.

You can give as many answers as you want; please put one paper per answer! Also, notice this is community wiki, so vote on everything you like!

(Note there has been a previous question about papers in recursion-theoretic complexity but that is quite specialized.)


texts: Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

texts:
Real computers have limited memory and only a finite number of states.
So they are essentially finite automata.
Why do theoretical computer scientists use the Turing machines
(and other equivalent models) for studying computers?
What is the point of studying these much stronger models with respect to real computers?
Why is the finite automata model not enough?


texts:
Take a set $S = \{a_1, a_2, ..., a_n\}$ of integers $a_i$ and a set $G = \{b_1, b_2, ..., b_m\}$ of integers $b_j$.

If we ask the question, is there a subset $C \subseteq S$ such that the sum $(\sum_{a_i \in C} a_i) \in G$, and $m = 1$ this is the traditional subset sum problem. We add an additional restriction (so that this is a promise problem) that all $b_j \in G$ must be between the minimum sum and the maximum sum of subsets of $S$.

I have three questions regarding the case where $m \gt 1$.

1.) Is there a known name for this problem and has it been studied?

2.) Are there threshold results for this problem, or can threshold results from k-SAT problems be reduced to this problem?

3.) Are there known or obvious instances where this problem is trivial? Or in general does it remain NP-Complete?

Edit: Threshold results - for a uniformally random selected set $S$ and $G$ of given sizes whose integer members are limited in size (under the usual binary encoding) of $b$ bits, and for a fixed ratio $k = |G|/|S|$, is there a $k$ for which the multiple target subset sum problem becomes almost certainly satisfiable or unsatisfiable (in the manner of 3-SAT)?


texts: Recursively presenting or even enumerating all P-hard languages

texts:
A class of languages $C$ is recursively presentable if there is an effective enumeration of Turing machines $\mathcal{M}_1,\mathcal{M}_2,\ldots$ such that $C=\{L(\mathcal{M}_i)\mid i=1,2,\ldots\}$. Uwe Schöning considers this notion in his elegant generalisation of Ladner's theorem ("A Uniform Approach to Obtain Diagonal Sets in Complexity Classes", Theor. Comp. Sci. 18, 1982).

In a previous answer on this site, Ryan Williams argues that the set of all P-hard languages can be recursively presented "similar to how Schoening does it for the NP-hard sets". I would like to know how this works, since I cannot find this in the paper. Schöning works with Turing reductions and shows that the NP-complete sets are recursively presentable. We can adapt his argument to NP-complete sets under polynomial many-one reductions as follows:

Take an enumeration $(\mathcal{M}_i,\mathcal{R}_i)_{i\geq 1}$ of pairs of polynomially time-bounded non-deterministic Turing machines $\mathcal{M}_i$ and polynomial reductions $\mathcal{R}_i$ (we can enumerate polytime machines and reductions by enumerating all machines and polynomials, and augmenting them with a polytime "stop clock" that enforces timely halting).
For each pair of a machine $\mathcal{M}_i$ and reduction $\mathcal{R}_i$, the let $\mathcal{M}'_i$ denote a machine that does the following on input word $w$:

For all input words $v$ with $|v|<|w|$, test whether $\mathrm{SAT}(v)=\mathcal{M}_i(\mathcal{R}_i(v))$, i.e., whether $\mathcal{R}_i$ reduces $\mathrm{SAT}$ to $L(\mathcal{M}_i)$ on these instances.
If yes, accept iff $\mathcal{M}_i$ accepts $w$
If no, accept iff $w\in\mathrm{SAT}$

The required enumeration is $\mathcal{M}'_1,\mathcal{M}'_2,\ldots$, since each of those either decides $\mathrm{SAT}$ (up to finitely many cases) or some other language in NP to which $\mathrm{SAT}$ can truly be reduced.

I do not see how to apply this idea to recursively present all P-hard languages. One could readily recursively present, e.g., all P-hard languages in ExpTime (which would suffice as an answer in the other thread), but I don't see why the P-hard languages in general (including undecidable ones) should even be countable.


texts:
It is trivial to model sum types using only union types and product types: simply add a discriminant. $A + B \cong (0 \times A) \cup (1 \times B)$.

What I am wondering is whether or not there is a concise, practical representation for union types using sum types and product types.


texts: Structure of graphs that exclude a perfect matching on four vertices as an induced graph

texts: I am interested in understanding the structure of the class of graphs $G$ such that there is no vertex induced subgraph on four vertices that is a perfect matching. Stated differently for any four vertices $a,b,c,d$ in $G$ if $ab$ and $cd$ are edges then the graph should have at least one more edge on the four vertices. Has this class been studied previously? Any references or insights would be appreciated. We understand this class when restricted to bipartite graphs but the general case seems more tricky.


texts: What are the complexities of the following SAT subsets ?

texts:
Assume $P \neq NP$

Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$).

|x| is the size of the instance x.

Let L be a language, $L|_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ |  } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

What is the complexity of the following languages :

$L_1 = SAT|_{{}^{2i}2 \leq |x| < {}^{2i+1}2}$
$L_2 = SAT|_{{}^{2i+1}2 \leq |x| < {}^{2i+2}2}$

As $L_1 \sqcup L_2 = SAT$, they can't be both in P under the assumption that $P \neq NP$.
As there both have exponential holes, I don't think SAT can be reduced to one.

Hence the intuition would be that they are both in NPI, but I can't find a proof or disproof.

Two others languages are
$L_3 = SAT|_{|x|={}^{2i+1}2}$
$L_4 = SAT|_{|x|={}^{2i}2}$

If one of both is in NPC, the other is in P because for each instance of one, it can't be transformed into an greater instance of the other because it is of exponential size, and smallers instances have a logarithmic size. Still by intuition, there is no reason why they would have a different complexity. What would their complexity be ?

Ladner's proof of NPI problems under $P \neq NP$ assumption use languages like $L_1$ or $L_2$, but $L_1$ and $L_2$ aren't built by diagonalization.


texts:
I've already posted this question a while ago on MathOverflow, but to the best of my knowledge it is still open, so I'm reposting it here in the hope that someone might have heard of it.

Problem statement

Let $P$, $Q$ and $R$ be three partitions into $p$ nonempty parts (denoted by $P_h$'s, $Q_i$'s and $R_j$'s) of the set {$1,2,\ldots,n$}. Find two permutations $\pi$ and $\sigma$ that minimise $$\sum_{i=1}^p\left|P_i\cup Q_{\pi_i}\cup R_{\sigma_i}\right|.$$

Questions

1) What is the complexity of this problem (or of the corresponding decision problem)?

2) If the problem is indeed solvable in polynomial time, does it remain true for any number $k\geq 4$ of partitions?

Previous work

Berman, DasGupta, Kao and Wang (http://dx.doi.org/10.1016/j.ipl.2007.06.008) study a similar problem for $k$ partitions, but using pairwise $\Delta$'s instead of $\cup$ in the above sum. They prove that the problem is MAX-SNP-hard for $k=3$, even when each part has only two elements, by reducing MAX-CUT on cubic graphs to a special case of their problem, and give a $(2-2/k)$-approximation for any $k$. So far, I have not been able to find my problem in the literature, or to adapt their proof.

Easy subcases

Here are some subcases I've found to be solvable in polynomial time:

the case $k=2$;
the case $p=2$, for any $k$;

Moreover, when $k=3$, no two parts are equal and all parts have size $2$, we have the lower bound $3p+1$ (I don't know if it's tight).


texts: Is there a systematic method for constructing lambda calculus terms that can distinguish between inputs?

texts:
For example, finding terms $\vec{a}$ such that:

$\vec{a}(\lambda x.x) = T\\\vec{a}(\lambda xy.x) = F$

Is there a systematic method for finding terms with these types of constraint?


texts: What is the asymptotically fastest known algorithm for computing the nullspace of a matrix?

texts: I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.


texts: Hardness jumps in computational complexity?

texts:
Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path by growing edge-disjoint paths of length at most $k$ from its nodes ($k$ is called the hair length). Minimum Bandwidth problem is in $P$ for 2-caterpillars but it is $NP$-complete for 3-caterpillars.

Here is a very interesting fact, Minimum bandwidth problem is solvable in polynomial time for 1-caterpillars (hair length at most one) but it is $NP$-complete for cyclic 1-caterpillars (in cyclic caterpillar, one edge is added to connect the endpoints of the main path). So, the addition of exactly one edge makes the problem $NP$-complete.

  What is the most striking example of problem hardness jump where a small variation of input instance causes a complexity jump from polynomial-time solvability to $NP$-completeness?


texts:
A priority argument, an important proof technique in recursion theory, was introduced by Friedberg and Muchnik, to solve Post's Problem, i.e., the existence of two r.e. sets that do not Turing reduce to each other.

My question is whether or not there has been an attempt to formalize priority arguments in some proof system adopted by proof checkers or proof checkers.  I believe this is an interesting problem, since:

Priority arguments can sometimes be very complicated (for humans to read);
Objects constructed by priority arguments are constructive (relative to something else), so it is possible that the argument is suitable to formalize in some proof systems, many of them are based on typed lambda calculi; and
Yet most construction in priority arguments do not look like a typical functional programs at all


texts: Reference for mixed graph acyclicity testing algorithm?

texts:
A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction an orientation of a mixed graph is obtained by assigning a direction to each undirected edge. A set of edges forms a cycle in a mixed graph if it can be oriented to form a directed cycle. A mixed graph is acyclic if and only if it has no cycles.

This is all standard and there are many published papers mentioning acyclic mixed graphs. So the following algorithm for testing acyclicity of mixed graphs must be known:

Repeat the following steps:

Remove any vertex that has no incoming directed edges and no incident undirected edges, as it cannot be part of any cycle.
If any vertex has no incoming directed edges but it has exactly one incident undirected edge, then any cycle using the undirected edge must come in on that edge. Replace the undirected edge by an incoming directed edge.

Stop when no more steps can be performed. If the result is an empty graph, then the original graph must necessarily have been acyclic. Otherwise, starting from any vertex that remains, one can backtrack through the graph, at each step following backwards through an incoming edge or following an undirected edge that is not the one used to reach the current vertex, until seeing a repeated vertex. The sequence of edges followed between the first and second repetition of this vertex (in reverse order) forms a cycle in the mixed graph.

The Wikipedia article on mixed graphs mentions acyclic mixed graphs but doesn't mention how to test them, so I'd like to add to it something about this algorithm, but for that I need a published reference. Can someone tell me where it (or any other algorithm for testing acyclicity) appears in the literature?


texts:
When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of algorithms (such as rounding or primal-dual algorithm).  In fact, there are many problems whose best approximation ratio matches the integrality gap.

Some algorithm may have a better approximation ratio than the integrality gap for some problem, but I don't know if such an example exists or not.  If the answer is yes, could you give some examples?

I know that some problems admit multiple mathematical formulations.  In such cases, consider the mathematical formulation with the smallest integrality gap, as long as it can be solved in polynomial time (perhaps some formulations may use separation oracles).

This question is related to [the question: The importance of Integrality Gap].


texts:
One gap that I was always aware that I don't really understand is between non uniform and uniform computational complexity where the circuit complexity represents the non uniform version and Turing machines is were things are uniform. I suppose "uniform" is a way to restrain the class of algorithms, e.g. not allowing an entirely different circuit for a problem with n variables compared to a problem of n+1 variables.

My questions are: 1) It there a description of uniformity just in terms of circuits, and 2) Is it possible to come with an even stronger form of uniformity and thus to give even more restricted notion of what effective (or restrained) algorithms in P are?

Late clarification: my intention in question 2 is about a restricted class of algorithms that "practically" has the same power as the class of polynomial algorithms.


texts:
Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest.  In most cases, blog posts are easier to understand than formal papers, because they omit most of the gory technical details and emphasize intuition (which papers generally omit).

Thus, it would be useful to have a list of recommended blogs, in the same spirit as other lists of recommended resources:

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

Of course one can follow the excellent Theory of Computing Blog Aggregator, but that list is rather overwhelming, especially for beginners.

Please highlight why you recommend them.


texts: What points should I mention and how? - in a theory paper's introduction part

texts:
this is my first time writing a theory paper and I am getting carried away with thoughts when I am writing theory paper's introduction, I have read some web pages telling what points should I mention but I am still confused on how to mention them? like using maths? examples? or just textual theory? its so confusing that it gave me headache.
So here I am asking what should I mention in my theory paper's introduction and how?


texts: Do you know this problem of deciding whether a given 0-1 matrix contains k pairwise disjoint “column-paths”?

texts:
Problem: $X$
  Instance: A $m\times n$ 0-1 Matrix $A$,  $k \in \mathbb{N}$.
  Question: Does $A$ contain $k$ pairwise disjoint "column-paths"?

A column-path starts in the first column, ends in the last one
and traverses only 1-entries.  It may visit any row at most once.
Any 1 may be visited once only, by any path.

Example:

    $ A =
    \begin{pmatrix}
    a_{00} & a_{01} & a_{02} \\
    a_{10} & a_{11} & a_{12} \\
    a_{20} & a_{21} & a_{22} \\
    a_{30} & a_{31} & a_{32} \\
    \end{pmatrix}
     =
     \begin{pmatrix}
    0 & 1 & 0 \\
    1 & 0 & 0 \\
    1 & 0 & 1 \\
    0 & 1 & 1 \\
    \end{pmatrix}
    $

$A$ contains the paths $(a_{10},a_{01},a_{22})$, $(a_{10},a_{01},a_{32})$, $(a_{10},a_{31},a_{22})$
and $(a_{20},a_{01},a_{32})$. Since there are (only) 2 disjoint paths, i.e. the
last 2, $(A,2) \in X$.

It is easy to see, that this problem reduces to set packing. It
does not work so easily the other way around, because the set
packing instance may be too "restrictive".

Any idea what kind of problem this is?


texts: Derivation of Expected-Maximization training equations for a noisy-OR Bayesian network

texts:
How do I derive the EM training equations for a noisy-OR Bayesian network?

I am familiar with one solution to these equations.  If I remember correctly, the result is:

Given a model with link weights $$p_{ij} = 1-e^{-w_{ij}}$$ between nodes $i$ and $j$.  Then, for each training example fix the input variables, and use the model to generate some configurations over latent variables.  For each configuration where $T$ is the set of variables that are true, the configuration probability probability is $q$:

\begin{align}
q_j &= 1-\prod_{i\in T} (1-p_{ij})=1-e^{-\sum_{i\in T}w_{ij}}\newline
q &= \prod_{j \in T}q_j\prod_{j \notin T}(1-q_j)
\end{align}

The E-step comprises updating counts:

Add $q$ to $x_i$: if $i \in T$.
Add $$q\frac{p_{ij}}{q_j}\qquad\qquad(1)$$
to $l_{ij}$ if $i, j \in T$ and there is a link from $i$ to $j$.

The M-step is to let each new link weight (from node $i$ to node $j$) be:

$$\frac{l_{ij}}{x_i}$$

When I tried to derive these equations, I wasn't able to generate equation (1).


texts:
A linear extension $L$ of a poset $\mathcal{P}$ is a linear order on the
elements of $\mathcal{P}$, such that $x \leq y$ in $\mathcal{P}$ implies $x \leq y$ in $L$ for all $x,y\in\mathcal{P}$.

A linear extension graph is a graph on the set of linear extensions of a poset, where two linear extensions are adjacent exactly if they diﬀer in one adjacent swap of elements.

On the following picture there is the poset known as $N$-poset, and its linear extension graph, where $a=1234, b=2134, c=1243, d=2143, e=2413$.

(This figure is taken from the work.)

When you study linear extension graphs (LEG) you can come up with an idea (conjecture) that if  $\Delta$ - maximal degree of a LEG, $\delta$ - respecrively, minimal degree, then the degree set of any LEG consists of $\Delta,\delta$ and each natural number between them. For example, let's take a poset, known as chevron, then in its LEG $\mathcal{G}$ with $\Delta(\mathcal{G})=5$ and $\delta(\mathcal{G})=2$, and also, according to our conjecture, vertices with the degrees 4 and 3 are contained in the graph. So, the question is can we prove or disprove this conjecture?

About LEGs and how do they look like one can read in the dissertation of Mareike Massow here. Chevron and its LEG can be seen on the page 23 of the dissertation.

On the degree sets there is the classical paper "Degree sets for graphs" by Kapoor S.F. et al.


texts: CSP-problem, based on context-free grammar

texts:
I'm trying to solve a  CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production rules: S->A, S->B, S->AB, A->Aa, A->a, A->aa, B->Bb, B->b, B->bb.

Now I'm looking for a word, which uses specific (sub-sequences of) production rules. For example:

"S->AB" must be used 3 times in the whole derivation-sequence
If "S->AB" is used, it must be followed by "B->Bb"
If "S->Aa" is used, it must directly be followed by "A->a"

I know the problem is a CSP, but I couldnt find a specific algorithm on how to solve this. Any ideas, which (concrete) algorithm could be used?
Also, I'm thinking about the right data-strucure. Should I rather use an n-Tree or an array (CYK-Table)?


texts:
The Balanced Max-2-SAT is a special case of Max-2-SAT (each clause is a disjunction of exactly 2 literals) in which for every variable $x$, there is a $k$ such that $x$ appears positive exactly $k$ times in the clauses, and exactly $k$ times negative in the clauses.

I'm looking for a published proof of NP-Hardness for this problem, for references.

It is implied NP-Hard by [this paper],
but I can't find the original NP-Hardness proof.

Is it a consequence of the hardness of Max-2-SAT ?

Also as a bonus, Balanced Max-2-SAT($k$) is the subcase in which every variable appears exactly $k$ times positive, exactly $k$ times negative.
Is there some known $k$ for which NP-Hardness is published?
I know that Balanced Max-3-SAT(2) is hard, but found nothing for the $2$ case.


texts: What are the most recent (say in the last 3 years) attempts at disproving $P = NP$, and where can I find the papers?


texts: Deciding whether an interval contains a prime number

texts: What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the interval and $\sim$ hides poly-logarithmic factors in the starting point of the interval; can we do better (in terms of $L$ alone)?


texts:
I'm puzzled by this statement from Wikipedia:

  For tail calls, there is no need to remember the place we are calling
  from — instead, we can perform tail call elimination by leaving the
  stack alone (except possibly for function arguments and local
  variables [my emphasis]) [...]

I thought that the amount of space for a tail call was constant.  I thought that it was O(1), not O(n) where n would be the depth of the stack (if it were not tail-recursive).  But what is this "(except possibly for function arguments and local variables)"?

Is memory usage for a tail call not constant and can you get a memory overflow?


texts: What forms of randomness are 'allowed' in FPRASs?

texts:
I cannot seem to find a source describing randomized approximation schemes ((F)PRAS) that tells me exactly what sort of randomness a program is allowed to use. A priori it seems to me that being able to generate uniformly random numbers in the unit interval is strictly stronger than being able to generate random bits. Is this true? Or can you approximate the uniform distribution over $[0, 1]$ sufficiently well with dyadic rationals? (Note that I'm explicitly talking about approximation schemes, so maybe you're able to hide an error term in your probability
distribution in the $\epsilon$ of the approximation.)

If it is true that one form of randomness is stronger than the other, what forms of randomness are generally assumed to be available to an (F)PRAS?


texts:
Possible Duplicate:
  Do you use any article organizers?

[[ This is intended as a wiki question ]]

I have tons of papers on the subject I'm studying.  When you get them from ACM or someone's website, they're usually called something like kautz-a1.pdf or, my favorite, paper.pdf.  What I've done is organize them by:

year - first author's last name - paper title.pdf

So for example, in /papers:

2007 - Wang - PRT for RT indirect lighting using spectral mesh basis.pdf

This seems to work, and I can usually find what I'm looking for.  I mirrored this folder on DropBox, so I can pull down the collection if I happen to be working on another computer than my main.

How do other people store them?


texts: Paths of length $p$ in a Graph, $p$ a prime

texts:
I came across the following decision problem, for which I wondered whether anybody of you came across a similar problem and can give me some insight on its nature/complexity.

Given as input a directed labeled graph $G = (V, E)$ and nodes $s,t \in V$, the question is whether there exists a path $\pi$ between $s$ and $t$ whose length equals some prime $p$ (in $\pi$, we allow repetition of vertices so that a self-loop answers this question trivially with yes.)

Thanks!


texts: Class of languages accepted by Python RegEx?

texts:
Python / Java / Perl / Ruby / etc. extend regular expressions to permit
look-ahead and look-behind, e.g.,
LookAround:

(?=...)
(?<=...)
(?!...)
(?<!...)

I would appreciate a formal definition of the languages accepted by these
modern "regex" modules. They don't reach context-free, do they? What is the superset of regular languages achieved by these recursive-backtracking additions
to regular languages?


texts: Parameterized complexity of Hitting Set in finite VC-dimension

texts:
I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and a positive integer k, does X contain a subset of size k that hits every range in R?  The parameterized version of the problem is parameterized by k.

For what values of d is the d-Dimensional Hitting Set problem

in FPT?
in W[1]?
W[1]-hard?
W[2]-hard?

What I know can be summarized as follows:

1-Dimensional Hitting Set is in P and is therefore in FPT.  If S has dimension 1 then it is not difficult to show that either there is a hitting set of size 2 or the incidence matrix of S is totally balanced.  In either case we can find a minimum hitting set in polynomial time.
4-Dimensional Hitting Set is W[1]-hard.  Dom, Fellows, and Rosamond [PDF] proved W[1]-hardness for the problem of stabbing axis-parallel rectangles in R^2 with axis-parallel lines.  This can be formulated as Hitting Set in a range space of VC-dimension 4.
If no restriction is placed on d then we have the standard Hitting Set problem which is W[2]-complete and NP-complete.
Langerman and Morin [citeseer link] give FPT algorithms for Set Cover in restricted dimension, though their bounded dimensionality model is not the same as the model defined by bounded VC-dimension. Their model does not seem to include, for example, the problem of hitting halfspaces with points, though the prototype problem for their model is equivalent to hitting hyperplanes with points.


texts: Array implementation of dictionary data structure

texts:
Is there a data structure that supports searching, inserting, deletion in worst-case O(log n) time and that satisfies the following "array implementation" property: at any point in time, the data structure only occupies memory cells 1..n (or 1..O(n)) if there are n elements?

Note that e.g. heaps do satisfy the property.

In particular, do standard data structures such as red-black, AVL, etc. allow for such an implementation?  (And if so, why is this not discussed in standard textbooks?)

(This is vaguely related to a previous question which got no answer.)


texts: Strongly weight-balanced deterministic skip lists

texts:
In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are defined as:

  For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants.

They claim:

  Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees,
  deterministic skip lists, and skip lists in the expected sense.

Other papers also claim that deterministic skip lists are strongly weight-balanced, including Concurrent Cache-Oblivious B-Trees and Cache-Oblivious Streaming B-trees.

I can't figure out why deterministic skip lists have this property. The original paper on deterministic skip-lists notes that

  As we see from Fig. 1, there exists a one-to-one correspondence between 1-2 skip lists and 2-3 trees.

It seems to me, however, that 2-3 trees are not strongly weight-balanced, since a node at height $h$ can have anywhere from $2^h$ to $3^h$ descendants.