What are some methods for representing a weighted directed graph with a non-weighted directed graph while preserving some properties?

The problem of computing the permanent of general matrices can indeed be reduced to the problem of computing the permanent of 0-1 matrices. This was shown in the paper that introduced the complexity class #P in 1979 [1] (which also showed that the problem is #P-complete).

There's a nice article that covers this on Wikipedia, based on a simpler proof published later [2].

As you mentioned sparse matrices particularly you may wish to know that if the matrix is the biadjacency matrix of a planar graph then the permanent can be computed in polynomial-time using the FKT algorithm. This is a consequence of the permanent of the biadjacency matrix of a bipartite graph being equal to the weighted sum of perfect matchings, as explained here. There's a previous question related to this.

[1] L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci.,
8:189-201, 1979. Available here.
[2] A. Ben-Dor and S. Halevi. Zero-one permanent is #P-complete, a simpler proof. Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, pages 108–117, 1993. Available from the author's webpage here.


The number of triangulations of a set of $n$ planar points: Why so difficult?

Here's one more "applied" reason why we care about triangulations. There's a body of work on mesh compression where the goal is to use as few bits per vertex as possible to encode a mesh (mainly to aid in storage and transmission). The particular base of the exponent in the number of triangulations of a planar point set provides an information-theoretic lower bound on the number of bits needed per vertex (specifically, $8.48^n$ triangulations means you need at least 8.48 bits per vertex). Such bounds can then be compared with actual mesh compression schemes to determine their efficacy.


if I were to define a new complexity class how should I start?

First you would search around and check e.g. the complexity zoo, because many, many classes are already defined and you don't want to redefine one that is already known by some other name.

The ways I know of are:

Define a complete problem and a notion of reduction; the class consists of all problems so reducible to that problem. This is usually only possible for so-called "syntactic" complexity classes -- see the question "Semantic vs Syntactic Complexity Classes" -- which tend to also have a nice definition in terms of a model of computation. (E.g. $\mathsf{NP}$ can be defined as all languages that are polytime mapping-reducible to $\mathsf{3SAT}$; or as all languages decidable by a polytime nondeterministic TM.)
Define a model of computation and what it means for that model to decide/compute a language/problem; the class consists of all languages/problems for which there exists such a model of computation that decides/computes the language/problem. This works for probabilistic classes like $\mathsf{BPP}$, but also for more exotic models like quantum classes, circuits, interactive protocols, or finite automata for that matter. This is probably the method you'd go for, and for more detail, maybe look at examples of all the above types (e.g. $\mathsf{BPP, BQP, ACC, IP, MA, PCP, REGULAR}$).

Perhaps those more expert than I am can say if there are other major methods that are missing, or expand on these if needed.


Beating naive dynamic programming: examples similar to integer partitions?

One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 Björklund gave an algorithm running in time $O(1.657^n)$ using determinants and polynomial identity testing in a field of characteristic $2$.

Another example is that of “connectivity problems”, such as Hamiltonian Path, Steiner Tree, or Feedback Vertex Set on graphs of treewidth $k$. The naive dynamic programming algorithms for these problems run in time $2^{O(k \log k)}n^{O(1)}$, and at a glance it really looks like that is what the ``correct’’ running time for these problems should be. However, in a wonderful paper, Cygan et al. showed that these problems all allow algorithms with running time $2^{O(k)}n^{O(1)}$, again cleverly using polynomial identity testing in a field of characteristic 2.


Data structure for radial orderings of points on the plane

This problem is the same as halfspace range counting up to polylog factors.

  Halfspace range counting in 2D

  Preprocess $n$ points $S$ on the plane. A query takes a halfspace $H$ (represented by the boundary), and return $|H\cap S|$.

For the case of $\tilde{O}(n)$ queries, one can use $\tilde{O}(n^{4/3})$ time to build a data structure that returns the answer in $\tilde{O}(n^{1/3})$ time. This is the best possible up to polylog factors [1].

Proof Sketch:

Upper bound:

The simplex partition tree data structure for halfspace range counting [1] can be used directly for this problem. A simple solution would be using a halfspace counting query as a proxy for binary search while navigating the partition tree. I believe polylog factors can be saved with more care.

Lower bound:

Consider we want to solve the halfspace range counting problem in 2D on $S$,
we first construct the radial orderings data structure.

For any halfspace $H$ as input, we shift the halfspace up until it touches an element in $S$. By duality, this operation can be modeled as a vertical ray shooting problem in a convex polygon defined by the intersection of halfspaces, which is known to be very fast [2].

We can use our data structure to do binary search. We find two adjacent points in the radial ordering so the slope of $H$ is in between. The index shows the number of points in $H\cap S$.

Matoušek, Jiří, Range searching with efficient hierarchical cuttings, Discrete Comput. Geom. 10, No. 2, 157-182 (1993). ZBL0774.68101.
Agarwal, Pankaj K.; Matoušek, Jiří, Ray shooting and parametric search, SIAM J. Comput. 22, No. 4, 794-806 (1993). ZBL0777.68042.


Without paying much attention to your code, your crossover rate is maybe a touch low, your mutation rate is orders of magnitude too low, your population is tiny, and you're only running 20 generations. You're just not doing enough search for anything to work. If your initial population had a 6 or 7, you find it. Otherwise, you get a handful of crossovers to hope to get lucky and then you're done.

You have 4 bits * 6 individuals = 24 bits per generation * 20 generations. At best, you have 480 bits of information here, and your mutation operator expects one flip per thousand bits.

You also select parents using fitness proportionate selection, which has pretty severe issues with selection pressure, made even worse with such a small population. Look at it this way, suppose you generate the following six individuals for your initial population (6, 0, 15, 13, 11, 2). f(6) is quite a bit better than every other choice -- the selection probabilities are roughly (0.36, 0, 0, 0.17, 0.29, 0.17). So you'd expect the parent pool to look something like (6, 13, 6, 11, 11, 2). Obviously the exact choices are random, but that fits the distribution. Now if you pair a 6 with a 6 or an 11 with an 11, you're guaranteed to produce another copy of those, as crossover of identical parents can't flip any bit. And you have no mutation at all (practically speaking). So your population just rapidly converges to the best thing you found in your initial random population.

Crossover does have some chance of producing better individuals, which is why you see the optimum 30% of the time instead of ~10% that you'd expect just by sampling for the initial population. But that's about it. You just don't have enough search happening to reliably do any better.

Again, there may also be bugs -- I didn't look carefully.


Why do we need a sphere to graphically represent a qubit?

If we have $a|0\rangle + b|1\rangle$, there are two quantities we need to know to specify the qubit:

the ratio $a/b$, which is encoded by the latitude: $\left|0\right\rangle$ is the north pole and $\left|1\right\rangle$ the south,
the relative phase of $a$ and $b$, which gives the longitude.

That is, you can treat either $a$ or $b$ as a real number, but not both.

A circle can only specify one quantity.


What are some example problems for integer programming that are *not binary*

Here are a few examples:

(Most Common) Cutting Stock Problem - determine patterns for which to cut boards in order to meet demand.
(Kinda same problem) - Knapsack with general integer variables - used for column generation in the cutting stock problem
Problems with modular constraints:  $x \equiv 3 \pmod 5$ can be written as $x + 5y = 3$, $y \in \mathbb{Z}$.  Most commonly seen in cyclic train schedules - https://www.sciencedirect.com/science/article/abs/pii/S0360835213001782
Generalized Vehicle Routing Problems - http://orel.uca.es/pdfs/ORP3_3_ClaudiaBode.pdf
B-matchings - https://arxiv.org/pdf/math/0607088.pdf
Bin Packing with a constant number of item types (theoretical application) https://arxiv.org/abs/1307.5108
Lattice point counting in polyhedra - https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf
Lattice vector problems - Closest Vector Problem (CVP) and Shortest Vector Problem (SVP) are technically unconstrained convex quadratic (general) integer programming problems. These are important problems in computer science. https://en.wikipedia.org/wiki/Lattice_problem
This also goes under the name of "integer least squares regression" since it is also just solving a quadratic regression problem with an integer constraint
https://stanford.edu/~boyd/papers/pdf/int_quad_cuts.pdf
"The integer least squares problem captures the essence of the phase ambiguity estimation problem arising in the global positioning systems (GPS) [HB98]."

I would, however, like to figure out upper bounds for integer variables used in practice.  Something still on my mind.  For instance, can we assume that all integer variable used in practice are upper bounded by 1000? 10,000?  How can we use this information?  It is true that often it can be advantageous when solving to convert integer variables into binary variables, but this is not always the case.


Sampling from the binomial distribution with limited randomness and time

To exactly sample from the binomial distribution on $\{0,1,\cdots,n\}$ requires $n$ random bits. However, we can approximately sample with $O(\log(n/\varepsilon))$ bits, where $\varepsilon$ is the statistical distance from binomial we allow.

Let $$a_0=0, ~~~~a_{k+1}=a_k+{n \choose k} \cdot 2^{-n} ~~~~(k \in \{0,1,\cdots,n\}).$$ We can sample exactly from the binomial distribution by sampling $x \in [0,1)$ uniformly and then picking $k$ such that $x \in [a_k,a_{k+1})$. The probability of picking any given $k$ is thus $$\mathrm{Pr}_x[k]=\mathrm{Pr}_x[x\in[a_k,a_{k+1})] = a_{k+1}-a_k = {n \choose k} \cdot 2^{-n}.$$

We will sample approximately by sampling $\tilde{x} \in \{ 0, 1/m, 2/m, \cdots, (m-1)/m \}$ uniformly and then picking $k$ such that $\tilde{x} \in [a_k,a_{k+1})$. This requires $O(\log m)$ bits of randomness. We have $$\mathrm{Pr}_\tilde{x}[k]=\mathrm{Pr}_\tilde{x}[\tilde{x}\in[a_k,a_{k+1})]=\frac{\lceil m a_{k+1} \rceil - \lceil m a_k \rceil}{m}=a_{k+1}-a_k \pm \frac{1}{m} =\mathrm{Pr}_x[k] \pm \frac{1}{m}.$$
So the difference between the probability of $k$ under exact sampling and under approximate sampling is at most $1/m$. Summing over all $k$, we have that the statistical distance is at most $(n+1)/m$. Setting $m=O(n/\varepsilon)$ ensures that the approximate sampling is $\varepsilon$ statistically close to binomial.


Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

If the number of counters or the number of reversals (or both) is part of the
input, the problem becomes coNP-complete (unless there is exactly one counter):

The upper bound was shown by Hague and Lin, using a reduction to existential Presburger arithmetic:
Hague and Lin, "Model Checking Recursive Programs with Numeric Data Types", CAV 2011, http://dx.doi.org/10.1007/978-3-642-22110-1_60.

If the number of counters is part of the input and one has exactly one
reversal, it is not hard to reduce the knapsack problem: Given
binary representations of $x_1,\ldots,x_k,y$, each containing at most $n$
bits, one can easily construct a $(k+1)n$-counter automaton $A$ that can nondeterministically pick a subset $S\subseteq \{1,\ldots,k\}$ and
produce $\sum_{i\in S} x_i$ on the first counter and then subtracts
$y$ from the first counter. Then the language of $A$ is non-empty
if and only if there is a subset $S\subseteq \{1,\ldots,k\}$ with
$\sum_{i\in S} x_i=y$.
If the number of reversals is part of the input and one has exactly
two counters, coNP-hardness was already shown in
Gurari and Ibarra, "The complexity of decision problems for finite-turn multicounter machines", http://dx.doi.org/10.1016/0022-0000(81)90028-3 .
This seems to be the journal version of the paper linked in the question.
If the number of reversals is part of the input and one has exactly
one counter, however, then the problem is NL-complete. This is a well-known
result on one-counter automata.


Are there non-constructive proofs of existence of "small" Turing machines / NFAs?

Only an extended comment with a trivial example; you can pick the one-element language:

$$L_k = \{ M \mid  \sigma(M) = \Sigma(k) \}$$

i.e. $L_k$ contains the first (in lexicographical order) busy beaver Turing machine of size $k$ (the Turing machine of size $k$ that attains the largest number of 1s on its tape after halting).

For every $k$ the language $L_k$ is regular ... but we have no idea on how to  build the small DFA that recognizes it (though it has only $\leq 2*k(\log k+2)$ states) :-)


Keyed queues with depth queries and delete

Your solution can be modified to do everything in $O(1)$ amortized time. Instead of maintaining a balanced tree, just keep track of the number of successful enqueue operations (those in which something was actually added to the back of the queue) and attach that number to queue along with the item during a successful enqueue operation. To find the depth of a key, just take the difference between the number of successful enqueues when it was enqueued, and the number of successful enqueues when the item currently at the front of the queue was enqueued. Note that this gives exact depth.

If you're worried about storing excessively large values after many enqueue and dequeue operations, you can also keep track of the size of the queue and whenever the size is less than half the number of enqueues, re-number the number of enqueues for each entry to 1 through the size, and reset the number of enqueues to the size. Everything takes constant amortized time and each key takes at most one more bit than necessary to represent its depth at insertion.


Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time

A good reference is
Code-Based Game-Playing Proofs and the Security of Triple Encryption by Bellare & Rogaway. The statement that you are asking about is called the PRF/PRP switching lemma. This paper goes into significant detail about "standard" proofs of this lemma and the subtleties therein. It uses the switching lemma as an illustrative example to advocate for a "game-playing" paradigm for cryptographic proofs that is the "real" purpose of the paper.

Here is another paper (A Short Proof of the PRP/PRF Switching Lemma, Chang & Nandi) that claims a short self-contained proof as well.


Is there any notion of sensitivity for probabilistic Boolean functions?

This should work fine inasmuch as if $f$ is now a random function, then you just get the expected sensitivity:
$$\mathbb E s(f, x) = \sum_{y \in N(x)} \mathbb E I(f(x) \neq f(y)) = \sum_{y \in N(x)} \Pr(f(x) \neq f(y)).$$


Two Decision Problems About Graphs --- Original Results?

Problem 1 is an exercise in CLRS (2nd ed., page 617).


The structure of pathological instances for simplex algorithms

Amenta and Ziegler proved that all currently-known constructions of exponential-time instances for simplex follow a particular structure that they call "deformed products":

  Deformed Products and Maximal Shadows of Polytopes by Amenta and Ziegler

However, I don't think there's any reason to believe that all bad instances for simplex have this structure.  This is probably just an artifact of the research process:

Klee and Minty found the first exponential-time example.
Other researchers looked and Klee and Minty's techniques and extended them to other pivot rules.  They naturally took the path of least resistance and followed the Klee-Minty cube as closely as possible.
Once someone finds one bad example for a pivot rule, there's no incentive for people to look for more.  As a result, all the bad examples we know of have a similar structure.


Winning strategy of an "edge or isolated vertex" deletion game

I post an update as a self-answer only to keep it distinct from the question (which is still open).

As shown in the comments (thanks to Tsuyoshi Ito) the problem is polynomial-time solvable for paths:

$Win(P_n) = 1$ iif $(n \bmod 34) \in \{3,7,23,27\}$

Starting from 0, the (calculated) sequence of the nim values is periodic:

0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated

I didn't work on a rigorous mathematical proof, but the idea is:

suppose that we want to calculate element $Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x < 34)$, then the first move (pick an edge) can split the path in $\lceil n / 2 \rceil$  different ways (n-2,0),(n-3,1),(n-4,2),...). The new nim value is equal to:

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$

The first 34 elements of the set are produced by the first non repeating sequence (0,1,1,0,...) (nim)summed with the elements of the repeating sequence in reverse order starting from element $(34-2-x) \bmod 34$.

For example: for $x = 0$:

     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4

For x=0..33 the resulting mex sequence is equal to the repeating sequence:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6

The remaining elements of the set are calulated only on the repeating sequence(s): $rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$ (for $j \geq 34$ the pairs are repeated, so they don't alter the mex result). The resulting mex sequence for x=0..33 is:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,

Which is equal to the repeating sequence except for $x=16$ and $x=33$; but the values are lower than the corresponding mex on the non-repeating sequence, so:

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$ = $mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{n-2-33}+P_{33}\}$

and for $(k\geq 4, 0 \leq x < 34)$, $Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\; $


clustering (lat,lng) pairs, with clusters having the same number of elements

This sounds like it may be a NP-hard problem. But perhaps a relatively simple heuristic will give good enough results, something like:

Use one of the heuristic approximations to the travelling salesman problem to find a (relatively) short loop that passes through all of your N locations.
Then arbitrary pick some location on that loop as a "starting" point location number 0, and number each location along that path from 0 to (N-1).
Each employee i (from 0 to k-1) gets the approximately N/k consecutive locations along that loop, from location i*N/k to location (i+1)*N/k - 1.


Complexity of finding weighted edge-disjunctive triangles in a graph

Here's a reduction from edge coloring that I believe shows this to be NP-complete.

Let G,k be an instance of edge coloring: that is, we wish to know whether the edges of graph G can be colored with k colors. Make all edges in G negative, and add k new vertices to G, each connected by positive edges to every existing vertex in G.

Then, if G has an edge coloring, the modified graph has a set of edge-disjoint valid triangles that includes all of the edges in G: simply form a triangle connecting each edge in G to the new vertex that corresponds to its color. Conversely, if there exists a set of edge-disjoint valid triangles that includes all of the edges in G, then one can use the identities of the new vertices in each triangle as colors in an edge coloring of G.


Translation from basic While-language to $\lambda$-calculus

Here is the toy language I am going to use. Note that locations are numbered.

$$    A := n \quad | \quad x_k \quad | \quad A_1 + A_2 \quad | \quad  ... \text{ (where $n,k ∈ \mathbb{N})$ } $$
$$    B := A_1 = A_2 \quad | \quad  ...  $$
$$    C := \quad  C_1 ; C_2 \quad |\quad  x_k := A\quad  | \quad  skip \quad |\quad \mathop{if}~B~\mathop{then}~C_1~\mathop{else}~C_2 \quad | \quad  ...  $$

First, you have to encode states.
What's a state ? It's map from your set $L$ of locations
to your set $V$ of values. Here I choose to implement them
by a function $σ : \mathbb{N} → \mathbb{N}$. We'll call
$Σ$ the set of states.

There are two common operation over states :
$$\mathop{get} : Σ → L → V$$
$$\mathop{get} = λs.λx.(s~x)$$

$$\mathop{set} : Σ → L → V → Σ$$
$$\mathop{set} = λs.λx.λv.\left(λk.\mathop{equal}~k~x~v~(s~k)\right)$$
where $equal$ is a λ-term representing equality between Church numerals.

Then we have to encode arithmetical expressions as function from $Σ$ to $V$
$$⟦n⟧ = λs.\lceil n \rceil$$
$$⟦x_k⟧ = λs.get~s~\lceil k \rceil$$
$$⟦A_1 + A_2⟧ = λs.\mathop{plus}~(⟦A₁⟧~s)~(⟦A₂⟧~s)$$
$$\vdots$$
where $\mathop{plus}$ is a λ-term representing addition over Church numerals and
$\lceil n \rceil$ is the $n$-th Church numeral.

And boolean expressions as functions from $Σ$ to booleans:
$$⟦A₁ = A₂⟧ = λs.\mathop{equal}~(⟦A₁⟧~s)~(⟦A₂⟧~s)$$
$$\vdots$$

Finally you encode your commands as "state transformers" from $Σ$ to $Σ$.
$$ ⟦skip⟧ = λs.s $$
$$ ⟦x_k := A⟧ = λs.\mathop{set}~s~\lceil k \rceil~(⟦A⟧~s) $$
$$ ⟦C₁;C₂⟧ = ⟦C_2⟧ ∘ ⟦C_1⟧ = λs.⟦C_2⟧~(⟦C_1⟧~s)$$
$$ ⟦\mathop{if}~B~\mathop{then}~C_1~\mathop{else}~C_2⟧ =
   λs.⟦B⟧~s~(⟦C₁⟧~s)~(⟦C₂⟧~s) $$
$$\vdots$$

Exercise 1: Prove the correctness of this compilation wrt to a standard operational semantics.
Exercise 2: Check that everything works in a typed context (you will however need some kind of fixpoint operator to translate the while construction).


The sum of finitely many binary numbers can be computed in $TC^0$ and is in fact complete for $TC^0$ under $AC^0$ reductions.

The maximum of finitely many binary numbers can be computed in $AC^0$.

So from the circuit-complexity perspective, sum is more difficult.


In regards to the tautologies of a polynomially-bounded propositional proof system

Your question is like asking what is the class of formulas for the problem SAT?
In the definition of SAT it is fixed to some fixed class,
say those based on $\{\lnot, \land, \lor\}$
but it doesn't really matter usually whether
we talk about formulas based on
$\{\lnot, \land, \lor\}$ or $\{\bot, \to \}$ or
any other complete set of Boolean connectives.
Therefore it is often not explicitly stated.
The reason is they can simulate each other with
at most polynomial increase in the size of formulas.
Therefore it is often not explicitly mentioned.
If we pick an unusual one then things might be completely different.
E.g. DNF-SAT is in P, but this does not mean SAT is in P.
Similarly CNF-TAUT is in P and therefore
if we define the concept of proof system for CNF-TAUT
it has polynomially bounded proof system.
But again this does not mean that
TAUT has polynomially bounded proof system.
The problem we are interested in is TAUT, not CNF-TAUT.
We want a polynomially bounded proof system for TAUT.

For the definition of proof system
we have to similarly fix the class of tautologies.
If we pick different classes we get different definitions.
TAUT being the dual to SAT
it is natural to take the dual of the formulas for SAT
(i.e. formulas based on connectives $\{\lnot, \land, \lor\}$).
It is also common to use DNF-TAUT as a dual to CNF-SAT
(there is a simple reduction from SAT to CNF-SAT
using new extension variables such that
the set of satisfying assignments of the original formula and resulting CNF
are P-isomorphic).
But as long as we can efficiently express DNF formulas
it usually does not matter what we use.
It can be linear equations, or any class of computational objects
as long as they can express DNFs with at most a polynomial increase in size.
If that is not the case then
the system is trivially not polynomially bounded as
it is not a proof system for TAUT (or DNF-TAUT).
The book does not deal with cases where
the class of formulas does not contain DNFs.

For the purpose of the book you can assume that the class of propositional formulas contains DNFs and every tautology means every DNF tautology.

  A proof system $Q$ is polynomially bounded if
  there is a polynomial $p$ such that
  for every DNF tautology $\varphi$
  there is a $Q$-proof $\pi$ such that
  $|\pi| \leq p(|\varphi|)$.

As you can see there is no mention of other proof systems.

If you want the more general definitions look at Reckhow's thesis.
Reckhow looks at the more general definition with different set of connectives
and classes of formulas.
He shows that any two Frege systems polynomially simulate each other
as long as we have a complete set of Boolean connectives.
I think the simplest way to explain it is as follows:

  If we have a complete set of connectives
  we can express in polynomial size the truth of formulas
  based on another finite set of Boolean connectives.

For more see the section in Reckhow's thesis
discussing polynomial simulation
between proof systems with different class of formulas.


Logical Reations for an Impredicative System in a Predicative MetaTheory

In general, what we usually call the logical relations argument isn't really linked to impredicativity: the main idea is simply to interpret terms in some abstract algebra $\cal A$, and to represent types as a ($n$-ary) relation $R \subseteq \cal A^n$.

This works perfectly fine for all kinds of type theories, including dependently typed theories, see e.g. Shürmann and Sarnat: Structural Logical Relations where a predicative logic (that of Twelf) is used to prove a certain property (decidability of equality) for a predicative calculus (simply typed $\lambda$-calculus) using logical relations.

As you may have suspected, however, it is not possible to prove normalization of system F in Agda (if Agda isn't secretly stronger than expected, i.e. about the strength of Martin-Löf type theory with a bunch of universes). This is because normalization of system F implies consistency of 2nd order arithmetic ($\mathrm{PA}_2$) which is stronger than M-L type theory with any number of (predicative) universes.

It's instructive to work out exactly where the proof goes wrong in Agda, though. It indeed occurs when you try to define the logical relations interpretation of the impredicative quantification. The interpretation of the non-impredicative connectives though (including "dependent" quantification) is kosher in a theory like Agda.


This is not an answer, but another version, NOT equivalent to the original of this excellent, but perhaps hard to grasp question.
Define the bipartite clique partition number of a graph as the least number of its complete bipartite subgraphs that cover each edge exactly once.
Similarly define the support of the fractional bipartite clique partition number of a graph as the least number of its complete bipartite subgraphs that have a positive weighing such that for each edge the sum of the weights of the subgraphs containing it is exactly one.
The question is whether these two parameters are always equal or not.

I find it quite surprising that while fractional version are studied a lot, I've never heard of studying the size of the support of the fractional version.
I also wonder whether this latter parameter has any applications.
Also, the question could be asked about several other parameters.


Complexity class for quantum computer with commutative gates

There isn't a one word answer to your question, but you can have a look at

Xiaotong Ni's master thesis,

where commuting circuits with several restrictions are considered and compared to classical classes.
There you can also find the definition of the class IQP, which is a subclass of polynomial size commuting Pauli circuits.


Why does the Fibonacci sequence produce a worst-case Huffman encoding?

This paper may shed some light on the issues: http://www.springerlink.com/content/w32x70520k8jj617/


Maximum cardinality subgraphs meeting a Jaccard overlap threshold

The problem is NP-hard if $\alpha$ is part of the input. We can reduce the Steiner tree problem to this. Given a graph $G$ and terminal vertices $T$, consider $G_0$ to be a complete graph on $T$, and $G_1=G$.

Let $|T|=k$ and the size of the minimum Steiner tree of $T$ in $G$ be $h$.

If $\alpha=k/h$, we claim that $V_0'=T$. Assume not, then $|V_0'|<k$.
$|V_0'|+|V_1'|\geq k+h$, so $|V_1'|> h$. But then $|V_0'|/|V_1'|<\alpha$. A contradiction. Also, $|V_1'|=h$, as anything larger violates $|V_0'|/|V_1'|\geq \alpha$. $V_1'$ also gives us the vertices of a minimum Steiner tree on $T$. We can obtain $h$ by guess every possible $h$, there are only $n$ possibilities. Hence we reduce Steiner tree problem to your problem.


Property testing of triangular properties

Your problem is well-understood in the case $S = \{0,1\}$.  Here, the function $\phi$ can be viewed as the adjacency matrix of a graph $G_\phi$ on the vertex set $V$.  And $\phi$ satisfying a triangular property $P$ just means that $G_\phi$ is free of some collection $C_P$ of induced subgraphs, each on $3$ vertices.  Now, it is known [Alon-Fischer-Krivelevich-Szegedy '99] that any such property is testable (in the property testing sense) with query complexity, independent of $n$, bounded from above by a tower of exponentials of height polynomial in $1/\epsilon$.  In particular, when $P$ is 1 only when its input is $(1,1,1)$, the property corresponds to triangle-freeness in graphs for which the best upper-bound is the tower of exp's I mentioned and the best lower bound is slightly superpolynomial in $1/\epsilon$ [Alon '01].  If you want better dependence on $1/\epsilon$ at the cost of perhaps having some dependence on $n$, I don't believe anything much better than what you described is known.  The test you described is more or less folklore.

For arbitrary fixed $S$, I don't know if the testability question has been resolved.  I believe the framework of graph limits, especially the paper [Borgs-Chayes-Lovász-Sos-Szegedy-Vesztergombi '06], might show testability for hereditary properties of weighted graphs which would imply testability of your triangle properties.  But I don't know this fact for sure.


Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

It is the case that $b \notin o( m )$.

Let $G = ( V_G, E_G )$ be a $3$-regular connected graph. Without loss of generality, let us fix $w = |V_G|$ and focus on $\Delta_{|V_G|} = O_{|V_G|} - E_{|V_G|}$.

Pick an arbitrary edge $e = \{u, v\} \in E_G$. Remove $e$ and replace it with the following gadget:

This has the effect of multiplying $\Delta_{|V_G|}$ by $8$. The resulting graph $H = (V_H, E_H)$ is still $3$-regular connected, and has $60$ vertices more than $G$.

By repeating this process $i$ times, we obtain a $3$-regular connected graph having $|V_H| = |V_G| + 60i$ vertices, and whose $\Delta_{|V_H|}$ is $8^i$ times bigger than $\Delta_{|V_G|}$.

After $i = \frac{|V_G|}{3}$ iterations, our final graph will have $|V_H| = 21|V_G|$ vertices and a $\Delta_{|V_H|}$ which is $2^{|V_G|}$ times bigger than the $\Delta_{|V_G|}$ we started with. Let $n = |V_H|$, recall how $m = 1.5n$ for $3$-regular graphs, and we get a $\Delta_{|V_H|}$ whose absolute value is lower-bounded by $2^{\frac{m}{31.5}}$. Henceforth $b$ is linear in $m$ in the worst case, and thus it cannot belong to $o( m )$.

Contrarily to intuition (at least mine), the number of edge covers of odd cardinality and the number of edge covers of even cardinality may diverge by an exponential amount.


Proving proof system properties within the proof system itself?

There is no loop. The purpose of a formal system is to make reasoning principles explicit and to explain more precisely how reasoning works. The word "foundation" in "foundations of mathematics" does not mean "create a secure base for mathematics out of nothing" – that would be an indifensible position.
There is absolutely nothing wrong with a logicians using sets to describe a formal system. Should a number theorist not be allowed to use numbers? Are logicians allowed to use strings of symbols? Where do you draw the line?
On the technical side of things, there are formal systems that can talk about their own syntax and proof rules. After all, that is the gist of Gödel's incompleteness theorems: he shows that as soon as a formal system contains arithmetic, it can speak about syntax and its own provability.


The concept of binary description by Ray Solomonoff

Later in page 10 of the pdf he explains that in fact the probabilities are almost 1/2, as there is a very small probability to stop the at each step.

This stems from the following assumption: There is some mechanism that produces these strings, and it does so sequentially, therefore going through shorter strings on its way to longer ones and having a certain probability to stop at each step.

Another explanation that was more satisfying:

These binary strings are in fact prefixes of infinite random sequences. The probability of a prefix to be 1 or 0 is of course 1/2 etc'. The machine that reads these infinite binary strings is a prefix turing machine, which means that if it produces a certain sequence, it does so by reading a prefix of the random string.


Expanding on Markus' answer a bit, note that the alphabet $\Sigma$ is in turn the powerset $2^{Prop}$ of the set $Prop=\{p_1,\dots,p_k\}$ of atomic propositions, i.e. it represents the set of valuations $a:Prop\to\{T,F\}$ of the $p_i$.

In the LTL formula, most boolean subformulas involve only a few of the propositions. In the translation, any such subformula corresponds to the set of all valuations $a\in\Sigma$ satisfying it, which is typically large. Using $\Sigma'$, you still only have one transition.

For example, Figure 1 in the paper shows an automaton with transitions labelled simply by $p$ or $q\wedge\neg r$ (where $p,q,r$ are the propositions from the formula). Using $\Sigma$, for the first you would instead have four transitions labelled $\{p\},\{p,q\},\{p,r\},$ and $\{p,q,r\}$.


Find the optimal way to use combinations of summands to get the most sum with a limited number of summands

The problem is a generalization of the set packing problem (exercise: why?), and therefore it is NP-hard even to approximate in a very weak sense.  See Maximum Set Packing and Maximum Clique in the compendium.


I think my comment was a little cryptic, so let me unpack. The key intuition behind hylomorphisms is that they let you reify the call graph as a data structure. You unfold a datastructure to build a representation of the call graph, and then you fold over the intermediate structure to consume and finish the computation.

Lists are a little misleading, because in a recursive algorithm over a list, the call graph will also form a list. However, in general this will not be the case: the call graph will have a different shape than your input data, and so you'll need to introduce a new datatype to represent it. As an example. here's your binary search example. I'll use Ocaml, since I'm more familiar with it, but it should be fairly easy to transcribe it to Haskell.

First, let's introduce a datatype of binary search trees. We'll just assume they maintain the invariant in a node Node(l, x, r) that the left subnode l contains the elements smaller than x and the right subtree r contains the elements bigger than x.

type tree = Leaf | Node of tree * int * tree

Now, let's introduce a datatype to represent the call graph of a binary search. A binary search will finish with failure if the tree is a Leaf, finish with success if you have a Node whose value is what you're looking for, and keep going otherwise.

We'll represent this with a datatype result that is either a Done b, where b is a boolean with success or failure, or else gives you a Next thunk with a computation which will give you a new result. (In Haskell, you wouldn't need the unit -> 'a thing because all datatypes are lazy.)

We'll split result into a functor resultF, and tie the recursive knot in this datatype explicitly, so that we can easily program the map functional for functor.

type 'a resultF = Done of bool | Next of (unit -> 'a)
type result = Rec of result resultF

let map_resultF f v =
  match v with
  | Done b -> Done b
  | Next thunk -> Next (fun () -> f (thunk()))

Now, we can define a fold operation for the result type.

(* val fold_result : ('a resultF -> 'a) -> result -> 'a *)
let rec fold_result f (Rec result) =
  f (map_resultF (fold_result f) result)

Here's a function that uses the fold function to force all the Next steps until you get to the boolean final answer.

(* val finish : result -> bool *)
let finish  =
  fold_result
    (fun r ->
       match r with
       | Done b -> b
       | Next thunk -> thunk())

We finally get to the interesting part. Here's the unfold operation for the result type:

(* val unfold_result : ('a -> 'a resultF) -> 'a -> result *)
let rec unfold_result f  seed =
  Rec (map_resultF (unfold_result f) (f seed))

Now, you can see how to use an integer and a tree to construct a result:

(* val mem' : int -> tree -> result *)
let mem' x =
  unfold_result
    (fun seed ->
      match seed with
      | Leaf -> Done false
      | Node(l, y, r) ->
          if       x < y then Next (fun () -> l)
          else if  x > y then Next (fun () -> r)
          else                Done true)

The really critical is that we're using the unfold to incrementally take the input, and building a result which we use to control the shape of the computation. This is where the pruning is taking place, and you can change it to whatever you like. Also, note that if you want to do something fancy (e.g., use intermediate estimates to control the pruning), you can change the result type to contain it, and update your unfold to compute it.

Finally, you can see the mem function as the fold followed by an unfold, of the result type:

(* val mem : int -> tree -> bool *)
let mem x tree = finish (mem' x tree)


What are some "must-read" papers for someone getting into Quantum Cryptography?

For an interesting starting paper, that nearly was never a paper see Stephen Wisener's paper on Conjugate Coding. This paper started off things like the BB 84. The paper is paywalled though, and a typewritten copy (with typos too,), as it was written sometime in the  60s or 70s is an interesting read, to start, or to get a historical perspective.


Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length

Introduce variables $y_{hi}$ together with constraints
$y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$ for all $h$ and $i$.
Introduce variables $z_h$ together with constraints
$z_h\ge y_{hi}$ for all $h$ and $i$.
Then minimize $\sum_h z_h$.

The resulting linear program can be solved in time polynomially bounded in $\ell, m, n$ and the logarithm of the largest cost coefficient.

(I am not sure whether you are asking for a strongly polynomial solution.
This seems to be out of reach.)


Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time algorithms (at least via Karp reductions) because it would only improve constants in the exponent of the runtime. In particular, if we reduce 3-SAT to a 3SUM instance of size $2^{O(n)}$, it will not refute ETH, and if we reduce 3-SAT to a 3SUM instance of size $2^{o(n)}$, it will refute ETH regardless of the complexity of 3SUM.
[1] Virginia V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). IPEC 2015. https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf


Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

Yes, this is known. It appears in one of the must-cite references on triangle finding...

Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most one more edge than the minimum length cycle. (See the first three sentences of the abstract here: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf) It is a simple procedure based on properties of breadth-first search.

So, if your graph is 4-cycle free and there is a triangle, their algorithm must output it, because it cannot output a 5-cycle or larger.


How to recognize safe queries in tuple relational calculus?

I attended a course on database theory some time ago, but I’m a bit rusty on the topic, so take what follows with a grain of salt.

If by “safe” you mean “domain independent”, then I think you’re out of luck: domain independence is undecidable, as unsatisfiability of relational calculus queries reduces to it.

I believe you can find the details on the slides for the above-mentioned course, and in the book Foundations of Databases by Abiteboul, Hull, and Vianu.


Polynomial Time Algorithm for Graph Isomorphism Testing

For some more discussion of this particular paper, see this thread on a related Wikipedia talk page. Some of the participants in that discussion found specific bugs, and the paper does not seem to have been updated in response. I tried to read it myself but rather than finding any specific bugs I just got lost in vague descriptions of matrices and matrix manipulations that did not make clear which variables were inputs and which were outputs. Based on that experience I don't think the paper should be taken seriously until it's passed some level of peer review (accepted to one of the usual journals or conferences).

More generally, it is easy to define algorithms for graph isomorphism that attempt to amplify some sort of subtle asymmetry in the graph to the point where it is obvious how to match the vertices to each other, and it is hard to find counterexamples for these algorithms, but that is very difficult from having a clear proof of correctness that works for all graphs.


A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. The problem is: given an edge-colored graph $G$ and an integer $k$, does $G$ have a rainbow matching with at least $k$ edges? This is known as rainbow matching problem, and its NP-complete even for properly edge-colored paths. The authors even note that prior to this result, no unweighted graph problem is known to be NP-hard for simple paths to the best of their knowledge.

See Le, Van Bang, and Florian Pfender. "Complexity results for rainbow matchings." Theoretical Computer Science (2013), or the arXiv version.


Lower bounds for Nondeterministic Multiparty Communication

After much reading, I've found the following paper

Troy Lee and Adi Shraibman. Disjointment is hard in the multi-party number-on-the-forehead model. In Proceedings of IEEE 23rd Annual Conference on Computational Complexity. June 22-26 2008.

The authors show that bounded error randomized communication is lower bounded by an approximate cylinder intersection norm $\mu_\alpha$ (cf. definition 5 in the paper).

  Theorem 6: Let M be a sign $k$-tensor, and $0\leq \epsilon<1/2$. Then $R_\epsilon^k(M)\geq \log(\mu^\alpha(M))-\log(\alpha_\epsilon)$ where $\alpha_\epsilon=1/(1-2\epsilon)$ and $\alpha\geq\alpha_\epsilon$.

Then, they make the following remark.

  Remark 7: It is nice to note that since a non-deterministic protocol induces a covering of the tensor with cylinder intersections, it follows that $\log\mu^\infty$ is a lower bound on non-deterministic communication complexity.

This answers my question. The problem now is when $\alpha\to\infty$ the authors show that for any given sign matrix $M$, $\mu^\infty(M)=1/Disc(M)$, where $Disc(M)$ is the discrepancy of $M$. It is a problem because the best lower bounds we can prove using discrepancy are polylogarithmic in the size of the input. For example, for disjointment with $k$ parties the lower bound is $\Omega(\log n/(k-1))$. In the same piece of work, the authors show that for randomized protocols, disjointment requires $\Omega(\frac{n^{1/(k+1)}}{2^{2^k}})$ using the $\mu^\alpha$ norm.

Is there any other norm stronger than discrepancy that can be used for lower bounds in nondeterministic multiparty communication? Or is it tight? These results are very recent, so maybe this is an open problem. The follow-up to this question is here.


Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

Clearly there are similarities - both kernelization algorithms and Karp reductions need to work in polynomial time and produce an output instances that is equivalent to the input instance (in the sense that both are “yes”-instances or both are “no”-instances).
But they are not the same concept, nor is one a special case of the other. First, they operate on different objects: Karp reductions deal with languages (subsets of $\Sigma^*$), while parameterized reductions deal with parameterized problems (subsets of $\Sigma^* \times \mathbb{N}$). Karp reductions (typically) go between different languages, while kernelization algorithms for a single (parameterized) problem. There are more differences, but I guess you get my drift.


What good notations for deterministic context-free and visibly pushdown languages exist?

Regarding DCFLs, I do not see a better notation than the transition function of the deterministic pushdown automaton, i.e. writing explicitly rules of form $q,z,a\to q',\gamma$ with $q,q'$ states in $Q$, $z$ a stack symbol, $\gamma$ a sequence of stack symbols, and $a$ an input symbol or the empty string.  The notation itself does not enforce determinism, but it is easily checked.  Using a context-free grammar kind of notation (as BNF), you are going to run into problems since DCFLs are a proper subclass of CFLs, and as noted by DaniCL, you cannot decide in general given a CFG whether its language is deterministic.

Regarding VPLs, a bracketed/parenthesis-style for CFGs would be good enough, with rules of form $A\to a\alpha b$ where $A$ is a nonterminal, $a$ a call symbol, $b$ a return symbol, and $\alpha$ a sequence of regular expression over mixed internal symbols and nonterminals.  Since any VPL is also a (D)CFL you could also reuse the above notation for pushdown automata and check that the stack operations match the calls and returns, or write down the transition relation of a nested word automaton (which would be less redundant).

Edit: come to think of it, a notation for XML schemas, like the compact syntax of RelaxNG---which is an ASCII notation---, could easily be used for VPLs.  You'd just need to enforce some naming conventions for tags, e.g. an opening tag "<ab>" for a call symbol $a$ matching a closing tag "</ab>" for a return symbol $b$.


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

TL;DR. The metamathematics of binding are subtle: they seem trivial but aren't — whether you deal with (higher-order) logics or -calculus. They're so subtle that binding representations form an open research field, with a competition (the POPLmark challenge) some years ago. There are even jokes by people in the field about the complexity of approaches to binding.

So, if you care about metamathematics (and most mathematicians don't), you need to deal with binding. But many mathematicians can safely treat the formalization of binding as if it were a "foundational" problem.

Another point is that binding was the only "new" problem in languages with higher-order functions, because the theory of languages with binding is just algebra (for constants) + binding. Mitchell's "Foundations of Programming Languages" actually presents things in this order and is rather enlightening.

  I'm aware of how his work paved way for λ-calculus and the impact of "it" on computing and functional programming in general. My question is mostly directed to the time "prior" to the creation of λ-calculus and "after" Schönfinkel's paper.

I must be missing something, but this remark seems to make no difference. Binding in higher-order logics and binding in λ-calculus seem as hard, so as long as people cared about higher-order logics, they had to deal with binding. I'm biased by using Curry-Howard-isomorphism-based theorem provers that implement logic by simply implementing a type theory (where types are formulas and programs are proof terms), so that I just deal with binding once.

On the other hand, IIRC, at the time indeed few cared about Schönfinkel's work — partly because of how he (didn't) publish it — the papers were mostly written by colleagues based on the research he did (see here, page 4); Curry then rediscovered the theory independently.

Caveat: I'm not an historian, but a PhD student in PL, so mine is a modern (and hopefully accurate) perspective on the topic.

EDIT:

Why is binding subtle, a bit more concretely

There are two facets to it — first, implementing it is hard. Secondly, metamathematics is the mathematics of proof manipulation: this manipulation is typically automatic, that is, it's an algorithm — so essentially, you face all the difficulties of implementation, plus making proofs about them. Below I give examples. The examples have a modern perspective — they are about actually formalized proofs. However, some of the difficulties would extend to accurate manual proofs — as long as you don't cheat on details.

This shows that Schönfinkel simply gave the first solution to this problem, but this was far from definitive.

Implementing it is subtle because of shadowing

The basic problem in implementation is shadowing. Usually one doesn't reuse the same name for different bound variables. But you can't avoid it in lambda calculus, at least because  functions (and their bound variables) are duplicated: $(\lambda f. f~1 + f~2) (\lambda x . x)$ reduces to $(\lambda x . x)~1 + (\lambda x . x)~2$. This isn't a problem yet, but starting from $(\lambda f x. f (f x))\ (\lambda g y . g~y)\ z$ gives you $(\lambda g y . g~y)\ (\lambda g y . g~y)\ z$ and then $(\lambda y . (\lambda g y . g~y)~y)\ \ z$: now you need to deal with shadowing. You can avoid this, at the cost of complicating the beta-reduction rule.

Once you have different variables with the same name, you also need to prevent capture. The simplest example of capture is that applying the function $\lambda x y. x$ (return first argument) to $y$ must not give $\lambda y. y$ (the identity function), but $\lambda y'. y$ (a constant function).

What's worse is that the counterexamples to naive algorithms are hard to construct when you know the problem already, let alone when you don't. Bugs in almost correct algorithms often lie undetected for years. I hear that even good students typically fail to come up  (on their own) with the correct definition of capture-avoiding substitution. In fact, PhD students (me included) and professors aren't exempt from these problem.

That's one reason why some (including one of the best textbooks on programming languages, Types and Programming Languages by Benjamin Pierce) recommend nameless representation (not quite combinatory logic, even though it has been used, but rather deBrujin indexes).

Proofs about it are subtle

It turns out that proofs about binding are no simpler than the implementation, as mentioned above. Of course, correct algorithms exist, and proof about them exist — but without advanced machinery, for each language using binding you need to repeat the proofs, and those proofs are simply very big and annoying if you use the definitions for binding on pen and paper.

To exemplify algorithms involved in metamathematics, consider the deduction theorem in logics, that allows composing a proof of $B$ assuming $A$ and a proof of $A$ to get a proof of $B$. To prove that theorem, you actually exhibit an algorithm that works on the syntax of the two proofs involved and produces the syntax for a proof of $B$. This algorithm needs to deal with binding.

Next, I looked up my best example of "what goes wrong if you try formalizing the standard definition". Russell O’Connor (who's on this site) formalized the first Gödel's incompleteness theorem in Coq (a theorem prover of the kind mentioned above) — and that theorem involves a logic (with all the relevant algorithms) in another logic (with the syntax of the first logic coded as numbers). He used the definitions which are used on paper and formalized them directly.
Search for "substitution" or "variable" and count how often they appear in reference to problems to get an impression.
http://r6.ca/Goedel/goedel1.html

I never use those definitions in my work, but each alternative approach has some downside.


Length bounded minimum cardinality cut in DAGs

The paper mentioned in the question uses a reduction from Vertex Cover problem to show that the length bounded cut problem is NP Hard. The instance they construct given an instance of vertex cover, is nothing but a DAG. In this case all the edge has unit weight which corresponds to the minimum cardinality case. Therefore, the problem of L-length bounded minimum cardinality cut on DAGs is NP hard.


Use $k=\lceil\log n\rceil$ random bits to get a random number $r$ between $0$ and $2^k$.  With probability at least $\tfrac{1}{2}$, $0\leq r < n$ so use that as your answer; otherwise, try again. If you've not succeeded after $t$ attempts, reject your input.  The probability of this happening is at most $2^{-t}$, which can be made as small as you like and is a component of the probability that the machine gives the wrong answer.


It depends on what you mean by "encode computation". There are many papers on the topic, a good starting reference is "Metamathematics of First Order Logic" by Petr Hajek and Pavel Pudlak. Pavel defined what is called sequential theory for theories where you can encode strings (I don't see if being a computation or not means much).

P vs. NP can be studied for other structures, first order logic with order is sufficient to phrase the question whether every $\Sigma^b_1$ formula is equivalent to a quantifier-free one (and you can enrich the language to contain all operations that you want to assume to be efficient). The strings case is old (I will add reference later). It is also studied over real numbers (in the context of BSS model).

The question can be studied over structures without order, see the work on algebraic complexity like Valiant's VP vs. VNP and also GCT (for complex numbers and other fields).


Are there any distributions with only polynomially many non-zero Fourier coefficients and a small support?

If you want $Y$ to have entropy less than $0.99 n$ bits, the answer is no, by the uncertainty principle: Either $Y$ has high entropy or its Fourier transform has large support.

Theorem. Let $H(Y)$ be the Shannon entropy of $Y$ and let $F  \subset \{0,1\}^n$ be the support of $\hat{Y}$. Then $H(Y) \geq n - \log |F|$.

Proof. Consider the collision probability of $Y$ (the probability that two independent samples of $Y$ are the same). By Parseval's identity,
$$CP(Y) = \sum_y \text{Pr}[Y=y]^2 = 2^{-n} \sum_s \hat{Y}(s)^2 \leq 2^{-n} |F|,$$ as $|\hat{Y}(s)| \leq 1$. On the other hand, $CP(Y) = 2^{-H_2(Y)}$, where $H_2(Y)$ is the Renyi entropy of $Y$. Noting that $H_2(Y) \leq H(Y)$ gives the result. Q.E.D.

If $|F| = \mathrm{poly}(n)$, then $H(Y) = n-O(\log n)$. So, if $Y$ is the output of a pseudorandom generator, the seed length is at least $n-O(\log n)$.


Operations on a database are divided into DDL and DML.

DDL are operations that alter the structure of the database. This includes creating/dropping tables, constraints, indexes, packages, views, dblinks, adding or removing columns to a table, changing object names and so on.

DML are the operations that alter the data stored in the database. This includes inserting, deleting and updating rows to/from a table.


Which $AC^0$ problems are not "truly feasible"?

If you want an example of an AC0 function that requires depth $d$, and cannot be computed by AC0 circuits of depth $d-1$, then try the Sipser functions $S^{d,n}$. The superscript $d$ is depth needed for a polynomial-size AC0 circuit. With depth $d-1$, the circuit would need exponentially many gates.

So computing $S^{d,n}$ for $d = 10^{10^{100}}$ would not be "truly feasible."

EDIT: Your question also asks why this would not be feasible. I guess the reason is that $10^{10^{100}}$ is more than the number of atoms in the visible universe.


How fast can we compute the set inclusion poset of a set family?

If randomness is in bounds, one rough idea would be to generate a bunch of "random monotonic signature" functions and use them to approximate the subset relation (a la Bloom filters).  Unfortunately, I don't know how to make this into a practical algorithm, but here are some estimates that don't immediately prove the idea impossible.  This is very far from a useful solution, but I'll write it out in case it helps.

Assume for simplicity that the sets are all nearly the same size, say $|S| = s \pm O(1)$, and that $s = o(u)$.  We can assume $1 \ll s$, otherwise we're done.  Define
$$\begin{aligned}
q &= [s/2] \\
p &= \left[\frac{u \choose q}{s \choose q}\right]
\end{aligned}$$
Note that $p \gg 1$.

Here is the wildly impractical part.  Randomly choose $p$ subsets $A_1, \ldots, A_p \subset U$ with replacement, each of size $q$, and define a function $f : 2^U \to \{0,1\}$ by $f(S) = 1$ iff $A_i \subset S$ for some $i$.  With $S$ fixed and $A_i,f$ varying randomly, we have
$$\begin{aligned}
\Pr(f(S) = 0) &= \Pr(\forall i. A_i \not\subset S) \\
              &= \Pr(A_1 \not\subset S)^p \\
              &= \left(1 - {s \choose q}/{u \choose q}\right)^p \\
              &= e^{-\Theta(1)}
\end{aligned} $$
Since $f(S)$ is monotonic, $S \subset T$ implies $f(S) \le f(T)$.  If $T \not\subset S$, fix some $t \in T-S$.  The probability that $f$ detects $T \not\subset S$ is
$$\begin{aligned}
\Pr(f(S) = 0 < 1 = f(T)) &= \Pr(f(S) = 0) \Pr(f(T) = 1 | f(S) = 0) \\
&= e^{-\Theta(1)} \Pr(\exists i. A_i \subset T, A_i \cap T-S \ne 0 | f(S) = 0) \\
&= e^{-\Theta(1)} \Pr(\exists i. t \in A_i \subset T | f(S) = 0) \\
&\le e^{-\Theta(1)} \Pr(\exists i. t \in A_i \subset T) \\
&\approx e^{-\Theta(1)} p \Pr(t \in A_1 \subset T) \\
&\le e^{-\Theta(1)} p {s \choose q-1} / {u \choose q} \\
&\approx e^{-\Theta(1)} p \frac{q}{s-q} {s \choose q} / {u \choose q} \\
&= e^{-\Theta(1)}
\end{aligned}$$
Some of those steps are pretty tenuous, but I don't have time to improve them tonight.  In any case, if they all hold, then at least it's not clearly impossible to randomly generate signature functions that have reasonable likelihood of distinguishing subsets from nonsubsets.  A logarithmic number of such functions would then distinguish all pairs correctly.  If generating a signature function $f$ and computing $f(S)$ could be reduced to $\tilde{O}(n+u)$ time, the result would be an overall $\tilde{O}(n^2+u^2)$ algorithm.

Even if the above calculations are correct, I have no idea how to generate monotonic signature functions with the desired features quickly.  It's also likely that this technique doesn't extend to significantly different set sizes.


What's the effect of imposing the following restriction on inductive type families?

This is not a real restriction to the power of the language

First, it is possible to turn all indices of the type family into variables by adding extra arguments to the constructor expressing the constraints. For example, Test can be turned into

data Test a where
  Foo :: Integer -> a = Color -> Test a
  Bar :: Float   -> a = Sign -> Test a

Second, you can define your own version of the propositional equality as an inductive family and use that instead of the built-in one.

data Eq :: * -> * -> * where
  Refl :: Eq a a

This definition follows your restrictions, but it won't be detected as being 'the' identity type. (In case you want to build in some kind of detection for identity-like types, I'd guess that the property of being identity-like may well be undecidable.) So there is nothing that you can do without your restriction that you couldn't do with it in a (somewhat) more complicated way.


Is every well-founded simplification order a well-partial order?

Every simplification order is indeed a well-partial order because of this simple statement:

  If $R$ is a well-quasi order, and $S$ is a partial order, and $R\subseteq S$, then $S$ is a well-partial order.

Proof: Exercise. Note that this nice property is not true for well-founded orders in general! In this sense, well-quasi orders are much more "stable". It's often the case that a stronger property is better behaved, even if the weaker property is what we want to prove at the end (well-quasi orderdness vs well-foundedness in this case).

Since every simplification order contains the homeomorphic embedding, it is indeed a WPO.

Your more precise statement is correct: we could directly prove that a simplification ordering is a WPO by re-producing the proof for the homeomorphic embedding, but this is not necessary because of the above statement, which shows that it suffices to prove the statement for the "minimal" such ordering.


Tight examples for approximating the feedback vertex set problem

I think you can make the classical local ratio algorithm by Bafna et al. give a $2-o(1)$ approximation on the following family of graphs:

Take $G_n$ to be a $K_{n,n}$ (the complete bipertite graph with $n$ vertices on each side), and then delete a single edge.
The following shows that the algorithm might output all of the "blue" vertices ($2n-4$ in number) as the FVS approximation, while there's a much smaller FVS for $G_n$.

(notice there's no edge between the teal vertices).

The optimal FVS is contains $n-1$ vertices (take all of the vertices on the right, except the top one).

Now there are no semi-disjoint cycles, and the vertices degrees are as follows:

Blue / Purple vertices - degree $n$.
Teal vertices - degree $n-1$.

This means that the all of the blue/purple vertices will be inserted first into the stack at arbitrary order (the teal vertices enters the stack at the end and are the first to be deleted from $F$).

Assuming that the purple vertices will pushed after (and popped before) the blue ones, they will be removed from $F$ which will be updated to contain all of the blue vertices.

From this point on, no other vertex can be deleted from $F$ (otherwise there will be a cycle using the teal/purpule vertices), and the resulting $FVS$ has size $2n-4$.

This gives us a $\frac{2n-4}{n-1}=2-o(1)$ approximation ratio, hence showing the analysis is tight even for the unweighted case.


Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)

Group Isomorphism! Although Ricky Demer gave lots (though certainly not all) details on this, there is an important point I want to highlight, esp. given the stated motivation for the question, namely:

  Putting Group Isomorphism into $\mathsf{P}$ is a key obstacle to putting Graph Isomorphism into $\mathsf{P}$

Group Isomorphism (when given by multiplication tables) reduces to Graph Isomorphism, so the above was technically always true. But when Graph Iso was way up at $2^{\tilde{O}(\sqrt{n})}$ it was so far from Group Iso's $2^{(\log n)^2}$ that there were clearly other obstacles in the way. If Graph Iso is in time $2^{(\log n)^{O(1)}}$, Group Isomorphism is then a much more immediately relevant obstacle to putting Graph Isomorphism into $\mathsf{P}$. In particular, this would suggest that Babai's algorithm handles much [1] of the combinatorics of GI, and the problem is now down to hard algebra. (Not that there's not hard algebra in GI, but GroupIso is by definition about algebra.)

[1] I won't say "all" of the combinatorics, because the exponent in Babai's algorithm is most likely $> 2$, which would still leave a gap between GI and GroupIso. Also because there may still be some combinatorics sitting inside the algebra of GroupIso...


Abstract algebra for Theoretical Computer Scientists

You could try the notes from Madhu Sudan's course: Algebra and Computation


Optimal bounds for $k$-wise non-uniform random bits

$$s = \Theta( k \cdot ( t + \log n ) )$$

As the question mentions, there is an upper bound of $s \le k\cdot\max\{t,\lceil \log_2 n \rceil\}$ bits for the seed length. Specifically, sample a random polynomial of degree $<k$ over a field of size $2^{\max\{t,\lceil \log_2 n \rceil\}}$, and evaluate it at $n$ points. This produces $k$-wise independent field elements which can easily be turned into bits with the appropriate bias.

There is also a trivial $s \ge k \cdot t$ lower bound: Just look at the first $k$ bits of the output. These will all be $1$ with probability $2^{-k \cdot t}$. Generating an event with precisely this probability requires a seed of $k\cdot t$ bits.

To characterize the required seed length up to constants, all that remains is to prove a lower bound of $s\ge \Omega(k \log n)$ bits in the setting of $t \le o(\log n)$. Assume for simplicity that $k$ is even.

Let $X$ denote the distribution in question and let $x$ be an arbitrary point in its support. We have $\Pr[X=x]\ge 2^{-s}$ where $s$ is the seed length. Thus an upper bound on $\Pr[X=x]$ entails a lower bound on the seed length.

Define $Y = \sum_{i=1}^n \mathbb{I}[X_i \ne x_i]$. Then $X=x \iff Y=0$ and $\mu:=\mathbb{E}[Y] \ge n \cdot 2^{-t}$. Thus, by Markov's inequality and a Bernstein moment bound (e.g., Eq. 10 in SSS06 or this answer), $$2^{-s} \le \Pr[X=x] \le \Pr[|Y-\mu|\ge \mu] \le \frac{\mathbb{E}[(Y-\mu)^k]}{\mu^k} \le \frac{O(k\mu)^{k/2}}{\mu^k} = O\left(\frac{k}{\mu}\right)^{k/2} \le O\left(\frac{k}{n \cdot 2^{-t}}\right)^{k/2}.$$
This rearranges to $s \ge \frac12 k \cdot \left( \log_2 n - t -\log_2 k - O(1) \right)$. If $t=o(\log n)$ and $k=n^{o(1)}$, this is the desired lower bound.

In summary,

  $$k \cdot \max\{t,\lceil \log_2 n \rceil\} \ge s \ge k \cdot \max\left\{t, \frac12 \cdot \left( \log_2 n - \log_2 k - t - O(1) \right) \right\}.$$

The only room for improvement on this bound is in the constants (or the regime where replacing $n$ with $n/k$ makes a difference). However, if we only need a distribution that approximates the requirements, then I believe we can achieve better seed length (depending on the nature of the allowed approximation).


Hardness jumps in computational complexity?

One of the more interesting applied examples of hardness jumps can be observed in the following problem:

Consider a soccer league championship with $n$ teams: The problem of deciding whether a given team can (still) win the league is in $P$ if in a match, the winning team is awarded 2 points, the losing one 0 and each team is awarded 1 point in a draw match. But if we change the rules so that the winning team gets 3 points, the same problem becomes $NP$-hard.

The result can be generalized for any $(0, 1, k)$-point rule for every $k > 2$ and even for only three remaining rounds.

Source: “Complexity Theory” by Ingo Wegener (http://portal.acm.org/citation.cfm?id=1076319)


Bounds on the size of smallest decision tree for a boolean function?

I think the number of true points isn't a good measure to say anything about the size of the smallest decision tree.

There is a chapter in Branching programs and binary decision diagrams: theory and applications by Ingo Wegener about the size of decision trees for boolean functions.

The size of the smallest DT is determined up to constant factors by the number of leaves of the tree. There is a lemma in the book that says: If you have a DT for a function $f$ with $s_0$ 0-leaves and $s_1$ 1-leaves then $f$ can be represented by a DNF with $s_1$ monomials and a CNF with $s_0$ clauses. So even if you have a function with only a small number of true points, the size of the smallest DT could be very large. So you need small size of CNF and DNF to have a small DT size.

There is a upper bound of the DT size with respect to the sum of the minimal number of monomials of $f$ and the minimal number of monomials of $\overline{f}$. Lets call this sum $DCNF(f)$. Then you have the following upper bound for the number of leaves $DT(f)$ of the smallest DT for the function $f: \lbrace 0,1 \rbrace^n \rightarrow \lbrace 0,1 \rbrace$
$$ DT(f) \leq n^{O(log^2 DCNF(f))}. $$


Maximum clique algorithm on undirected graph


Combinatorial Expansion implies Algebraic Expansion

If we have combinatorial expansion, then the second eigenvalue (without taking absolute value) is not too large (or, equivalently, second eigenvalue of the Laplacian is not too small) no matter what (that is, regardless of bipartiteness or having self-loops or even all vertices having the same degree, if notions are defined properly). See the proof of Cheeger's inequality, for example here:

Spielman's lecture notes on Cheeger's inequality.


Complexity of Uniform Generation of Perfect Matchings

In [1], the author presents an acceptance/rejection algorithm for generating a uniform sample from the set of perfect matchings of a bipartite graph. While the samples are exactly uniform regardless of the structure of the graph, the run-time is only guaranteed to be polynomial if the graph has a particular structure -- essentially, if the degree of each node is $\gamma n \pm O(log (n))$ for some constant $\gamma$.

Huber, Mark. Exact sampling from perfect matchings of dense regular bipartite graphs. Algorithmica 44.3 (2006): 183-193.


Finding the perfomance ratio in a multicommodity-flow

$f_i$ are constant real numbers. They stay the same over the entire path. But note that the paths are not necessarily edge-disjoint. So an edge could be present in multiple paths and hence the actual flow in that edge will be sum of all the corresponding path flows.
For a path $P$, let $cap(P)$ denote the smallest edge capacity in the path. A thickest path is a path $P$ with largest $cap(P)$ (imagine the edges as pipes and capacity defining the thickness of pipe). A bottleneck edge of path $P$ would be an edge with capacity $cap(P)$. After sending a flow $f_1$ on $P_1$, in the corresponding residual graph, let $P_3$ be a thickest path. If the residual capacity of the bottleneck edge is $0$ (i.e., maximum $cap(P)$ value is $0$ over all paths), then no more flow can be sent from $s$ to $t$. But this implies $f_1 \geq f_1^* + f_2^*$ contradicting the assumption that $f_1 \lt f_1^* + f_2^*$.
While constructing this new graph $G^\prime$, edge capacities were reduced to smallest values that allowed the flow $f_1$ to be feasible and the flows $f_1^*$, $f_2^*$ to be feasible. Suppose $e$ is not present in one of the two paths (say $P_1^*$). Then the capacity on edge $e$ must have been reduced to $f_1$ (as $f_1 \geq f_2^*$), resulting in zero residual capacity. So $e$ must be present in both the paths $P_1^*$ and $P_2^*$.
When we say something is $(1/r)$-integral, it means the values involved are integral multiples of $1/r$ (so standard integral solution will be $1$-integral). Here, $D/k$ integral flow means that each edge has a flow which is an integral multiple of $D/k$.
Using lemma $1$, if we have a flow $f_1+f_2$ obtained through two augmenting path iterations, then this flow can be written as sum of $3$ paths with flows $f_1^ \prime ,f_2^ \prime ,f_3^ \prime $. So we have $f_1^ \prime +f_2^ \prime +f_3^ \prime = f_1 + f_2 \geq f_1^* + f_2^*$, where $f_1^* + f_2^*$ is a maximum 2-splittable flow (from lemma 2). Suppose $f_3 ^\prime$ is smallest among $f_1^ \prime ,f_2^ \prime ,f_3^ \prime $. Then $f_3^\prime \leq (1/3) (f_1^ \prime +f_2^ \prime +f_3^ \prime )$. So taking the two paths corresponding to $f_1^\prime$ and $f_2^\prime$, the net flow is $f_1^ \prime +f_2^ \prime \geq (2/3)(f_1^ \prime +f_2^ \prime +f_3^ \prime ) \geq (2/3)(f_1^* + f_2^*)$. So this gives a $\frac{2}{3}$-approximation.

I am not able to see why lemma $1$ is true. Do you have any simple proof for that?


Testing for positivity instead of equality

This is known as Greater-Than problem in communication complexity. An algorithm with $O(\log n) $ communication complexity exists (Exercise 3.18 in Nisan-Kushilevitz book).

Edit: The algorithm is due to Nisan (page 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf

It uses the approach suggested by @Sasho Nikolov below --- running a binary search using equality tests with constant error to do the comparisons. This can be done with $O(\log n)$ queries using the "noisy binary search algorithm" by Feige, Peleg, Raghavan and Upfal: http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdf

To get a (non-explicit) private randomness protocol one can apply the result of Newman: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf


Rapidly mixing Markov chains on 3-colorings of a cycle

I got the following solution by email from Dana Randall, so any credit for the solution should go to her (which I guess means: don't upvote this answer) and any bugs were likely introduced by me.

The short version of Dana's solution is: instead of using the Markov chain I described, in which potentially-large two-colored regions are recolored, use a "heat bath" in which we repeatedly remove the colors of two vertices and then choose a valid coloring for them at random. It's not hard to show that, if this chain mixes, then the other one does as well. But a standard path coupling argument turns out to work to show that the heat bath does indeed mix.

The long version is too long to include here, so I put it in a blog post instead.


Average height of the least common ancestor of 2 random nodes in a binary tree

It took me a while to see the nice formula, but there is one.
Consider a node $w$ at height $k$. The root is at height $h$ and the leaves at height $1$.

The probability that $w$ is the least common ancestor of the two nodes is the probability that:

  (1) Both random nodes are in the subtree rooted at $w$;

and we do not have that

  (2) Both nodes are in $w$'s left subtree or both nodes are in $w$'s right subtree.

The size of a subtree at height $k$ is $2^k-1$.
The probability of #1 is therefore $\left(\frac{2^k-1}{2^h - 1}\right)^2$. The probability of #2 is $2 \left(\frac{2^{k-1}-1}{2^h - 1}\right)^2$.

The probability of the event that #1 happens and #2 does not (since #2 is a subset of #1) is thus
\begin{align}
\Pr[\text{$w$ at height $k$ is lca}] &= \frac{\left(2^k-1\right)^2 - 2\left(2^{k-1}-1\right)^2}{\left(2^h - 1\right)^2} \\
&=\frac{2^{2k-1} - 1}{\left(2^h -1 \right)^2}
\end{align}
once you work it out. (You can check that these probabilities sum to $1$.)

There are $2^{h-k}$ nodes at height $k$. So the probability that the lca is at height $k$ is $\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2}$.

The expected height is thus
\begin{align}
  &\sum_{k=1}^h (k)\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2} \\
  &\approx \sum_{k=1}^h \frac{(k)\left(2^{k-1} - 2^{-k}\right)}{2^h} \\
  &\approx h - 1 - \Theta\left(\frac{1}{2^h}\right) .
\end{align}
Simulations bear this out up to three decimal points anyway. By the way, this is very easy to simulate: Suppose the nodes are numbered $1,2,\dots, 2^h - 1$. Pick two random numbers from this range. Now each node $x$'s parent is $\lfloor \frac{x}{2} \rfloor$. To find the lca of two numbers, continue halving (and rounding down) the larger number until they are equal. To find the height of a number, continue halving (and rounding down) until it is one and count the steps. So if your random number generator is comfortable giving you random numbers in the range $[1,2^{100}]$ (as python's seems to be) then you can simulate easily.


NP-Completeness of Finding Minimum Automaton, in Gold's paper

After more and more digging, here is what I found:
First reference: Introduction to Automata Theory, Languages, and Computation 3rd Edition.
Specifically, theorem 4.26 indicates that the provided algorithm constructs a minimum state machine M for a A such that M has as few states as any DFA equivalent to A.
This was my original understanding, so the answer is "NO" to the pre-question.
Second reference: Grammatical Inference: Learning Automata and Grammar
First question:
This book was excellent source for my understanding. It turns out, Gold's construction does not necessarily "EXACTLY" fit the data. The data may be a subset of of the inferred automaton, and this is a key reason as to why eventually, identification in the limit can happen, so ab(ab*)* can be learnt, eventually, but we can never tell we learned it until we wait for ever (I see this as a halting problem sort of issue)
Second question:
The confusion occurred from the meaning of "consistent". The construction used in the paper has "holes" where an "experiment" is not known to accept or reject a string at that "point in time". It is difficult to summarize a whole chapter here, but what ends up happening is "consistent" does not mean "EXACT". Eventually, identification in the limit produces "EXACT" fit for "historical" and "future" experiments.
The reason why identification is NP-Hard is due to the holes in the algorithm. At some point a value is assumed to fill the holes, but based on the value, some inconsistency may arise, and a parsing tree is returned instead (which has large number of states). The other option is to use backtracking to implement nondeterminism and try different values (or run this in parallel...) to find the reduced automaton.
Since the algorithm is non deterministic and can find the correct consistent minimum automaton, finding the minimum automaton from data, in the limit, is NP hard.
Some Final Remarks
If we have a "complete" finite log, we can find the minimum automaton in P.
Then one may ask, what if we generate lots of experiments before we attempt to find an automaton, and assume that the log is complete?
The answer is:
If the log was indeed complete, then an algorithm in P can find the minimum state. Otherwise, the algorithm did not find the minimum state.
I believe this makes the question: "Is the Log Complete?" to be the problem here, because if we can answer that with a YES, then identification of automata from finite data would be possible (not in the limit...), which is not possible.
One way to circumvent this is to add domain knowledge, such as having an upper bound on the number of possible states.


Random restrictions and the connection to total influence of Boolean functions

Claim: If $\delta$-random restriction of $f$ has decision tree of size $O(1)$ (in expectation), then the total influence of such $f$ is $O(\delta^{-1})$.

Proof sketch:
By definition of influence we have
$Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)]$.
Let us upper bound $\Pr_{x,i}[f(x) \neq f(x+e_i)]$ by first applying a $\delta$-restriction, then picking $i \in [n]$ among the remaining coordinates, and fixing at random everything except for $x_i$.

Now, if $\delta$-restriction reduces the decision tree of $f$ to size $O(1)$,
then in particular the $\delta$-restriction of $f$ depends on $r = O(1)$ coordinated.
Let us now pick one random unfixed coordinate (among $\delta n$), and fix all others randomly. Since the $\delta$-restriction of $f$ depends on at most $r$ coordinates, we get a function (on one bit) that is not constant with probability at most $\frac{r}{\delta n}$.
Therefore $Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)] \leq \frac{r}{\delta}$, as required.

Remark: The claim above is tight by taking a parity function on $O(1/\delta)$ bits.


Max flow with restriction of individual flows

That constraint is linear, so the entire problem is an instance of linear programming, thus can be solved in polynomial time.  (I am assuming there is no restriction or requirement for integer flows.)

In general if you allow arbitrary constraints, the problem can become NP-hard.


Subquadratic 3SUM when one set is in [n^1.99]

I think one can solve this problem as follows. Assume that we have three sets $A, B, C$ of integers, $|A|=|B|=|C|=n$, and $C\subseteq [n^{2-\delta}]$. We want to check whether there exist $a\in A, b \in B, c \in C$ such that $a+b+c=0$.

First, we partition the set $A$ into $k\leq n$ sets $A_1,\ldots A_k$, where each $A_i$ contains numbers in an interval of length $n^{2-\delta}$. Now from the set $B$, we construct sets $B_1,\ldots, B_k$ as follows. $B_i$ contains numbers from $B$ in the interval $[-n^{2-\delta}-\max_{a \in A_i}{a}, -\min_{a\in A_i}a]$. This way each number from $B$ appears in at most two sets $B_i$. And now we only need to check whether for some $i$ there exists a solution in $A_i + B_i + C$.

Let $a_i=|A_i|$, $b_i=|B_i|$. If $a_i\geq n^{1-\delta/2}$ or $b_i\geq n^{1-\delta/2}$, we solve $A_i+B_i+C$ by FFT in time $O(n^{2-\delta}\log{n})$. (Because numbers in all three sets lie in intervals of length $O(n^{2-\delta})$.) Since $\sum_i a_i=n$ and $\sum_i b_i\leq 2n$, the total number of such $a_i$ and $b_i$ is at most $3n^{\delta/2}$, which means that the running time of this step is $O(n^{2-\delta/2}\log{n})$.

For the remaining values of $i$, we solve the problem by trying all $a\in A_i$ and $b \in B_i$, and looking up their sum in $C$ in logarithmic time. This step takes time $\sum a_i b_i \log{n} \leq O(n^{2-\delta/2}\log{n})$. (I believe one can shave off the $\log{n}$ factor here by using the standard 3-SUM trick.)


What is the right theoretical model to design algorithms for current and upcoming high performance computers

At PODC 2009, Bruce Hendrickson gave a phenomenmal invited talk about these issues.  (His slides don't appear to be online, but you might want to ask him if you could see them.)  I don't think there's a "right" model yet -- bonus for you! -- but I would suggest you look at his papers, especially the ones on the Graphs and Architectures page, where he tries to figure out how to handle enormous graphs with little structure (i.e. "modern" datasets) on massively multithreaded machines.


Support Vector Machines and privacy-preservation

Before giving some detail, I'll briefly say: regarding (1), kernel trick is basically the worst thing for privacy, and regarding (2), you have replaced each vector with a vector of kernel products (via the linear kernel), and this is non-equivalent to replacing inner products with kernel products inside the algorithm.

Some background on (1) for those who asked.  Suppose you want to learn a linear predictor; among those consistent with the data (i.e. correct on all examples), which do you choose?  The SVM solution is to pick the one which maximizes the minimum distance to any example (maximizes the 'margin').  In the case that no consistent predictor exists, small penalization is assigned to margin violations (learning the best linear predictor, in the presence of noise, is NP-hard).

now say your data is a set of records for some group of people (for instance, each "point" is a vector of medical parameters for some person).  You want to release a predictor (say, a website where someone can put in some info and see if they have some disease or not), but don't want anyone to be able to reconstruct properties of the people in your data set.  Here's an example; let's say I know someone is the only person in some remote part of saskatchewan, and I want to see if they were used to learn this predictor.  And say, one of the attributes in the web form is location.  For privacy ignorant algorithms, I can see how sensitive the algorithm is to queries with this personal data, and infer things about the person in question (for instance, if saying I'm from remote-part-of-saskatchewan but varying all other parameters always says I have the disease (and the answer is sensitive to location), that means that guy has the disease).  Said another way, if I know some unique characteristics of a person, I can see how the algorithm reacts to them in order to determine other properties of that person.

Anyway, here's why the kernel trick is the worst thing for this.  The kernel trick just means you store your predictor as
$$
p(x) = \sum_{i=1}^m a_ik(v_i, x),
$$
where $\{v_i\}_1^m$ are your support vectors.  This means the predictor for any kernelized linear classifier (not just SVM) will explicitly store a set of records!  Therefore, if you manage to plug in a support vector for $x$, you can
expect it to strongly affect the value of the predictor.  Going back to the remote-part-of-saskatchewan example, suppose the kernel is gaussian, and you fix all other parameters, and see the effect of the saskatchewan input.  Since distances are all huge in high dimension, that means, if the guy is in the dataset, the predictor value will be strongly affected by matching the remote-part-of-saskatchewan fields or not.  Thinking geometrically, each support vector plops a gaussian in the space (color them white or black based on their label), and if this guy is really the only person in that remote part of saskatchewan (and if he was a support vector), that means his gaussian will basically entirely control the value of the predictor.

EDIT. I should say that research in privacy preserving learning is all about taking privacy-ignorant algorithms and making them output privacy-secure predictors.  There are definitely strategies to make kernelized algorithms more privacy preserving--for instance, don't let any region of the space be "covered" by just one support vector (some sort of smoothness condition, i.e. how much the predictor is affected by removing or adding in this example); this in turn usually means.. have TONS of support vectors.  Another strategy is to inject perturbations in places, but notice this is delicate--if you just perturb this saskatchewan record, it is still basically the only gaussian in that region of space, so you've done nothing.  Anyway all I am saying is that kernelized algorithms are a difficult starting point for privacy preservation.  (and the "have TONS of support vectors parts" starts to mitigate the benefits of the kernel trick..)

About (2).. let $A$ contain all points as columns; a linear predictor can be written as
$$
p(x) = x^\top Av
$$
where $v$ is a vector of weights (in the linear case, you can "compress" this and just keep weights $w=Av$ around).  (to be explicit, you also check the predicate $p(x)\geq 0$.)  In your case, you have replaced $A$ with $AA^\top$, and also you must map any input vector $x$ to $Ax$, thus your predictor is
$$
p'(Ax) = x^\top A^\top AA^\top v'.
$$
For general matrices $A$, it is possible that some choice $v$ does not have a choice $v'$ which makes these equivalent...... thus, this is not the same as simply "kernelizing" the algorithm.

That said, it is reasonable to replace your data with kernel products in this way, but that is a feature selection issue; i've attempted to discuss the math part...........


Inferring optimal utility values from a decision process

You might want to have a look at Inverse Reinforcement Learning. IRL tries to infer a reward function given observed optimal behavior in some MDP. I believe the framework was originally described in the 1998 paper Learning agents for uncertain environments by Stuart Russel. This paper and and those that cite it should be a good place to start, assuming IRL is a good fit for your problem.


A direct-sum theorem for the non-deterministic communication complexity of inequality?

I think this can be done with $\log n \cdot\log t + t \cdot\log\log t$ bits of nondeterministic communication.

By encoding all strings with an error correcting code, we may assume that whenever we have an input pair $(x,y)$ with $x\neq y$ the two strings differ in a constant fraction of coordinates. Suppose we are given $t$ pairs $(x^j,y^j)_{j\in[t]}$ that we want to certify are all nonequal. By averaging, there is some coordinate $i\in[n]$ that witnesses $x^j_i\neq y^j_i$ for a constant fraction of $j\in[t]$. Iterating this argument we may construct a set $S\subseteq[n]$ of about $|S|=\log t$ coordinates such that for every $j$ there is some $i\in S$ such that $x^j_i\neq y^j_i$. The nondeterministic proof consists of $S$ (which is $\log t\cdot \log n$ bits) and a mapping $[t]\to S$ (which is $t\cdot\log\log t$ bits) that indicates which coordinate in $S$ to use for each of the $t$ input pairs.


"The Solution Problem" - How to get credit for your work as an undergrad?

Worrying about someone taking credit for your work is very common among amateurs and people just starting out, but in my experience is far less common with more experienced researchers. I'm not really sure exactly what the reason for this is, but I have encountered this phenomenon numerous times. I would venture that it is perhaps because those with more experience in the field know how uncommon it is for one person to essentially steal another's results. Most people are relatively good, or at worst benign, and wouldn't dream of taking credit for work they haven't contributed to. Couple that with the fact that being caught plagiarizing someone else's work would be career suicide, and you can be pretty confident that no one you talk to is likely to write up your idea and pass it off as their own.

As Suresh says, you could always upload it to the arxiv, but I would be inclined not to do this, as if it turns out that the work is not novel or there is a major error, then you cannot actually delete the paper, but rather will have to post a retraction, and the original will still be there for all to see. Even now, I still ask colleagues to check any paper I consider relatively important before uploading a manuscript.

If I were you, I would be inclined to talk to one of my lecturers in the first instance, as they can probably give you a feel for whether your solution is novel (and correct), and if it meets both of these criteria, they should be able to give you an idea of how best to proceed. Alternatively, you could just post it as a question here, asking if the result was previously known, or if anybody could point you to a good survey paper on the problem. You'd have a time stamp from the post time, so you wouldn't have to worry about that. If you got an encouraging response here (i.e. that it was not currently known), then you could consider how to proceed from there. If on the other hand, it was already known, or there was a flaw, then it wouldn't really matter.

Technically, you could also simply write it up and submit it to a journal. As Dave says, no one involved in the process will actually know your level (the first time, it's kind of a kick when you get the correspondence addressed to you as either Dr. or Professor), unless one of the reviewers happens to know you personally. However, I would not suggest doing so. You need to search the literature to make sure your idea is actually novel, and as Dave mentions, the writing of papers is an art in and of itself. You would probably need to read a lot of journal articles to even get the style right.


Proof-techniques for the hardness of optimization problems (esp. Polynomial time)

Regarding question 2, there are at least two other classes of matrices that give integral polehydra: the balanced and totally balanced matrices. When available, these properties are simpler to establish than total unimodularity.

I'm not sure about question 1: your first paragraph seems to contain the answer, but after closer inspection I realize that total unimodularity yields integral polyhedras for arbitrary budget vectors. As Linear Programming is not known to be strongly polynomial, I suspect that you won't get polynomial time with an arbitrary integral budget that is binary-encoded (but it works say for a 0,1-budget vector).

You can find some relevant lecture notes online; some textbooks might be useful too (such as "Combinatorial Optimization" or "Hypergraph Theory: An Introduction").


If you model a box as a point $(b_1,b_2, \ldots, b_d)$, and you define the dominance relationship $p \prec q$  $\iff$ $p_i < q_i$, for all $i$, then you are looking for the longest chain in this partial order. In $d$ dimensions this problem can be solved in $O(n \log^{d} n)$ times, I believe.
I would sketch a somewhat inferior solution, because it is late.
To see how to do it, consider the two dimensional case. For a point $p$, let $||p||_1 = |x(p)| + |y(p)|$. Consider the input points, $p_1, \ldots, p_n$, and observe that $p_i \prec p_j$ only if $||p_i||_1 < ||p_j||_1$. As such, sort the points by their $L_1$ norm, in increasing ordering, and let $p_1,\ldots, p_i$ be the points handled so far, where for each $p_j$, $j=1,\ldots, i$, we computed $\ell(p_j)$ -- the length of the longest path in the relation that ends at $p_j$. We add the extra dimension $\ell(p_j)$ to the point $p_j$, so that this is now its third coordinate.
Now, given a new point $p_{i+1}$, we need to compute the highest point (in the third dimension) that it dominates (in the first two dimensions) -- this is an open quadrant question, and can be solved in $O( \log^{O(1)} n)$ time using orthogonal range searching techniques. Assume you get the point $p_k$ as returned by the query -- we have that $\ell_{i+1} = \ell(p_{i+1}) = \ell(p_k)+1$. We need to insert this new point $(p_{i+1}, \ell_{i+1})$ in the the orthogonal range searching data-structure.
Thus, you can handle each point in $O(\log^{O(1)} n)$ time which readily implies that you can compute the longest chain in $O( n\log^{O(1)} n)$ time. Being more careful about the details, the running time can be improved to $O(n \log n)$ in two dimensions.
I have a paper on a related problem here:
https://arxiv.org/abs/1910.07586
I think a solution for your problem should be readily implied by some previous work.
More maybe later...


As far as I know, there is no "right" or "only" way of associating operations of theorems to mathematical structures. Certainly there is no canonical way, and even on paper you often see sentences such as "we write foo instead of foobar when no ambiguity occurs". Even this does not prevent misunderstandings, and often clarification by the author or guesswork by the reader is required.

There has been a lot of work in disambiguating mathematical statements of the kind you describe, especially in mathematical proof assistants like Coq, Isabelle, Mizar, etc., but there are many annoyances in practice, and a lot of compromise to design a disambiguation system which insures:

Inferring reasonable statements, i.e. $1+\pi$ should be easy to recognize as a real number
Acceptable performance, i.e. $1+1$ in $\mathbb{N}$ should be recognized nigh-instantaneously, even as part of a much larger expression
Understandable error messages, i.e. $\pi+\mathbb{Z}$ should fail because $\mathbb{Z}$ is not (coercible to) a real number, rather than some crazy failure involving additive structure on quotient sets.

I can't understate how important (and difficult) point 3 is: experimentally, it's better to fail predictably than succeed in a bizarre manner, as I'm sure Scala users are aware.

Another issue is that notations like $+$ and $\cdot$ are often used to describe abstract operations like commuative monoids, but also concrete operations on the sets that support them, so if you want to write
$$ \forall\ x\ y\ z,\ (x\cdot y)\cdot z=x \cdot (y\cdot z)$$
for any monoid, you have to imagine instantiating $\cdot$ by addition in the naturals.

In general, the idea of applying an operation to a whole structure rather than just the carrier set is called the bundled approach, and it is mostly used in the mathematical components library which was used in the recent formalization of the Feit-Thompson theorem in Coq.

One big disadvantage of the bundled approach is that, as you noticed, mathematical sets often carry a great deal of structure, e.g. $\mathbb{R}$ is a group, and a ring and a field (as well as a topological space, and a great many other things) and one wants to exploit the knowledge that the additive group operation of $\mathbb{R}$ is the same as the $+$ operation of the ring, and that the order $\leq$ is compatible with them.

The unbundled approach is much more amenable to these kinds of mixins, which are more severe in mathematics than in CS, as properties need to be supported in addition to simply operations.

The Mathematical Components team has written about these issues in the 2009 paper Packaging Mathematical Structures, as have we in the context of the Lean interactive theorem prover in the paper Elaboration in Dependent Type Theory.

I feel that the question of a reasonable inference mechanism for disambiguation is still a very open question though.


I'm not very familiar with the field, but my advisor Shigeru Yamashita is. I recommend you to check his home page. Here are some interesting papers he has:

A transduction-based framework to synthesize RSFQ circuits. Shigeru Yamashita, Katsunori Tanaka, Hideyuki Takada, Koji Obata, Kazuyoshi Takagi. In ASP-DAC 2006.
Transformation rules for designing CNOT-based quantum circuits. Kazuo Iwama, Yahiko Kambayashi, Shigeru Yamashita. DAC 2002.
DDMF: An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction. Shigeru YAMASHITA, Shin-ichi MINATO and D. Michael MILLER. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E91.A (2008) , No. 12 pp.3793-3802.

Other people that you should check their home pages are Igor Markov and Dimitri Maslov.


Finding the paths through a graph that reuse as many of the nodes as possible

You are looking for the shortest straight-line program to compute a set of formulas involving xor.

This is NP-hard. There are papers on how to efficiently solve this problem with  SAT solver. For example, Fuhs and Schneider-Kamp had this recent paper on Synthesizing Shortest Linear Straight-Line
Programs over GF(2) using SAT.

There is a proof that this problem is MAXSNP-hard by Boyar, Matthews and Peralta, see here.