This work deals with exploiting the low-dimensional hierarchical structure of speech signals towards the  goal  of  improving  acoustic  modelling using deep neural networks (DNN).  To this aim the work employ tools from sparsity aware signal processing under novel frameworks to enrich  the  acoustic  information  present  in  DNN posterior features. 

Graphs are a central object of study in various scientific fields, such as discrete mathematics, theoretical computer science and network science. These graphs are typically studied using combinatorial, algebraic or probabilistic methods, each of which highlights the properties of graphs in a unique way. I will discuss a novel approach to study graphs: the simplex geometry (a simplex is a generalized triangle). This perspective, proposed by Miroslav Fiedler, introduces techniques from (simplex) geometry into the field of graph theory and conversely, via an exact correspondence. We introduce the graph-simplex correspondence, identify a number of basic connections between graph characteristics and simplex properties, and suggest some applications as example.

Reference: https://arxiv.org/abs/1807.06475
 

Pseudorandom functions (PRFs) are one of the fundamental building blocks in cryptography. Traditionally, there have been two main approaches for PRF design: the ``practitioner's approach'' of building concretely-efficient constructions based on known heuristics and prior experience, and the ``theoretician's approach'' of proposing constructions and reducing their security to a previously-studied hardness assumption. While both approaches have their merits, the resulting PRF candidates vary greatly in terms of concrete efficiency and design complexity. In this work, we depart from these traditional approaches by exploring a new space of plausible PRF candidates. Our guiding principle is to maximize simplicity while optimizing complexity measures that are relevant to cryptographic applications. Our primary focus is on weak PRFs computable by very simple circuits (depth-2 ACC^0 circuits). Concretely, our main weak PRF candidate is a ``piecewise-linear'' function that first applies a secret mod-2 linear mapping to the input, and then a public mod-3 linear mapping to the result. We also put forward a similar depth-3 strong PRF candidate.  
The advantage of our approach is twofold. On the theoretical side, the simplicity of our candidates enables us to draw many natural connections between their hardness and questions in complexity theory or learning theory (e.g., learnability of depth-2 ACC^0 circuits and width-3 branching programs, interpolation and property testing for sparse polynomials, and natural proof barriers for showing super-linear circuit lower bounds). On the applied side, the piecewise-linear structure of our candidates lends itself nicely to applications in secure multiparty computation (MPC). Using our PRF candidates, we construct protocols for distributed PRF evaluation that achieve better round complexity and/or communication complexity (often both) compared to protocols obtained by combining standard MPC protocols with PRFs like AES, LowMC, or Rasta (the latter two are specialized MPC-friendly PRFs).
Finally, we introduce a new primitive we call an encoded-input PRF, which can be viewed as an interpolation between weak PRFs and standard (strong) PRFs. As we demonstrate, an encoded-input PRF can often be used as a drop-in replacement for a strong PRF, combining the efficiency benefits of weak PRFs and the security benefits of strong PRFs. We conclude by showing that our main weak PRF candidate can plausibly be boosted to an encoded-input PRF by leveraging standard error-correcting codes.
Joint work with Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu.

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus qq. For a polynomial L, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed L-bit bitstrings x, y and z are the binary representations of integers X, Y and Z satisfying Z=X+Y over the integers. The complexity of our arguments is only linear in L. Using them, we construct arguments allowing to prove inequalities X <Z among committed integers, as well as arguments showing that a committed X belongs to a public interval [α,β], where α and β can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in L) in the maximal range magnitude. Using these tools, we obtain zero-knowledge arguments showing that a committed element X does not belong to a public set S using soft-O(n⋅log|S|) bits of communication, where n is the security parameter. We finally give a protocol allowing to argue that committed L-bit integers X, Y and Z satisfy multiplicative relations Z=XY over the integers, with communication cost subquadratic in L. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba's multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.

TBA

Convex and in particular semidefinite relaxations (SDP) for non-convex continuous quadratic optimisation can provide tighter bounds than traditional linear relaxations. However, using SDP relaxations directly in Branch&Cut is impeded by lack of warm starting and inefficiency when combined with other cut classes, i.e. the reformulation-linearization technique. We present a general framework based on machine learning for a strong linear outer-approximation that can retain most tightness of such SDP relaxations, in the form of few strong low dimensional linear cuts selected offline. The cut selection complexity is taken offline by using a neural network estimator (trained before installing solver software) as a selection device for the strongest cuts. Lastly, we present results of our method on QP/QCQP problem instances.

If k is a field of characteristic zero, a theorem of Lurie and Pridham establishes an equivalence between formal moduli problems and differential graded Lie algebras over k. We generalise this equivalence in two different ways to arbitrary ground fields by using “partition Lie algebras”. These mysterious new gadgets are intimately related to the genuine equivariant topology of the partition complex, which allows us to access the operations acting on their homotopy groups (relying on earlier work of Dyer-Lashof, Priddy, Goerss, and Arone-B.). This is joint work with Mathew.

Let $G$ be a regular graph of degree $d$ and let $A\subset V(G)$. Say that $A$ is $\eta$-closed if the average degree of the subgraph induced by $A$ is at least $\eta d$. This says that if we choose a random vertex $x\in A$ and a random neighbour $y$ of $x$, then the probability that $y\in A$ is at least $\eta$. In recent joint work with Tim Gowers, we were aiming to obtain a qualitative description of closed subsets of the Cayley graph $\Gamma$ whose vertex set is $\mathbb{F}_2^{n_1}\otimes \dots \otimes \mathbb{F}_2^{n_d}$ with two vertices joined by an edge if their difference is of the form $u_1\otimes \cdots \otimes u_d$. For the matrix case (that is, when $d=2$), such a description was obtained by Khot, Minzer and Safra, a breakthrough that completed the proof of the 2-to-2 conjecture. We have formulated a conjecture for higher dimensions, and proved it in an important special case. In this talk, I will sketch this proof. Also, we have identified a statement about $\eta$-closed sets in Cayley graphs on arbitrary finite Abelian groups that implies the conjecture and can be considered as a "highly asymmetric Balog-Szemerédi-Gowers theorem" when it holds. I will present an example to show that this statement is not true for an arbitrary Cayley graph. It remains to decide whether the statement can be proved for the Cayley graph $\Gamma$.

In the classical theory of fluid mechanics, a linear relationship between the stress and rate of strain is often assumed. Even when this relationship is non-linear, it is typically formulated in terms of an explicit relation. Implicit constitutive theories provide a theoretical framework that generalises this, allowing a, possibly multi-valued, implicit constitutive relation. Since it is not possible to solve explicitly for the stress in the constitutive relation, a more natural approach would be to include the stress as a fundamental unknown in the formulation of the problem. In this talk I will present a formulation with this feature and a proof of convergence of the finite element approximations to a solution of the original problem.