What is the difference between non-determinism and randomness? I recently heard this -
"A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for transitions are not known".

I feel as if I get the point but I really don't. Could someone explain this to me (in the context of machines or in general)?

Edit 1:
Just to clarify, the quote was in context of finite automaton, but the question is meaningful for Turing machines too as others have answered.

Also, I hear people say - "... then I choose object x from the set non-deterministically". I used to think they mean - "randomly". Hence the confusion.

It's important to understand that computer scientists use the term "nondeterministic" differently from how it's typically used in other sciences.  A nondeterministic TM is actually deterministic in the physics sense--that is to say, an NTM always produces the same answer on a given input: it either always accepts, or always rejects.  A probabilistic TM will accept or reject an input with a certain probability, so on one run it might accept and on another it might reject.

In more detail:  At each step in the computation performed by an NTM, instead of having a single transition rule, there are multiple rules that can be invoked.  To determine if the NTM accepts or rejects, you look at all possible branches of the computation.  (So if there are, say, exactly 2 transitions to choose from at each step, and each computation branch has a total of N steps, then there will be $2^N$ total brances to consider.)  For a standard NTM, an input is accepted if any of the computation branches accepts.

This last part of the definition can be modified to get other, related types of Turing machines.  If you are interested in problems that have a unique solution, you can have the TM accept if exactly one branch accepts.  If you are interested in majority behavior, you can define the TM to accept if more than half of the branches accept.  And if you randomly (according to some probability distribution) choose one of the possible branches, and accept or reject based on what that branch does, then you've got a probabilistic TM.


Trade off between width and depth of free BDDs for total functions Terminology
A binary decision diagram is a directed acyclic graph with one source (root), and two sinks ($A$ and $B$). Each non-sink nodes is labeled by an integer $i \in \{1,...,n\}$ and has out-degree 2 (one edge labeled '0', the other '1'). Visiting a node with label $i$ corresponds to queering the bit $x_i$ of the input and following the $0$-edge if $x_i = 0$ and the $1$-edge otherwise. When you arrive at a sink, you output its value $A$ or $B$ as the solution to the function represented by the BDD.

The depth of a BDD is the length of the longest path from source to sink.
A slice at depth $k$ is the set of all nodes that are a distance $k$ from the root. The width of a BDD is the size of the largest slice.
The size of a BDD is the total number of nodes.

A BDD is free, if there is no constraints on the labeling of the nodes. This is in contrast to the more commonly studied restriction of Ordered BDD that does not allow you to label a vertex $i \geq j$ if an ancestor is labeled $j$.
Question
Given a total boolean function $f$ is there a trade off between the depth and width (or depth and size) of the BDDs representing it?
Let $D(f)$ be the query complexity of $f$, and let BDD mean BDD representing $f$. Are there cases that every BDD of depth $D(f)$ has a strictly larger width than a BDD of larger depth?

Motivation
This question is a follow up to:
Trade off between time and query complexity
The hope is that by looking at a more rigid model such as BDDs we might be able to build intuition for that question in the interesting case of total functions. For a free BDD the depth corresponds directly to query complexity. The width is usually seen as a measure of space not time, so this question is also a restriction of time-space trade offs. However, the hope is that learning some trade offs between depth and width/size can help build similar things for query-vs-time in the circuit model.
Note that the case of partial functions is not interesting, since the Kothari-Fitzsimons construction from the previous question can be modified to give a separation for BDDs (although not an arbitrary one; at most exponential). The case of the better studied ordered BDDs is also less interesting, because it is easy to show that the depth of an ordered BDD does not correspond to query complexity. You can give examples of total functions where any ordered BDD has exponentially higher depth than the function's query complexity.

There are known functions on $n$ variables where depth $n$ branching programs (as non-oblivious BDDs are usually called) require exponential size.  The book to read is by Wegner.

Stronger lower bounds are given by Ajtai, and there is some newer work, but I'm not sure about which is best to read.


Detecting infeasibility of System of Linear Inequalities Infeasibility of a system of linear inequalities can be detected by using artificial variables and then using an algorithm like the simplex algorithm (or ellipsoid/interior point methods) to find a basic feasible solution. If one cannot be found then the problem is infeasible.

Are there any other methods to detect infeasibility of a the system?

(1) Farkas' Lemma should show the equivalence of the infeasibility problem and LP in strongly polynomial time.

(2) Solving a linear programming problem (as a computational problem) usually means "detect the problem is either infeasible, unbounded, or having an optimal solution, and if the problem has an optimal solution, find one".  In this sense, they are equivalent.


Lower bound on the worst-case unbiased coin flips to sample a distribution? Say that we have a distribution $\mathcal{D}$ such that all probabitilities associated with it are $p$-bit fixed precision numbers, so:
$$
\Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i},\quad k_i\in\{0,1\}
$$
Say that this is a non-trivial $p$-bit distribution if at least one element $k$ truly takes all $p$ bits to represent, meaning $\exists k\in\mathsf{supp}(\mathcal{D})$ such that $k_p = 1$

I'm interested in the number of $\mathsf{Bern}(1/2)$ random variables required to sample a single sample from this in the worst-case.
From some discussions with others we think it's obvious that it's $p$, and that there should be a lower bound. It seems like a rather basic observation though, so I was wondering if I could find it in the literature anywhere so I could cite it.

Edit: To make the question slightly more specific, I have a ~1/2 page information theoretic argument showing this is true (it's really quite trivial), so I'm solely looking for a reference for who to cite regarding this lower bound.

Fix such a distribution, and an element $k$ showing its non-triviality. In particular, $\Pr[X=k]= (2m+1)/2^p$ for some integer $m$.

Suppose by contradiction you have an algorithm A to sample from the distribution given $p-1$ i.i.d. unbiased bits. Such an algorithm is, given the realization of the coins, deterministic: i.e., it is equivalent to a partition of the leaves of the complete binary tree of height $p-1$, each output $x$ corresponding to a different set $S_x$ in the partition.

As such, since all leaves have probability $1/2^{p-1}$, any output $x$ has probability $|S_x|/2^{p-1}$, i.e., of the form $2\ell/2^p$ for some integer $\ell$. That cannot be equal to $(2m+1)/2^p$.


Non-uniform hierarchy theorem for approximating functions It is easy to show (by probabilistic argument) that there exist functions that require circuits of size $O(2^n/n)$. This, in turn, can be used to prove a non-deterministic hierarchy theorem showing (roughly) that if $2^n/n > T(n) \gg t(n)$ then there exist functions that can be computed by circuits of size $T$ but not by circuits of size $t$.

What is known if we are instead interested in approximating functions rather than computing them exactly? This question can be asked in many ways, but for concreteness let us say that $f \in approxSIZE(t)$ if there is a circuit family of size $t$ that (for each input length) computes $f$ correctly 3/4 of the time. What can be said about existence of hard functions here? What kind of hierarchy theorem is known? Does the answer change if we require the circuits to compute $f$ correctly $1-1/n$ of the time?

Note (added after Ryan Williams's answer): In fact, the answer to my first question follows from a simple modification of Shannon's lower bound, since a circuit on $n$ input bits can only $\epsilon$-approximate $\sum_{i=0}^{\epsilon \cdot 2^n} {2^n \choose i} < 2^{H(\epsilon) \cdot 2^n}$ functions, where $H$ denotes the binary entropy function. A hierarchy theorem should follow from this in the usual way.

There are some fairly tight results known for tradeoffs between circuit size and theirapproximation, with which one can prove hierarchy theorems for approximating functions. I would start with the following reference:

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim. Optimal Bounds for the Approximation of Boolean Functions and Some Applications. ECCC, 1995.


Examples of Fat-Shattering Dimension What are some good examples for analysis of a class's Fat-Shattering dimension?

By (Alon et al) I know that the Fat-Shattering Dimension characterizes the learnability of real-valued function classes but I didn't find any proper examples of function class with a proof for a bound on the Fat-Shattering Dimension of the class.

For $L$-Lipschitz functions on a metric space $(X,\rho)$ with $\epsilon$-packing number $M(\epsilon)$, the $\gamma$-shattering dimension is $M(2\gamma/L)$, as proved here:
http://ieeexplore.ieee.org/document/6867374/


Complexity of Unknotting problems The complexity of the Unknotting problem is known to be in $\mathrm{NP} \cap\mathrm{co\text-NP}$, see references:

 The Computational Complexity of Knot Problems.
Knottedness is in NP, modulo GRH. .
Unknotting is in $\mathrm{AM}\cap\mathrm{co\text-AM} $.

Some even believe the problem to be in $P$, but to relax the ptime constraints, due to (maybe) either the cost, or diagram of the knot. It maybe there exists an Arthur-Merlin type protocol for unknottedness. This could lead to possibly interesting applications too. Also, if Unknottedness is $\mathrm{NP}$ -complete then the polynomial hierarchy collapses.
But  by relaxing the ptime constraints to a quasipolynomial one leads one to quasipolynomial time algorithm for Unknotting. Is there any such quasipolynomial time algorithm for Unknotting?
What (if any) would be the implications of such a quasipolynomial algorithm be to other conjectures such as GRH(?), ETH, or even SETH?

Such a quasi-polynomial algorithm has just been claimed by Marc Lackenby from Oxford University. He will present in next Tuesday (02 Feb 2021) in a Zoom talk: https://www.math.ucdavis.edu/research/seminars/?talk_id=6082


Lower bound on the element distinctness problem The element distinctness problem asks whether any two elements of the input
sequence $<x_1,\ldots,x_n>$ are equal? This problem has a lower bound of
$\Omega(n \log n)$ in the algebraic decision tree model when the $x_i$'s are
real numbers. My question is what is the lower bound if we restrict the $x_i$'s
to positive integers?

Such a lower bound for integer inputs is indeed known, and is not just a trivial consequence of the result for the reals:

  A. C.-C. Yao, Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains, SIAM J. Comput., 20(4), 655–668.

Rather, Yao has to re-prove the Milnor-Thom-Oleinik-Petrovski bound on the number of connected components of a semi-algebraic variety over $\mathbb{R}$ more or less from scratch to get it to work over $\mathbb{Q}$, where the notion of connectedness is a bit thornier. He also needs to assume that the problem is scale-invariant and "rationally dispersed" (see the paper), and only counts connected components of nonzero measure. These technical conditions already hint that it is not a simple consequence of the result over the reals.


What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem? A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based on the undecidability of the halting problem - see for example https://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof

Who first proposed this proof and in what article or book has it been first published?

I believe that some version of this connection can be tied back to Turing's seminal paper on computability.

Namely, Turing makes the following two claims:

"The results of Section 8 have some important applications. In particular, they can  be used  to  show that  the  Hilbert Entscheidungsproblem can  have no solution."
"If the negation of what Godel has shown had been proved, i.e. if, for each $U$ either $U$ or $\neg U$ is provable, then  we should have an immediate solution of the Entscheidungsproblem."

The conclusion, I believe, follows from Modus Tollens.


Existence of $d$-regular expander graph that can be represented as a bipartite graph It is easy to derive from the definition of expander graphs that a $n$-vertex expander graph $G$ does not have a $o(n)$-vertex/edge separator. I was wondering if we can build a $d$-regular expander graph that is also a bipartite graph? Thus I have a sparse bipartite graph example that does not have a $o(n)$-vertex/edge separator.

Note that by definition this bipartite graph is not exactly a bipartite expander graph, which only requires that every small subset on the left side of the bipartite graph to have large neighbors on the right.

The obvious thing to try would be to convert a non-bipartite regular expander to a bipartite one using the bipartite double cover, which preserves regularity. But it might not preserve expansion; in particular, if you have only a small number of vertices involved in odd cycles, they would become a bottleneck in the double cover.

But if all you need is constant expansion (rather than stronger properties like, say, being a Ramanujan graph) then converting a non-bipartite graph to a bipartite one while preserving constant expansion is easy: just subdivide each edge to make it bipartite (as Yixin Cao already suggested in comments), and then add enough extra edges to the subdivision vertices to make it regular again.

For the stronger expansion that you get from Ramanujan graphs, see Marcus, Spielman, and Srivastava "Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees", FOCS 2013. Judging from the abstract (I haven't read the paper carefully) they appear to be using the bipartite double cover idea, but with a bit more care to avoid the bottlenecks.


On Defining Probabilistic/Nondeterministic Circuits Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit.

The standard way of defining probabilistic/nondeterministic circuits is to augment the input with inputs. Let's assume that the circuit is still of size $f(n)$. What is $n$ in this case?

 $n$ is the number of deterministic inputs.
 $n$ is the number of deterministic PLUS probabilistic/nondeterministic inputs.

My confusion is that some references consider case 1, while others consider case 2.

I found the following text in [1] (cited below); it shows that---as Ryan pointed out---there must be some function limiting the number of nondeterministic/random inputs; unless it can be judged from other things without ambiguity:

We develop nondeterministic $\mathbf{NC}$ ($\mathbf{NC}$) circuits by uniformly adding guessing gates to families of $\mathbf{LOGSPACE}$-uniform $\mathbf{NC}$ circuits. Let $\mathbf{NNC}(f(n))$ be the class of languages accepted by $\mathbf{LOGSPACE}$-uniform families of $\mathbf{NC}$ circuits with $O(f(n))$ nondeterministic gates or guess gates, where $n$ is the length of the input. We will refer to a circuit from such a family as a uniform $\mathbf{NNC}$ circuit, and such a circuit accepts an input if it outputs a 1. The guessing gates give the circuit a set of guessing inputs, $y$, in addition to the ordinary inputs, $x$. Note that $|x|=n$ and $|y|=f(n)$. An $\mathbf{NNC}$ circuit is said to accept $x$ if and only if there is some string of guessing bits $y$ that causes the circuit to output a 1. Thus, $f(n)$ can be thought of as the maximum number of guess bits used in computations on inputs of length $n$.

[1] Wolf, M. J. 1994. Nondeterministic circuits, space complexity and quasigroups. Theor. Comput. Sci. 125, 2 (Mar. 1994), 295-313. DOI= http://dx.doi.org/10.1016/0304-3975(92)00014-I


NBE for MiniTT: Why is labelled sum eliminator both a normal form and a neutral value? I am studying A simple type-theoretic language: MiniTT, which introduces a dependently typed language with The language contains data types, mutual recursive/inductive definitions and a universe of small types. The type checking proceeds by a mostly-straightforward bidirectional type-checking, coupled with normalization-by-evaluation to compute normal forms. It is here that I am confused. First, some quick syntax:
A sum type is created using Sum(c1 A1, ..., cn An), which contains objects
of the form ci E : Sum(c1 A1, ..., cn An), where E: Ai. For example, booleans are encoded as Sum(true 1, false 1) where 1 is the unit type. The type of naturals is encoded as rec Nat : U = Sum (zero | succ Nat). Sum types are eliminated using case-analysis, written as fun(c1 M1, ..., cn Mn), where each constructor is ci and the associated handler is Mi. For example, the elimination rule for booleans can be encoded as:
Bool : U = Sum (true | false)
elimBool : Π C:Bool → U. C false → C true → Π b:Bool. C b
= λ C.λ h0.λ h1.fun (true → h1 | false → h0)

and the elimination for naturals can be written as:
rec natrec: ΠC : Nat → U. C zero → (Πn:Nat . C n → C (succ n)) → Π n:Nat. C n
= λ C.λ a.λ g. fun (zero → a | succ n1 → g n1 (natrec C a g n1))

Now, I had always assumed that when implementing normalization-by-evaluation (NBE), the normal forms always consist of constructors, while the neutral values consist of eliminators, since an eliminator can get stuck if it does not know enough about its argument, while a constructor can always freely construct.
However, in the paper's implementation of NBE (given in the appendix), it appears that Fun (labelled sum eliminators) are one of the normal forms:
data Val =
Lam Clos
 ...
| Fun SClos -- function is a normal form?!
...
| Nt Neut
deriving Show

Furthermore, the inductive data type of stuck/neutral values has yet another encoding of a stuck fun, called as NtFun:
data Neut = Gen Int
...
| NtFun SClos Neut -- Fun as a stuck term

I have not seen an explanation of NBE which allows one to encode a particular syntactic category (in this case, the labelled sum eliminator fun), as both a normal form and a neutral/stuck term.

What is going on here? Why can a fun be both a normal form and a stuck/neutral term?
How should I think about what my normal forms and stuck terms should be? I had previously imagined that constructors would be normal forms, and eliminators are stuck terms. What's the rule of thumb that's being followed here?

They are different things. SClos is a case-split function, which is a function that pattern match on its parameter. Think of it as a lambda (if you know Haskell, you can think of it as a LambdaCase \case, which is a sugared lambda). This is definitely a canonical value in Mini-TT.
The neutral value, OTOH, is an application on a case-split function, where the argument supplied is neutral. If an instance of a sum type is neutral, you don't know which constructor it belongs to, so you don't know which clause in the pattern matching should be selected, so this is a neutral value.
Summary: pattern matching itself is canonical, while application on pattern matching is not. If this application stucks, it becomes a neutral value.


Heuristics for graph bisection i'm trying to find an algorithm
that will divide my graph in 2 parts by telling me what connections should be broken
but the 2 parts should contain about the same number of nodes

its for a practical problem that i'm implementing. the graph will never have more then 64 nodes.

edit

this will be applied to a 64 nodes graph every time the program runs.
the connections have distances from 0-90, where 90 is far apart

the described algorithm sounds good
is it an existing one? can you get a link to pseudo code?
or should i try implementing it myself ^^

(transferred from a comment above)

The problem you want to solve is called Graph Bisection and is NP-hard. A simple heuristic that might work well in your case is to find two nodes that are as far apart as possible, and then grow out their neighborhoods till you get roughly equal sizes on both. Another local improvement heuristic is to take a candidate solution, and find two vertices to swap that will reduce the cut size.


Obtaining the Axiom of Choice through a modality in HTT In (constructive) homotopy type theory, the law of excluded middle is not derivable. Moreover, assuming parametricity it is refutable.

But, one can work inside the double negation modality to obtain (a form of) the law of excluded middle.

The question now is, can the same be done to obtain the axiom of choice? To be exact, is there a modality M such that the type $\Pi x : A. \|\Sigma y : B. R(x, y)\| \to M \|\Sigma f : A \to B. \Pi x : A. R (x, f(x))\|$ is inhabited?

There is a trivial sense in which the answer is yes.  For any proposition $P$, there's a modality $O_P$ called the open modality determined by $P$, defined by $O_P(X) \equiv (P\to X)$.  If you take $P$ to be the statement of the axiom of choice (relative to some universe), then for $M=O_P$ the type you showed is inhabited, since you get to use the axiom of choice in proving the conclusion.

However, this is not as useful as the double-negation modality for LEM.  To see why, notice that there is an even more trivial sense in which the answer is yes, namely when $M$ is the trivial modality, $M_{\rm triv}(X) \equiv \mathbf{1}$.  Obviously that's not very interesting.  The point is that $M_{\rm triv} = O_{\mathbf{0}}$, and  if we don't know whether $P=\mathbf{0}$ (such as when $P=\rm AC$), then we don't know whether $O_P = M_{\rm triv}$.  (And in fact, in models where $\rm AC$ is refutable, we do have $O_{\rm AC} = M_{\rm triv}$.)  The same argument applies to $P=\rm LEM$, of course; but $O_{\rm LEM}$ is not the same as double-negation, and we can prove that double-negation is always nontrivial (e.g. $\neg\neg \mathbf{0} = \mathbf{0}$).  So this "answer" is not really telling us anything.

As Ingo says, it seems unlikely that we can construct any provably-nontrivial modality with this property.  I don't know how to prove that we can't, but I think I can prove that no such lex modality can be constructed in the absence of univalence.  Take a model of ZF that doesn't satisfy AC.  Then its topos of sets is a model of MLTT with function extensionality, propositional extensionality, propositional truncation, and propositional resizing, in which lex modalities correspond to geometric subtoposes; but it has no proper nontrivial geometric subtoposes.

It should be possible to include Univalence as well, but I'm hazy on the necessary details.  Voevodsky's original simplicial model of HoTT has no nontrivial proper lex modalities, but its construction uses AC.  More recent cubical-type models of HoTT are constructive, but many of them do have nontrivial proper lex modalities.  Possibly the recent "equivariant" cartesian cubical model would work: it exists constructively, and classically is Quillen equivalent to the simplicial model and hence has no nontrivial proper lex modalities; but I'm not quite sure whether the latter equivalence uses AC or only LEM.

Relaxing lexness is going to be trickier, since even the classical simplicial model has lots of nontrivial proper non-lex modalities, like the $n$-truncations for all $n$.  I don't know whether there's any classification of all such modalities, or any other way to verify that none of them make AC true.


Complexity of recognizing vertex-transitive graphs I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.

  Question 1. Let $G$ be a simple undirected graph of order $n$. What is the
  computational complexity (in terms of $n$) of determining if $G$ is
  vertex-transitive?

Recall that a graph $G$ is vertex-transitive if $\mathrm{Aut}(G)$ acts transitively on $V(G).$

I am not sure if the above definition allows for a polynomial time algorithm since it can be that the order of $\mathrm{Aut}(G)$ is exponential.

However vertex-transitive graphs have some other structural properties that might be exploited in order to be able to efficiently determine them so I am not sure what is the status of the above question.

Another interesting subclass of vertex-transitive graphs that has even more structure is the class of Cayley graphs. So it is natural to also pose the following related question

  Question 2. What is the computational complexity of determing if a graph $G$ is a
  Cayley graph?

I don't have a complete answer, but I think both problems are open.

The paper by Jajcay, Malnič, Marušič [3] is related to your first question.
They provide some tools to test vertex-transitivity. They say in the introduction that:

  For a given finite graph $\Gamma$,
  it is decidedly hard to determine whether $\Gamma$ is vertex-transitive,
  and the ultimate answer comes usually only after a substantial part of
  the full automorphism group of $\Gamma$ has been determined.

Note that vertex-transitivity test can be done by testing graph isomorphism $n−1$ times.
Make two copies $G$ and $G'$ of your graph,
with special anchors (like paths of length $n+1$) at $u \in V(G)$ and $v \in V(G')$.
There is an isomorphism between $G$ and $G'$ if and only if
the original graph has an automorphism mapping $u$ to $v$.
Thus you can test vertex-tansitivity by fixing a vertex $x$,
and checking that there are automorphisms mapping $x$ to all the other vertices.

Also note that if vertex-transitivity test can be done in polynomial time,
then so is isomorphism test for vertex-transitive graphs.
This is because two vertex-transitive graphs are isomorphic if and only if
their disjoint union is vertex-transitive.
I believe that complexity of graph isomorphism for vertex-transitive graphs is not known.

For the 2nd question, I found a partial result.
A circulant graph is a Cayley graph on a cyclic group.
Evdokimov and Ponomarenko [2] show that recognition of
circulant graphs can be done in polynomial time.
Also the book chapter by Alspach [1, Chapter 6: Cayley graphs, Section 6.2: Recognition]
would be interesting for you, although it says that:

  We shall ignore the computational problem of recognizing whether an
  arbitrary graph is a Cayley graph. Instead, we always assume that
  Cayley graphs have been described in terms of the groups on which they
  are built, together with the connection sets. For most problems this
  is not a drawback.

Beineke, Wilson, Cameron. Topics in Algebraic Graph Theory. Cambridge University Press, 2004.
Evdokimov, Ponomarenko. Circulant graphs: Recognizing and isomorphism testing in polynomial time. St. Petersburg Math. J. 15 (2004) 813-835. doi:10.1090/S1061-0022-04-00833-7
Jajcay, Malnič, Marušič. On the number of closed walks in vertex-transitive graphs. Discrete Math. 307 (2007) 484-493. doi:10.1016/j.disc.2005.09.039


Security of message authentication codes and tag size The obvious way to attack a MAC is to try every key; therefore, if we use an n-bit key we need $2^n$ steps to break it.

But we can also try every tag in order to find the correct one, and in some concrete scenarios (e.g. CBC-MAC with AES-256) the tag is smaller than the key.

Does this mean that a MAC with n-bit keys and t-bit tags will offer $\min(n,t)$ bits of security, or is there something wrong with this reasoning?

Theoretically, that is correct. Given your approach, the attacker needs to try $2^t/2$ tags on average, while to find the key, he needs to try $2^n/2$ keys on average. In CBC-MAC with AES-256, we have $t=128$. Therefore, the adversary needs to try about $2^{128}/2=2^{127}$ tags to find the correct one. While in this case the brute force needs much less effort than trying to break the key itself (which amounts to $2^{255}$ trial-and-errors), it is still far beyond the  current computing power of supercomputers.

It is worth noting that, we usually take any scheme whose best attack needs at least $2^{80}$ operations as secure. (I read this somewhere, but forgot the reference. Sorry!)


Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory I read the famous book by Alon and Spencer on the probabilistic method in combinatorics.

Is there a survey or lecture notes on recent advances and relationships with the following complexity theoretic topics of this method beyond this textbook?

pseudorandom generators fooling concrete computation models, expander graphs.
complexity lower bounds for concrete computation models such as circuits, branching programs, streaming, property testing, learning, and communication complexity.
randomized complexity theoretic aspects of algebraic coding theory and information theory.
VC-dimension, discrepancy and other geometric topics.

I recommend looking at Stasys Jukna's books Extremal Combinatorics and Boolean Function Complexity. For discrepancy and the like, you can look at Bernard Chazelle's book The Discrepancy Method (available online at his homepage).


Finding divisors of an interval of integers This numerical problem arose in one of my projects. It seems simple at first sight, but I can't seem to find a good approach. Maybe someone else has an idea:

We have two integers, $n$ and $N$. Let's say that $n \approx 10^6$ and $N>10^{18}$.

I need to create a list of all numbers between n and $\sqrt N$ that divide some number in the interval $[N,N+n-1]$.

Obviously, each number can divide at most one, and the total number of answers is approximately $n \ln{\sqrt N  \over n}$; $6.9*10^6$ for $10^{18}$.

The most straightforward approach is to enumerate all integers from $n$ to $\sqrt N$ and to try each one, and that takes $O(\sqrt N)$ operations. Surely we can do much better?

Your problem is more or less equivalent to the problem of factoring $N,N+1,\ldots,N+n$. To get from these factorizations to the solution to your problem, simply enumerate the factors. To get from the solution to your problem to the factorization, simply test each factor for primality. In the future you may wish to state this problem in this other form, as it sounds more natural and fundamental that way.

One way to factor these numbers is to simply use a standard factorization algorithm on each one. Note that most numbers have lots of small divisors and therefore are a lot easier to factor than the products of two large primes that need to be factored to break RSA public key cryptography. According to Wikipedia the Lenstra elliptic curve factorization method works well on numbers with small factors and the Quadratic Sieve works well for numbers under 100 digits. I would give those two factorization algorithms a try.

In light of the above I suggest something along the lines of the following algorithm:

Iterate over all numbers X between $N$ and $N+n$. For each such X:

Compute its prime factors as follows:

i. Use trial division by 2,3,5 and 7 to dispose of tiny factors

ii. Run the Lenstra or Quadratic Sieve factorization method to factor what's left.
Use the prime factorization to generate all factors (prime or composite) of X. Insert all of these factors that are between $n$ and $\sqrt{N}$ to your output list.


What is the fastest algorithm for Weighted Planar Max Cut In 1990's, the paper Unifying Maximum Cut and Minimum Cut of a Planar Graph described an
$O(n^{3/2}\log n)$-time algorithm for Weighted Planar Max Cut, a landmark in the field.

Recently, this paper appeared:

  Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
  http://arxiv.org/abs/1003.1320

I was wondering if the time for Weighted Planar Max Cut could be improved from $O(n^{3/2}\log n)$ to $O(n \log^c n)$ for some small constant $c$, using ideas from this paper?

In general, have any improvements in Weighted Planar Max Cut been published?

Shih, Wu, and Kuo's "unifying" paper reduces the planar maximum cut problem to two related problems in planar graphs: (1) maximum-weight bipartite matching and (2) minimum cycle (aka weighed girth).  Both problems are solved in $O(n^{3/2}\log n)$ time using divide-and-conquer algorithms that rely on Lipton and Tarjan's planar separator theorem.

After a long series of improvements, the minimum-weight cycle in a weighted planar graph can now be computed in $O(n \log\log n)$ time using a recent algorithm of Łącki and Sankowski (2011).

However, I am unaware of any improvement on the time to find maximum-weight matchings, which means Shih, Wu, and Kuo's $O(n^{3/2}\log n)$ time algorithm is still the fastest algorithm known (at least to me) for weighted planar max-cut.


Is there current research into the implemention of Randomness Extractors? Has there been research into implementing randomness extractor constructions?

It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making programmatic implementations potentially unrealistic.

Some context:
I'm interested in using randomness extractors as a fast source of (provably?) random numbers for use in Monte Carlo simulations. We (an ETHZ Computational Physics group) have biased high-entropy sources from quantum random number generators that we would like to extract randomness from. A previous student attempted to implement a Trevisan construction and ran into spacial complexity problems. Aside from that student, I have not found any reference to people trying to implement extractors.

Note:
I'm a CS undergrad who is very new to the area of Theoretical CS and Randomness Extractors.

Much of extractor literature is about minimizing the seed length, which is important for derandomization application. However, it may not be crucial for yours. Also, often the literature focuses on relatively large error (e.g., 1/100), which is fine for derandomization but may be problematic in other settings, that require an exponentially small error.

In your setting, it may be OK to generate once and for all a long random seed (say by tossing coins), and then use it to extract. In this case you could use pairwise independent hash functions that have rather efficient implementations. I wrote a paper with Shaltiel and Tromer on this issue. You may also be able to use almost independent hash functions, that can be more efficient and have smaller seed. (Don't know offhand a good reference for their efficient implementation, though there have been several works on this.)

If you have multiple sources that are independent, then you can do better things. The classical Hadamard extractor works if the entropy rate is larger than 50% (this should be mentioned in the surveys above). If the entropy is smaller than 50% then we had one simple construction with Impagliazzo and Wigderson . The dependence between of number of sources and error achieved on the entropy rate is not ideal, though to really understand it you'll need to look at the exact bounds given by today's state of the art sum product theorems. (And if you're willing to assume certain number theoretic conjectures you can get even more efficient extractors.) This construction has been greatly improved in various ways, some of which could be relevant to your application. A great source for these is Anup Rao's Thesis.


Can concurrency models be compared in terms of some metrics? In Seven Concurrency Models in Seven Weeks by Butcher, it compares Actor Model and Communicating Sequential Processes (CSP):

CSP is more flexible than actor model:
In actor model, the medium of communication is tightly coupled to the unit of execution: each actor has precisely one mailbox;
In CSP, channels are first class and can be independently created, written to, read from, and passed between tasks.

Nothing stops  CSP  from  supporting distribution  and  fault  tolerance,  but historically  CSP  has not had  the  same  level  of  focus  and  support  of the two as actor model does.

Both actor model and CSP do not directly support parallelism. Parallelism has to be created based on concurrency building blocks.

I was wondering if the two concurrency models can be compared in terms of some metrics (some measurement, quantities, ...) in aspects either mentioned above or not. (Butcher's book doesn't mention such metrics. I also tried  but haven't found it in Varela's Programming Distributed Computing Systems.)
If concurrency models can not be compared in metrics, how can they be compared?
I am looking for some metrics to fit into the comparison between the concurrency models. Also for books, papers and articles for comparing them.
Thanks.

There are no metrics, but an excellent discussion of many concurrency models, in Tony Garnock-Jones PhD thesis. See the (HTML version of the) chapter "Approaches to coordination". This studies concurrency models with a particular focus, namely how information is exchanged for coordination.


Difficulty of Getting into Top Graduate Program in TCS I'm currently a sophomore interested in TCS. Recently I've been somewhat bothered by the difficulty of getting into PhD programs in the future since the selection is indeed very competitive.

I looked through the webpages of some top CS school and found that their current grad students mostly also come from top undergrad schools and many graduated summa cum laude, i.e. with highest honors(top GPA, I guess?).

I've also been advised by a PhD student that by the time of application, I'd better figure out a specific area in theory(algorithms, complexity, crypto, etc) to write in my PS. Being interested in a wide range of topics would put me at disadvantage.

Though I'm at a top 5 university, I started learning CS only after getting into college. I fell in love with theory right away but I felt really left behind by many around me. I have a relatively good GPA, but not stellar enough. I've also been doing research in a few diffenrent topics but haven't published a paper yet. And currently I'm still widely interested in graph theory, complexity, cryptography and even quantum computing.

I know I still have two years to go. But sometimes I felt really pushed by the scenario in academia nowadays. I believe that many students are in the same boat as I am.

I wonder roughly what is the difficulty of getting into top graduate programs in theoretical cs(MIT,Berkeley,Stanford,CMU,Princeton etc.)nowadays? Does GPA really play no role once you have reached a "bar"(like 3.7/4), as many said?
Do I have to decide on a specific area just after 3 years of undergrad studies?

And any other advice related to my situation(research, application, anything) would be appreciated.

Disclaimer: I am just a student, so I cannot speak authoritatively about admissions. I haven't been on an admissions committee, but I can tell you my understanding of how it works.

A PhD admissions committee looks at an application and asks "will this person do well in our PhD program?" Doing a PhD is first and foremost about doing novel research. So the question is: "Can this person do research?"

Your application has several parts, which together need to convince the committee that the answer is yes. Below are my thoughts on the various aspects.

Recommendation Letters: These are extremely important. A good recommendation letter comes from someone who knows you well in a research setting and who is an established researcher. Such a person should be in a good position to judge your ability to do research and their opinion will carry a lot of weight.
 A strong recommendation letter will talk about research-level work you have done and speak about your skills as a researcher, particularly your ability to be self-directed. A letter that only talks about how you did in class is not strong.
 To get strong recommendation letters, you should try to do research projects with professors either at your college or at a different college through an REU program or similar. If you do well, those professors will be able to write strong letters for you. (Make sure to work with research-active professors. e.g. work with a professor that has current PhD students. The more well-known your letter writer is, the more weight their recommendation carries.)
 Publications: If you already have written research articles, that is a clear sign that you can do research. Don't worry too much about this. If your recommendation letters say that the work you did is of publishable quality, that already says a lot, even if it hasn't been published yet.
 GPA and Transcript: Having a good GPA and transcript matters, but is not decisive on its own. It shows that you are hardworking and that you have the appropriate background, which are necessary attributes for a PhD student.
More important than overall GPA is which courses you took and how well you did in them. Getting a B in art history will not sink your Theoretical Computer Science PhD application, whereas a B in Algorithms or Linear Algebra is a red flag.
Taking more computer science and math courses, particularly at higher levels, and getting good grades makes your application look solid.
 Your College: Being an undergraduate at a top research university is an advantage because it gives you exposure to a research environment and gives you opportunities to do research, which leads to strong recommendation letters. If you are at, say, a liberal arts college, you will need to be more proactive about finding research opportunities (e.g. by doing a REU at a research university over the summer).
 Admissions committees will not discount your application based on your undergraduate institution.
Personal Statement: The personal statement should convince the committee that you have the right motivation for doing a PhD. In particular, it should tell them why you want to do research.Do not talk about what you did when you were 10 years old --- that's completely irrelevant. Talk about your recent research experiences; talk about scientific questions that excite you.
 You do not need to choose a subfield when applying. However, it looks good if you can discuss some subfields that interest you; it shows that you have thought seriously about what you want to do. Read up on the professors at the school you are applying to. If one of them does something that excites you, mention it (and why).
GRE scores: Everyone knows the GRE is flawed, but it is the only standardized information available. Top programs receive far too many applications, so they may use the GRE to "filter" applications. As long as your GRE score is passable, it is not a problem.
Writing Sample: A few places ask for a writing sample. They want to know if you can write clearly --- this is important when writing research articles.  Just make sure this has been appropriately proofread. Bad spelling and grammar or rambling are a bad look. (This applies to your whole application!)
CV: This should be a concise overview of your skills and experiences.
Web Presence: Some professors will google you. So your web presence can matter.You can take control of your web presence by setting up a homepage. This doesn't need to be fancy. As a bonus, you can set up analytics and see who is googling you.

The fact that you are thinking about this as a sophomore is a promising sign that you are on the right track.

Don't worry too much! Get some research experience --- this is also useful to you, as it gives you useful experience and helps you figure out whether you will enjoy doing research full time. Otherwise, just work hard and take courses that interest you.

One final piece of advice: Ask people to read over your application, e.g. the people writing your recommendation letters. They can tell you if you have missed something.

TL;DR: Do research!


Hardness of MAX-CUT on sparse graphs Let a weighted graph $G(V,E)$, where the weights are real (positve and negative). Assume that $G$ has $\mathcal{O}(n\log n)$ edges.

How fast can we compute MAX-CUT on this graph?
Can we compute (approximate within $\epsilon$) MAXCUT faster on sparse graphs compared to dense ones?

There cannot be significantly better algorithms for graphs with $O(n\log n)$ edges than there are for general graphs. This is because the Benczur-Karger cut sparsifier can take an arbitrary graph, and output a graph with only $O(\frac{n\log n}{\epsilon})$ edges such that the value of any cut in the sparsified graph is within a $(1\pm\epsilon)$ factor of the cut value in the original graph. Therefore, a PTAS for sparse graphs would yield a PTAS for general graphs, by simply first running the cut sparsifier, and then approximating max-cut in the sparse graph. Since it is NP hard to approximate max cut in general graphs to within a factor of 16/17, this is also true for sparse graphs.

Note that there is no PTAS for max-cut even when all edge weights are non-negative. Things are even worse when negative edge weights are allowed, as in your question. See this question for the negative edge weight case: Max-cut with negative weight edges


Graphs for maximum number of min cuts? Aside from the cycle graph, are there other simple unweighted graph constructions for which there are $\omega(n)$ distinct min cuts?

Aside from the cycle graph, I think a nontrivial class of graphs with $\Omega(n^2)$
distinct min cuts are cactuses. A cactus  is a connected graph in which every block (a maximal 2-connected subgraph) is a chordless cycle.

EDIT: In case the considered cactus has $n$ nodes and $b$ blocks of order $n_1, n_2, \ldots, n_b$, the number of min cuts is $\Omega\left(\sum_{i=1}^b n_i^2\right)$.
As $\sum_{i=1}^b n_i^2 \ge \frac{1}{b} n^2$, the number of min cuts is $\Omega(n^2)$,
provided the number of blocks $b$ is bounded.


Machine Learning: Calibrating SubGroups of Probability Predictions inside a Dataset which should sum to 100% I am working on an interesting type of problem where I want to make predicitons for individual elements within subgroups- with the knowledge that the sum of the probabilities within a subgroup should sum to 1. The initial response will probably be to use a softmax system but this is subtley different (unless I have misunderstood something).
I will use an analogy to keep it straighforward:
Effectively in a flowerpot there are 10 flowers- only 1 of which is certainly is a daffodil and the other 9 are certainly not- some are quite similar to daffodils while others are more similar to flavorsome herbs or thorny bushes.
I have a dataset of 100,000 flowers (which are in 10,000 flagged lower pots/subgroups). I know characteristics for each of the flowers such as stem height, petal colour, odour pleasure, diameter etc. as well it being flagged whether or not it is indeed a delightful daffodil.
I am able to generate a logistic ML model quite easily which informs me of the probability that a certain flower is a daffodil based on the data from the other flowers. But I am unable to get it to work so the sums of probabilities within sub groups equal one- generally they are close but often as low as 65% or as high as 130%.
My interim solution is to carry out a post prediction clean, which determines the total probability assigned to the group and normalises predictions so they sum to one. Not awful but not great.
Am I a moron? Is this a softmax problem? Or something that a ML algo in existence can handle?
Thank you, a daffodil to those who help :)

Let $p_i=\Pr[F_i]$ be the probability that flower $i$ is a daffodil, according to your model (without taking into account the group structure).
Now you are given a group of 10 flowers, with probabilities $p_1,\dots,p_{10}$, and you're given the promise that exactly one of them is a daffodil.  To update your probabilities based on this additional promise, you can use Bayes rule.  Let $E$ be the event that exactly one in the group is a daffodil.    Then
$$\begin{align*}
\Pr[F_i|E] &= {\Pr[F_i \land E] \over \Pr[E]}\\
&= {\Pr[F_i \land E] \over \sum_j \Pr[F_j \land E]}.
\end{align*}$$
Note that
$$\Pr[F_i \land E] = \Pr[\neg F_1 \land \cdots \land \neg F_{i-1} \land F_i \land \neg F_{i+1} \land \cdots] = (1-p_1) (1-p_2) \cdots p_i \cdots (1-p_{10}) = {p_i \over 1-p_i} \prod_j (1-p_j).$$
Therefore,
$$\Pr[F_i|E] = {{p_i \over 1-p_i} \over \sum_j {p_j \over 1-p_j}}.$$
This is the probability you wanted to compute; so, use that.


Breaking cycles in network graph by adding nodes and rerouting edges I have a quite "common" need : making a directed graph (with one or several cycles) a directed acyclic graph (DAG).

But the way I want to achieve it is, I guess, way more specific : I would like to break cycles by duplicating nodes, and rerouting edges.

For exemple, for a graph with such a loop (A > B > C > A) :

I would like to get a non-looping graph like this one :

So here :

A new node A' has been created (duplicated from A)
The edge C > A has been deleted, replaced by C > A'
Another edge A' > D is also created, to preserve "adjacency": it was possible to go from B to D in the first graph, so I want this to be possible in the transformed graph too.

The case above may appear quite simple, but I am tryig to build an automated method to do that. I also have some cases with interwined cycles, which are way more complex to deal with. Finally, I aim to minimise the number of duplicated nodes. I usually work with graphs having less than 100 nodes.

The aim of all this is to be able to order nodes (using Kahn or DFS).

In the exemple above, A > B > C > A' > D seems the most intuitive order.
A > D > B > C > A' would also be a valid order, but I think it is less intuitive.

This is also the reason for keeping the original A > D arc, forcing the resulting order to be the first one mentionned above.

Any leads about how to do that ? Any existing methods or scripts (preferably python) ?
During my research, I have never found any information about such a way to break cycles, maybe I have not searched enough, or maybe not in the good direction.

Note : this question has also been posted on StackOverflow [here]

This problem is Feedback Vertex Set in disguise, and hence NP-Hard, but I'd imagine there are good heuristics out there (I don't know the references myself, maybe someone can help me out here).

More specifically, for an input graph $G = (V, E)$ with minimal FVS $S \subseteq V$, there is a solution to your problem that copies each member of $S$ once (and no other nodes are copied at all), and this is best possible.  That solution is as follows.  Define the nodes of $G'$ in the following order: first we put all the nodes in $S$ (in any order), then we put the nodes of $V \setminus S$ in topological order in the DAG $G \setminus S$, and finally we put another identical copy of the nodes of $S$ (again in any order).  The edges $(u, v) \in E$ are placed in $G'$ in the natural way: if either endpoint $u, v \notin S$ then there is only one way to place the edge in $G'$, and if both $u, v \in S$ then in $G'$ the corresponding edge goes from the first copy of $u$ to the last copy of $v$.

This graph $G'$ will have the following property: you can map the nodes of $G'$ to the nodes of $G$ in a way that bijects the edges of $G'$ with the edges of $G$.  I believe this is the right way to formalize the node-splitting process you are describing (in the node-splitting view, you would iteratively split each node $s \in S$ into the two corresponding nodes in $G'$, rerouting edges such that the incoming edges all go to one new copy $s_1$ and the outgoing edges all go to the other new copy $s_2$).

Additionally, if $G$ has $n$ nodes then $G'$ has $n + |S|$ nodes, but there is no graph $G''$ on $n + |S| - 1$ nodes with the above property.
That is because, if one can split a set of nodes $S$ to reach a DAG, then surely one also has a DAG by deleting $S$ entirely.  So the size of a minimal FVS is no more than the number of extra nodes required in $G'$.


What's known about basing one-way function on the $P \neq NP$ assumption? Is there a conditional impossibility result or the question is completely open?

We cannot hope to prove a general impossibility result since if one-way functions exist (and we believe they do), then in particular it follows that the statement "If $P \ne NP$ then one-way functions exist" is true.

However, we can prove that certain proof techniques are too weak to prove that statement. In particular, the following paper of Akavia, Goldreich, Goldwasser and Moshkovitz proves that this statement cannot be proved by certain black-box reductions (conditioned on plausible assumptions):

http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html


Forms of types in the calculus of constructions In the usual presentations of the calculus of constructions (CC) with two kinds Prop and Type such that Prop:Type and impredicative on Prop, it is easy to show the following result:
every closed term A such that $\Gamma \vdash A:\kappa$ (where $\kappa$ is a kind) reduces to a product, namely $A \rightsquigarrow^* \forall x^C.D$.

The easy proof relies on the size of the longuest path from $A$ to its normal form, namely on strong normalization of CC (lexicographic induction on the length of the longuest path to normal form, and height of the derivation).

In "Benthem Jutting, Typing in Pure Type Systems, 1993, Information and computation" there is the following result for all pure type systems:
if $a \in T_S$ and $\Gamma \vdash a:A$ then $A \rightsquigarrow^* \forall x_1^{C_1}\ldots\forall x_n^{C_n}.s$ where $s$ is a sort and $T_S$ is almost the "set of types".

We can think prove first statement using the second: if $\Gamma \vdash A:\kappa$ then $\Gamma, x:A \vdash x:A$ and then $A$ reduces to a product. Unfortunately $T_S$ does not contain the variables.

The question is: is there a proof of the first statement not relying on the strong normalization of CC ?

My guess is that the answer is no: $A$ can $\beta$-reduces to an application, that can reduces to an application, ... The only way to know if it eventually reduces to a product is to effectively $\beta$-reduce it, and in the worst case to normalize $A$.

On the face of it, the result you're asking for is a normalization result, as it asserts that every well-typed term of a certain form has a head-normal form (of a certain shape).

However it is legitimate to ask whether your statement is equivalent to normalization of the CC, since you are only asking for head normal forms of a certain sub-class of terms.

In general, it doesn't make sense to ask whether two true statements are equivalent, since the answer is always (trivially) yes. However in this specific case, normalization of CC must rely on powerful meta-theory, since it implies consistency of some strong form of higher-order logic! So it makes sense to ask:

  In some weak meta-theory (say $\mathrm{PRA}$ or $\mathrm{PA}$) can we prove "CC is normalizing" $\Longleftrightarrow$ "Every closed term of type $*$ or $\square$ reduces to a product"?

The answer, I believe, is no.

Certainly, direction $\Longrightarrow$ holds, as you noted. But in the other direction, we have some counter-examples: in system $\mathrm{F_\omega}$, the fact that "type level" computations are normalizing is a consequence of the normalization of the simply-typed $\lambda$-calculus, and in Girard's system $U^-$, type level normalization holds, whereas it does not at the term level!

Things are a bit more complicated in the CC though, since type level terms can contain arbitrary term-level terms. The trick is that to compute head-normal forms, you don't actually need to dip into those terms to do reductions.

In PTS lingo, you only need to reduce $(*,\square, \square)$ and $(\square, \square, \square)$ redexes. But normalization of those only relies on the normalization of some variant of the simply typed $\lambda$-calculus (though I won't detail that argument right now). The hard part is showing that reducing the 2 types of redexes above must result in a head-normal form for terms of type $*$ or $\square$. You can do this by contradiction by supposing there is a head redex at that level, and showing that it must be of one of the two forms above.


reference request- property of subset of rows in a matrix I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M such that the following holds: for every $i\in [n]$, there is $at$ $most$ one row in $v\in S$ such that $v_i\neq z_i$.

I was wondering if this combinatorial notion has been used to characterize some complexity in literature? Any reference/ pointer is welcome. I am not interested in an algorithm to find the largest subset, but rather if such a combinatorial notion has been used to character some "other complexity measure"

Your problem can be solved in polynomial time, by reduction to bipartite matching.  In other words, there is a polynomial-time algorithm to find the largest subset $S$ of rows with your desired property.

Construct an undirected bipartite graph with $m$ left-vertices (one per row) and $n$ right-vertices (one per columN).  Add an edge $(i,j)$ whenever $M_{i,j} \ne z_j$.  Now each subset of rows with your property corresponds to a matching in this bipartite graph: take $S$ to be the set of left-vertices covered by the matching.  In particular, the maximum matching in this graph corresponds to the largest subset of rows that satisfies your property.  You can compute the maximum matching in polynomial time.


Statement that inequality of P and NP obstructs finding a proof of their separation In this set of video lectures, Prof. Mulmuley emphasizes several times that P vs. NP is a very deep philosophical question at the core of Mathematics and that the fact that the two classes are not equal stands as an obstruction to proving that they are not equal (I paraphrase here, according to my limited understanding).

Now, I have two difficulties with this idea. Firstly, it was presented as though it were common mainstream belief (akin to the belief that P != NP). I did not come across this idea before, being expressed explicitly in this manner (maybe this is lack of exposure from my side).

The second difficulty is a bit more technical. P != NP tells something about hardness of finding proofs for provable statements, it does not saying anything about existence vs. non-existence of such proofs. Said naively, if P != NP, then this fact should not obstruct the existence of an easy, verifiable proof of this fact (other facts may provide such an obstruction though).

Am I misunderstanding something?

Note: I was not really sure if this question belongs to tcs.SE but I couldn't find a more suitable choice.

I also think that what was meant might have been obstructions akin to the natural proofs barrier of Razborov and Rudich. The barrier on a high level shows that current methods of proving circuit lower bounds are "self-defeating" when applied to the P vs NP problem. Suppose you want to prove that SAT is hard by showing that it satisfies some predicate which is not satisfied by problems in P. Suppose the predicate is satisfied by most boolean functions (the largeness property) and can be computed in time $2^{O(n)}$ on functions that take $n$ inputs, when given the $2^n$-size truth table of the function (the constructivity property). Razborov and Rudich show that if such a predicate exists, then there are no strong pseudorandom number generators. So the existence of the object we're trying to use to separate P from NP would itself imply a statement in the spirit of P=NP.

There are arguments why you expect that hardness predicates would satisfy the largeness property. Certain "formal complexity measures" have the property that if they lower bound the complexity of any one function, then they lower bound the complexity of most functions. Also, by the classical counting argument, most functions are hard, so if you expect that the predicate captures hardness, then it should be satisfied by most functions. The constructivity property gets to your question. It is true that there could in principle exist a hardness predicate that cannot be evaluated in time polynomial in the truth table of the function. But most combinatorial proofs of existence can be made constructive. Even proofs that on first inspection seem to use inherently non-constructive arguments were often later made constructive. Two recent examples are the algorithmic Lovasz Local Lemma of Moser and Tardos and Nikhil Bansal's constructive version of Spencer's discrepancy upper bound for general set systems. So it looks like we might not have proof methods that take us outside the realm of polynomial time constructions.

Check the details in the natural proofs chapter of Arora-Barak: http://www.cs.princeton.edu/theory/complexity/naturalchap.pdf


Universal sets of gates for SU(3)? In quantum computing we are often interested in cases where group of special unitary operators, G, for some d-dimensional system gives either the whole group SU(d) exactly or even just an approximation provided by a dense cover of SU(d).

A group of finite order, such as the Clifford group for a d-dimensional system C(d), will not give a dense cover.  A group of infinite order will not give a dense cover if the group is Abelian. However, my rough intuition is that an infinite number of gates and basis changing operations of the Clifford group should suffice to provide a dense cover.

Formally, my question is:

I have a group G that is a subgroup of SU(d). G has infinite order and C(d) is a subgroup of G. Do all such G provide a dense cover of SU(d).

Note that I am particular interested in the case when d>2.

I take the Clifford group to be as defined here:
http://arxiv.org/abs/quant-ph/9802007

I believe the answer to original question is probably yes, but unfortunately, I can't say that definitively.  I can help answer Peter's extended question, however.

In math/0001038, by Nebe, Rains, and Sloane, they show that the Clifford group is a maximal finite subgroup of U(2^n).  Solovay has also shown this in unpublished work that "uses essentially the classification of finite simple groups."  The Nebe et al. paper also shows that the qudit Clifford group is a maximal finite subgroup for prime p, also using the classification of finite groups.  This means that the Clifford group plus any gate is an infinite group, which makes one of the assumptions of the original question redundant.

Now, both Rains and Solovay told me that the next step, showing that an infinite group containing the Clifford group is universal, is relatively straightforward. However, I don't know how that step actually works.  And more importantly for the original question, I don't know if they were only considering the qubit case or also the qudit case.

Actually, I might add that I don't understand the Nebe, Rains, and Sloane proof either, but would like to.


How to find largest supergroup in polynomial time? Let $G \le S_n$, and G acts on set $[n]$ via a map $\pi$:
$$\pi : G \times [n]\mapsto [n] $$

In Input generating set of $G$ is given.

Question : I need to find the largest supergroup $G^{'}$ (generating set) of $G$  in $S_n$ which has same blocks as $G$.

  For all $x \notin \langle G \rangle$

  check whether $\langle G,x\rangle$ has same blocks as $\langle G\rangle$

  If yes then add $x$ to the generating set of $G$
  Else do nothing

This is a brute force algorithm and running time of this algorithm is exponential many operations i.e. $O(n^n)$.

Question  : Is there an polynomial time algorithm for the above problem ?

Motivation : Isomorphism of hyper-graphs of low rank in moderately exponential time (see this)

Yes, this can be solved in polynomial time (and, I think, even in $\mathsf{NC}$).

First, it's easy to reduce to the case of transitive $G$.

Next, find the minimal blocks of $G$. (See e.g. Section 3.6(B) of Dixon & Mortimer.) This can be done by choosing a point $x \in [n]$, and for each $y \in [n]$, $y \neq x$, computing the (undirected) connected components of the orbital digraph generated by $(x,y)$. Each such connected component is a block; take the smallest ones.

If there are $b$ blocks each of size $s$, then the desired group is the wreath product $S_b \wr S_s = (S_b)^s \rtimes S_s$ in its natural action on $[n]$.


What formalisms exist to describe the translation of an abstract syntax tree into another formal language? I'm looking for a declarative formalism to describe the transformation of an abstract syntax tree generated by the parsing of one formal language into second formal language. An example of a transformation that it would have to describe is to transform following,

type Bool : Type {
    value false : Bool;
    value true : Bool;
};

into the following,

$Bool : Type;$

$Bool = (Unit \lor Unit);$

$true : Bool;$

$true = (inj_0 unit);$

$false : Bool;$

$false = (inj_1 unit);$

The only thing I can think of is defining piecewise-defined recursive function with nodes of the abstract syntax tree of the original language as input. Is there not a more concise way of declaring the transformation?

I've already implemented such transformations straightforwardly and compositionally in the programming language Haskell but I'm not doing so well on formalising the tranformation.

Also, to be clear I am not talking about attaching semantic actions t the original grammar (or an attribute grammar) because I assume an abstract syntax tree has already been generated by parsing the first formal language because other analysis and rewriting needs to be done on such a tree.

Note that I have no interest in algorithmic efficiency of such a formalism, I only want to show that a injective function from the original formal language to the second formal language exists.

I know I must have read about this in the formal language literature but I can't think of anything specific. I've probably forgotten something really obvious...

Edit:

What about natural deduction style? How could such translations be represented in natural deduction? I'll have to think about that...

Look at Bob Harper's book. It provides loads of declarative formalisms for specifying programming language semantics and so forth. Chapter 6 describes declaratively how to translate concrete into abstract syntax. You could use the same ideas to translate one language into another.

Following Harper (and many others), you could write rules defined inductively on the structure of your source syntax, as follows:

$\begin{array}{c}
a \leadsto e \qquad b \leadsto f \qquad x=foo(a,b,e,f) \\
\hline
\mathsf{K}~a~b \leadsto \mathsf{S}~e~f~x
\end{array}
$

Here $\mathsf{K}$ is a constructor in your source language and $\mathsf{S}$ is in your target language. $foo$ is some function which may compute other required information (it too could be defined as a set of rules).
The translation function/relation essentially inductively decomposes your source syntax and produces a term in your target. You can also thread through additional information to help with the translation process. For example, your rule could look like:

$\begin{array}{c}
E'\vdash a \leadsto e \qquad E''\vdash b \leadsto f \qquad x=foo(E,E',E'',a,b,e,f) \qquad E' = \cdots
\qquad E''=\cdots \\
\hline
E\vdash \mathsf{K}~a~b \leadsto \mathsf{S}~e~f~x
\end{array}
$

Here $E$ can store any information that needs to be threaded through.

Note that such specifications differ very little from a standard recursive function defined inductively in the program syntax. But they may be easier to read, and they may actually define a relation, rather than a function, by allowing a little nondeterminism.


Johnson and Lindenstrauss lemma for hamming space A result of Johnson and Lindenstrauss shows that a set of $n$ points in high
dimensional Euclidean space can be mapped into an $O(\frac{\log n}{\epsilon^2})$- dimensional Euclidean space such that the distance between any two points changes by only a factor of $(1\pm \epsilon).$

I am looking for reference for a similar result for Hamming space- i.e.  a set of $n$ binary vectors  can be mapped into a very low dimensional  space such that the hamming distance between any pair of vectors is approximately preserved.

Consider the $n$ vectors $e_1,\ldots,e_n$ of weight $1$, and the zero vector $e_0$. The Hamming distance between $e_0$ to any $e_i$ is $1$. Let $\varphi$ be a map into a Hamming cube of dimension $m$, and suppose that it preserves distances up to a factor of $C$. In particular, the $n$ points $\varphi(e_1),\ldots,\varphi(e_n)$ are within distance $C$ of $\varphi(e_0)$. On the other hand, the number of points at distance at most $C$ from $\varphi(e_0)$ is $O(m^C)$. We conclude that $m = \Omega(n^{1/C})$ is polynomial in $n$ rather than logarithmic in $n$.


Is the exponent in the rectangular matrix multiplication convex? My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a $n \times n^c$ and a $n^c \times n$ matrix. The authors show a graph of how the exponent in the time complexity depends on $c$. This graph is clearly convex. This would mean that one can upper bound the time complexity by linearly interpolating the exponent between that case of $c = 0.31389$ (where the exponent is 2) and $c=1$ (where the exponent is $\omega$). This would be useful for stating the time complexity of an algorithm I came up with.
However, they do not prove that the graph is convex. Is it convex? If so, any ideas as to how to cite this fact?
https://arxiv.org/abs/1708.05622

Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?


Is an infinite incomputable sequence random wrt a computable measure? Take an arbitrary infinite binary sequence $\omega$. The interesting case is when $\omega$ is not computable. Is there a computable (semi-)measure $\mu$ such that sequence $\omega$ is $\mu$-random in the sense of Martin-Löf?

Or $\mu$-random is some weaker sense?

Clearly, $\omega$ is $\mu$-random for $\mu$-almost all sequences. So the question is what happens with the sequences from that set of measure zero.

Mucknik, Semenov and Uspensky showed that there are sequences which are not Martin-Löf random for any computable measure.  They call all other sequences (which are Martin-Löf random for some computable measure) "natural sequences".

  Andrei A. Muchnik, Alexei Semenov, and Vladimir Uspensky. Mathematical metaphysics of randomness. Theoretical Computer Science, 207(2):263–317, 1998.

This topic is also discussed in

  Laurent Bienvenu and Christopher Porter. Effective randomness, strong reductions and Demuth’s theorem.

  Jan Reimann and Theodore A. Slaman. Probability measures and effective randomness.

  Jan Reimann and Theodore A. Slaman. Measures and their random reals.

Here is a quick proof (which may be different from the above references):

Let $\{U_i\}$ be a (non-effective) enumeration of all $\Sigma^0_1$ sets making up some level of the universal Martin-Löf test for some computable measure $\mu$.  Each $U_i$ is dense and open, so by the Baire category theorem (countable intersection of dense open sets is dense), the intersection $\bigcap_i U_i$ is nonempty.  Any sequence in this intersection cannot be Martin-Löf random for any computable measure $\mu$.

The same can be done for Schnorr randomness (which is weaker than Martin-Löf randomness). Let $\{U_i\}$ be the collection of all dense $\Sigma^0_1$ sets of computable $\mu$-measure for some computable measure $\mu$.

UPDATE Oct 23, 2013:

I realize there are three things to add (which I am sure are all well-known and they are probably in the above mentioned papers).

My above proof actually shows that 1-generics cannot be Martin-Löf random for a computable measure, since 1-generics are in all dense $\Sigma^0_1$ sets.
The K-trivials are not Martin-Löf random on any computable measure.  A sequence $X \in \{0,1\}^\mathbb{N}$ is low-for-random (a.k.a. $K$-trivial) if $\text{MLR}^X = \text{MLR}$. It can be shown that this property also extends to all computable $\mu$.  That is, if $X$ is K-trivial, then $\text{MLR}_{\mu}^X = \text{MLR}_{\mu}$ for all computable $\mu$. Hence, the non-computable $K$-trivials cannot be random for any computable measure.  For if a $K$-trivial $X$ is random on a computable measure $\mu$ then $X$ is random relative to $X$.  This means $X$ is an atom.  However, only computable points can be atoms of computable measures.
The set of all "natural sequences" is precisely the set of sequences truth-table reducible to a Martin-Löf random (on the fair-coin measure).  (The main idea is that every computable measure is the push-forward on an a.e. computable map, and the Martin-Löf randoms on the measure $\mu$ are exactly the sequences pushed over to the new measure.  The reason this computation is "truth-table" involves using "layerwise computability".)


deterministic randomness extractor and privacy Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over  the channel $P_{Y|X}$ which outputs $Y$ taking values on finite alphabet $\mathcal{Y}$. Suppose we take $n$ independent samples from channel output; namely, $Y^n=(Y_1, Y_2, \dots, Y_n)$ with distribution $\prod_{i=1}^nP_{Y|X}(y_k|x)$ where $x$ is the message sent over the channel.

Hence, we have $m$ distributions $\{P_{Y^n|X}(\cdot|x_1), \dots, P_{Y^n|X}(\cdot|x_m)\}$. I am looking for a deterministic randomness extractor which works for all of these $m$ distributions, that is, a randomness $Ext:\mathcal{Y^n}$ such that for given $Y^n$ distributed as one of these $m$ distribution $Ext(Y^n)$ is $\epsilon-$close to uniform distribution over $\{0,1\}^r$ (in total variation distance sense).

What is the largest random bits that we can extract, i.e., the largest $r$?
Is that $\min_{x}H_{\infty}(P_{Y^n|X}(\cdot|x))$?

The motivation of this comes from privacy.

I came across this late. Don't know if this question still matters. I am posting this as an answer since it is too long for a comment.

If n can be 1 but m is not too large (say, at most a small exponential in the min-entropy), a random function will be a good extractor with high probability. It will cost you a factor of something like log m in the min-entropy.

However, for large values of n, you should be able to find a good deterministic  extractor no matter how large m is since, once you condition on x, the distribution on outputs is IID. In particular, it is symmetric, so you can use as idea like von Neumann's trick or its generalizations to extract a small number of random bits just from the ordering of the elements. That might be enough to get the seed for a strong randomness extractor which could extract the rest of the randomness from the source. You have to be careful, but the idea would be to rely heavily on the IID structure to get a a deterministic extractor. Don't know if that's good enough for the application.


Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries? Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient algorithm for calculating permanents of 0/1 matrices exactly. On the other hand, Valiant provided a polynomial time reduction from the permanent of an arbitrary matrix with integer entries to the permanent of a 0/1 matrix. Why could one not make use of this reduction, followed by an application of the JSV algorithm (which can efficiently approximate the permanents of matrices with nonnegative entries but cannot handle matrices with negative entries) to efficiently approximate the permanents of arbitrary integer matrices?

The answer to the title question is: it's difficult to simulate a Markov chain with negative transition probabilies.

Valiant's reduction uses the Chinese remainder theorem, which requires an exact number, not just an approximation. The JSV algorithm cannot tell you what the permanent of a matrix is modulo 3, for example.

The type of reductions you'd need to reduce to JSV were named "approximation preserving reductions" by Dyer at al. An approximation-preserving reduction from a problem X to a problem Y is a way of turning an FPRAS for Y into an FPRAS for X (in a way that relativises). A simpler case of the same pattern is #DNF and #SAT:

There is an approximation algorithm (an FPRAS) for counting solutions of a formula in disjunctive normal form.
It is NP hard to approximate the number of solutions of a formula in conjunctive normal form to within a multiplicative constant (because it is NP hard to determine whether there is any satisfying assignment at all).
There is a reduction from #SAT to #DNF: given a CNF formula $\phi$ on $n$ variables, replace all the conjunctions by disjunctions and vice versa. If the resulting formula has $x$ solutions, then $\phi$ has $2^n-x$ solutions.

There is no contradiction, because the reduction described above is not approximation-preserving. Another common non-approximation-preserving reduction for counting problems is polynomial interpolation.


Time complexity of counting triangles in planar graphs Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward procedure shows that it can be done in $O(n\log{n})$ time. My question is two-fold:

What is a reference for this procedure?
Can the time be made linear?

From the algorithmic proof of Lipton-Tarjan's planar separator theorem we can, in time linear in the size of the graph, find a partition of vertices of the graph into three sets $A,B,S$ such that there are no edges with one endpoint in $A$ and the other in $B$, $S$ has size bounded by $O(\sqrt{n})$ and both $A,B$ have sizes upper bounded by $\frac{2}{3}$ of the number of vertices. Notice that any triangle in the graph either lies entirely inside $A$ or entirely inside $B$ or uses at least one vertex of $S$ with the other two vertices from $A \cup S$ or both from $B \cup S$. Thus it suffices to count the number of triangles in the graph on $S$ and the neighbours of $S$ in $A$ (and similarly for $B$). Notice that $S$ and its $A$-neighbours induce a $k$-outer planar graph (the said graph is a subgraph of a planar graph of diameter $4$). Thus counting the number of triangles in such a graph can be done directly by dynamic programming or by an application of Courcelle's theorem (I know for sure that such a counting version exists in the Logspace world by Elberfeld et al and am guessing that it also exists in the linear time world) since forming an undirected triangle is an $\mathsf{MSO}_1$ property and since a bounded width tree decomposition is easy to obtain from an embedded $k$-outer planar graph.

Thus we have reduced the problem to a pair of problems which are each a constant fraction smaller at the expense of a linear time procedure.

Notice that the procedure can be extended to find the count of the number of instances of any fixed connected graph inside an input graph in $O(n\log{n})$ time.

The number of occurrences of any fixed subgraph H in a planar graph G can be counted in O(n) time, even if H is disconnected. This, and several related results, are described in the paper Subgraph Isomorphism in Planar Graphs and Related Problems by David Eppstein of 1999; see Theorem 1. The paper indeed uses treewidth techniques.


What's the most efficient algorithm for Divisibility? What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask for is not (necessarily) an algorithm for Remainder Calculation. I just want to know whether $a$ divides $b$ or not. Being more specific, my question is whether exists or not some recent algorithm for Divisibility with time complexity better than $O(m\log m\log\log m)$, where $m$ is the number of bits of $\max\{a,b\}$. Further, is $\Omega(m\log m\log\log m)$ the lower bound of this problem?

Thanks and regards, and sorry if this is such a naive question.

Fleshing out my comments into an answer: since divisibility is (trivially) reducible to division, and since division is (nontrivially) reducible to multiplication via approaches like Newton's method, then your problem should have the same time complexity as integer multiplication.  AFAIK, there are no known lower bounds for multiplication better than the trivial linear one, so the same should hold true of your problem - and in particular, since multiplication is known to have (essentially) $O(n\log n\log^* n)$ algorithms, your hopes for a $n\log n\log\log n$ lower bound are almost certainly in vain.

The reason that division reduces precisely in complexity to multiplication — as I understand it — is that Newton's method will do a sequence of multiplications of different escalating sizes; this means that if there's an algorithm for multiplication with complexity $\Theta(f(n))$ then the complexity of a division algorithm using this multiplication algorithm as an intermediate step will be along the lines of $\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$ — and for all of the complexity classes under discussion this is just $\Theta(f(n))$.


Most general setting for fine-grained exponential-time complexity classes? Consider the class of functions computable in time $(b+o(1))^n = 2^{\log_2{(b)} \times n + o(n)}$ on a $2$-tape Turing machine.

By the Hennie-Stearns theorem, the same functions are computable in time $(b+o(1))^n$ on a $k$-tape Turing machine for any $k \geq 2$. And we can extend this equivalence to any model of computation that has an essentially linear time translation to and from $2$-tape machines. But this isn't a very natural class, even given that we believe in the extended Church-Turing thesis.

If we account for the space usage as well, more models are time-translatable with a blowup of the form $O(t \times s^k)$.  For example, when emulating a $2$-tape machine on a $1$-tape machine, it only has to scan the space used each time step, so the time blowup is $O(t \times s)$. Similarly, it seems like for RAM models there is a small $k$ that works: use one tape as an associative memory, a list of key-value pairs, which the emulator searches to find a key written on a different tape.

Now it seems sensible to say something like this: $F$ is computable in $(b+o(1))^n$ time and $2^{o(n)} = (1+o(1))^n$ space. I don't have to say what model I'm using because all the obvious ones work.  There is sort of a trade-off here, in exchange for a subexponential space restriction, we can specify a particular base $b$ for the time complexity of our function that's invariant in a larger context.

That's about as far as I understand this issue right now.  And I could be completely mistaken about something so partly I'm looking for some reassurance that the above is roughly correct. But I wonder if that's all there is to it? Is there some other set of assumptions under which the exponential time base of a function can be uniquely specified?

EXAMPLE: Rubinstein's theorem says that we can factor with base $2^\frac{1}{3}$. Since the algorithm uses subexponential space, this result is robust across models.

EXAMPLE: The square-root barrier for finding primes. If it were broken by exhibiting an algorithm that required exponential space on a Turing machine, would that really be a natural result, or possibly just an artifact of the machine model?

EXAMPLE: The Strong Exponential-Time Hypothesis. Might it be the case that a RAM program can solve general $\text{CNF-SAT}$ in exponential time with a base less than $2$, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base at least $2$ and (a slightly-weakened version of) SETH is true in the TM model only?  Is there a variant of SETH where only subexponential space algorithms are considered in order to make it applicable to more models?  Or is there some reason I'm not understanding that no generality is lost without this assumption?

(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few.

Might it be the case that a RAM program can solve general CNF-SAT in exponential time with a base less than 2, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base at least 2 and (a slightly-weakened version of) SETH is true in the TM model only?

SETH is generally stated in the word RAM model (in particular, with $O(\log t)$ word size, where the running time is $t$). This is mainly because most (if not all?) algorithmists don't care about or work in the multi-tape Turing machine model, but rather a random-access style model. It is true that in general we do not know how to simulate such time-t RAMs with multi-tape Turing machines super-efficiently, and (more importantly) we do not know how to simulate such RAMs in less than $O(t^2)$ gates with a Boolean circuit. But see the answer to the next question.

Is there a variant of SETH where only subexponential space algorithms are considered in order to make it applicable to more models? Or is there some reason I'm not understanding that no generality is lost without this assumption?

Note there is a very simple time-space tradeoff one can obtain, if SETH is false. Suppose we have a $2^{\beta n}$ time algorithm $A$ for k-SAT on $n$ variables, using $\Theta(2^{\beta n})$ space, where $\beta < 1$. Consider the following algorithm $A_{\alpha}$ parameterized by some parameter $\alpha \in (0,1)$:
On $k$-SAT formula $F$, enumerate all assignments $a$ to the first $n-\alpha n$ variables of $F$, plug $a$ into $F$ and run $A$ on the resulting $\alpha n$-variable formula. Stop and output a SAT assignment if it's found.
Note the above $A_{\alpha}$ runs in $O(2^{n-\alpha n}\cdot 2^{\beta \alpha n}) \leq O(2^{n-(1-\beta)\alpha n})$ time and uses only $\Theta(2^{\beta \alpha n}+\alpha n)$ space.
Corollary: If $k$-SAT has a $2^{\beta n}$ time algorithm, then for every $\epsilon \in (0,\beta)$ there is a $\delta > 0$ such that $k$-SAT can be solved in $O(2^{\epsilon n})$ space and $O(2^{(1-\delta)n})$ time.
Proof: Let $k$-SAT have a $2^{\beta n}$ time algorithm. For any given $\epsilon \in (0,\beta)$, set $\alpha = \epsilon/\beta < 1$. Applying the above reduction, we can solve $k$-SAT in $O(2^{\epsilon n})$ space and $2^{n-(1-\beta)\alpha n}$ time, so $\delta = (1-\beta)\alpha$ suffices. QED
However, note the time-space product of the resulting algorithm is not very favorable...
I do think that the "polynomial-space SETH" (which I believe I have seen in the literature, but am blanking on a reference) that only rules out polynomial-space faster-than-$2^n$ time for $k$-SAT, is a much more plausible hypothesis than SETH itself.


Set of languages that can represent every c. e. languange Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e. L$?

For example, a lot of languages can be formed by  it's union, intersection, complement of context-free languages, but some languages can not be, is, it possible that every L , computably enumerable language with infinity words be formed by union,complement,intersection (finite/infinite) of unabiguous CFLs with infinite words? If not, is it possible that every L , computably enumerable language with infinity words be formed by union,complement,intersection (finite/infinite) or any operation of unabiguous CFLs with infinite words plus some other languages such as  some context-sensitive languages?

$\textbf{update:}$ although the question has been answered, I hope there will be more solution to this problem. Thanks in advance.

$\newcommand{\CE}{\mathsf{CE}}$
$\newcommand{\NN}{\mathbb{N}}$

Because the set of c.e. languages over some alphabet $\Sigma$ is computably isomorphic to the set of c.e. subsets of $\NN$ (via a computable bijection between $\NN$ and $\Sigma^{*}$), we may as well consider c.e. subsets of $\NN$.

Let $\CE$ be the family of all c.e. subsets of $\NN$. Scott's graph model of the untyped $\lambda$-calculus is $\CE$ equipped with the application operation
$$X \cdot Y = \{n \in \NN \mid \exists k_1, \ldots, k_m \in Y . \langle [k_1, \ldots, k_m], n\rangle \in X\}$$
where $\langle {-}, {-} \rangle : \NN \times \NN \to \NN$ is a pairing function e.g., $\langle u, v \rangle = 2^u (2 v + 1)$, and $[k_1, \ldots, k_m]$ is the coding of finite lists, e.g., $[] = 0$ and $[k_1, \ldots, k_m] = \langle k_1, [k_2, \ldots, k_m]\rangle$. Think of $\langle [k_1, \ldots, k_m], n\rangle \in X$ as encoding information of the form "if input contains all of $k_1, \ldots, k_m$ then output $n$".

Now we can ask whether it is possible to generate all of $\CE$ using application and starting from some generators. The answer is positive. In fact, there is a single $G \in \CE$ such that by forming all possible applications
$$G, G \cdot G, (G \cdot G) \cdot G, G \cdot (G \cdot G), (G \cdot G) \cdot (G \cdot G), \ldots$$
we get precisely $\CE$. You can read more about it in Dana Scott's "Datatypes as lattices", SIAM J. of Computing, Vol 5. No. 3, 1976, pp. 522–587.


$\epsilon$-nets with respect to the cut norm The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\right|$.

Define the distance between two matrices $A$ and $B$ to be $d_C(A,B) = ||A-B||_C$

  What is the cardinality of the smallest $\epsilon$-net of the metric space $([0,1]^{n\times n}, d_C)$?

i.e. the size of the smallest subset $S \subset [0,1]^{n\times n}$ such that for all $A \in [0,1]^{n\times n}$, there exists an $A' \in S$ such that $d_C(A, A') \leq \epsilon$.

(EDIT: I forgot to mention, but I am also interested in "non-proper" $\epsilon$-nets, with $S \subset \mathcal{R}_+^{n\times n}$ -- i.e. if the elements of the $\epsilon$-net have entries outside of [0,1], that is also interesting.)

I am interested in both upper bounds and lower bounds.

Note that cut sparsifier techniques imply $\epsilon$-nets for cut metrics, but give something stronger than I need -- they give an $\epsilon$-net for which you can efficiently find an $\epsilon$-close point to any matrix simply by sampling from that matrix. One might imagine that there exist much smaller $\epsilon$-nets for which you cannot simply sample do find an $\epsilon$-close point to an arbitrary matrix.

I initially asked this question here on mathoverflow.

Here is an easy estimate.  Here we call a set S⊆X an ε-net of a metric space X when for every point x∈X, there exists a point s∈S such that the distance between x and s is at most ε.  If you want a strict inequality in the definition of ε-net, you can tweak the value of ε slightly.

It holds that ||A||∞ ≤ ||A||C ≤ n2||A||∞, where ||A||∞ denotes the entrywise max-norm of an n×n matrix A.

It is easy to construct an ε-net of the metric space ([0,1]N, d∞) with size ⌈1/(2ε)⌉N, and it is not hard to show that this size is the minimum.  (To show the minimality, consider the ⌈1/(2ε)⌉N points whose coordinates are multiples of 1/⌈1/(2ε)−1⌉ and show that the distance between any two of these points is greater than 2ε.)  By setting N=n2 and combining this with the aforementioned comparison between the cut norm and the max-norm, the minimum cardinality of an ε-net with respect to the cut norm is at least ⌈1/(2ε)⌉n2 and at most ⌈n2/(2ε)⌉n2.

Update: If my calculation is correct, a better lower bound Ω(n/ε)n2 can be obtained by the volume argument.  To do this, we need an upper bound on the volume of an ε-ball with respect to the cut norm.

First we consider the “cut norm” of a single vector, which is the maximum between the sum of positive elements and the negated sum of negative elements.  It is not hard to show that the volume of an ε-ball in ℝn with respect to this “cut norm” is equal to

$$ \varepsilon^n \sum_{I \subseteq \{1,\dotsc,n\}} \frac{1}{|I|!} \cdot \frac{1}{(n-|I|)!}
= \varepsilon^n \sum_{r=0}^n \binom{n}{r} \frac{1}{r!(n-r)!} $$

$$ = \frac{\varepsilon^n}{n!} \sum_{r=0}^n \binom{n}{r}^2
= \frac{\varepsilon^n}{n!} \binom{2n}{n}
= \frac{(2n)!\varepsilon^n}{(n!)^3}. $$

Next, since the cut norm of an n×n matrix A is greater than or equal to the cut norm of each row, the volume of an ε-ball in ℝn×n is at most the nth power of the volume of an ε-ball in ℝn.  Therefore the size of an ε-net of [0,1]n×n must be at least

$$ \frac{(n!)^{3n}}{(2n)!^n \varepsilon^{n^2}} = \left(\Omega\left(\frac{n}{\varepsilon}\right)\right)^{n^2}, $$

where the last equality is a boring calculation in which we use Stirling’s formula: ln n! = n ln n − n + O(log n).


Making SAT solvers competitive with specialized algorithms What are obstacles to making SAT solvers competitive with specialized graph algorithms? In other words, is it feasible to expect SAT solvers that can replace the role of algorithm designer -- ie, be able to automatically recognize problem structure and then solve it as quickly as a specialized algorithm?

Here some examples I think are challenging for today's SAT solvers:

Counting independent sets of size $k$. Encoding "x is an independent set of size k" gives a large formula which is hard to solve. An ideal SAT solver would recognize that this problem is easy on bounded tree-width graph with an addition of an extra "count" variable for bags.
Finding minimum Steiner tree. Again, "Steiner tree" has a global constraint, however, a specialized algorithm (like here) makes the task easier by adding an extra variable
Any problem that reduces to planar perfect matchings.

There is a nice paper that helps visualize the internal structure of SAT instances. See Visualizing SAT Instances and Runs of the DPLL Algorithm by Carsten Sienz (Appeared in SAT 2004). Basically, it draws a graph which the author calls "variable interaction graph" (according to some rules) to visualize the relation between the satisfied clauses. The author shows this by several partial runs of DPLL.

The main claim is that these visualization techniques could be used to detect structure and design an appropiate algorithm for it. However, it is still not clear how can we detect efficiently structures like the one presented in the paper. It is well known that SAT algorithms for one specific problem behave poorly in other problems. So there is "no-free-lunch", although this claim cannot be formally stated as far as I know.


History and status of the graph matching problem Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from it when using search engines.

Given two graphs $G=(V,E)$ and $G'=(V',E')$ such that $|V| = |V'|$, the task is to find a bijection $\pi : V \rightarrow V'$ such that this bijection establishes as much correspondences between edges of $G$ and $G'$ as possible.

In other words, if $M$ and $M'$ are the adjascency matrices, then we want to maximize

$\sum_{v,w \in V} M_{v,w} \cdot M'_{\pi(v),\pi(w)}$

This problem clearly contains graph isomorphism as a special case, and can be reduced to bipartite matching under a (non-polynomial!) reduction.

What kind of algorithms do exist, and what is known about its complexity?

From the paper Approximate Graph Isomorphism:

  We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $π$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log{n})}$ time approximation scheme that for any constant factor $α < 1$, computes an $α$-approximation. We prove this by combining the $n^{O(\log{n})}$ time additive error approximation algorithm of Arora et al. [Math. Program., 92, 2002] with a simple averaging algorithm. We also consider the corresponding minimization problem (of mismatches) and prove that it is NP-hard to $α$-approximate for any constant factor $α$. Further, we show that it is also NP-hard to approximate the maximum number of edges mapped to edges beyond a factor of 0.94.