computational complexity - Use of randomness in constant parallel time

Not sure what you mean by "0-ary random-bool gates", but I think you mean: take a circuit $C$ with $n$ real inputs and $poly(n)$ extra inputs. For each input $x$ of length $n$, the "probabilistic" circuit $C$ is said to output $b$ on $x$ iff when we attach $x$ to the real inputs, and put a uniform random input on the extra inputs, the probability $C(x)=b$ is at least $2/3$.

Given that, it is known that $BPAC0 subset non-uniform-AC0$. This was first proved by Ajtai and Ben-Or in:

Miklós Ajtai, Michael Ben-Or: A Theorem on Probabilistic Constant Depth Computations STOC 1984: 471-474

A very short and sweet paper. However it only results in non-uniform constant depth circuits. I believe that the best known uniform simulation of $BPAC0$ is with quasipolynomial size constant depth circuits, by Klivans:

Adam Klivans: On the Derandomization of Constant Depth Circuits. RANDOM-APPROX 2001: 249-260

Under some very weak hardness assumptions, $BPAC0 = AC0$, see:

Emanuele Viola: Hardness vs. Randomness within Alternating Time. IEEE Conference on Computational Complexity 2003

Edit: I should also mention the work of Nisan (1991) "Pseudorandom bits for constant depth circuits" which really made a lot of the later work possible.

ho.history overview - Italian school of algebraic geometry and rigorous proofs

Many of the amazing results by Italian geometers of the second half of the 19th and the first half of the 20th century were initially given heuristic explanations rather than rigorous proofs by their discoverers. Proofs appeared only later. In some cases, an intuitive explanation could be more or less directly translated into modern language. In some other cases, essentially new ideas were required (e.g., among others, the classification of algebraic surfaces by Shafarevich's seminar; construction of the moduli spaces of curves and their projective compactifications by Deligne, Mumford and Knudsen; solution of the Luroth problem by Iskovskikh and Manin).

I would like to ask: what are, in your opinion, the most interesting results obtained by pre-1950 Italian geometers which still do not have a rigorous proof?

[This is a community wiki, since there may be several answers, none of which is the "correct" one; however, please include as many things as possible per posting -- this is not intended as a popularity contest.]

[upd: since I'me getting much less answers that I had expected (in fact, only one so far), I would like to clarify a couple of things: as mentioned in the comments, I would be equally interested in results which are "slightly false" but are believed to be essentially correct, e.g. a classification with a particular case missing etc. I'm also interested in natural generalizations that still haven't been proven such as extending a result to finite characteristic etc.]

lo.logic - Propositional Logic, First-Order Logic, and Higher-Order Logics

I've been reading up a bit on the fundamentals of formal logic, and have accumulated a few questions along the way. I am pretty much a complete beginner to the field, so I would very much appreciate if anyone could clarify some of these points.

1. A complete (and consitent) propositional logic can be defined in a number of ways, as I understand, which are all equivalent. I have heard it can be defined with one axiom and multiple rules of inferences or multiple axioms and a single rule of inference (e.g. Modus Ponens) - or somewhere inbetween. Are there any advantage/disvantages to either? Which is more conventional?




2. Propositional (zeroth-order) logic is simply capable of making and verifying logical statements. First-order (and higher order) logics can represent proofs (or increasing hierarchial complexity) - true/false, and why?




3. What exactly is the relationship between an nth-order logic and an (n+1)th-order logic, in general. An explanation mathematical notation would be desirable here, as long as it's not too advanced.




4. Any formal logic above (or perhaps including?) first-order is sufficiently powerful to be rendered inconsistent or incomplete by Godel's Incompleteness Theorem - true/false? What are the advantages/disadvantages of using lower/higher-order formal logics? Is there a lower bound on the order of logic required to prove all known mathematics today, or would you in theory have to use an arbitrarily high-order logic?




5. What is the role type theory plays in formal logic? Is it simply a way of describing nth-order logic in a consolidated theory (but orthogonal to formal logic itself), or is it some generalisation of formal logic that explains everything by itself?

Hopefully I've phrased these questions in some vaguely meaningful/understandable way, but apologies if not! If anyone could provide me with some details on the various points without assuming too much prior knowledge of the fields, that would be great. (I am an undergraduate Physics student, with a background largely in mathematical methods and the fundamentals of mathematical analysis, if that helps.)

nt.number theory - Is the given expression, monotonically increasing or decreasing with increasing x?

I'm not sure I should bother answering this question, because it seems like the original poster may not have asked the right question. However, it is a nice exercise in basic asymptotics.

---

For $x$ sufficiently large, the sum in question is decreasing.

First, note that this sum is equal to
$$sum_{k geq 1} frac{(log x)^{k-1}}{x k! zeta(k+1)}.$$
(See here for a very similar series; we are using the highly nontrivial identity $sum mu(i)/i=0$ to get rid of the "$k=0$" term.)

Substituting $x=e^u$, we want to know whether or not
$$e^{-u} sum_{k geq 1} frac{u^{k-1}}{k! zeta(k+1)}$$
is increasing or decreasing in $u$. One can justify taking term by term derivatives, so we want to know whether
$$e^{-u} left( sum_{k geq 2} frac{(k-1) u^{k-2}}{k! zeta(k+1)} - sum_{k geq 1} frac{u^{k-1}}{k! zeta(k+1)} right)$$
is positive or negative.

Rearranging terms, we are interested in the sign of
$$e^{-u} sum_{ell geq 0} frac{u^{ell}}{ell!} left( frac{ 1}{(ell+2) zeta(ell+3)} - frac{1}{(ell+1) zeta(ell+2)} right).$$

The quantity in parenthesis is $-1/(ell+1)(ell+2) + O(2^{- ell})$. So we are interested in the sign of
$$e^{-u} left( - sum_{ell geq 0} frac{u^{ell}}{(ell+2)!} + sum O(frac{ u^{ell} 2^{- ell}}{ell !}) right) =$$
$$e^{-u} left( - frac{e^u -1-u}{u^2} + O(e^{u/2}) right)=$$
$$-1/u^2 + O(e^{-u/2}).$$

This is negative for $u$ sufficiently large.

set theory - Equivalent definitions of M-genericity.

I'm trying to learn about forcing, and have heard that there are several equivalent ways to define genericity. For instance, let M be a transitive model of ZFC containing a poset (P, ≤). Suppose G ⊆ P is such that q ∈ G whenever both p ∈ G and q ≥ p. Suppose also that whenever p,q ∈ G then there is r ∈ G such that r ≤ p and r ≤ q.
Then the following are equivalent ways to say that G is generic:

(1) G meets every element of M dense in P. That is, for all D ∈ M, if for all p ∈ P there is q ∈ D such that q ≤ p, then G ∩ D is nonempty.

(2) G is nonempty and meets every element of M dense below some p ∈ G. That is, for all p ∈ G and all B ∈ M, if for each q ≤ p there is r ∈ B such that r ≤ q, then G ∩ B is nonempty.

Proving this equivalence seemed like it would be an easy exercise, but I think I'm missing something. Can someone point me toward a source where I can find a proof? I hope this is an acceptable question; this is my first time posting.

EDIT: Typo and omission fixed.

ra.rings and algebras - Tensor products and two-sided faithful flatness

Here's an example. Let $R = {mathbb C}[x]$ and let $S = {mathbb C}langle x,yrangle/(xy-yx-1)$, i.e. the first Weyl algebra $A_1$. Then $S$ is free as both a left and right
$R$-module, and comes equipped with the natural ($R$-bimodule) inclusion of $R$. On the
other hand, if you take $M = {mathbb C}[x]/(x) = N$, you'll get for $Motimes_R Sotimes_R M$ the zero module. Indeed, any element of $S$, i.e. any differential operator with polynomial coefficients (writing $partial = partial/partial x$ in place of $y$) can be written in the form $sum_i p_i(x) partial^i$, so any element in $Motimes_R S = {mathbb C}[x]/(x) otimes S$ is represented by an expression $sum_i c_i partial^i$ where the $c_i$ are constants, and now an induction on $k$ shows (I believe, my brain is a little fuzzy at this hour) that, for the right $R$-module structure on $S/xS$, one has $partial^k cdot x = k partial^{k-1}$. One can conclude that $Motimes_R Sotimes_R M = 0$, whereas of course $Motimes_R Mcong M$ in this example...

computational complexity - Best-case Running-time to solve an NP-Complete problem

If P is an NP-complete problem, then define P_k = instances of P in which the instances have been blown up from size n to size n^k by padding them with blanks. Then P_k is also NP-complete, but if P takes time exp(p(n)) to solve where p is some polynomial then P_k can be solved in time essentially exp(p(n^1/k)) (there's a little more time required to check that the input really does have the right amount of padding but unless the running time is polynomial this is a negligable fraction of the total time). So there is no "easiest" problem: for every problem you name this construction gives another easier but still NP-complete problem.

As for non-artificial problems: most hard graph problems like Hamiltonian circuit, that are hard when restricted to planar graphs, can be solved in time exponential in √n or in (√n)(log n) by dynamic programming using a recursive partition by graph separators.