Friday Aug 29	Abhiram Natarajan Purdue	HAAS 101, 1-2pm. Title: Computational Complexity of Certifying Restricted Isometry Property Abstract: A matrix is (k, delta)-RIP if, when multiplied on the left, it preserves the 2-norm of k-sparse vectors within a delta threshold of the original magnitude. In many applications, such as compressed sensing and sparse recovery, it is desirable to construct RIP matrices with a large k and a small delta. Deterministic constructions are not very effective in giving large k, while randomized methods are extremely effective. Given the efficacy of random constructions in generating useful RIP matrices, the problem of certifying the RIP parameters of a matrix has become important. In this paper, we prove that it is hard to approximate the RIP parameters of a matrix assuming the Small-Set-Expansion-Hypothesis. In order to prove the hardness result, we prove a variant of the Cheeger's Inequality for sparse vectors. This is joint work with Yi Wu.
Mon Sept 8	Abram Magner Purdue	HAAS 111, 2-3pm. Title: Variance of Size in Regular Graph Tries Abstract: Graph tries are a generalization of classical digital trees: instead of being built from strings, a $G$-trie is built from label functions on the graph $G$. In this work, we determine leading order asymptotics for the variance of the size of a $G$-trie built on a memoryless source on a uniform alphabet distribution, where $G$ is a member of a large class of infinite, $M$-regular directed, acyclic graphs with $M>1$ fixed. In particular, this covers the cases of trees and grids. We find that, in such tries, the variance is of order $\Theta(n^{\rho'})$, for some $\rho'$ depending on $G$ which is minimized when $G$ is a tree (the analysis for the tree case was covered in a previous work). We also give an explicit expression for $\rho'$ in the case where $G$ is a grid, with $M=2$. Joint work with Philippe Jacquet
Mon Oct 6	Mahdi Cheraghchi MIT	HAAS 111, 2-3pm. Title: Capacity and Constructions of Non-Malleable Codes Abstract: Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010) and motivated by applications in tamper-resilient cryptography, encode messages in a manner so that tampering the codeword causes the decoder to either output the correct message or an uncorrelated message. While this relaxation of error detection is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against any fixed family of tampering functions that is not too large. In this talk, I will discuss the following: 1. "Capacity" of non-malleable codes: For any tampering family of a prescribed size, we derive an explicit lower bound on the maximum possible rate of a non-malleable code against the given family. Furthermore, we show that this bound is essentially optimal. 2. An efficient Monte-Carlo construction of non-malleable codes against any family of tampering functions of exponential size (e.g., polynomial-sized Boolean circuits). Codes obtained by this construction achieve rates arbitrarily close to 1 and do not rely on any unproven assumptions. 3. The specific family of bit-tampering adversaries, that is adversaries that independently act on each encoded bit. For this family, we are able to obtain an explicit construction of non-malleable codes achieving rate arbitrarily close to 1. Based on joint work with Venkatesan Guruswami and articles arXiv:1309.0458 (ITCS 2014) and arXiv:1309.1151 (TCC 2014).
Fri Oct 17	Karthik Chandrasekaran UIUC	HAAS 111, 12:01pm. Title: Finding small stabilizers for unstable graphs Abstract: An undirected graph G is stable if its inessential vertices (those that are exposed by at least one maximum matching) form a stable set. Stable graphs play an important role in cooperative game theory and network bargaining. In this talk, I will focus on the following edge-deletion problem: given a graph G, can we find a minimum cardinality subset of edges whose removal yields a stable graph? I will show that the removal of any such minimum cardinality subset of edges does not decrease the cardinality of the maximum matching in the graph. This insight will be used to show that the problem is vertex-cover hard and also to develop efficient approximation algorithms for sparse graphs and for regular graphs. Based on joint work with Adrian Bock, Jochen Koenemann, Britta Peis and Laura Sanita.
Fri Oct 24	Thanh Nguyen Purdue, Krannert School of Management	HAAS 111, 12-1pm. Title: Near Feasible Stable Matchings with Complementarities Abstract: The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable matching problem has a `nearby' instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Our approach is general and applies to other type of complementarities, as well as matchings with side constraints and contracts. http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2500824 Joint work with Rakesh Vohra
Fri Nov 21	Robert McGrail Professor, Bard College	HAAS 111, 1-2pm. Title: CSPs and Connectedness: P/NP Dichotomy for Idempotent, Right Quasigroups Abstract: In the 1990's, Jeavons showed that every finite algebra corresponds to a class of constraint satisfaction problems. Vardi later conjectured that idempotent algebras exhibit P/NP dichotomy: Every non NP-complete algebra in this class must be tractable. Here we discuss how tractability corresponds to connectivity in Cayley graphs. In particular, we show that dichotomy in finite idempotent, right quasigroups follows from a very strong notion of connectivity. Moreover, P/NP membership is first-order axiomatizable over involutory quandles. (The talk will be mostly self-contained).
Fri Dec 5	Edinah Gnang Purdue, Math	LWSN 3102, 12-2pm. Yes, 2 hrs, whiteboard talk! Note the unusual location too. Title: Approximating the spectrum of matrices and hypermatrices Abstract: We will motivate and present a natural generalization of the algebra of matrices to an algebra of hypermatrices proposed by Bhattacharya-Mesner in the 90s. We will show how the proposed algebra extends to hypermatrices classical notions such as matrix Inverse, Gram-Schmidt process, Unitarity, Combinatorial Interpretations of the Cayley-Hamilton theorem as well as the Spectral Theorem. We will show how this new languages provide a family of new invariants for addressing combinatorial optimization problems which include special instances of graph and subgraph Isomorphism problems. (The talk will be mostly self-contained)

Link to schedule forSpring 2014. Fall 2013. Spring 2013. Fall 2012.