An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

We prove lower bounds of the form exp(n^{ε d}), ε_d > 0, on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth d, for any constant d. This is the largest lower bound for the strongest proof system, for which any superpolynomial lower bounds are known.     

The Module Structure Theorem for Sobolev Spaces on Open Manifolds

We prove a general embedding theorem for Sobolev spaces on open manifolds of bounded geometry and infer from this the module structure theorem. Thereafter we apply this to weighted Sobolev spaces.     

Interpolation by a Game

We introduce a notion of a real game (a generalisation of the Karchmer-Wigderson game (cf. [3]) and of real communication complexity, and relate this complexity to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols (defined in [4, Definition 2.2]) of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for prepositional logic (by a problem posed in [5, Section 8], in particular). Our main objective is to extend the communication complexity approach of [4, 5] to a wider class of proof systems. In this direction we obtain an effective interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree-like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree-like cutting planes proofs for which an exponential lower bound was demonstrated in [2]).     

Effect of Ga doping on magneto-transport properties in colossal magnetoresistive La0.7Ca0.3Mn1−xGaxO3 (0<x<0.1)

Samples of La_0.7Ca_0.3Mn_1−xGa_xO₃ with x=0, 0.025, 0.05 and 0.10 were prepared by standard solid-state reaction. They were first characterized chemically, including the microstructure. The magnetic properties and various transport properties, i.e. the electrical resistivity, magnetoresistivity (for a field below 8 T), thermoelectric power and thermal conductivity measured each time on the same sample, are reported. The markedly different behaviour of the x=0.1 sample from those with a smaller Ga content, is discussed. The dilution of the Mn³⁺/Mn⁴⁺ interactions with Ga doping considerably reduces the ferromagnetic double exchange interaction within the manganese lattice leading to a decrease of the Curie temperature. The polaron binding energy varies from 224 to 243 meV with increased Ga doping.     

An example of a superproportional graph

In the theory of random graphs, several classes of graphs occur that are exceptional cases in limit theorems for subgraph counts. The purpose of this article is to show the existence of graphs in one of these classes, by providing an explicit, computer generated, example. We also show that the class is closed under complementation. © 1994 John Wiley & Sons, Inc.     

Convex ordering criteria for Lévy processes

Modelling financial and insurance time series with Lévy processes or with exponential Lévy processes is a relevant actual practice and an active area of research. It allows qualitatively and quantitatively good adaptation to the empirical statistical properties of asset returns. Due to model incompleteness it is a problem of considerable interest to determine the dependence of option prices in these models on the choice of pricing measures and to establish nontrivial price bounds. In this paper we review and extend ordering results of stochastic and convex type for this class of models. We also extend the ordering results to processes with independent increments (PII) and present several examples and applications as to α-stable processes, NIG-processes, GH-distributions, and others. Criteria are given for the Lévy measures which imply corresponding comparison results for European type options in (exponential) Lévy models.