Coordinates: KD102, 5 PM 17th Aug 2019
Vazirani and Vidick (2011) introduced a protocol which outputs random bits from a small seed input, using a pair of quantum mechanical devices. Any user can certify the randomness of these bits with a simple classical test. I will be covering all the necessary prerequisites needed to understand the protocol as well.
Coordinates: KD102, 3 PM 5th Aug 2019
Recently Hao Huang proved the famous “Sensitivity Conjecture”, one of the main conjectures about Boolean functions open for last 30 years. Surprisingly, the proof is pretty simple and requires not more than 2 pages to explain completely. I will present preliminaries, context and proof of the conjecture in this talk.
Coordinates: KD102, 10 AM 17th Apr 2019
Lattice-based cryptosystems are the main candidate of Post-quantum cryptography. In this talk, we will cover the reductions between the lattice problem and how there hardness factor is related.
Coordinates: KD102, 5 PM 31st Jan 2019
The downward density of a class of Turing degrees is the following property: given two Turing degrees a and b from that class such that a is less than b, there is a Turing degree c of that class such that a is less than c and c is less than b? If the class of sets computes a minimal degree, then density does not hold. In 1980, Carl Jokusch showed that the class of sufficiently generic sets is dense by establishing that 2-generics are downward dense below a given 2-generic. In 1990 Kumabe, and independently, Chong and Downey established that 1-generics are not dense, by constructing a minimal degree computable from a 1-generic. For a well-studied intermediate notion, weakly 2-generics, the density question was open. We settle the question by showing that there is a minimal degree computable from a weakly 2-generic. The proof uses a technique from recursion theory called full approximation. (This is joint work with Rod Downey.)
Coordinates: KD102, 5 PM 17th Jan 2019
We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear depth-4 circuit of size at most exp({O(\sqrt{nlog n}). For degree d = omega(n/log n), this improves upon the upper bound of exp({O(\sqrt{d}\log n)} obtained by Tavenas for general (non-multilinear) circuits, and is known to be asymptotically optimal in the exponent when d is less than n^{\epsilon} for a small enough constant epsilon. Our upper bound matches the lower bound of exp({Omega(\sqrt{nlog n})} proved by Raz and Yehudayoff, and thus cannot be improved further in the exponent. Based on joint work with Mrinal Kumar and Rafael Oliveira.
Coordinates: KD103, 5 PM 10th Jan 2019
Whether checking a solution of a computational problem is easier than computing a solution is captured by the famous P vs NP question. Valiant asked a related question, whether any string function, for which it can be checked in polynomial time whether it takes a given value, can also be evaluated in polynomial time. In complexity theory (Boolean)/cryptography, the answer is expected to be negative, as it would rule out the existence of one way functions otherwise. But in the algebraic complexity setting, the answer is expected to be positive. In this talk, we present results due to Sturtivant and Zhang (FOCS ‘90) and Burgisser (FOCS’ 01) that partially resolve the above question in algebraic setting. The question is related to two concrete problems about polynomials and arithmetic circuits (1) Given an invertible polynomial map given as a small arithmetic circuit, whether its inverse map also has a small circuit (2) Given a reducible polynomial computed by an arithmetic circuit, whether its factors of low degree have small sized arithmetic circuits. For both the problems, the key tool used is Newton iteration for root finding.
Coordinates: KD101, 5 PM 2nd Jan 2019
In a sequence of seminal results in the 80’s, Kaltofen showed that if an n-variate polynomial of degree poly(n) can be computed by an arithmetic circuit of size poly(n), then each of its factors can also be computed an arithmetic circuit of size poly(n). In other words, the complexity class VP (the algebraic analog of P) of polynomials, is closed under taking factors.
A fundamental question in this line of research, which has largely remained open is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, constant depth arithmetic circuits or the complexity class VNP (the algebraic analog of NP) of polynomials, are closed under taking factors. In addition to being fundamental questions on their own, such ‘closure results’ for polynomial factorization play a crucial role in the understanding of hardness randomness tradeoffs for algebraic computation.
I will talk about the following two results, whose study was motivated by these questions.
The class VNP is closed under taking factors. This proves a conjecture of B{"u}rgisser.
All factors of degree at most poly(log n) of polynomials with constant depth circuits of size poly(n) have constant (a slightly larger constant) depth arithmetic circuits of size poly(n). This partially answers a question of Shpilka and Yehudayoff and has applications to hardness-randomness tradeoffs for constant depth arithmetic circuits.
Based on joint work with Chi-Ning Chou and Noam Solomon.
Coordinates: KD102, 4 PM 1st Sept 2018
In this talk, we shall discuss about Hoza and Zuckerman’s recent construction of explicit HSGs for boolean read-once branching programs (ROBPs) (Hoza, Zuckerman, FOCS 2018).
A $\epsilon$-HSG for ROBPs is a function $G$ such that if an ROBP has acceptance probability at least $\epsilon$ using perfect randomness, then it has nonzero acceptance probability using the output of $G$ with a random seed. One way to prove RL=L is constructing a $1/2$-HSG for width-$n$, length-$n$ ROBPs with seed length $O(\log n)$ that can be simulated in logspace.
Hoza and Zuckerman recently obtained a simple construction of explicit HSGs that improves previously known HSGs. In particular, their generator has seed length $o(\log n\log r)$ for ROBPs of length $r=n^{o(1)}$, improving Nisan’s generator (Nisan, 1992) which has seed length $O(\log n\log r)$.
Coordinates: KD102, 12:15 PM 25th Aug 2018
In this talk,we will focus on two fundamental problems in Lattice Theory, First one is Shortest Vector Problem (SVP) where we find shortest non-zero vector in Lattice. The other one is Closet Vector Problem (CVP) where we find closet Lattice point of a given vector. These problems have applications in Integer Factorization, post-Quantum Cryptography. Security of the lattice-based cryptosystem is based on the hardness of these problems. We will show that both the problems are NP-hard within some constant approximation factor.
No prior knowledge related to lattice is required.
References:
Arora, S., Babai, L., Stern, J., and Sweedyk, Z. (1993, November). The hardness of approximate optima in lattices, codes, and systems of linear equations. In Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on (pp. 724-733). IEEE.
D. Micciancio The shortest vector problem is NP-hard to approximate to within some constant. SIAM Journal on Computing 30(6):2008-2035 (March 2001)
Coordinates: KD102, 4 PM 18th Aug 2018
Given a multiset of n positive integers and a target integer t, the SubsetSum problem asks to determine whether there exists a subset of S that sums up to t. Bringmann (SODA’17) gave a randomized O(n+t) time algorithm (hiding polylogarithmic factors) which is believed to be near optimal. In this paper, Jin and Wu (Wu is a high school student in China!) give a very simple and elegant randomized algorithm matching the running time of Bringmann.
This paper follows the approach of using algebraic techniques (manipulating polynomials) to design faster algorithms for hard combinatorial problems. Time permitting, we shall discuss some of the other recent applications of this approach.