The importance of Integrality Gap I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real solution of the relaxation of the problem. Lets consider vertex cover (VC) as an example. VC can be stated as finding an optimal integer solution of the following set of linear equations:

We have zero/one valued variables $x_v$s for each vertex $v \in V(G)$ of the graph $G$. The equations are: $0 \leq x_v \leq 1$ for $v\in V(G)$, and $1 \leq x_v+x_u$ for each edge $uv \in E(G)$. We are looking for values which will minimize $\sum_{v \in V(G)} x_v$.

The relaxation of this problem allows real values between $0$ and $1$ so the space of solutions is larger and an optimal real solution can be smaller than an optimal integer solution we want to find. Therefore we need to perform a "rounding" process on the optimal real answer obtained from linear programming to find an integer solution. The optimal integer solution will be between the optimal real solution and the result of the rounding process. IG is the ratio of an optimal integer solution to an optimal real solution and does not say anything about the rounding process. The rounding process can (in theory) completely ignore the real solution and compute the optimal integer solution directly.

  Why are people interested in proving bounds on IG?

Integrality gaps essentially represent the inherent limits of a particular linear or convex relaxation in approximating an integer program.  Generally, if the integrality gap of a particular relaxation is $x$, then any approximation algorithm based on that relaxation cannot hope to do better than an $x$-approximation.  So at the very least, integrality gaps are of interest to algorithm designers since they suggest limitations in certain techniques.

So why not just come up with another LP relaxation or switch to other techniques and move on?  Linear and convex programming have proven to be central to approximation algorithms; for many problems the integrality gap of a natural LP or SDP formulation is equal to the approximation ratio of the best algorithm as well as the hardness of approximation ratio.  This is just an empirical observation, but it means that proving an integrality gap may suggest much stronger consequences of an improved algorithm or lower bound.

There may be deeper and more rigorous reasons for this phenomenon.  For instance, assuming the unique games conjecture, it is known that the approximation ratio and inapproximability ratio for constraint satisfaction problems is equal to the integrality gap of a simple SDP relaxation (see Optimal Algorithms and Inapproximability Results for Every CSP? by Prasad Raghavendra)

Finally, integrality gaps represent unconditional lower bounds.  Usually, we need to rely on unproven assumptions (e.g. $P \neq NP$) if we want to make any progress in lower bounds, but for restricted models of computation, we can sometimes get away without it (see lecture notes by Luca Trevisan).  Integrality gaps, being purely geometric rather than computational, are one way of getting fairly powerful lower bounds without the baggage of extra assumptions.


Guessing a low entropy value in multiple attempts Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice draws a value $x$ from $\mu$, and then asks Bob (who knows $\mu$) to guess $x$.

What is the success probability for Bob? If he is only allowed one guess, then one can lower bound this probability as follows: the entropy upper bounds the min-entropy, so there is an element that has probability of at least $2^{-\varepsilon}$. If Bob chooses this element as his guess, his success probability will be $2^{-\varepsilon}$.

Now, suppose that Bob is allowed to make multiple guesses, say $t$ guesses, and Bob wins if one of his guesses is correct. Is there a guessing scheme that improves Bob's success probability? In particular, is it possible to show that Bob's failure probability decreases exponentially with $t$?

Bob's best bet is to guess the $t$ values with largest probability.

If you're willing to use Rényi entropy instead, Proposition 17 in Boztaş' Entropies, Guessing and Cryptography states that the error probability after $t$ guesses is at most
$$ 1 - 2^{-H_2(\mu)\left(1-\frac{\log t}{\log n}\right)} \approx \ln 2 \left(1-\frac{\log t}{\log n}\right) H_2(\mu), $$
where $n$ is the size of the domain. Granted, the dependency on $t$ is pretty bad, and perhaps Boztaş was focused on a different regime of the entropy.

For the Shannon entropy, you can try to solve the dual optimization problem: given a fixed failure probability $\delta$, find the maximal entropy of such a distribution. Using the convexity of $-x\log x$, we know that the distribution $\mu$ has the form $a,b,\ldots,b;b,\ldots,b,c$, where $a\geq b\geq c$, $a+(t-1)b = 1-\delta$, and $c = \delta-\lfloor\frac{\delta}{b}\rfloor b$. We have $t-1+\lfloor\frac{\delta}{b}\rfloor$ values that get probability $b$. Conditioning on $s = \lfloor\frac{\delta}{b}\rfloor$, we can try to find $b$ which minimizes the entropy. For the correct value of $s$, this will be an internal point (at which the derivative vanishes). I'm not sure how to get asymptotic estimates using this approach.


Minimum equivalent digraph with respect to sources and sinks Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$.
Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that:

For all pairs $u \in S, v \in T$ there is a path from $u$ to $v$ in $D$ if and only if there is a path from $u$ to $v$ in $D'$.

One application of this is representing a set family by a DAG.
For such a representation each source is a variable in the universe and each sink is a set in the set family, and a element u is in a set S if and only if there is a path from the vertex representing u to the vertex representing the set S.

Is this problem well known?
Is there a polynomial algorithm for this problem?

Let's assume that $D$ contains only sources and sinks, since the input can be translated into an equivalent such input easily.

Then, note that, in any solution $D'$ for $D$, each vertex $v$ corresponds to a biclique in the underlying undirected graph $G$ of $D$ (the biclique between all sources that reach $v$ in $D'$ and all sinks that are reached from $v$ in $D'$).

I conjecture that, if $D'$ is optimal, then it contains a vertex-cut that 1:1 corresponds to an optimal biclique covering of $G$. Then, any minimum vertex-cut in $D'$ corresponds to an optimal biclique covering in $G$. However, since BICLIQUE COVER (aka BIPARTITE DIMENSION) is NP-complete, your problem is unlikely to admit a polynomial-time algorithm unless my conjecture fails.

Note that, even if my conjecture holds, technically this argument does not prove NP-hardness of your problem, since the reduction is not a Karp- but a Cook reduction.


Inferring Cartesian position from a set of nodes where only distance is known I am attempting to resolve a problem of inferring Cartesian position from distance. I have a set of nodes arbitrarily but statically positioned on a 2-D plane. Every node is aware of its position relative to the other $n-1$ nodes. From this set of $n$ nodes, is it possible to infer each node's position ($x$,$y$) by choosing any node and using it as a basis?

For example, with two nodes, this is not possible, as the distance alone leaves open the possibility of the node not chosen as the basis for being located anywhere in the radial distance from the basis node.

With three nodes, it also seems impossible because the orientation can be flipped and is thus ambiguous based solely on distance. How many nodes are needed to unambiguously infer the position of the elements on a Cartesian plane?

I think that "Trilateration" should solve your problem.

In geometry, trilateration is the process of determinating absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In addition to its interest as a geometric problem, trilateration does have practical applications in surveying and navigation, including global positioning systems (GPS). In contrast to triangulation it does not involve the measurement of angles. ...


Interesting functions on graphs that can be efficiently maximized. Say that I have a weighted graph $G = (V,E,w)$ such that $w:E\rightarrow [-1,1]$ is the weighting function -- note that negative weights are allowed.

Say that $f:2^V\rightarrow \mathbb{R}$ defines a property of any subset of the vertices $S \subset V$.

  Question: What are some interesting examples of
  $f$s for which the maximization
  problem: $\arg\max_{S \subseteq
  V}f(S)$ can be performed in polynomial
  time?

For example, the graph cut function
$$f(S) = \sum_{(u,v) \in E : u \in S, v \not\in S}w((u,v))$$
 is an interesting property of subsets of vertices, but cannot be efficiently maximized. The edge density function is another example of an interesting property that alas, cannot be efficiently maximized. I'm looking for functions that are equally interesting, but can be efficiently maximized.

I'll let the definition of "interesting" be somewhat vague, but I want the maximization problem to be non-trivial. For example it should not be that you can determine the answer without examining the edges of the graph (so constant functions, and the cardinality function are not interesting). It should also not be the case that $f$ is really just encoding some other function with a polynomially sized domain by padding it into the domain $2^V$ (i.e. I don't want there to be some small domain $X$, and some function $m:2^S\rightarrow X$ known before looking at the graph, such that the function of interest is really $g:X\rightarrow \mathbb{R}$, and $f(S) = g(m(S))$ If this is the case, then the "maximization" problem is really just a question of evaluating the function on all inputs.)

Edit: Its true that sometimes minimization problems are easy if you ignore the edge weights (although not minimizing the cut function, since I allow negative edge weights). But I'm explicitly interested in maximization problems. It does not become an issue in natural weighted problems in this setting though.

Whenever $f(S)$ counts the number of edges $(u,v)$ satisfying some Boolean predicate defined in terms of $u\in S$ and $v\in S$, then what you wrote is just a Boolean 2-CSP. The objective function asks to maximize the number of satisfied clauses over all assignments to the variables. This is known to be NP-hard and the exact hardness threshold is also known assuming UGC (see Raghavendra'08).

There are many natural positive examples when you want to maximize over subsets of edges, e.g, Maximum matching is one example of a polynomial time problem in this case.


the number of rational points of a curve modulo 2 Consider the language $L=\{f, q\}$ - the number of solutions of equations $f(x,y)=0$ in $\mathbb{F}_q^2$ is equal to zero modulo $2$, where $q = 2^m$. Does $L$ belong to $P$? to $NP$? ($f$ is written as $\sum a_{ij} x^i y^j. $)

This language belongs to P. See Corollary 7.4 at
"Algorithmic theory of zeta functions
over finite fields"
by Daqing Wan. (There $n$ is the number of variables of a hypersurface, $d$ is the total degree of it, and  $q$ is the cardinality of the corresponding finite field.)


Lower bounds for the size of nondeterministic circuits It is known that the minimum size of $U_2$-circuits computing the parity function exactly equals $3(n-1)$. The lower bound proof is based on the gate elimination method.

Recently, I noticed that the gate elimination method works well also for nondeterministic $U_2$-circuits, and we can prove a $3(n-1)$ lower bound for the size of nondeterministic $U_2$-circuits computing the parity function.

(It means that nondeterministic computation is useless to compute parity by $U_2$-circuits and cannot reduce the size from $3(n-1)$. Thus, the minimum circuits don't change from the deterministic case.)

My questions are the following two:

(1) Is this a new result or a known result?

(2) More generally, are there some known results of lower bounds for the size of nondeterministic circuits (including formulas, constant depth circuits, and so on) with unlimited nondeterministic input bits (or, in other words, unlimited nondeterminism) for an explicit function?

Additional explanation (Nov 27, 2014)

In the second question, I intended that I would like to know especially whether
this is the first nontrivial lower bound for the size of nondeterministic circuits
(including formulas, constant depth circuits, and so on) with unlimited nondeterminism
for an explicit function or not.
I know there are some results if nondeterminism is limited, as follows.

[1] Hartmut Klauck: Lower Bounds for Computation with Limited Nondeterminism.
    IEEE Conference on Computational Complexity 1998: 141-

[2] Vikraman Arvind, K. V. Subrahmanyam, N. V. Vinodchandran:
    The Query Complexity of Program Checking by Constant-Depth Circuits.
    ISAAC 1999: 123-132

A partial answer to the second question:

exponential lower bounds for explicit functions for any class that contains 3-CNF do not translate into exponential lower bounds for unlimited nondeterminism, because one can transform any circuit of size $S$ into a nondeterministic 3-CNF of size $O(S)$ with non-determinism $S$,
even if you want non-determinism less than S, this is still doable if the function is computed by a $B_2$ formula (for example, parity), because one can split this formula of size $S$ into, say, $S/100$ pieces introducing $S/100$ new variables, and the resulting formula will be $O(S)$ size (though the constant in the $O()$ will be large),
for limited (but growing) nondeterminism one can, of course, use good old bounds (for example, Hastad's exponential lower bound $2^{n^{1/d}}$ for parity remains exponential if the nondeterminism is much less than $n^{1/d}$: just enumerate all possible bits for the nondeterminism and take a big OR of the resulting formulas).

A partial answer to the first question:

not known to me :) it would be interesting to see the proof (in particular, how can you substitute values for the existential variables).


Nontrivial problems solvable in constant time? Constant time is the absolute low end of time complexity. One may wonder: is there anything nontrivial that can be computed in constant time? If we stick to the Turing machine model, then not much can be done, since the answer can only depend on a constant length initial segment of the input, as farther parts of the input cannot even be reached in constant time.

On the other hand, if we adopt the somewhat more powerful (and more realistic) unit-cost RAM model, in which elementary operations on $O(\log n)$-bit numbers are counted as single steps, then we may be able to solve nontrivial tasks, even in constant time. Here is an example:

  Instance: Integers $n, k, l, d$, each given in binary format by $O(\log n)$ bits.

  Question: Does there exist an $n$-vertex graph, such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$?

Note that from the definition it is not even obvious that the problem is in NP. The reason is that the natural witness (the graph) may need $\Omega(n^2)$-bit long description, while the input is given by only $O(\log n)$ bits. On the other hand, the following theorem (see  Extremal Graph Theory  by B. Bollobas) comes to the rescue.

  Theorem:  Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree  $d$, if and only if one of the following conditions is satisfied:
    $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$,
   $1\leq 2d+2-n\leq k\leq l = d< n-1$
   $k=l=d=n-1.$

Since these conditions can be checked in constant time (in the unit-cost RAM model), the Theorem leads to a constant time algorithm in this model.

Question: What are some other nontrivial examples of constant time algorithms?

The paper Constant-Time Approximation Algorithms via Local Improvements by Nguyen and Onak gives a lot of examples of random constant time approximation schemes: Maximum Matching (the running time depends only on the maximum degree of the graph), Set cover, etc. The authors present a method to design such algorithms.


formalizing a statement about the expressive power of programming languages wrt divergence In the Coq'Art book the authors mention in passing that any language that can calculate all computable functions must also be able to express diverging computations.
Or in other words, there can be no Coq' that is Turing-complete that maintains the guarantee that all computations describable in that language terminate.

How would I go about formalizing this statement? I feel it's a simple corollary to the Halting problem, but I don't know enough about formal semantics of programming languages to express or prove this.

Let us take a somewhat simplified view of a programming language as a mapping $C$ (the compiler) from finite strings of characters (source code) to descriptions of Turing machines (machine code). A description of a Turing machine is just a finite string of characters of a certain kind. And since finite strings of characters are computably isomorphic to natural numbers (we can computably encode string as numbers and vice versa), we can pretend that both source code and Turing machines are described by numbers.

Under this view a programming language $C$ is a partial map from natural numbers to natural numbers which accepts a number $n$ (the source code) and either diverges or returns a number $C(n)$ (the "compiled" Turing machine). It makes sense to require that $C$ is a computable map, i.e., that there is in fact a Turing machine that calculates it, otherwise magic is required to understand the programming language.

Note that I can enumerate all possible outputs of $C$. I simply try $C$ on every input in parallel by dovetailing, and whenever any parallel copy gives a result, I enumerate it. Let $f : \mathbb{N} \to \mathbb{N}$ be an enumeration of all outputs of $C$.

Let $\phi_k$ be the partial computable map that is computed by the Turing machine described by the number $k$.

We now come to the crux of the matter. Suppose $f$ enumerated precisely the total computable maps, i.e., $\phi_{f(n)}$ is a total computable map for all $n \in \mathbb{N}$, and for every computable map $g$ there is $n$ such that $g = \phi_{f(n)}$. Consider the computable map $d(n) = 1 + \phi_{f(n)}(n)$. This map is total because $\phi_{f(n)}$ is total for every $n$. There is $j$ such that $\phi_{f(j)} = d$, but then $\phi_{f(j)}(j) = d(j) = 1 + \phi_{f(j)}(j)$, contradiction.

The conclusion is that $f$ cannot possibly enumerate precisely the total computable maps. Therefore it either misses out some total maps, or enumerates some partial ones.


Why does this cut elimination procedure terminate (contraction case)? In Melliès’ survey Categorical Semantics of Linear Logic, a cut elimination procedure for intuitionistic linear logic is given which includes the following case:

3.9.3 Promotion vs. contraction
The proof
$$
\displaystyle\frac{
\displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion}
\qquad
\displaystyle\frac{\displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B}}{\Upsilon_1 , !A , \Upsilon_2 \vdash B} \text{ Contraction}
}{
\Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B
} \text{ Cut}
$$
is transformed into the proof
$$
\displaystyle\frac{
\displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion}
\qquad
\displaystyle\frac{
\displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion}
\qquad
\displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B}
}{
\Upsilon_1 , !A , !\Gamma , \Upsilon_2 \vdash B
} \text{ Cut}
}{
\displaystyle\frac{\Upsilon_1 , !\Gamma , !\Gamma , \Upsilon_2 \vdash B}{\Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B} \rlap{\;\text{ Series of Contractions and Exchanges}}
} \text{ Cut}
$$

Why is this a valid inductive step? Neither the size of the cut formula nor the sizes of the derivations are decreasing. (In the transformed proof, the right branch of the lower cut is potentially larger after inductively eliminating the upper cut.) So it's not clear why this procedure should terminate.

I extend what I wrote as a comment. As there is a great number of cases in the proof, I only give an idea of why this transformation terminates. The short answer is:

In the case promotion vs contraction, after the transformation, the number of contractions in the part of the proof containing cuts has decreased by one.

To go a bit more into details, I would say that you were mistaken because you thought that either the number of cuts or the size of the proof should decrease in order to ensure termination. However, termination can be proven by looking at other parameters of the proof.

If you want to prove termination, you only have to show that each rule will be applied a finite number of time. You can prove that the transformation rule promotion vs contraction will be applied at most m times, where m is the number of contractions in your initial proof. To prove this, you just have to observe that no rule introduces a new contraction in proof tree. And this one decreases the number of contraction by one. You can do this trick for any other rules "promotion vs sthg" to prove that this one will be applied only a finite number of time.


Number of mincuts of a graph without using Karger's algorithm We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$.

I was wondering if we could somehow prove this identity by giving a bijective (rather injective) proof from the set of mincuts to another set of cardinality $n \choose 2$. No specific reasons, its just a curiosity. I tried doing it on my own but so far have not had any success. I would not want anyone to squander time over this and so if the question seems pointless I would request the moderators to take action accordingly.

Best
-Akash

The $\binom{n}{2}$ bound I think was originally proven by Dinitz, Karzanov and Lomonosov in 1976, in "A structure for the system of all minimum cuts of a graph".  Perhaps you can find what you're looking for in this paper, but I'm not sure if it's online.


Major advance for measurement based quantum computing? http://arxiv.org/abs/1211.3405

The Measurement Based Quantum Computing Search Algorithm is Faster than Grover's Algorithm

If this recent paper is true, it seems like a major advance for measurement based quantum computing.  The claim is based on numerical evidence, rather than a formal proof.  Is this as important/revolutionary as I think it is?

This makes me wonder: Is there a known relation between the speed of gate-based quantum computing and the speed of measurement-based quantum computing?

A paper which makes strong claims ought to be sufficiently clearly written for readers to  check those claims. I don't find the current (http://arxiv.org/pdf/1211.3405v2.pdf) version of this paper expresses its results clearly enough to make a concrete assessment.

But if it were, I'd want to check:

a) whether the quantum part of the algorithm solely consists of Pauli measurements on a cluster state.

Such a measurement-based quantum computation can be simulated using polytime classical processing (due to the Gottesman-Knill theorem), and hence one would have a solely classical superfast search algorithm.

b) whether the oracle used might be of a different type to the oracle in Grover's algorithm.

The oracle in Grover's algorithm has the property that it must recognise the target string, but, crucially, it does not need to know this string in advance, or be able to calculate that target string in polytime (see Nielsen and Chuang chapter 6 for a discussion of this).

Unless P=NP, an oracle which knows the target string needs to be more powerful than one which merely recognises it (consider a search for a solution of an NP-hard problem). I'd want to check whether the oracle here is of the "recognising" or "knowing" kind. If it is the second, then the extra computational power in the oracle might, on its own, explain any exponential improvement reported.


Advice for attending my first TCS conference I will be attending my first computer science conference and after reading the advice for how to improve conferences I noticed the several suggestions were about grad students attending their first conference.

What advice do you have for a grad student attending his first conference and what should his focus be.

Talk to people, even if they are scary big names.
Attend all the keynote/invited presentations.
Attend the talks most relevant to you.
Don't be afraid to ask questions.
Attend the social events, meet other graduate students, have fun.
Talk enthusiastically about your research.
Make sure you have a 1 minute pitch describing your work, plus a 5 minute description, and also be prepared to enter into a more detailed discussion.
Ask people about their research.   Simply asking what are you working on? will get the conversation started.
Be open to possible collaborations, and follow up after the conference.


Can a natural graph problem be universally hard? Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to  any  polynomial-time recognizable graph class? To avoid degenerated cases, let us consider only  dense  graph classes, in which   the number of non-isomorphic $\leq n$-vertex graphs grows exponentially with $n$.

 Notes:

(1) Both a "yes" or a "no" answer would be quite interesting. If the answer is yes, then we would have a natural  $\mathsf{NP}$-complete graph property that could be called  universally hard,  because it preserves hardness even when  restricted to any reasonable graph class.  If the answer is no, it would mean that every natural $\mathsf{NP}$-complete graph property can be made easy on some nontrivial graph class.

(2) It is important to consider only polynomial-time recognizable graph classes, to exclude that the hardness of the property is simply shifted to the class.
For example, 3-COLORABILITY becomes trivial when restricted  to 3-colorable graphs.

The definition of "natural" is a bit fuzzy, but there's a trivial reason the answer here is likely "no". Suppose to the contrary that there is such a problem, $P$. If $P$ only acts on the first component of the provided graph, then $P$ is easy on the class of graphs where the first component is an instance of $P$ and the second component encodes a certificate of $P$ holding on the first component. Further, this class of graphs is polytime recognizable. Indeed, the same holds true if we can designate a portion of the graph as a "this is a certificate and not part of the problem component", in the sense that we can sneak this certificate in without affecting the true answer.

Most "natural" problems, as far as I can tell, allow for the designation of such a piece of the graph. Here are a few examples

Max Clique: just ensure that the certificate portion of the graph does not have a large clique (eg. encode it using a matching)
Hamiltonian Path: the tail node is replaced by a certificate graph which has an easy-to-find Hamiltonian path of its own
Hamiltonian Circuit: same as Hamiltonian path except some designated vertex is replaced with a certificate graph containing a Hamiltonian cycle
Max Cut: this doesn't affect the solution as long as there are no edges to the rest of the graph, so we just ensure that the max cut here is easy to find (eg. we encode using a matching)
Vertex cover: the certificate is again encoded by a matching

We ensure that the certificate portion of the graph is designated as such, so to not lose it in the rest of the graph (though designating them implicitly via the graph structure is probably easy enough for most "natural" problems).

Since NP-complete problems cannot be sparse unless $P=NP$ (Mahaney's theorem), neither can this construction, satisfying your non-triviality constraint.


Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$? I need to use the following well-known result in my paper:

  Let $X$ be a set of $n$ points in $\mathbb{R}^d$. Then $(X,\ell_2^d)$ embeds isometrically in $\ell_p^\binom{n}{2}$ for all $p \geq 1$.

What is the best reference to cite for this? I found a result which is nearly identical (but doesn't include the $\binom{n}{2}$ dimension bound) in some lecture notes from Michel Goemans, but I'm (a) unsure if I can cite lecture notes in a scientific publication, and (b) still in need of an $O(n^k)$ bound on the dimension.

This paper by Keith Ball seems to be what you are looking for:

  Ball, Keith. "Isometric embedding in $\ell_p$-spaces."
  European Journal of Combinatorics 11.4 (1990): 305-311.

Link to the paper here:
https://www.sciencedirect.com/science/article/pii/S019566981380131X


NP-hardness proof: looking for some good restricted np-hard problems To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can be used for the reduction, but in practice, some of the problems are more easily reduced than others.

For instance, 3-SAT is usually a better choice for constructing a reduction than SAT because the former one is more restricted than the latter one, 3-partition is usually an easier choice than bin packing, ...

One way to find such "good" problems for the reduction is to do a statistical analysis over the existing reductions. E.g., one can shape all the pairs of from -> to reductions of the book Computers and Intractability: A Guide to the Theory of NP-Completeness
(or other resources)
and draw a histogram of the problems in the from set.
Then we can find out which problems are more commonly used for reductions.

I wonder if such a statistical analysis makes sense at all. Has such a research been already conducted or not? If not, what is your guess about the most commonly used problems for
reductions.

The reason I am asking this question is that I have already done a few proofs of NP-hardness, but almost all of them rely on reduction from the same problem (3-partition).
I am looking for other options to use in my proofs.

I don't know if there is a machinery way to do this, but my little personal experience works as follows.

I try to provide a polynomial time algorithm for a problem. In those tries usually I can see there are some restricted versions of problem which are polynomial time solvable. I also will understand what part of my algorithm was handwaving for original problem. I can compare this two cases (difference between restricted versions and the general one also the part of an algorithm which was hard to improve). By comparing those two cases usually it's possible to guess how does the problem bottleneck looks like. So we can find a related hard problem. Usually providing an algorithm for a problem is hard job, and needs good knowledge about a problem. After we get this knowledge about the problem we can have many different ideas to tackle problem in different scenarios (not just hardness results).

P.S: If your proof relays on a particular problem, I think it's because that problem is very close to your work, so don't blame yourself.


What technique is used to implement type checking for CoC? I am studying David Christiansen's tutorial on implementing a dependently typed language, where it says:

Typed normalization by evaluation is far from the only way to implement conversion checking for dependent types. Indeed, normalization by evaluation has a number of characteristics that make it only suitable for certain theories: it η-expands expressions as many times as possible, but η-expansion is not valid for some theories (including Coq’s Calculus of Constructions)

May I have a reference to why η expansion is invalid for CoC? Is there some "moral" by which one can see the rules of CoC and realise that η expansion is invalid?
The rules for implementing CoC in ATAPL Chapter 2 look to my naive eye like NBE (Normalization by Evaluation). The rules for CoC are given as an extension to the equivalence rules of LF, augmented with extra rules that govern how Prf (the encoding mechanism of Pi types) and Prop interact. The rules QA-NABS-1, QA-NABS-2 seem to be implementing η expansion for stuck terms? Why do these rules not describe NBE?
Is there a name for the rules given in ATAPL to implement type checking for CoC? They seem ad-hoc to me, and I don't understand how I would come up with them. I would appreciate a reference to the framework that is used to create the reduction rules for CoC (for clarity, by a framework, I refer to ideas such as NBE or hereditary substitution)

I have included the rules for CoC as given in ATAPL, Chapter 2, for reference:

May I have a reference to why η expansion is invalid for CoC?

It's not invalid. It's up to choice whether $\eta$-conversion for functions (or other types) is included. The original CoC paper seems to omit it, but as you see ATAPL includes it. I'm not certain, but $\eta$ may have been omitted from the original source because it was difficult to handle in the strong normalization arguments, back in the days. Nowadays normalization proofs are more likely to be based on NbE themselves, and have no issues with $\eta$-rules. Modern Coq definitely has $\eta$ for functions, and it is generally considered a highly useful basic feature.

The rules QA-NABS-1, QA-NABS-2 seem to be implementing η expansion for stuck terms? Why do these rules not describe NBE?

They do specify $\eta$ for functions. It's not really NbE though. ATAPL only describes how to compare weak head normal forms for conversion in an iterated fashion, it does not say how to efficiently compute to whnf. The essential part of NbE is the separation of syntax and values; this is missing from the ATAPL exposition.

Indeed, normalization by evaluation has a number of characteristics that make it only suitable for certain theories: it η-expands expressions as many times as possible

This is incorrect. NbE is not necessarily type-directed, and does not necessarily include $\eta$-expansion. If you look at QA-NABS-1, QA-NABS-2 and the other rules in ATAPL, they can be adapted to a conversion checking algorithm on NbE values, which is a) purely syntax-directed b) does not require $\eta$-expansion in evaluation c) decides $\eta$-conversion for functions.

Is there a name for the rules given in ATAPL to implement type checking for CoC? They seem ad-hoc to me, and I don't understand how I would come up with them.

I'm not aware of any rigorous and generic way for specifying conversion checking algorithms. I would summarize the rules of thumbs as follows.
The specification of values is obtained from the specification of syntax by replacing binders with metalanguage functions or closures. Evaluation goes from syntax to values and performs $\beta$-reduction (but not necessarily $\eta$-conversions). Then, conversion checking can be implemented on values, proceeding purely structurally, except where we want syntax-directed $\eta$-checking in the manner specified in ATAPL.


How is rebalancing of DHTs handled in case of failure or addition of new node? I am reading about Dynamo-like DHT data storage applications like cassandra and project voldemort. I was curious, say:

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

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

Thanks

That's the whole purpose of consistent hashing. When you add a new node, you compute its hash key, find the two nearest neighbors on the hash ring and link the node in between them. When the hash function has good statistics, you expect a uniform distribution of hash keys, resulting in good load balancing. You don't have to redistribute the existing keys. Removal of nodes works analogously.

In summary, there's no global coordination to achieve even coverage of the key space. That is an emergent property of the hash function. The only coordination is local in the form of linking and unlinking nodes into the circular list of nodes on the ring.

Incidentally, if nodes were only ever added and not deleted, low-discrepancy sequences would be a better choice than hashing (such sequences are particularly simple in one dimension). But in the real world, nodes are added and deleted in an unpredictable pattern. Hashing is better able to cope with those conditions; the trade-off is worse discrepancy in the monotone growth case. Using a low-discrepancy sequence would also require new nodes to coordinate with a key manager, though no existing keys need to be redistributed.


Generalization bounds for multiclass learning when the output is vector space? There are plenty of results for muli-class learning with with fixed discrete labels:
$$
\text{Standard multi-class classification:}
\begin{cases}
f: X \rightarrow Y_{index} = \{1, 2, 3, ..., k \}, \\ s.t. X \subset \mathbb{R}^{d_x}
\end{cases}
$$

I was wondering if there are any results which study multi-class learning with (countable, possibly finite) vector-valued outputs.

$$
\text{Vector-output multi-class classification:}
\begin{cases}
f: X \rightarrow Y_{vector} = \{y_1, y_2, y_3, ..., y_k \}, \\
s.t.
X \subset \mathbb{R}^{d_x},
y_i \in  \mathbb{R}^{d_y}
\end{cases}
$$

One may suggest that this is another problem: metric-learning between $X$ and $Y$ space:
$$
\text{Standard metric-learning problem:}
\begin{cases}
f: X, Y \rightarrow [0,1], \\
s.t.
X \subset \mathbb{R}^{d_x},
Y \subset  \mathbb{R}^{d_y}
\end{cases}
$$

However all the results I came across in the metric-learning study the functions on one single vector space (as in unsupervised metric learning). In addition, vector-output multi-class classification is much more restricted (easier to learn?) than metric learning, since in what I am asking, the number of possible output vectors is fixed (unlike metric learning).

Sounds like you're trying to learn a map from vector space $X$ to vector space $Y$. The first thing that comes to mind is regression, which is a map from $X$ to $\mathbb{R}$. You can of course perform multiple regressions in parallel -- one for each dimension of $Y$ -- to learn a map from $X$ to $Y$. This has the shortcoming of ignoring any "interaction" or dependencies between the labels. You could first perform PCA on both the inputs in $X$ and the outputs in $Y$, and learn a map from the principal vectors of the input to the principle vectors of the output.

Another idea -- one that I'm particularly fond of -- is to perform Lipschitz extension. This assumes that $X$ and $Y$ are both metric spaces with known metrics. (A much more general setting than vectors spaces!) See the pioneering paper of von Luxburg and Bousquet, for example:
http://www.jmlr.org/papers/volume5/luxburg04b/luxburg04b.pdf


Are research papers hard to read? This question may not suit to here, but I couldn't find a better place to ask (it was closed in SO).

I find research papers on computer science hard to understand. Of course the subjects are complicated. But after I understand a paper usually I can tell it to someone in simpler terms, and make them understand. If somebody else tells me what is done in that research I understand too.

I think the best example that I can tell here is: I have tried to understand SIFT paper for a long time, and I found a tutorial while googling, in a couple of hours I was ready to implement the algorithm. If I was to understand the algorithm from the paper itself it might have taken a couple of days I think.

My question is: is it only me who finds research papers this hard to understand? If not how do you deal with it? What are your techniques? Can you give tips?

Unfortunately, research conferences generally do not place a premium on writing for readability. In fact, sometimes it seems the opposite is true: papers that explain their results carefully and readably, in a way that makes them easy to understand, are downgraded in the conference reviewing process because they are "too easy" while papers that could be simplified but haven't been are thought to be deep and rated highly because of it. So, if you rephrase your question to add another word, is it not just you who finds some research papers unnecessarily hard to read, then no, it is not. If you can find a survey paper on the same subject, that may be better, both because the point of a survey is to be readable and because the process of re-developing ideas while writing a survey often leads to simplifications.

As for strategies to read papers that you find hard, one of them that I sometimes use is the following: read the introduction to find out what problem they're trying to solve and some of the basic ideas of the solution, then stop reading and think about how you might try to use those ideas to solve the problem, and then go back and compare what you thought they might be doing to what they're actually doing. That way it may become clearer which parts of the paper are just technical but not difficult detail, and which other parts contain the key ideas needed to get through the difficult parts.


What do we know about provably correct programs? The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in which you have to give a formal proof that your code works correctly.

I believe the term is a 'certifying compiler' (I found it here): a compiler compiling a programming language in which one not only has to write the code, but also state the specification of the code and prove that the code adheres to the specification (or use an automated prover to do so).

While searching the internet, I only found projects that either use a very simple programming language or failed projects that try to adapt modern programming languages. This leads me to my question:

  Are there any certifying compilers implementing a full-blown programming language, or is this very hard/theoretically impossible?

Additionally, I've yet to see any complexity class involving provable programs, such as 'the class of all languages decidable by a Turing machine for which a proof exists that this Turing machine halts', which I shall call $ProvableR$, as an analogue to $R$, the set of recursive languages.

I can see advantages of studying such a complexity class: for instance, for $ProvableR$ the Halting problem is decidable (I even conjecture $ProvableRE$ defined in the obvious way would be the largest class of languages for which it is decidable). In addition, I doubt we would rule out any practically useful programs: who would use a program when you can't prove it terminates?

So my second question is:

  What do we know about complexity classes which require their containing languages to provably have certain properties?

"Certifying compiler" usually means something slightly different: it means that you have a compiler which can prove that the machine code it emits correctly implements the high-level semantics. That is, this is a proof that there are no compiler bugs. The programs that people give to the compiler can still be wrong, but the compiler will generate a correct machine code version of the wrong program. The biggest success story along these lines is the CompCert verified compiler, which is a compiler for a large subset of C.

The Compcert compiler itself is a program with a correctness proof (done in Coq), which guarantees that if it generates code for a program, it will be correct (with respect to the operational semantics of assembly & C that the CompCert designers used).  The effort to machine-check these things is quite large; typically the correctness proof will be anywhere from 1x to 100x the size of the program you are verifying. Writing machine-checked programs and proofs is a new skill you have to learn -- it's not mathematics or programming as usual, though it depends on being able to do both well. It feels like you are starting from scratch, like being a novice programmer again.

There are no special theoretical barriers to this, though. The only thing along these lines is the Blum Size theorem that for any language in which all programs are total, you can find a program in a general recursive language which will be at least exponentially larger when programmed in the total language. The way to understand this result is that a total language encodes not just a program, but also a termination proof. So you can have short programs with long termination proofs. However, this doesn't really matter in practice, since we're only going to ever write programs with manageable termination proofs.

EDIT: Dai Le asked for some elaboration of the last point.

This is mostly a pragmatic claim, based on the fact that if you can understand why a program works, then it's unlikely that the reason is  some vast invariant millions of pages long. (The longest invariants I've used are a few pages long, and boy do they make the reviewers grumble! Understandably so, too, since the invariant is the reason the program works stripped of all the narrative that helps people understand it.)

But there are also some theoretical reasons, as well. Basically, we don't know very many ways to systematically invent programs whose correctness proofs are very long. The main method is to (1) take the logic in which you prove correctness, (2) find a property which can't be directly expressed in that logic (consistency proofs are the typical source), and (3) find a program whose correctness proof relies on a family of expressible consequences of the inexpressible property. Because (2) is inexpressible, this means that the proof of each expressible consequence must be done independently, which lets you blow up the size of the correctness proof. As a simple example, note that in first-order logic with a parent relation, you can't express the ancestor relation. But $k$-ancestry (ancestry of depth $k$) is expressible, for each fixed $k$. So by giving a program that uses some property of ancestry up to some depth (say, 100), you can force a correctness proof in FOL to contain proofs of those properties a hundred times over.

The sophisticated take on this subject is called "reverse mathematics", and is the study of which axioms are required to prove given theorems. I don't know that much about it, but if you post a question on its application to CS, and I'm sure at least Timothy Chow, and probably several other people,  will be able to tell you interesting things.


First order satisfiability that doesn't have finite models We know from Church's theorem that determining first order satisfiability is undecidable in general, but there are several techniques we can use to determine first order satisfiability. The most obvious is to search for a finite model. However, there are a number of statements in first order logic that we can demonstrate have no finite models. For instance, any domain in which an injective and non-surjective function operates is infinite.

How do we demonstrate satisfiability for first order statements where there aren't finite models or the existence of finite models is unknown? In automated theorem proving we can determine satisfiability several ways:

We can negate the sentence, and search for a contradiction. If one is found, we prove first order validity of the statement and thus satisfiability.
We use saturation with resolution and run out of inferences. More often than not, we will have an infinite amount of inferences to make, so this isn't dependable.
We can use forcing, which assumes the existence of a model and also the consistency of the theory.

I don't know of anyone implementing forcing as a mechanized technique for automated theorem proving, and it doesn't look easy, but I'm interested if it's been done or attempted, as it's been used to prove independence for a number of statements in set theory, which itself has no finite models.

Are there other techniques known for searching for first order satisfiability that are applicable for automated reasoning or has anyone worked on an automated forcing algorithm?

Here's an amusing approach by Brock-Nannestad and Schürmann:

Truthful Monadic Abstractions

The idea is to try to translate first-order sentences into monadic first-order logic, by "forgetting" some of the arguments. Certainly the translation isn't complete: there are some consistent sentences which become inconsistent after translation.

However, monadic first order logic is decidable. One can therefore verify if the translation $\overline F$ of a formula $F$ is consistent:

$$ \overline F\not\vdash\bot$$

can be checked by a decision procedure, and implies

$$ F\not\vdash\bot$$

Which implies that $F$ has a model, by the completeness theorem.

This theme can apply somewhat more generally: identify a decidable sub-logic of your problem, then translate your problem into it, in a way that preserves truth. In particular modern SMT solvers like Z3 have gotten astonishingly good at proving satisfiability of formulas with quantifiers (by default $\Sigma^0_1$, but can perform well on $\Pi^0_2$ formulas).

Forcing seems to be far out of reach of automated methods at the present.


Is the unbounded fan-in model realistic? Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates?

As I understand, standard silicon ASICs are made of so-called cells where the number of input signals in the largest cells is small (e.g. never exceeds a fan-in of 100).

Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables $n$ (in the definition of $\mathsf{AC}$ for instance) .


How to talk about theory I realize this might be a contentious question, but this seemed like the right place to ask. Please redirect me if not.

The background is that I am a "practitioner" (PhD student, I don't study CS theory) but I have a reasonable foundation in undergraduate algorithms and math. Nevertheless, discussions with theorists are usually very surface-level, as if they're afraid to use mathematical terms with me in case I get scared. In reality, I'm perfectly comfortable with and interested in theory, but I'm just not used to discussing it so I probably don't always use terms that would flag me as "theorist". I find that the direct approach ("please tell me the details") doesn't always work, particularly if the theorist in question has assumed a condescending tone that sets a high bar for expertise (this happens often).

As theorists, if you filter people in this way, do you have recommendations for how a practitioner can avoid being "flagged" by your filter?

You may be working with rude elitists, but from my experience, being reluctant to explain technical details depends more on the context than on the person I am talking to. I would usually avoid giving technical details of a proof/algorithm over lunch or in the corridor even if my interlocutor were Alan Turing himself. The reason is that details heavily depend on the choice of notations and on hand-crafted concepts introduced to smooth a claim. Also, because everyone understands things differently and I do not have a generic way to explain a concept, I always have to adapt to my interlocutor (that is why giving technical details in a research presentation is so hard by the way).

One exception is if my interlocutor has worked closely with me on this kind of problem and then, I know that we can use this common gibberish that only we understand because we grow into it together after several white board sessions (or before an urgent deadline).

Another exception is if after giving a crude overall scheme of the proof without details, my interlocutor asks a precise question showing he has seen a particular hard part of the proof that I have been intentionally hiding from him in order to simplify the presentation. In that case, we would naturally open the Pandora box and go together into the heart of the proof, layer by layer... and usually end up on a white board because at some point, we again need this common gibberish that only fit us and this problem.

There are several morals with my already too long story:

Do not depreciate yourself because you are not actively working in theoretical computer science. Most people will not care about your precise background as long as you show that you are curious about their work.
When people are vague about a proof/concept, stay alert and try to guide the conversation by asking a precise question showing your understanding and thus helping your interlocutor to choose which part of the proof he should develop first. This is obviously quite hard and unpredictable because you may not be able to give relevant comments on the go (this happens to everyone even to "theorists"), but if you manage it, then you will likely end up with a very enlightening discussion.
Even "theorists" need time to reload the details of a proof in their head before being able to clearly explain it. Make an appointment by explicitly asking that you are interested in the technical details of X. This will allow for time for your interlocutor and you to prepare, and will ease the discussion. Make sure to have a white board or a piece of paper during the discussion so that you can really go into details.


PhD Development; Literature Review Tactics Not sure if correct area, but here goes.

Starting a PhD in Trust and Reputation Management in Communications networks (lots of graph theory, probabilistic analysis, etc), and have lots of reading ahead of me.

Can anyone advise the best ways to manage academic reading and what I should be noting for literature review/progress reports, etc?

I'm a younger researcher so I have no personal advice, but I have found this method by Michael Nielsen quite effective.

One unusual but very useful style was to set a goal like reading 15 papers in 3 hours. I use the term "reading" here in an unusual way. Of course, I don't mean understanding everything in the papers. Instead, I'd do something like this: for each paper, I had 12 minutes to read it. The goal was to produce a 3-point written LaTeX summary of the most important material I could extract: usually questions, open problems, results, new techniques, or connections I hadn't seen previously. When time was up, it was onto the next paper. A week later, I'd make a revision pass over the material, typically it would take an hour or so.
I found this a great way of rapidly getting an overview of a field, understanding what was important, what was not, what the interesting questions were, and so on. In particular, it really helped identify the most important papers, for a deeper read.
For deeper reads of important papers or sections of books I would take days, weeks or months. Giving lectures about the material and writing LaTeX lecture notes helped a lot.

In particular, I found his opinion on identifying useful material mirrored my own:

Most material isn't worth spending a lot of time on. It's better to spend an hour each seriously reviewing 10 quantum texts, and finding one that's good, and will repay hundreds of hours of study, than it is to spend 10 hours ploughing through the first quantum text that looks okay when you browse through it in the library. Understanding mathematics deeply takes a lot of time. That means effort spent in identifying high quality material is often repaid far more than with (say) a novel or lighter non-fiction.

The whole comment is definitely worth the read.
As far as managing your materials go, I have yet to find an application as useful as Papers. It hooks into your institution's library proxy and allows you to get at licensed content quickly without VPNing in to campus. It's also great for organizing papers by topic and searching over your library via author, title, conference, etc. Unfortunately it's Mac OS X specific. I'm curious if anyone has experience with alternatives on other operating systems.


Grover's algorithm, M out of N, when M is large The more general version of Grover's algorithm searches for one of $M$ entries that match a criterion, out of $N$ total entries.

I have seen it written that this takes $O(\sqrt{N/M})$ iterations, to find one of the $M$ matching entries, with good probability.
(e.g. on wikipedia )

Is this still valid when $M$ is large, say $M=N/2$ ?  In that case we get $O(1)$ iterations?

When $M=N/2$, you don't need a quantum algorithm; a classical algorithm can find a matching entry in $O(1)$ iterations on average (expected running time), just by randomly guessing an item and checking if it matches.  Grover's algorithm is also randomized, so the quantum computer offers no advantage in asymptotic running time for that case.


Fitting minimum number of rectangles of width/height 1 into a 2D grid Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied
and you need to put the minimum number of non-overlapping rectangles of any size w x h where w = 1 or h = 1 (i.e. "square segments") such that all unoccupied squares are covered and each rectangle covers only unoccupied squares.

For example, for the grid

..###
.....
..###
.#...

the solution would be 4, since you can cover all the unoccupied squares (denoted by '.') with 4 such rectangles as follows:

12###
12333
12###
1#444

I tried to come up with a polynomial algorithm or prove that this problem is NP-hard, but without success. Can anyone help me to prove / disprove that this is problem is in P, or point me to some related work / problems?

Ok, so you have a polygon $P$ with integer-length axis-parallel sides and possibly with holes (the shape you want to cover) and you want to partition it into as few $1\times a$ or $b\times 1$ rectangles as possible. At first I thought you wanted the minimum partition into rectangles of arbitrary shapes, which has a known polynomial time solution involving a reduction to maximum independent sets in bipartite graphs. But I think this one is also polynomial, via a different reduction to the same problem.

Draw a graph $G$ that has a vertex for every unit-length line segment that separates two squares of $P$, and that has an edge connecting the vertices for every two perpendicular line segments that share an endpoint. Then the partitions of $P$ into unit-width rectangles correspond one-for-one with independent sets of $G$. If a vertex $v$ of $G$ corresponds to a line segment $s$, then $v$ belongs to a given independent set exactly when the two squares separated by $s$ belong to the same rectangle as each other in the corresponding partition.

Under this correspondence, we have the equation $R=S-I$ where $R$ denotes the number of rectangles in a given partition, $S$ denotes the number of squares in $P$, and $I$ denotes the cardinality of the independent set; this is easy to see by induction on $I$, by removing one independent set element at a time. Since $S$ is fixed, minimizing $R$ is the same as maximizing $I$, and the optimal partition of $P$ corresponds to the maximum independent set of $G$. But $G$ is a bipartite graph (horizontal segments are adjacent only to vertical segments and vice versa) so its maximum independent set may be found in polynomial time (see König's theorem on Wikipedia).


"How much diagonal" a matrix is I have a (biological) computational system that outputs squared matrices. These matrices will sometimes have a tendency to be diagonal-like, with higher values at and around the diagonal.

I would like to have some summary measure on how "much diagonal" a matrix is, so that I can batch process hundreds of outputs and score them on how much the higher entries cluster in and around the diagonal.

Any ideas of some standard approach that I can generalise?

Thanks !
JL

You might consider as a first approximation:

$\sum_i((A[i,i])^2) \over \epsilon + \sum_{i \ne j}((A[i,j])^2)$

(The epsilon value is there to avoid divide-by-zero errors).

Having said that, you might also consider the question of whether the matrices are tri-diagonal. A matrix is often converted to tri-diagonal form before computing its eigenvalues.

Another measure of "diagonalness" could be the sum of the absolute value of the differences between the eigenvalues (arranged in sorted order) and the diagonals (arranged in order of largest diagonal-entry first). This is great if you already know the eigenvalues. In fact, it is probably a better measure. However, in terms of efficiency, I would probably prefer the sum of squares ratios.


Problems in $\mathsf{BPP}$ not known to be in $\mathsf P$? What problems are known to belong to $\mathsf{BPP}$ but not known to belong to $\mathsf P$?

More precisely, I am interested in independent problems, that is whose derandomizations are not known to be equivalent. For instance, it is known that derandomizing PIT and multivariate polynomial factorization are equivalent and I would count them as only one problem.

The motivation of my question is that it is common to say that "there are few problems in $\mathsf{BPP}$ not known to be in $\mathsf{P}$", but I was not able to find a list of them. In particular, if I have to cite problems in this category, I usually cite the factorization of univariate polynomials over finite fields, or the factorization of multivariate polynomials. I suppose that there exist examples that are not related to polynomial factorization, for instance in other domains such as graph theory or formal language theory.

P.S.: I find curious that a similar question does not exist on this website yet. My apologies if I simply did not find it (or them)!

If you're asking for independent problems, how about:

  Find a prime in the interval $[N, 5N/4]$,
  Find two primes whose product is in the interval $[N, 9N/8]$,
  Find three primes whose product is in the interval $[N, 17N/16]$,
  Find four primes whose product is in the interval $[N, 33N/32]$,
  Find five primes whose product is in the interval $[N, 65N/64]$,
  $\ldots$.

It's overwhelmingly likely that if you actually had a polynomial algorithm to solve the first of these, you would have a polynomial algorithm for all of them. But I don't see how to formally reduce any of these to any of the others. Of course, the problem

  Find a prime in the interval $[N, N+\log^{17} N ]$

solves all of these.


Natural theorems proven only "to high probability"? There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing.

Question: Are there any natural mathematical "theorems" where a randomized proof is known but a deterministic proof is not?

By a "randomized proof" of a statement $P$ I mean that

There is a randomized algorithm that takes an input $n > 0$ and if $P$ is false produces a deterministic proof of $\neg P$ with probability at least $1-2^{-n}$.
Someone has run the algorithm for, say, $n = 100$, and not disproved the theorem.

It's easy to generate non-natural statements that fit: just pick a large instance of any problem where only an efficient randomized algorithm is known.  However, although there a lot of mathematical theorems with "lots of numerical evidence", such as the Riemann hypothesis, I don't know of any with rigorous randomized evidence of the above form.

$
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\maj}{maj}
$
This is not an example of what you are asking for, but it suggests how such an example can come about. Some combinatorial identities can be encoded as identities about polynomials of bounded degree $d$. If the polynomials are univariate, to prove the identity it is enough to verify it on $d+1$ points. However, if the polynomials are multivariate, and the degree is at least moderately large, the Scwartz-Zippel lemma may be the only practical way to verify the identity.

For an example of the univariate case, check this article by Zeilberger, resolving a question of Knuth. He proves a statement about statistics of permutations. For a permutation $\pi \in S_n$, let $\inv(\pi)$ be the number $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ of inversions of $\pi$, and let the major index $\maj(\pi)$ of $\pi$  be the sum of all integers in the set $\{i: \pi(i+1) < \pi(i)\}$ . Zeilberger proves that, for all $n$, the covariance of the two statistics is

$$
\mathbb{E}[(\inv(\pi) - \mathbb{E}[\inv(\pi)])\cdot(\maj(\pi) - \mathbb{E}[\maj(\pi)])] = \frac{1}{4}{n \choose 2},
$$
where all expectations are over a uniformly random $\pi$ in $S_n$. Zeilberger's proof is just a computer verification for $n \in \{1, 2, 3, 4, 5\}$, and an observation that the statement is equivalent to an identity between polynomials in $n$ of degree at most $4$.


Finding odd holes in circulant Paley graphs The Paley graphs Pq are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a2 for some a ∈ GF(q). In the case that q is prime, the finite field GF(q) is just the set of integers modulo q.

In a recent paper, Maistrelli and Penman show that the only Paley graph which is perfect (having a chromatic number equal to the size of its largest clique) is the one on nine vertices. This implies, in particular, that none of the Paley graphs Pq are perfect for q prime.

The Strong Perfect Graph Theorem asserts that a graph G is perfect if and only if both G and its complement lacks odd holes (an induced subgraph which is a cycle of odd length, and size at least 5.) The Paley graphs of prime order are self-complementary, and imperfect; therefore they must contain odd holes.

Question. For q≡1 (mod 4) prime, is there a poly(q) algorithm for finding an odd hole in Pq? Is there a polylog(q) algorithm? Randomness and popular number-theoretic conjectures are allowed.

I believe there is a known poly(q) algorithm. My understanding of the algorithm by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković, "Recognizing Berge Graphs", Combinatorica 2005, is that it finds either an odd hole or an odd antihole in any non-perfect graph in polynomial time. The authors write on page 2 of their paper that the problem of finding odd holes in graphs that have them remains open, because steps 1 and 3 of their algorithm find holes but step 2 might find an antihole instead. However, in the case of Paley graphs, if you find an antihole, just multiply all the vertices in it by a nonresidue to turn it into an odd hole instead.

Alternatively, by analogy to the Rado graph, for each k there should be an N such that Paley graphs on N or more vertices should have the extension property: for any subset of fewer than k vertices, and any 2-coloring of the subset, there exists another vertex adjacent to every vertex in one color class and nonadjacent to every vertex in the other color class. If so, then for k=5 you could build an odd 5-hole greedily in polynomial time per step. Maybe this direction is hopeful for a poly(log(q)) algorithm? If it works it would at least show that there are short odd holes, seemingly a necessary prerequisite to finding them quickly.

Actually, it wouldn't surprise me if the following were a poly(log(q)) algorithm: if q is smaller than some fixed constant, look up the answer, else greedily build an odd 5-hole by searching sequentially through the numbers 0, 1, 2, 3, ... for vertices that can be added as part of a partial 5-hole. But maybe proving that it works in poly(log(q)) time would require some deep number theory.

By results of Chung, Graham, and Wilson, "Quasi-random graphs", Combinatorica 1989, the following randomized algorithm solves the problem in a constant expected number of trials when q is prime: if q is sufficiently small then look up the answer, else repeatedly choose a random set of five vertices, check whether they form an odd hole, and if so return it. But they don't say whether it works when q is not a prime but a prime power, so maybe you'd need to be more careful in that case.


Kolmogorov Complexity of the composition of two computable functions Let's suppose we encode two computable functions $f$ and $g$ as binary strings so $f,g \in \{0,1\}^*$. What I am curious about is whether we can find good upper and lower bounds for:

\begin{equation}
K(f \circ g) \tag{1}
\end{equation}

where $K(\cdot)$ denotes Kolmogorov Complexity.

My intuition suggests that we can compress each function separately and therefore:

\begin{equation}
K(f \circ g) \leq K(f) + K(g) \tag{2}
\end{equation}

and in general I think we can demonstrate that:

\begin{equation}
K(f_n \circ f_{n-1} \circ ... \circ f_1) \leq \sum_{i=1}^n K(f_i) \tag{3}
\end{equation}

However, my intuition also suggests that this is probably not the best upper bound and I am also curious about tight lower bounds.

Might there be a general theorem that gives the best possible upper and lower bounds?

Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some infinite incomprehensible sequence. If you could compress the composition, you would be able to compress at least one of the constants—a contradiction.

Edit: You might need to pay additional bits for the composition, as for ordered pairings -- as observed by  Emil Jeřábek in the comments.


Early history of certain results on space-time tradeoffs? I'm interested in the early history of published results on general-purpose space-time tradeoffs.  In particular, I want to know who first described the following type of algorithm for evaluating a computation having an arbitrary dataflow graph with in-degree O(1) using space proportional to the depth (not width) of the dataflow graph (plus the size of the input) by doing a straightforward depth-first evaluation of the graph.  In more detail:

Let the dataflow graph be G=(V,E) where V is the set of computational vertices (O(1)-size data values) and E is is the set of edges (v_p, v_s), such that the value of successor vertex v_s \in V depends immediately on the value of predecessor vertex v_p \in V.  Let v_f be the vertex with no successors representing the final result of the computation.  Let I be a canonically ordered set of input vertices (with no predecessors), for i \in I its value x(i) is given.  For other vertices v \in S, their values are defined by x(v) = F_v(x(P(v))) where P(v) is a canonically ordered list of v's predecessors, x(P(v)) is the corresponding list of their values, and F_v is the vertex's function that determines its value as a function of the list of values of its predecessors.  Assume that the length of P(v) is O(1) for all dataflow graphs in some given class of interest (e.g., Boolean circuits with 1- and 2-input gates).

Given this setup, the algorithm in question is fairly obvious & trivial:

def eval(v):     (v can be any vertex in the graph)
   let P := P(v), the list of v's predecessors  (has O(1) elements by assumption)
   let val[] := uninitialized array of |P| data values
   for each predecessor p[i] in P (i.e. for i from 1 to |P|):
      if p[i] is in I then
         val[i] = x(p)      (look up a given input)
      else
         val[i] = eval(p[i])   (recursive call)
   return F_v(val[])        (apply vertex's function to list of predecessor values)

This takes O(d) levels of recursion, where d is the depth of the dataflow graph, and the stack space at each level is constant due to the assumptions that the in-degree of the dataflow graph is constant, and that the size of the data values is constant.  (For simplicity here, I'm treating the size of the vertex references as constant as well, even though they are really logarithmic in |V|.)  Thus, total space usage is O(d + |I|).  The maximum width of the dataflow graph can be exponentially larger than this, so in the best case this technique can provide a pretty extreme space savings, in comparison to, say, a greedy forwards evaluation of the graph (which might be to, at each step, evaluate all vertices that directly depend only on vertices whose values are already known, and discard all vertices that are no longer needed because all of their immediate successors have already been computed).

Anyway, it's a fairly obvious technique, at least in retrospect, and it's certainly long-known, but I was wondering just how back the literature on it goes.  Anyone know the early history of results of this sort (whether described in these terms, or other analogous ones), and what would be a good reference for digging into this subject?

Thanks very much,
-Mike Frank

I do not know if it is the first occurrence or not, but the construction appears in the proof of Lemma 1 of Borodin [Bor77] about the space complexity of evaluating a Boolean circuit.  (It contains slightly more than just the idea of recursive evaluation to reduce the space complexity further from O(D log S) bits to O(D + log S) bits, where D is the depth of the circuit and S is the size of the circuit.)

[Bor77] Allan Borodin.  On relating time and space to size and depth.  SIAM Journal on Computing, 6(4):733–744, Dec. 1977.  DOI: 10.1137/0206054.


Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states? Brzozowski's algorithm for converting a DFA into an equivalent minimum-state DFA is remarkably simple: if $R(D)$ denotes the NFA formed by reversing all the edges in a DFA $D$, making the old start state an accepting state, and making the old accepting states start states, and if $P(N)$ denotes the result of applying the subset construction to the NFA $N$, then $$P(R(P(R(D))))$$ is a minimum-state DFA with the same language as $D$.

We can think of a DFA as a computational device that accepts an input string $w$ and then outputs 0 if $w$ ends in a rejecting state and 1 if $w$ ends in an accepting state. A natural generalization of DFAs associated each state in the DFA with some natural number between 0 and $k-1$, inclusive.

To the best of my knowledge, it's possible to minimize these modified classes of DFAs by using a distinguishability-based minimization algorithm, such as the canonical one by Hopcroft. However, I can't see how it would be possible to adapt Brzozowski's minimization algorithm to this new class of automata because the key step (reversing the automaton) no longer has a clear interpretation in this generalized setting.

Is there a known generalization of Brzozowski's algorithm for minimizing these sorts of automata? If not, are there any theoretical reasons why we'd expect that such a modified algorithm wouldn't exist?

The answer to your question is yes.

See Bonchi, Bonsangue, Rutten and Silva's papers Brzozowski's algorithm (co)algebraically (shorter conference version) and Algebra-Coalgebra Duality in Brzozowski’s Minimization Algorithm (longer journal version with more generalizations).

They give a (lightly) categorical presentation of Brzowzowski's algorithm, and use it to derive versions of it for more general classes of automata, including Moore automata (which gives an affirmative answer to your question).


Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals Looking for some lecture videos (introductory level) on  logic, models of computation as well as computational complexity/ other theoretical computer science fundamentals

Ryan O'Donnell (professor at Carnegie Mellon) has a wonderful undergraduate complexity theory series that goes through the fundamentals quite well, and he's an engaging lecturer. He also has a similar graduate lecture series that mostly picks up where the undergrad series left off.
(Note that this series does not cover logic, and I'm not aware of any videos that do cover that subject.)


Kolmogorov Complexity vs Running Time (Edited) Let $U$ be a universal Turing Machine. Suppose I have a Kolmogorov incompressible string $s$ of length $n$. Let $A:\{1,...,n\} \to \{0,1\}$ be an algorithm such that $A(i) = s_i$.

I believe that the time it takes for the universal Turing machine to evaluate $A$ on input $i$ should be $\Theta(n)$. I'm not familiar with Kolmogorov complexity, and I wanted to ask if the following intuition is correct

An upper bound on the running time of $A$ is $O(n)$, since the description of $A$ can just list the whole string $s$ and return $s_i$ on input $i$. The universal Turing machine on inputs $(A,i)$ simply reads the description of $A$ (Which is $O(n)$ in length) and outputs the $i^{th}$ coordinate (which takes time $\log n$)
A lower bound on the running time of $A$ can be proved as follows.

a. The description length of $A$ must be at least $n - log n - c$ for a constant $c > 0$. This is because the program $B$: "Run $A$ on every input from $1$ to $n$" has description length $DL(B) = DL(A) + log(n) + c$ and generates the string $s$. Thus $DL(B) \geq n$ and $DL(A) \geq n- \log(n) - c$.

b. The universal Turing machine $U$ on input $(A,i)$ needs to read both $A$ and $i$, which requires at least $DL(A) + \log n \geq n-c$ operations.

Is this intuition correct? Or am I missing something big about Kolmogorov complexity?

It really depends on your computation model. Suppose for example a model which allows random "seek" instructions, say the RAM machine. The algorithm $A$ can just include a description of the string, and on input $i$ you output the $i$th bit of the string. Conceivably, a universal Turing machine (running on a RAM machine) can execute this algorithm in time $O(\log n)$, especially if we engineer it to specifically handle algorithms of this type.

Any proof that a universal Turing machine (running on an actual Turing machine) requires time $\Theta(n)$ thus needs to appeal specifically to the Turing machine model. In particular, you claim that the universal Turing machine $U$ must read all of $A$ and $i$. But in fact, for any given string $s$ we can construct a universal Turing machine whose programs come in two types: (1) output $s$; (2) everything else. Such a Turing machine can "simulate" $A$ in time $O(\log n)$. The correct claim you should try to prove thus needs to accommodate finitely many exceptions, unless you are fixing a universal Turing machine. (On second thought, it's not clear whether you can pull it off while keeping the string random. Indeed, it seems you won't be able to recognize the program $A$ without reading all of it, which would take time $n$ if the string is Kolmogorov random.)

Even if we fix a universal Turing machine, it's not clear that $A$ necessarily takes time $O(n)$. We can arrange for $A$ to first output $n!$ many zeroes, then erase them and proceed as in your algorithm. Perhaps you meant $A$ to be the one with the lowest time complexity? (say the one minimizing the maximal execution time over all indices)


Can we quantify the "degree of quantumness" in a quantum algorithm ? Entanglement is often held up as the key ingredient that makes quantum algorithms well... quantum, and this can be traced back to the Bell states that destroy the idea of quantum physics as a hidden-state probabilistic model. In quantum information theory (from my rather weak understanding), entanglement can also be used as a concrete resource that bounds the ability to do certain kinds of coding.

But from other conversations (I recently sat on the Ph.D committee of a physicist working in quantum methods) I gather that entanglement is difficult to quantify, especially for mixed-state quantum states. Specifically, it appears hard to say that a particular quantum state has X units of entanglement in it (the student's Ph.D thesis was about trying to quantify amounts of entanglement "added" by well known gate operations). In fact, a recent Ph.D thesis suggests that a notion termed "quantum discord" might also be relevant (and needed) to quantify the "quantumness" of an algorithm or a state.

If we want to treat entanglement as a resource like randomness, it's fair to ask how to measure how much of it is "needed" for an algorithm. I'm not talking about complete dequantization, merely a way of measuring the quantity.

So is there currently any accepted way of measuring the "quantumness" of a state or an operator, or an algorithm in general ?

It depends on the context.

 For quantum algorithms, the situation is tricky, since for all we know, P=BPP=BQP.  So we can never say that a quantum algorithm does something that no classical algorithm can do; only something that a naive simulation would have trouble with.  For example, if a quantum circuit is drawn as a graph, then there is a classical simulation that runs in time exponential in the treewidth of the graph).  So treewidth can be thought of as an upper bound to 'quantumness', although not a precise measure.

Sometimes measuring quantumness in algorithms gets conflated with trying to measure the amount of entanglement produced by an algorithm, but we now think that a noisy quantum computer could have computational advantages over classical computer even with so much noise that its qubits are never in an entangled state (e.g. the one clean qubit model).  So the consensus is now more on the side of thinking of the quantumness in quantum algorithms as related to the dynamics rather than the states generated along the way.  This can help explain why 'dequantizing' is not likely to be generally possible.

 For bipartite quantum states, where the context is two-party correlations, we have many many good measures of quantumness.  Many have flaws, like being NP-hard, or not additive, but nevertheless we have a pretty sophisticated understanding of this situation.  Here is a recent review.

 There are other contexts, such as when we have a quantum state and would like to choose between different incompatible measurements.  In this setting, there are uncertainty principles that tell us things about how incompatible the measurements are.  The more incompatible the measurements are, the more 'quantum' a situation we have.  This is related to cryptography and zero-error capacities of noisy channels, among many other things.


Reusing 5-independent hash functions for linear probing In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (Sufficiency: "Linear probing with constant independence", Pagh et al., necessity: "On the k-Independence Required by Linear Probing and Minwise Independence", Pătraşcu and Thorup)

It is my understanding that the fastest known 5-independent families use tabulation. Picking a function from such a family may be expensive, so I would like to minimize the number of times I do so while still preventing algorithmic complexity attacks as described in Crosby and Wallach's "Denial of Service via Algorithmic Complexity Attacks". I'm less worried about timing attacks (i.e. adversaries with stopwatches). What are the consequences of reusing the same function:

When growing a hash table that is too full?
When shrinking a hash table that is not full enough?
When rebuilding a hash table that has too many "deleted" bits set?
In $k$ different hash tables that may contain some keys in common?
In $k$ different hash tables that contain no keys in common?

One potential issue is when reading from a hash table, the elements should not be read in the order of the slots if all hash tables use the same hash function. This is because those elements, in that order, can cause the insert procedure on a smaller hash table with the same hash function to go quadratic, assuming that the max fill factor is over $1/2$. See:

https://issues.cloudera.org/browse/IMPALA-2653
https://github.com/rust-lang/rust/issues/36481


Is the church-style affine calculus of constructions with unrestricted recursion consistent? Suppose we take the church-style calculus of constructions, except with affine functions (variables must occur at most once) and mutual recursive definitions. For example:

Nat =
  ∀ P : *
  ∀ S : Nat -> P
  ∀ Z : P
  P

Zer =
  λ P : *
  λ S : Nat -> P
  λ Z : Nat
  Z

Suc =
  λ x : Nat
  λ P : *
  λ S : Nat -> P
  λ Z : Nat
  S x

two =
  Suc (Suc Zer)

If we built an eager type-checker and asked it to infer Zer, it'd not halt, as Zer's type is infinite:

two : ∀ (P : *) -> ∀ S : (∀ (P : *) -> ∀ S : (∀ (P : *) -> ∀ S : ...

But if we do it lazily, then it'd output:

Zer :
  ∀ P : *
  ∀ S : Nat -> P
  ∀ Z : Nat
  Z

Which is the same as Nat and correct, since Zer is indeed a proof of Nat. One could wonder if it could accept "wrong" proofs such as false : ∀ (P : *) -> P, for some construction of false. The obvious approach, though, seems not to work:

false = (λ (x : ∀ (P : *) -> P) -> x) false

If we had top-level type-annotations (such as false : ∀ (P : *) -> P), the checker would indeed accept this term. But, because of curry-style, the only way to infer the type of false is by inferring the type of false: it'll be stuck in an infinite loop and never output anything.

In other words, it seems that, for the subset of terms that this type-inferencer halts, it behaves as a consistent proof assistant. Of course, it works a bit differently from usual as it has infinite types and whatnot, but, intuitively, it seems to be a functional system for mathematical proofs, since it seems to be unable to accept false or other incorrect proofs. If one is able to prove that this type-checker could never accept false, would it indeed be well suited for mathematical proofs?

Let me first state that I'm not sure what are you getting at, I'm not sure how linearity/affinity is relevant. I'll answer the question in 'standard' setting.

How would you define how to compare two infinite types lazily?

It seems to me that it can't be done automatically since they can eventually diverge.

[Checking for  nominal equality ("pointer quality", exactly same identifier) seems shortsighted since you could define two identical infinite structures Nat and Nat2 and they would not be equal nominally while they should.]

But in some cases it can be done, its just that the programmer needs to lead the checker on how the equality should be verified.

In your case, think about Nat as a type-level fix point:

natF =
  ∀ nat : *
  ∀ P : *
  ∀ S : nat -> P
  ∀ Z : P
  P

Nat = fix nat . natF nat

That gives Nat and the two functions:

fix : Nat -> natF Nat
unfix : natF Nat -> Nat

You can use these functions as annotations that control the infinity and allow the checker to work with finite structures all the time.

This article has a nice intro (there are plenty of similar tutorials):
Gentle introduction to the general technique of F-algebras

For Nat, you would use this functor:

data Nat nat = Z | S nat


Single author papers against my advisor's will? I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor.

My advisor is not involved in my research projects at all. In particular, I have come up with all of my paper ideas, and have executed the papers alone. However, she always insists on adding her name as a co-author. This has started to increasingly bother me, as I work very hard (alone) on my research and believe I should get credit for that. In addition, she is a bully and treats me quite badly, so it makes it even harder for me to benefit her in this way.

For my most recent paper, I brought up how I didn't believe she was meeting the IEEE 1 or ACM 2 guidelines for authorship, and told her that I believed I should be sole author on my paper. She agreed that she shouldn't be an author, although she was visibly angry. She said that I was a "weirdo" for doing this, and said that everybody already knows that advisors take credit for their student's work and that publishing with your advisor is the same as publishing alone. But most importantly, she told me that she would not approve my proposal/dissertation if I did not add her name to several more top-tier papers because then I "have no ties to the university" since I am not working with a professor, and therefore cannot receive my PhD.

Obviously, I need a new advisor. However, there is really no one in my department in my research area. Switching research areas or departments are not options. So the remaining options are the following:

(1) Add her name to several more papers. I do not like this idea because it is unethical, and there is no guarantee that anything is even gained in this option. She could simply refuse to recommend me in the end after I got her a bunch of papers.

(2) Ignore her threats, and force my way to finishing my PhD while publishing single author papers. I do not believe she could stop me from graduating since I already have a decent publication record, and presumably will continue getting my work out. I have a fellowship, so she can't control my funding. Clearly, I will not have a letter of recommendation in this case. On the other hand, I will have a bunch of single author papers.

(3) Try to convince a professor in an unrelated research area to be my advisor, emphasizing that I am independent and can do my work alone. There are a few theory professors in my dept, although they are totally different areas. I have no idea the chance of this working out.

(4) Go to the department chair and tell him the whole story, ask what to do.

What do you think I should do?

As a department chair, I can say you aren't alone. These situations come up all too often.

Please do reach out to your department chair, graduate program director or grad student ombudsperson if your institution has one. We want to know when our faculty are behaving badly and often we can help.


Scott's normal form for $\exists y \forall x R(x,y) $ In this paper  Scott's reduction is discussed, which reduces any FO2 formula to Scott's Normal form. As far as I understand the reduction process explained in the paper can get you to formulas with only $\forall \forall$ and $\forall \exists$ quantification prefixes. Which has three possibilities of prefixes  $\forall x \forall y $, $\forall x \exists y$ and $\exists y \forall x$. Now scott's normal form only admits $\forall x \forall y $ and $\forall x \exists y$ quantification. Then how is the explained process sound for a formula like $\exists x \forall y R(x,y) $ ?
In other words, what is the scott's reduction for $\Phi(x,y) = \exists x \forall y R(x,y)$.
My attempt on reduction according to the paper:
$ Sc( \Phi(x,y) )= \exists x P(x)  \land \forall x \forall y (P(x) \leftrightarrow R(x,y)) $

Your solution is correct. It suffices to see that the formulae $\exists{y} P(y)$ and $\forall{x} \exists{y} P(y)$ are equi-satisfiable, which allows you to put your formulae in the desired form.