text:
# Seminars (DAN)

Videos and presentation materials from other INI events are also available.

Search seminar archive

Event When Speaker Title Presentation Material
DANW01 10th January 2011
10:00 to 11:00
B Bukh Complexity of spatial embeddings of graphs
We introduce a measure of topological complexity of an embedding of a graph into R^3. We show that the notion strengthens the crossing number for graph embeddings in R^2, and that the complexity of expander graphs is high, as expected. We will also discuss the questions related to generalisations to higher dimensions. Joint work with Alfredo Hubard.
DANW01 10th January 2011
11:30 to 12:30
Vertex sparsifiers: New results from old techniques (and some open questions)
Given a capacitated graph G = (V,E) and a set of terminals $K \subseteq V$, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between the terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow-sparsifier for G.) What if we want H to be a simple'' graph? What if we allow H to be a convex combination of simple graphs? And is the question easier if we wanted H to maintain the distances among the terminals (rather than flows)?

Joint work with Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam-Cohen and Kunal Talwar.
DANW01 10th January 2011
14:00 to 15:00
N Linial Topology and probability? What a strange combination...
I will talk about various ways in which the probabilistic method can be applied to study various problems in topology.
DANW01 10th January 2011
15:30 to 16:30
Hilbert space compression of groups and dimension growth
I am going to talk about joint results with Arzhantseva, Guba, Drutu and Dranishnikov. It turned out that the same method is used to compute the Hilbert compression of a group (in particular, the Thompson group F) and its dimension growth. Some open problems will be discussed also.
DANW01 10th January 2011
16:30 to 17:30
Duality for Lipschitz p-summing operators
A theorem of J. Bourgain states that any finite metric space can be embedded into a Hilbert space with distortion proportional to the logarithm of the number of points. In fact Bourgain's embedding has a richer structure, that of a Lipschitz p-summing operator. These operators were introduced by J. Farmer and W. B. Johnson, and generalize the concept of a linear p-summing operator between Banach spaces . In this talk we identify the dual of the space of Lipschitz p-summing operators from a fi nite metric space to a normed space, answering a question of Farmer and Johnson. Furthermore, we use it to give a characterization of the non-linear concept of Lipschitz p-summing operator between metric spaces in terms of linear operators between certain Banach spaces.
DANW01 11th January 2011
10:00 to 11:00
Discrete differentiation and local rigidity of smooth sets in the plane
We exhibit an infinite doubling metric space whose n-point subsets require distortion sqrt(log n/log log n) to embed into L_1. This nearly matches the upper bound of sqrt(log n) (Gupta-Krauthgamer-Lee 2003) and improves over the best previous bound of (log n)^c for some c > 0 (Cheeger-Kleiner-Naor 2009). Furthermore, this offers a nearly tight integrality gap for a weak version of the Goemans-Linial SDP for Sparsest Cut, matching the upper bound of Arora-Lee-Naor (2005). We discuss how our results might lead to a resolution of the full Goemans-Linial conjecture.

Following the general approach developed by Cheeger and Kleiner (2006), our lower bound uses a differentiation argument to achieve local control on the cut measure, followed by a classification step of the cuts that can appear. In order to get tight bounds, the classification step has to deal with sets which satisfy only a weak average regularity assumption, meaning that we have to control not just "99%-structured sets," but "1%-structured" sets as well. This weak regularity is achieved via a random differentiation argument which measures the variation of the function along randomly chosen subdivisions of geodesics.

Our lower bound space is a 2-dimensional complex which takes inspiration from both the Heisenberg group and the diamond graphs.

This is joint work with James R. Lee (University of Washington).
DANW01 11th January 2011
11:30 to 12:30
M Mendel Ultrametric subsets with large Hausdorff dimension
We show that for any 1>ε>0, any metric space X contains a subset Y which is O(1/ε) equivalent to an ultrametric and dimH(Y)>(1-ε)dimH(X), where dimH is the Hausdorff dimension. The dependence on ε is tight up-to a constant multiplicative factor.

This result can be viewed as high distortion metric analog of Dvoretzky theorem. Low distortion analog of Dvoretzky theorem is impossible since there are examples of compact metric spaces of arbitrary large Hausdorff dimension for which any subset that embeds in Hilbert space with distortion smaller than 2 must have zero Hausdorff dimension.
DANW01 11th January 2011
14:00 to 15:00
Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
The celebrated dimension reduction lemma of Johnson and Lindenstrauss has numerous computational and other applications. Due to its application in practice, speeding up the computation of a Johnson-Lindenstrauss style dimension reduction is an important question. Recently, Dasgupta, Kumar, and Sarlos (STOC 2010) constructed such a transform that uses a sparse matrix. This is motivated by the desire to speed up the computation when applied to sparse input vectors, a scenario that comes up in applications. The sparsity of their construction was further improved by Kane and Nelson (ArXiv 2010).

We improve the previous bound on the number of non-zero entries per column of Kane and Nelson. We also improve the amount of randomness needed to generate the matrix. Our results are obtained by connecting the moments of an order 2 Rademacher chaos to the combinatorial properties of random Eulerian multigraphs. Estimating the chance that a random multigraph is composed of a given number of node-disjoint Eulerian components leads to a new tail bound on the chaos. Our estimates may be of independent interest, and as this part of the argument is decoupled from the analysis of the coefficients of the chaos, we believe that our methods can be useful in the analysis of other chaoses.

Joint work with Vladimir Braverman and Rafail Ostrovsky.
DANW01 11th January 2011
15:30 to 16:30
N Alon A non-linear lower bound for planar epsilon-nets
After a brief description of the notion of epsilon-nets for range spaces and of the main known results about them, I will show that the minimum possible size of an epsilon-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/epsilon. This settles a problem raised by Matousek, Seidel and Welzl in 1990.
DANW01 11th January 2011
16:30 to 17:30
A Valette Behaviour of Hilbert compression for groups, under group constructions
If $(X,d)$ is a metric space, the Hilbert compression of $X$ is the supremum of all $\alpha$'s for which there exists a Lipschitz embedding $f$ from X to a Hilbert space, such that $C.d(x,y)^\alpha \leq \|f(x)-f(y)\|$ for every $x,y\in X$. When $G$ is a finitely generated group, Hilbert compression is a quasi-isometry invariant which has been related to concepts such as exactness, amenability, Haagerup property. In this survey talk, we will review the known results about the range of this invariant, then we will move on to some recent results (due to Naor-Peres, Li, Dreesen) on the behaviour of Hilbert compression under various group constructions (wreath products, free and amalgamated products, HNN-extensions, etc...).
DANW01 12th January 2011
10:00 to 11:00
Norm Estimation, Precision Sampling, and Rademacher Type
We describe new algorithms to compute norms of a vector in a stream, which can be seen as linear embeddings into certain low-dimensional "computational spaces". In particular, we show that for a variety of settings, simple algorithms follow from the application of a single simple probabilistic technique, called Precision Sampling. These settings include classic scenarios such as l_p norms for p\in(0,2] and p>2, as well as mixed norms l_p(l_q). In the latter case, we show how (a natural generalization of) the Rademacher type yields essentially tight bounds for all regimes p,q>0.

Precision Sampling itself addresses the problem of estimating a sum of reals \sum a_i from weak estimates of each a_i\in[0,1]. More precisely, one chooses in advance "precisions" w_i>=1 for each i and obtains an estimate of a_i within additive 1/w_i. The core question is: what is the best trade-off between the approximation to \sum a_i and the total precision, \sum_i w_i ?

Joint work with Robert Krauthgamer and Krzysztof Onak.
DANW01 12th January 2011
11:30 to 12:30
A survey on random walks on groups
DANW01 12th January 2011
14:00 to 15:00
Coarse non-amenability and coarse embeddings
The concept of coarse embedding was introduced by Gromov in 1993. It plays an important role in the study of large-scale geometry of groups and the Novikov higher signature conjecture. Guoliang Yu's property A is a weak amenability-type condition that is satisfied by many known metric spaces. It implies the existence of a coarse embedding into a Hilbert space.

We construct the first example of a metric space with bounded geometry which coarsely embeds into a Hilbert space, but does not have property A. This is a joint work with Erik Guentner and Jan Spakula.
DANW01 13th January 2011
10:00 to 11:00
Cover times of graphs, majorizing measures, and the Gaussian free field
The cover time of a finite graph (the expected time for the simple random walk to visit all the vertices) has been extensively studied, yet a number of fundamental questions have remained open. We present a connection between the cover time, the discrete Gaussian free field on the underlying graph, and the Fernique-Talagrand theory of majorizing measures. At its most basic level, this involves embedding the graph into Euclidean space via the effective resistance, and then studying the associated Gaussian process (the image points under random projection) using the geometry of the resistance metric, in combination with Talagrand's ultrametric interpretation of majorizing measures.

This allows us resolve a number of open questions. Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution if within a factor of 2, say, of the stationary distribution) and conjectured that the blanket time is always within O(1) of the cover time. Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to an O(1) factor. The best approximation factor found so far for both these problems was (log log n)^2 for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000). We use the aforementioned connection to deduce a positive answer to the question of Aldous and Fill and to establish the conjecture of Winkler and Zuckerman. These results extend to arbitrary reversible finite Markov chains

This is joint work with Jian Ding (U. C. Berkeley) and Yuval Peres (Microsoft Research).
DANW01 13th January 2011
11:30 to 12:30
Tight embedding of subspaces of $L_p$ in $\ell_p^n$ for even $p$
Given $1\le p\infty$ and $k$ what is the minimal $n$ such that $\ell_p^n$ almost isometrically contain all $k$-dimensional subspaces of $L_p$? I'll survey what is known about this problem and then concentrate on a recent result, basically solving the problem for even $p$. The proof uses a recent result of Batson, Spielman and Srivastava.
DANW01 13th January 2011
15:30 to 16:30
Embeddings and topological rigidity
I will discuss the relations between embedability and topological rigidity of manifolds.
DANW01 13th January 2011
16:30 to 17:30
Recent work of Nigel Kalton
Nigel Kalton passed away on August 2010. Shortly before his death, he sent me several remarkable preprints that contain major progress on embedding theory. In this talk I will present some of his new results, explain at least one of his beautiful proofs in detail, and describe the significance of these results and some problems that remain open.
DANW01 14th January 2011
10:00 to 11:00
ME embeddings for groups
Two countable discrete groups $G$ and $H$ are said to be measure equivalent, or ME in short, if there is a standard measure space which carries commuting measure-preserving actions of $G$ and $H$ such that each of actions has a fundamental domain of finite measure. For example lattices of a locally compact group are ME to each other. The notion of measure equivalence is introduced by Gromov as a younger brother of quasi-isometry for groups. I will give a survey on ME embeddings.
DANW01 14th January 2011
11:30 to 12:30
Topics in Sparse Recovery
DANW01 14th January 2011
14:00 to 15:00
On the Unique Games Conjecture
This talk will survey recently discovered connections between the Unique Games Conjecture and computational complexity, algorithms, discrete Fourier analysis, and geometry.

The power-point presentation and a written article are available at the address below, though the talk will focus a bit more on the open problems and research directions.
DANW01 14th January 2011
15:30 to 16:30
Equilateral sets in normed spaces
This talk will be a survey about what is known about equilateral sets in normed spaces, mostly finite dimensional.
DANW01 14th January 2011
16:30 to 17:30
Coarse Lipschitz embeddings of expander graphs and cotype
In this talk we will discuss recent results of M. Ostrovskii about embeddings of graphs into graphs of bounded degree and Lipschitz embeddings of expanders. Then we will show how we can adapt his construction to prove that there exists a family of expander graphs whose coarse Lipschitz embedding (a.k.a quasi-isometric embedding) into a Banach space forces the target space to have trivial cotype. One wants to mention that the proof does not require a metric cotype approach'' and uses only classical Banach space theory.
DAN 19th January 2011
14:00 to 15:00
Maximal inequality for high-dimensional cubes
The talk will deal with the behaviour of the best constant in the Hardy-Littlewood maximal inequality in R^n when the dimension goes to infinity. More precisely, I will sketch a simple probabilistic proof of the following result (due to Aldaz): when the maximal function is defined by averaging over all centred cubes, the Hardy-Littlewood inequality does not hold with a constant independent of the dimension.
DAN 26th January 2011
14:00 to 15:00
Jordan's theorem on finite linear groups and its approximate Analogues
DAN 26th January 2011
15:15 to 16:15
On geometric incidences
DAN 28th January 2011
14:00 to 15:00
T Tao On Gromov's theorem on groups of polynominal growth and related topics
DAN 31st January 2011
14:00 to 15:00
On a conjecture of Snevily
DAN 1st February 2011
14:00 to 15:00
DAN 2nd February 2011
14:00 to 15:00
Applications of Discrete Analysis in Inapproximability of NP-hard Problems
DAN 4th February 2011
11:00 to 12:00
Self-affine sets and measures
DAN 9th February 2011
14:00 to 15:00
Plunnecke-type product set estimates in groups
DAN 9th February 2011
15:15 to 16:15
Multiplicative translates of subgroups in residue classes
DAN 11th February 2011
14:00 to 15:00
Linear threshold predicates and approximation resistance
DAN 12th February 2011
14:00 to 15:00
3 terms arithmetic progressions in finite fields (IV)
DAN 16th February 2011
14:00 to 15:00
Some remarks on Mahler's conjecture for convex bodies
Let $P(K)$ be the product of the volume of an origin symmetric convex body $K$ and its dual/polar body $K^*$. Mahler conjectured that $P(K)$ is minimized by a cube and maximized by a ball. The second claim of this conjecture was proved by Santalo; despite many important partial results, the first problem is still open in dimensions 3 and higher. In this talk we will discuss some recent progress and ideas concerning this conjecture.
DAN 18th February 2011
14:00 to 15:00
The Khinchine inequalities with optimal constants via ultra log-concavity
We shall present a new approach to the comparison of moments for sums of independent symmetric random variables, based on Walkup's theorem which states that the binomial convolution transform preserves log-concavity. This is a joint work with Piotr Nayar.
DAN 21st February 2011
14:00 to 15:00
O Guedon Concentration inequalities for log-concave measures
DAN 23rd February 2011
14:00 to 15:00
Row products of random matrices
We define the row product of K matrices of size d by n as a matrix of size d^K by n, whose rows are entry-wise products of rows of these matrices. This construction arises in certain computer science problems. We study to what extent the spectral and geometric properties of the row product of independent random matrices resemble those properties for a d^K by n matrix with independent random entries.
DAN 23rd February 2011
15:15 to 16:15
A Plagne From coding theory to Davenport constant
DAN 2nd March 2011
14:00 to 15:00
Vertices of high degree in the preferential attachment tree
The preferential attachment tree is the most basic model of evolving web graphs. At each stage of the process, a new vertex is added and joined to one of the existing vertices, with each vertex chosen with probability proportional to its current degree. In probability theory, this is also known as a Yule process. Much is known about this model, including the fact that the numbers of vertices of each small degree follow a power law''. Here we study in detail the degree sequence of the preferential attachment tree, looking at the vertices of large degrees as well as the numbers of vertices of each fixed degree. Our method is based on bounding martingale deviations, using exponential supermartingales. This is joint work with Graham Brightwell.
DAN 2nd March 2011
15:15 to 16:15
Polarisation problems
Let $u_1, u_2, ..., u_n$ be unit vectors in a Hilbert space $H$. The polarisation problem states that there is another unit vector $v$ in $H$, which is sufficiently far from the orthogonal complements of the given vectors in the sense that $\prod |(u_i, v)| \geq n^{-n/2}$. The strong polarisation problem asserts that there is choice of $v$ for which $\sum 1/ (u_i, v)^2 \leq n^2$ holds. These follow from the complex plank problem if $H$ is a complex Hilbert space, but for real Hilbert spaces the general conjectures are still open. We prove special cases by transforming the statements to geometric forms and introducing inverse eigenvectors of positive semi-definite matrices.
DAN 9th March 2011
14:00 to 15:00
Finding primes deterministically
DAN 9th March 2011
15:15 to 16:15
A Sen A new definition of influences of Boolean functions
The notion of influences of variables on Boolean functions is one of the central concepts in the theory of discrete harmonic analysis. We present a new definition of influences in product spaces of continuous distributions. Our definition is geometric, and for monotone sets it is identical with the measure of the boundary with respect to uniform enlargement. We prove analogues of the Kahn-Kalai-Linial (KKL) and Talagrand's influence sum bounds for the new definition. This result is then used to obtain an isoperimetric inequality for the Gaussian measure on R^n and the class of sets invariant under transitive permutation group of the coordinates. I will also discuss some statistical connection to this problem. This is joint work with Nathan Keller and Elchanan Mossel
DAN 16th March 2011
14:00 to 15:00
Spectrum of large non-hermitian random matrices
In this talk, we will revisit recent works of T. Tao, V. Vu and others on large non-hermitian random matrices with independent and identically distributed entries. We will explain the general strategy behind this class of problems. As a byproduct, we will explain why the generalized eigenvalues distribution of two independent matrices converges almost surely to the uniform measure on the Riemann sphere.
DAN 16th March 2011
15:15 to 16:15
G Lancien Coarse Lipschitz embeddings and asymptotic structure of Banach Spaces
The linear properties of Banach spaces considered in this talk will be the ex- istence of an equivalent asymptotically uniformly smooth (or convex) equivalent norm. We shall study the stability of these properties under various non linear transformations, but we will concentrate on the coarse Lipschitz embeddings (i.e. maps that are bi-Lipschitz for very large distances). These questions in relation with uniform asymptotic smoothness are now quite well understood. We will try to present the progress made last year by N.J. Kalton on the stability of uniform asymptotic convexity under coarse embeddings. We will focus on the use of some fundamental metric graphs or trees in the subject, and present a few open questions that we find interesting.
DANW02 28th March 2011
10:00 to 11:00
Threshold behaviour
In the lecture I will describe some results and problems regarding threshold behavior of Boolean and other functions.

1. Sharp threshold, the equal-slice measure and the Shapley value:

Result: Boolean functions with diminishing threshold window are precisely Boolean functions with diminishing maximum Shapley value.

Problem: Close the exponential gap in the quantitative version of this result,

2. Sharp threshold for larger alphabets (with Elchanan Mossel)

We show that sharp threshold behavior for monotone Boolean functions with symmetry extends to a larger alphabet. Large alphabets offer new challenges and new phenomena.

3. Problems about the relation between the expectation threshold and the threshold for graph properties and Boolean functions. (with Jeff Kahn). When probabilities get tiny matters are more difficult and more interesting.
DANW02 28th March 2011
11:30 to 12:30
R Latala Tail and moment estimates for Rademacher chaos
We present two-sided estimates of moments and tails of polynomial chaoses of order at most three generated by Rademacher sequence (i.e. a sequence of independent symmetric random variables taking values +/-1). The estimates involve only deterministic quantities and are optimal up to universal constants.

This is a joint work with R Adamczak (Warsaw).

DANW02 28th March 2011
14:00 to 15:00
R O'Donnell The Fourier Entropy-Influence conjecture for certain classes of Boolean functions
In this talk we report some progress on Friedgut and Kalai's "Fourier Entropy-Influence Conjecture". We verify the conjecture for symmetric functions, read-once decision trees, and certain generalizations of these classes.

Joint work with John Wright and Yuan Zhou of Carnegie Mellon University.
DANW02 28th March 2011
15:30 to 16:30
P Tetali Transportation and related inequalities in discrete spaces
Following exciting developments in the continuous setting of manifolds (and other geodesic spaces), in joint works with various collaborators, I have explored discrete analogs of the interconnection between several functional inequalities in discrete spaces; such inequalities include concentration, transportation, displacement convexity and modified versions of the logarithmic Sobolev inequality. I will attempt to review some of these connections and illustrate with examples. Computational aspects of the underlying functional constants and other open problems will also be mentioned.
DANW02 28th March 2011
17:00 to 18:00
The power and weakness of randomness, when you are short on time (Rothschild Lecture)
Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I'll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms efficient. Time permitting, I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.
DANW02 29th March 2011
10:00 to 11:00
O Regev Quantum one-way communication can be exponentially stronger than classical communication
In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only O(log n) qubits, but for which any classical (randomized, bounded-error) protocol requires poly(n) bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. In other words, can quantum one-way communication be exponentially stronger than classical two-way communication? Here we settle this question in the affirmative.

Based on joint work with Bo'az Klartag.

NOTE: This talk is about lower bounds for *classical* communication complexity; no knowledge of quantum communication complexity is assumed or required.
DANW02 29th March 2011
11:30 to 12:30
Dictatorships and juntas in the symmetric group
One of the main themes of using discrete harmonic analysis in combinatorial settings, is detecting structures, (or functions) that essentially depend on few coordinates. The Fourier characterization of these juntas is usually expressed by the fact that the Fourier transform is concentrated on low levels.

In this talk I will study the question of the analog of this phenomenon in the symmetric group.
DANW02 29th March 2011
14:00 to 15:00
On the usefulness of predicates
One successful application of discrete harmonic analysis has been the analysis of Max-CSPs, maximum constraint satisfaction problems.

In the Max-CSP defined by a predicate P of arity k we are presented with a list of k-tupels of literals and the goal is to find assignments to the variables in order to maximize the number of resulting k-bit strings that satisfy P.

A predicate P is approximation resistant if, even for instances where the optimal assignments satisfies (almost) all constraints, it is infeasible to do find an assignment that satisfies substantially more constraints than what is obtained by picking a random assignment.

We study a more general question of given the promise of the existence of an assignment that satisfies all the constraints given by P, to efficiently finding an assignment that satisfies a weaker predicate (or more general function) Q.

In particular we say P is useless if it is infeasible to do substantially better than random for any Q.

In this talk we describe this framework and derive results on uselessness based on NP ≠ P and the Unique Games Conjecture.
DANW02 29th March 2011
15:30 to 16:30
Influences and Boolean functions representations
More than twenty years ago the important work of Kahn, Kalai and Linial gave general bounds on the influence of variables in arbitrary Boolean functions over the discrete hypercube. In theoretical computer science, though, often one is interested in particular types of "simple" Boolean functions such as constant-depth circuits, decision trees, low-degree polynomial threshold functions, etc. This additional structure raises the possibility that refined influence bounds can be obtained, and indeed it turns out that this is sometimes the case. This talk will give an overview of several such results and their applications, with an emphasis on currently open questions and directions for future work.
DANW02 29th March 2011
16:30 to 17:30
N Anantharaman The semiclassical limit for eigenfunctions of the laplacian : a survey
This will be a (non exhaustive) survey talk about the behaviour of eigenfunctions of the laplacian on a compact manifold, in the asymptotic regime where the eigenvalue goes to infinity. The issue of quantum ergodicity'' is to understand the places where the eigenfunctions can concentrate. Recently, there has been increasing interest about possible analogues for the discrete laplacian on finite graphs (for instance, with the work of Brooks and Lindenstrauss). According to the physics literature, the interesting asymptotic regime to look at is the case of families of graphs whose size goes to infinity. As far as graphs are concerned, the talk will contain more open questions than results.
DANW02 30th March 2011
10:00 to 11:00
Sharp threshold for percolation on expanders
In this joint work with I. Benjamini, S. Boucheron, and R. Rossignol, we study the appearance of the giant component in random subgraphs of a given finite graph G = (V,E) in which each edge is present independently with probability p. We show that if G is an expander with vertices of bounded degree, then for any c in (0,1), the property that the random subgraph contains a giant component of size c|V | has a sharp threshold. The main technical tools are based on variance inequalities for functions of independent random variables.
DANW02 30th March 2011
11:30 to 12:30
P Dai Pra Convex decay of entropy in interacting systems
For a Markov process, the exponential decay of relative entropy with respect to the invariant measure corresponds to a functional inequality sometimes called "Modified logarithmic Sobolev inequality" (MLSI). We consider a stronger inequality, that, besides exponential decay, implies that the relative entropy is convex in time. The advantage of this inequality is that it can be obtained, for some systems of interacting particle, via a Bakry-Emery-type approach, avoiding more complicated martingale methods. After having illustrated this approach, I will present some recent progresses on the subject, obtained in collaboration with G. Posta.
DANW02 30th March 2011
15:30 to 16:30
S Khot A two prover one round game with strong soundness
We show that for any large integer q, it is NP-hard to distinguish whether a two prover one round game with q^6 answers has value close to 1 or at most O(1/q). The result is obtained by combining two new techniques: (i) An Inner PCP based on the "point versus subspace" test for linear functions. The test is analyzed Fourier analytically. (ii) The Outer/Inner PCP composition that relies on a certain "sub-code covering" property for Hadamard codes.

As an application, we show that unless NP has quasi-polynomial time deterministic algorithms, the Quadratic Programming Problem is inapproximable within factor (\log n)^{1/6 - o(1)}.

The talk should be self-contained.

Joint work with Muli Safra
DANW02 30th March 2011
16:30 to 17:30
Somewhere between Freiman's theorem and the Polynomial Freiman-Ruzsa conjecture
Freiman's theorem describes the structure of sets of integers having small doubling which enjoys numerous applications in additive combinatorics. While the result is qualitatively comprehensive, a truer picture is suggested by the Polynomial Freiman-Ruzsa conjecture, and in this talk we shall discuss how a remarkable new technique of Croot and Sisask can be used in conjunction with a trick of Lopez and Ross to provide much clearer quantitative information. We shall focus on the model finite field setting where there are few prerequisites and the details are the cleanest.
DANW02 31st March 2011
10:00 to 11:00
Proving theorems inside sparse random sets
In 1996 Kohayakawa, Luczak and Rödl proved that Roth's theorem holds almost surely inside a subset of {1,2,...,n} of density Cn^{-1/2}. That is, if A is such a subset, chosen randomly, then with high probability every subset B of A of size at least c|A| contains an arithmetic progression of length 3. (The constant C depends on c.) It is easy to see that the result fails for sparser sets A. Recently, David Conlon and I found a new proof of this theorem using a very general method. As a consequence we obtained many other results with sharp bounds, thereby solving several open problems. In this talk I shall focus on the case of Roth's theorem, but the generality of the method should be clear from that.
DANW02 31st March 2011
11:30 to 12:30
J Bennett The Brascamp--Lieb inequalities and the restriction problem for the Fourier transform
The Brascamp--Lieb inequalities simultaneously generalise classical inequalities in analysis such as the multilinear Holder, Young convolution and Loomis--Whitney inequalities. In this talk we will describe certain geometric and combinatorial generalisations of these multilinear inequalities which arise naturally in harmonic analysis and PDE. Particular emphasis will be placed on their intimate connected with the recent restriction theory of the Fourier transform.
DANW02 31st March 2011
15:30 to 16:30
Expansion of small sets in graphs
A small set expander is a graph where every set of sufficiently small size has near perfect edge expansion. This talk concerns the computational problem of distinguishing a small set-expander, from a graph containing a small non-expanding set of vertices. This problem henceforth referred to as the Small-Set Expansion problem has proven to be intimately connected to the complexity of large classes of combinatorial optimization problems. More precisely, the small set expansion problem can be shown to be directly related to the well-known Unique Games Conjecture -- a conjecture that has numerous implications in approximation algorithms.

In this talk, we motivate the problem, and survey recent work consisting of algorithms and interesting connections within graph expansion, and its relation to Unique Games Conjecture.
DANW02 31st March 2011
16:30 to 17:30
High frequency criteria for Boolean functions (with an application to percolation)
Assume you are given a certain Boolean function f: {0,1}^n -> {0,1} and you are suspecting that it is a high frequency'' one. It is a non-trivial problem to localize at a low cost' where the Spectral mass'' lies. Of course, one could compute the Fourier-Walsh coefficients one at a time, but in the generic case this would take forever and this is the kind of techniques we are trying to avoid by looking for a low cost' criterion.

In this talk, I will survey different criteria or techniques which enables one to detect whether a Boolean function is of high frequency or not.

To give an example of such a criterion, the first result in this direction is due to Benjamini, Kalai and Schramm. It states that if the Boolean function f is such that its individual influences are small'' (in a precise L^2 way), then the function has to be of high frequency with a quantitative bound on how high the spectrum is.

Most of these criteria have been discovered while analyzing the percolation case. Indeed any geometrical event about configurations of percolation can be written as a Boolean function where each bit'' determines whether its corresponding edge (or site) is open or closed. It turns out that at criticality, these Boolean functions are of very high frequency. In other words, percolation is very sensitive to small perturbations at the critical point. Since it is very hard to compute all the Fourier coefficients of such functions, several tools have been developed in the literature to understand the Fourier spectrum of percolation. Interestingly, most of these tools can be simply stated and are not specifically designed for percolation.

Therefore, the purpose of this talk will be to expose these criteria in an accessible way, with the hope that some of them could be used elsewhere.
DANW02 1st April 2011
10:00 to 11:00
On reverse hypercontractive inequalities
A hyper-contractive inequality for an operator T states that |Tf|_q \leq |f|_p where q > p > 1 for all functions f. Hyper contractive inequalities play a crucial role in analysis in general and in discrete Fourier analysis in particular.

A reverse hyper-contractive inequality for the operator T states that |Tf|_q \geq |f|_p for q The first reverse hyper-contractive inequalities were proved by Borell more than 2 decades ago. While these inequalities may look obscure, they have been used for the solution of a number of problems in the last decade. I will survey applications of the inequalities and discuss new results relating reverse hyper-contractive inequalities to hyper-contractive, Log-Sobolev and Poincare inequalities as well as some new applications.

This is a joint work with K Oleszkiewicz (Warsaw) and A Sen (Cambridge).
DANW02 1st April 2011
11:30 to 12:30
G Kindler A quantitative version of the Gibbard-Satterthwaite theorem
Consider an election between q alternatives, where each of the voters rank the different alternatives, and the winner is determined according to some predefined function of this voting profile. Such a social choice function is called manipulable, if a situation might occur where a voter who knows the rankings given by other voters can change her ranking in a way that does not reflect her true preference, but which leads to an outcome that is more desirable to her.

Gibbard and Satterthwaite proved that any social choice function where more than two alternatives can be selected is manipulable, unless it is a dictatorship (where the outcome of the election only depends on the choices of one voter). In the case where the social choice function is neutral, namely when it is invariant under changing the names of the alternatives, we prove a lower bound on the fraction of manipulable preference profiles which is inverse polynomial in the number of voters and alternatives. Our proof in fact does not rely on discrete harmonic analysis - finding an analytic version of the proof would be the role of the audience.

Joint work with Marcus Isaksson and Elchanan Mossel.
DANW02 1st April 2011
14:00 to 15:00
Large Deviation Principle for the Erdös-Renyi random graph
What does an Erdos-Renyi graph look like when a rare event happens? I will describe an answer to this question when p is fixed and n tends to infinity by establishing a large deviation principle under an appropriate topology. The formulation and proof of the main result uses the recent development of the theory of graph limits by Lovasz and coauthors and Szemeredi's regularity lemma from graph theory. As a basic application of the general principle, we work out large deviations for the number of triangles in G(n,p). Surprisingly, even this simple example yields an interesting double phase transition. This is based on joint work with S. R. S. Varadhan.
DAN 5th April 2011
14:00 to 15:00
A Wigderson Arithmetic complexity and the sum of squares problem (I)
In this lecture I will survey basic models, results and problems on the computation of computing polynomials, such as DFT, symmetric polynomials, determinant, permanent, matrix multiplication and more...
DAN 5th April 2011
15:15 to 16:15
D Ellis Triangle-intersecting families of graphs
A family of graphs F on a fixed set of n vertices is said to be triangle-intersecting if for any two graphs G,H 2 F, G \ H contains a triangle. Simonovits and S´os conjectured that such a family has size at most 18 2(n2),and that equality holds only if F consists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved a strengthening of this conjecture, namely that if F is an odd-cycleintersecting family of graphs, then |F| · 18 2(n2). Equality holds only if F consists of all graphs containing some fixed triangle. A stability result also holds: an odd-cycle-intersecting family with size close to the maximum must be close to a family of the above form. We will outline proofs of these results, which use Fourier analysis, together with an analysis of the properties of random cuts in graphs, and some results in the theory of Boolean functions. We will then discuss some related open questions. All will be based on joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem).
DAN 7th April 2011
14:00 to 15:00
Multilinear Kakeya type inequalities and factorization
DAN 7th April 2011
15:15 to 16:15
A Wigderson Arithmetic complexity and the sum of squares problem (II)
This lecture will be largely independent from the first. I will explain the completeness of the determinant and permanent in respective classes of polynomials, and its importance to the P vs. NP problem. I will discuss the non commutative versions of their complexity, and show how these relate to the famous sum-of-squares problem. Then I'll mention some recent small progress on that problem and some of its variants.
DAN 12th April 2011
13:45 to 14:45
A Wigderson Explicit Euclidean Sections, Codes over the Reals and Expanders
Here is a basic problem, which comes under various names including "compressed sensing matrices", Euclidean sections of L1", "restricted isometries" and more. Find a subspace X or R^N such that every vector x in X has the same L1 and L2 norms (with proper normalization) up to constant factors. It is known that such subspaces of dimension N/2 exist (indeed "most" of them are), and the problem is to describe one explicitly. I will describe some progress towards this problem, based on extending the notion of expander codes from finite fields to the reals.
DAN 13th April 2011
13:45 to 14:45
On the Log-Concave Ensemble of random matrices
DAN 14th April 2011
13:45 to 14:45
Long Arithmetic Progressions in Sumsets
DAN 21st April 2011
14:00 to 15:00
The ferromagnetic Potts model: phase transition, gadgets and computational complexity
An instance of the Potts model is defined by a graph of interactions and a number q of different "spins". A configuration is this model is an assignment of spins to vertices. Each configuration has a weight, which in the ferromagnetic case is greater when more pairs of adjacent spins are alike. The classical Ising model is the special case of q=2 spins. We consider the problem of computing an approximation to the partition function, i.e., weighted sum of configurations, of an instance of the Potts model. Through the random cluster formulation it is possible to make sense of the partition function also for non-integer q. Yet another equivalent formulation is as the Tutte polynomial in the positive quadrant. About twenty years ago, Jerrum and Sinclair gave an efficient (i.e., polynomial-time) algorithm for approximating the partition function of a ferromagnetic Ising system. Attempts to extend this result to q2 have been unsuccessful. At the same time, no convincing evidence has been presented to indicate that such an extension is impossible. In this talk, I sketch a recent result to the effect that, for q>2, approximating the partition function of the ferromagnetic Potts model is hard for a certain complexity class, which contains a large number of other approximation problems for which no efficient approximation algorithm is known. The reduction used to establish this result exploits a first-order phase transition, already known to exist when q>2, to construct a bi-stable combinatorial "gadget". Along the way, a hypergraph version of the Tutte polynomial arises quite naturally. This is joint work with Leslie Ann Goldberg, University of Liverpool.
DAN 27th April 2011
14:00 to 15:00
On various sum-product inequalities
DAN 27th April 2011
15:15 to 16:15
Randomized algorithms for the approximation of matrices
DAN 3rd May 2011
14:00 to 15:00
3-terms arithmetic progressions in finite fields (I)
DAN 4th May 2011
13:45 to 14:45
Correlation testing for affine invariant properties on $F_p^n$
Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f: F_p^n \rightarrow F_p$ with polynomials of degree at most $d \le p$ is non-negligible, while making only a constant number of queries to the function. This is an instance of {\em correlation testing}. In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analog of {\em proximity oblivious testing}, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree $d$ polynomials for some fixed $d$. We stress that our result holds also for non-linear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is an extension of a graph theoretical theorem of Erd\"os, Lov\'asz and Spencer to the context of additive number theory. Joint work with Hamed Hatami.
DAN 6th May 2011
14:00 to 15:00
3 terns arithmetic progressions in finite fields (II)
DAN 9th May 2011
14:00 to 15:00
3-terms arithmetic progressions in finite fields (III)
DAN 10th May 2011
14:00 to 15:00
S Bobkov Rates of convergence in the entropic central limit theorem
Abstract. Under moment conditions, we will be discussing asymptotic formulas for the entropy of sums of i.i.d. random variables. (Joint work with G. P. Chistyakov and F. G\"otze).
DAN 12th May 2011
14:00 to 15:00
3-terms arithmetic progressions in finite fields (IV)
DAN 18th May 2011
14:00 to 15:00
Discrete Ricci curvature with applications
We define a notion of discrete Ricci curvature for a metric measure space by looking at whether "small balls are closer than their centers are". In a Riemannian manifolds this gives back usual Ricci curvature up to scaling. This definition is very easy to apply in a series of examples such as graphs (eg the discrete cube has positive curvature). We are able to generalize several Riemannian theorems in positive curvature, such as concentration of measure and the log-Sobolev inequality. This definition also allows to prove new theorems both in the Riemannian and discrete case: for example improved bounds on spectral gap of the Laplace-Beltrami operator, and fast convergence results for some Monte Carlo Markov Chain methods.
DAN 19th May 2011
14:00 to 15:00
A curved Brunn-Minkowski inequality in the discrete cube
(Joint work with C.Villani) We try (and fail) to implement the displacement convexity property of Lott-Sturm-Villani to the discrete hypercube. Yet along the way we get new, unexpected results of a combinatorial and probabilistic nature, including a curved Brunn--Minkowski inequality on the discrete hypercube.
DAN 24th May 2011
14:00 to 15:00
How to Play Unique Games Against a Semi-Random Adversary
We study the average case complexity of the Unique Games problem. We propose a semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an epsilon-fraction of all edges, and finally replaces ("corrupts'') the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1-epsilon)-satisfiable instance, so then the problem is as hard as in the worst case. We show however that we can find a solution satisfying a (1-delta)-fraction of all constraints in polynomial-time if at least one step is random (we require that the average degree of the graph is at least log k). Our result holds only for epsilon less than some absolute constant. We prove that if epsilon 1/2, then the problem is hard, that is, no polynomial-time algorithm can distinguish between the following two cases: (i) the instance is a (1-epsilon) satisfiable semi-random instance and (ii) the instance is at most delta satisfiable (for every delta > 0); the result assumes the 2-to-2 Unique Games conjecture. Finally, we study semi-random instances of Unique Games that are at most (1-epsilon) satisfiable. We present an algorithm that distinguishes between the case when the instance is a semi-random instance and the case when the instance is an arbitrary (1-delta)-satisfiable instance (if epsilon > c delta, for some absolute constant c). Joint work with Alexandra Kolla and Yury Makarychev
DAN 25th May 2011
14:00 to 15:00
Favourite distances in high dimensions
DAN 25th May 2011
15:15 to 16:15
Y Makarychev Vertex Sparsifiers and Lipschitz Extendability
DAN 31st May 2011
14:00 to 15:00
Singular integrals in bad neighborhoods I: Singular integrals for Geometric Measure Theory
Very bad sets on which singular integrals are tame cannot be bad. They have to have the structure. This is the first topic in which we explain the solution of some old problems of Vitushkin, Denjoy, Painlev\'e, David--Semmes. The second lecture is mostly about probabilistic methods in taming the singular integrals in bad environment.
DAN 1st June 2011
14:00 to 15:00
Ricci curvature of Finsler manifolds, towards applications in the geometry of Banach spaces
I will introduce the notion of Ricci curvature for general Finsler manifolds. Bounding this curvature from below is equivalent to Lott, Sturm and Villani's curvature-dimension condition, and there are further applications (e.g., a Bochner-type formula and gradient estimates). I also would like to discuss some possible applications of this differential geometric technique to the geometry of Banach spaces.
DAN 1st June 2011
15:15 to 16:15
Computability and Complexity of Julia Sets
Studying dynamical systems is key to understanding a wide range of phenomena ranging from planetary movement to climate patterns to market dynamics. Various computational and numerical tools have been developed to address specific questions about dynamical systems, such as predicting the weather or planning the trajectory of a satellite. However, the theory of computation behind these problems appears to be very difficult to develop. In fact, little is known about computability of even the most natural problems arising from dynamical systems. In this talk I will survey the recent study of the computational properties of dynamical systems that arise from iterating quadratic polynomials on the complex plane. These give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. The theory behind them is even more fascinating, and the dynamical systems generating them are in many ways archetypal. I will present both positive and negative results on the computability and computational complexity of Julia sets.
DAN 6th June 2011
14:00 to 15:00
Singular integrals in bad neighborhoods II: Stochastic Optimal Control and sharp estimates of Singular Integrals
Very bad sets sets on which singular integrals are tame cannot be bad. They have to have the structure. This is the first topic in which we explain the solution of some old problems of Vitushkin, Denjoy, Painlev\'e, David--Semmes. The second lecture is mostly about probabilistic methods in taming the singular integrals in bad environment.
DAN 7th June 2011
14:00 to 15:00
Isoperimetric and concentration inequalities - equivalence and applications
Given a metric space equipped with a measure, various ways exist for studying the interaction between measure and metric. A very strong form is given by isoperimetric inequalities, which for a set of given measure, provide a lower bound on its boundary measure. A much weaker form is given by concentration inequalities, which quantify large-deviation behavior of measures of separated sets. There are also other tiers, interpolating between these two extremes, such as the tier of Sobolev-type inequalities. It is classical (by results of Cheeger, Maz'ya, Gromov--Milman andothers) that isoperimetric inequalities imply corresponding functional versions, which in turn imply concentration counterparts. However, in general, these implications cannot be reversed. We show that under a suitable (possibly negative) lower bound on the generalized Ricci curvature of a Riemannian-manifold-with-density, completely general concentration inequalities imply back their isoperimetric counterparts, up to dimension \emph{independent} bounds. Consequently, in such spaces, all of the above tiers of the hierarchy are equivalent, clarifying the role which curvature plays in the interaction between measure and metric. Several applications of this equivalence will be presented, ranging from Statistical Mechanics to Spectral Geometry. Time permitting, we will also present new \emph{sharp} isoperimetric inequalities, generalizing classical results due to P. L\'evy, Sudakov--Tsirelson and Borell, Gromov and Bakry--Ledoux, into one single form. The talk will be self-contained and accessible to all.
DAN 10th June 2011
14:00 to 15:00
Stochastic completeness for random walks and jump processes
DAN 14th June 2011
14:00 to 15:00
Is asymptotic extremal graph theory of dense graphs trivial?
Recent developments in asymptotic extremal combinatorics have provided powerful automatic and semi-automatic methods for proving theorems in the dense setting. For example I will show how relying completely on a computer, one can solve an old conjecture of Erdos and answer a question of Sidorenko and of Jagger, Stovicek and Thomason. These new discoveries raise the following fundamental question: is it possible to prove every true algebraic inequalities between graph densities using a finite amount of manipulation with densities of finitely many graphs?'' Although this question itself is not well-defined, various precise refinements of it are formulated independently by Razborov and Lovasz. I will present a joint theorem with Sergey Norin which answers many of these questions.
DAN 15th June 2011
15:30 to 16:30
Towards an entropy-based sumset calculus for additive combinatorics and convex geometry
We use common entropy-based tools to study two kinds of problems: the first of proving general cardinality inequalities for sumsets in possibly nonabelian groups, and the second of proving volume inequalities of interest in convex geometry and geometric functional analysis. We will spend most of our time on the discrete setting (joint work with A. Marcus and P. Tetali), introducing the notion of partition-determined functions, and presenting some basic new inequalities for the entropy of such functions of independent random variables, as well as for cardinalities of compound sets obtained using these functions. Corollaries of the results for partition-determined functions include entropic analogues of general Pl\"unnecke-Ruzsa type inequalities, sumset cardinality inequalities in abelian groups generalizing inequalities of Gyarmati-Matolcsi-Ruzsa and Balister-Bollob\'as, and partial progress towards a conjecture of Ruzsa for sumsets in nonabelian groups. Time permitting, we will also mention some results in the continuous setting (joint work with S. Bobkov) including some Pl\"unnecke-type inequalities for Minkowski sums of convex sets, and an entropic generalization of V. Milman's reverse Brunn-Minkowski inequality.
DAN 15th June 2011
17:00 to 17:50
Quantitative geometry and efficient classification procedures
This talk will illustrate to non-experts the use of geometric methods to design efficient partitioning algorithms for discrete objects or, in some cases, to prove that such algorithms must fail to perform well. These connections show that combinatorial optimization problems are intimately related to classical questions in continuous geometry, and we will describe some recent progress on old questions that translates to the best known results on algorithmic problems of central interest. This talk will provide an introduction to geometric aspects of computational complexity via an examination of specific examples. No specialized background will be required.
DAN 21st June 2011
14:00 to 15:00
Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and Kernelization
Let $P$ be a decision problem (answers are yes or no). A parameterized problem $\Pi$ is a set of pairs $(x,k)$ where $x$ is an instance of $P$ and $k$ (usually an integer) is the parameter. One example is the $k$-Vertex Cover problem, where for a given graph $G$ we are to decide whether there is a set of $k$ vertices covering all edges of $G.$ A kernelization of $\Pi$ is a polynomial time algorithm that maps an instance $(x,k)\in \Pi$ to an instance $(x',k')\in \Pi$ (kernel) such that (i) $(x,k)$ is a yes-instance iff $(x',k')$ is a yes-instance, (ii) $k'\leq h(k)$ and $|x'|\leq g(k)$ for some functions $h$ and $g$, where $|x'|$ is the size of $x'$. For example, there is a kernelization of $k$-Vertex Cover reducing each pair ($G,k$) into ($H,k$), where $H$ has at most $2k$ vertices and $k^2$ edges. A parameterized problem is fixed-parameter tractable if it can be solved in time $O(f(k)|x|^{O(1)})$ for some function $f$ in $k$. It is well-known that a parameterized problem is fixed-parameter tractable iff it is decidable and admits a kernelization. We'll discuss applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra to some parameterized problems. We'll mainly discuss MaxLin2-AA: given a system of linear equations over GF(2) in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least $W/2+k,$ where $W$ is the total weight of all equations of the system. Solving an open question of Mahajan, Raman and Sikdar (2006,2009), we'll show that MaxLin2-AA is fixed-parameter tractable and admits a kernel with at most $O(k^2\log k)$ variables. Here we use Linear Algebra. This is a very recent result, see http://arxiv.org/abs/1104.1135 It is still unknown whether MaxLin2-AA admits a kernel with a polynomial number of equations (rather than variables), but we can prove that such a kernel exists for a number of special cases of MaxLin2-AA. Here we apply Probabilistic Method and Discrete Harmonic Analysis. In particular, we use the well-known (4,2)-Hypercontractive Inequality as well as its new version.
DAN 22nd June 2011
14:00 to 15:00
Gradient flows of the entropy for finite Markov chains
At the end of the nineties, Jordan, Kinderlehrer, and Otto discovered a new interpretation of the heat equation in R^n, as the gradient flow of the entropy in the Wasserstein space of probability measures. In this talk, I will present a discrete counterpart to this result: given a reversible Markov kernel on a finite set, there exists a Riemannian metric on the space of probability densities, for which the law of the continuous time Markov chain evolves as the gradient flow of the entropy.
DAN 22nd June 2011
15:30 to 16:30
The logarithmic Laplace transform in convex geometry
My plan is to give a slow introduction to the use of the logarithmic Laplace transform in obtaining bounds on the isotropic constants of convex bodies. We will review the proofs of Bourgain's n^{1/4} bound, the bound by the width of the thinshell, and the bound in term of the sub-gaussian coefficient. This talk is based on joint works with Ronen Eldan and with Emanuel Milman.
DAN 5th July 2011
14:00 to 15:00
Positive projections
If A is a set of n positive integers, how small can the set { (a,b) : a,b in A } be? Here as usual (a,b) denotes the HCF of a and b. This elegant question was raised by Granville and Roesler, who also reformulated it in the following way: given a set A of n points in the integer grid Z^d, how small can (A-A)^+, the projection of the difference set of A onto the positive orthant, be? Freiman and Lev gave an example to show that (in any dimension) the size can be as small as n^{2/3} (up to a constant factor). Granville and Roesler proved that in two dimensions this bound is correct, i.e. that the size is always at least n^{2/3}, and they asked if this holds in any dimension. After some background material, the talk will focus on recent developments, including a negative answer to the n^{2/3} question. (joint work with Bela Bollobas)


text:
### Correlated Orienteering Problem and its Application to Persistent Monitoring Tasks

@article{yu_correlated_2016,
title = {Correlated {Orienteering} {Problem} and its {Application} to {Persistent} {Monitoring} {Tasks}},
volume = {32},
issn = {1552-3098, 1941-0468},
url = {http://ieeexplore.ieee.org/document/7555356/},
abstract = {We propose the Correlated Orienteering Problem (COP) as a novel non-linear extension to the classic Orienteering Problem (OP). With the introduction of COP it becomes possible to model the planning of informative tours for the persistent monitoring of a spatiotemporal ﬁeld with time-invariant spatial correlations using autonomous mobile robots, in which the robots are range- or time-constrained. Our focus in this paper is QCOP, a quadratic COP instantiation that looks at correlations between neighboring nodes in a node network. The main feature of QCOP is a quadratic utility function capturing the said spatial correlation. We solve QCOP using mixed integer quadratic programming (MIQP), with the resulting anytime algorithm capable of planning multiple disjoint tours that maximize the quadratic utility. In particular, our algorithm can quickly plan a near-optimal tour over a network with up to 150 nodes. Beside performing extensive simulation studies to verify the algorithm’s correctness and characterize its performance, we also successfully applied QCOP to two realistic persistent monitoring tasks: (i) estimation over a synthetic spatiotemporal ﬁeld, and (ii) estimating the temperature distribution in the state of Massachusetts.},
language = {en},
number = {5},
urldate = {2020-09-15},
journal = {IEEE Transactions on Robotics},
author = {Yu, Jingjin and Schwager, Mac and Rus, Daniela},
month = oct,
year = {2016},
keywords = {cooperative\_planning},
pages = {1106--1118},
month_numeric = {10}
}

format: plain


text:
Enter the annual demand, the cost per order ($), and the carrying cost per unit ($) into the Ordering Cost Calculator. The calculator will evaluate and display the Ordering Cost.

## Ordering Cost Formula

The following formula is used to calculate the Ordering Cost.

OC = SQRT ( (2* AD*CPO)/CC)

• Where OC is the Ordering Cost ($) • AD is the annual demand • CPO is the cost per order ($)
• CC is the carrying cost per unit ($) ## How to Calculate Ordering Cost? The following example problems outline how to calculate Ordering Cost. Example Problem #1 1. First, determine the annual demand. The annual demand is given as 500 . 2. Next, determine the cost per order ($). The cost per order ($) is calculated as 20 . 3. Next, determine the carrying cost per unit ($). The carrying cost per unit ($) is found to be 4. 4. Finally, calculate the Ordering Cost using the formula above: OC = SQRT ( (2* AD*CPO)/CC) Inserting the values from above yields: OC = SQRT ( (2* 500*20)/4) = 70.71 ($)

Example Problem #2

The variables needed for this problem are provided below:

annual demand = 700

cost per order ($) = 30 carrying cost per unit ($) = 10

Entering these values and solving gives:

OC = SQRT ( (2* 700*30)/10) = 64.807 (\$)


text:
Physics Forums (http://www.physicsforums.com/index.php)
-   Classical Physics (http://www.physicsforums.com/forumdisplay.php?f=61)
-   -   [Something descriptive here will yield more responses] (http://www.physicsforums.com/showthread.php?t=251548)

 Narcol2000 Aug22-08 10:10 PM

[Something descriptive here will yield more responses]

I'm trying to solve the question b) in this linkhttp://i36.tinypic.com/2h3wmtx.jpg

My reasoning is

$$dK = dm v^2$$

$$dm = \rho dV = \rho A(x) dx$$

where A(x) is a function of how the cross sectional area varies along the tube from left to right.

$$A(x) = \pi r(x)^2$$

where r(x) is how the radius of the cross sectional area varies and is given by

$$r(x) = r(1+x/l)$$

this gives

$$dm = \rho \pi r^2 (1+x/l)^2$$

the answer given gives the (1+x/l)^2 term in the denominator but the method i have used will give it in the numerator, i don't see the flaw in what i have done though unfortunately.

 Mårten Aug23-08 10:12 AM

Re: [Something descriptive here will yield more responses]

Hi Narcol2000!

This is a kind of question that I think is better posted in the Homework area (see link below). And don't forget to give the post a title! :smile:

http://www.physicsforums.com/forumdisplay.php?f=152

 All times are GMT -5. The time now is 12:47 AM.


text:
## Edwards Curves

On the second day of 29c3, we talked about the group law on an elliptic curve based on our old script (in German) called "Das Gruppengesetz auf Elliptischen Kurven". Today, we explained to some people how elliptic curves can be used to factorize the product of two primes, i.e. attack weak RSA keys. When we were done, we let the flipchart paper taped to the wall and sat down. Few minutes passed before two people in passing showed an unusual interest in our notes. A few words into the conversation, I bluntly asked them about their mathematical background, which was met with an amused > I'm a math professor, does that suffice? These people turned out to be Tanja Lange and Daniel Bernstein, two scientists who are rather big shots in mathematical cryptography. I am ashamed to say that I did not even know that, but I certainly understood that they knew a lot more about elliptic curves than me and they were willing to share. To be precise, they were really friendly, and good at explaining it. That's rare. Of course, I eagerly listened as they began elaborating on the advantages of Edwards coordinates on elliptic curves. The two of them had attended the talk by Edwards introducing the concept in 2007 and observed the cryptographic potential: Basically (and leaving out some details), it's all about the fact that $x^2+y^2 = 1+dx^2y^2$ defines an elliptic curve, with all relevant points visible in the affine plane; check out the picture. Choosing $(0,1)$ as your neutral element, a group law on this curve is given by $(x_1,y_1) \oplus (x_2,y_2) := \left( \frac{x_1y_2+x_2y_1}{1+dx_1x_2y_1y_2}, \frac{y_1y_2+x_1x_2}{1+dx_1x_2y_1y_2}\right).$ With this shape, you never have to mention projective coordinates, the group law can be explained in a very elementary kind of way — and then it turns out that this shape also yields faster algorithms for point multiplication. In short: If you're into curves, cryptography or both, I thoroughly encourage you to check out their summary page about Edwards coordinates.


text:
5:32 AM
0

Let $A$ be a subset of $X$ which is a compact connected metric space, and A with more than $n$ components. Do exist $C_1, \ldots, C_{n+1}$ pairwise separated subsets such that $A = \bigcup_{i=1}^{n+1}C_i$? I have tried to take the first $n$ components of $A$ as $C_1, \ldots, C_n$ and define \$C_{...


text:
1
JEE Main 2021 (Online) 18th March Morning Shift
+4
-1
In Young's double slit arrangement, slits are separated by a gap of 0.5 mm, and the screen is placed at a distance of 0.5 m from them. The distance between the first and the third bright fringe formed when the slits are illuminated by a mnochromatic light of 5890 $$\mathop A\limits^o$$ is :-
A
1178 $$\times$$ 10$$-$$9 m
B
1178 $$\times$$ 10$$-$$6 m
C
1178 $$\times$$ 10$$-$$12 m
D
5890 $$\times$$ 10$$-$$7 m
2
JEE Main 2021 (Online) 18th March Morning Shift
+4
-1
Your friend is having eye sight problem. She is not able to see clearly a distant uniform window mesh and it appears to her as non-uniform and distorted. The doctor diagnosed the problem as :
A
Astigmatism
B
Myopia with Astigmatism
C
Presbyopia with Astigmatism
D
Myopia and Hypermetropia
3
JEE Main 2021 (Online) 17th March Morning Shift
+4
-1
The thickness at the centre of a plane convex lens is 3 mm and the diameter is 6 cm. If the speed of light in the material of the lens is 2 $$\times$$ 108 ms$$-$$1. The focal length of the lens is ____________.
A
0.30 cm
B
30 cm
C
15 cm
D
1.5 cm
4
JEE Main 2021 (Online) 16th March Evening Shift
+4
-1
The refractive index of a converging lens is 1.4. What will be the focal length of this lens if it is placed in a medium of same refractive index? Assume the radii of curvature of the faces of lens are R1 and R2 respectively.
A
Zero
B
Infinite
C
1
D
$${{{R_1}{R_2}} \over {{R_1} - {R_2}}}$$
JEE Main Subjects
Physics
Mechanics
Electricity
Optics
Modern Physics
Chemistry
Physical Chemistry
Inorganic Chemistry
Organic Chemistry
Mathematics
Algebra
Trigonometry
Coordinate Geometry
Calculus
EXAM MAP
Joint Entrance Examination


text:
## Physics for Scientists and Engineers: A Strategic Approach with Modern Physics (3rd Edition)

(a) $x = 6.0~m$ $v = 4.0 ~m/s$ $a = 0$ (b) $x = 13.0~m$ $v = 2.0 ~m/s$ $a = -2.0~m/s^2$
The area under the velocity versus time graph is equal to the displacement. We can read the velocity directly from the velocity versus time graph. The acceleration is equal to the slope of the velocity versus time graph. (a) From t = 0 to t = 1.0 s: The area under the velocity versus time graph is 4.0 m. $\Delta x = 4.0~m$ At t = 1.0 s: $x = x_0 + \Delta x$ $x = 2.0~m+4.0~m = 6.0~m$ At t = 1.0 s: $v = 4.0 ~m/s$ At t = 1.0 s, the slope of the velocity versus time graph is 0. Therefore, $a = 0$. (b) From t = 1.0 s to t = 3.0 s: The area under the velocity versus time graph is 7.0 m. $\Delta x = 7.0~m$ At t = 3.0 s: $x = 6.0~m + \Delta x$ $x = 6.0~m+ 7.0~m = 13.0~m$ At t = 3.0 s: $v = 2.0~m/s$ At t = 3.0 s, the slope of the velocity versus time graph is $\frac{-4.0~m/s}{2.0~s} = -2.0~m/s^2$ Therefore, $a = -2.0~m/s^2$.


text:
# Manipulate single terms that involve negative powers

## Interactive practice questions

State the base for the expression $4^{-3}$43.

Easy
Less than a minute
Identify the power for the expression $10^{-8}$108.
We want to evaluate $10^3\div10^4$103÷104 by first evaluating each term in the quotient separately.
We want to evaluate $\frac{5^3}{5^5}$5355 using repeated multiplication to simplify the fraction.


text:
# Amplitude of discrete Fourier transform of Gaussian is incorrect

I am trying to understand why the amplitude of the FFT (computed with numpy) of a Gaussian differs from its analytic solution.

The $\mathcal{F}\{e^{-\pi t^2}\} = e^{-\pi f^2}$. However if I calculate it with the FFT function in numpy the resulting Gaussian's amplitude is not 1?

I have already done the following:

• I do divide the fft result by the number of samples (normalize).
• I have even tried shifting the Gaussian so that its first sample is its height. This corrects the sinusoidal behaviour, and removes the maginary part, but does not improve the amplitude result (same as absolute value of unshifted case). I will however be taking the absolute value in any case.

Here is the code:

def test_gauss_1D(self,a,f_c,delta_f):
delta_t = 1.0/(2.0*f_c)
N = int(np.ceil(1/(delta_f*delta_t)))+1
if (N % 2) == 0:
N = N + 1

t = np.linspace(-(N-1)/2*delta_t,(N-1)/2*delta_t,N)
f = np.linspace(-1/(2*delta_t),1/(2*delta_t),N)

x_t = np.exp(-np.pi*t**2)

#x_t = np.roll(x_t,-1*(N-1)/2)

#x_t = 1/(np.sqrt(2*np.pi)*a)*np.exp(-t**2/(2*a**2))

#print "std = ", 1/(4*a**2*np.pi**2)
#print "ampl =", np.sqrt(2*np.pi)*a

plt.plot(t,x_t)
plt.show()

#x_f = np.fft.fft(x_t)/N
#print "N = ",N
x_f = np.fft.fft(x_t)/N

x_f = np.roll(x_f,1*(N-1)/2)

plt.plot(f,np.absolute(f))
plt.show()

Here are the images:

As you can see the amplitude is incorrect in the second image (should be one).

Why is this?

• Is there a missing factor of $1/2\pi$? – Bill Barth Mar 31 '14 at 12:56
• No the missing factor is $10\frac{1}{12}$. – trienko Mar 31 '14 at 13:07


text:
# Week 1 - Graphs

## 1. Undirected Graphs

### 1.1. Graph terminology

• Path. Sequence of vertices connected by edges.
• Cycle. Path whose first and last vertices are the same.
• Two vertices are connected if there is a path between them.
• Some graph-processing problems

• Path. Is there a path between s and t ?
• Shortest path. What is the shortest path between s and t ?
• Cycle. Is there a cycle in the graph?
• Euler tour. Is there a cycle that uses each edge exactly once? Hamilton tour. Is there a cycle that uses each vertex exactly once.
• Connectivity. Is there a way to connect all of the vertices?
• MST. What is the best way to connect all of the vertices? Biconnectivity. Is there a vertex whose removal disconnects the graph?
• Planarity. Can you draw the graph in the plane with no crossing edges Graph isomorphism. Do two adjacency lists represent the same graph?
• Challenge. Which of these problems are easy? difficult? intractable?

### 1.2. Graph API

• Typical graph-processing code

• Goal. Find all vertices connected to s (and a corresponding path).
• Algorithm.
• Use recursion (ball of string).
• Mark each visited vertex (and keep track of edge taken to visit it). Return (retrace steps) when no unvisited options.
• Data structures.
• boolean[] marked to mark visited vertices.
• int[] edgeTo to keep tree of paths.
• (edgeTo[w] == v) means that edge v-w taken to visit w for first time
• Depth-first search. Put unvisited vertices on a stack.
• Breadth-first search. Put unvisited vertices on a queue.
• Shortest path. Find path from s to t that uses fewest number of edges.

• Algorithm.

• Put s onto a FIFO queue, and mark s as visited.
• Repeat until the queue is empty:
• remove the least recently added vertex v
• add each of v's unvisited neighbors to the queue, and mark them as visited.

### 1.5. Connected Components

• Goal:
• Vertices v and w are connected if there is a path between them.
• Preprocess graph to answer queries of the form is v connected to w? in constant time.
• The relation "is connected to" is an equivalence relation:
• Reflexive: v is connected to v.
• Symmetric: if v is connected to w, then w is connected to v.
• Transitive: if v connected to w and w connected to x, then v connected to x.
• A connected component is a maximal set of connected vertices.
• Algorithm:
• Initialize all vertices v as unmarked.
• For each unmarked vertex v, run DFS to identify all vertices discovered as part of the same component.

### 1.6. Some Quizzes

• Some definitions:
• An edge having the same vertex as both its end vertices is called a self-loop.
• Two edges with the same end vertices are referred to as parallel edges.
• A graph that has neither self-loops nor parallel edges is called a simple graph.
• The eccentricity of a vertex v in a connected graph G is the maximum graph distance between v and any other vertex in the graph G.
• The maximum eccentricity is the graph diameter. The minimum graph eccentricity is called the graph radius.
• The center of a graph G is the set of vertices of graph eccentricity equal to the graph radius. (i.e., the set of central points).
• From Wolfram Mathworld
• Diameter of a tree. Given a graph that is a tree (connected and acyclic), find the longest path, i.e., a pair of vertices v and w that are as far apart as possible. Your algorithm should run in linear time.

1. Assume x and y are the vertices with the longest diameter.
2. Randomly pick any vertex v, and its furthest vertex w should be either x or y. Because the distance between any two vertices is definitely less than or equal to x-y.
1. Remember there are always paths from v to x and y, so [v-w] > [v-x] and [v-w] > [v-y] can't be true in the same time. otherwise, y or x should be equal to w.
3. Then just use x or y to find y or x which correspond to its furthest vertex.
• Center of a tree. Given a graph that is a tree (connected and acyclic), find a vertex such that its maximum distance from any other vertex is minimized.

• Find the diameter of the tree (the longest path between two vertices) and return a vertex in the middle.
• Parallel edge detection. Devise a linear-time algorithm to count the parallel edges in a graph.
• Hint: maintain a boolean array of the neighbors of a vertex, and reuse this array by only reinitializing the entries as needed.
• // TODO Don't understand.

## 2. Directed Graphs (Digraphs)

• Set of vertices connected pairwise by directed edges.

### 2.1. Digraph API

• toString()

  In in = new In(args[0]);
Digraph G = new Digraph(in);
for (int v = 0; v < G.V(); v++)
StdOut.pringln(v + "->" + w);

• same as graph APIs. only difference is:

  public void addEdge(int v, int w) {
}

• same as Undirected Graph.

### 2.3. Topological(拓扑) Sort

• Goal. Given a set of tasks to be completed with precedence constraints, in which order should we schedule the tasks?
• Digraph model.
• edge = precedence constraint.
• DAG. Directed acyclic graph.
• Topological sort. Redraw DAG so all edges point upwards.

• Run depth-first search.
• Return vertices in reverse postorder.
• A digraph has a topological order iff no directed cycle.

### 2.4. Strong Components

• Def. Vertices v and w are strongly connected if there is both a directed path from v to w and a directed path from w to v.
• Def. A strong component is a maximal subset of strongly-connected vertices.

#### Kosaraju-Sharir algorithm

• Reverse graph. Strong components in G are same as in G^R.
• G^R denotes reversed G.
• Kernel DAG. Contract each strong component into a single vertex.

• Compute topological order in kernel DAG.
• Run DFS, considering vertices in reverse topological order.
• Phases:

1. Compute topological order in G^R.
2. run DFS on G, considering vertices in order given by first DFS
• Java Implement(Strong components in a digraph (with two DFSs))


text:
# Plotting Timeseries#

Dymos provides a simple function to plot timeseries,

timeseries_plots(solution_recorder_filename, simulation_record_file=None, plot_dir="plots")

A separate plot file will be created for each timeseries variable. The plots will be saved and not displayed. The user has to manually open the plot files for them to be displayed.

The only required argument, solution_recorder_filename, is the file path to the case recorder file containing the solution results.

If the optional argument, simulation_record_file, is given, then that will be used to get data for plotting the timeseries of the simulation.

Finally, the optional argument, plot_dir, can be set to indicate to what directory the plot files will be saved.

Here is an example of the kind of plot that is created.


text:
# Minimum Wages and Employment: A Case Study of the Fast Food Industry in New Jersey and Pennsylvania

Author On April 1, 1992 New Jersey's minimum wage rose from $4.25 to$5.05 per hour. To evaluate the impact of the new law we surveyed over 400 fast food restaurants in New Jersey and Pennsylvania before and after the rise in the minimum. Comparisons of the changes in wages, employment, and prices at stores in New Jersey relative to stores in Pennsylvania (where the minimum remained constant at $4.25 per hour) provide simple robust estimates of the effect of the increased minimum wage. Our empirical findings challenge the conventional notion that a rise in the minimum causes employment to decline. Relative to stores in Pennsylvania, fast food restaurants in New Jersey increased employment by 2.5 employees per store. We also compare employment changes at stores in New Jersey that were initially paying$5.00 per hour or more (and were therefore largely unaffected by the new law) to the employment changes at lower-wage stores, where the new law raised wages by 10-15 percent. Stores that were unaffected by the minimum wage had the same employment growth as stores in Pennsylvania, while stores that had to increase their wages increased their employment. Finally, we evaluate theoretical models that might explain these results. 1993 315 03/1993 eng American Economic Review, Vol. 84, No. 4, September, 1994 Working Papers


text:
An object with a mass of 4 kg is lying still on a surface and is compressing a horizontal spring by 7/8 m. If the spring's constant is 12 (kg)/s^2, what is the minimum value of the surface's coefficient of static friction?

Dec 16, 2017

The coefficient of static friction must be at least 0.268

Explanation:

If the object is motionless, then Newton's first law assures us that the (two) horizontal forces acting on it must be is balance.

These forces are the elastic force of the spring, which is described by Hooke's law:

$F = k x$ where $k$ is the spring constant and x is the amount of compression (or extension) of the spring.

and the force of friction:

${F}_{f} = {\mu}_{s} {F}_{N}$

where ${F}_{N}$ is the normal force between the mass and the surface it rests on, and in the case of a horizontal surface, is equal to $m g$.

Putting it together, we get

$k x = {\mu}_{s} m g$

and, solving for ${\mu}_{s}$:

${\mu}_{s} = \frac{k x}{m g} = \frac{12 \times \frac{7}{8}}{4 \times 9.8} = \frac{10.5}{39.2} = 0.268$

Dec 16, 2017

The coefficient of static friction is $= 0.27$

Explanation:

The mass is $m = 4 k g$

The compression of the spring is $x = \frac{7}{8} m$

The spring constant is $k = 12 k g {s}^{-} 2$

The reaction of the spring is $R = k x = 12 \cdot \frac{7}{8} = 10.5 N$

THe acceleration due to gravity is $g = 9.8 m {s}^{-} 2$

The normal reaction of the object is $N = m g = 4 \cdot 9.8 = 39.2 N$

The coefficient of static friction is

${\mu}_{s} = \frac{R}{N} = \frac{10.5}{39.2} = 0.27$


text:
Representation of lie algebra of SL(2,C)

Lie algebra $$\mathfrak{sl}(2,\mathbb{C})$$ consists of all 2x2 complex
traceless matricies. The space of these matricies is 6-dimensional vector space
over real numbers field but is 3-dimensional space over complex numbers field.
Number of different representations of this algebra depend on how we look at
this algebra. If we assume that it's over complex number then it's just complexification
of $$\mathfrak{su}(2)$$ (all representation might be indexed by one integer or
halfinteger number). However if we treat it as space over real numbers then its
representation are index by pair of (half)integer numbers.


text:
## Summing up Squares

Earlier in the week my son’s math team had a practice problem with this sum:

2 + 5 + 10 + 17 + . . . .

The question was how many terms would it take in order to be above 650?

I though that this problem would make a good starting point for reviewing the formula for the sum of squares:

$1^2 + 2^2 + 3^2 + \ldots + n^2 = (n)(n + 1)(2n + 1) / 6$

This project didn’t go as well as I’d hoped, but maybe there’s a way to come back to it again later to reinforce some of the ideas. The difficulty the kids had – arranging 6 stacks of $1^2 + 2^2 + 3^2$ cubes into a box – comes in the 3rd and 4th videos below.

We started by talking about sums of integers. Of course the infinite sum came up at the end!

With the sums of integers out of the way, we introduced sums of squares. After we wrote down the formula, we started exploring that formula with snap cubes:

Now we studied the slightly more difficult geometric cases of $1^2 + 2^2$ and $1^2 + 2^2 + 3^3$. The second case gave the kids a lot of trouble.

In the last video we weren’t able to construct the box relating to the sum of the first 3 squares. We kept trying here. I didn’t expect this piece to give them as much trouble as it did, so, unfortunately, I didn’t have any good ideas to help them see what to do.

One thing that was interesting to me is that the pattern with the colors seemed to hinder their progress as much as help them:

As prep for this project yeterday, I 3d printed 6 of the block sets for $1^2 + 2^2 + 3^2$. This was a fun 3d printing project all by itself, and came in handy in this project to see if they were able to build the shape without the colors.

Although, as I mentioned above, the color patters seemed to give them as many difficulties as help, my older son thought it was actually harder to build the shape without the colors:

To wrap up the project we took a look at the three pyramids that fold together to make a cube. This idea was a fun project all by itself last year:

A neat geometry project inspired by a James Tanton / James Key tweet

We also looked to see if the sum of squares was approximated well by $n^3 / 3$ for a few values of n.

So, although this one didn’t go exactly as planned, it was still pretty fun. After we finished I had they try to build the box made out of 6 $1^2 + 2^2 + 3^3 + 4^2$ pyramids, and they built that shape pretty quickly.

I like the connection with the sum and the 3 dimensional box and am excited to come up with ways to revisit that connection. I’m also trying to think through ways to show a connection with the sum of cubes and a 4D box – I bet that will be fun!


text:
Running a shell script within Mathematica

The title pretty much explains it and I have not found something similar already posted. Perhaps I am not searching for the correct title or maybe this is something very basic, but I would appreciate any help!

Is there a way within the Mathematica front-end to run a command line argument into the terminal? I am using bash and Mathematica 9.0.

Thanks!

-
This google groups talk about it :) –  Öskå Apr 11 at 10:31
I do not want to sound rude, but please try to search for information on the web first, because the answer given below can easily be found there. –  Wizard Apr 11 at 11:02
@Öskå Thanks, Run[] works perfectly! –  someuser_ Apr 11 at 11:09
@Wizard without wanting to sound rude myself, I already checked the web and could not find the answer. Moreover, since this group is interested in collecting answers to questions about Mathematica, perhaps it is nevertheless useful to have the question posted here. There seems to be enough space on the web for that –  someuser_ Apr 11 at 11:11
@Wizard To be honest, I struggled with getting this to work myself some while ago. I find interaction with external commands to be pretty touchy. Having more, clearer resources on this is in no way a bad thing, I think. –  episanty Apr 11 at 11:23

The command Run will do exactly that. For example, try

Run["touch ~/Desktop/blankfile"]

If you want to read the results back in, there are a few options, and the choice between them depends on exactly what you want to do.

• The RunThrough command lets you read the output of a command-line back as a Mathematica expression. For example, try

RunThrough["bc", 123 + 456]

579

• The OpenRead command can also run external comands, and returns the output as an InputStream object. This can then be accessed using ReadList and related commands, and allows for some fancier manipulations. For a basic example, try

ReadList[OpenRead["!echo hi"]]

Note, in particular, the use of an exclamation mark at the beginning of the OpenRead argument. In general OpenRead["!command"] is equivalent to typing command into a terminal.

I should also mention that for many of the applications you might want to call - including C, C++, Java, .NET, and MATLAB - there are dedicated interfaces which are overwhelmingly likely to be more useful than a direct call on the terminal. Some of these can be accessed on the Calling External Programs guide; to communicate with MATLAB you should use MATLink.

-
Exactly what i need, thanks! –  someuser_ Apr 11 at 11:12
It seems that Run[] does not work with alias commands for me. For example, Run["ls"] returns 0 but I am trying this: Run["matlab -nodesktop -nosplash -r \"creatematrix('RadarFile');quit;\""] and it doesnt work (no 0 return). I am trying to run a Matlab script that reads in a radar data file (of some special format) and saves as .csv so that I can then Import[] with Mathematica. Any suggestions? –  someuser_ Apr 11 at 11:40
If your external script is actually MATLAB then I would strongly urge you to use MATLink. –  episanty Apr 11 at 12:37


text:
## Archive for July, 2011

### A mean value theorem

July 29, 2011

Christine Riedtmann asked me about the proof of the general mean value theorem mentioned in the very first entry of this blog. Let me recall the statement. In what follows ${I}$ is an interval and ${{x_0, \ldots, x_n}}$ are (pairwise distinct) points on ${I}$.

Theorem 1 Let ${{f_0, \ldots, f_n}}$ be ${n}$ times differentiable functions on ${I}$. Then

$\displaystyle \det \bigl[f_i(x_j)\bigr]= \det \left[\frac{f_i^{(j)}(\tau_{ij})}{j!}\right]V(x_0, \ldots, x_n)$

with some ${{\tau_{ij}\in I}}$.

Here ${V(x_0, \ldots, x_n)}$ is the Vandermonde determinant.

The proof is based on the more special Schwarz mean value theorem, also mentioned in that entry. It is more convenient for us to state the Schwarz theorem as follows.

Theorem 2 (Schwarz) Let ${f}$ be an ${n}$ times differentiable function on ${I}$. Denote by ${P(t)}$ the Lagrange interpolation polynomial for ${f}$ at the points ${{x_0, \ldots, x_n}}$ (the polynomial of degree at most~${n}$ taking value ${f(x_j)}$ at ${x_j}$ for ${j=0,\ldots,n}$.) Then for some ${{\tau \in I}}$ we have ${{f^{(n)}(\tau)=P^{(n)}(=P^{(n)}(\tau))}}$.

In this form the Schwarz theorem is immediate: the “auxiliary function” ${{f(t)-P(t)}}$ vanishes at ${{x_0, \ldots, x_n}}$, and by the Rolle theorem its ${n}$-th derivative vanishes somewhere on ${I}$.

To prove Theorem 1 we consider the interpolation polynomials ${P_{ij}(t)}$ of ${f_i}$ at ${{x_0, \ldots, x_j}}$. Let ${{t_0, \ldots, t_n}}$ be independent indeterminates. Elementary transformations of determinants show that

$\displaystyle \det\bigl[P_{ij}(t_j)\bigr] =\frac{\prod_{0\le k< \ell\le n}(t_\ell-x_k) }{V(x_0, \ldots, x_n)}\det\bigl[f_i(x_j)\bigr].$

Applying to the both sides the differential operator

$\displaystyle \frac{1}{0!1!\cdots n!}\,\frac{\partial^{0+1+\cdots+n}}{\partial t_0^0\partial t_1^1\cdots \partial t_n^n},$

we obtain

$\displaystyle \det \left[\frac{P_{ij}^{(j)}}{j!}\right]=\frac{1 }{V(x_0, \ldots, x_n)}\det\bigl[f_i(x_j)\bigr].$

Now the Schwarz theorem implies that ${{P_{ij}^{(j)}= f_i^{(j)}(\tau_{ij})}}$ with a suitably chosen ${\tau_{ij}}$.


text:
# Quora: What is an ALGEBRA structure

What is an algebra? by Tikhon Jelvis https://www.quora.com/What-is-an-algebra/answer/Tikhon-Jelvis?ch=3&share=2dd8711d&srid=oZzP

“Basically, an algebra is just an algebraic structure. It’s some set A along with some number of functions closed over the set. It’s a generalization over the structures we normally study: a group is an algebra, a ring is an algebra, a lattice is an algebra… etc.

Algebras have different “signatures” which specify the functions it has. For example, a group is an algebra that has an identity element, a function of one argument and a function of two arguments.

That is, a group with a carrier set A is just a tuple:
⟨A, 0:A, −:A→A, +:A×A→A⟩

For uniformity, we can write all of these as functions in the form An→A, where n is the “arity” of a function—the number of arguments it has. The identity element is a function A0→A, which just identifies a single element from A. Thus, we can talk about the signature of an algebra as the arities of its functions.

A group would be (0, 1, 2) while a ring would be (0, 0, 1, 2, 2).

Generally, the functions of an algebra have to be associative. Sometimes, we also look at other laws—for example, we might want to study algebras with commutative operations like Abelian groups.

So the intuition for an algebra in general is that it’s any structure like a group, a ring or whatever else we like. As the name “structure” implies, these additional operations on a set expose the internal structure of its elements: a group describes symmetries, a lattice describes a partial order and so on.

The study of algebras, then, can be thought of as the study of “structured sets” in general.”

# BM Category Theory II 8: F-Algebra, Lambek’s Lemma , Catamorphism, Coalgebra, Anamorphism

[Continued from previous BM Category Theory …]

$\boxed { \text {type Algebra f a = f a} \to \text {a} }$

Intuition: [Artificial Intelligence] You teach the computer like to a Primary 6 kid, that Algebra is a type of expression (f) which, after evaluation,  returns a value.

If a = i (initial) [or u (terminal)],
$\boxed { \text {(f i} \to \text {i )} \implies \text {f = Fix-point} }$

Intuition: Fix-point because, the Initial “i”, after evaluating the expression f, returns itself “i”.

Lambek’s Lemma
$\boxed { \text {Initial Algebra is an Isomorphism} }$

Note: Endo-functor is a functor (equivalent to function in Set Theory) within the same Category (Endo = Self = 自)

Video 8.1 F-Algebras & Lambek’s Lemma

Video 8.2 Catamorphism & Anamorphism

foldr ~ catamorphism (浅层变质) of a Fix-point endo-functor on a List.

Examples: Fibonacci, Sum_List

Remark: Cool Math! the more  advanced concept it is, the more closer to Nature (eg.Geology, Biology) : Catamorphism 浅层(风化)变质, or “thin-layer change in nature” (in Functional Programming languages: foldr or map) eg : add1 to a list (1 5 3 8…)
= (2 6 4 9 …)

$\boxed { \text {type Coalgebra f a = a} \to \text {f a} }$

Intuition: Reverse of Algebra, given a value, Coalgebra returns an expression (f).

Anamorphism (合成变质) ~ unfoldr

Example: Prime numbers

Remark: Anamorphism (合成变质) or “synthesised change in nature“: eg. Start from a  “seed” prime number “2” generates  all other infinite prime numbers (3 5 7 9 11 13 17 …)

Note: In Haskell, no difference between Initial and Terminal Fix-points. However, since Fix-point is not unique, in Category Theory there is the Least Fix-point (Initial) and Greatest Fix-point (Terminal).

Ref:

Reading “Understanding F-Algebra ” by BM: https://bartoszmilewski.com/2013/06/10/understanding-f-algebras/

Anamorphism : https://zhuanlan.zhihu.com/cofree/21354189

F-Algebra & F-coalgebra: http://stackoverflow.com/a/16022059/5822795

# Initiation aux Mathématiques Modernes – (TV 1969)

This French Classic (8 series lectures) on “Introduction to Modern Maths” made in 1969 is still valid today for Modern Maths students who need to be “initialized” for abstract, rigorous math, different from high-school maths.

Partie 1 : ensembles et parties

View the other 7 series below:

Initiation à l’algèbre (TV 1969): http://www.youtube.com/playlist?list=PLGwb7STcll74lv38PsnYmB4sr5fpWTEsq

# Analysis -> (Topology) -> Algebra

Mathematics is divided into 2 major branches:
1. Analysis (Continuity, Calculus)
2. Algebra (Set, Discrete numbers, Structure)

In between the two branches, Poincaré invented in 1900s the Topology (拓扑学) – which studies the ‘holes’ (disconnected) in-between, or ‘neighborhood’.

Topology specialised in
–  ‘local knowledge’ = Point-Set Topology.
– ”global knowledge’ = Algebraic Topology.

Example:
The local data of consumer behavior uses ‘Point-Set Topology’; the global one is ‘BIG Data’ using Algebraic Topology.

# The Beauty I See in Algebra

The beauty I see in algebra: Margot Gerritsen at TEDxSTANFORD:

From equations to matrices… to Google search, MRI body scan, …