What is the enlightenment I'm supposed to attain after studying finite automata? I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we study deterministic and non-deterministic finite automata (DFA/NFAs)? So here are some answers I came up with after soliloquing  but still fail to see their overall contribution to the 'aha' moment:

To study what they are and aren't capable of i.e. limitations

Why?

Since they are the basic models of theoretical computation and would lay the foundation of other more capable models of computation.

What makes them 'basic'? Is it that they have only one bit of storage and state transitions?

Okay, so what? How does all this contribute to answer the question of computability? It seems Turing machines help understand this really well and there are 'lesser' models of computations like PDAs, DFA/NFAs/Regexes etc. But if one didn't know FAs what is it that they are missing out on?

So although I 'get it' to some extent, I am unable to answer this question to myself? How best would you explain 'why study D/N-FAs'? What's the question they seek to answer? How does it help and why is it the first thing taught in Automata Theory?

PS: I'm aware of the various lexicographic applications and pattern matchers that can be implemented as such. However, I don't wish to know what it can be used for practically but what was their reason for use/invention/design during the culmination of studying the theory of computation. Historically speaking what led one to start with this and what 'aha' understanding is it supposed to lead to? If you were to explain their importance to CS students just beginning to study Automata Theory, how'd you do it?

I have personally enjoyed several Aha! moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole.

Does Non-determinism Lead to Efficiency? There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. Understanding this difference for Turing machines is at the core of (theoretical) computer science. NFAs and DFAs provide the simplest example I know where you can explicitly see the strict gap between determinism and non-determinism.
Computability != Complexity. NFAs and DFAs both represent regular languages and are equivalent in what they compute. They differ in how they compute.
Machines Refine Languages. This is a different take on what we compute and how we compute. You can think of computable languages (and functions) as defining an equivalence class of automata. This is a fundamental perspective change in TCS, where we focus not just on the what, but the how of computation and try to choose the right 'how' when designing an algorithm or understand the space of different how's in studying complexity classes.
The Value of Canonical Representation. DFAs are the quintessential example of a data-structure admitting a canonical representation. Every regular language has a unique, minimal DFA. This means that given a minimal DFA, important operations like language inclusion, complementation, and checking acceptance of a word become trivial. Devising and exploiting canonical representations is a useful trick when developing algorithms.
The Absence of Canonical Representations. There is no well accepted canonical representation of regular expressions or NFA. So, despite the point above, canonical representations do not always exist. You will see this point in many different areas in computer science. (for example, propositional logic formulae also do not have canonical representations, while ROBDDs do).
The Cost of a Canonical Representation. You can even understand the difference between NFAs and DFAs as an algorithmic no-free-lunch theorem. If we want to check language inclusion between, or complement an NFA, you can determinize and minimize it and continue from there. However, this "reduction" operation comes at a cost. You will see examples of canonization at a cost in several other areas of computer science.
Infinite != Undecidable. A common misconception is that problems of an infinitary nature are inherently undecidable. Regular languages contain infinitely many strings and yet have several decidable properties. The theory of regular languages shows you that infinity alone is not the source of undecidability.
Hold Infinity in the Palm of Your Automaton. You can view a finite automaton purely as a data-structure for representing infinite sets. An ROBDD is a data-structure for representing Boolean functions, which you can understand as representing finite sets. A finite-automaton is a natural, infinitary extension of an ROBDD.
The Humble Processor. A modern processor has a lot in it, but you can understand it as a finite automaton. Just this realisation made computer architecture and processor design far less intimidating to me. It also shows that, in practice, if you structure and manipulate your states carefully, you can get very far with finite automata.
The Algebraic Perspective. Regular languages form a syntactic monoid and can be studied from that perspective. More generally, you can in later studies also ask, what is the right algebraic structure corresponding to some computational problem.
The Combinatorial Perspective. A finite-automaton is a labelled graph. Checking if a word is accepted reduces to finding a path in a labelled graph. Automata algorithms amount to graph transformations. Understanding the structure of automata for various sub-families of regular languages is an active research area.
The Algebra-Language-Combinatorics love triangle. The Myhill-Nerode theorem allows you to start with a language and generate an automaton or a syntactic monoid. Mathematically, we obtain a translation between very different types of mathematical objects. It is useful to keep such translations in mind and look for them in other areas of computer science, and to move between them depending on your application.
Mathematics is the Language of Big-Pictures. Regular languages can be characterised by NFAs (graphs), regular expressions (formal grammar), read-only Turing machines (machine), syntactic monoids (algebra), Kleene algebras (algebra), monadic second-order logic, etc. The more general phenomenon is that important, enduring concepts have many different mathematical characterizations, each of which brings different flavours to our understanding of the idea.
Lemmas for the Working Mathematician. The Pumping Lemma is a great example of a theoretical tool that you can leverage to solve different problems. Working with Lemmas is good practice for trying to build upon existing results.
Necessary != Sufficient. The Myhill-Nerode theorem gives you necessary and sufficient conditions for a language to be regular. The Pumping Lemma gives us necessary conditions. Comparing the two and using them in different situations helped me understand the difference between necessary and sufficient conditions in mathematical practice. I also learnt that a reusable necessary and sufficient condition is a luxury.
The Programming Language Perspective. Regular expressions are a simple and beautiful example of a programming language. In concatenation, you have an analogue of sequential composition and in Kleene star, you have the analogue of iteration. In defining the syntax and semantics of regular expressions, you make a baby step in the direction of programming language theory by seeing inductive definitions and compositional semantics.
The Compiler Perspective. The translation from a regular expression to a finite automaton is also a simple, theoretical compiler. You can see the difference between parsing, intermediate-code generation, and compiler optimizations, because of the difference in reading a regular expression, generating an automaton, and then minimizing/determinizing the automaton.
The Power of Iteration. In seeing what you can do in a finite-automaton with a loop and one without, you can appreciate the power of iteration. This can help understanding differences between circuits and machines, or between classical logics and fixed point logics.
Algebra and Coalgebra. Regular languages form a syntactic monoid, which is an algebraic structure. Finite automata form what in the language of category theory is called a coalgebra. In the case of a deterministic automaton, we can easily move between an algebraic and a coalgebraic representation, but in the case of NFAs, this is not so easy.
The Arithmetic Perspective. There is a deep connection between computation and number-theory. You may choose to understand this as a statement about the power of number theory, and/or the universality of computation. You usually know that finite automata can recognize an even number of symbols, and that they cannot count enough to match parenthesis. But how much arithmetic are they capable of? Finite automata can decide Presburger arithmetic formulae. The simplest decision procedure I know for Presburger arithmetic reduces a formula to an automaton. This is one glimpse from which you can progress to Hilbert's 10th problem and it's resolution which led to discovery of a connection between Diophantine equations and Turing machines.
The Logical Perspective. Computation can be understood from a purely logical perspective. Finite automata can be characterised by weak, monadic second order logic over finite words. This is my favourite, non-trivial example of a logical characterisation of a computational device. Descriptive complexity theory shows that many complexity classes have purely logical characterisations too.
Finite Automata are Hiding in Places you Never Imagined.  (Hat-tip to Martin Berger's comment on the connection to coding theory) The 2011 Nobel Prize in Chemistry was given to the discovery of quasi-crystals. The mathematics behind quasi-crystals is connected to aperiodic tilings. One specific aperiodic tiling of the plane is called the Cartwheel Tiling, which consists of a kite shape and a bow-tie shape. You can encode these shapes in terms of 0s and 1s and then study properties of these sequences, which code sequences of patterns. In fact, if you map 0 to 01 and 1 to 0, and repeatedly apply this map to the digit 0, you will get, 0, 01, 010, 01001, etc. Observe that the lengths of these strings follow the Fibonacci sequence. Words generated in this manner are called Fibonacci words. Certain shape sequences observed in Penrose tilings can be coded as Fibonacci words. Such words have been studied from an automat-theoretic perspective, and guess what, some families of words are accepted by finite automata, and even provide examples of worst-case behaviour for standard algorithms such as Hopcroft's minimization algorithm. Please tell me you are dizzy.

I could go on.(And on.)* I find it useful to have automata in the back of my head and recall them every now and then to understand a new concept or to gain intuition about high-level mathematical ideas. I doubt that everything I mention above can be communicated in the first few lectures of a course, or even in a first course. These are long-term rewards based on an initial investment made in the initial lectures of an automata theory course.

To address your title: I don't always seek enlightenment, but when I do, I prefer finite automata. Stay thirsty, my friend.


Monotone arithmetic circuit complexity of elementary symmetric polynomials? The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables.
I am interested in the monotone arithmetic $(+,\times)$ circuit complexity
of this polynomial. A simple dynamic programming algorithm (as well as Fig. 1 below) gives a $(+,\times)$ circuit with $O(kn)$ gates.

 Question:
Is a lower bound of $\Omega(kn)$  known?

A $(+,\times)$ circuit is skew if at least one of the two inputs of each product
gate is a variable. Such a circuit is actually  the same as switching-and-rectifying network (a directed acyclic graph with some edges labeled by variables; each s-t path gives the product of its labels, and the output is the sum of over all s-t paths). Already 40 years ago, Markov proved a surprisingly tight result: a minimal
monotone arithmetic skew circuit for $S_k^n$ has exactly $k(n-k+1)$ product gates. The upper bound follows from Fig. 1:

 But I haven't seen any attempt to prove such a lower bound for non-skew circuits. Is this just our "arrogance", or are there some inherent difficulties observed along the way?

P.S. I know that $\Omega(n\log n)$ gates are necessary to simultaneously compute all $S_1^n,\ldots,S_n^n$. This follows from the lower bound on the size of monotone boolean circuits sorting the 0-1 input; see page 158 of Ingo Wegener's book. The AKS sorting network also implies that $O(n\log n)$ gates are sufficient in this (boolean) case. Actually, Baur and Strassen have proved a tight bound $\Theta(n\log n)$ on the size of non-monotone arithmetic circuit for $S_{n/2}^n$. But what about monotone arithmetic circuits?

One challenge is that if you remove the "monotone" restriction, we do know how to compute such things efficiently.  You can compute the value of all $S_0^n,\dots,S_n^n$ (evaluate all $n+1$ elementary symmetric polynomials) in $O(n \log^2 n)$ time, using FFT-based polynomial multiplication.  So, proving a $\Omega(nk)$ lower bound in the monotone circuit model would require proving a $\Omega(n^2)$ lower bound on polynomial multiplication.

Here's how.  Introduce a formal unknown $y$, and consider the polynomial

$$P(y) = \prod_{i=1}^n (1 + x_i y).$$

Note that since the $x_i$'s are known constants, this is a univariate polynomial with unknown $y$ and with degree $n$.  Now you can note that the coefficient of $y^k$ in $P(y)$ is exactly $S_k^n$, so to evaluate all the $S_0^n,\dots,S_n^n$, it suffices to compute $P(y)$.

This makes it possible to compute $P(y)$ in $O(n \lg^2 n)$ time: build a balanced binary tree of polynomials with the $(1+x_i y)$'s at the leaves, and multiply the polynomials.  Multiplying two polynomials of degree $d$ takes $O(d \lg d)$ time using FFT techniques, so we get the recurrence $T(n) = 2 T(n/2) + O(n \lg n)$, which solves to $T(n) = O(n \lg^2 n)$.  For convenience, I am ignoring $\text{poly}(\lg \lg n)$ factors.

If you care about the case where $k$ is very small, you can compute $S_0^n,\dots,S_k^n$ in $O(n \lg^2 k)$ time using similar tricks, keeping in mind that you only care about $P(x) \bmod y^{k+1}$ (i.e., throwing away all terms of $y^{k+1}$ or higher powers of $y$).

Of course, the FFT uses subtraction, so naively it's not expressible in a monotone circuit.  I don't know whether there's some other way to multiply polynomials efficiently with monotone arithmetic circuits, but any efficient monotone method for polynomial multiplication immediately leads to an algorithm for your problem as well.  So, lower bounds on your problem require/imply lower bounds for polynomial multiplication.


The complexity of recognizing optimal set systems for the V-C dimension The Vapnik-Chervonenkis dimension of a set system $(X,\mathcal S)$ with ground set $X$ is the maximum size of a set $X'\subseteq X$ such that for each subset $X'_i\subseteq X'$, there is a set $S_i\in\mathcal S$ with $S_i\cap X'=X'_i$.

The following decision problem is then natural:

  VC DIMENSION
  Input: a set system $(X,\mathcal S)$ and an integer $k$.
  Task: decide whether the VC dimension of $(X,\mathcal S)$ is at least $k$.

Since there are $2^{|X'|}$ subsets of $X'$, we have $|X'|\leq\log_2(|\mathcal S|)$, and hence VC DIMENSION can be solved in time $O\binom{|X|}{\log_2(|\mathcal S|)}$. For the hardness side, VC DIMENSION is LOGNP-hard (see here). However, I wonder whether something is known for the following specific case:

  My question: what is the complexity of deciding whether a given set system $(X,\mathcal S)$ has VC dimension exactly $\log_2(|\mathcal S|)$?

This doesn't answer the question, but it might be helpful.  Mossel and Umans have made a detailed study of the complexity of approximating VC-dimension, when the set system is succinctly presented:

On the Complexity of Approximating the VC Dimension
http://users.cms.caltech.edu/~umans/papers/MU01-final.ps


Landscape of interactive proof systems My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively enumerable functions classic (among others). Specifically,is an interactive proof system characterisation known for recursive and recursively enumerable functions?

I only know that IP = PSPACE and that MIP = NEXPTIME. By `know'  means I understand the definitions of objects on both sides of the equality and possibly understand the equality.

My second question is whether there is a graphical summary of different types of interactive proof systems and the complexity classes they characterise.

Specifically, I would like a reference to a figure similar to Immerman's picture of description complexity characterisations.

NP is ofter characterized as a proof system in which the prover sends a polynomial-length proof to a deterministic polynomial-time verifier, and after which there is no interaction. The class of recursively enumerable languages can be characterized similarly by replacing "polynomial" with "finite".

Also, since the class of recursive languages R is the intersection of RE and coRE, you can characterize R as a proof system in which an all-mighty prover can convince a finite time verifier both in the validity of correct claims and in the invalidity of false claims.

The class EXP has a characterization in terms of a proof system with "competing provers" - i.e., a proof system in which there is a prover that tries to convince the verifier that the claim is true and a refuter that tries to convince the verifier that the claim is false. See the paper "Making games short" of Feige and Kilian for more details.


Entropy inequality of joint von Neumann entropy given some marginal inequalities Assume that I have a pure, multipartite state $\omega_{ABCD}$ and a unitary $U(\omega_{ABCD})=\tau_{ABCD}$. The effect of $U$ on $\omega$ results in
$$
S(\omega_B)<S(\tau_B)
$$
and
$$
S(\omega_A)>S(\tau_A).
$$
$S$ is the von Neumann entropy and the states $\omega_A,\tau_A$ etc are the marginal density matrices (for instance, $\omega_A$= $Tr_{BCD}{\omega_{ABCD}}$). This effect of $U$ is an assumption, I don't say it always holds.

QUESTION:
Comparing the joint entropies $S(\omega_{AB})$ and $S(\tau_{AB})$, is this true
$$
S(\tau_{AB})-S(\omega_{AB})\leq S(\tau_{B})-S(\omega_{B})
$$
and if yes, why?

EDIT: Another assumption is that $S(\omega_{AB})\geq S(\omega_B)$.

Why should this be true?

Let the dimensions of $A, B, C, D$ all be the same.

Let $\omega_{AB}$ and $\omega_{CD}$ both be pure states, with
$$S(\omega_A) = S(\omega_B) = S(\omega_C) = S(\omega_D).$$

Now, let $U$ perform a cyclic permutation on $A, B, C, D$.

We have $S(\tau_{AB}) = 2 S(\tau_B)$, and  $S(\omega_{AB}) = 0$, while
$S(\tau_B) = S(\omega_B)$.

Now all you have to do is show that you can perturb this construction slightly to get the desired inequalities in your hypothesis.


Is there any good literature on the computational complexity of function problems? There are some cstheory questions that touches function-problems. Like this:
Complexity class corresponding to sorting

So here is the question: Is there good literature about the computational complexity of functions problems? Especially, but not limited to that, about functions-problems with polynomial space bound.

There is an article from Alan Selman: A taxonomy of complexity classes of functions

Please note, that i found this reference in an Answer (by Joshua Grochow) for this Question:

Complexity class when reducing decision problem to function problem

Note also the Comments from Kaveh:

  If you have a function you can look at the bit graph of the function which is a decision problem. If you can compute the function you can compute the bit graph easily from it. If you can compute the bit graph you can compute the function by simple computing the bits of the output one by one.

if i found more, i will add it here.


Good practices for writing algorithms This is about how effectively we can express an algorithm at hand. I need this for my undergraduate teaching.

I understand there is no such thing as standard way of writing a pseudo code. Different authors follow different conventions.

It would be helpful if people here point out, the way they follow and think the best one.

Is there any book that deals with this in a good detail?

Writing pseudocode is like writing code:  It's not particularly important which standard you follow, as long as you (and the people you write with) actually follow some standard.

But for the record, here's the idiosyncratic standard I use in my lecture notes, research papers, and upcoming book.

Use standard imperative syntax for control flow and memory access — if, while, for, return, array[index], function(arguments).  Spell out "else if".

But use $field(record)$ instead of record.field or record->field

Use standard mathematical notation for math — Write $xy$ instead of x*y, $a\bmod b$ instead of a%b, $s\le t$ instead of s <= t, $\lnot p$ instead of !p, $\sqrt{x}$ instead of sqrt(x), $\pi$ instead of PI, $\infty$ instead of MAX_INT, etc.

But use $x\gets y$ for assignment, to avoid the == problem.
But avoid notation (and pseudocode!) entirely if English is clearer.

Symmetrically, avoid English if notation is clearer!

Minimize syntactic sugar — Indicate block structure by consistent indentation (à la Python).  Omit sugary keywords like "begin/end" or "do/od" or "fi".  Omit line numbers.  Do not emphasize keywords like "for" or "while" or "if" by setting them in a different typeface or style.  Ever.  Just don't.

But typeset algorithm names and constants in \textsc{Small Caps}, variable names in italic, and literal strings in sans serif.
But add a small amount of vertical "breathing" space (\\[0.5ex]) between meaningful code chunks.

Don't specify unimportant details.  If it doesn't matter what order you visit the vertices, just say "for all vertices".

For example, here is a recursive formulation of Borůvka's minimum spanning tree algorithm.  I've previously defined $G / L$ as the graph obtained from $G$ by contracting all edges in the set $L$, and Flatten as a subroutine that removes loops and parallel edges.

I use my own lightweight algorithm LaTeX environment to typeset pseudocode.  (It's just a tabbing environment inside an \fbox.)  Here's my source code for Borůvka's algorithm:

\begin{algorithm}
 \textul{$\textsc{Borůvka}(G)$:}\+
\\ if $G$ has no edges\+
\\  return $\varnothing$\-
\\[0.5ex]
 $L \gets \varnothing$
\\ for each vertex $v$ of $G$\+
\\  add the lightest edge incident to $v$ to $L$\-
\\[0.5ex]
 return $L \cup \textsc{Borůvka}(\textsc{Flatten}(G / L))$
\end{algorithm}


Is there a standard definition of Quantum Randomness? I hope this question is not too vague.

For classical bit generators there is the classical statistical definition which (informally) states that a source is ideally random if its output $X_1,X_2,\ldots$ is a sequence of uniform i.i.d. bits.

There is also the alternative Kolmogorov Complexity definition in which an individual string's complexity (informally analogous to randomness) is expressed by its compressibility which is defined as the length of the shortest computer program (w.r.t. a Universal Turing Machine) which will generate the string.

Another definition relates the randomness of the string to the computational complexity of predicting it. This is used, e.g., in the Blum-Blum-Shub generator, where it can be shown that its next output bit can be predicted with probability $(1/2 + \varepsilon)$
for some $\varepsilon>0$ if and only if the RSA problem (given 2 randomly chosen n bit primes $p,q$, form their product $N=pq$ and erase $p$ and $q$; how difficult is it to obtain $p$ and $q$ from $N$?) has an efficient solution polynomial in $n.$

I think some quantum randomness generators use photonic processes to generate bits at their output. However, what is the standard (if any) definition of quantum randomness? I don't know much about quantum theory, but if a quantum system is undergoing the normal Hermitian evolution it seems to me that the output obtained from such a system will not be very random.

The randomness used in quantum computing comes from quantum mechanics and is postulated to be an inherent 'randomness' of nature (and one of the problems Einstein, for instance, had with QM). If you take a state like

$|+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$

and measure it in the computational basis, there is absolutely nothing you can do to predict the result (assuming our standard pictures of QM is not horribly wrong). Half the time you will measure $0$ and half the time you will measure $1$. Of course, if you measure in the Hadamard ($|+\rangle$, $|-\rangle$) basis, then your result will always be $+$.

I don't think there is a standard notion of quantum randomness, mostly because how random a state looks depends on your choice of measurement. Once you choose a particular basis to measure in, then you might as well start talking about the classical probabilities associated with the results and then you can do your standard classical tests of randomness.

Usually when someone talks about the 'quantumness' of a state, they try to capture ideas like entanglement.


How do you encode Lamping's abstract algorithm using interaction combinators? Interaction combinators have been proposed as a compile target for the λ-calculus before. That paper implements the full λ-calculus. It is also known that it is possible to optimize interaction-net encodings of the λ-calculus for the subset of λ-terms that is EAL-typeable. That paper implements that subset of the λ-calculus by translating EAL-typeable λ-terms to interaction nets that are arguably more complex than interaction combinators, since they use an infinite alphabet of labels to group duplicators.

I wonder if it is possible to combine both proposals. That is, is there any encoding for the abstract algorithm - that is, λ-terms that are EAL-typeable - as interaction combinators?

I am not aware of any implementation of Lamping's algorithm directly in the interaction combinators.  I do know that the presence of integer labels is a necessary feature of Lamping's algorithm, even for EAL-typable terms, because the labels reflect the nesting of so-called exponential boxes in proof nets, and Lamping's algorithm is essentially the execution of proof nets using the geometry of interaction, as first observed by Gonthier, Abadi and Lévy.  So the question of implementing the algorithm in the interaction combinators boils down to representing exponential boxes in proof nets using the combinators. This is essentially what Mackie and Pinto did in their paper.

Of course, Mackie and Pinto's encoding adresses all $\lambda$-terms, which use full linear logic boxes, whereas EAL-typable terms use elementary linear logic boxes, which are simpler (they are so-called functorial boxes).  However, I do not believe that this simplification would have a notable impact on interaction combinator implementations.  This is because boxes are a global feature (they identify arbitrarily big subnets to be duplicated/erased), whereas the interaction combinators (as any interaction net system) are completely local (reduction only modifies bounded subnets), so the challenge is to represent such global features locally.  Now, global duplication/erasing in EAL is identical as in full linear logic, that is why I do not expect that an interaction combinator implementation of EAL would radically differ from the one proposed by Mackie and Pinto.


Sorting algorithm with a complexity smaller than $n \log n$? If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input.

But if we want to encode input, we can't encode each object of the list into a fixed-size binary representation because hence, we would consider that the domain of the objects is fixed and thus, I think we could find better sorting algorithms by precomputing some stuff in the Turing Machine.

If we consider that the domain isn't fixed, we have to encode each of our items into a $\log(n)$-size representation. Thus the input is of size $N = n\log(n)$. But as our numbers are of variable length, then we can consider that comparison has a cost of $\log(n)$, but even with this, if we apply a reasonable sorting algorithm (ie an $n \log n$ algorithm), the algorithm will take $n \log^2(n)$ time in a Turing machine, where $n$ is the number of objects, but where $n \log n$ is the size of our input. In this case, we have an algorithm of complexity lower than $O(N \log(N))$ where $N$ is the size of the input.

Is there a mistake?

Without looking at any details, why do your say your algorithm beats $O(N\log N)$?

In your notation, $N\log N = n\log n\log(n\log n) = n\log n\log n + n\log n\log\log n = O(n\log^2n)$.

No contradiction.


Layman Interpretation: Quantum Factoring Algorithm I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media.

So, I'm hoping that somebody will be able to help me to correct my understanding of quantum computing.

My understanding is as follows:

a qubit acts as though it is in both states at once (1 and 0)
a register of n qubits can act as though it is in any of $2^n$ states.
this has obvious benefits in terms of a factoring algorithm: we can identify whether any of these states is a 'correct' solution to a problem.
however, I understand that although we can identify whether or not there is a correct state, we can not necessarily observe the state which is correct

So, my assumption up to now has been that we can 'pin' one or more of the qubits by replacing with a classical bit, and observe whether or not the remaining set of states still contain a correct solution. (Simple!)

My problem is that this would seem to lead to a solution to the factoring problem in $O(log n)$ time, by passing down and pinning each of the bits. I haven't proved that out but it feels right, based on my assumptions.

However, Shor's algorithm takes $O((logn)^3)$ and doesn't seem that simple. I'd like to know which of my assumptions are wrong, but Wikipedia's description of Shor's algorithm seems intractable to me.

Can you help identify my misconception? Which of my points of understanding are correct/incorrect?
Thanks!

The problem stems from the fact that your understanding of quantum computing (as outlined in the question) is incorrect. Certainly quantum computers are poorly explained in most popularizations. A quantum computer cannot simply check if a solution exists within a superposition deterministically, let alone in unit time.

The most general representation of the quantum state of $n$ qubits is the $2^n \times 2^n$ density matrix $\rho$, where the diagonal entries correspond to the probability of finding the system in a particular classical state, and the off diagonal entries indicate the phase of the superposition (going to 0 for classical probability distributions).

Any quantum algorithm can be seen as a unitary operation followed by some measurement in the computational basis. Given an initial input state $\rho$, it will evolve to $\rho' = U\rho U^\dagger$. The most general set of measurements that can be performed are called positive operator valued measurements(POVMs), where each measurement outcome $i$ is associated with a positive sei-definite Hermitian operator $P_i$ and the probability of outcome $i$ is given by $p_i = \mbox{Tr}(P_i \rho)$ (and hence $\sum_i P_i = \mathbb{I}$).

Within these constraints the operations you describe simply are not possible.


P/Poly vs Uniform Complexity Classes It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization.

What is the smallest uniform class C for which one can prove that
C is not contained in P/poly?
Would showing that co-NEXP is not contained in P/poly have some
    other complexity theoretic consequences as in the case NEXP vs P/poly?

Note: I'm aware that $SP_2$ is known not to be contained in $Size[n^k]$ for each fixed constant $k$ (This was also shown for MA with 1 bit of advice). But in this question I'm not interested in results for fixed $k$. I'm really interested in classes which are different from P/Poly, even if these classes are very large.

$\let\mr\mathrm$There are several results in the literature stating that a certain class $C$ satisfies $C\nsubseteq\mr{SIZE}(n^k)$ for any $k$, and usually it is straightforward to pad them to show that any barely superpolynomially expanded version of $C$ is not in $\mr{P/poly}$.

Let me say that $f\colon\mathbb N\to\mathbb N$ is a superpolynomial bound if it is time-constructible, and $f(n)=n^{\omega(1)}$. For example, $n^{\log\log\log\log n}$ is a superpolynomial bound. In fact, an instructive exercise shows that if $g(n)$ is any unbounded monotone computable function, there is a superpolynomial bound $f$ such that $f(n)\le n^{g(n)}$.

First, direct diagonalization shows that $\Sigma_4^P\nsubseteq\mr{SIZE}(n^k)$ for any $k$. The same argument gives:

If $f$ is any superpolynomial bound, then $\Sigma_4\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$.

Proof sketch: For any $n$, let $C_n$ be the lexicographically first circuit of size $2f(n)$ that computes a Boolean function in $n$ variables not computable by a circuit of size $<f(n)$. Then, the language $L$ defined by $x\in L\iff C_{|x|}(x)=1$ works.

A well-known improvement states that $S_2\mr P\nsubseteq\mr{SIZE}(n^k)$ for any $k$. Likewise,

If $f$ is any superpolynomial bound, then $S_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$.

Proof sketch: If not, then in particular $\mr{NP}\subseteq S_2\mr P\subseteq\mr{P/poly}$, hence $\mr{PH}=S_2\mr P$. By a padding argument, $\Sigma_4\text-\mr{TIME}(f(n))\subseteq S_2\text-\mr{TIME}(f(n))\subseteq\mr{P/poly}$, quod non.

Oblivious classes do even better. Taking into account the objection raised by Apoorva Bhagwat, let $\mr{NLin=NTIME}(n)$. Then $\mr{NLin}\cup O_2\mr P\nsubseteq\mr{SIZE}(n^k)$ for any $k$, and the same argument yields:

If $f$ is any superpolynomial bound, then $\mr{NLin}\cup O_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$.

Proof sketch: If $\mr{NLin\subseteq P/poly}$, then by padding, $\mr{NP\subseteq P/poly}$, which implies $\mr{PH}=O_2\mr P$. Then we proceed as before.

There are also results involving MA. The often mentioned result that $\mr{MA\text-EXP\nsubseteq P/poly}$ is an overkill. Santhanam proved
$$\mr{promise\text-MA\cap promise\text-coMA\nsubseteq SIZE}(n^k)$$
for any $k$, and a similar argument gives:

If $f$ is any superpolynomial bound, then
$$\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}.$$

Proof sketch: By Santhanam’s Lemma 11 (which is a sharpened version of the standard fact that $\mr{PSPACE=IP}$ with a PSPACE prover), there is a PSPACE-complete language $L$ and a randomized poly-time oracle TM $M$ such that on input $x$, $M$ only asks oracle queries of length $|x|$; if $x\in L$, then $M^L(x)$ accepts with probability $1$; and if $x\notin L$, then for any oracle $A$, $M^A(x)$ accepts with probability $\le1/2$.

For a suitable monotone polynomial $p$, let $A=(A_{\mr{YES}},A_{\mr{NO}})$ be the promise problem defined by
$$\begin{align}
(x,s)\in A_{\mr{YES}}&\iff\exists\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\land\Pr[M^C(x)\text{ accepts}]=1\bigr),\\
(x,s)\in A_{\rlap{\mr{NO}}\phantom{YES}}&\iff\forall\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\to\Pr[M^C(x)\text{ accepts}]\le1/2\bigr).
\end{align}$$
Let $h(x)$ be a polynomial reduction of $L$ to its complement, and let $B=(B_{\mr{YES}},B_{\mr{NO}})$ be the promise problem
$$\begin{align}
(x,s)\in B_{\mr{YES}}&\iff(x,s)\in A_{\mr{YES}}\land(h(x),s)\in A_{\mr{NO}},\\
(x,s)\in B_{\rlap{\mr{NO}}\phantom{YES}}&\iff(x,s)\in A_{\mr{NO}}\land(h(x),s)\in A_{\mr{YES}}.
\end{align}$$
If $p(n)$ is chosen suitably large,
$$B\in\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n)).$$
So, let us assume for contradiction that $B$ has polynomial-size circuits, say, $B\in\mr{SIZE}(n^k)$. Let $s(n)$ denote the size of the smallest circuit computing $L$ on inputs of length $n$, and put $t(n)=f^{-1}(p(s(n)))$; more precisely,
$$t(n)=\min\{m:p(s(n))\le f(m)\}.$$
Then $x\mapsto(x,1^{t(n)})$ is a reduction of $L$ to $B$, thus $L\in\mr{SIZE}(t(n)^k)$, which means
$$s(n)\le t(n)^k.$$
But since $f$ is superpolynomial, we have $t(n)=s(n)^{o(1)}$. This gives a contradiction for $n$ sufficiently large.

If we prefer a result with a non-promise version of MA, Miltersen, Vinodchandran, and Watanabe proved
$$\mr{MA\text-TIME}(f(n))\cap\mr{coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}$$
for a half-exponential function $f$. We can improve it in two ways: first, it holds for $\tfrac1k$-exponential bounds for any constant $k$, and second, it holds for oblivious classes. Here, a $\tfrac1k$-exponential function is, roughly speaking, a function $f$ such that $\underbrace{f\circ\dots\circ f}_k=\exp$. See the Miltersen–Vinodchandran–Watanabe paper and references therein for the precise definition; it involves a well-behaved family of well-behaved functions $e_\alpha(x)$, $\alpha\in\mathbb R_+$, such that $e_0(x)=x$, $e_1(x)=e^x-1$, and $e_{\alpha+\beta}=e_\alpha\circ e_\beta$. Also, if $f(n)\le e_\alpha(\mr{poly}(n))$ and $g(n)\le e_\beta(\mr{poly}(n))$, then $f(g(n))\le e_{\alpha+\beta}(\mr{poly}(n))$. Then we have:

$\mr{OMA\text-TIME}(e_\alpha)\cap\mr{coOMA\text-TIME}(e_\alpha)\nsubseteq\mr{P/poly}$ for any $\alpha>0$.

Proof sketch: Assume otherwise. Fix an integer $k$ such that $1/k<\alpha$. Let me abbreviate
$$\mr{OcOMT}(f)=\mr{OMA\text-TIME}(\mr{poly}(f(\mr{poly}(n)))\cap\mr{coOMA\text-TIME}(\mr{poly}(f(\mr{poly}(n))).$$
By padding, we have
$$\tag{1}\mr{OcOMT}(e_{\beta+1/k})\subseteq\mr{SIZE}(e_\beta(\mr{poly}(n)))$$
for any $\beta\ge0$. Moreover, using e.g. Santhanam’s Lemma 11 above, we have the implication
$$\tag{2}\mr{PSPACE\subseteq SIZE}(e_\beta(\mr{poly}(n)))\implies\mr{PSPACE\subseteq OcOMT}(e_\beta).$$
Since trivially $\mr{PSPACE\subseteq OcOMT}(e_1)$, a repeated application of (1) and (2) shows $\mr{PSPACE\subseteq SIZE}(e_{(k-1)/k}(\mr{poly}(n)))$, $\mr{PSPACE\subseteq OcOMT}(e_{(k-1)/k})$, $\mr{PSPACE\subseteq SIZE}(e_{(k-2)/k}(\mr{poly}(n)))$, $\mr{PSPACE\subseteq OcOMT}(e_{(k-2)/k})$, and so on. After $k$ steps, we reach
$$\mr{PSPACE\subseteq P/poly}\qquad\text{and}\qquad\mr{PSPACE=OMA\cap coOMA}.$$
Using padding once more, we get
$$\mr{DSPACE}(e_{1/k})\subseteq\mr{OcOMT}(e_{1/k})\subseteq\mr{P/poly},$$
which contradicts the results above, as $e_{1/k}$ is a superpolynomial bound.


Parametrized Complexity of Counting Bicliques In a previous question Parametrized Algorithm for Finding Bicliques, I inquired if there were fast parametrized algorithms for finding a $k\times k$-biclique in an $n$ vertex graph and learnt that it was open if it is FPT w.r.t. $k$. Is the same true for counting the $k\times k$-bicliques, or is it known that this is #$W\[1\]$-hard w.r.t. $k$ (or some other notion of hardness)?

I know that counting induced $k\times k$-bicliques are #$W\[1\]$-hard, expanding a simple reduction for finding an induced biclique in section 4.5 in Serge Gaspers' thesis.

This should be #W[1]-hard by a standard interpolation argument. Here is a rough sketch.

First, consider the multicolored version of the biclique problem: given a graph whose set of vertices is partitioned into classes $X_1,\dots, X_{2k}$, find a biclique containing exactly one vertex from each set. Unlike Biclique, whose FPT status is open, this multicolored version is known to be W[1]-hard: there is an easy reduction from clique. I believe it should also be #W[1]-hard.

Given a graph $G$ and partition as above, let us obtain a new graph $G'$ by replacing every vertex of $X_i$ with an independent set of size $x_i$ (and replacing each edge between $X_i$ and $X_j$ by an $x_i\times x_j$ biclique). Now the number of $k\times k$ bicliques in $G'$ is a function of the $2k$ variables $x_1,\dots,x_{2k}$. In fact, one can see that this function is a polynomial of degree at most $2k$ and the coefficient of the term $x_1\cdot\dots\cdot x_{2k}$ is exactly the number of multicolored bicliques in $G$. Thus by substituting sufficiently many combination of values into the variables $x_i$ and counting the number of bicliques in $G'$, we can evaluate this polynomial at sufficiently many places to recover its coefficients by interpolation.


Randomized and deterministic query complexity of symmetric functions The deterministic query complexity $D(f)$ of a symmetric function $f$ is $\Omega(n)$ (except for f = 0 or f = 1). I am wondering if the same result holds for the (bounded-error) randomized query complexity? Do we have $R_{1/4}(f) = \Omega(n)$?

I know it's true for some well-known functions (like the OR function), and that it doesn't hold in the quantum setting (for instance, $Q(OR) = \Theta(\sqrt{n})$ by Grover's algorithm). In fact, $D(f) = O(Q(f)^2)$ so we have at least $R_{1/4}(f) = \Omega(\sqrt{n})$.

Ok, I found the answer in this survey: http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf

The sensitivity $s(f)$ of a (nonconstant) symmetric function $f$ is $s(f) \geq \lceil\frac{n+1}{2}\rceil$. However, $D(f) \geq s(f)$ and $R_{1/4}(f) \geq \frac{s(f)}{3}$...

There are other interesting results concerning symmetric functions in this survey (see Section 6.1).


An interesting variant of maximum matching problem Given a graph $G(V,E)$, the classic maximum matching problem is choosing the maximum subset of edges $M$ s.t., for each edge $(u,v) \in M$, $d(u)=d(v)=1$.

Has anybody studied the following variant? For each edge $(u,v) \in M$ , $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$ holds, where c is a constant. We call this constraint a degree-constraint.

The classic constraint is an conjunction on degree with constant 1. The new variant is an disjunction on degree with constant $c$.

The problem on $c=2$ is already $NP-complete$ as shown by Jukka Suomela. I am interested in the potential approximation algorithms. A simple greedy algorithm is selecting maximum star subgraph iteratively until no star subgraph (i.e., no edge(a special star) ) can be selected. But this algorithm performs bad even when $G$ is a tree when $c=3$. There is a inner star whose center has degree $x$, and there are $x$ outer stars each center has degree $x$ and connected to the center of the inner star. The optimum value is $2*x+(x-2)*(x-1)$ by selecting $x-2$ edges from each of $x-2$ outer stars and 2 complete outer stars. The value produced by the greeedy algorithm is $x+1*x$ by selecting the inner star and one edge from every outer star.

The greedy algorithm above is $2\sqrt{n-1}$ approximation, where $n=|V|$. I want to find better approximation algorithm of this algorithm or prove its hardness of approximation.

Furthermore, I want to know the complexity class of this problem in the framework of parameterized complexity. Maybe it bears reasonable fixed parameter algorithm.

Thanks a lot for your comment and answer in advance. :-)

(As it seems that the connection is not completely obvious, I will write an extended version of the above comments as an answer.)

I will focus on the case of $c = 2$. In that case, the problem can be rephrased as follows:

Let $G = (V,E)$ be a graph. The task is to find a maximum-size $M \subseteq E$ such that the following constraint is satisfied: for each $\{u,v\} \in M$, either $u$ is incident to at most $1$ edge in $M$, or $v$ is incident to at most $1$ edge in $M$, or both.

Equivalently:

The subgraph induced by $M$ has to have the property that all neighbours of a non-leaf node (degree > 1) are leaf nodes (degree = 1).

Equivalently:

The subgraph induced by $M$ consists of node-disjoint stars.

In what follows I will interpret unmatched nodes (nodes not incident to any edge in $M$) as stars with 0 edges. Hence a feasible solution partitions the set of nodes into node-disjoint stars.

Now if the number of such stars is $k$, then the number of edges in $M$ is exactly $n-k$: there are $n-k$ leaf nodes that are connected to a star center. Therefore maximising the number of edges in $M$ is equivalent to minimising then number of stars.

Now it is straightforward to see that we have a solution with $k$ such stars iff we have a dominating set of size $k$:

Assume that we are given $k$ such stars. Then we can find a dominating set of size $k$: simply take the centers of the stars (in a star with 1 edge you can pick a node arbitrarily).
Assume that we are given a dominating set $D$ with $|D| = k$. Then we can simply connect each node in $V \setminus D$ to one node in $D$. These edges form a family of $k$ stars.

Therefore solving the problem optimally in a certain graph family $F$ is exactly as hard as finding a minimum dominating set in the same graph family $F$. In particular, the problem is NP-hard even in the case of bipartite graphs.

(However, (in)approximability results related to dominating sets cannot be directly applied here. In essence, we have changed the objective function from $\min |D|$ to $\max n-|D|$.)


Automata as term rewriting systems It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words acceptance is just a particular case of equational reasoning in term rewriting systems.

My question is, has this approach been developed before? In particular, it would be  interesting to see  if Turing machines can be modelled in this language.

Comments

Someone has suggested regular grammars do model deterministic automata. Maybe it is useful to recall the difference between abstract reduction system and term rewriting system. From "Term rewriting and all that":

  A rewrite rule is an identity $l \approx r$ such that l i not a variable and $Var(l) \supseteq Var(r)$. In this case we may write $l \to r$. A term rewriting system is a set of rewrite rules.

It seems that formal gramars fit better the definition of abstract reduction system:

  An abstract reduction system is a pair $(A,\to)$ where the reduction $\to$ is a binary relation on the set $A$, i.e. $\to \subseteq A \times A$.

For the future I note:

Relationship between Turing Machine and Lambda calculus?

As mentioned in the comments, regular grammars are more or less a (string) rewriting system, where the arrow of a derivation is in the reverse direction of the rewriting arrow. Since you seem to be especially interested in term rewriting systems (as opposed to string rewriting systems), the automaton model that you are probably looking for is that of tree automata, that is, finite automata accepting trees instead of strings. I've heard that the following is a very good book on tree automata (although I haven't read through it yet).

H. Comon, M. Dauchet, R. Gilleron, C. Löding
and F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi: "Tree Automata: Techniques and Applications", 2007.

As far as I can tell, the question you asked is quite natural and thus has already been explored. With some googling I found out that Sophie Tison (co-author of the TATA book above) had some invited talks with "term rewriting" and "tree automata" in the title (I haven't read them either).

Tison S. (2011) Tree Automata, (Dis-)Equality Constraints and Term Rewriting. In: Ong L. (eds) Typed Lambda Calculi and Applications. TLCA 2011. Lecture Notes in Computer Science, vol 6690. Springer, Berlin, Heidelberg

Tison S. (2000) Tree Automata and Term Rewrite Systems. In: Bachmair L. (eds) Rewriting Techniques and Applications. RTA 2000. Lecture Notes in Computer Science, vol 1833. Springer, Berlin, Heidelberg


Can $L=SL$ be shown with the replacement product instead of the zig-zag product? (This is a bit of follow-up to https://cstheory.stackexchange.com/posts/comments/93266 but is a distinct enough question I though it should be on its own.)

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

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

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

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

There is a paper already in 2005 that describes how to do this...
See https://people.seas.harvard.edu/~salil/research/derand_squaring-abs.html

I cannot say why people use zig-zag instead, other than perhaps they found the original reference readable enough that they did not need to look at secondary literature. At least for teaching purposes it seems the replacement product is simpler, as the above link shows.


Application of graph theory in computer science I am a CS student. We did graph theory in one course. I found it interesting.

What are the real applications of graph theory in the computer science field?

For example, I found that some concepts in graph theory can be used to design networks. What are other similar applications?

This is in no way a definitive answer, and I do not intend it as such.

Many problems of interest to computer scientists can be phrased as graph problems, and as a result graph theory shows up quite a lot in complexity theory. The computational effort required to determine where two graphs are isomorphic, for example, is currently a topic of much interest in complexity theory (it is neither known to be NP-complete nor contained in P, BPP or BQP, but is clearly in NP). Graph non-isomorphism, on the other hand, has a very nice zero-knowledge proof (another area of study in complexity theory). Many complexity classes have graph problems which are complete for that class (under some reduction).

However it is not just complexity theory that makes use of graph theory. As you can see from some of the other answers, there is quite an array of problems for which the language of graph theory is most appropriate. There are far to many applications to provide a diffinitive list, so instead I will leave you with an example of how graph theory plays a fundamental role in my own area of research.

Measurement-based quantum computation is a model of computation which does not have a counterpart in the classical world. In this model, the computation is driven by making measurements on a special class of quantum states. These states are known as graph states, because each state can be uniquely identified with an undirected graph with a number of vertices equal to the number of qubits in the graph state. This link with graph theory is more than coincidental, however. We know that an important class of measurements (Pauli-basis measurements in case you are interested) map the underlying graph state to a new graph state on one less qubit, and the rules by which this occurs are well understood. Further, properties of the underlying graph family (it's flow and g-flow) determined fully whether it supports universal computation. Lastly, for any graph G' which can be reached from another graph G by an arbitrary sequence of complementing the edges of the neighbourhood of a vertex can be reached by single-qubit operations alone, and so are equally powerful as a resource for computation. This is interesting because the number of edges, maximum of the vertex degrees, etc. can change drastically.


Non constructible functions and anomalous results In the Arora-Barak book, in the definition of time constructible functions, it is said that using functions that are not time constructible can lead to "anomalous results". Does anyone have an example of such an "anomalous result"? I have heard in particular that there might exist functions such that the time hierarchy theorem does not hold, does anyone have an example of such functions? Is there something about this somewhere in the litterature?

Borodin's Gap Theorem: For every total computable function $g(n) \geq n$, there is a total computable function $t$ such that $DTIME[g(t(n))] = DTIME[t(n)]$.

In fact, this holds for any Blum complexity measure in place of $DTIME$.

See also the wikipedia page and references therein.


Decidability/algorithm for checking universality of a quantum gate set Given a finite set of quantum gates $\mathcal{G} = \{G_1, \dots, G_n\}$, is it decidable (in computation theoretic sense) whether $\mathcal{G}$ is a universal gate set? On one hand, "almost all" gate sets are universal, on the other, non-universal gate sets are still not well understood (in particular, of course, it is not known whether every non-universal gate set is classically simulatable), so I imagine giving an explicit algorithm for checking universality could be nontrivial.

For the case of Hamiltonians, rather than gates the answer is trivially yes: you simply enumerate the independent elements of the Lie algebra. Since the Lie algebra is a vector space with the addition of the Lie bracket operator. Since the space is finite, it has a finite basis, and which can easily be checked as to whether it is closed or open under the Lie bracket operation. Simply checking the Lie bracket of all pairs of orthogonal operators can be done in time polynomial in the dimensionality of the space, and a suitable operator basis can be found by the Gram-Schmidt method.

For gates, you don't really have the same option to resort to infinitesimals straight off, and need to construct gates with irrational eigenvalues so that you can arbitrarily well approximate the required infinitesimal generators. I guess that there is a relatively simple way to do this, but it is not immediately obvious to me.

In any case, taking the log of the gates to obtain a set of operators which generate them when exponentiated and checking whether these generated the full Lie algebra would provide a simple necessary but not sufficient criteria for universality.


Number of operations to compute product of pairwise sums over a commutative semiring Let $S$ be a commutative semiring and $T\subset S$, how many semiring operations are required to compute the following
$$\prod_{a,b\in T} a+b$$?
This problem can be solved for commutative rings in $O(n \log n)$ ring operations using multipoint polynomial evaluation from a related problem. However, the algorithm requires there is an inverse to addition.
Actually I'm mostly interested in a similar problem. We have $M = \{A_1,\ldots,A_k\}$ such that $A_i\subset S$. We want to compute
$$\prod_{A\in M} \prod_{A\neq B\in M} \prod_{a\in A,b\in B} a+b$$
with least number of semiring operations.

Not an answer to your exact question, but may be useful if you happen to have a semiring with cancellation: if you have an algorithm which works in any ring, you can apply that algorithm to the difference ring $S-S$ consisting of subtraction pairs $s - t$.  The result will have the form $s - t$ where $s,t \in S$, and the answer will be $d \in S$ s.t. $s = d + t$.  Thus, in addition to semiring operations, you'd need to perform a single cancellation step at the end.


How to analyze a randomized recursive algorithm? Consider the following algorithm, where $c$ is a fixed constant.

void partition(A[1..m], B[1..n])
{
   if m=1 or n=1
      return

   k = random(min(c,m,n));
   partition A into k sublists Asub[1..k] at k-1 distinct random indices
   partition B into k sublists Bsub[1..k] at k-1 distinct random indices

   for i = 1 to k
     for j = 1 to k
        partition(Asub[i], Bsub[j])

   Do something that takes O(n+m) time.
}

What is the expected running time of this algorithm?  The running time appears to be $O(mn)$, but I can't find the proof for this.

If we instead partitioned the input lists into $k$ different parts of equal length, we would have the recurrence $T(n,m) = k^2\,T(n/k,m/k) + O(n+m)$ with base case $T(1,n) = T(m,1) = O(1)$; it is not hard to prove that $T(n,m) = O(mn)$.  But the algorithm partitions the input into a  random number of parts with random sizes.  (As usual, "random" is shorthand for "uniformly at random".)  How does one analyze such an algorithm?

Here is a proof that this algorithm runs in $O(n\,m)$ time in expectation and with high probability.

First consider the algorithm modified so that $k$ is chosen in $\{2,3,..,\min(c,n)\}$ instead of randomly in $\{1,2,...,\min(c,n)\}$.

Lemma 1. For this modified algorithm, regardless of the random choices of the algorithm, the time is always $O(n\,m)$.

Proof.  Fix an input $A[1..n]$ and $B[1..m]$ and fix the random
choices of the algorithm arbitrarily.  In each (possibly recursive)
call to partition(), the two arguments correspond respectively to two
subarrays: a subarray $A[i_1..i_2]$ of $A$ and a subarray
$B[j_1..j_2]$ of $B$.  Identify such a call with the rectangle
$[i_1-1,i_2] \times [j_1-1,j_2]$.  Thus, the top-level call is
$[0,n]\times[0,m]$, and each recursive call corresponds to a
sub-rectangle within this $n\times m$ rectangle.  These rectangles
form a tree, where the rectangle corresponding to one call has as
children the rectangles that correspond to the calls made directly by
that call.  Each parent rectangle is partitioned by its child
rectangles, which form a $k\times k$ grid (of non-uniform rectangles) with $k$ at least 2.  Of course each rectangle's corners have only integer coordinates.

The running time of the algorithm is bounded by a constant times the sum, over the rectangles, of the perimeters of all of these rectangles.  (This is because the time within each call is O(n+m), and the perimiter of the corresponding rectangle is $2(n+m)$.)

I claim that in any set of rectangles as described above, the sum of the perimeters is at most $12 n\,m$.  If true, this proves the lemma.

To prove the claim, observe first that, because $k \ge 2$, for any parent rectangle, the perimeter of the parent is at most 2/3 times the total perimeter of the children. (The perimeter of the parent is $2(n+m)$.  The total perimiter of the children is $(1+k)(n+m)$, and $k >= 2$.)

It follows by a standard charging argument that the total perimiter of all the rectangles is at most $(1 + 2/3 + (2/3)^2 + \ldots ) = 3$ times the perimiter of just the leaf rectangles.  (The observation implies that $P_N \le (2/3) P_T$, where $P_N$ is the total perimeter of the non-leaf rectangles and $P_T$ is the total perimeter of all the rectangles.  This implies $P_T \le 3(P_T-P_N)$, and $P_T-P_N$ is the total perimeter of the leaf rectangles.)

Next, observe that the leaf rectangles partition the original $n\times m$ rectangle.  The maximum possible perimeter of the leaves is obtained when the leaves correspond to the unit squares with integer endpoints, in which case the total perimeter of the leaves is $4\,n\,m$.  Thus, the sum of the perimeters is at most $3\cdot 4\,n\,m$, that is, at most $12 n\,m$.

This proves Lemma 1.

Corollary: The original algorithm runs in $O(n\,m)$ time in expectation.

Proof. If partition chooses $k=1$, it just duplicates the rectangle.  Since $n>1$, the probability that $k=1$ is at most 1/2.  Thus, the expected number of times each rectangle is duplicated is at most 1 (and the expected number of copies of each rectangle is at most 2).  Thus, for the original algorithm, the expected sum of the perimiters of all the rectangles is at most twice that of the modified algorithm, i.e. at most $24 n\,m$.  Just as in the analysis of that algorithm, the running time is proportional to this sum, so is $O(n\,m)$.  QED

Corollary. The bound also holds with high probability (assuming both $n$ and $m$ tend to infinity).

Proof sketch. Fixing every random choice except the number of duplicates of each rectangle, the time is proportional to
$$\sum_{r\in R} (1+X_r) |r|$$
where $R$ is the set of rectangles generated, $X_r$ is the number of times $r$ is duplicated (i.e., times when $k=1$ for that rectangle), and $|r|$ is the perimeter of $r$.

The variables $\{X_r : r \in R\}$ are independent, and each $|r|$ is $O(n+m) = o(n m)$, so by a standard Chernoff bound, the probability that the sum exceeds twice its expectation is $o(1)$.  (More specifically, take $Y_r = (1+X_r) |r|/2(n+m)$, then apply Chernoff to the sum of the $Y_{r}$'s.) QED

As an aside: if the algorithm were to choose $k$ randomly up to $\min(n,m)$ instead of $\min(c,n)$ and then do $O(m n)$ work in each call (instead of $O(m+n)$), the total time would still be $O(mn)$ in expectation.

Proof. First note that the total time would be proportional to the sum of the areas of all the rectangles.  This sum equals the sum, over the integer coordinates $(i,j)$, of the number of rectangles that $(i,j)$ occurs in.  This is $O(nm)$ in expectation because, in expectation, any given $(i,j)$ in the original rectangle occurs in $O(1)$ rectangles.

To see this, suppose $(i,j)$ is contained in a rectangle $r$, and consider the call to partition on $r$.  Let $q(r) = \min(n_r,m_r)$.  Let $r'$ be the rectangle that is the child (containing $(i,j)$) of $r$.  With probability at least $1/3$, $k$ is chosen to be at least $(2/3)q(r)$.  Conditioned on that, $E[q(r')] \le 3/2$, so with constant probability $q(r')$ is at most 1.  If that happens, then $r'$ is a leaf (has no children).  It follows from this that the expected number of rectangles that $(i,j)$ is in is $O(1)$.  QED

(Whether the $O(nm)$ bound would hold with high probability is an interesting question.. I think it would.  Certainly $O(nm\log(nm))$ would hold w.h.p.)


SAT Solution Space - Definition of Cluster of Solutions I'm looking for a formal definition of Cluster of Solutions. My current understanding is the following. Let $x$ be a boolean assignment on $n$ variables. Let $f: \{ 0,1 \} ^n \to \mathbb{N}$ be a function that, given a boolean assignment $x$ on $n$ variables, just returns the natural number $i \in [0, 2^n-1]$ corresponding to $x$. Let $g: \mathbb{N} \to \{ 0,1 \} ^n$ be the inverse of $f$: given a natural number $i$, $g$ returns the corresponding solution (i.e. the binary encoding of $i$ in $n$ bits). Now, a Cluster of Solutions is a set $S$ of solutions such that, for each solution $x \in S$ and for each solution $y \in S$, it's the case that $g(i) \in S$ for each $i \in (f(x), f(y))$. Less formally, a Cluster of Solutions is a set whose solutions are "packed", i.e. "there are no non-solutions among the solutions". Is this definition correct?

I think a cluster of solutions is a maximal set of solutions $T$ s.t. you can reach every $\tau' \in T$ from every other $\tau \in T$ by a sequence of solutions $\{\tau_i\}_{0\leq i\leq n}$ ($\tau = \tau_0$ and $\tau' = \tau_n$) where the hamming distance between each consecutive pair of solutions is bounded, i.e. they are just connected components in the graph where two solutions are adjacent iff the hamming distance between them is less than the bound.

See these notes by Dimitris Achlioptas (or papers on statistical physics and random k-SAT).


Reference for the number of samples needed to distinguish two probability distributions I am looking for a reference (and/or a full proof) for this statement:

  $O(1/\epsilon^2)$ samples suffice to distinguish any two probability
  distributions with variation distance $\epsilon$.

I would be very grateful for any pointers.

So here, you only have two options: either your samples come from $p$, or from $q$ (and you know explicitly both).

By definition of the statistical/total variation distance, we have
$$
d_{TV}(p,q) = \sup_S( p(S)-q(S))
$$
where the supremum is taken over all measurable sets $S$. I haven't looked at the paper, but assuming all is nice (finite), the $\sup$ is a $\max$ and achieved for some particular set $S^\ast$, that you can compute given $p,q$.

So at this point, you have an explicit set $S^\ast$, the values $p(S^\ast)$, $q(S^\ast)$ which by definition satisfy
$$
p(S^\ast) = q(S^\ast) + \varepsilon
$$
and you know that the unknown distribution $h$ is either $p$ or $q$. So to distinguish between the two cases, it suffices to estimate $h(S^\ast)$ up to an additive $\frac{\varepsilon}{2}$, which can be done straightforwardly with $O(1/\varepsilon^2)$ samples.

Side remark: this can be improved a little if both $p(S^\ast), q(S^\ast)$ are both $O(\varepsilon)$ themselves. In which case, distinguishing between the two cases only requires $O(1/\varepsilon)$ samples. (The "hard case" basically is to distinguish $1/2$ from $1/2+\varepsilon$, which requires $\Omega(1/\varepsilon^2)$ samples.)

Second remark: usul refers,in his answer, to a harder problem, composite hypothesis testing. In this problem, you only have one distribution $p$, and want to distinguish between (i) $h=p$ and (ii) $d_{TV}(h,p)>\varepsilon$ (that is, the second option is not a singleton $\{q\}$, but the much larger set of all distributions that are $\varepsilon$-far from $p$). In this case, you need a lot more samples: as a function of the (explicitly known) $p$, this will be basically* $\lVert p^{-\max}_{-\Theta(\varepsilon)}\rVert _{2/3}/\varepsilon^2$ (see [VV14]), where $\lVert p^{-\max}_{-\Theta(\varepsilon)}\rVert _{2/3}$ is a functional of the distribution $p$ (equal to $\Theta(\sqrt{n})$, for instance, when $p$ is the uniform distribution on a set of $n$ elements). See also [BCG16] for an alternative, also tight* characterization of this quantity in terms of another functional.

$*$ The two characterizations are tight in most cases, except some pathological/strange ones.

[VV14]  G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. In Proceedings of FOCS, 2014. [full version]

[BCG16] E. Blais, C. Canonne, and T. Gur. Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)
Manuscript, 2016. [ECCC TR16-168]


Uncertainties in GCT program In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. NP problem".

It seems to indicate that the only currently viable program could face serious obstacles.

What are some of the obstacles where the program could fail?

It depends what you count as "the GCT program."

Consider the specific suggestion (GCT I, GCT II) to use the vanishing/nonvanishing of certain multiplicities in the orbit closures of the determinant and permanent to resolve the strong permanent versus determinant conjecture (i.e., that the permanent is not in the orbit closure of any polynomially larger determinant). In this case, it is possible that even if the conjecture is true, that this is not reflected in the vanishing/nonvanishing of multiplicities of irreps supported on these orbit closures. It is even possible that the conjecture is not reflected in the appropriate inequality of multiplicities. I should note that there are various forms of evidence that this shouldn't happen, but it has not yet been formally ruled out.

Note, however, that if instead of multiplicities you merely want a separating module, then the strong perm v det conjecture is true if and only if there exists a separating module.

If your goal is the original permanent versus determinant conjecture, there is an earlier step in GCT, namely (as pointed out by chazisop) moving to the strong perm v det conjecture by considering the orbit closures. It is conceivable that the original permanent versus determinant conjecture is true but the strong version is false. However, this seems highly unlikely to me. Also, if this is the situation, then none of our current methods can even come close to resolving the perm v det conjecture, since they all currently work for the "strong"/"approximative"/"border-"/Zariski-closed version of whatever algebraic complexity statement they are proving.
If your goal is not perm v det but Boolean $\mathsf{NP} \not\subseteq \mathsf{P/poly}$, there are additional claimed steps in GCT that have yet to be published. It is possible that one of these unpublished steps could fail as well, but obviously it is hard to comment on the details of mathematics one hasn't seen...
[Potential failures of lower bounds in general, not specific to GCT.] GCT is currently aimed at nonuniform lower bounds; that is, even in the GCT approach to Boolean lower bounds, it is aimed at showing $\mathsf{NP} \not\subseteq \mathsf{P/poly}$. But of course, it is consistent with current theorems that $\mathsf{P} \neq \mathsf{NP}$ yet $\mathsf{NP} \subseteq \mathsf{P/poly}$. Of course, it's also technically possible that $\mathsf{P} = \mathsf{NP}$ and the perm v det conjecture is false!

However, let me point out that the GCT program as it currently exists still seems to me like the first thing to try. If it turns out that any one of (1)-(3) above actually doesn't work, it will mean that the perm v det conjecture (and hence, $\mathsf{P}$ versus $\mathsf{NP}$) is almost unimaginably harder than we currently think it is. (It may be worth noting that this statement is coming from someone who already thinks that the following analogy may be roughly correct, if not inadequate: $\mathsf{P} \neq \mathsf{NP}$ is to our current state of knowledge as the Classification of Finite Simple Groups is to Fermat's Little Theorem). And even if that is the case, understanding the exact way in which the failure occurs will likely be important to making further progress.


Preserving termination when rewriting recursive programs Powerful program transformations like partial evaluation, deforestation and supercompilation are based on applying three kinds of transformations:

Rewrite using axioms, e.g. a+b = b+a.
Unfolding/inlining: replace a function call with the body of the function.
Folding/un-inlining: replace a subexpression that matches the body of a function with a call to the function.

Each of these transformations will not change the result of a computation if it still terminates, but rule #3 may introduce non-termination. Here is a simple example of this. We have this program:

f(x) = x+1

We apply transformation #3 to the expression (x+1) and replace it with an equivalent function call:

f(x) = f(x)

Now the program doesn't terminate any more (infinite recursion). Rule #3 is however essential for powerful program transformations (see example below).

Transformations like deforestation and supercompilation ensure that termination behavior is not changed as a side effect of how these algorithms work. However, whether or not a sequence of transformations preserves the termination behavior is a property of the sequence itself, independent of any algorithm that generated it. My question is: how can we limit the application of the rules in such a way that a terminating program is never turned into a non-terminating program, but is still sufficiently general to allow useful program transformations, like deforestation and supercompilation (and hopefully, more)?

Algorithms like deforestation and supercompilation intertwine in their execution the search for good program transformations with ensuring that they preserve termination. I'm looking for a way to separate that into two problems: (1) characterizing a class of transformations that preserve termination (2) the search for good transformations in that class.

Here is an example. Suppose we have an append function in a language like Haskell:

app xs ys = case xs of
            [] -> ys
            x:xs' -> x:(app xs' ys)

And we have a function that appends three lists:

app3 a b c = app (app a b) c

The problem with this is that the outer app copies the (app a b), so the newly constructed list immediately becomes garbage. We can avoid this with a transformation:

Step 1. Unfold the inner app:

 app3 a b c = app (case a of
                  [] -> b
                  x:a' -> x:(app a' b)) c

Step 2. Apply an axiom that distributes a function over a case expression:

app3 a b c = case a of
             [] -> app b c
             x:a' -> app (x:(app a' b)) c

Step 3. Unfold the outer app:

app3 a b c = case a of
             [] -> app b c
             x:a' -> case x:(app a' b)
                     [] -> c
                     x:d -> x:(app d c)

Step 4. Apply axiom to eliminate dead case alternative:

app3 a b c = case a of
             [] -> app b c
             x:a' -> x:(app (app a' b) c)

Note that this is the step where the needless allocation is eliminated! We eliminate the pair x:(app a' b), because it then is immediately destructured again.

Step 5. Fold the expression app (app a' b) c:

app3 a b c = case a of
             [] -> app b c
             x:a' -> x:(app3 a' b c)

This function is equivalent to the original one, but more efficient because it does not construct an intermediate list. Note that the after step 4, only a single node allocation is eliminated. By folding in step 5, we generalize that to eliminating the allocation of the entire list (supercompilation can do this transformation automatically).

The standard presentation of program transformation ideas is unsound, quite unfortunately.  They usually think of program transformation as forward deduction.  Using equational reasoning, you can deduce new facts from the old program, and lo and behold, it gives a better program!  While the new facts are quite clearly facts, nothing guarantees that they constitute a program.  The problem you have spotted is this naive presentation of the program transformation ideas.

However, it is possible to think of very much the same process as a backward deduction.  We think of the old program as a specification, and derive a new program that satisfies the specification.  Since equational reasoning is often bidirectional, you would see very similar steps in deriving the new program.  However, the meaning of these steps is opposite to what the naive methods imply.  When you use this "correct" method, you reason about termination while introducing recursion, and always derive a correct program.

For a paper describing the technique, see Deductive and inductive synthesis of equational programs (PDF).  This was done for first-order "equational" programs, but very similar ideas should be applicable to terminating functional programs.  If you are interested in non-terminating programs, I think you could use coinduction techniques (an off-the-cuff intuition).  However, my efforts to apply domain theory techniques to do these kinds of transformations did not bear fruit.  It might still be possible, but I haven't seen anything written on it.


Optimal upper bound on the number of non-isomorphic graphs with certain parameter What are the optimal (or best known) bounds (preferably exact or else asymptotic but not expectation on random graphs) on the number of  non-isomorphic (unlabelled) simple (no self-loop), undirected graphs with the following parameters/conditions:

a) connected, $|V| = m, \ |E| = n$,
b) (a) AND spectrum of adjacency matrices is same,
c) (a) AND same degree distribution
d) (c) and (b) (i.e. all of the above)

My interest is in finding lower bounds on the resource (time steps, variables required etc, enegy.) for solving graph isomorphism problem. I am aware of one such work by Cai, Furer and Immerman. Any other references aiming at or helpful in understanding the optimal resources (in any form) required for solving graph isomorphism problem will be greatly appreciated.

This is just a partial answer mainly answering just $a)$ and $b)$

The number of non-isomorphic graphs is asymptotically equivalent to $$\frac{2^{n \choose 2}}{n!}$$ Almost all graphs are connected (in fact $k$-connected for any constant $k$) hence this answer your first question.
This is an open problem. If we restrict ourselves to trees then it is well known that almost all trees are cospectral hence that for every tree $T$ there exist another non-isomorphic tree $T'$ with equal adjacency spectrum. I believe there is no other result generalizing this one.  There is plenty of literature on this subject, check on Google for "cospectral graphs".

It is conjectured that almost all graphs are determined by their spectrum but no real evidence for this fact is known. The conjecture is of course motivated by the isomorphism problem.

The number (and proportion) of cospectral graphs on $n=12$ vertices has been computed recently and can be found here.


What is contextual equivalence ignoring non-termination called? Contextual equivalence ($M_1 \cong_{ctx} M_2$) is often defined as:
$C[M_1] \Downarrow V \iff C[M_2] \Downarrow V$

Which is to say for any context $C$, $C[M_1]$ terminates with value $V$ iff $C[M_2]$ terminates with value $V$.

Is there a name for the weaker equivalence: $C[M_1] \Downarrow V_1 \wedge C[M_2] \Downarrow V_2 \Rightarrow V_1 = V_2$?

Which is to say $C[M_1]$ and $C[M_2]$ reduce to equal values iff they both terminate.

(This is an extended comment).

I may be misreading your definitions, but it seems to me that the relation you introduce, let us call it $\simeq$, is not an equivalence relation because it is not transitive.

If $V_1,V_2$ are two distinct closed normal forms (values), then obviously $V_1\not\simeq V_2$.

On the other hand, the genericity lemma (Proposition 14.3.24 in Barendregt's $\lambda$-calculus book) says that given an unsolvable term, say $\Omega$, for any context $C$, either $C[\Omega]\!\Uparrow$ or $C[M]$ has the same normal form (a value, if we assume to work with closed terms) for every term $M$ (including $\Omega$). This shows in particular that $\Omega\simeq V_1$ and $\Omega\simeq V_2$, hence the failure of transitivity.


Does assigning missing literals after unit propagation keep a Boolean formula satisfiable? Let's denote $F$ a Boolean formula (in CNF if you wish) and $F_{a}$ the same formula where literal $a$ was assigned and propagated (using unit propagation).

If $F_{a} \rightarrow b$ (b is propagated from a) and $F_{\neg a} \rightarrow b$ then I can imply $b$ ($\neg a \rightarrow b \land a \rightarrow b \Rightarrow b $). In other words, any satisfying assignment for $F$ must have $b$.

If $F_{a} \rightarrow b$ and $F_{\neg a}$ is independent of $b$, is there always a satisfying assignment for $F$ that has $b$ when $F$ can be satisfied?

If "independent" means "not inferred by unit propagation", then the answer is "no". Eg.
$$
\lnot a \lor b, x\lor \lnot b,\lnot x\lor \lnot b
$$.


Is { ww' | HamDist(w,w')>1 } context-free? After reading the recent question "Is the complement of $\{ www \mid ...\}$ context-free?"; I remembered a similar problem I wasn't able to disprove:

  Is $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \}$ context free?

Here we require that the two strings differ in at least two positions (the Hamming distance must be greater than $1$).

It is context-free if we require that $HamDist(w,w')\geq 1$ (i.e. the two strings must simply be different).

I suspect that the language is not context-free: if we intersect it with the regular  $0^*10^*10^*10^*$ we get cases in which a PDA should "remember" two positions in reverse order after reaching the half of the string.

Update: if we intersect $L$ with the regular $R = \{  0^*10^*10^*10^* \}$ we get a context-free language as showed by domotorp in his answer; a slightly more complex $L \cap R' $ with  $R' = \{  0^*10^*10^*10^*10^*10^* \}$ (one more $1$ to "keep track" of) still suggest that $L$ should not be context-free.

The intersection with $R=\{0^*10^*10^*10^*\mid$ even length words$\}$ is context-free, because a PDA can remember two positions, in a way. Anyhow, let's first see what this language $L$ is. Its complement is
$R\setminus L=\{0^a10^b10^c10^d\mid b=n/2 \vee c=n/2 \vee a+d=n/2\}$. Therefore,
$L=\{0^a10^b10^c10^d\mid b\ne n/2 \wedge  c\ne n/2 \wedge a+d\ne n/2\}$. We can rewrite this as
$L=\{0^a10^b10^c10^d\mid b> n/2 \vee  c> n/2 \vee a+d> n/2 \vee b,c,a+d<n/2\}$.

The first $3$ cases can be easily verified, and so can the fourth one.

$b>n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach the second 1. From then on pop the stack.

$c>n/2$: Same.

$a+d>n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach the third 1. From then on pop the stack.

$b,c,a+d<n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach $a+n/2$ (guessed non-deterministically, somewhere between second and third 1). From then on pop the stack.


Given a graph, decide if its edge connectivity is at least n/2 or not Chapter 1 of the book The Probabilistic Method, by Alon and Spencer mentions the following problem:

Given a graph $G$, decide if its edge connectivity is at least $n/2$ or not.

The author mentions the existence of a $O(n^3)$ algorithm by Matula and improves it to $O(n^{8/3}\log n)$.

My question is, what's the best known running time for this problem?

Let me describe the improved algorithm.

First, decide if $G$ has its minimum degree at least $n/2$ or not. If not, then the edge connectivity is clearly less than $n/2$.

Next, if that is not the case, then compute a dominating set $U$ of $G$ of size $O(\log n)$. This can be done in time $O(n^2)$, by an algorithm described in the previous section of the book.

Next, it uses the following not very difficult to prove fact:

If the minimum degree is $\delta$, then for any edge cut of size at most $\delta$ that divides $V$ into $V_1$ and $V_2$, any dominating set of $G$ must have its vertices in both $V_1$ and $V_2$.

Now consider the dominating set $U = \{u_1, \ldots , u_k\}$. Since $G$ has minimum degree $n/2$, any edge cut of size less than $n/2$ must also separate $U$. Thus for each $i\in \{2, k\}$, we find the size of the smallest edge cut that separates $u_1$ and $u_i$. Each of these things can be done in time $O(n^{8/3})$ using a max-flow algorithm. Thus total time taken is $O(n^{8/3}\log n)$.

You can easily check this in linear time, since a graph has edge
connectivity at least $n/2$ if and only if its minimum degree is at
least $n/2$. You already argued for the “only if” part. Consider now a
graph where every vertex has degree at least $n/2$ and a cut that
divides the graph into two vertex sets $X$ and $\bar X$ with $x := |X|
\leq n/2$. A vertex in $X$ can have at most $x - 1$ connections to
other vertices in $X$, and thus must contribute at least $n/2 - (x -
1)$ edges to the cut. Thus, the cut must have size at least $x (n/2 -
x + 1)$. It remains to show that $x (n/2 - x + 1) \geq n/2$, which is
true since $(x - 1)(n/2 - x) \geq 0$.

Strangely enough, the only reference I find to this result is this from a bioinformatics conference. I'd be really curious to see whether it has been proven somewhere else.

Edit: An earlier reference is: Gary Chartrand: A Graph-Theoretic Approach to a Communications Problem, SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.


How to show that ECTL* is more expressive than CTL* $\cup$ Büchi (with an example) I am looking for a preferably simple property that is expressible in ECTL* but not in CTL* and not in Büchi, with a citable reference to the proof.

Details of what I've tried:

I've tried a modification of Wolper's even-property: the property $Eeven$ that holds for every Kripke structure containing a path where p holds at least in every even state. The ECTL* formula $E (\mathcal{A}_{even}(p))$ specifies $Eeven$ (with $\mathcal{A}_{even}$ being the Büchi automaton that accepts words where p holds at least in every even state).

Because of the existential path quantifier, $E (\mathcal{A}_{even}(p))$ is trivially not expressible in Büchi.

But is there a short proof that $E (\mathcal{A}_{even}(p))$ is not in CTL*? Or a reference to a proof (of any length)?
After looking at Computation Tree Logic and Regular $\omega$-Languages, Wolfgang Thomas, 1989, I can think of a proof showing $Eeven$ is counting - but that would definitely not be a short proof :( Would using $Eeven$ is not star-free or $M(Eeven)$ is not group-free be any easier?

I think the simpler example is your property, which can be written for instance $E(((a+b)a)^\omega))$.
A simple way to show that is is not in CTL* is to show that this would imply that the word language $((a+b)a)^\omega$ is in LTL (because CTL* on linear structures is LTL).

This fact is a classical result.
To show it, it suffices (for instance) to use the theorem stating LTL<=>aperiodic $\omega$-semigroup. So we just need to compute the minimal $\omega$-semigroup of this language, and observe that it contains the group $\mathbb{Z}/2\mathbb{Z}$, so it is not aperiodic.


Distributed file storage system - theoretical approaches What are the main theoretical approaches to a distributed file storage system that allows files to be stored across a network of nodes, assuring their availability in case a node randomly loses connection, but without replicating the entire tree in each node (as in git)?

A simple approach to achieve reliability and fast lookup in a "well connected" network $G$ is to replicate each file $f$ on a set $V_f$ of $\Theta(\sqrt{n}\log n)$ nodes and use random walks to efficiently find members of $V_f$.

When searching for a file $f$, we start $c\sqrt{n}\in \Theta(\sqrt{n})$ random walks of length $\tau$ from some particular node, where $\tau$ is the mixing time of a random walk on $G$. That is, after taking $\tau$ steps, a random walk has probability in $[1/2n,3/2n]$ of being at any particular node in $G$.
Even if some $\epsilon\sqrt{n}\log n$ (for some small $\epsilon>0$) nodes have failed, the probability that at least one of these random walks encounters a node in $V_f$ is at least $$1-\left(1-\frac{\log n}{2\sqrt{n}}\right)^{c\sqrt{n}} \approx 1-\frac{1}{n^{c'}},$$
where $c'$ is a constant $>2$. Of course, this approach only makes sense if $\tau$ is sufficiently small - that's what I meant above when saying "well connected" network. This is the case in networks with sufficiently large (i.e. constant) spectral gap since $\tau \in O(\log n)$. A similar approach is taken in [1].

After some time, most of the $\Theta(\sqrt{n}\log n)$ could have been removed. Thus it is necessary to estimate the current size of $V_f$ periodically and replenish the removed members of $V_f$ by replicating $f$ on new nodes.

[1] Ruggero, Bhattacharjee, Srinivasan, Marsh.
 Efficient lookup on unstructured topologies.


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

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

If you have notions of linear logic, you might want to have a look at the article Soft Linear Logic and Polynomial Time [1] that describes a variant of linear logic (some of the deduction rules have been modified) whose formulas are only provable by proof that are polynomial-time algorithm.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1196

Abstract: We present a subsystem of second order Linear Logic with restricted rules for exponentials so that proofs correspond to polynomial time algorithms, and vice-versa.


Counting avoiding improper 3-colorings Given a graph $G=(V,E)$, what I call an improper $3$-coloring of $G$ is simply a function $c:V \to \{1,2,3\}$. I say that $c$ is $1$-$2$-avoiding when
there do not exist two adjacent nodes $u,v$ with $c(u)=1$ and $c(v)=2$. I am interested in the problem that takes as input a graph and counts the number of $1$-$2$-avoiding improper $3$-colorings of $G$. Or equivalently, this is the number of pairs of disjoint node subsets $(S,S')$ that are not adjacent (in the sense that $E \cap (S\times S') = \emptyset$).

Question: has this problem already been studied? It is obviously in the complexity class #P, but is it also #P-hard?

I don't know whether this problem has been studied but I think its #P-hardness should follow directly from the #CSP dichotomy established by Bulatov (Bulatov JACM'13), later  simplified by Dyer and Richerby (Dyer and Richerby SICOMP'13). In particular, your problem is equivalent to a CSP with a constraint language on the domain D := {1,2,3} with a single binary relation R in the language defined by R := D^2 \ {(1,2),(2,1)}; i.e., all tuples but (1,2) and (2,1) are allowed. A necessary (but not sufficient) condition for tractability is admitting a Mal'tsev polymorphism, which is a ternary operation f:D^3 -> D satisfying, for all a,b in D, f(a,b,b)=f(b,b,a)=a and preserving membership in R. If you take tuples (1,3), (3,3), and (3,2), they all belong to R but any Mal'tsev polymorphism would have to return (1,2) as 1=f(1,3,3) and 2=f(3,3,2) [applying f on the columns if viewing the tuples as rows of a 3x2 matrix]. However, (1,2) is not in R, which is a contradiction.

If I remember correctly, the required result (the necessity of a Mal'tserv polymorphism for tractability of #CSP) is probably established already in Bulatov and Dalmau IC'07 but you may find the other two papers also useful.


Various conjectures which is similar to Log Rank conjecture Log rank conjecture is one of the most famous open problems in the area of communication compleixty.

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

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

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

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

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

The log-rank conjecture is equivalent to the following conjecture.

  For any graph $G$ with adjacency matrix $A$ and complement graph $\bar{G}$, the chromatic number of $\bar{G}$ is at most $(\log \mathsf{rank}(A))^{O(1)}$.

This is from Lovasz and Saks's original paper, which has more connections.

Nisan and Wigderson observed that to prove the log-rank conjecture it suffices to show that any $M \in \{0, 1\}^{N \times N}$ has a monochromatic rectangle of size at least $N 2^{-(\log \mathsf{rank} M)^{O(1)}}$.

More intuitively, the hardness in trying to disprove the conjecture comes from the fact that it's difficult to construct a non-trivial example of a binary matrix that has low rank over the reals. The trivial examples are matrices that can be decomposed into a small number of combinatorial rectangles, but we know that such a decomposition implies small communication complexity. So the conjecture asks, are all low rank binary matrices decomposable into a small number of rectangles.


Delaunay tesselations and convex hulls According to Wikipedia the Delaunay tesselation in $d$ dimensions can be viewed as a convex hull problem in $d+1$ dimensions. Given a countable set of points $S\subset \mathbb{R}^d$ and a point $p\in S$, find the largest subset $X\subset S\setminus\{p\}$ with the following properties:

Every point in $X$ is a vertex of the convex hull of $X$.
$p$ is the only point in $S$ that lies in the interior of the convex hull of $X$.

Is there a relationship between the $d$-dimensional Delaunay tesselation and the set of polytopes for each point $p\in S$ as described?

The relationship I remember is that the Delaunay tessalation is the "visual complement" of Voronoi cells.

I just found this paper on Google which has a nice figure as to why finding the convex hull in d+a dimensions is equivalent to finding the Delaunay tessalation:

http://www.cs.mtu.edu/~shene/PUBLICATIONS/2004/Hull2VD.pdf

What's also interesting from a theoretical cs perspective is that the knn problem can be mapped to the Voronoi cell problem, and by extension to the Delaunay tesselation and the convex hull problem. Known algorithms in d-dimensions typically have an exponential dependency on dimension.