Regular Resolution Lower Bounds For The Weak Pigeonhole Principle

We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length , (for some global constant > 0).* Research supported by NSF grant CCR-9820831, US-Israel BSF grant 98-00349, and an NSERC grant. Research supported by US-Israel BSF grant 98-00349, and NSF grant CCR-9987077.     

Asymptotics of derivatives of orthogonal polynomials on the real line

We show that uniform asymptotics of orthogonal polynomials on the real line imply uniform asymptotics for all their derivatives. This is more technically challenging than the corresponding problem on the unit circle. We also examine asymptotics in the L ₂ norm. Research supported by NSF grant DMS0400446 and US-Israel BSF grant 2004353.     

On the Airy Reproducing Kernel, Sampling Series, and Quadrature Formula

We determine the class of entire functions for which the Airy kernel (of random matrix theory) is a reproducing kernel. We deduce an Airy sampling series and quadrature formula. Our results are analogues of well known ones for the Bessel kernel. The need for these arises in investigating universality limits for random matrices at the soft edge of the spectrum. Research supported by NSF grant DMS0400446 and US-Israel BSF grant 2004353.     

A simplex based algorithm to solve separated continuous linear programs

We consider the separated continuous linear programming problem with linear data. We characterize the form of its optimal solution, and present an algorithm which solves it in a finite number of steps, using an analog of the simplex method, in the space of bounded measurable functions. Research supported in part by US-Israel BSF grant 9400196, by German-Israel GIF grant I-564-246/06/97 and by Israel Science Foundation Grants 249/02 and 454/05.     

Large deviations in the geometry of convex lattice polygons

We provide a full large deviation principle (LDP) for the uniform measure on certain ensembles of convex lattice polygons. This LDP provides for the analysis of concentration of the measure on convex closed curves. In particular, convergence to a limiting shape results in some particular cases, including convergence to a circle when the ensemble is defined as those centered convex polygons, with vertices on a scaled two dimensional lattice, and with length bounded by a constant. The Gauss-Minkowskii transform of convex curves plays a crucial role in our approach. Partially supported by grants ININS 94-3420 and RFF1-96-01-00676. Partially supported by a US-Israel BSF grant and by the fund for promotion of research at the Technion.     

Duality,crossing and MacLane’s coherence

It is shown that MacLane’ rectangle, pentagon and hexagon identities in category theory, when applied in particle physics to duality diagrams or to rational conformal field theories in two dimensions, yield the necessary physical algebraic constraints. Supported in part by DOE grant no. DE-FG05-85ER40200 Supported by US-Israel BSF grant 87-00009/1.     

Branched two-sheeted covers

In this paper we explore the connection between Weierstrass points of subspaces of the holomorphic differentials and the geometry of the canonical curve inPC ^g−1. In particular, we consider non-hyperelliptic Riemann surfaces with involution and the Weierstrass points of the −1 eigenspace of the holomorphic differentials. The case of coverings of a torus is considered in detail. Research of the first author supported in part by the Paul and Gabriella Rosenbaum Foundation, the Landau Center for Research in Mathematical Analysis (supported by Minerva Foundation-Germany) and a US-Israel BSF grant. Research by the second author supported in part by NSF Grant DMS 9003361 and a Lady Davis Visiting Professorship at the Hebrew University.     

Multidimensional random subshifts of finite type and their large deviations

Summary I introduce random multidimensional subshifts of finite type which generalize models of spin-glasses and establish the “almost sure” large deviations bounds for Gibbs measures there. The paper is sequel to [EKW] where the corresponding results were obtained for deterministic multidimensional subshifts of finite type. Partially supported by US-Israel BSF     

New higher-order equiaffine invariants

We introduce new affine invariants for smooth convex bodies. Some sharp affine isoperimetric inequalities are established for the new invariants. Partially supported by an NSERC grant and an FRDP grant. Partially supported by an NSF grant, an FRG-NSF grant and a BSF grant.     

On singular compactness

We present some applications of Shelah's singular compactness theorem to algebraic situations where the Shreier property fails. The principal application is to valuated vector spaces, where we make use of an alternate, unpublished, version of Shelah's theorem. Research partially supported by NSF Grant No. MCS 80-03591 and by the US-Israel BSF. Presented by L. Fuchs.     

Deformations of balls in Schiffer’s conjecture for Riemannian symmetric spaces

It is proved that geodesic balls in a Riemannian symmetric space of rank one arestable solutions to a free-boundary problem for the Laplace-Beltrami operator with constant Dirichlet-Neumann boundary conditions. This result supports Schiffer's conjecture that balls are the only solutions to the problem. The main ingredient of the proof is a characterization of geodesic balls by the multiplicity of eigenvalues of the Laplace-Beltrami operator. Partially supported by a grant from the Academy of Sciences of Israel, no. 540/92-1 and by a grant from the US-Israel Science Foundation, no. 92-00246.     

Finitely generated groups of polynomial subgroup growth

We determine the structure of finitely generated residually finite groups in which the number of subgroups of each finite indexn is bounded by a fixed power ofn. To John Thompson, an inspiration to group theory, on his being awarded the Wolf Prize Partially supported by BSF and GIF grants. Partially supported by a BSF grant.     

On rank vs. communication complexity

This paper concerns the open problem of Lovász and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems.A preliminary version of this paper appeared in [10].This work was supported by USA-Israel BSF grant 92-00043 and by a Wolfeson research award administered by the Israeli Academy of Sciences.This work was supported by USA-Israel BSF grant 92-00106 and by a Wolfeson research award administered by the Israeli Academy of Sciences.     

Diffusion approximation for slow motion in fully coupled averaging

In systems which combine fast and slow motions it is usually impossible to study directly corresponding two scale equations and the averaging principle suggests to approximate the slow motion by averaging in fast variables. We consider the averaging setup when both fast and slow motions are diffusion processes depending on each other (fully coupled) and show that there exists a diffusion process which approximates the slow motion in the $L^2$ sense much better than the averaged motion prescribed by the averaging principle.The authors are partially supported by INTAS, project No. 99-00559 and by US-Israel BSF, respectively. Part of the work was done during the visit of the 1st author to the Hebrew University.Mathematics Subject Classification (2000): Primary 34C29; Secondary 60F15, 58J65     

Reducing The Seed Length In The Nisan-Wigderson Generator*

The Nisan–Wigderson pseudo-random generator [19] was constructed to derandomize probabilistic algorithms under the assumption that there exist explicit functions which are hard for small circuits. We give the first explicit construction of a pseudo-random generator with asymptotically optimal seed length even when given a function which is hard for relatively small circuits. Generators with optimal seed length were previously known only assuming hardness for exponential size circuits [13,26]. We also give the first explicit construction of an extractor which uses asymptotically optimal seed length for random sources of arbitrary min-entropy. Our construction is the first to use the optimal seed length for sub-polynomial entropy levels. It builds on the fundamental connection between extractors and pseudo-random generators discovered by Trevisan [29], combined with the construction above. The key is a new analysis of the NW-generator [19]. We show that it fails to be pseudorandom only if a much harder function can be efficiently constructed from the given hard function. By repeatedly using this idea we get a new recursive generator, which may be viewed as a reduction from the general case of arbitrary hardness to the solved case of exponential hardness. * This paper is based on two conference papers [11,12] by the same authors. † Research Supported by NSF Award CCR-9734911, NSF Award CCR-0098197, Sloan Research Fellowship BR-3311, grant #93025 of the joint US-Czechoslovak Science and Technology Program, and USA-Israel BSF Grant 97-00188. ‡ Part of this work was done while at the Hebrew University and the Institute for advanced study. § This research was supported by grant number 69/96 of the Israel Science Foundation, founded by the Israel Academy for Sciences and Humanities and USA-Israel BSF Grant 97-00188.     

Localization for a Family of One-dimensional Quasiperiodic Operators of Magnetic Origin

We show strong dynamical localization for a family of one-dimensional quasiperiodic Jacobi operators of magnetic origin, throughout the regime of positive Lyapunov exponents.The authors were supported in part by BSF grant 2002068 and NSF grant DMS-0300974.submitted 7/07/04, accepted 22/07/04     

On the concentration of eigenvalues of random symmetric matrices

It is shown that for every 1≤s≤n, the probability that thes-th largest eigenvalue of a random symmetricn-by-n matrix with independent random entries of absolute value at most 1 deviates from its median by more thant is at most 4e ⁻ t ²32 ^s2. The main ingredient in the proof is Talagrand’s Inequality for concentration of measure in product spaces. Research supported in part by a USA — Israel BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research supported in part by a USA — Israel BSF grant and by a Bergmann Memorial Grant.     

Effective counting of the points of definable sets over finite fields

Given a formula in the language of fields we use Galois stratification to establish an effective algorithm to estimate the number of points over finite fields that satisfy the formula This work was partially done while all three authors were members of the Institute for Advanced Studies in Jerusalem. Parially supported by BSF grant #87-00038 and NSA grant MDA 904-91-H-0057. Partially supported by grants from the German-Israeli Foundation for Scientific Research and Development.     

Lagrangian embeddings into subcritical Stein manifolds

In this paper we obtain new topological restrictions on Lagrangian embeddings into subcritical Stein manifolds. We also extend previous results of Gromov, Oh, Polterovich and Viterbo on Lagrangian submanifolds of ℂ ⁿ to the more general case of subcritical Stein manifolds. Research partially supported by the US-Israel Binational Science Foundation grant 1999086.     

Averaging in dynamical systems and large deviations

Summary The paper treats ordinary differential equations of the form wheref ^t is a hyperbolic flow. Large deviations bounds for the averaging principle are obtained here in the form appeared previously in [F₁, F₂] for the case when the flowf ^t is replaced by a Markov process.Oblatum 4-XII-1991Partially supported by US-Israel BSF and the Landau Center for Research in Mathematical Analysis, supported by Minerva Foundation (Germany)