Archive | problems

There is no excerpt because this is a protected post.

Protected: cache choice conundrum

There is no excerpt because this is a protected post.

ECE 490: projects for 4th credit

$$\def\Real{\mathbb{R}}$$

1. For a smooth function $$f$$ on $$\Real^n$$, consider the gradient descent algorithm
$x_{n+1}=x_n-\eta\nabla f(x_n)$
(here $$\eta>0$$ is a step size.It is known that for almost all starting positions, the iterations of the gradient descent converge to a local minimizer of $$f$$. To ensure convergence for all initial data, it was suggested to perturb the trajectory once in a while, to escape potential trap in saddles, and shown that the procedure works, at least for non-degenerate critical points.What happens at the degenerate critical points?

Shuffling the sheep

$latex \def\xx{\mathbf{x}}\def\Real{\mathbb{R}}$

We consider the problem of flock control: what are the natural constraints on the steering agents in reconfiguring an ensemble of agents?

Our basic setup is following: the agents are modeled as points $latex \xx=(x_1,\ldots,x_n), x_k\in X, k=1,\ldots, N$, with $latex X$ some terrain (for simplicity, we constrain ourselves here to Euclidean plane, but in general it can be some reasonably tame subset of a manifold). Quasi-static behavior is assumed, under which the system, for each value of the controlling parameters quickly settles into (locally minimizing) the equilibrium whose basin of attraction contains current position.…

Protected: Curvilinear Origami

There is no excerpt because this is a protected post.

Fact of the day: Brownian centroids

$latex \def\Real{\mathbb{R}}\def\Z{\mathcal{Z}}\def\sg{\mathfrak{S}}\def\B{\mathbf{B}}\def\xx{\mathbf{x}}\def\ex{\mathbb{E}}$

Consider $latex n$ points in Euclidean space, $latex \xx=\{x_1,\ldots, x_n\}, x_k\in \Real^d, n\leq d+1$.

Generically, there is a unique sphere in the affine space spanned by those points, containing all of them. This centroid (which we will denote as $latex o(x_1,\ldots,x_n)$) lies at the intersection of the bisectors $latex H_{kl}, 1\leq k\lt l\leq n$, hyperplanes of points equidistant from $latex x_k, x_l$.

Assume now that the points $latex x_k,k=1,\ldots,n$ are independent standard $latex d$-dimensional Brownian motions. What is the law of the centroid?…

Fact of the day: Condorset domains, tiling permutations and contractibility

$latex \def\Real{\mathbb{R}}\def\Z{\mathcal{Z}}\def\sg{\mathfrak{S}}\def\B{\mathbf{B}}$

Consider a collection of vectors $latex e_1,\ldots,e_n$ in the upper half-plane, such that $latex e_k=(x_k,1)$ and $latex x_1>x_2\gt \ldots \gt x_n$. Minkowski sum of the segments $latex s_k:=[0,e_k]$ is a zonotope $latex \Z$. Rhombus in this context are the Minkowski sums $latex \Z(k,l)=s_k\oplus s_l, 1\leq k\lt l\leq n$ of pairs of the segments. Tilings of $latex \Z$ by $latex n\choose 2$ rhombuses $latex \Z(k,l)$ define also an oriented graph (formed by the edges of the rhombuses, and oriented up in the plane).…

Topologically constrained models of statistical physics.

$$\def\Real{\mathbb{R}} \def\Int{\mathbb{Z}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}} \def\blob{\mathcal{B}}$$

The Blob

Consider the following planar “spin model”: the state of the system is a function from $$\Int^2$$ into $$\{0,1\}$$ (on and off states). We interpret the site $$(i,j), i,j\in\Int$$ as the plaque, i.e. the (closed) square given by the inequalities $$s_{ij}:=i-1/2\leq x\leq i+1/2; j-1/2\leq y\leq j+1/2$$.

To any configuration $$\eta$$ we associate the corresponding active domain,
$A_\eta=\bigcup_{(i,j): \eta(i,j)=1} s_{ij}.$

We are interested in the statistical ensembles supported by the finite contractible active domains – let’s refer to such domains as blobs.…

$$\def\Real{\mathbb{R}} \def\views{\mathbb{G}} \def\earth{\mathbb{E}} \def\hsp{\mathbb{H}}$$

Google Maps and the Space of Views

Let’s consider the geometry hidden behind one of the best user interfaces in mobile apps ever, – the smartphone maps, the ones which you can swipe, flick and pinch. We are not talking here about the incredible engine that generates the maps on the fly as your finger waddles over the screen – just about the interface, which in a very intuitive and remarkably efficient way allows you to move between various maps.…

unimodal category

We say that a continuous function is unimodal if all the upper excursion sets
$$e_f(c):=\{f≥c\}$$ are contractible. For a nonnegative function
$$f:\mathbb{R}^d\to\mathbb{R}_+$$ with compact support its unimodal category UCat(f) as the least number $$u$$ of summands in a decomposition $$f=\sum_{i=1}^u f_i$$, where all $$f_i$$ are unimodal. Unimodal category is a “soft” version of Lyusternik-Schnirelman category, hence the name. We know how to compute UCat only in one-dimensional situation. In other dimensions, even the simplest questions seem hard, for example:

Find the unimodal category of the suspension of univariate Morse functions, i.e.