texts: Some questions about the Ryan O'Donnel and Yuan Zhou's paper "Approximability and proof complexity"

texts:
My question is particularly about the set-up in section $8$ (``Analysis of the KV Max-Cut instances") of the paper, https://arxiv.org/pdf/1211.1958.pdf.

What they call the Khot-Vishnoi UG instance doesn't seem like a generic UG instance. Am I right? The UG instance that they are starting from (at least the one in the middle of page 24) seems to assume that the underlying graph of the UG instance is such that it has a non-negative weight valued in the interval $[0,1]$ associated to every edge. (And this is what allows them to have the probability interpretation!) But isn't this an extra structure assumed to be true than what UG would come with?
In the middle of page $25$ when they construct the Max-CUT instance from the UG instance in the last step it says, "Output the edge $(w_{u_1,x \circ \pi_1 },w_{u_2, x \circ \pi_2 })$ ". Is that a typo? There is nothing called $u_1$ and $u_2$ defined before. Should that be, $(w_{v_1,x \circ \pi_1 },w_{v_2, x \circ \pi_2 })$?  (...atleast with $v_1, v_2$ this would look closer to the last step of the PCP inner-verifier construction at the bottom of page $18$ in the original KKMO reduction, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf..)

This step when the construction of Max-CUT is described it again refers to this quantity called $\cal{E}$ which I guess is a probability distribution on the edges of the UG instance that they are assuming to be given. Or does any UG instance somehow implicitly come with this thing they call $\cal{E}$?


texts: Is anyone actively researching distributed prediction models?

texts: Is there any current, ongoing, research being performed, looking specifically at implementing prediction models on a distributed system? I'm specifically interested in work where the underlying system can be modeled as a network of devices that has significant churn in terms of connections between the nodes, and nodes joining/leaving the network (for example, a peer-to-peer network).


texts: Fixed dimension Integer programming minus LLL in fixed parameter $NC$?

texts:
If you remove LLL part then is remaining part of
a. Lenstra algorithm
b. Barvinok algorithm
in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$ dimension, $m$ constraints and $L$ bit length input for some functions $f,g:\Bbb R\rightarrow\Bbb R$?

Note we know linear programming and convex programming are not in $NC$ in general dimension.


texts: Do all complexity classes have a leaf language characterization?

texts:
Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a resource bound (log time, poly space, etc.). However in the leaf language formulation, there is only one model of computation, and the class is specified by giving its leaf language.

The details are too long to explain, so I'll direct interested readers to either of these two surveys:

Uniform characterizations of complexity classes by H Vollmer
Leaf Language Classes by KW Wagner

Both surveys do a great job of explaining the formulation within the first few pages.

In Wagner's survey, he says "it turns out that practically every complexity class considered so far can be described by leaf languages."

My question relates to this statement. I know there are some classes for which we do not know a leaf language characterization, so this means either the classes don't necessarily have such a characterization, or we haven't found it.

Do we expect every complexity class (say between P and PSPACE) to have a leaf language characterization? (Let's restrict ourselves to "natural" complexity classes.) Is there any result of this sort in the literature?

(A related question that I'd be happy to know the answer to: Is there a (heuristic) method to come up with a leaf language for a given class?)

EDIT: Suresh points out that there is a short definition of leaf languages in the Wikipedia article. I'm copying it below.

Several complexity classes are typically defined in terms of a polynomial-time nondeterministic Turing machine, where each branch can either accept or reject, and the entire machine accepts or rejects as some function of the branches' conditions. For example, a non-deterministic Turing machine accepts if at least one branch accepts, and rejects only if all branches reject. A co-non-deterministic Turing machine, on the other hand, accepts only if all branches accept, and rejects if any branch rejects. Many classes can be defined in this fashion.


texts: What's the fastest algorithm to compute Max{max flow with single source and multiple sinks}

texts:
Given an arbitrary directed graph(not planar, cycles included), a source node $S$ and constant constraints on edges, for each sink node $t_i$, the maximum flow from $S$ to $t_i$ is denoted by $f(S,t_i)$.

Find $\max{f(S,t_i)}$
Find $\max{d(S,t_i) * f(S,t_i)}$, where $d(S,t_i)$ represents the length of shortest path from $S$ to $t_i$

I have found some papers about computing max flows of multiple targets on a planar graph, but is there any algorithm faster than computing $f(S,t_i)$ for $|T|$ times?


texts: Is uniform convergence faster for low-entropy distributions?

texts:
Let $\mathcal D$ be a probability distribution on $\{0,1\}^d$. Let $X_1, \cdots, X_n \in \{0,1\}^d$ be i.i.d. samples from $\mathcal D$.  Let $\mu \in [0,1]^d$ be the mean of $\mathcal D$ and let $\overline X = \frac{1}{n} \sum_{i=1}^n X_i \in [0,1]^d$ be the mean of the samples.

By Hoeffding's inequality and a union bound, $$\mathbb{P}\left[\left\| \overline X - \mu \right\|_\infty \ge \varepsilon \right] \le 2d \cdot e^{-2n\varepsilon^2}$$ for all $\varepsilon \ge 0$. Equivalently, for $\varepsilon,\delta>0$, if $n \ge \frac{\log(2d/\delta)}{2\varepsilon^2}$, then $\mathbb{P}\left[\left\| \overline X - \mu \right\|_\infty \ge \varepsilon \right] \le \delta$.

This bound is tight (up to constants) in the worst case. In particular, the uniform distribution achieves this bound.

My question is whether better bounds are known if we know that $\mathcal D$ has low entropy.

Obviously, if $\mathcal D$ has no entropy (i.e., $\mathcal D$ is a point mass) then one sample is enough for perfect convergence. If the entropy is maximal, then $\mathcal D$ is the uniform distribution and the above bound is tight. What if the entropy is intermediate, e.g., $\mathsf H(\mathcal D) = \Theta(\log d)$? Could we replace $d$ with, say, $\mathsf H(\mathcal D)$ in the above bounds?

Some remarks about how I came to this question:

Let's imagine you are running the Multiplicative Weights algorithm for online learning or solving a repeated zero-sum game. Typically we assume that it outputs a full probability distribution at each step and the loss/gain is exactly the expectation over this distribution. What happens if we cannot output the whole distribution?

If you only output one sample from the MW distribution, then the environment/adversary/other player can best-respond to that move and force the MW algorithm to suffer large loss/small gain. So one sample is insufficient to retain the no-regret guarantee.

What if instead you have $n$ samples from the MW distribution? If $n$ is large enough, uniform convergence kicks in and the empirical distribution of the sample is close to the desired MW distribution and you get the no regret guarantee with high probability.

So the question is how many samples $n$ do you need from the multiplicative weights distribution to get the desired uniform convergence? One thing to note is that the entropy of the MW distribution decreases with each step. (Entropy is one way to analyze the MW algorithm.) So I was hoping that one could show that, as the MW algorithm proceeds, fewer and fewer samples are needed. That led to this question, which I think is interesting in its own right.

My question about MW arose from reading this paper. Here there is a specific cost to each sample from the MW distribution and that cost grows linearly with the number of time steps. Thus, if we could show that, in the final steps where the entropy is low (since MW has converged) and the cost is high, fewer samples are needed, then this might improve the algorithm.


texts: Satisfaction and synthesis of models in logics

texts:
It is well known that for propositional logic, the problem of constructing a model of a given formula is equivalent to deciding whether the formula has a model. Satisfiability is NP-complete, and finding a model can be done by instanciating the variables one after another and checking each time whether the formula is still satisfiable, and this problem has the same complexity.

The satisfiability problem for LTL is PSPACE-complete, but he proof involves constructing an automaton that represents the set of all models, and from this, generating a model is easy, so synthesis in this case is also PSPACE-complete.

My question is: does this relation hold for any logic ? I.e. given some logic L, if the satisfiabiliy problem for L has complexity class C, is the problem of constructing a model always also in C ? Are there logics for which the model synthesis problem is significantly more difficult than satisfiability ?


texts:
Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are connected and such that $|w(G')-w(G'')|$ is maximal, where $w(G')$ is the sum of vertex weights in $G'$.

I know that the problem of minimizing $|w(G')-w(G'')|$ is called Balanced Connected Partition for $k=2$, or $BCP_2$, with vertex weights. Chlebikova in 1996 showed that this admits a poly-time $4/3$-approximation algorithm. Is there also literature for the maximizing version? Even a heuristic algorithm without proof of approximation bound would be helpful.

Actually, the ultimate problem I am trying to solve is a combination of these. If each vertex has two weights $w_1(v), w_2(v)$ then I wish to maximize $|w_1(G')-w_1(G'')| - |w_2(G') - w_2(G'')|$.


texts:
I know that knowledge about relationships between things can be represented using ontologies and stored in some sort of file or database system.

Can a network of procedural knowledge also be created in this way? Such that complex algorithms can be defined and stored efficiently, translated into other languages and forms (such as finite state machines or machine language), changed, and form the basis for other AI axioms?

i.e. Procedural Reasoning Systems -- how would a Knowledge Area (KA) be represented as a cognitive primitive in a computer system?


texts: Relating functors to relational functors with the parametricity translation

texts:
$\newcommand{\Type}{\text{Type}}\newcommand{\id}{\text{id}}\newcommand{\map}{\text{map}}$
In attempting to answer the question: Rigorous proof that parametric polymorphism implies naturality using parametricity? I tried showing that one obtains the theory of relational functors by applying the parametricity translation to the theory of functors, where relational functors are defined in Logical Relations and Parametricity - A Reynolds Programme for Category Theory and Programming Languages.
Specifically, if we are given
\begin{align*}
F_! &: \Type\to\Type\\
F_{\map} &: (A,B:\Type)\to(A\to B)\to(F_!A\to F_!B)\\
F_{\id}&:(A:\Type)\to F_{\map}(\id(A)) = \id(F_!A)
\end{align*}
I was able to show (with generous hand-waving) that
\begin{align*}
F_!^R &: (A,B:\Type)\to \text{Rel}(A,B)\to\text{Rel}(F_!A,F_!B)\\
F_\map^R &:(A_0,A_1: \Type)\to(A^R:\text{Rel}(A_0,A_1))\to (B_0,B_1:\Type)\to(B^R:\text{Rel}(B_0,B_1))\\
&\quad\to(f_0:A_0\to B_0)\to(f_1 : A_1\to B_1)\\
&\quad\to((x_0:A_0)\to(x_1:A_1)\to A^R(x_0,x_1)\to B^R(f_0x_0,f_1x_1))\\
&\quad\to(x_0 : F_! A_0)\to(x_1 : F_! A_1)\to F_!^R(A_0,A_1,A^R,x_0,x_1) \\
&\quad\to F_!^R(B_0,B_1,B^R,F_\map (A_0,B_0,f_0,x_0),F_\map (A_1,B_1,f_1,x_1))
\end{align*}
But I am having trouble showing that $F_\id^R$ gives some form of the identity extension property, namely that
$$A:\Type\vdash F_!^R(A,A,\text{Id}(A)) = \text{Id}(F_!^RA) $$
It seems to me that the pair $(F,F^R)$ should give a relational functor in the sense of definition 6.1.
Is my intuition that this should be the case correct, and if so, is there some higher level explanation for this (perhaps some sort of Yoneda embedding?)?


texts: Type-based memory safety without manual memory manage or runtime garbage collection?

texts:
Let's say we wanted a typeful, pure functional programming language, like Haskell or Idris, that is aimed at systems programming without garbage collection and has no runtime (or at least not more than the C and Rust "runtimes"). Something that can run, more or less, on bare metal.

What are some of the options for static memory safety that don't require manual memory management or runtime garbage collection, and how might the problem be solved using the type system of a pure functional similar to Haskell or Idris?


texts: Tools to bound the singular values of a finite sum of random matrices from below?

texts:
Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower bound on the smallest eigenvalue of a finite sum of random positive semidefinite (PSD) matrices.

For PSD matrices, the eigenvalues are the same as the singular values. My question is:

  Is there any tool, or any other special cases (apart from the PSD case) for which there is a tool, to obtain lower bounds on the singular values of a finite sum of random matrices, or random symmetrical matrices?


texts:
I thought the relation between P using a #P-oracle and NP using a #P-oracle is still unknown (or equivalently the relation between P^PP and NP^PP).

Recently, I have read in a journal article that P^#P = NP^#P (citing Toda's publication "PP is as hard as the polynomial time hierarchy"). As far as I remember this relation was posed as an open question in Toda's paper.

I am very confused at the moment and I would be glad if someone could clarify this situation. Thanks a lot.


texts: Can addition be carried out in less than depth 5?

texts:
Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary numbers using a polynomial size circuit family with depth less than that obtained by carry look ahead algorithm?

Are there any super polynomial lowerbounds for the size of $AC^0_d$ circuit families computing addition where $d$ is 2 or 3?

By depth I mean alternation depth.


texts:
Most of the work on programming language metatheory mechanization focus on the declarative properties of the languages (e.g., type soundness), but fail to address the algorithmic side, i.e. the type checking (or reconstruction) algorithm.

As far as I know, the only works that verified the algorithmic properties of type systems are the early papers on the mechanization of Algorithm W (Naraschewski & Nipkow 1999, Urban & Nipkow 2009), and Jacques Garrigue's certified type checker for a representative subset of OCaml (2014).

Are there any other work on formally verifying the completeness, soundness & other algorithmic properties (e.g., decidability) of type checking (or type inference) algorithms?


texts: Reference for the undefinability of modulus of continuity functional in PCF?

texts:
Can someone point me to the reference for the non-definability of the modulus of continuity functional in PCF? $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\bool}{\mathsf{bool}}$

Andrej Bauer has written a very nice blog post exploring some of the issues in more detail, but I'll summarize just a bit of his post to lend some context to this question. The Baire space $B$ is the set of natural number sequences, or equivalently the set of functions from naturals to naturals $\N \to \N$. For this question, we will restrict our attention only to the streams which are computable.

Now, a function $f : B \to \bool$ is continuous if for every $xs \in B$, the value of $f(xs)$ depends only a finite number of the elements of $xs$, and it's computably continuous if we can actually compute an upper bound on how many elements of $xs$ are needed. In some models of computation, it's actually possible to write a program  $\mathsf{modulus} : (B \to \bool) \to B \to \N$ which takes a computable function on the Baire space and an element of the Baire space, and gives back the upper bound on the number of elements of the stream.

One trick for implementing this is to use local storage to record the maximum index into the stream seen:

let modulus f xs =
  let r = ref 0 in
  let ys = fun i -> (r := max i !r; xs i) in
    f ys;
    !r

Of course, the ys argument is no longer a purely functional program. My interest in this program comes from the fact that it only makes use of local store, and is therefore extensionally pure. I work on (among other things) higher-order imperative programming, and am designing type theories which could classify this as a pure function.

There are more practical examples as well, involving things like memoization and connection pooling, but I find this a particularly beautiful example.


texts: Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution

texts: One of the main parameters in the construction of extractors is $k$, the min-entropy of the source distribution. In practice, suppose we want to extract randomness from a given source $S$. How do we determine $k$ in this source $S$? More generally, how do we quantify the amount of (extracted) randomness in the output distribution of the extractor.


texts: $\mathsf{UPH}$, $\Pi_2^{\mathsf{P}}$ and $\mathsf{PP}$

texts:
In literature, the biggest class I have seen proven to be in $PP$ is $NP$ (and $coNP$ of course as $PP$ is closed under complementation).

However, if we use the following results :

$PP^{RP} = PP$  (in fact $PP^{BQP} = PP$)
There exists a RP-reduction from $SAT$ to $USAT$

Where $USAT$ is the promise class of boolean formulae such that

if $F \in USAT$ then $F$ has a unique solution.
if $F \not \in USAT$ then $F$ is not satisfiable.

It seems quite straightforward to prove that $\Pi_2^P \subseteq PP$ (hence $\Sigma_2^P \subseteq PP$).

  Construction:
  Let $\mathcal{M}\ $ be the following $PP^{RP}$  Turing Machine :

  Input: $\forall x_1, \dots, x_m, \exists y_1, \dots y_n, F$
  Computation:

  Choose uniformely $x_1, \dots, x_m$.
  We obtain then an existential formula.
  Use the Valiant-Vazirani theorem to obtain an USAT formula $\exists! z_1, \cdots z_o G$.
  We choose uniformly $z_1, \dots, z_o$, and if $G$ is satisfied, accept, otherwise, reject with probability $\frac{1}{2}$.

  Modify the previous TM by adding $2^n-1$ rejecting paths. (I know I'm going a bit fast, but we can manage that by adjusting rejecting probabilities after having tested G)

  Validity:

  if $\forall \dots \exists \dots F$ is true, then $\mathcal{M}\ $ has $2^n$ accepting paths + $2^{n-1}$ rejecting paths + an equal number of accepting and rejecting paths, and then $\mathcal{M}\ $ accepts.
  if $\forall \dots \exists \dots F$ is false, then $\mathcal{M}\ $ has less than $2^n$ accepting paths + $2^n-1$ rejecting maths + more rejecting paths than accepting paths. then $\mathcal{M}\ $ rejects.

Moreover, if we extend Valiant-Vazirani theorem to $RP$-reduce $PH$ to $UPH$ (alternation of forall and unique existentials), then by modifying a bit previous construction we would prove that $PH \subseteq PP$.

  Is the previous construction correct ?

  Is there any known litterature around $UPH$ ? (It may not be called $UPH$)


texts: What is the Relationship between QMA and AM?

texts:
I read in S. P. Jordan, D. Gosset, P. J. Love's "$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices" that it is unlikely that $QMA \subseteq AM$.

I was surprised about this assertion. So what is the proper relationship between $QMA$ and $AM$?


texts: Graph families which have polynomial time algorithms for computing the chromatic number

texts:
Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings.

For which graph families there exists a polynomial time algorithm for computing the chromatic number $\chi(G)$?

The problem is solvable in polynomial time when $\chi(G) = 2$ (bipartite graphs).
In general when $\chi(G) \ge 3$, computing the chromatic number is NP-hard, but there are many graph families where this is not the case. For example, colouring cycles and perfect graphs can be done in polynomial time.

Also, for many graph classes, we can simply evaluate the corresponding chromatic polynomial; some examples in Mathworld.

I suppose most of the above is common knowledge. I would gladly learn whether there are any other (non-trivial) graph families for which the minimum graph colouring is solvable in polynomial time.

In particular, I am interested in exact and deterministic algorithms but feel free to point out any interesting randomized algorithms or approximation algorithms.

Update (Aug 31):

Thanks to everyone for submitting interesting answers. Here's a short summary of the answers and references.

Perfect and almost perfect graphs

Geometric Algorithms and Combinatorial Optimization (1988), Chapter 9 (Stable sets in graphs).  Martin Grotschel, Laszlo Lovasz , Alexander Schrijver.

Chapter 9 of the book shows how to solve the coloring problem via the minimum weighted clique covering problem.
Since they rely on the ellipsoid method, these algorithms may not be very useful in practice. Also, the chapter
has a nice reference list for different classes of perfect graphs.
Combinatorial Optimization (2003), Volume B, Section VI
Alexander Schrijver.

This book has three chapters devoted to perfect graphs and their polynomial time colourability. I took only a quick look but the basic approach seems the same as in the previous book.
A characterization of b-perfect graphs (2010).
Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek

Graphs with bounded tree-width or clique-width

Edge dominating set and colorings on graphs with fixed clique-width (2001).
Daniel Kobler, Udi Rotics

The algorithms here require a k-expression (an algebraic formula for constructing a graph with a bounded clique-width) as a parameter. For some graphs, this expression can be computed in linear time.
Yaroslav pointed out in methods for counting colourings in bounded tree-width graphs. See his answer below.

These two study graph families where $k$ vertices or edges can be either added or deleted.

Parameterized complexity of vertex colouring (2003).
Leizhen Cai.

Colouring can be solved in polynomial time when adding or deleting $k$ edges (for fixed $k$) in split graphs.
Parameterized coloring problems on chordal graphs (2006).
Dániel Marx.

For fixed $k$, chordal graphs to which $k$ edges are added, can be coloured in polynomial time.

Graphs not containing particular subgraphs

Deciding k-Colorability of P5-Free Graphs in Polynomial Time (2010).
Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.
3-colouring AT-free graphs in polynomial time (2010).
Juraj Stacho.

Colouring quadtrees

Algorithms for coloring quadtrees (1999).
David Eppstein, Marshall W. Bern, Brad Hutchings.


texts: Deterministic context-free languages that can be represented as the word problem of a group

texts:
Consider a group $G$. We call $G$ virtually free is it contains a free subgroup of finite index.
If $G$ is finitely generated by some set $X \subseteq G$ one can consider the word problem $W\!P(G)$ that is the formal language consisting of all words over the alphabet $X \cup X^{-1}$ that evaluate to the unit in $G$.
It is a famous result by Mueller and Schupp that the $W\!P(G)$ is context-free if and only if $G$ is virtually free.
It is also known that if $W\!P(G)$ is context-free, it is deterministic context-free.
My question is: Do we know more about how the class of deterministic context-free languages that can be represented as the word problem of some group, is contained in the class of all (deterministic) context-free languages?


texts: Why is the Greedy Conjecture so difficult?

texts:
I recently learned about the Greedy conjecture for the Shortest Superstring Problem.

In this problem, we are given a set of strings $s_1,\dots, s_n$ and we want to find the shortest superstring $s$ i.e. such that each $s_i$ appears as a substring of $s$.

This problem is NP-hard and after a long sequence of papers the best known approximation algorithm for this problem has a ratio $2+\frac{11}{30}$ [Paluch '14].

In practice, biologists use the following Greedy algorithm:

At each step, merge two strings that has maximum overlap over all pairs (the maximum suffix that is the prefix of another string), and repeat on this new instance until there is only one string left (which is a superstring of the all input strings)

A lower bound of $2$ in the approximation ratio of this Greedy Algorithm can be obtained from the input $c(ab)^k,(ba)^k,(ab)^kc$.

Interestingly, it was conjectured that this is the worst example i.e. that Greedy achieves a $2$-approximation for Shortest Superstring Problem. I was very surprised to see that such a natural and easy algorithm is so difficult to analyse.

Are there any intuitions, facts, observations, examples that suggest why this question is that challenging ?


texts: historical question: earliest description of beta-normal terms together with "neutral" terms in lambda calculus?

texts:
A bit of "folklore" in lambda calculus is the idea of characterizing the class of $\beta$-normal terms inductively as a syntactic category ($R$) defined in mutual induction with an auxiliary syntactic category of "neutral" terms ($B$):

$R$ ::= $\lambda x.R \mid B$

$B$ ::= $x \mid B(R)$

This division shows up in many places, such as in bidirectional type checking, normalization-by-evaluation, and in proofs by logical relations.  I was recently surprised to see this grammar clearly displayed in an old essay by Don Knuth, "Examples of Formal Semantics" (albeit followed by a word of warning!):

This is the oldest reference that I know (1970), but Jean-Yves Girard's thesis work was around the same time and also talked explicitly about neutral ("simple") terms in connection with proofs of strong normalization.  How far back does the idea go?  Did, say, Church or Curry discuss it?


texts:
Suppose we are given a general (connected) undirected graph $G = (V, E)$. An EDGE COVER asks a set $S\subseteq E$ of the minimum number of edges, such that each vertex $v\in V$ is incident to at least one edge $s\in S$. Note that this is solvable in polynomial time.

Now I'd like to generalize this problem to find a set $S$ of vertex-induced connected subgraphs that covers each vertex $v\in V$, but each subgraph $s\in S$ consists of at most (or exactly) 3 vertices (The goal is still to minimize $|S|$). Of course, the topology of a connected subgraph with 3 vertices is fixed (the only way is to form a line with 2 edges connecting them). In other words, we need to find a minimum path cover but the length of each path is at most (or exactly) 3.

Is this problem still poly-time solvable or it's NP-hard? Is it related with 3d matching or steiner tree?


texts: Graph partition with objective over intra-partition weights

texts:
I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar problems to which I can map to. Perhaps someone can give some insight or point me to a similar problem from the graph theory literature.

The problem is as follows, given a fully connected graph $G=(V,E)$ with weights $w_i$ on the edges. Find a partition which removes edges $E_p$ $(E_p \subset E)$ to create exactly $k$ connected components that maximize an objective. A solution or mapping for $k=2$ should be good enough to get me started so I'll just formulate the problem for k=2. The partition seeks to maximize a function over the $2$ subgraphs $\frac{\sum\limits_{w \in W_1} w}{|S_1|}+\frac{\sum\limits_{w \in W_2} w}{|S_2|}$ where $W_1$ and $W_2$ are the set of edge weights for connected components $S_1$ and $S_2$. Without the cardinality normalization term this problem can be mapped to min-cut. There is some similarity here with the ratio cut problem which seeks to maximize $\frac{cut(S_1,S_2)}{|S_1|}+\frac{cut(S_1,S_2)}{|S_2|}$ but I have been unable to find any mapping between the problems. Any suggestions or key search terms would be helpful


texts: Complexity of low-rank matrix factorizations with rows in a simplex and outliers

texts:
Our goal is to obtain a matrix factorization in form of $M = U V'$, where $U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$ and each row of $V$ satisfies
$$ \sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0 $$
for each $i$. Also, we have $rank(U)=r$ and $N\gg r$, which means that $U$ is the basis matrix and $V$ is the coefficient matrix.

We know that there exist methods including semi-nonnegative matrix factorization and convex nonnegative matrix factorization, but these methods do not guarantee convergence to the globally optimal solution. Moreover, we aim to make the algorithm robust to outliers. So we are wondering whether there is any method that solves this problem with theoretical guarantees or there is hardness characterization.

A much simpler equivalent formulation of this problem is: if we have a $(r-1)$-dimensional simplex with outliers, how do we find this simplex? Suppose that we have $r$ linearly independent basis $\{b_j\}_{j=1}^r$, and our observed data points are supposed to have the form of $$\sum_{j=1}^r \lambda_j b_j, \lambda_j \ge 0,\sum_j \lambda_j =1,$$ meaning that they lie on a simplex. However, due to corruption, some of these data points may not lie on the simplex, but still, lie in the linear space spanned by the $r$ basis, which means that they are outliers. The outliers still have the form of  $\sum_{j=1}^r \lambda_j b_j$, but they do not satisfy $\sum \lambda_j=1$. Moreover, suppose that we have $N$ data points ($N\gg r$) of which $f$ points are outliers and we want $f/N$ to be as large as possible. Our question is how to develop a robust algorithm to detect the simplex and outliers.


texts:
I am trying to understand the bitcoin protocol in the context of computational cryptographic security.

The question is a reference request to foundations of cryptography articles on bitcoin.

My first question is what abstract cryptographic protocol bitcoin is trying to implement? Do we have a definition of electronic money/digital currency in cryptography that captures bitcoin? What are the security requirements for a secure electronic money?

If the answer is yes, companies like eBay provide a centralized mean of electronic money transfer. Does considering a decentralized electronic money changes the definition of abstract cryptographic protocol for electronic money? Or is it just the same concept but in a model where there is no trusted third party?

Can the adversary break the protocol if it has more computational power than the combined computational power of other (honest) parties?

Assume that we have $n$ parties $P_i$ for $1 \leq i \leq n$ plus an adversary $A$ networked and the adversary wants to break the bitcoin protocol. For simplicity let's assume that the network graph is $K_{n+1}$ and adversary does not control the network and simply is a party like others. What would be the exact mathematical claim about the security of the protocol in this simple case?


texts:
Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all $i$, $P = \cup_{i=1}^n P_i$ and $Q = \cup_{i=1}^n Q_i$. It is known that if $P$ and $Q$ are polygons of equal area, such an equidecomposition always exists and that this does not hold in general for higher dimensions.

I am curious as to the complexity of the minimum equidecomposition problem:

  For two polygons $P$ and $Q$, find a equidecomposition $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ that minimizes $n$.

Are there algorithms (exact, polynomial, exponential, approximation) for this?  Is the complexity known?


texts: Why does randomness have stronger effect on reductions than on algorithms?

texts:
It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite different effect on polynomial time reductions. By the well known result of Valiant and Vazirani, $SAT$ reduces to $USAT$ via randomized polynomial time reduction. It is not likely that the reduction could be derandomized, since it would yield ${\bf NP}={\bf UP}$, which is thought unlikely.

I wonder, what could be the reason for this asymmetric situation: derandomization seems quite possible in probabilistic polynomial time algorithms, but not in  probabilistic polynomial time reductions?


texts: Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial?

texts:
AFAIK, The first evidence of using higher order functions goes back to Schönfinkel's 1924 paper: "On the Building Blocks of Mathematical Logic" - where he allowed one to pass functions as arguments to other functions.

That seems interesting. However, everything that I've been reading about his work (and Curry's by extension) seems to allude to one thing in some form or the other: [higher order functions]...this eliminates the need for bound variables...

What I haven't been able to wrap my head around is - what's the big deal? Why did logicians and mathematicians of that time care about this? And do we as theoreticians, care about this today? Why was it "groundbreaking" to get rid of bound variables and what impact did (or does) it have on computing (theoretically) as we know it?

PS: I'm aware of how his work paved way for $\lambda$-calculus and the impact of "it" on computing and functional programming in general. My question is mostly directed to the time "prior" to the creation of $\lambda$-calculus and "after" Schönfinkel's paper. The fact the Curry independently picked up that line of work, which was later known as "combinatory logic" too alludes to the importance of Schönfinkel's work.


texts: Complexity of approximating the range of a matrix

texts:
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:

$$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$

I believe that it is NP-hard to compute $S_M$ exactly, by applying the reductions from Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1 to the following decision problem: does $S_M = 2^n$?

  Is it possible to approximate $S_M$ to within a constant factor in
  polynomial time? If not, what is the best one can do in polynomial
  time?

[Cross-posted to https://mathoverflow.net/questions/229852/complexity-of-approximating-the-size-of-the-range-of-a-matrix ]


texts: Linear Programming with Modulo Linear Constraints

texts:
Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as:

find feasible point s.t.

$\min \sum_{ij}v_{ij}$

for all $(i,j)$ in $E$

$z_{ij} \le (c_i - c_j) \bmod k$ (i)

$z_{ij} \le (c_j - c_i) \bmod k$ (ii)

$z_{ij} + v_{ij} \ge 1$ (iii)

Think of the last as something like the soft margin constraint for an SVM.

In other words, all $c_i$ are real numbers and the absolute modulo $k$ difference between all adjacent $c_i,c_j$ must be greater than 1. It seems like a sensible notion of an update to de-violate constraints is to increase a given variable $c_i$ to make minimize the objective, then hop to a neighbor with infeasible edges and do the same, repeat, etc. Each greedy local update is natural.

What sort of issues would this formulation encounter if I tried to put it into practice? Could I get a reasonable approximation procedure from it, or would I be stuck with a heuristic, or is it likely to fall into some sort of weird cyclic behavior.

In general, what can I do and not do with modulo constraints for linear programming?


texts:
In connection to this question:
Expected values of Kolmogorov complexity in a random sample

Let $n$ be number of bits. Let $A = \{0,1,2,\dots,2^{n}-1\}$ be indexed by the $n$-bits. Let $ \delta > 0$ be fixed. Is there an estimate of what fraction of integers in $A$ can have Kolmogorov complexity be greater than $\delta n$?


texts: How are side effects handled in semantics?

texts:
In Anthony Aaby's "Introduction to Programming Languages" section on Semantics, he makes the following observation:

  Much of the work in the semantics of
  programming languages is motivated by
  the problems encountered in trying to
  construct and understand imperative
  programs---programs with assignment
  commands. Since the assignment command
  reassigns values to variables, the
  assignment can have unexpected effects
  in distant portions of the program.

This strikes me as a remarkable admission, that allowing side effects would motivate a major part of the work in semantics.

How does the existence of side effects in a programming language impact the ability to map a program to a computational model?  Are there approaches to managing state that can improve this process while still allowing side effects?


texts: Non-Linear Programming with \min operator in the constraint

texts:
Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1.

\begin{align}
  \text{maximize } &\sum_{i,j=1}^{m,n} c_{ij} \gamma_{ij} \notag\\
  \text{subject to: }& \notag\\
  &  \gamma_{ij} = \min\{1, \sum_{k = 1}^{K}{x_{ik}y_{jk} }\}  &&
\forall i,j\\
  & 0 \le x_{ik}, y_{jk} \le 1 && \forall i,j,k
\end{align}


texts: Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?

texts:
There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, here, here, and on the Wikipedia page). However, the first article to prove the result was only co-authored by Bar-Hillel:

Y. Bar-Hillel, M. Perles, E. Shamir. On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14:143–172, 1961.

Is there a good reason the result is sometimes called Bar-Hillel's Lemma, or is it simply a mis-attribution?


texts: Communication complexity problems with linear distance

texts:
Are there any known (non-trivial) randomized communication complexity lower bounds for natural gap problems in which the 1-inputs are linearly far from the 0-inputs? That is, partial functions $f:\{0,1\}^{2n} \to \{0,1,*\}$ such that the Hamming distance between every $(x,y) \in f^{-1}(1)$ and $(x',y') \in f^{-1}(0)$ is linear -- and that $f$ requires randomized protocols to communicate (say) $\Omega(\sqrt{n})$ bits?

(For instance, the Gap-Hamming-Distance problem has $2\sqrt{n}$ distance, whereas I'm looking for $\Omega(n)$ distance; where $GHD(x,y) = 1$ if $HD(x,y) \ge n/2 + \sqrt{n}$ and $GHD(x,y) = 1$ if $HD(x,y) \le n/2 - \sqrt{n}$.)

Edit: As pointed out by Igor, any communication complexity predicate can be made into a problem with linear-distance by requiring the inputs to be encoded by a good code. What interests me though, is whether there exist problems in the literature, in which the linear-distance occurs in a natural way (as the distance in the Gap-Hamming-Distance problem).


texts: All literals implied by a set of horn clauses

texts: What is the name of this problem: given a set of Horn clauses (in fact just definite clauses and facts), find the set of literals which can be deduced from it. E.g. given $\{a, a \Rightarrow b, b \wedge c \Rightarrow d\}$, output $\{a, b\}$.


texts: The meaning of separations in cryptography

texts:
From the paper of Impagliazzo and Rudich "Limits on the Provable Consequences of One-Way Permutations":

  We provide strong evidence that it will be difficult to prove that secure secret agreement is possible assuming only that a one-way permutation exists. We model the existence of a one-way permutation by allowing all parties access to a randomly chosen permutation oracle. A random permutation oracle is provable one-way in the strongest possible sense.

Given that we don't know if one-way function exists, how should one interpret this? Doesn't the above say one-way fucntion does exist?

Also, they exhibit an oracle relative to which one-way permutation exists, but not key agreement. Again, how is that possible? What does that mean? A black-box key agreement can be constructed independently ignoring both the oracle and the one-way permutation.


texts: Type checking, Hypothetical judgments, meaning explanations and computational type theory

texts:
We say that a system is a computational type theory if it is a type theory defined by not a bunch of inference rules, but some sort of Martin-Löfian meaning explanations (e.g. in the sense of NuPRL). Now according to Martin-Löf's meaning explanations [1], a hypothetical judgment of the form
$$ x_1 : A_1, ..., x_n : A_n \vdash a : A \qquad\qquad\qquad\qquad\qquad\qquad (1)$$
means that
$$ \vdash a[x_1,...,x_n/a_1,...,a_n] : [x_1,...,x_n/a_1,...,a_n]A \qquad (2)$$
for all closed terms $a_1 : A_1, ..., a_n : A_n$ (and also that this judgment should be functional in respect to judgmental equality, but I don't need to tackle this issue here).

This means, among other things, that the judgment
$$ x : \mathsf{empty} \vdash \mathsf{1} : \mathsf{nat} \to \mathsf{nat}  \qquad\qquad\qquad\qquad\qquad\qquad\quad (3)$$
is derivable in the theory, since there are no closed terms of the empty type (for the condition given is vacuously true). But also that less obvious judgments are also vacuously evident:
$$ x : \mathsf{nat} \times (\mathsf{nat} \to \mathsf{empty}) \vdash \mathsf{1} : \mathsf{nat} \to \mathsf{nat} \qquad\qquad\qquad\qquad (4)$$
since any closed term of $\mathsf{nat} \times (\mathsf{nat} \to \mathsf{empty})$ gives us a closed term of $\mathsf{empty}$, which should have none.

My question is:

  What is a nice way to implement a type checker for such a hypothetical judgments?

(I'm aware that the problem is undecidable in general, but in theory this should affect us only in the sense that we are unable to rule out all invalid judgments).

For simplicity, we can suppose that we already have a type checking algorithm for categorical judgments.

IMHO$-$and in the spirit of the universal introduction rule of predicate logic$-$the obvious type checking algorithm for (1) to say that it is valid whenever $$\vdash a[x_1,...,x_n/t_1,...,t_n] : [x_1,...,x_n/t_1,...,t_n]A$$ for a list of arbitraries closed terms $t_1 : A_1 ,..., t_n : A_n $ (since we can't possibly consider each closed term of such types). However, this algorithm is clearly unable to validate sequents such as (3), let alone (4).

There is a quick highly-inelegant fix, which is to add the condition that if you find $x : \mathsf{empty}$ in the context list, halt and automatically recognize the whole sequent as true. But what about not-so-evident vacuously evident judgments such as (4)?

Anyway, how would a correct, elegant and general approach look like?

PS: I'm sorry if the question is not precise enough, but I can't think of a better way to state it.

[1] Martin-Löf, Constructive Mathematics and Computer Programming, 1982.


texts: Upper bound on Euler characteristic of downward closed family

texts:
(Definition: $\mathcal{F}$ is called downward closed if for any $A \in \mathcal{F}$
and $B \subseteq A$ it holds that $B \in \mathcal{F}.$)

Let $\mathcal{F}$ be a downward closed family of subsets of $\{1, ..., n\}$
generated by $m$ sets.
Let $\chi(\mathcal{F})$ := number of odd cardinality members of $\mathcal{F}$ minus
the number of even cardinality members of $\mathcal{F}.$
Prove or disprove: $|\chi(\mathcal{F})| \leq m^{O(\log n)}.$

MathOverflow Link:
https://mathoverflow.net/questions/161471/is-euler-characteristic-of-a-simplicial-complex-on-n-vertices-and-f-facets-a?lq=1

As a side question, I am also curious about how easy/hard it is to compute/approximate
$|\chi(\mathcal{F})|$ given $n$ and the $m$ generators of $\mathcal{F}.$


texts:
Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one.

More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?


texts: Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT

texts:
Stated briefly, my question is: is Karp's original proof reducing SAT to 3SAT  unnecessarily elaborate?  The details are as follows.

In his 1972 paper Reducibility Among Combinatorial Problems, Karp proved that SAT reduces to 3SAT by stating:

  Replace a clause $\sigma_1 \cup \sigma_2
 \cup \ldots \cup \sigma_m$, where the
   $\sigma_i$ are literals and $m>3$, by
   $$
   (\sigma_1 \cup \sigma_2 \cup u_1)
   (\sigma_3 \cup \ldots \cup \sigma_m \cup \bar{u}_1) (\bar{\sigma}_3 \cup u_1) \ldots (\bar{\sigma}_m \cup u_1),
 $$
   where $u_1$ is a new variable. Repeat this
   transformation until no clause has more than
   three literals.

It seems to me that the final $m-2$ clauses (i.e. the clauses containing two literals) here are unnecessary. So, the construction is correct as written but it is more elaborate than necessary. Without the 2-literal clauses,  we obtain the construction usually given in undergraduate textbooks.   Is this correct, or am I missing something obvious?   I feel extremely unsure of myself suggesting that anything done by Karp could be expressed more elegantly.


texts:
Summary: if we are trying to use combinator logic to solve first-order logic type problems, is the best method to feed in free variables and use the standard first-order unification algorithm?

In standard first-order logic, consider the problem of deducing that the following is a contradiction

p(x)
~p(5)

By the rule that we can substitute specific for general, we can derive

p(5)
~p(5)

and q & ~q => false.

The particular choice of the constant 5 to substitute for x is obtained using the standard unification algorithm, which in the case of first-order logic is computable (and indeed quite efficient).

Translating this into combinator logic gives

p = K true
~(p 5)

Substituting the value of p gives

~(K true 5)

Evaluating gives

~true

Which is false, QED.

But it doesn't look so good when we try a more complex expression

p(f(f(x)))
~p(f(f(5)))

In standard first-order logic, unification works just as well here as for the simpler case. The translation to CL, however, is

S (K p) (S (K f) f) = K true
~(p (f (f 5)))

This isn't a problem we can solve with simple substitution. One approach we could try is to feed both sides of an equation the same value; if we take the number 5 as a value, the left-hand side of the equation evaluates as

S (K p) (S (K f) f) 5
K p 5 (S (K f) f 5)
p (S (K f) f 5)
p (S (K f) f 5)
p (K f 5 (f 5))
p (f (f 5))

So we have

p (f (f 5)) = K true 5
p (f (f 5)) = true

Substituting into the second expression from the original problem gives

~true

So we have solved the problem, but we did it by guessing the correct value to feed both sides of the equation, by inspection. Is there a general method that could be used?

One that suggests itself is to feed in a variable, which would give

p (f (f x)) = true

From which the standard first-order unification algorithm could be used.

Have we just established that the only way to solve problems in CL is to convert them back into standard logic? Perhaps it's not that bad; at least we have eliminated lambda and the other quantifiers, and their associated bound variables, leaving only free variables.

Still, is there a better method that I'm missing?

(I'm omitting consideration of types here; because combinator logic is Turing complete, presumably type checking will also be needed to avoid the paradoxes of the sort that make simple untyped lambda calculus unsound.)


texts: Statistical relationship between diameter and density in strongly connected random digraphs

texts:
I would like to know if there is any known relation between diameter and density in (connected) simple digraphs. Asymptotic results for n→∞, statistical, conditioned results that would restrict the graph class to a subset of all digraphs are also welcome...

For example, let's say I have a digraph $G$ constructed by the following algorithm :

produce $n$ vertices : $V_{G} = \{v_{i}, 0 < i < n\}$
for each vertex $v_{i}$, create the edge $i \rightarrow j$ with probability $p$

Let $G_{2}$ be the biggest strongly subgraph of $G$. Can we deduce a statistical relationship between the diameter $D(G_{2})$ and $p$ ?

EDIT : No answer seems to come, so any possible answer related to graphs that are defined through a different process (different random process, fixed arity, characterized subset of digraphs...) is also plainly welcome !

The goal is to use that relation in a complexity analysis, where the estimated complexity in time of an algorithm $A$ on a strongly connected digraph $G$ is $C(A,G) = D(G) * |V_{G}| * |E_{G}|$, where $D(G)$ is the diameter of $G$. I'd like to reduce the expression of mean complexity to an expression of $|V_{G}|$ and $|E_{G}|$ only.

Thanks by advance,
Alex

PS : I ported this question from math.stackexchange.com, since I didn't get any answer there for a week.


texts: What is the current known hardness of Graph Isomorphism?

texts:
Inspired by the question is factoring known to be P-hard, I wonder what the current similar state of knowledge is about the hardness of graph isomorphism. I am sure that it is currently not known if GI is in P, but:

  what is the currently known largest class that GI is harder than?

(it was not answered at a similar sounding question)

To address some of the comments, I want to know the currently known maximal class(es) that GI, the problem is complete for. Known algorithms for GI are upper-bounded by superpolynomial functions, and it is a member of NP. But it is not known that GI is P-hard. I'd like to know any classes C for which it -is- known it is C-hard, and hopefully as inclusive as possible.


texts: Complexity of the min edge-colored cut problem

texts:
Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V_1,V_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V_1, v \in V_2$ is minimized.

For example, a cut with 1 blue edge, 1 red edge, and 1 yellow edge between $V_1$ and $V_2$ is worst than a cut with 10 blue edges and 15 red edges between $V_1$ and $V_2$.

Of course, the uncolored cut is well-known to be polynomial-time solvable. The complexity of this colored version is reported as an open-problem in http://hal.archives-ouvertes.fr/hal-00371100/en. It surprise me. Do I miss some known result?


texts:
Sometimes it is useful to enumerate in increasing order
  programs that have a given type.  A
  simple example  is test
  generation for compilers: we want to test a new optimising phase and
  are interested in generating programs that trigger that phase (we
  use types for this purpose). Since we want to find 'minimal'
  examples exhibiting  bugs in the new optimising phase, it makes
  sense to start with the smallest programs as test cases first.
Another (somewhat trivial) example is superoptimising compilation where
we enumerate all possible assembly programs by increasing length. The typing system is trivial in the sense that all assembly programs are admissible.

  There is a trivial algorithm solving this problem: lazily enumerate
  all untyped programs and do type inference on each, reject those
  that fail to type. The trivial algorithm is unlikely to be
  efficient since for reasonable typing systems, most programs don't have the target type.  Surely one can do better by interspersing typing and
  enumeration. Let's express this problem in a more abstract setting.

  Assume fixed an untyped programming language $L$ and a well-founded partial-order (or
  preorder) $\sqsubseteq$ on $L$ programs. We are also given a typing
  system for $L$. We write $\Gamma \vdash P : \tau$ to indicate that
  program $P$ has type $\tau$ assuming $P$'s free variables are typed
  as described in the typing environment $\Gamma$.

Problem.  Given a typing environment $\Gamma$
  and a type $\tau$, (lazily) enumerate (in increasing
  $\sqsubseteq$-order) all programs $P$ such that $\Gamma \vdash P :
  \tau$.

Note that my formulation of the problem has been deliberately vague,
  for it's likely that a lot depends on $\sqsubseteq$ and the typing
  system. Most orders $\sqsubseteq$ will be too complicated to admit
  efficient algorithms, I imagine. The orders I have in mind are program size, or weighted program size (some program constructors are 'heavier' than others).

    Question. What is the state-of-the-art of research on efficient algorithms for
  such (and related) problems?


texts: Abstract stone duality and cohesive homotopy type theory

texts:
I have been reading the real-cohesive homotopy type theory paper and one of the remarks has sparked an interest. In this paper a string of monadic and comonadic modalities is introduced together with cohesion axioms, such that it is possible to prove that $\int \mathbb{S}^1 = S^1$ (Theorem 9.17), where $\int$ is one of the comonadic modalities, $S^1$ is the higher inductive type of circle, and $\mathbb{S}^1$ is defined  as some circle in terms of the type of reals $\mathbb{R}$.
Are there any result, papers, blogposts, mailing list discussions etc., which (attempt to) connect the lambda calculus term for various topological spaces as in Abstract stone duality with the higher inductive types in homotopy type theory?
Is there a theory which extends Abstract stone duality to homotopy type theory and where it would be possible to develop synthetic topology and connect it to the higher inductive types? Something I am imagining is some form of synthetic topology in terms of types connected with higher inductive types using modalities without mentioning reals.


texts: Closure of unambiguous context-free languages under pre- and postfix.

texts:
Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: if $L$ is context-free and has a non-ambiguous grammar, is the same true for $ppc(L)$?

I believe that this kind of basic question would already have been resolved in the heyday of language theory, but I could not find a suitable reference.


texts: Reconstruction Conjecture and Partial 2-trees

texts:
Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.

Searching relevant literature, I found that the following classes of graphs are known to be reconstructible :

trees
disconnected graphs, graphs whose complement is disconnected
regular graphs
Maximal Outerplanar Graphs
maximal planar graphs
outerplanar graphs
Critical blocks
Separable graphs without end vertices
unicyclic graphs (graphs with one cycle)
non-trivial cartesian product graphs
squares of trees
bidegreed graphs
unit interval graphs
threshold graphs
nearly acyclic graphs (i.e., G-v is acyclic)
cacti graphs
graphs for which one of the vertex deleted graph is a forest.

I recently proved that a special case of partial 2-trees are reconstructible. I am wondering if partial 2-trees (a.k.a series-parallel graphs) are known to be reconstructible. Partial 2-trees do not seem to fall into any of the above mentioned categories.

Am I missing any other known classes of reconstructible graphs in the above list ?
In particular, are partial 2-trees known to be reconstructible ?


texts: Flow networks: Push flow on either edges but not both!

texts:
I have a flow network with random capacities on edges, is there some way to add a constraint of the type (push flow on either one of these two edges but not on both)?

I'm not sure if this is correct or not, but I think the maximum independent set problem can be reduced to the problem I stated above, let's call our graph $S$ and make a flow network $G$ with a source node $src$ and sink node $sink$.

For each vertex $v \in V(S)$ we make an edge $(src \rightarrow sink)$ with capacity 1 in $G$ and for each edge $(A \rightarrow B) \in E(S)$ we add the constraint to pass flow on either the edge that corresponds to $A$ or $B$ in $G$ . The resulting maximum flow on $G$ is the cardinality of the maximum independent set on $S$ and the set of saturated edges in $G$ are the nodes in the maximum independent set of $S$ .

Is my intuition correct or not?


texts: Finding two vertices with the most/least common neighbors

texts:
I am not a computer scientist so please bear with me if this is a naive question.

Take any graph, pick a set S of vertices (by some criteria or random).
Find two vertices in set S with the most/least number of common neighbors.

This feels like a "hard" problem to write an efficient algorithm for, because if set S has n vertices, I might need to make n choose 2 or n(n-1)/2 comparisons. I am hoping to do this "efficiently" in terms of time complexity.

Is there a similar problem in computer science that has been studied, which I can look up in textbooks or research papers?

Edit - Additional Info

Many thanks to the two comments. I should add that I am looking for non-matrix multiplication methods because I am working with a large dataset in a sparse graph format like edgelist or compressed sparse row.


texts: Formalization of dependent record types/kinds in MLTT or variant thereof?

texts:
Has anyone formalized Pollack's Dependently Typed Records in Type Theory ? Agda would be preferred, but anyone close to MLTT would work.  Weaker versions would be fine too, i.e. what Luo dubs 'dependently kinded records would be appreciated as well.

Full reference:

@Article{Pollack2002,
author="Pollack, Robert",
title="Dependently Typed Records in Type Theory",
journal="Formal Aspects of Computing",
year="2002",
month="Jul",
day="01",
volume="13",
number="3",
pages="386--402",
abstract="The language Pebble of Burstall and Lampson proposed dependent types as the underlying principle in a unified framework to explain facilities for programming in the large, such as modules and signatures, as well as for programming in the small. This proposal soon extended to large scale formal proof development as well. In fact, the functional approach to modularity has turned out to be a hard problem, which is still far from a fully satisfactory solution. This paper discusses aspects of this approach, including representations of records, informative signatures, sharing, and subtyping. My main contribution in this paper is to show that structures with dependent types and manifest fields (roughly ML style modules) are internally definable in a type theoretic framework extended with inductive-recursive definition. This shows that powerful modules follow from general principles without module-specific assumptions.",
issn="1433-299X",
doi="10.1007/s001650200018",
url="https://doi.org/10.1007/s001650200018"
}


texts: The connection between compressed sensing and sparse representation

texts:
If I understand correctly, Compressed Sensing as an application of Sparse Representation is defined as:

  To find linear compression schemes for huge input signals that are
  known to have a sparse representation, so that the input signal can be
  recovered efficiently from the compression (the "sketch").(ref: this
  question)

So based on my understanding, compressed sensing is like a precoding before analog to digital data conversion.
And my take on sparse representation is:
A signal can be represented as a linear combination of basis functions where the set of basis functions is called dictionary and data samples are much more than their features. Mathematically, in the system of linear equations $Y=DX$ where $Y \in \mathbb{R}^{n \times N} (n \ll N)$ we seek a dictionary that results in sparse representation of $Y$.

So as far as I've understood, the output of sparse representation is used in compressed sensing. In my thesis on dictionary learning, after an introduction about compressed sensing, I'd like to talk a bit about the connection between compressed sensing and sparse representation before getting into the details of sparse representation. What I fail to do  is to explain the connection between the two even though I am aware of the concepts.
I'd like to have a good understanding of the connection between compressed sensing and sparse representation. Any explanation would be greatly appreciated!


texts: Complete axiomatization of relation algebras without ${}^-$ and $\top$

texts:
I'm working on a more thorough algebraic treatment of delta modeling. Briefly, deltas are syntactic entities that can modify products (as in 'software products'). They actually represent relations on products, so that they could be both partially defined and non-deterministic.

I've been looking into relation algebras. For obvious reasons they seemed like a good place to start.

A relation algebra is a structure $(S, \vee, \wedge, {}^-, \bot, \top, \cdot, \epsilon, {}^\smallsmile)$ with disjunction, conjunction, negation, an empty element, a complete element, composition, a neutral element and converse. Semantically they correspond to the relation operations $(2^{P^2}, \cup, \cap, {}^{\mathsf C}, \varnothing, P^2, \circ, \mathrm{id}_P, {}^{-1})$.

But this is more expressiveness than I need. If I could just remove negation $^-$ and the complete element $\top$, the operations that remain have sensible interpretations for delta modeling. Moreover, it seems that in contrast to $^-$ and $\top$, the operations that remain are in a sense 'constructive' (though I'm not sure the term is apt here), since their meaning does not depend on the description of the full set of products $P$.

Has the structure $(S, \vee, \wedge, \bot, \cdot, \epsilon, {}^\smallsmile)$ been studied? Is there a complete axiomatization for it (with respect to the behavior of the corresponding relation operations)? Does it have a decidable theory?

Edit: I've discovered the work of Hajnal Andréka and Szabolcs Mikulás. In particular the article entitled Axiomatizability of positive algebras of binary relations (a PDF version can be found with Google).

This article seems to summarize some of the results I need. If I understand correctly, the exact structure I describe is not finitely axiomatizable, but it will be if I also remove either $\wedge$, $\cdot$ or ${}^\smallsmile$. Moreover, any signature without that combination, but with $\cdot$ and either $\vee$ or $\wedge$, is finitely axiomatizable.

However, I'm not well-versed enough yet in abstract algebra to write up a coherent answer myself. For example, I don't understand why the presence of $\vee$ or $\wedge$ is required. If I omit both, aren't we simply in monoid territory? And I also still don't know about a decidable theory.

So I would still appreciate it if someone with more experience could write up an answer, preferably one that is easier to understand for the layman than the above cited article.


texts: Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

texts:
In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between these two problems that also works as a reduction from counting satisfying assignnments to counting 3-dimensional matchings.
My question then, is what is an example of a parsimonious reduction from 3-SAT to 3-DM?
Additional Context:
The only reduction from 3-SAT to 3-DM I know of is the one presented in Garey & Johnson's Computers and Intractability (page 50, theorem 3.2). That reduction involves composing certain variable gadgets, clause gadgets, and garbage collection gadgets. Roughly speaking, a satisfying assignment is mapped to a partial matching of vertices in the variable and clause gadgets, and then this partial matching is extended to a full matching using the garbage collection gadgets.
It seems like that reduction ought not to be parsimonious because each satisfying assignment is mapped to a partial matching, and there are many different ways of using the garbage collection to extend this to a full matching. In addition, if a satisfying assignment is chosen that does not set a unique literal to True in each clause, the clause gadgets also seem to have multiple ways to extend the matching.
Is there a way to fix this reduction to be parsimonious? Or is the parsimonious reduction completely different? Or maybe the observations I made in this question are false?


texts: Computational complexity of quantum optics

texts:
In "Requirement for quantum computation", Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table:

MY question is three-fold:

Nine years later, can the last cell be filled in?
If a column is added with the title "Universal for BQP", how would the rest of the column look?
Can Aaronson and Arkhipov's 95 page masterpiece be summarized into a new row?


texts: Difference between theory and practice of security and cryptography?

texts:
What interesting differences are there between theory and practice of security and cryptography?

Most interesting will of course be examples that suggest new avenues for theoretical research based on practical experience :).

Answers might include (but are not limited to):

Examples where theory suggests something is possible but it never gets used in practice
Examples where theory suggests that something is safe that is not safe in practice
Examples of something in widespread practical use has little theory behind it.

...

Caveat

If your answer is essentially of the form "Theory is about asymptotics, but practice is not," then either the theory should be really central, or the answer should include specific examples where the practical experience on real-world instances differs from the expectations based on the theory.

One example I know of: secure circuit evaluation.  Very powerful in theory, but too complicated to ever use in practice, because it would involve taking your code, unrolling it into a circuit, and then doing secure evaluation of each gate one at a time.


texts: reordering a DAG with the minimum changes

texts:
Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertice in topological order while keeping as many vertices as possible.
The problem is:  Is it NP-hard to find the reordering solution with the most vertice remaining still?
Note: This came up while I was trying to update the IP tables with the minimum operations. Since IP prefixes should be placed in the order of their prefix length, some prefixes existed in IP tables should be moved around when a new prefix is going to be inserted. The operation includes writing and nullifying(Note that we do not need to nullify a IP table entry before writing a new prefix into it),  I want to insert a prefix with the minimum number of operations. The proposed question is actually a special case of the IP table update problem, i.e., The IP table is full after inserting the new IP prefix.
The problem has been raised in find the most similar topological ordering of a dag, but it still cannot be solved. Although one person claims to prove that it is NP-hard, but due to my limited understanding, I cannot fully understand his answer.


texts:
There is no classical algorithm for $n$-bit TQBF with better than $O(2^n)$ complexity.  Is that also the best known bound for quantum algorithms / circuits?
Edit: As pointed out by Huck Bennett, in the full alternation subset of TQBF we can in fact beat $O(2^n)$ via randomized tree search.  This is the case I care about most, so I would also be curious for the best exponent for a quantum algorithm if there are all $n-1$ quantifier flips.


texts: "Relatives" of the shortest path problem

texts:
Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such that some function of the edge weights on the path is minimum. In this sense they are all "relatives" of the shortest path problem; in the latter the function is simply the sum.
Note: We are looking for simple paths, that is, without any repeated vertices. Since I did not find standard names for these problems in the literature, I named them myself.

Path with minimum weight gap: find an $s-t$ path, such that the difference between the largest  and smallest edge weights on the path is minimum.
Smoothest path: find an $s-t$ path, such that the largest step size on the path is minimum, where a step size is the absolute value of the weight difference between two consecutive edges.
Path with minimum altitude: Let us define the altitude of a path by the sum of the step sizes along the path (see the definition of step size above). Find an $s-t$ path with minimum altitude.
Path with minimum prime weight: assuming that all edge weights are positive integers, find an $s-t$ path, such that its weight is a prime number. If there is such a path, find one with the smallest possible prime weight.

Question: what is known about these path problems? (And others that could be conceived in a similar spirit, applying a different function of the weights.) In general, is there any guidance that which functions of the edge weights can be minimized in polynomial time, and which are NP-hard?
Note: it is interesting, for example, that while the sum of the weights is easy to minimize (it is the classical shortest path problem), but minimizing the closely related average of the weights on the path is NP-hard. (Assign weight 2 to all edges incident to $s$ and $t$, and weight 1 to all others. Then a min average weight path will be a longest $s-t$ path).


texts:
Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable language classes, although a formal proof that there are context-free languages not expressible via PEGs appears surprisingly elusive.

  Bryan Ford, "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation", 2002.

Is there a context-free language that is not expressible as a PEG?

As pointed out by Emil,
my proposed language $a^n a^* b^n$ does not work.
It can be expressed as the PEG $S \to a S b / a S / \varepsilon$.


texts: Introductions to steganography from an information-theoretic standpoint

texts:
Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to the field besides a few links and papers.

Kessler, Gary C. An Overview of Steganography for the Computer Forensics Examiner. Retrieved on 02/12/2015. www.garykessler.net/library/fsc_stego.html
Hopper, N. J., Langford, J., and von Ahn, L. (2002). Provably Secure Steganography. IEEE Transactions on Computers, 58, 662 - 678.
Hundt, C., Liskiewicz, M., and Wolfel, U. (2006). Provably Secure Steganography and the Complexity of Sampling. Algorithms and Computation, 4288, 754 - 763.


texts: How can the actor model be applied to allow pure functional languages to have side-effects?

texts:
I just read this blog post which argues that monads might be too obscure or difficult to understand as the default "interface to the impure world" in purely functional programming languages; instead, it suggests that the actor model would be more comprehensible when it comes to pedagogy.  That may be true -- I do think that actors are easier to understand than monads -- but the post leaves a lot to be desired.  In particular, the author offers no examples of what this sort of actor-based purely-functional language would look like, and he doesn't seem to have followed up on the blog post since it was written a few years ago.

So my question is:  in what way can actors be leveraged to capture side-effects in a purely functional way?  How would source code in that hypothetical language look?  What advantages/disadvantages would that approach offer in comparison to monads (outside of the cosmetic differences)?


texts: Example of pairwise independent random process with expected max load $\sqrt{n}$

texts:
This question was previously posted at https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now realise this is relevant to hashing so I am reposting it here.

Throw $n$ balls into $n$ bins.  Each bin is selected uniformly at random but the process is only pairwise independent.  Call the maximum number of balls in any bin the max load.

Lemma 2 in these notes tells us that the max load is at most $\sqrt{2n}$ with probability at least $1/2$.

  Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the
  expected max load to be $\Theta(\sqrt{n})$ asymptotically?


texts: Decidability of existential first-order theory of reals with exponential

texts:
The first-order theory over the reals as an ordered field with polynomials is decidable with doubly exponential complexity. However, if we additionally allow the exponential function, that is $e^x$ decidability is unknown (see here).

If we consider the existential fragment of first-order theory with polynomials the complexity is PSACE instead of doubly exponential (see here).

I am interested in results concerning decidability of existential first-order theory with polynomials extended with the function $a^x$, where $a$ is a rational number. I consider this not standard exponential function because of the application I have for this logic.


texts: Is black box parallel quantum speedup ever nontrivial?

texts:
Grover's algorithm is not parallelizable, in that $p$ quantum processors searching over $n$ elements can't do better than $O(\sqrt{n/p})$ queries.

Are there any oracle problems where quantum computers see some polynomial speedup over classical, but where the algorithm is nontrivially parallelizable?  Here's one attempt at formalizing this:

Question: Are there any oracle problems such that

The classical complexity is $O(t)$, and achieves perfect parallel speedup to $O(t/p)$.
The quantum complexity is $O(t^\alpha)$ for $\alpha \in [1/4,1)$.
The parallel quantum complexity is $O(t^\alpha / p^\beta)$, with $\beta \in (\alpha,1]$.

Even better, is there a problem where $\beta = 1$ (perfect parallel quantum speedup)?


texts: How does Theoretical Computer Science relate to security?

texts: When I think of software that is insecure I think that it is "too useful" and can be abused by an attacker.  So in a sense securing software is the process of making software less useful.  In Theoretical Computer Science you aren't working with the real world.  So are there any security concerns when working with pure theory?  Or the other side of the coin, does Theoretical Computer Science affect the real world of people getting hacked?  If so,  what security topics are considered Theoretical?


texts: Kernighan–Lin algorithm and multiple gain functions

texts:
I want to know if there is an algorithm like KERNIGHAN-LIN for graph partitioning that can handle several (different) gain functions.

Is there some technique to combine gain functions in one algorithm?

The KL algorithm and its gain function is defined here for example:

http://www.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html#link_4.2


texts: Lower bounds on the period in integer factorization?

texts:
In 1975, Miller has shown how to reduce the factorization of integer $N$ to finding the period $r$ of a function $f(x)=a^x\;\bmod\;N$ such that $f(x+r)=f(x)$ with some randomly chosen $a<N$. It is well known that Shor's algorithm can find $r$ efficiently on a quantum computer, whereas it is believed to be intractable for a classical computer to find $r$.

My question now is: Are there any known lower bounds on $r$ for random $N$? Are there any bounds on $r$ given $N=pq$ is chosen as in RSA? Clearly, $r$ must be $\Omega(\log(N))$ as otherwise one could just evaluate $f(x)$ on $O(\log(N))$ successive points to figure out $r$ classically. Would it suffice to break RSA if there was a classical factoring algorithm which only works under some assumption on the distribution of $r$, e.g. $r \in \Theta(N/\log(N))$ or $r \in \Theta(\sqrt{N})$?

A presentation of Carl Pomerance on "The multiplicative order mod $n$ on average" cites evidence that $r$ is $O(N/\log(N))$ on average over all $N$, yet I'm not sure whether a classical algorithm which can factor $N$ under the hypothesis of $r \in O(N/\log(N))$ would conclusively break RSA. Can $N$ be adverserially chosen to have $r \in O(N))$ or $r \in O(\sqrt{N})$?

(Note: There is a related question on generic factoring vs. RSA factoring)


texts: What are the limitations of dependent typing?

texts: It seems dependent types can provide lots of desirable guarantees about program behavior. What kinds of program properties can they NOT guarantee (besides what's computationally infeasible)? Is there an even more powerful or general type system that can model any computable property of a program?


texts: I believe this problem to be NP-Complete, but I'm unable to find any references on possible reductions. Given a weighted graph (either undirected or directed, I cannot find results for either but am interested in both), and vertices s, t, u, find the shortest path from s to t which includes u. To clarify, the path should NOT repeat edges. Hence simply combining the shortest s-u and u-t paths is not valid.


texts: Why is it impossible to work with polylog length encoding schemes for quantum circuits?

texts:
I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said:

  The encoding disallows compression: it is not possible to work with
  encoding schemes that allow for extremely short (e.g.,
  polylogarithmic-length) encodings of circuits; so for simplicity it is
  assumed that the length of every encoding of a quantum circuit is at
  least the size of the circuit.

My question:

Why is it impossible to work with polylogarithmic-length encoding schemes for quantum circuits?


texts:
What bounds (lower or upper) are known about the complexity of partitioning a Directly Acyclic Graph (DAG) into paths of respective sizes $n_1,\ldots,n_w$, such that to minimize their entropy $n{\cal H}(n_1,\ldots,n_w)= n\lg n - \sum_{i=1}^w n_i \lg n_i$?

Motivation

Daskalakis et al. represent a Partially Ordered Set (poset) $P$ of width $w$ by $w$ chains and pointers of length $\lg n$ bits each between them. A partition such as the one described above would yield a smaller encoding of some posets?
Farzan and Fischer presented a data-structure for posets, compressed into space depending on $n$ and $w$ and supporting many operators in constant time, inspired from the one from  Daskalakis et al.. Plugging in a nice partitioning algorithm for DAGs would yield a data structure compressed into space depending on $n$ and the entropy of the poset (a finer measure than $w$).


texts: Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices

texts:
Are there any publications focusing on solving TSP with ant colony optimization that consider small changes in the graph's nodes or vertices?

So what I have is:

a traveling salesman problem (TSP)
and a single solution for the TSP
a slight change in the graph afterwards (extra/removed node for example)

and what I want is:

An ant algorithm to solve the new TSP (on a subset-basis) using the original solution
And a benchmark

Thanks for you help so far.


texts: Resources to learn about the P vs. NP problem

texts:
I was recently reminded about the $\mathsf{P}$ vs. $\mathsf{NP}$ problem as explained by Stephen A. Cook on Clay Mathematics Institute.

It has piqued my interest and I would like to learn more about it. The first step would be gaining a deeper understanding of the problem and an understanding of the area in general.

Can you recommend any books or other resources where I can learn more about the problem?


texts: Construct proof systems for common algorithmic task, like equivalence of regular expressions

texts:
A propositional proof system according to Cook and Reckhow for a language $L \subseteq \Sigma^{\ast}$ is a deterministic polynomial time function $f : \Sigma^{\ast} \to L$ that is onto.

For $y \in L$ a word $x \in \Sigma^{\ast}$ with $f(x) = y$ is called a proof for $y$.

Here is a post on the intuition, but I do not get it when I want to apply it.

For example, if I consider the language
$$
 EQUIV = \{ (u,v) : \mbox{$u$ and $v$ are equivalent regular expressions} \}
$$
then I know an algorithm for this language would be to convert these regular expression into NFA's, determinize them and minimize them and then check if they are isomorphic.

But how would a proof system for $EQUIV$ look like? Would it be a surjective function $f : \Sigma^{\ast} \to EQUIV$ where the arguments somehow codes the regular expression, DFA's for them and an isomorphism between those DFA's? Then $f$ would simply check if the isomorphism is a valid isomorphism between the DFA's, guess this would be a simple task.

But how to check that the regular expression belong to the DFA's, I am not sure if that would be an easy task as it involves computing DFA's for regular expressions, which might take exponential time, or? Or could it code additional DFA's which could easily be composed to REGEXPs with some fixed algorithms (but is it then easy to check that these give isomorphic minimal DFA's as the given ones? I mean that includes to find an isomorphism, which is not easy, so code that again into the input?).

Or am I on the wrong track, might a proof system look totally different?


texts: Is there an online-algorithm to keep track of components in a changing undirected graph?

texts:
Problem

I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected components of this graph.

Properties

Additional properties are that no two components will ever be reconnected. Obviously, the graph can have cycles to an arbitrary amount (otherwise the solution would be trivial).
If an edge $e$ does not contain a node $n$, it will never adopt that node. However, if $n \in e$, it can change to $n \notin e$.

Approaches

I have two possible approaches so far, but as you will see they are horrible:

Slow state-less

I can search (dfs/bfs) the graph starting from the modified element(s) every time. This conserves space, but is slow as we have O(n+m) for each modification.

Stateful fast(-er) (?) approach

I can store all possible paths for each node to all possible nodes, but if I see it correctly, this will take O(n^4) memory. But I am not sure how the runtime improvement is (if there is one at all, because I have to keep the information up-to-day for every node in the same component).

Question

Do you have any pointers, how I can learn more about that problem or perhaps some algorithms I can build on?

Note

If there is a vast improvement in runtime/memory I could live with a non-optimal solution that sometimes says two components are one, but of course I would prefer an optimal solution.


texts:
What is the underlying physical principle behind quantum fault tolerance in quantum computation?

I am trying to follow the mathematical steps behind quantum fault tolerance, and while I can just manage to do so, I have to admit I fail to see the underlying principle behind them, or the motivation for just why it works. I kind of understand how entanglement swapping with a heat sink lies behind quantum error correction, but what underlying principler lies behind quantum fault tolerance?


texts: Can we always find a graph with a given algebraic connectivity?

texts:
This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong.

I would like to experiment with various spectral properties of graphs, but in order to do so in a controlled way, I need to be able to find graphs with specified spectral properties. Unfortunately, I'm struggling to find literature on the topic, and I'm beginning to think it might be Hard to figure out myself.

More concretely, say I give you a value $\lambda \in [0,2]$. Can you find a $d$-regular graph on $n \gg 1$ vertices whose (normalized) Laplacian has its first nonzero eigenvalue $\approx \lambda$?

Ideally, we could fix $d$ in advance and only vary $n$, but I'm open to solutions which allow $d$ to vary.
Now, obviously we can't relax the notion of $\approx \lambda$. Since $\lambda$ must be a root of the (degree $n$) characteristic polynomial of the laplacian it cannot be entirely arbitrary. Moreover, if we want to keep $n$ from getting "too big", approximation is necessary even when $\lambda$ is algebraic.
I also suspect this problem is Hard. Particularly if we want a deterministic algorithm (this is another reason to allow some wiggle room with $\lambda$). If we had a good handle on building graphs with given spectral properties, then we would be able to make good expanders using similar technology. Since that problem is currently quite hard, I suspect this one is too. My only hope is that the smallest eigenvalue may be easier to control than the largest one (which is what we would have to control to build an expander).
Are there any results for building graphs with a predetermined algebraic connectivity $\lambda$?
Thanks in advance ^_^

I see on this site there's a similar question here that I didn't find while googling. Seeing as that question is quite old, I think I'll ask this one anyways to see if there's any new results. Plus, I'm primarily interested in the (slightly easier?) problem of controlling only one eigenvalue.


texts: Forbidden Subgraph Characterization for Graphs with few Maximal Cliques

texts:
Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced subgraphs of this property.
In a paper on this topic [1], we showed that given a graph which violates the $s$-vertex overlap property, one can compute a subgraph with $O(s^2)$ vertices that still violates the property in polynomial time as follows: Find a vertex $v$ that is contained in at least $s+1$ maximal cliques. This can be done in polynomial time using a polynomial delay clique enumeration algorithm. Choose $s+1$ of these maximal cliques. Then, choose for each pair of maximal cliques $A$ and $B$ a pair of vertices that witnesses that these maximal cliques are distinct. Altogether, we choose at most ${s+1 \choose 2} + 1 = O(s^2)$ vertices.
My question: Is this implicitly given characterization tight with respect to $s$? Or is there a forbidden subgraph characterization for example with $O(s)$ vertices?
Observe that there are minimal forbidden subgraphs with $s+2$ vertices, for example when $v$ is the center of a star with $s+1$ leaves. It may be easier to think about the property without the vertex $v$, then we are asking for minimal forbidden induced subgraphs for the graph property of having at most $s$ maximal cliques.
Michael R. Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann:
Graph-based data clustering with overlaps. Discret. Optim. 8(1): 2-17 (2011)


texts: In the neutral zone between polynomial and sub-exponential

texts:
What are examples of problems that are known to be sub-exponential, but

are known to be non-polynomial, or
are not known to be polynomial?

EDIT. Here is what I mean by sub-exponential (apologies for leaving this open). A function $f:\mathbb{N}\to\mathbb{N}$ is subexponential if $$f(n) = 2^{n^{o(1)}}.$$ (Thanks to Emil Jerabek for his help in the comment section below!)


texts: A continuous center point of a convex spherical polygon

texts:
In discrete geometry, the center point $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a center point always exists.)

My problem is similar but in a continuous setting.
I have a convex spherical polygon $P$ on the unit sphere. In this context an "area-center" point $c$ is such that any half sphere that contains $c$ also contains a part of $P$ whose area is at least a constant fraction of the area of $P$.

The definition can be similarly phrased with convex polygons on the plane and half-planes instead of half-spheres. It can also be generalised to higher dimension.

My questions are:

Does this definition has a well-known name? ("area-center point"?)
Do we know algorithm to compute such an area-center point? (exact or approximate)

(My motivation for finding such a point is for doing logarithmic search on the unit sphere.)

I ask this question here because searching the web only leads me to centroids or discrete center point, or the Tverberg generalization, but nothing related to the specific definition given above. (I have already asked question 30 minutes ago on math SE, but realised it is probably more relevant to comp. geom. hence its posting here)

Thank you !


texts:
I am reading Paxos Made Simple. I am quite confused about the proof of P2b. It said

  We would make the proof easier by using induction on n, so we can prove that proposal number n has value v under the additional assumption that every proposal issued with a number in m..(n - 1) has value v.

How can he add the additional assumption? Is it reasonable? In reality, proposal numbered in m..(n - 1) can have value other than v, isn't it?

I am really confused about that, please help! Thanks


texts: Why have computer scientists chosen recursor instead of iterator in primitive recursion?

texts:
I wonder why computer scientist have chosen recursor instead of iterator (or tail recursor if you like) in primitive recursion, given that function defined in terms of iteration behaves more efficiently than that in terms of recursion.

EDIT:

Let us go further, do you think iteration would be better than recursion to complexity?


texts: Instances of Noninteractive Zero knowlege Proofs

texts:
I am working on Cryptographic protocols. While I was doing a survey, I required some "Non-Interactive Zero Knowledge Proofs" (NIZK) which I can use.

I can only find transformations between different models of NIZK in the abstract sense, like the Hidden Bits Model (J.Katz) and non-malleable NIZK (A.Sahai)

Is there any credible material like Thesis/Papers where I can find example constructions of Non-Interactive Zero Knowledge Proofs which I can make use for my protocols.

Thanks!


texts: Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory

texts:
The post is related to:
https://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

How far away is the Lovasz bound from the zero-error capacity of regular graphs? Are there any examples where the Lovasz bound is known to be not equal to the zero-error capacity of a regular graph? (This was answered below by Oleksandr Bondarenko.)

In particular is any strict inequality known for odd cycles of sides greater than or equal to $7$?

Update
What improvement is needed in spectral theory to improve the Lovasz theta function so that the gap between Shannon capacity and Lovasz Theta for the cases for which a gap exists could be lowered? (Note I am concerned only from spectral perspective)


texts: Is there any such thing as a non-nested hierarchy?

texts:
(I didn't see any question like this on the CSTheory exchange -- apologies if it has already been answered.)
In a nested hierarchy, a higher level includes all levels below it.
The classic example of a "non-nested" hierarchy is military rank.  A general is not a lieutenant, so military rank is a non-nested hierarchy.
But here's my objection -- doesn't a general have all the skills a lieutenant has, plus more skills?  So in that sense, isn't every general a lieutenant?  He may not be called "lieutenant", but in reality he is a lieutenant-plus.
Thus, I am wondering... can we really say that any hierarchy is non-nested?


texts: Why Ramanujan graphs are named after Ramanujan?

texts:
I recently taught expanders, and introduced the notion of Ramanujan graphs.
Michael Forbes asked why they are called this way, and I had to admit I don't know.
Anyone?


texts: Commonalities and differences between canonical structures and the implicit calculus

texts: There is a paper on The Implicit Calculus as a generalization of type classes. Coq's canonical structures are also a generalization of type classes. The paper does not mention canonical structures however. The approaches seem quite similar. What are the commonalities and differences of these two approaches to generalize type classes?


texts: Intersection models for weakly chordal graphs?

texts:
Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :)

Among the many known classes of perfect graphs, there are three classes that I find especially interesting:

(1) the weakly chordal graphs, whose obstruction set is $\{C_n,\bar{C_n} : n \geq 5\}$,

(2) the chordal graphs, whose obstruction set is $\{C_n : n \geq 4\}$,

(3) the strongly chordal graphs, whose obstruction set is $\{C_n : n \geq 4\} \cup \{S_n : n \geq 3\}$.

Here, $C_n$ denotes the $n$-cycle, and $S_n$ denotes the $n$-sun (obtained by starting from a cycle $x_1 ... x_n$ and adding the edges $x_i y_i x_{i+1}$ for $1 \leq i \leq n$).

These classes admit polynomial algorithms for clique/independent set, the most general one being for the class of weakly chordal graphs and uses a clever 'two-pair contraction' argument (see 'Optimizing weakly triangulated graphs' by R. Hayward, C.T. Hoang and F. Maffray).

Intersection models are known for classes (2) and (3) as they correspond to the clique graphs of acyclic, resp. totally balanced, hypergraphs. Are there any known results about intersection models for weakly chordal graphs?

As a side note, there is a recursive construction of totally balanced hypergraphs due to Lehel (see 'A characterization of totally balanced matrices'), and I was also wondering about possible algorithmic applications of this result?


texts: Tight upper bound on the number of iterations of Weisfeiler–Lehman Procedure (Graph isomorphism)

texts:
Graph Isomorphism is a very well known problem in computer science. A generic procedure for the graph isomorphism problem builds on a simple color refinement procedure given below (One dimensional Weisfeiler–Lehman Procedure)

To begin with, all vertices have the same color.
In each color refinement step, if two vertices $u$ and $v$ have the same color but their neighbourhood are differently coloured (counting color multiplicity), then $u$  and $v$ get fresh different colours.

Please note that for $k$-WL runs at most $|V|^k$ refinement steps. See this paper by V. Arvind

Question 1: What is the tight upper  bound on the number of iterations of  Weisfeiler–Lehman Procedure?

I know that if the given input graphs are regular then in a one step (one iteration) algorithm will stop. I am thinking like this there is going to be partitioning of the vertices and in each iteration a partition can only split, so in the worst case at the end I can have at most $n-2$ partitions.

Question 2 : Are there graph classes not able to distinguish by color refinement procedure other than regular non-isomorphic graphs ?


texts: I am exploring the idea of writing a DBMS in purely functional way. The traditional data structure used for indexing is B-Tree. I'd like to know some purely functional equivalent of B-Tree that would be optimized to minimize disk access. Thanks.


texts: What is the worst case of the randomized incremental delaunay triangulation algorithm?

texts:
I know that the expected worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in Computational Geometry) is $\mathcal O(n \log n)$.
There is an exercise which implies the worst-case runtime is $\Omega(n^2)$.
I've tried to construct an example where this actually is the case but haven't been successful so far.

One of those tries was to arrange and order the point set in a manner such that, when adding a point $p_r$ in step $r$, about $r-1$ edges are created.

Another approach might involve the point-location structure:
Try to arrange the points such that the path taken in the point-location structure for locating a point $p_r$ in step $r$ is as long as possible.

Still, I'm unsure which of these two approaches is correct (if at all) and would be glad for some hints.


texts: Notation of sequences in rate distortion theory

texts:
I have been reading whatever sources I could get my hands on today, regarding this problem.
Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas M. Cover and Joy A. Thomas. The book seems well regarded so  I assume i am misunderstanding something.

I.e the following slides. I am confused by the notation - which comes from the book. If we look at slides 14 and 16 in the slides deck linked. Firstly on slide 14 they denote a sequence of random variables (i.e a sequence of bits, as far as I understand) as $X^n$
$$
X^n = (X_{1}, \ldots, X_{n}), \quad X_{n} \sim p(x)
$$
and the codeword for that sequence as $\hat{X}^n$.  Now moving on to slide 16 they seem to mix between $X^n$ and $x^n$ i.e they mention that the distortion between sequences
$$
d\left(x^{n}, \hat{x}^{n}\right)=\frac{1}{n} \sum_{i=1}^{n} d\left(x_{i}, \hat{x}_{i}\right)
$$

And distortion for a $\left(2^{n R}, n\right)$ code:
$$
D=E d\left(X^{n}, g_{n}\left(f_{n}\left(X^{n}\right)\right)\right)=\sum_{x^{n}} p\left(x^{n}\right) d\left(x^{n}, g_{n}\left(f_{n}\left(x^{n}\right)\right)\right)
$$

but as far as i can $x^n$ and $X^n$, and consequently $\hat{x}^n$ and $\hat{X}^n$ denote the same thing? What is the idea behind this, if any?  It would make more sense to me to keep the capitalization consistent unless I am missing something? This notation is consistent across all sources I could find.