texts:
I am interested in the best currently known algorithm (in fact, any relevant reference) for the following problem:

  Given a  family of subsets $S_1,S_2,\ldots S_N\subseteq \{1,2,\ldots N\}$,    determine if there is a pair of disjoint subsets $S_i\cap S_j=\emptyset$.

This is the $k=2$ case of set packing problem; by taking complements, we obtain the $k=2$ set cover problem. An obvious generalization considers $M$ subsets.

There is a straightforward reduction to matrix multiplication: if $B$ is the incidence matrix of the family $\{S_1,\ldots S_N\}$, then we can check if $BB^T$ has a zero element in $O(N^{2.373})$ time.

Curiously enough, the only discussion of this problem in literature I was able to come by was an elementary textbook by Kleinberg and Tardos where it was given as an example of $O(N^3)$ complexity, followed by "For this problem, there are algorithms that improve on $O(N^3)$ running time, but they are quite complicated. Furthermore, it is not clear whether the improved algorithms for this problem are practical on inputs of reasonable size". The wording, however, suggests that matrix multiplication was assumed.

Is there a $O(N^2\mathrm{polylog}(N))$ algorithm for this problem? Conversely, would such an algorithm necessarily imply an improvement in matrix multiplication?
Assume we restrict the algorithm to decision trees in some way in order to exclude integer arithmetic and thus fast matrix multiplication. Are there nontrivial lower bounds for this case?
A weakened version is equivalent to testing whether a given graph has diameter at least $3$. Is this problem known to be easier than all-pairs-shortest-paths?


texts: Proofs to verify quantum states without revealing their description

texts:
Consider the following function $$f_s: k \rightarrow \lvert \psi_k \rangle$$
where $s,k$ are bit strings, and $\lvert \psi_k \rangle$ is a $n$-qubit state.
Assume the function is a one-to-one mapping.

Given only $\big(f, k, \lvert \psi_k \rangle \big) $ is there a way to produce a (zero knowledge) proof $P$ that only verifies that $\lvert \psi_k \rangle$ has been generated from $k$, but not learn any more information about $\lvert \psi_k \rangle$ or $s$?

Digression (to the classical world where factoring is difficult)

Consider a classical function $f_s: k \rightarrow p$
so a function $f$ does the following $f_p(q) = p*q*r*s$, where  $p,q,r,s$ are all large primes,
now given only $(f,q, n=p*q*r*s)$, one can easily check $q|n$, but cannot learn $p$ since that requires factoring $p*r*s$

I am looking for something similar for the quantum regime.


texts: Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$

texts:
I have a certain impossibility result that holds unless $\mathsf{NP} = \mathsf{QP}$. It seems quite likely that one could strengthen this to hold unless $\mathsf{NP} = \mathsf{P}$, which I would not need to motivate further in my paper.
Unfortunately, I don't have time to do that in this particular paper, so instead want to quickly motivate to cryptographers why $\mathsf{NP} = \mathsf{QP}$ is unlikely. I know of basic consequences (namely that it would badly violate essentially any form of ETH, so would imply that tournament dominating set is in P), but not much else.
Of course, there's also the obvious motivation that $\mathsf{NP} = \mathsf{QP}$ implies $\mathsf{NP}\cap\mathsf{coNP}\subseteq \mathsf{QP}$. Most hardness assumptions used in crypto are in $\mathsf{NP}\cap\mathsf{coNP}$, and a particular weak hardness assumption (fixed characteristic finite field discrete log) is known to be in $\mathsf{QP}$. One can therefore interpret $\mathsf{NP} = \mathsf{QP}$ as "most hardness assumptions in crypto are roughly comperable to fixed characteristic finite-field discrete log", which may work fine as motivation.
Still, is there any clearer motivation from a complexity theory point of view? For example a hierarchy collapse/something along those lines.


texts: Do we know some quasi-polynomial problem that is known to not be in NP?

texts:
The title pretty much says it all, but to explain how I got there:

I think, that one of the reasons we are unable to prove or disprove , but mainly disprove $P=NP$ (and yes, I was provoked by the discussed recent proof about $P$ vs $NP$) is because we can't take some superpolynomial subexponential problem and reduce it to some $NP$-complete, because in this "grey" area above $P$ are two types of problems - ones in $NP$ and ones not in $NP$. But I know little to nothing about these problems, nor what is the state-of-the-art of current scientific community knowledge, but I just wonder whether there is a problem known to have this property.

I\ve been going through similar question to this one, but I could not deduce from posts there answer to this question.

EDIT: It is irrelevant whether the language is mathematically artificial or describes something "natural", as long as one can prove it is in $QP$ and not in $NP$, or at least give a very convincing argument for it.


texts: Statistical query model with Gaussian noise?

texts:
Kearns' statistical query model is a well-known learning model with noise tolerance. The statistical query oracle takes as input a statistical query of the form $\{\chi, \tau\}$. Here $\chi$ is any mapping of a labeled example to $\{0, 1\}$ and $\tau \in [0, 1]$ is called the noise tolerance. The oracle returns an estimate for the expectation $\mathbf{E}\chi$, that is, the probability that $\chi = 1$. The additive error of this estimate is at most $\tau$.

The statistical query oracle only guarantees an upper bound of the noise and Kearns' model mentions nothing about the noise distribution. Is there any query oracle in computational learning theory that can answer a statistical query with normal distributed noise? That is, the oracle takes as input a statistical query of the form $\{\chi, \sigma^2\}$ and returns the estimate of $\mathbf{E}\chi$ with additive error of Gaussian distribution $\mathcal{N}(0, \sigma^2)$.

I think this model is reasonable because Gaussian noise is a common assumption in many problems. Also, for central limit theorem, the estimate will converge to a Gaussian distribution (but we are not able to control the variance).


texts: Can quantum algorithms with exponential speed-up be rederived using span-programs?

texts:
The general adversary lower-bound is now known to characterize quantum query complexity
due to breakthrough work by Reichardt et al. The same line of work also establishes connections
to the span program framework to design quantum algorithms.

Many interesting quantum algorithms, including ones with exponential speed-up like
Simon's algorithm and Shor's algorithm for period finding can be expressed in the
quantum query model.

Is there any work showing lower-bounds for these algorithms in the general adversary model?
Is there any work re-deriving Simon's or Shor's algorithms in the span-program framework?

Apparently, only quantum algorithms with polynomial speed-up, like Grover's , have been re-derived using span programs (or Belov's learning graph) framework.

There is work by Korian et al. showing lower-bounds for Simon using the polynomial method, but there is apparently no known way to translate polynomial-method lower-bounds to general adversary lower bounds.


texts: Is counting maximal cliques in an incomparability graph #P-complete?

texts: This question is motivated by a MathOverflow question by Peng Zhang.  Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs (i.e., we want to count maximal antichains in a finite poset)?  This question seems natural enough that I suspect that it has been considered before, but I have not been able to locate it in the literature.


texts: How is rebalancing of DHTs handled in case of failure or addition of new node?

texts:
I am reading about Dynamo-like DHT data storage applications like cassandra and project voldemort. I was curious, say:

A new node is added to the cluster (since all the nodes are full) then the whole DHTs load factor will be messed up, so the DHT needs a re-balancing. So, how is that handled? Any optimized method/algo to do that?
During the re-balancing process, there must be a data outage time. So, how to deal with that?

I got something about voldemort re-balancing but I didn't really understand, how is the dynamic growth (addition of new nodes) in the cluster is handled?

Thanks


texts: Why is it important that the secret is at the end when signing with MD5?

texts: it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?


texts: Possibility of hierarchy with $UP$ class?

texts:
I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The reference https://link.springer.com/content/pdf/10.1007%2FBF01184809.pdf gives some classes for which we have oracles with respect to which $UP$ is not low.

Which classes are known to be low with $UP$ oracle ($PSPACE$ is one of them)?
Is there a hierarchy to concoct with $UP$ and $coUP$ analogous to the standard polynomial hierarchy and in particular is there an analog of $PSPACE$?


texts: Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming

texts:
Does someone dare to attempt to clarify what's the relation of these fields of study or perhaps even give a more concrete answer at the level of problems? Like which includes which assuming some widely accepted formulations. If I got this correctly, when you go from SAT to SMT you're basically entering the field of CSP; vice-versa, if you limit CSP to booleans you're basically talking of SAT and maybe a few related problems like #SAT. I think this much is clear (e.g. cf Kolaitis and Vardi's chapter "A Logical Approach to Constraint Satisfaction" in Finite Model Theory and Its Applications by Grädel et al.), but what's less clear to me is when are the constraints "modulo a theory" and when aren't they? Does SMT always imply the theory uses only equality and inequality constraints are always in the broader field of CSP? As far as I can tell, you can often introduce slack variables, so the distinction [if it exists] is less than obvious.

The relatively recent "Satisfiability handbook" (IOP Press 2009) gathers both SMT and CSP problems under its broad "satisfiability" umbrella, but given the way it is structured (chapters written by various authors) doesn't really help me with figuring out this.

I would hope the terminology gets less confusing when you talk of constraint programming, which (by analogy with the term ''mathematical programming'') I hope involves minimizing/maximizing some objective function. The Wikipedia article on constraint programming is alas so vague that I can't really say if this framing happens though. What I can gather from Essentials of Constraint Programming by
Frühwirth and Abdennadher (p. 56)  is that a "constraint solver" usually provides more than just a satisfiability checker, with simplification etc. being important in practice.

Although this is hardly an actual CS-theory research question, I don't expect good answers to this one on the undergraduate CS.SE site given what I saw at https://cs.stackexchange.com/questions/14946/distinguish-decision-procedure-vs-smt-solver-vs-theorem-prover-vs-constraint-sol (which contains a lot of words but not what I would consider a real answer, alas).


texts: How did TCS become conference-oriented rather than journal-oriented?

texts:
Disclaimer: I can only vouch for my research fields, namely formal methods, semantics and programming language theory. The situation is possibly different in other parts of the discipline.

It seems that TCS has become rather conference-oriented. Researchers aim at publishing in the next conference. Sometimes a journal version appears. Sometimes it doesn't.

In other disciplines (biology, mathematics, and most others I guess) this is unheard of. The effort put into writing the conference papers is a lot lesser, but in turn, the conference papers count a lot less. The "real deal" is the journal publication.

Arguing whether this situation is good or bad could result in a flame war, and doesn't have a precise answer. Instead, let's try a more factual question:

How did we become so conference-oriented? How did conference papers gain so much weight?


texts:
The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection.
A hypergraph is an $r$-hypergraph if each of its edges has at most $r$ vertices.

What is the complexity of the following problem: Given a graph $G$, does there exist a $3$-hypergraph $H$ such that $G$ is the line graph of $H$?

It is well-known that recognizing line graphs of $2$-hypergraph is polynomial, and it is known (by Poljak et al., Discrete Appl. Math. 3(1981)301-312) that recognizing line graphs of $r$-hypergraphs is NP-complete for any fixed $r \ge 4$.

Note: In case of simple hypergraphs, i.e. all hyperedges are distinct,
the problem is NP-complete as proved in the paper by Poljak et al.


texts: Is predicting (in the limit) computable sequences as hard as a dominating function?

texts:
Define a "predicting oracle" to be an oracle that does as described in this question.

default (weak) version:

Is it the case that, for every predicting oracle $O$, there exists an

oracle machine $M$ such that when $M$ operates on $O$, the result

computes a function that dominates all (ordinarily) computable functions?

uniform (strong) version:

Does there exist an oracle machine $M$ such that for every predicting oracle $O$, when $M$ operates on $O$, the result computes a function that dominates all (ordinarily) computable functions?


texts: Bounds on size of self-concatenation of Finite Languages

texts:
Given a finite language $L$ with $|L|$ number of elements, what is $|L^i|$ (the language $L$ concatenated with itself $i$ times)? If there is no exact result, is there an upper/lower bound?

Define concatenation of $L$ with itself to be as the classical definition: $LL = \{wx \space | \space w,x \in L\}$. Similarly, $L^n = \{a_1a_2...a_n \space | \space a_i \in L, \forall i \in [1, n] \}$.

Clearly, a non-tight upper bound is $|L|^i$ (each element in concatenation is unique) given that $|L| > 1$, but I would like to know if there is either a tight upper bound or tight lower bound.


texts: Automata and a kind of pumping lemma on state transition function

texts:
We encountered this question as an exercise in a Büchi automata book a couple of decades ago, and back then gave a few tries thinking that it should be easy. But haven't seen a solution. My friend Deepak helped me with the problem statement, here it is:

Given a DFA $A =
(Q,Letters,\delta,Final)$ with $n$ states,
each letter $a$ induces a function
$f_a: Q \to Q$, given by $f_a(q) = \delta(q,a)$.
A word $w$, by extension, also induces a
function $f_w : Q \to Q$.

The problem was to show that for any $w$, we can find
a $w'$ of length $\leq n!$, such that $f_{w'} = f_w$.

Wondering if there is any bound on the word length, even if not a $n!$ (like $n^n$).


texts: How do minimally violated k-mod cuts work (intuitive explanation)?

texts:
As a background, I am not a specialist in theoretical computer science. But I have to take an exam with research-level optimization topics, and I have to learn it on my own, without lectures or tutors.

One of the subtopics I am required to learn in integer programming are maximally violated mod-k cuts. I was able to understand cutting plane methods in general, and how Chvatal-Gomory cuts work. The book I am using says that k-mod cuts are created by multiplying the system of constraining inequalities with some vector $\lambda$, then summing up all inequalities. I have difficulty picturing this and understanding why this leads to an interesting form of cut.

I tried making a numerical example for myself starting out with an easy system with 2 variables and 3 inequalities, but wasn't able to come up with any (apparently, finding them is NP-hard for the general case, I had hoped to come up with something obvious with a few tries for a very small example).

Could you please give me an explanation about the intuition behind these cuts? What do they look like, what makes them "maximally violated", how are they an improvement over other cuts?

The main text from which I have to learn is http://www.springer.com/de/book/9783642167287, and I also found exactly one paper on the topic, http://www.lancaster.ac.uk/staff/letchfoa/articles/mod_k.pdf. They are research-level sources, and I don't have enough background to build an intuitive understanding when reading the definitions.


texts: Cover time and spectral gap for reversible random walks

texts:
I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda_2|$, that is, we ignore the smallest eigenvalue of the chain.

The only result I was able to find in this direction is from Bounds on the Cover Time, Broder and Karlin, FOCS 88. There it is assumed that the transition matrix of the chain is doubly stochastic (but not necessarily reversible) and aperiodic; roughly speaking, the paper shows that under these assumptions if the cover time is $O(n \log n)$, then $1-\max(|\lambda_2|, |\lambda_n|)$ is at least $n^{-1}$.

Intuitively, it seems very plausible that if you can cover all the vertices of a graph quickly, then mixing time ought to be small. In particular, if you can cover all the vertices of a graph in $n^2$ time, surely you should be able to rule out a spectral gap of, say, $n^{-1000}$?

One possible obstacle that would break the implication between small cover time and large spectral gap is bipartiteness: on a bipartite graph, you can have a small cover time with an eigenvalue of $-1$. By in my question, I am bypassing this issue by ignoring the smallest eigenvalue.


texts: Processor failures in distributed computing that are not crash or Byzantine

texts:
There are two main types of processor failures in distributed computing models:

(1) Crash failures: a processor stops, and never starts again.
(2) Byzantine failures: processors behave adversarially, maliciously.

My question is:

  What are some other types of processor failures that have been studied, that do not reduce to crash or Byzantine failures?

Also, a more specific question:

  Has a model been studied where, with some probability, a process is on at time step $t$, and otherwise off?  So each process is winking on and off, as it were.

I am most interested in how these failures relate to consensus and other distributed agreement problems.

Thank you.


texts: Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$

texts:
Let $x_i \in \{-1,0,+1\}$ for $i \in \{1,\ldots,n\}$, with the promise that $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (where the sum is over $\mathbb{Z}$). Then what is the complexity of determining if $x = 1$?

Notice that trivially the problem lies in $\cap_{m \geq 2}{\mathsf{AC}^0[m]}$ because $x \equiv 1\bmod{m}$ iff $x = 1$. Question is: does the problem lie in
$\mathsf{AC}^0$? If so, what is the circuit witnessing this? If not, how does one prove this?


texts: "Largest" class properly contained in PSPACE for a random oracle

texts:
Green [1] showed that $PP^{PH}$ is properly contained in $PSPACE$ relative to some oracle. Around the same time, in the famous "voting polynomials" paper [2], it was shown that $PP$ is properly contained in $PSPACE$ for a random oracle.

Question

  Is it also true that $PP^{PH}$ is properly contained in $PSPACE$ relative to a random oracle?

Observations

From what I understand, this can be proved by showing that "small" $AC^{0}$ circuits with a MAJORITY gate at the root fail to compute the PARITY function even on a (1/2+small)-fraction of inputs. I found such claim in Theorem 6 of [3]. Does this reasoning make sense? Am I interpreting Klivans' theorem in the right way?
I wrote "largest" class in the title, because I am also interested in classes that have this same property and that are uncomparable with $PP^{PH}$.

Motivations

Nostalgia for 90s research :)
I am looking at similar questions in quantum complexity theory.

References

Frederic Green, An oracle separating $\oplus P$ from $PP^{PH}$, Information Processing Letters, '91
James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich, The expressive power of voting polynomials, STOC '91
Adam Klivans, On the Derandomization of Constant Depth Circuits, RANDOM '01


texts: Is the complexity of ARC KAYLES still open?

texts:
In the problem NODE KAYLES two opposing players take turns playing on an undirected graph. In each turn, a player selects a vertex $u$ and removes $u$ and all its neighbors from the graph. The first player who is unable to select a vertex loses. In other words, the two players take turns selecting vertices under the constraint that the set of all selected vertices must be independent.

NODE KAYLES was shown to be PSPACE-complete by Schaefer in the late '70s. (See "On the complexity of some two-person perfect-information games", Thomas J. Schaefer, JCSS 1978). In the same paper, the edge version of the game, called there ARC KAYLES, is mentioned as an open problem. In ARC KAYLES, players take turns selecting edges (rather than vertices) under the constraint that the set of edges selected is independent (i.e. a matching).

My question is if the complexity of ARC KAYLES is still open. I have seen a few more recent papers on NODE KAYLES (e.g. "Kayles and Nimbers", by Bodlaender and Kratsch) but I haven't been able to find a reference on any follow-up work regarding ARC KAYLES. Is it by now known that ARC KAYLES is PSPACE-complete?


texts: Is there a characteristic function of a tree?

texts:
Consider a set of trees $T=\{T_{\alpha}\}$, and for any $T_{\alpha}\in T$, $T_{\alpha}$ has $n$ nodes. Can we find a ‘characteristic’ function $f:T\longmapsto{\mathbb{R}}$ describing trees' topological feature? That is to say, $T_{\alpha}\simeq T_{\beta}$ only and if only $f(T_{\alpha})=f(T_{\beta})$, and if $T_{\alpha}$ is more similar to $T_{\gamma}$ than $T_{\beta}$ is, then $|f(T_{\alpha})-f(T_{\gamma})|<|f(T_{\beta})-f(T_{\gamma})|$.

It seems that $f$ is a topological invariant of $T$ and this is a very natural thought. I'm not much familiar with graph theory and I'm wondering if someone has considered this problem before. There are two aspects about this problem, one is such $f$ exists, and another is how to calculate $f$， or what the algorithm is.


texts: Is CoC inconsistent with cnat_ind axiom?

texts:
It is not possible to derive induction for Church-encoded datatypes on the Calculus of Constructions (source). Moreover, according to the accepted answer to another question, it is also not possible to derive induction for Church-encoded datatypes on CoIC, despite the presence of inductive datatypes. As such, I wonder if we assume induction for Church-encoded Nat, cnat_ind; that is:

cnat_ind :
  (n : CNat) ->
  (P : CNat -> Type) ->
  (S : ∀ (n : CNat) -> P n -> P (csucc n)) ->
  (Z : P czero) ->
  P n

where CNat, csucc and czero are the usual Church-encoded Nat type and constructors, would that allow us to inhabit the empty type ∀ (P : *) -> P?


texts:
I am looking for a concept in type theory that I am sure has probably been explored, but do not know the name behind.

Let's consider a ML-like language with product and sum types and a Hindley-Milner like type system. I'll use OCaml syntax.

I'm wondering about ways two different values can be different.

Use

My use case is writing "clearer" error messages in a xUnit-like library: if two values are different when they were expected to be equal, this can help build a clearer better message:

Before:

  Values differ: expected {x = [1;2;3;4], y = "a long string"}, got {x = [1;2;3;3], y = "a long string"}

After:

  Values differ: at position .x[3], expected 4, got 3.

(there might be a relation with functional lenses since we're ultimately constructing a lens to a smaller value which differs).

Product types

For example:

type p =
  { x : int
  ; y : string
  }

Equality can be defined as:

let equal a b =
  equal_int a.x b.x && equal_string a.y b.y

But it's also possible to reify the differences:

type delta_p =
  | Equal
  | Diff_x of int * int
  | Diff_y of string * string

let diff_p a b =
  if not (equal_int a.x b.x) then
    Diff_x (a.x, b.x)
  else if not (equal_string a.y b.y) then
    Diff_y (a.y, b.y)
  else
    Equal

(it might make sense to define a delta_int type as int * int to show that it is recursive)

Sum types

For a sum type there are more ways to differ: having a different constructor, or a different value

type s = X of int | Y of string

type ctor_s =
  | Ctor_X
  | Ctor_Y

type delta_s =
  | Equal
  | Diff_ctor of ctor_s * ctor_s
  | Diff_X of int * int
  | Diff_Y of string * string

let diff_s a b = match (a, b) with
  | X xa, X xb ->
    if equal_int xa xb then
      Equal
    else
      Diff_X (xa, xb)
  | (* Y case similar *)
  | X _, Y _ -> Diff_ctor (Ctor_X, Ctor_Y)
  | Y _, X _ -> Diff_ctor (Ctor_Y, Ctor_X)

What's the name of this concept? Where can I learn more about this?

Thanks!


texts: Decentralized algorithm for determining influential nodes in social networks

texts:
In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social networks.

Basically the algorithm goes as follows:

$S = {\rm empty~set}$
pick the node with highest individual influence, call it $v_1$; $S = S\cup v_1$
remove $v_1$ and all edges connecting $v_1$ to the rest of the network
repeat until $S$ has $k$ vertices

I have two questions about influential nodes in social networks.
a) Is there any algorithm to find the solution, or an approximation of it in a decentralized fashion?
b) Did anyone apply other algorithms, such as Page-Rank and similar, to solve the same problem?


texts: Can $L=SL$ be shown with the replacement product instead of the zig-zag product?

texts:
(This is a bit of follow-up to https://cstheory.stackexchange.com/posts/comments/93266 but is a distinct enough question I though it should be on its own.)

In Omer Reingold's logspace USTCON algorithm, he uses zig-zag products; the zig-zag product is attractive in that if $H$ is a good expander, then $G{\,\,\,\mathbin{{
      \hspace{-.4em}\bigcirc\hspace{-.75em}{\rm z}\hspace{.15em}}}\,} H$ is "not much worse" of an expander then $G$. Then $G$ can be powered, to make it a much better expander; and balancing these two operations allows him to turn $G$ into a larger, good expander.

The replacement product is a few senses, simpler to understand: steps on it naturally correspond to a step in either $G$ or $H$. In "Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders", Reingold at all actually mention that replacement products aren't much worse than zig-zag products: the cube of the replacement product contains all of the edges of the zig-zag product, so has at least as good connectivity.

This means that the proof for $L=SL$ should be able to accomplished with only the replacement product, instead of the zig-zag product. In terms of the loosest bound: instead of taking the 8th power of the graph, the 24th power is taken; and then the replacement product is used instead. This means taking a $(D^{48}, D, 1/2)$ graph to start with instead of $(D^{16}, D, 1/2)$, but these also exist by the same construction they used (just plugging in different numbers).

Assuming that I'm not somehow totally misled in the above -- why is the result so often stated with zig-zag products? Replacement products seem more natural, and clearly fulfill the same requirements. Currently the only proof of their expansion properties I could find was in terms of zig-zag products, but I don't expect it to be too difficult to deal with them directly. Maybe my question really should be -- why are zig-zag products preferred over replacement products?


texts:
This question is two-fold, and is mainly reference-oriented:

Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know the proof is long and difficult, but surely there must be key ideas that can be communicated in an easier way.
Are there other relations on graphs that can be shown to be well quasi-orders, maybe in a simpler way than for the minor relation? (obviously I am not interested in trivial results here, like comparing sizes). Directed graphs are also in the scope of the question.


texts: Probability of random variable $X$ less than $max(Y_i)$

texts:
For $\lambda > \mu$, consider independent random variables (i)  $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$.

Question : Can we upper-bound the following?
$$\mathbb{P}\big(X\geq\max(Y_1, Y_2)\big)$$


texts: How to check if a number is a perfect power in polynomial time

texts: The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in details. Can someone tell me how to do this in polynomial time? Thanks.


texts: Busy Beavers: quadratic relation of output size and running time?

texts:
When glancing at the running times and output sizes of some Busy Beaver candidates on this page, I find that there seems to be a rough (up to some small power of 10) quadratic relation between output size and running time. Do you know a heuristic argument or even proof for this? Is it related to the computational model of Turing machines, or is it some more general principle?

Because (under the assumption of a computational model where the binary description of the algorithm and the algorithms' length can be read out and operated on by the program) no program can decide the halting problem for all programs a little bit longer than itself and access to the busy beaver program of some length entails ability to solve the Halting problem for that length by checking whether a given program runs longer than the busy beaver, it can't be that this is somehow a test (for said programs with efficient access to memory) that will vastly constrain the possible candidates for all sizes, as then a smaller number of supplied bits would suffice to generate the busy beaver and thee would be a program could solve the halting problem for somewhat bigger programs. If you sharpen the notion of "vastly", this reasoning will also apply to Turing machines.


texts:
I am studying program analysis and synthesis, I was reading a presentation
about some data flow analysis.

I can't seem to understand why $$\bigcap_{s'\in\text{pred (s)}}\text{Out}(s')$$
and $$\operatorname{Gen}(s)\cup(\operatorname{In}(s)\setminus \operatorname{Kill}(s))$$ is monotone, as claimed in
slide 22.

I don't even understand exactly what is the function that is claimed to be monotone.
Can anyone please help ? any help is greatly appreciated!

*This was cross-posted on Math.SE a couple of days ago


texts: Finding the closest point to a sets of discrete points

texts:
In a paper I am reviewing, the authors define the following problem and construct an algorithm. They give no further references and I suspect it has appeared somewhere in the literature before.

Let $P_1,\ldots,P_n$ be sets of points in a space with a metric $d$. Define the distance to a set as
    $$\operatorname{dist}(x, P_i) = \min\{ d(x,p) \,|\, x \in P_i\}.$$
The problem is to compute
    $$\min_x \sum_{i=1}^n \operatorname{dist}(x, P_i).$$
What is the name of this problem? Has it been discussed in the literature? What if $d(x,P_i) = ||x - P_i||_2?$


texts: Minimal context-free Grammar for a special one-letter Language

texts:
For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given:
$$
L_{n,m} = \{ a^i | 2 \leq i \leq  m \} \setminus \{a^{2^i}|2 \leq i \leq  n-2\}
$$
Find and prove a minimal context-free grammar according to the number of rules that generates $L_{n,m}$.

I think this cannot be done with a fewer number of rules as shown below:
$$
P = \{S \rightarrow a^{2^{i-1} + 1} A^{2^{i-1} - 2} | 2 \leq i \leq n-2 \} \cup \\ \{S \rightarrow a^{2^{n-2}+1}A^{m - (2^{n-2}+1)}, A \rightarrow a, A \rightarrow \epsilon\}
$$

Note: For the "complement" language
$$\{a^{2^i}|1 \leq i \leq  n\}$$
it’s known that a minimal context-free grammar needs exactly $n$ rules (one rule for each word $a^{2^i}$).

Any suggestions to prove or disprove my conjecture?


texts: Various conjectures which is similar to Log Rank conjecture

texts:
Log rank conjecture is one of the most famous open problems in the area of communication compleixty.

Lets consider the two party cdommunication complexity. Alice and Bob have $n$ bit strings $a,b$ , respectively, and they wish to compute arbitrary boolean function $f(a,b)$.

Communication matrix of $f$ is a $2^{n}\times 2^{n}$ matrix whose indices  of row (column) corresponds to the inputs of Alice (Bob) and each entry $M_f (a,b)$ correspond to function value $f(a,b)$.

Log rank conjecture asserts that $CC(f) = (\log rank (M_{f}))^{O(1)}$

On the other hand, rank is a crucial role in the linea algebra and similar concepts of rank are considered.

  QUESTION:I am looking for similar conjectures in the area of communication compleixty and related compleixty theoretic areas, similar-seeming conjectures without the communication complexity machinery, similar-seeming conjectures in linear algebra.Is there an appropriate reference ?


texts: How to treat dynamic memory allocation in algorithm analysis?

texts:
I have an algorithm in which I want to dynamically allocate some memory.
Let's say that I have N numbers and that I want to describe some binary relation over them. To do so I want to create a N*N matrix. But how fast is the memory allocation itself regarding N?

I do not want to zero out the new memory. In fact I do not want to touch it at all in this moment - I just want to allocate it and be sure that all of it is there.

I understand that the answer is: how is the memory allocation implemented?
Bit I hope that you can give me some upper bounds that are common for most of the popular memory management strategies.


texts: At what parameters is following $NP$-hard?

texts:
Problem Instances at given $\alpha>0$.

$(1)$ Given $a_1,\dots,a_{n^\alpha}\in\Bbb Z$ with $|a_i|\in(2^{n-1},2^n-1)$ is there a subset of that sums to $0$?

$(2)$ Given $a_1,\dots,a_{n}\in\Bbb Z$ with $|a_i|\in(2^{n-1},2^n-1)$ is there a subset of size at most $n^\alpha$ that sums to $0$?

At what range of $\alpha$ are these problems $NP$-hard?

Is the problem studied anywhere?


texts:
What is the complexity of enumerating all connected induced subgraphs from an undirected graph.

Also, Is the complexity of enumerating all maximal connected induced subgraphs the same?


texts:
Given an instance of MAX-2-SAT, let us call an assignment of variables a "local maximum" if changing the value of any variable reduces the number of satisfied clauses.  My question is, how many local maxima can an instance of MAX-2-SAT have?  Clearly it must be less than $2^N$, but how large can it be?

To illustrate, suppose instead of considering MAX-2-SAT, we considered MAX-k-CSP with $k=N$ and a single clause.  This means that we can choose any function of $N$ variables as the truth value of the clause.  If we pick, for example, the parity function so that the clause is true if parity is odd, then there are $2^{N-1}$ local maxima (any odd parity configuration is a local maximum as flipping any spin makes it even parity).  On the other hand, I would guess that going from MAX-k-CSP to MAX-2-SAT will significantly reduce the maximum possible number of local maxima.

I would also be interested if anyone knows the answer to the number of local maximum for MAX-k-SAT and MAX-k-CSP for $k>2$ but $k=O(1)$.  I would also be interested in the answer in the case of bounded ratio of number of clauses to number of variables.


texts: Rademacher complexity beyond the agnostic setting

texts:
The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf. Here the quantity on the LHS that Rademacher complexity is trying to upperbound is given as, $L_{\phi}(\hat{f}_{\phi}^*)-\min_{f \in F} L_{\phi}(f)$ where $F$ is some "hypothesis class" of functions mapping $ f :X \rightarrow D$, $\phi : D \times Y \rightarrow [0,1]$ is the "loss function", "$\phi-$"loss of any function $g : X \rightarrow D$ is defined as, $L_\phi(g) = \mathbb{E}[\phi(f(x),y)]$ - where the expectation is taken over some distribution over the points $(x,y) \in X \times Y$ and $\hat{f}_{\phi}^*$ is what the ERM returns over some $m$ samples i.e $\hat{f}_{\phi}^* = \mathrm{argmin}_{f \in F} \frac{1}{m} \sum_{i=1}^m \phi(f(x_i),y_i)$.
The above setting is called ``agnostic" because at no point was it assumed that, $\exists$ any ground-truth labelling function $L \in F$ such that $y = L(x)$ but rather the class $F$ is to be seen to be trying to learn via empirical risk minimization a distribution, say ${\cal D}$, over $X \times Y$.
My question is 3 fold , is there any analogue of this Theorem $2.4$ when,
(a)
an existence of a $L$ is assumed with $L$ may or maynot be in $F$. (the later is I guess often called the ``realizable setting") (...I have seen some papers trying to bound generalization error of a specific algorithm in the realizable setting but I somehow dont see Rademacher complexity defined in those settings!..)
(b)
the loss function $\phi$ is not assumed to be bounded above but only assumed to be bounded below.
(c)
AND most importantly, say I have a class of labelling functions ${\cal L}$ mapping $X \rightarrow Y$ and I want to say the following, "Given a loss function $\phi$, irrespective of which member of ${\cal L}$ labels the data (maybe also irrespective of the distribution over $X$ used to measure $L_{\phi}$) the member of class $F$ obtained via ERM on the data, can never generalize well". Is there a version of Rademacher complexity which captures this?


texts: Clustering massive data sets in practice

texts:
If you have a very large data set of $n$ vectors and you want to cluster them according to some metric measure, what is the current state of the art when you can not afford to do more than $\Theta(n)$ work?  I am interested in methods that work well in practice as well as having nice theoretical properties.

A web search brings up "A sublinear time approximation scheme for clustering in metric spaces" by P. Indyk as the most cited paper in the area.


texts: Complexity of SAT parameterized by treewidth

texts:
Many papers state that Boolean satisfiability is in FPT when parameterized by primal, dual, or incidence treewidth. What are the best known time complexities of these parameterized algorithms? In particular, I would expect something like $O(2^{tw} nm)$ time complexity for at least primal treewidth, but I cannot find a reference for it.

Also, how about (weighted) Max-SAT and #SAT?


texts: Squared Hellinger distance between Binomial(n,p) and Binomial(n+1,p)

texts:
I came across a claim in a paper Trace reconstruction revisited (in Lemma 11), which is basically that the squared Hellinger distance between Binomial$(n,p)$ and Binomial$(n+1,p)$ grows as $O(1/n)$. $p$ is a small positive number less than $\frac{1}{2}$.

I've been trying to prove it but have not been able to see this. Is there an easy way to see this?


texts: Theoretical computer science self-study resources for programmers

texts:
I am a pretty proficient software engineer, but
I don't know much theory.
I want to learn more theory.
Particular topics that I am interested in are:
computational complexity, formal languages, and type theory.
But I am at a loss as for how to begin learning about these fields.

  What resources would you recommend to someone
  who wants to learn more theory through self-study?
  Are there any theoretical computer science self-study guides
  for software engineers?


texts:
We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $I_i = [s_i,t_i]$ associated with it, where $s_i$ is the start vertex and $t_i$ is the end vertex. A set of requests $\mathcal{R}$ is called feasible, if the total demand of all requests in $\mathcal{R}$ passing through any edge $e$ does not exceed it's capacity, i.e., $\sum_{i:e \in R_i, R_i \in \mathcal{R}} d_i \le c_e$ for all $e \in E$. The goal is to partition the requests $R_1,\ldots,R_k$ into a number of sets such that each set is feasible and the total number of sets is minimized. We can think of this as coloring the requests in such a manner so that requests in each color class are feasible and we want to minimize the number of colors.

Let $r_e = \frac{\sum_{i:e \in R_i} d_i}{c_e}$ be the congestion on edge $e$ and let $r = \max_{e \in E} r_e$ be the maximum congestion. Clearly, $r$ is a lower bound on the number of colors required.

We consider the online scenario, where the requests are coming one after another, and we have to assign a color to each request upon its arrival. What is the best online algorithm and hardness result (lower bound) known for this problem? In particular, for small values of $r$ what is the number of colors required? For $r = 1$, one color is sufficient. For $r = 2$ and $r = 3$ can we do it with small number of colors? What is the performance of first-fit for $r = 2$ and $r = 3$?


texts: Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed

texts:
The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the partition to have size exactly $k$?

Formally, given a graph $G(V, E)$ and integer $k$, find the set $S \subset V$, such that $|S| = k$ and the number of edges between $S$ and $V \setminus S$ is maximized. What is the name of this problem (for example, if $k = |V|/2$, this is known as MAX-BISECTION)? Does it become easier to approximate in polynomial time, if $k$ is $polylog(|V|)$?


texts: Minimum number of triangles required to cover a complete graph?

texts:
Let $K_n$ be a complete graph, I am interested in knowing the minimum number of triangles required to get a edge cover of $K_n$. In case there is no closed-form solution to this problem, then I would like to know the best known upper bound (the naive bound is $n\choose 3$ i.e all possible triangles).
An example:
Let $K_4 = \{1,2,3,4\}$, then any three of the following triangles make a full edge cover on $K_4$:
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}

Furthermore, I would also like to add a generalisation i.e you assign a weight $w$ to each triangle such that $w \in [0,1] $, now I want to have a cover that minimises the sum of $w$, given that each edge's weight contribution sums to more than one.
What is the lower bound on this sum ?


texts: possible bridge between group growth theory and complexity theory?

texts:
RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with complexity theory. (of course there are other deep known links between TCS/ group theory.)

  has anyone seen a link between group growth theory and complexity theory? eg have any complexity class separations been found expressible in this framework, etc?

(eg conceivably there could be an intermediate link via boolean circuits etc.)


texts: Which areas of TCS are better for a math bachelor?

texts:
I am graduating from mathemetics bachelor program and I've been accepted for masters degree in mathematics. But I am not sure to pursue math, hence I am looking for other field I can do research. I am going to study potenial theory in the masters degree in math so I am good at analysis, particularly in measure theory. I also took some statistics courses, java and matlab. Moreover, I really like computers so I educated myself on some other stuff(I do some game modding and photoshop)

Some friends of mine suggested machine learning but they are undergrad and they don't really know the subject well. So my question is what fields/areas of computer science I can work on for PhD and what should I learn.

Or in this respect can I work on CS(Phd) as a math grad?

(I've read the similar questions but they are only similar. So I appreciate any help.)

Edit: In Math M.S program I only have one none-technical elective and I will get some undergrad CS lectures(additional). So, as @RB suggested, I am asking for the areas that require realtively less CS and more math. But note that I am willing to study/work hard.


texts: Can interaction combinators implement any interaction net efficiently?

texts: It is widely known that interaction combinators can implement any interaction net. My question is, can they do so efficiently? I.e., is it possible to prove that there is no interaction net system that can't be emulated on interaction combinators with the same number of reductions up to a finite constant?


texts: Problems that are counter-intuitively solvable in practice?

texts:
Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in algorithms or complexity before. Not surprisingly, a lot of notions seemed strange at first but made sense with some examples (PTIME, intractability, uncomputability), while others seem to come more natural (problem classification via reductions, time and space as resources, asymptotic analysis). Everything was going great until I accidentally admitted that SAT can be solved efficiently* in practice... And just like that, I lost them. It didn't matter how convincingly I was trying to argue for theory, the kid was convinced that it was all artificial crap math that he should not care for. Well...

¯\_(ツ)_/¯

No, I was not heart-broken, nor did I really care about what he thought, that's not the point of this question. Our conversation had me thinking of a different question,

  How much do I really know about problems that are theoretically
  intractable (superpolynomial time complexity) but practically
  solvable (via heuristics, approximations, SAT-solvers etc.)?

I realized, not much. I know that there are some very efficient SAT-solvers that solve enormous instances efficiently, that Simplex works great in practice, and maybe a few more problems or algorithms. Can you help me paint a more complete picture? Which well-known problems or even classes of problems are in this category?

TL;DR: What are problems that are counter-intuitively solvable in practice? Is there an (updated) resource to read more? Do we have a characterization for them? And, finally, as a general discussion question, shouldn't we?

EDIT #1: In trying to answer my last discussion question about such a characterization, I was introduced to smoothed analysis of algorithms, a concept introduced by Daniel Spielman and Shang-Hua Teng in [1] that continuously interpolates between the worst-case and average-case analyses of algorithms. It is not exactly the characterization discussed above, but it captures the same concept, and I found it interesting.

[1] Spielman, Daniel A., and Shang-Hua Teng. "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time." Journal of the ACM (JACM) 51, no. 3 (2004): 385-463.


texts: Calculation of sum of weights of nodes in a tree graph

texts:
Updated
There's a real production project related to real estate properties around the world. The data has a structure of nested nodes. E.g. end nodes which have no outgoing edges (red) are properties and all nodes which have outgoing edges (blue) are just names of groups for those properties like "in Germany" or "residential apartments" group names. So in terms of graphs it is a closed and directional tree-like graph with terminal states as real-estate properties and all transitional nodes as group-names.
I am sure there is an efficient way to count the number of all terminal nodes (aka "properties", red) which belong to a given parent node (aka "group-name", blue). I just do not know what algorithms can be used to efficiently calculate this with as little CPU/Memory capacity as possible. Can you please suggest?


texts: I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, weighted/unweighted) of the graphs in the source if they are known.


texts: Quick Sampling from Probability Distribution: Is there a name for this algorithm?

texts:
I'm trying to quickly sample from a near-uniform discrete probability distribution exactly once without calculating the entire CDF. Here's the algorithm.

Givens:

$N,$ the number of elements to sample from
$p : \{n \in \mathbb{N} | n < N\} \to \mathbb{R}[0,1],$ the probability distribution function
$M : \mathbb{R} = \max_{\forall n < N} p(n)$, the maximum probability

The algorithm is as follows (pseudocode):

define select(N, p, M):
    LET i := a random natural number < N
    WITH PROBABILITY p(i) / M:
        return i
    ELSE:
        return select(N, p, M)

The distribution that this algorithm selects is

$$\mathbf{q} = \frac{1}{N}\sum_{i=0}^N\left(\frac{p_i}{M}\mathbf{e_i} + \left(1-\frac{p_i}{M}\right)\mathbf q\right)$$

Solving for $\mathbf q$:

$$N\mathbf{q} = \frac{1}{M}\mathbf p + N\mathbf q - \frac{1}{M}\mathbf q$$

$$\mathbf p = \mathbf q$$

And the time complexity is

$$t = \frac{1}{n}\sum_{i=0}^n \left(\frac{p_i}{M} \cdot 1 + (1 + t)\left(1-\frac{p_i}{M}\right)\right)$$

$$Nt = \frac{1}{M} + N(1+t) - \frac{t+1}{M}$$

$$0 = N - \frac{t}{M}$$
$$t = MN$$

So for a near-uniform distribution, where $M = O(N^{-1})$ then the algorithm is $O(1)$.

My question is: is there a name for this algorithm?


texts: The source of the modular decomposition graph

texts:
When introducing graph modular decomposition, most authors use the 11-vertex graph, which I copy from wikipedia.

The question is who is (are) the original designer of it. (I'm not asking who drew this graph for wikipedia, but the original source of it.)

The wikipedia page was created in December 2006. The earliest source I can find is the Habilitation thesis of Christophe Paul dated on May 17, 2006. (I didn't search intensively.)


texts: Spectral Graph Theory and Matroid Theory

texts:
I have just started grad school this year and I have been into Spectral Graph Theory for some time now. Recently I got introduced to Matroid Theory and although I know the field has been around for decades, it somehow feels "hot" lately.

I know that Matroid Theory is related to both Graph Theory and Linear Algebra. The question is though, is there a connection to Spectral Graph Theory? Has there been any work in trying to combine results of the two fields? Does anyone have the intuition that there is some common ground of potentially interesting and useful results?

Thank you in advance,


texts: Reference request: complexity of $k$-partite $k$-SAT

texts:
Let's consider following variation of $k$-SAT that I will call $k$-partite $k$-SAT:

given $n$ variables that are divided into $k$ groups and a $k$-SAT formula $\phi$ such that each clause has literal from each group. Is $\phi$ satisfiable?

There is an almost straightforward reduction from $k$-SAT to $k$-partite $k$-SAT that takes formula on $n$ variables and produces formula on $kn$ variables. This proves that this problem is exponentially hard under $ETH$.

On the other hand there a very simple $O^*(2^{(1-\frac{2}{k})n})$ time algorithm for this problem: branch over all variables except 2 groups. You will end up with $2$-SAT problem, that can be solved in polynomial time.

As we don't know algorithms with this kind of savings for $k$-SAT, I'd be surprised if there is a simple reduction from $k$-SAT to $k$-partite $k$-SAT that preserves number of variables.

So I have following question:

Was this problem studied before?
Is there an algorithm with running time $O^*(2^{(1-\epsilon)n})$, where $\epsilon$ is independent on $k$?
If answer for previous question is no, do we know that complexity goes to $2^n$ as $k$ goes to infinity under $SETH$?


texts: Symbolic Execution of the Quine-McCluskey Algorithim

texts:
If I understand correctly, the Quine–McCluskey algorithm will find the minimum boolean formula size for given boolean function.  Has there been any attempts to (for lack of a better term) symbolically execute the algorithm with a class of boolean functions rather than a single one to find a circuit unconditional lower bound?  Just curious to see if anybody has tried this before, and if so,(presumably) why it wouldn't work.

https://en.wikipedia.org/wiki/Symbolic_execution


texts: Why is the "free store" memory called the "heap"?

texts:
Does it have anything to do with the heap data structure, for example the Buddy blocks implementation, or does it only take the literal English meaning of the word (a big pile)?

I know heap memory is more practical than theoretical, but there's no Stack Exchange for "Practical Computer Science" yet.


texts:
Consider a Generalized Sequential Machine (GSM; or nearly equivalently -- an FSM transducer). These machines are closed under compositions. A composition of two GSMs $f(x)$ and $g(x)$ can be written as a function $h(x) = f(g(x))$.  I am interested in the inverse problem:

Given a transducer $h(x)$, decompose it into a composition of two transducers $f(g(x))$. (One of the $f,g$ might be given.)

Has this question been studied?

Motivation
This question that occurred to me many years ago and is similar to a recent question by Dave Lang. After some back-and-forth we agree that it seems basic, yet not to under-studied. Although, Dave Lang did find a potentially related paper: Weber, A. (1996). Decomposing a k-valued transducer into k unambiguous ones. Informatique théorique et applications, 30(5): 379-413.
I suspect that this is linked to the Krohn-Rhodes decomposition and that through the natural correspondence between TMs and transducers, we might find hidden structure that could be useful in termination analysis and automated theorem proving.


texts: DAG reachability with O(n log n) space and O(log n)-time queries?

texts:
For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time?  Ideally I seek an algorithm using only O(log n) space per vertex and logarithmic time where $n=|V|+|E|$.

It seemed intuitively obvious to me that a data structure like this ought to exist, based on some generalization of standard sorting algorithms.  But I was surprised that I couldn't find any.  Everything I came across either made assumptions about the graph (e.g. planarity) or solved a harder problem in quadratic time/space (e.g. queries interleaved with graph modifications).

The Wikipedia page on Reachability only covers one general algorithm (Floyd-Warshall); the rest of the page deals with special cases involving assumptions like the graph being planar (it isn't).

The most commonly cited paper in this space appears to be Amortized efficiency of a path retrieval data structure, but this and all the papers it cites involve either O(n^2) space or else O(n^2) time in order to allow updates to the graph interleaved with the queries (i.e. no preprocessing).

This question wasn't answered, but it deals with the harder problem of allowing edge insertions interleaved with queries.

This question asked for a persistent (pure functional) data structure, which isn't required here.  The "Succinct Posets" paper needs $O(n^2)$ space but it achieves $O(1)$-time queries; I seek a worse-time, better-space algorithm.

Mostly looking for a foothold in the literature here.  If there's a survey paper on graph reachability that doesn't spend 99% of its time on the planar-graph case, that would help.


texts: "Fast" approximation algorithm for geometric hitting set of same-height rectangles

texts:
In the Geometric Hitting Set problem, we are given a set of $m$ geometric objects and a set of $n$ points in $\mathbb{R}^2$, and we wish to find a small subset of the points that hits all the objects.
Geometric Hitting Set has a PTAS running in time $mn^{O(1/\epsilon^2)}$ for various types of geometric objects, including pseudo-disks and same-height rectangles (Mustapha-Ray, 2010).
I am interested in approximation algorithms that achieve a constant-factor approximation, but that run relatively fast, say, $O((m+n)^{20})$. For example, for pseudo-disk objects, such algorithms exist (Bus-Garg-Mustapaha-Ray, 2015).
My question: does there exist a comparable algorithm for same-height rectangle objects?


texts:
In the recent movie called The Imitation Game, there is a affirmation that Turing was building his theoretical machine.
That machine is the Bombe Machine. Is this machine really equivalent to a Turing Machine ?


texts: Efficient algorithm for a particular graph closure property

texts:
In the context of an unusual compiler problem, I have a graph in which the vertices are variables, and the edges correspond to whether the instruction set has an instruction that copies the source vertex to the target vertex.  The instruction set also has the unusual property that the instructions may destroy (overwrite with non-predictable values) the contents of some of the variables.  Hence the edges are labeled with sets:  subsets of the (fixed) set of all variables that are destroyed by the instruction.

So for example, I might have instructions like the following:

a -> b, clobber set = {d}
b -> c, clobber set = {}
a -> c, clobber set = {d,f}

Note that there is a direct path from a -> c, but that there is also an indirect path from a -> b -> c, where the union of the clobber sets is {d}, i.e., a strict subset of the clobber set from the direct path, namely {d,f}.  Hence the path a -> b -> c should be preferred as it has a lesser effect on the other variables.

Consider the following variation on the above example:

a -> b, clobber set = {e}
b -> c, clobber set = {}
a -> c, clobber set = {d,f}

By similar reasoning, we have two paths from a -> c:  the direct one, which clobbers {d,f} and the indirect one a -> b -> c which clobbers {e}.  Given that {d,f} and {e} are incomparable subsets of the variable set, we would like to retain information about both of these paths.

So the problem is as follows:  given such a directed graph with edges labeled with sets, compute all "minimal" paths through the graph with respect to the clobber sets.  For the first example, we should return a -> b: {d}, b -> c: {}, a -> c: {d}.  For the second example, we should return a -> b: {e}, b -> c: {}, a -> c: {d,f}, a -> c: {e} (where this last fact was derived from the other edges).

The problem has some flavor of a shortest-paths problem, but given the weaker partial ordering rather than the stricter total ordering on the edge labels, the existing algorithms are inapplicable.

References to literature would also be appreciated.


texts:
Can someone kindly help clarify as to exactly what is the generally accepted definition of the "sparsest cut" problem for a graph?
(Isn't the set which achieves the Cheeger constant for a graph, the same set which would be said to have the "sparsest cut"? http://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29)

I guess one can think of the ARV algorithm to be giving a polynomial time $O(\sqrt{log (n)})$-approximation algorithm to get the Cheeger constant. Right?

Now consider the quantity, $N-cut = \sum_{i=1}^{k} \frac { E(S_i,V /\ S_i)}{Vol(S_i) }$ where $S_i$ are $k$ disjoint sets partitioning the graph and $Vol(S_i)$ is the sum of the degrees of the vertices in $S_i$.
Does the ARV algorithm automatically also give an approxmation algorithm for finding the sets $S_i$ which will give the lowest value of N-cut? (if not, then what is the best known answer to this?)

This paper I believe gives the best known approximation algorithm to the Cheeger constant, http://www.cs.princeton.edu/~arora/pubs/AHK.pdf


texts: I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic effects and handlers, people mention effects that are not algebraic, like backtracking. How does one can tell an algebraic effect apart from a non-algebraic one?


texts: How do I get started in theoretical CS ?

texts:
I'm a freshmen studying computer science and I already know that I want to go into academia with focus of theoretical comp sci. I already read some of papers referenced in this question and this question convinced me further.

What should I be doing now, as an undergrad, to get involved in the field? What can I do to prepare for research in the field?


texts: Restricting entries of unitary operators to real numbers and universal gate sets

texts:
In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-trivial rotations" and "near-trivial phase shifts".

"Near-trivial rotations" are $d$-dimensional unitary matrices that act as the identity on all but 2 dimensions, but act as a rotation in the plane spanned by those two dimensions (i.e. has a 2x2 submatrix of the form:

$
 \begin{pmatrix}
  \cos{\theta} & -\sin{\theta} \\
  \sin{\theta} & \cos{\theta} \\
 \end{pmatrix}
$

for some $\theta$).

"Near-trivial phase shifts" are $d$-dimensional unitary matrices that act as the identity on all but 1 dimension, but apply a factor of $e^{i\theta}$ for some $\theta$ to that one dimension.

Furthermore, they show that only one rotation angle is needed (for both the rotation and phase shift unitaries), given that the angle is an irrational multiple of $2\pi$ (BV set the angle to $2\pi\sum_{j=1}^{\infty}{2^{-2^j}}$.

Subsequent papers on quantum complexity theory (like that by Adleman et al or Fortnow and Rogers) claim that the B-V result implies that universal quantum computation can be accomplished with unitary operators whose entries are in $\mathbb{R}$.

How does this follow? I can understand that a product of near-trivial rotation matrices will give you a unitary matrix with real entries, but what about the phase shift matrices?

That is: if you are only able perform near-trivial rotations, and phase shift matrices where the entries of the matrix are either $0,\pm 1$, can we efficiently approximate all other phase shift matrices?

I suspect that this implication is not immediately obvious, and the proper proof for it would resemble the proof that Deutsch's Toffoli-like gate is universal - or am I missing something very obvious?


texts: In what complexity classes other than $NP$ are these problems related to unary languages?

texts:
If I remember correctly saw this reduction in
a paper can't find at the moment.

Consider the following NP-complete variation
of the Subset Sum problem.

Given a set of positive integers $S=\{x_1,\ldots ,x_n\}$ and
integer $t$, is there a subset of $S$ that sums to $t$?

There is polynomial reduction from Subset Sum to
decision if a word is in an unary language which is
Context-free grammar (CFG).

The unary CFG $G$ is over alphabet $\Sigma=\{1\}$ and the
productions are:

Express powers of $2$ in unary via $B_0 \to 1, B_{2^n} \to B_{2^{n-1}} B_{2^{n-1}}$. We have $|B_{2^n}|=|B_{2^{n-1}}|+|B_{2^{n-1}}|=2|B_{2^{n-1}}|$
This is bounded by the largest $x_i$.
Add non terminals $X_i$ corresponding to the values of $x_i$
(after writing $x_i$ in binary)
s.t. $|X_i|=x_i$, i.e. to express $x_i = 8 + 2 + 1$
add $X_i \to B_8 B_2 B_1$.
Express the powerset of $X_i$ via the productions
$P_1 \to \epsilon | X_1, P_n \to P_{n-1} | P_{n-1} X_n$
Set $S \to P_n$.

$L(G)$ is finite and the length of words in it
correspond to the sums of the subsets in $S$.

The Subset Sum has solution iff $1^t \in L(G)$.

Not sure about this, but there is a related problem:
construct unary CFG $F$ which accepts only $1^t$ using
(1) and (2).  Set $L=L(G) \cap L(F)$. $L$ is unary
language (possibly there are Turing machines corresponding
to it). $L$ is either empty or $1^t$, which is another
reduction to Subset Sum.

The question:

  In what complexity classes other than $NP$ are the
  reductions to problems related to unary language?

According to Wikipedia and
Complexity Zoo
unary languages
(TALLY) do not contain NP-complete problems unless $P=NP$
and the reductions are related to NP-complete problems.
This means unary languages are not expressible enough
unless a collapse.


texts: Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?

texts:
In chapter 10 of HAC (10.4.2), we see the well-known Feige-Fiat-Shamir identification protocol based on a zero-knowledge proof using the (presumed) difficulty of extracting square roots modulo a composite that is hard to factor.  I'll give the scheme in my own words (and hopefully get it right).

Let's start with a simpler scheme: let $n$ be a Blum integer (so $n=pq$ and each of $p$ and $q$ is 3 mod 4) of sufficiently large size that factoring is intractible.  Since $n$ is a Blum integer, half of the elements of $Z_n^*$ have Jacobi symbol +1 and the other half have -1.  For the +1 elements, half of those have square roots, and each element having a square root has four of them, exactly one being itself a square.

Now Peggy selects a random element $s$ from $Z_n^*$ and sets $v=s^2$.  She then sends $v$ to Victor.  Next is the protocol: Victor wishes to verify that Peggy knows a square root of $v$ and Peggy wishes to prove it to him without divulging anything about $s$ beyond the fact she knows such an $s$.

Peggy chooses a random $r$ in $Z_n^*$ and sends $r^2$ to Victor.
Victor equiprobably sends $b=0$ or $b=1$ back to Peggy.
Peggy sends $rs^b$ to Victor.

Victor can verify that Peggy has sent the correct answer by squaring what he receives and comparing to the correct result.  Of course, we repeat this interaction to reduce the chance that Peggy is just a lucky guesser. This protocol is claimed to be ZK; a proof can be found in various places (eg, Boaz Barak's lecture notes).

When we extend this protocol to make it more efficient it is called Feige-Fiat-Shamir; it's very similar to the above.  We start Peggy with $k$ random values $s_1\cdots s_k$ and random signs $t_1 = \pm 1, \cdots t_k  = \pm 1$ she publishes their squares as $v_1=t_1s_1^2, \cdots, v_k = t_ks_k^2$. In other words, we randomly negate some of the $v_i$.  Now

Peggy chooses a random $r$ in $Z_n^*$ and sends $r^2$ to Victor.
Victor equiprobably sends $k$ values $b_i$ from $\{0,1\}$ back to Peggy.
Peggy sends $r\Pi_{i=1}^ks_i^{b_i}$ to Victor.

My Question: Why are the $t_i$ sign bits necessary?  In parentheses, HAC notes that they are there as a technical requirement required to prove that no secret information is leaked.  The wikipedia page for Feige-Fiat-Shamir (which gets the protocol wrong) implies that without this a bit is leaked.

I cannot find an attack that extracts anything from Peggy if she omits the signs.


texts:
Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important?

Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem?

Why is it so hard?

All I'm looking for is the hindrances to solving $\mathsf{P}$ vs. $\mathsf{NP}$. Are there any theorems that help explain why $\mathsf{P}$ vs. $\mathsf{NP}$ is so hard?


texts:
Let $P$ be the class of formal languages that have polynomial-time decider, i.e. for each $L\in P$ there exists a Turing-machine $T$ such that for each $w\in L$ machine $T$ decides if $w\in L$ in polynomial time wrt the length of $w$.

Is it possible to define a grammar (in any "reasonable" sense) that could be used to define exactly the languages in $P$?


texts: Entropy of a byte in a compression algorithm?

texts:
I have a (fixed, long) string of bytes that I want to compress, $C$. I use a typical (good) lossless compression algorithm on it, to generate a compressed string of bytes, $C^*$. Then I define a random variable $X$ which samples a bit uniformly at random from $C^*$. Should I expect Prob[X = 0] to be close to 1/2?

A good compression algorithm is defined as one that achieves good information-theoretic bounds, such as Shannon coding.
A counter-example would be a compression algorithm that achieves, on average, a non-equal proportion of bits as the length of $C$ goes to infinity, where the contents of $C$ itself are chosen uniformly at random among all strings of that length.
This is to say the following: Let $S(n)$ be a string of length $n$ chosen uniformly at random. Let $C(s)$ be the result of the compression algorithm with input $s$. Let $X(s)$ denote the proportion of '0's in the string $s$. Then the question is whether $X(C(S(n)))$ necessarily converges to $1/2$ as $n$ goes to infinity.


texts: What are the consequences of Parity-L = P?

texts:
Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero number of acceptance paths), and which is further restricted to work in logarithmic space. Solving a linear system of equations over ℤ2 is a complete problem for Parity-L, and so Parity-L is contained in P.

What other complexity class relations would be known, if Parity-L and P were equal?


texts: On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

texts: I'm looking to link a problem I'm working on to a known NP-hard problem.  I think I can model my problem as a resource constrained shortest path problem.  However, the structure of my graph is not completely arbitrary.  Thus, it will be useful to know when RCSP becomes hard.  Is it hard for a DAG, for a planar DAG, for a DAG with bounded degree?  Any help would be greatly appreciated!


texts: Set cover in which some pairs of sets are forbidden

texts:
I'm trying to find an approximation algorithm for a variant of the weighted set cover problem.  However, this variation doesn't seem to let me apply the traditional set cover arguments for an approximation.  I'd like to know if anyone has ever encountered a similar problem (and, if possible, have info on the approximability of the problem - I'd be glad to have a factor $f$ approximation as there is for set cover, $f$ being the maximum frequency of some element $u \in U$).

Say we're given a ground set $U$, subsets $\mathcal{S} \subseteq U$, $\overline{\mathcal{S}} \subseteq U$ and a forbidden set of pairs of the form $\{S, \overline{S} \}$ with $S \in \mathcal{S}, \overline{S} \in \overline{\mathcal{S}}$.

We can assume that every set is in exactly one forbidden pair, i.e. there is a bijection between $\mathcal{S}$ and $\overline{\mathcal{S}}$ that forms the forbidden pairs.  We can also assume that $\cup_{S \in \mathcal{S}}S = \cup_{\overline{S} \in \overline{\mathcal{S}}}\overline{S} = U$, to guarantee the existence of a set cover without forbidden pairs.

Each set is also weighted by some weight function $w : \mathcal{S} \cup \overline{\mathcal{S}} \rightarrow \mathbb{R}$.

I want to find a set cover of minimum weight in which no forbidden pair is present.  That is, find $S_1, \ldots, S_k \in \mathcal{S} \cup \overline{\mathcal{S}}$ of minimum total weight such that $\cup_{1 \leq i \leq k}S_i = U$ such that for any $i, j$, $\{S_i, S_j\}$ doesn't form a forbidden pair.


texts: Efficiently computable variants of Kolmogorov complexity

texts:
Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:

It corresponds to an intuition of giving strings with patters or structure a lower complexity than strings without.
It allows us to define conditional complexity $K(x|y)$, or even better $K(x|O)$ for some oracle $O$.
It is sub-additive $K(x,y) \leq K(x) + K(y)$.

However it has an awful downside: returning $K(x)$ given $x$ is undecidable.
I have wondered if there is a variant of Kolmogorov complexity $K'(x)$ using a restricted model of computation (either by using weaker languages than TMs, or using resourced bounded TM) that preserves features (1) and (2) (feature (3) is a bonus, but not a must) while being efficiently computable?
The motivation for this question is for use in simulation studies of various toy-models of evolution. Thus an answer that has been used as a 'rough approximation' for Kolmogorov complexity in numeric work before is preferred. However, the goal isn't to go completely experimental, so a relatively simple/clean description language/model-of-computation for $K'$ is preferred, so that it might be possible to prove some reasonable theorems about how drastically $K'$ differs from $K$ and on what kind of strings.
Relates questions
Kolmogorov complexity with weak description languages
Is there a sensible notion of an approximation algorithm for an undecidable problem?


texts:
I'm not expert on complexity theory and combinatorial optimization.
I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete.
Thank you in advance for your help.

Input:

Two parameters X and Y, which can be equal.
n customers C1, C2, ... Cn
m types of goods M1, M2 ... Mm

There are X pieces available for each good Mi: a piece of 1kg, another piece of 2kg, ...., a piece of X kg.
Every customer wants to buy a certain number of goods. For example, the client C1 may be interested in buying goods M1, M4, M8 and M9.
A customer is satisfied if he can find all the goods he wants to buy. In addition, the weights of the parts he was able to purchase must satisfy a constraint that I'll explain below.

Output:
How many customers can be satisfied?

The constraint on the weights is as follows:
Take for example the client C1 who is interested in buying goods M1, M4, M8 and M9. Assume that C1 was able to purchase all four goods. Let P1, P2, P3, P4 be the weights of the pieces he was able to buy.
C1 is satisfied if $\sum_i  P_i -1 <Y$.

Edit: Note that the limit Y is common for all customers. The intuition behind the constraint is that we want to limit the number of pieces whose weight is not equal to 1kg.


texts: Is there a continuous version of parallel repetition theorem

texts:
Raz's Parallel pretition theorem is an important result in PCP, inapproximation, etc. The theorem is fomalized as follows.

A game $G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi, V)$, where $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are finite sets, $\pi$ is a distribution on $\mathcal{S}\times\mathcal{T}$, and predicate  $V:\mathcal{S}\times\mathcal{T}\times\mathcal{A}\times\mathcal{B}\rightarrow\{0,1\}$. Define value of the game $$v(G)=\max_{h_A\in\mathcal{H}_A,h_B\in\mathcal{H}_B}\sum_{s,t}\pi(s,t)V(s,t,h_A(s),h_B(t))$$  And $n$-fold game $G^n=(\mathcal{S}^n,\mathcal{T}^n,\mathcal{A}^n,\mathcal{B}^n,\pi^n, V^n)$. The theorem says if $v(G)\leq 1-\epsilon,$ then $v(G^n)\leq (1-\epsilon^c)^{\Omega(\frac{n}{\log\max\{|A|,|B|\}})}$.

My quesion is what happen if the sets are infinite, in a continuous space. Say if $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are subsets of a space, say $R^n$, or more abstract spaces. All the rest are same. Raz's theorem  only gives a trivial upper bound $1$ since the sizes of answer sets are infinite. Obviously $n$-fold value is upper bounded by single copy.  Does exponential decrease also happen in continuous case?  Would it be more interesting to restrict $\mathcal{H}_A,\mathcal{H}_B$ to be collections of continuous functions or $C^{\infty}$ functions or measureable functions?


texts: Parameterized complexity from P to NP-hard and back again

texts:
I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, for example $k$-SAT has a single phase transition from $k \in \{1,2\}$ (where the problem is in P) to $k \ge 3$ (where the problem is NP-complete). I'm interested in problems where there are phase transitions in both directions (from easy to hard and vice-versa) as $k$ increases.

My question is somewhat similar to the one asked at Hardness Jumps in Computational Complexity, and in fact some of the responses there are relevant to my question.

Examples I am aware of:

$k$-colorability of planar graphs: In P except when $k=3$, where it is NP-complete.
Steiner tree with $k$ terminals: In P when $k=2$ (collapses to shortest $s$-$t$ path) and when $k=n$ (collapses to MST), but NP-hard "in between". I don't know if these phase transitions are sharp (e.g., P for $k_0$ but NP-hard for $k_0+1$). Also the transitions of $k$ depend on the size of input instance, unlike my other examples.
Counting satisfying assignments of a planar formula modulo $n$: In P when $n$ is a Mersenne prime number $n=2^k-1$, and #P-complete for most(?)/all other values of $n$ (from Aaron Sterling in this thread). Lots of phase transitions!
Induced subgraph detection: The problem is not parametrized by an integer but a graph. There exist graphs $H_1 \subseteq H_2 \subseteq H_3$ (where $\subseteq$ denotes a certain kind of subgraph relation), for which determining whether $H_i \subseteq G$ for a given graph $G$ is in P for $i\in \{1,3\}$ but NP-complete for $i=2$. (from Hsien-Chih Chang in the same thread).


texts: Applications of an access lemma for dynamic forests?

texts:
Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma.  For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum of the weights of all descendants of $v$.  The Access Lemma states that  any node $v$ can be splayed in $O(\lg (size(root) / size(v)))$ amortized time.  This result has several corollaries:

Amortized balance: The amortized cost of splaying any node in an $n$-node binary tree is $O(\log n)$.
Static optimality: In any sequence of $N$ splays, where each node $v$ is splayed $N_v$ times, the amortized cost of splaying $v$ is $O(\log (N/N_v))$.
Static finger: Fix an arbitrary node $f$, and for any other node $v$, let $dist(f,v)$ be one more than the difference in inorder ranks of $f$ and $v$.  The amortized cost of splaying $v$ is $O(\log(dist(f,v))$.
Working set: The amortized cost of splaying $v$ is $O(\log |W_v|)$, where $W_v$ is the set of nodes that have been splayed since the last time $v$ was splayed.  (If $v$ has never been splayed before, the amortized cost of splaying $v$ is $O(\log n)$.)
Sequential access: Starting with an arbitrary binary tree, splaying all $n$ nodes in  order by rank requires $O(n)$ time.

Splay trees are an essential component of several dynamic forest data structures, including Sleator and Tarjan's link-cut trees and Tarjan and Werneck's self-adjusting top trees.  These data structures support several operations in $O(\log n)$ amortized time: insert an edge between two trees (link), delete an edge (cut), test whether two nodes are connected, add a value to the weight of every node on a path, find the minimum weight node on a path, and so on.  The $O(\log n)$ amortized time bound for all these operations follows from a careful application of the Access Lemma and a few other tricks.

So far all this is well known.  But it appears that the Access Lemma for splay trees actually implies a similar Access Lemma for dynamic forests, which may imply  (appropriate variants of) static optimality, static finger, sequential access, and working set bounds for dynamic forests.  (I'm being deliberately vague here, in part because I haven't worked out all the details.)

Does this observation matter?  Are there any algorithms where more nuanced amortized time bounds for dynamic forest operations might yield better overall time bounds?  For example, are there applications of dynamic trees where some nodes/edges are accessed significantly more often than others, or where the accessed edges/nodes have some locality of reference, either spatially (for fingers) or temporally (for working set)?

For the applications that I'm most familiar with—maximum flows and parametric shortest paths—more nuanced analysis of dynamic forests does not seem to imply better time bounds.  For example, in Goldberg, Grigoriadis, and Tarjan's network-simplex algorithm for maximum flows via network simplex, the time analysis only relies the observation that every edge is cut from a certain spanning tree at most $n$ times.  There is no obvious pattern to which edges are cut when, so more nuanced bounds (whatever they are) don't seem to help.


texts:
We all know that F<: is undecidable: http://www.cse.chalmers.se/~abela/lehre/SS07/Typen/pierce93bounded.pdf

However, I have difficulties finding that anyone claiming the version with bottom added being also undecidable: https://www.cs.indiana.edu/pub/techreports/TR492.pdf

Intuitively F<: with bottom should be undecidable, but if one claims that without proving it, I feel it's just a sloppy belief. In particular, I think that the proof must involve showing S-BOT rule from the version with bottom must be either non-existent, or can be removed from the derivation tree, which doesn't seem immediate to me.

So I am wondering if there is any source actually showing adding bottom doesn't turn the calculus decidable (as expected)?


texts: Control optimization for a black box model

texts:
Computer science is not my major, hence my question is two folded :

how is defined the problem I have (if I can name it, it will be easier for me to look for references) ?
what kind algorithm would be more suited to solve it ?

Let's take a wheeled remote controlled turtle (the real turtle) and a numerical model of it (the model turtle).

We first play once with the real turtle, record the commands and the resulting trajectory.

The problem is to find the right commands for the model turtle in order to fit (as much as possible) with the trajectory obtained previously with the real turtle.

With a perfectly representative model, it won't be an issue at all: for similar commands, one would get similar trajectory. But the model turtle will never be perfect, and commands will need to be tweaked.

Extra constraints are :

model turtle can only be initialized (at t=0) and run forward (in time) to the end of the trajectory (no reverse play, snapshot/recall, etc.). Simulation can be run many times though.
model turtle is in fact a complex black box system, with no known equations of it and a bunch of internal states (mostly filters).

Thanks in advance for the leads


texts: Reduction from OR-SAT to Exact CNF-SAT, keeping the number of variables polynomially bounded?

texts:
Let me define both the problems first:

$OR$-$SAT$:  $m$ Boolean formulae are given in $CNF$, $\phi_1$,$\phi_2$, $\ldots$, $\phi_m$, each on variable set, $x_1, x_2, \ldots, x_n$. ($m$ $<$ $2^n$, otherwise the problem is polynomial time solvable) Each $\phi_{i}$ is of size at most $poly(n)$.

$Question$: Is there an assignments to the given $n$ variable, such that at least one of the $\phi_i$s is satisfiable ?

$Exact\ CNF$-$SAT$:  A formula $\phi$ in conjunctive normal form of size $m$ over $n$ variables.

$Question$: Is there any satisfiable assignment for $\phi$, such that exactly one of the literals in each clause of $\phi$ is assigned to True ?

I am interested to know if there is a reduction from $OR$-$SAT$ to $Exact\ CNF$-$SAT$, keeping the number of variables polynomially bounded, or if it can be proved, no such reduction possible unless some bad thing happens. There are standard reductions from $OR$-$SAT$ to $SAT$ and $SAT$ to $Exact\ CNF$-$SAT$, but the second reduction doesn't keep the number of variables polynomially bounded. Any thought ??

In $OR$-$SAT$, each $\phi_i$ is of size $poly(n)$. So $SAT$ and $OR$-$SAT$ are pretty much different problems. They are in different levels in $VC$-hierarchy. There are many problems between these 2 levels.  I am actually interested to know the exact position of $Exact$ $CNF$-$SAT$ in that hierarchy. I am interested to bound the number of variables to $poly(n)$, as I am interested in PPT (Parametric Polynomial Time) reduction rather than normal polynomial reduction.


texts: What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?

texts:
What are the problems with the best known approximation ratio achieved by an algorithm returning a uniformly random solution?

I know one such example for permutation flow shop problem $F|perm|C_{max}$: in the paper "Tight Bounds for Permutation Flow Shop Scheduling" Viswanath Nagarajan and Maxim Sviridenko proved that random sequence of jobs have guarantee $2\sqrt{min\{m,n\}}$ ($m$-number of machines and $n$ - number of jobs) which is the best known currently.


texts: What algorithms are known for computing Craig interpolants?

texts:
Is there any survey of algorithms for computing interpolants? What about papers on only one algorithm? The case I'm most interested in is $A=\lnot p\land q$ and $C=q$, plus the constraint that the interpolant is as small as possible. (I know of McMillan's paper from 2005, which describes how to get interpolants, while avoiding quantifiers.)

Background: Craig's interpolation theorem (1957) says that if $\vdash_{T_A\cup T_C}A\to C$, where $A$ is a (fol) formula in $T_A$ and $C$ is a formula of $T_C$, then there is a formula $B$ such that $\vdash_{T_A}A\to B$ and $\vdash_{T_C}B\to C$. Formula $B$ is a Craig interpolant of $A$ and $C$ (or, in alternative definitions, of $A$ and $\lnot C$). A trivial interpolant of $\lnot p\land q$ and $q$ is $q$, but I want a small interpolant, for some reasonable definition of 'small' (such as syntactic size). (Interpolants have many uses and, in case you are curious, here's one.)

Motivation: This would be useful in (very) incremental program verification via verification condition generation.


texts: What is higher-order in higher-order abstract syntax?

texts:
I understand that using higher-order abstract syntax essentially means using host (meta) language abstraction facilities to represent binders in embedded (object) language. But, Why exactly is it higher-order? Why is traditional abstract syntax called first-order abstract syntax?

I read the paper (Frank Pfenning, and Conal Elliott, Higher-Order Abstract Syntax, PLDI'88) that introduced HOAS as we use today. I could not quite understand the following paragraph ($\S$ 3.2) that describes encoding in HOAS:

  In this first generalization, simply typed lambda terms represent programs. .. . The lexical terminals and the operators that do not introduce variable bindings are, respectively, first-order and second-order constants of the $\lambda$-calculus. Another crucial change occurs for the variables. Operators in the object language that are binding constructs are now explicitly encoded as third-order constants. As the following examples will show, this requires that bound object language variables actually become variables in the typed lambda calculus.

Particularly, I am not convinced why encodings for binding-introducing constructs like let (shown in Figure 1 of the paper) are considered third-order.


texts: Estimating the average contiguous sequence length of a balanced boolean function

texts:
Given a balanced Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, is there a sampling strategy that needs less than $O(2^n)$ samples to estimate the average length of contiguous sequences of 1's?

Balanced means over all possible x's $f(x)=0$ 50% of the time, $f(x)=1$ 50% of the time.

Pointers to background papers related to this topic would be much appreciated.


texts:
Context: Refering to the  question: Complexity of the $(3,2)_s$ SAT problem? and since the paper by Porshen and Speckenmayer : Satisfiability of mixed Horn formulas, we know that even when $F_3$ is Horn, the problem of deciding the satisfiability of $F_3 \wedge F_2$ is NP-complete - where $F_3$ and $F_2$ are respectively 3-CNF and 2-CNF formulas.
I am wondering if there exist some cases where $F_3 \wedge F_2$ is easy to decide.
Hence my question:
Let $F_3$ a 3-CNF containing only clauses with exactly 3 different literals and $F_2$ a 2-CNF defined on the same variables as $F_3$.
What is the complexity of deciding the satisfiability of $F_3 \wedge F_2$ when $F_3$ and $F_2$ are both monotone?
Thank you.


texts: Worst number of questions needed to learn a monotonic predicate over a poset

texts:
Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by providing one node $x \in X$ and finding out if $P(x)$ holds or not. My goal is to determine exactly the set of nodes $x \in X$ such that $P(x)$ holds, using as few evaluations of $P$ as possible. (I can choose my queries depending on the answer of all previous queries, I am not required to plan all queries in advance.)

A strategy $S$ over $(X, \leq)$ is a function which tells me, as a function of the queries that I ran so far and their answers, which node to query, and which ensures that on any predicate $P$, by following the strategy, I will reach a state in which I know the value of $P$ on all nodes. The running time $r(S, P)$ of $S$ on a predicate $P$ is the number of queries required to know the value of $P$ on all nodes. The worst running time of $S$ is $wr(S) = \max_P r(S, P)$. An optimal strategy $S'$ is such that $wr(S') = \min_S wr(S)$.

My question is the following: given as input the poset $(X, \leq)$, how can I determine the worst running time of the optimal strategies?

[It is clear that for an empty poset $n$ queries will be needed (we need to ask about each single node), and that for a total order around $\lceil \log_2 n \rceil$ queries will be needed (doing a binary search to find the frontier). A more general result is the following information-theoretic lower bound: the number of possible choices for the predicate $P$ is the number $N_X$ of antichains of $(X, \leq)$ (because there is a one-to-one mapping between monotonic predicates and antichains interpreted as the maximal elements of $P$), so, since each query gives us one bit of information, we will need at least $\lceil \log_2 N_X \rceil$ queries, subsuming the two previous cases. Is this bound tight, or are them some posets whose structure is such that learning can require asymptotically more queries than the number of antichains?]


texts: I am currently reading the book Programming in Martin-Löf type theory by Nordström et al. In the book they have two important parts, one about monomorphic set theory and the other about polymorphic set theory. Why do they do this? What are important differences. As far as I understand from the book monomorphic version reduces to polymorphic but not vice versa. Why is this so?


texts: Questions about special types of partial assignments

texts:
Considering the definition

  "2-SAT: Given a CNF formula whose clauses have exactly 2 literals,
  does there exist an assignment of $\mathsf{TRUE}$ or $\mathsf{FALSE}$ to the variables
  that will satisfy the formula?"

Question 1: Is it necessary to give an assignment, or is it sufficient to prove that an assignment exists? (This question has been answered by Vijay D.)

Question 2: A reliable assignment is a partial assignment which is guaranteed to deliver only satisfying assignments under DPLL. I.e., DPLL can never resolve an empty clause and therefore never produces an unsatisfying assignment. A reliable assignment is different from an implicant as it does not necessarily satisfy all clauses. However, an implicant is a special case of a reliable assignment.

I would prefer using the correct term for this type of assignment.

Question3: Reliable assignments appear in my SAT solving algorithm as an entire set with cost O(n^2). A set of implicants can be generated by distributive expansion of the disjunctions defining the reliable assignments with cost O(2^n). Due to the construction, each implicant is necessarily defined by the conjunction of a subset of reliable assignments.

Does such a set of reliable assignments appear in other algorithms?

Context

The reliable assignments appear in the context of Partial Distributive Expansion

Detailed examples are available at Prime Implicants and Reliable Assignments.

The full context is an integrated SAT algorithm for a complete set of solutions. Here is an informal rationale on what I have to cover eventually. Any hints welcome.


texts:
I am exploring using annotated grammars to formalize and enforce parts of contracts between nodes in a distributed application.

I've found a number of articles on languages for specifying fairly general types of contracts, mostly based around the idea of a contract as a state machine; and others (mostly object-capability schemes) based around the idea of identifying a "safe" subset of a language; but none that use a grammar as the specification of the contract.

I was wondering how attempts to formalize contracts tend to fail, and what else should one keep in mind.

Below are details of the particular kind of contract I am trying to enforce.

Given a BNF grammar for part of HTML:

HTML ::== (Text | Link)*;
Text ::== ("&amp;" | "&lt;" | "&quot;" | [^&<"])+;
Link ::== "" Text "";
Href ::== "href=\"" Text+ "\"";

I can infer which strings are in the language and which are not, and the structure of a parse tree, but by adding annotations thus

HTML ::== (Text | Link)*;
Text ::== @String((@CharValue{"&"}"&amp;"
                 | @CharValue{"<"}"&lt;"
                 | @CharValue{"\""}"&quot;"
                 | [^&<"]))+;
Link ::== "" Text? "";
Href ::== " href=\"" @Embeds{URI}Text+ "\"";

I can infer additional facts:

That plain text can be encoded/decoded by replacing "&" with "&amp;", etc. and that a string can be encoded as a string that matches the Text non-terminal.
That the URI grammar should be recursively applied to the content of the href post-decoding.

From this I hope to generate several artifacts:

Encoders.  An encoder for non-terminal T is a 'a -> T string function that encodes a data value.
Sanitizers.  A function T string -> T string that produces a similar string that falls in a subset of the language that is well-handled by many different implementations and which does not contain high-power instructions.
A template context propagator.  A function string * context -> string * context which takes a string from a trusted source and the context before the string (context is a type describing a set of prefixes of strings in the language) and produces a string in the well-handled subset of the language and the context after that string is appended to any of the prefixes described by the input context.  This is useful for composing a string from trusted and untrusted code.

With these tools, I hope to be able to enforce the contract that any powerful instructions which are parsed by the receiver of a network message composed using these tools are instructions that are present in snippets of code authored by the message sender, and not instructions authored by a provider of untrusted data.

If the sender uses the derived tools to encode or sanitize all untrusted data appropriately, and uses the template propagation algorithm to choose encoders/sanitizers appropriate to the context of the buffer on which the message is being built, then high-power instructions in the buffer must have come from a privileged source.

If the recipient receives a message over a secure channel, and uses the same grammar to parse and decode the message, then it can be confident of the provenance of the instructions it receives.

So the annotated grammar serves as a formal description of a contract, and the tools move the burden of preserving the contract from the application author to the grammar author.  Since there are many application authors who tend to know the well-tested parts of a language, a much smaller number of language specialists who know the poorly tested parts of the grammars as well should be able to make applications robust against code injection.


texts:
The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial).
In the Complexity Zoo, there are four kinds of relationships being mentioned ( https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N )

NEXP vs. Interactive Proof Systems

  Equals MIP [BFL91] (but not relative to all oracles).
  NEXP is in MIP* [IV12].
  NEXP is in P/poly if and only if NEXP = MA [IKW01].

NEXP vs. Randomized Polynomial Time Complexity Classes

  [KI02] show the following:
  If P = RP, then NEXP is not computable by polynomial-size arithmetic circuits.
  If P = BPP and if checking whether a Boolean circuit computes a function that is close to a low-degree polynomial over a finite field is in P, then

NEXP vs. Small Size Nonuniform Circuits

  NEXP is not in P/poly.
  If NEXP is in P/poly, then matrix permanent is NEXP-complete.
  Does not equal NP [SFM78].
  Does not equal EXP if and only if there is a sparse set in NP that is not in P.

Off course, Ryan William's breakthrough separation between NEXP and ACC (and also SYM $\circ$ THR) is contained in this category.

NEXP vs. EXP

  There exists an oracle relative to which EXP = NEXP but still P does not equal NP [Dek76].
  The theory of reals with addition (see EXPSPACE) is hard for NEXP [FR74].

One of important complexity resources which is not mentioned above is space complexity, and one of the most natural classes is PSPACE.

My Question is the following and a reference request question:

  Q1: Is there some known theorems with the assumption that NEXP is in PSPACE?

My intention of this question is as follows.

As an example, we consider collapses of PH (the polynomial time hierarchy).
By Karp-Lipton's theorem NP $\subset$ P/poly implies PH collapses into the second level.
However, NP $\subseteq$ P implies PH collapses into the first level.
These two claims mean that the claim NP $\subset$ P is more unlikely than NP $\subseteq$ P/poly.

Similarly, NEXP $\subseteq$ PSPACE is more unlikely than NEXP $\subseteq$ EXP.

So, my question is about some comparison between two unlikely conclusions.