Weekly Seminar

This is the weekly seminar page for our awesome research group. Our talks are on no specific topic and can range within any topic in theoretical computer science. The talks are deliberately informal, sometimes chaotic, but always cool.

We meet (almost) every Friday at 12noon (or so). Afterwards we eat cake and socialise.

Location is at COM3-02-70 (Meeting Room 25), School of Computing, NUS unless otherwise stated.

If you would like to join our seminar channel on slack for notifications, you may contact Zeyong (li.zeyong@u.nus.edu) or Maciej (cqtmlo@nus.edu.sg) or Pranjal (duttpranjal@gmail.com).

Upcoming Talk:

Title: Quantum Algorithms in a Superposition of Spacetimes

Speaker: Shashwat Agrawal

Abstract: This talk will be based on a recent work by Omri Shmueli: “Quantum Algorithms in a Superposition of Spacetimes” where he introduces a computational model inspired by quantum gravitational effects such as spacetime superposition. The model essentially allows a quantum computer access to an oracle (called Order Interference or OI) that computes superpositions of unitary evolution orders. The author then defines a relaxed variant of the Statistical Difference problem called the Sequentially Invertible Statistical Difference (SISD) problem and shows that with suitable parameters, SISD is decidable by an efficient quantum algorithm with the above oracle access (i.e. it is in the complexity class BQP^{OI}). Finally it is shown that the Graph Isomorphism Problem and the Gap Closest Vector Problem (for approximation factor O(n^{3/2})) which are believed to be hard problems even for quantum computers are classically poly-time reducible to SISD with suitable parameters, which shows that these problems are also in BQP^{OI}.

Time: Friday, 22 November 2024, 12:30 PM

Location: COM3-02-70 (Meeting Room 25)

Past Talks:

Title: Polynomials Power Computation

Speaker: Pranjal Dutta

Time: Friday, 15 November 2024, 12:30 PM

Location: COM3-02-70 (Meeting Room 25)

Title: Tree Evaluation in o(log^2(n)) SPACE.

Speaker: Li Zeyong

Abstract: I will talk about recent result by Cook and Mertz (2024) showing that Tree Evaluation is in O(log n log log n) SPACE. Tree Evaluation is postulated to be a good candidate for separating P and LOGSPACE. I will follow the exposition by Goldreich (2024).

Time: Friday, 08 November 2024, 12:30 PM

Location: COM3-02-70 (Meeting Room 25)

Title: Hilbert Functions and Low-Degree Randomness Extractors

Speaker: Satyajeet Nagargoje

Abstract: For $S\subseteq \F^n$, consider the linear space of restrictions of degree-$d$ polynomials to~$S$. The~Hilbert function of $S$, denoted~$\h_S(d,\F)$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\F^n$ with a fixed size $|S|$. We achieve this by proving that this value coincides with a combinatorial quantity, namely the smallest number of low Hamming weight points in a down-closed set of size $|S|$. Understanding the smallest values of Hilbert functions is closely related to the study of degree-$d$ closure of sets, a notion introduced by Nie and Wang (Journal of Combinatorial Theory, Series A, 2015). We use bounds on the Hilbert function to obtain a tight bound on the size of degree-$d$ closures of subsets of $\F_q^n$, which answers a question posed by Doron, Ta-Shma, and Tell (Computational Complexity, 2022). We use the bounds on the Hilbert function and degree-$d$ closure of sets to prove that a random low-degree polynomial is an extractor for samplable randomness sources. Most notably, we prove the existence of low-degree extractors and dispersers for sources generated by constant-degree polynomials and polynomial-size circuits. Until recently, even the existence of arbitrary deterministic extractors for such sources was not known.

Joint work with: Alexander Golovnev, Zeyu Guo, Pooya Hatami, Chao Yan.

Time: Friday, 18 October 2024, 12:30 PM

Location: COM3-02-70 (Meeting Room 25)

Title: Tightly relating L_1 and L_{\infty} norms of polynomials over reals.

Speaker: Vipul Arora

Abstract: I will present a new result, that gives tight upper, and lower bounds for the L_{\infty} norm of an individual degree-d, n-variate polynomial with real coefficients, over the solid cube [-1,1]^n, in terms of its L_1 norm, over the same solid cube. The techniques used are elementary real analysis, Legendre polynomials, and a lesser known inequality about polynomials and their derivatives, proven by Vladimir Markov.

Time: Friday, 11 October 2024, 12:30 PM

Location: COM3-02-70 (Meeting Room 25)

Title: When is SETH not useful for showing tight lower bounds?

Speaker: Rucha Kulkarni

Abstract: SETH is a widely believed conjecture that essentially states that k-SAT does not have a sub-exponential time algorithm. SETH has allowed us to prove tight lower bounds for numerous other problems via fine-grained reductions to k-SAT. This leads to the natural question - `For what kind of problems can we NOT prove tight lower bounds using SETH or similar conjectures’? In this talk, we will discuss the following SOSA 2024 paper by Kulikov and Mihajlin, that gives one interesting answer to this question.

Title of the paper: If Edge Coloring is Hard under SETH, then SETH is False

Abstract: The Edge Coloring problem is notoriously hard: it is still unknown whether it can be solved in time 2^o(n^2)(let alone 2^O(n) where n is the number of nodes of the input graph. Can one explain the lack of such upper bounds by deriving a lower bound 2^Ω(n^2) from a lower bound for SAT, 3-SUM, or APSP? In this note, we provide a negative answer for this question: if there is a reduction showing that Edge Coloring cannot be solved faster than in α^n^2 (where α > 1 is an explicit constant) under a hypothesis that known algorithms for one of the problems mentioned above are optimal, then the corresponding hypothesis is false.

Link: https://epubs.siam.org/doi/10.1137/1.9781611977936.12

Time: Friday, 04 October 2024, 1:00 PM

Location: COM3-02-70 (Meeting Room 25)

Title: MPC in the head signatures: from Dlog to SBC (subfield bilinear collisions)

Speaker: Antoine Joux

Abstract: In this talk, we will discuss the main ideas underlying MPC-in-the-head signature schemes. As a first example, we show how to realize such a signature based on the hardness of discrete logarithms. Then, we introduce and motivate the SBC problem, which turns out to be an extremely effective (post-quantum) candidate for MPC-in-the-head signatures.

Time: Friday, 20 September 2024, 12:30 PM

Location: COM3-02-70 (Meeting Room 25)

Title: Exponential Time Hypothesis implies Parametrised Inapproximability Hypothesis

Speaker: Rishav Gupta

Abstract: In this talk we'll talk about “Parametrised Inapproximablity hypothesis” (PIH) and look at its connections with PCP. Then we will sketch out and summarise the paper "Parameterised Inapproximability Hypothesis under ETH"(STOC'24) [GLRSW24]. We will also try to sketch out the proof of GAP-ETH implies PIH, and state why the result is like parametrised PCP but not exactly parametrised PCP and more.

Time: Friday, 13 September 2024, 12:30 PM

Location: COM3-02-70 (Meeting Room 25)

Title: Exponential lower bound via exponential sums.

Speaker: Saswata Mukherjee

Abstract: Valiant’s famous VP vs. VNP conjecture states that the symbolic permanent polynomial does not have polynomial-size algebraic circuits. However, the best upper bound on the size of the circuits computing the permanent is exponential. Informally, VNP is an exponential sum of VP-circuits. [Burgisser, Computational Complexity2004] has proved a super-polynomial lower bound in constant free model (where the only constants we can use for free are +1,-1), assuming the famous Shub-Smale 𝛕-conjecture. In a recent work, we study whether, in general, exponential sums (of algebraic circuits) require exponential-size algebraic circuits. We show that the famous Shub-Smale 𝛕-conjecture indeed implies such an exponential lower bound for an exponential sum. Our main tools come from parameterized complexity. In this talk I'll mainly sketch the background, previous result by Burgisser, it's barriers and in brief how parameterization helps in improvement. It is based on the work, jointly with Somnath Bhattacherjee (UToronto), Markus Blaeser (Saarland University) and Pranjal Dutta (NUS) that appeared in ICALP'24.

Time: Friday, 6 September 2024, 12:30 PM

Location: COM3-02-70 (Meeting Room 25)

Title: Derandomizing Multivariate Polynomial Factoring for Low Degree Factors.

Speaker: Pranjal Dutta

Abstract: Multivariate polynomial factorization is one of the most fundamental problems in Computational algebra, with applications in algebraic property testing, hardness vs. randomness tradeoff, error correction codes, Polynomial Identity Testing, among others. In a series of influencial work, Kaltofen (STOC'86) finally gave a randomized polynomial time algorithm to factor multivariate polynomials.

In this talk, I'll sketch a very special case to output constant degree factors of a given sparse polynomial deterministically. Our proof works for a much more general model.

This is from a recent joint work with Amit Sinhababu (CMI) and Thomas Thierauf (Ulm University), that appeared in RANDOM 2024 and got invited to Theory of Computing.

Time: Friday, 30 August 2024, 12 Noon

Location: COM3-02-70 (Meeting Room 25)

Title: Basis reduction for codes.

Speaker: Noah Stephens-Davidowitz

Abstract: We will discuss and expand on recent exciting work of Debris-Alazard, Ducas, and van Woerden (DDvW), which introduced the notion of basis reduction for codes, in analogy with the extremely successful paradigm of basis reduction for lattices. In particular, DDvW showed an analogue of the LLL algorithm (an incredibly important algorithm in the lattice setting) that works for codes, and they show how to use this algorithm to provide small but non-trivial speedups to code cryptanalysis.

We will present this LLL algorithm and then show some new generalizations and variants of it. Some of our algorithms are rather pathological, as they are in some sense not interesting in their own right but rather because they illustrate that basis reduction for codes is really a rather silly thing to think about. We will also show basis reduction algorithms that don’t seem so silly. So, we’ll end up rather confused.

Based on joint work with Surendra Ghentiyala (to appear in approx 2024, and hopefully eventually online as well).

Time: 10 July (Wednesday), 2pm.

Title: Solving Integer Programming in Polynomial Time in Total Regime

Speaker: Divesh Aggarwal

Abstract: The classical Erdős-Graham theorem asserts the existence of non-negative integer solutions x_1, ..., x_n to the equation a_1 x_1 + ... + a_n x_n = b, where a_1 < a_2 < ... < a_n are positive integers and b > a_n^2 / (n-1). The problem of finding such an x_1,...,x_n is known as the unbounded subset sum problem.

In this talk, we explore this theorem and its extensions. We begin by introducing a straightforward polynomial-time greedy algorithm that finds a solution when b satisfies a slightly strengthened condition. Building upon this, we generalize the problem to finding non-negative integers x_1,..,x_n that simultaneously satisfy d such equations.

Our main result provides a near-optimal characterization of when such systems of equations have non-negative integer solutions. We give a polynomial-time algorithm to solve this generalized problem.

This talk will only need background in elementary number theory.

Joint work with Antoine Joux, Miklos Santha, and Karol Wegrzycki

Time: 2nd July (Tuesday), 2pm.

Title: Removing Envy using Rainbows and Charity

Speaker: Rucha Kulkarni

Abstract: This talk is a gentle introduction to the problem of finding approximately envy-free allocations, a central problem in fair division theory. The setting of the problem is a set of indivisible goods that must be distributed among a set of agents in a fair manner according to agent preferences; for example, assigning classes to undergrads according to their preferences when each class has limited seats.

The focus of this talk is the envy-free up to any good (EFX) fairness objective. I will introduce the EFX notion and two crucial ideas that together helped make great progress towards solving it- envy graph cycle elimination, and rainbow cycle numbers. We will first discuss the envy graph cycle elimination method and see how it solves a simpler objective than EFX, namely envy-freeness up to one good (EF1), completely. We will then discuss rainbow cycle numbers, and how the two ideas together almost solve EFX, so long as a few goods are donated to charity.

The talk is based on the work ‘Improving EFX guarantees through rainbow cycle number’ by Chaudhury, Garg, Mehlhorn, Mehta and Misra.

Time: 30 May (Thursday), 2024. 12noon.

Location: COM1-02-09.

Title: Succinct Data Structures.

Speaker: Renfei Zhou

Abstract: This talk is a tutorial session on succinct data structures, which is a field studying how to reduce the space usage of data structures to the extreme without losing much on the running time. We provide a high-level view of the field and illustrate 2-3 commonly used techniques via a toy example -- the rank problem.

Time: 17 May, 2024. 12Noon.

Title: Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem .

Speaker: Siyao Guo.

Abstract: In the (preprocessing) Decisional Diffie-Hellman (DDH) problem, we are given a cyclic group $G$ with a generator $g$ and a prime order $N$, and want to prepare some advice of $S$, such that we can efficiently distinguish $(g^{x},g^{y},g^{xy})$ from $(g^{x},g^{y},g^{z})$ in time $T$ for uniformly and independently chosen $x,y,z$ from $[N]$. This is a central cryptographic problem whose computational hardness underpins many widely deployed schemes such as the Diffie–Hellman key exchange protocol.

We prove that any generic preprocessing DDH algorithm (operating in any cyclic group) achieves an advantage at most $O(ST^2 / N)$. This bound matches the best-known attack up to poly-log factors, and confirms that DDH is as secure as the (seemingly harder) discrete logarithm problem against preprocessing attacks. Our result resolves an open question by Corrigan-Gibbs and Kogan (EUROCRYPT 2018), which proved optimal bounds for many variants of discrete logarithm problems except DDH (with an $\Tilde{O}(\sqrt{ST^2/N})$ bound).

Joint work with Akshima (NYU Shanghai), Tyler Besselman (NYU Shanghai), Zhiye Xie (NYU Shanghai), and Yuping Ye (NYU Shanghai & ECNU).

Time: 9 May, 2024. 1PM.

Venue: COM2-02-26 - MR3 @ COM2

(Note the change in date to 1PM Thursday, and change in venue)

Title: One-Way Functions and Zero Knowledge.

Speaker: Li Zeyong.

Abstract: In this talk we will see that assuming NP is contained in CZKP(computational zero knowledge proof) and worst-case hard implies the existence of one-way function. This is a recent result by Shuichi Hirahara and Mikito Nanashima: https://eccc.weizmann.ac.il/report/2024/063/

Time: 3 May, 2024. 12 Noon.

Title: On Computing Optimal Representations of Finite Groups.

Speaker: Dhara Thakkar.

Abstract: Abstract: For a finite group G of order n, a generating set of minimum size is called a minimum generating set of G. A Cayley table for G is a representation of a group to an algorithm. It stores the product of the ith and jth element for each i,j \in \{1,2,..,n\}. Given a group G of order n, by its Cayley table, output the size of a minimum generating set problem is known as the minimum generating set (MIN-GEN) problem. The MIN-GEN problem admits a trivial algorithm that runs in time n^{\log n+O(1)}. In this talk, I will present a polynomial time algorithm that solves the MIN-GEN problem for arbitrary groups. Our algorithm also finds one minimum generating set for a given group.

Cayley's theorem says that every finite group G can be viewed as a subgroup of a symmetric group S_m for some integer m. The \emph{minimal faithful permutation degree} \mu(G) of a finite group G is the smallest integer m such that there is an injective homomorphism \phi from G to S_m. I will present a randomized polynomial time algorithm for computing the minimal faithful permutation degree of permutation groups without any abelian normal subgroups.

This talk is based on the joint work with Bireswar Das, and Andrea Lucchini.

Time: 19 April, 2024. 12 Noon.
Zoom Link: https://nus-sg.zoom.us/j/83245372469?pwd=YmYzUlNGSFg5aWxWWldVM3MxdFNJZz09

Title: Information-theoretically secure disctributed comparison functions.

Speaker: Kruglik Stanislav.

Abstract: In this talk, I consider the problem of constructing information-theoretically secure function secret-sharing schemes for special interval functions f_{\alpha,\beta}^{<} that evaluate to \beta on inputs lesser than \alpha and to zero on all other inputs. These schemes are known under the name of distributed comparison functions (DCF). I present a recently introduced construction of t private DCF for d(t+1) servers for any positive integer d, with a key size of O(n^{1/d}*s*log(p)) for an output group of size p^s (https://eprint.iacr.org/2024/453). Additionally, I will provide intuition on how to verify that the function is correctly computed, also known as ensuring the verifiability property.

Time: 12 April, 2024. 12 Noon.

Title: Assorted Topics.

Speaker: Maciej Obremski, Zeyong Li, Eldon Chung.

Abstract: We will go through an assortment of topics ranging from hash function family sizes, to complexity theory, to streaming algorithms.

Time: 05 Mar, 2024. 12 Noon.

Title: SETH-reduction provides: (arithmetic circuit) Lower Bound or (series-parallel Boolean circuit) Lower Bound.

Speaker: Zeyong Li.

Abstract: I will go through the example in the recent result by Belova et al. (https://arxiv.org/abs/2205.07709). In essence, they show that if we have SETH-reduction for a class of problems (e.g. Hamiltionian Path), then we either have some form of arithmetic circuit Lower Bound, or break NSETH (and hence obtain a series-parallel Boolean circuit Lower Bound).

Time: 22 Mar, 2024.

Title: Online bipartite matching with imperfect advice

Speaker: Davin Choo

Abstract: Consider the classic online unweighted bipartite matching problem with n offline vertices and n online vertices where one wishes to be competitive against the optimal offline algorithm. The classic algorithm to solve this is the RANKING algorithm [KVV'90] which achieves a competitive ratio of 1-1/e > 1/2. In this talk, we explore the possibility of improving the competitive ratio using imperfect advice where the typical metrics to evaluate such algorithms are consistency (how well you do with perfect advice) and robustness (how well you do with arbitrarily bad advice). Under the adversarial arrival model, we show that no such method can be both 1-consistent and strictly better than 1/2-robust. However, under the weaker random order arrival model, we show how one can utilize methods from distribution testing to design an algorithm whose competitive ratio provably interpolates between 1 and beta, where beta is the best attainable ratio under random order arrival depending on the advice quality.

This talk is based on joint work (under submission to ICML) with Chun Kai Ling, Themis Gouleakis, and Arnab Bhattacharyya.

Time: 15 Mar, 2024, 12noon.

Location: COM3-02-70 .

Title: Entropy Estimation in the Streaming Model.

Speaker: Suparno Ghoshal.

Abstract: The talk will be primarily on the task of estimating the Shannon entropy $H(p)$ of a k-ary distribution with an $\epsilon$-accuracy, by considering

samples in the streaming model with a restriction on the memory space. In the study of entropy estimation it has always been an interesting

question to understand the space-sample trade-offs. Moreover algorithms considered here are required to have constant $O(1)$ memory space and output a $\pm \epsilon$ estimate of $H(p)$. The focus of the talk will be on an algorithm given by Acharya et.al in the streaming model using the state-of-the-art interval partitioning method to achieve a sample space of $O(k(\log(1/\epsilon))^2 / \epsilon^3)$.

Time: 8 Mar, 2024, 12noon.

Location: COM3-02-70 .

Title: On the Perebor Conjecture for time bounded Kolmogorov Complexity.

Speaker: Noam Mazor.

Abstract: The Perebor (Russian for ``brute-force search") conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP =\= P conjecture (which they predate) and state that for ``meta-complexity" problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search.

In this work, we disprove the non-uniform version of the Perebor conjecture for the Time-Bounded Kolmogorov complexity problem. We demonstrate that for every polynomial t(·), there exists of a circuit of size 2^{4n/5+o(n)} that solves the t(·)-bounded Kolmogorov complexity problem on every instanceAlong the way (and of independent interest), in this work we extend the result of Fiat and Naor and demonstrate that any efficiently computable function can be inverted (with probability 1) by a circuit of size 2^{4n/5+o(n)}; as far as we know, this yields the first formal proof that a non-trivial circuit can invert any efficient function.

(Based on a joint work with Rafael Pass.)

Time: 23 Feb, 2024, 12noon.

Location: COM3-02-70.

Title: Exponential time hypothesis (ETH) and some results.

Speaker: Rajeev Raghunath .

Abstract: Over the years, efficient algorithms have been designed for various NP problems. These algorithms all run in time O(c^n) for constants c>1.

An interesting question is, what is the fastest algorithm that can be designed for 3-SAT (or other NP hard problems).

The ETH assumption states that there is a constant c s.t. 3-SAT cannot be solved in time c^n. We look at some of the implications of ETH via reductions of other problems to 3-SAT.

Time: 16 Feb, 2024, 12noon.

Location: COM3-02-70.

Title: Lower bounds for lattice sieving via approximate nearest neighbour search.

Speaker: Aditya Morolia.

Abstract: The shortest (non-zero) vector problem (SVP) on a lattice forms the basis for a majority of the proposed post quantum cryptosystems. Lattice sieving is currently the best known algorithm to solve SVP. Given the importance of the problem, it has received significant attention in the past two decades, leading to several (largely heuristic) improvements over the initial ASK Sieve (https://dl.acm.org/doi/10.1145/380752.380857). Most improvements rely on locality sensitive hashing to speed up the approximate nearest neighbour search (which forms the core subroutine of lattice sieving.) In this talk, we present lower bounds for lattice sieving (Laarhoven, Crypto 2021), and for the approximate nearest neighbour search problem (Rubinstein, STOC 2018). We highlight the possibility of a stronger lower bound on lattice sieving via Rubinstein'18.

Time: 02 Feb, 2024, 12 noon.

Location: COM3-02-70.

Title: MacORAMa: Optimal Oblivious RAM with Integrity.

Speaker: Surya Mathialagan.

Abstract: Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM `96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size �, well-known lower bounds show that a multiplicative overhead of Ω(log N) in the number of RAM queries is necessary assuming O(1) client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO `21) with O(log N) worst-case overhead and O(1) client storage. However, this optimal ORAM is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.

In this work, we construct the first maliciously secure ORAM with worst-case O(log N) overhead and O(1) client storage assuming one-way functions, which are also necessary. By the Ω(log N) lower bound, our construction is asymptotically optimal. To attain this overhead, we develop techniques to intricately interleave online and offline memory checking for malicious security. Furthermore, we complement our positive result by showing the impossibility of a generic overhead-preserving compiler from honest-but-curious to malicious security, barring a breakthrough in memory checking.

Joint work with Neekon Vafa.

Time: 26 Jan, 2024, 1pm.

Location: COM3-02-70.

Title: Bridging Bounded Leakage and Real-World Side-Channel Attacks via Hockey-Stick Divergences.

Speaker: Maciej Obremski.

Abstract: Leakage, Leakage, Leakage. There is a mismatch between theory (that wants to use bounded leakage) and practice (that likes statistical distance leakage). We fix it and bring the world peace with clever generalization of statistical distance leakage!

Time: 3 Nov, 2023, 1pm.

Location: COM3-02-70.

Title: Single-valued algorithms for Range Avoidance.

Speaker: Zeyong Li.

Abstract: This friday I will talk about the possiblility of a single-valued FSigma_2P algorithm for the Range Avoidance problem, for all n. As a corollary, one can obtain circuit lower bound for Sigma_2E. The result naturally extends to FS_2P and gives pseudodeterministic (with an NP oracle) algorithm for Avoid.

This is based on very recent (aka last week) unpublished work, building on the recent breaking through by Lijie Chen, Shuichi Hirahara, Hanlin Ren (https://eccc.weizmann.ac.il/report/2023/144/) which gives single-valued algorithms for Range Avoidance for infinitely many n.

Time: 20 Oct, 2023, 1pm.

Location: COM3-02-70.

Title: Lattice sieving via quantum random walks.

Speaker: Aditya Morolia.

Abstract: Building upon the contents of the talk in the previous week, we will first describe a framework for lattice sieving which can then be extended into novel classical and quantum algorithms for the shortest vector problems. We will mainly focus on the quantum algorithm using random walks on a Johnson graph, which achieves a SoTA asymptotic complexity.

Ref: https://dl.acm.org/doi/10.5555/2884435.2884437, https://eprint.iacr.org/2021/570.

Time: 6 Oct, 2023, 1pm.

Location: COM3-02-70.

Title: Lattice sieving for shortest vector problem via nearest neighbour search.

Speaker: Aditya Morolia.

Abstract: The asymptotic complexity of SVP and related problems is important to determine the NIST security standards for various lattice based encryption schemes. Today we will discuss how nearest neighbour search via random product codes and hashing can be used to create new algorithms for SVP. Ref:https://dl.acm.org/doi/10.5555/2884435.2884437, https://eprint.iacr.org/2021/570.

Time: 29 Sept, 2023, 1pm.

Location: COM3-02-70.

Title: SOS Lower Bounds for XOR Refutation.

Speaker: Sidhant Saraogi.

Abstract: The Sum of Squares (SOS) hierarchy is a hierarchy of increasingly powerful convex relations that captures a number of algorithmic techniques. In this talk, I will briefly introduce SOS. Then, we will try to prove a limitation of this computational model. We will prove that refuting random 3-XOR instances lies outside the SOS hierarchy.

Time: 15 Sept, 2023, 1pm.

Title: On composition of approximate degree.

Speaker: Chandrima Kayal.

Abstract: We can compose two Boolean functions to obtain a new function. But what happens to the complexity measures? Do they compose? This question plays a central role in understanding different complexity measures of Boolean functions. Following a long line of work two big open problems in this area now,

(1) Does approximate degree compose?

(2) Does randomized query complexity compose?

We will explore some of the techniques for 'Approximate degree composition' and see what is known there. Apart from the main open problem, we will also try to see what other weaker versions can be considered and can be a stepping stone towards the original problem.

Time: 8 Sept, 2023, 12pm.

Title: Differentially Private Linear Sketches: Efficient Implementations and Applications.

Speaker: Eldon Chung.

Abstract: Linear sketches have been widely adopted to process fast data streams, and they can be used to accurately answer frequency estimation, approximate top K items, and summarize data distributions. When data are sensitive, it is desirable to provide privacy guarantees for linear sketches to preserve private information while delivering useful results with theoretical bounds. We show that linear sketches can ensure privacy and maintain their unique properties with a small amount of noise added at initialization. From the differentially private linear sketches, we showcase that the state-of-the-art quantile sketch in the turnstile model can also be private and maintain high performance. Experiments further demonstrate that our proposed differentially private sketches are quantitatively and qualitatively similar to noise-free sketches with high utilization on synthetic and real datasets. The result is from the following paper: https://arxiv.org/abs/2205.09873.

Time: 31 Aug, 2023, 1pm.

Location: COM2-02-24 .

Title: Polynomial Data Structure Lower Bounds in the Group Model.

Speaker: Alexander Golovnev.

Abstract: In this talk, we will see the state of the art in the field of static data structures. Proving super-logarithmic data structure lower bounds in the static model has been a fundamental challenge in computational geometry and complexity theory since the early 80's. First, we will show barriers for proving such lower bounds in the linear model. As a second result, we will prove a polynomial lower bound in the group model for an explicit range counting problem of n^3 convex polygons in R^2. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing---in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime. As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

Time: 3 Aug, 2023, 2pm.

Location: Seminar Room 12, COM3 01-21.

Title: Lattice problems beyond polynomial time (but mostly not beyond polynomial time).

Speaker: Noah Stephens-Davidowitz.

Abstract: We will revisit five different decades-old results that together largely laid the foundations of lattice-based cryptography (and which are conveniently numbered below).

The first is (1) Ajtai's celebrated worst-case to average-case reduction from 1996, showing how to build secure secret-key cryptography under the assumption that a certain *worst-case* *approximate* lattice problem is hard. Around the same time, (2) Ajtai proved that the exact version of this problem was NP-hard (resolving a decades-old open question), and a series of NP-hardness of approximation results with progressively larger approximation factors. Together, these results led to speculation and hope that lattice techniques might lead us to one of the holy grails of cryptography: proof that cryptography exists under the minimal assumption that BPP =/= NP---all one had to do was show NP-hardness for an approximation factor large enough to be compatible with Ajtai's worst-case to average-case reduction!

This hope was basically quashed twice by our next two celebrated results: (3) Goldreich and Goldwasser's simple and elegant 1998 proof system for approximate lattice problems, followed by (4) a different beautiful proof system by Aharonov and Regev in 2005. Both of these results showed that NP-hardness of these problems would collapse the polynomial hierarchy (to different levels, with different approximation factors). Though these results largely ruled out a very exciting line of research, they also introduced powerful and beautiful tools that have found innumerable applications in lattice cryptography and beyond.

The last (also celebrated!) result is (5) Regev's worst-case to average-case reduction from 2005, showing how to build secure *public-key* cryptography, again under the assumption that a certain worst-case approximate lattice problem is hard. This result led to a revolution in cryptography, with applications ranging from fully homomorphic encryption to the post-quantum public-key encryption schemes that will be running the internet shortly.

As an excuse to talk about these results, our ostensible purpose is to point out that all of them are fundamentally focused on the gap between polynomial time and superpolynomial time: relying on polynomial-time reductions and proof systems. This distinction between polynomial and superpolynomial time is extremely convenient and has proven to be an incredibly fruitful way of thinking about computation, but it is also rather arbitrary. In fact, in the context of lattice-based cryptography, it seems that higher running times are more relevant. Indeed, we show that all 5 of the above results are even more interesting if we relax the restriction that reductions and proof systems should run in polynomial time (and we will mention a bonus 6th result that only makes sense in a superpolynomial setting).

Based loosely on https://arxiv.org/abs/2211.11693, which is joint work with Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, and Vinod Vaikuntanathan.

Time: 4 Aug, 2023, 2pm.

Location: Seminar Room 12, COM3 01-21.

Title: The Planted k-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography.

Speaker: Prashant Vasudevan.

Abstract: I will give an overview of the results from https://arxiv.org/abs/2304.01787, and then focus mostly on the hardness amplification. If there is time, we will see details of the other results as well.

Time: 23 June, 2023, 1pm.

Title: Hardness Self-Amplification: Simplified, Optimized, and Unified.

Speaker: Divesh Aggarwal.

Abstract:

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. I will present a recent result that shows a general technique to obtain strong average case hardness from weak-average case hardness. This is a result by Shuichi Hirahara and Nobutaka Shimizu that appeared at STOC 2023.

Their approach uses a one-query upward self-reduction, that is, a reduction that maps a small instance to a large instance. They demonstrate that this reduction yields hardness self-amplification if the bipartite graph, whose left and right vertices correspond to small and large instances, respectively, has an expansion property.

As a motivating example from their paper, I will show how this technique can be used to obtain a much simpler (compared to prior work) worst-case to average-case reduction for matrix multiplication.

Time: 19 May, 2023, 1pm.

Title: On Counting t-Cliques Mod 2.

Speaker: Pranjal Dutta.

Abstract: For a fixed integer t, we consider the problem of counting the number of t-cliques mod 2 in a given graph. We establish that this problem is at least as hard as determining whether a graph contains a t-clique. Moreover, we provide a reduction from worst-case to average-case for this, which is very algebraic in nature. The reduction can be executed in linear time when the graphs are represented by their adjacency matrices.

This is based on Oded Goldreich's work: https://eccc.weizmann.ac.il/report/2020/104/

Time: 12 May, 2023, 1pm.

Title: Learning High-dimensional Gaussians from Censored Data.

Speaker: Arnab Bhattacharyya.

Abstract:

We provide efficient algorithms for the problem of distribution learning from high-dimensional Gaussian data when some of the variable values are censored in the observed samples. The censorship model is that variables are missing not at random (MNAR), that is, the subset of variables that are missing may be systematically related to the unobserved data. We assume the missingness mechanism to be known. Concretely, we study two settings:

(i) [Self-censoring] An observation x is generated by first sampling x = (x1, . . . , xd) from a d dimensional Gaussian with unknown mean and variance, and xi is seen if xi is in Si while xi is missing otherwise. Here, S1,...,Sd are fixed subsets of the reals. We design an algorithm that learns the distribution up to TV distance ε, using poly (d, 1/ε) samples, assuming only that each pair of coordinates is observed with sufficiently high probability.

(ii) [Linear thresholding] An observation is generated by first sampling x = (x1, . . . , xd) from a d-

dimensional Gaussian N (μ∗, Σ) with unknown μ∗ and known Σ, and for each i, we observe xi iff <vi, x> ≤ bi, where v1, . . . , vd ∈ R^d and b1, . . . , bd ∈ R are known. We design an efficient mean estimation algorithm, assuming that the observed missingness pattern is not very rare conditioned on the values of the observed coordinates and that any small subset of coordinates is observed with sufficiently high probability.

Joint work with Costis Daskalakis, Themis Gouleakis, and Yuhao Wang.

Time: 21 April, 2023, 1pm.

Title: On the hardness of Multivariate polynomials.

Speaker: Pranjal Dutta.

Abstract: Proving lower bounds for explicit functions, and obtaining efficient deterministic algorithms for problems known to have efficient randomised algorithms, are two of the most fundamental themes of study in theoretical computer science. In today's talk, we will cover some basic hardness vs randomness results, and lower bound results known in the algebraic complexity theory. In particular we plan to cover proof ideas/sketches of

(1) Why a random multivariate polynomial is 'hard'. [Folklore]

(2) A classic (algebraic) hardness vs randomness result due to Kabanets-Impaggliazzo [STOC'03],

(3) A linear algebraic proof of exponential hardness in the Waring model. It's based on an unpublished result due to Balaji-Limaye-Sandeep-Srinivasan'18, which I very recently got to personally know from them.

(4) If time permits, we'll also cover Shachar Lovett's combinatorial construction to compute any arbitrary multivariate polynomial using near-optimal multiplications. [ToC'11]

This talk will be self-contained.

Time: 21 April, 2023, 1pm.

Title: Invertible Bloom Lookup Tables (IBLT) and some hashing tricks.

Speaker: Maciej Obremski.

Abstract: IBLTs are data structures that allow for adding and deleting unlimited amount of elements, if at the end you are left with few elements (i.e. you at some point deleted most of what you added) then you can retrieve all remaining elements.

It's immensely useful with set reconsolidation problems etc.

Also I'll talk about some hashing tricks.

This will be relatively short talk, I'll try to convey the gist of the ideas without going too deep into technical details.

Based on joint work with Nils Fleischhacker, Kasper Green Larsen and Mark Simkin.

Time: 14 April, 2023.

Title: Differential privacy vs key agreement.

Speaker: Eldon Chung.

Abstract: In this talk we will study the relationship between statistical differential privacy, computational differential privacy, and black box protocols for key agreement and public key encryption.

Time: 17 Mar, 2023, 1pm.

Title: MASETH is False.

Speaker: Zeyong Li.

Abstract: Two weeks ago we saw how to (conditionally) refute NSETH which asserts that coSAT cannot be solved in NTIME[2^{(1-eps)n}]. This week we will see how to (unconditionally) refute MASETH (which can be seen as NSETH with randomized verifier). More specifically, we will see that the class #P is in MA(2^{n/2}). This is a result by Ryan Williams in 2016 (https://arxiv.org/abs/1601.04743).

Time: 3 Mar, 2023.

Title: SETH-reduction provides: (arithmetic circuit) Lower Bound or (series-parallel Boolean circuit) Lower Bound.

Speaker: Zeyong Li.

Time: 17 Feb, 2023.

Title: (Discrete) Low Degree Testing over the Reals.

Speaker: Vipul Arora.

Abstract: We study the problem of testing whether a function $f: \reals^n \to \reals$ is a polynomial of degree at most $d$ in the \emph{distribution-free} testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\reals^n$ from which we can draw samples. In contrast to previous work, we do not assume that $\mathcal{D}$ has finite support.

We design a tester that given query access to $f$, and sample access to $\mathcal{D}$, makes $\poly(d/\eps)$ many queries to $f$, accepts with probability $1$ if $f$ is a polynomial of degree $d$, and rejects with probability at least $\mathfrac{2}{3}$ if every degree-$d$ polynomial $P$ disagrees with $f$ on a set of mass at least $\eps$ with respect to $\mathcal{D}$.

Our result also holds under mild assumptions when we receive only a polynomial number of bits of precision for each query to $f$, or when $f$ can only be queried on rational points representable using a logarithmic number of bits.

I will present the analysis of the discrete tester (for second type of assumption), when $f$ can only be queried on rational points (forming a lattice), representable by a finite number of bits.

Time: 10 Feb, 2023.

Title: Non-malleable codes in the split-state model.

Speaker: Divesh Aggarwal.

Abstract: I will survey some of the constructions of non-malleable codes in the split-state model.

Time: 3 Feb, 2023.

Title: Separating Computational Differential Privacy and Statistical (Information-Theoretic) Differential Privacy (in the Central Setting)

Speaker: Haoxing Lin.

Abstract: In this talk, I will introduce a (the first) computational task that is achievable under the computational notion of DP but not the conventional (statistical/information-theory) notion of DP. The achievability refers to the existence of a DP mechanism that enjoys desirable privacy guarantees, i.e., a $(\epsilon,\delta)$-DP mechanism with $\epsilon = o(1), \delta = neg(n), while maintaining the usefulness of the function to compute, i.e., $1 - o(1)$ usefulness (utility). We will construct a computational task, called $d$-distance problem, which is to output a circuit $C$ given a database $D = \{0,1\}^n$ as the input, and $C(D')$ outputs $1$ if $D' = D$ or $0$ if $D'$ is more than $d$-far from $D$ (in terms of hamming distance). It can be proved that this task is not achievable under the notion of SDP. So if we can show that there exists a mechanism for the $d$-distance problem that is private against efficient adversaries, this task can then separate CDP and SDP. To show this, we first show that by circuit obfuscation the obfuscated circuit is private against a certain class of decision tree adversaries, and then we use cryptographic constructions to "lift" this into privacy against computational adversaries.

Time: 27 Jan, 2023.

Title: On the border complexity of binomials (& more)

Speaker: Pranjal Dutta

Abstract: The border complexity of polynomials plays an integral role in GCT (Geometric complexity theory) to approach P != NP. It tries to formalize the notion of ‘approximating a polynomial’ via limits (Burgisser FOCS’01). This raises whether border VP ?= VP; as the approximation involves exponential precision that may not be efficiently simulable. In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials, which has a small border-Σ^[2]ΠΣ circuit (or binomial complexity). In this talk, we will discuss its connection to Waring rank and some new bounds on the Waring rank and border Waring rank. We will further discuss that the border of bounded top-fanin depth-3 circuits (border-Σ^[k]ΠΣ for constant k) is relatively easy– it can be computed by a polynomial-size algebraic branching program (ABP). Then, we will discuss several exponential separations between related polynomials contained in the border.

I will mostly discuss the basics without getting into technical details. Anybody interested in basic algebra/theoretical computer science is welcome!

Time: 13 Jan, 2023.

Title: Exact tester for low degree polynomials.

Speaker: Vipul Arora.

I will present the analysis of the exact tester, that I pushed under the rug in the talk on Monday.

Time: 25 Nov, 2022.

Title: coMA protocol for O(1/eps)-GapCVP given 2^{eps n} time.

Speaker: Zeyong Li.

Abstract: We will see a simple and arguably elegant coMA protocol that dicides O(1)-GapCVP when given 2^{eps n} verification time and message size. This is a recent work that can be seen as a combination of the coAM protocol from [GG00] and the coNP protocol from [AR05].

Time: 18 Nov, 2022.

Title: Reductions involving lattice-based problems SIVP, CVP and a learning problem defined in paper LWE.

Speaker Ashutosh Shukla.

Abstract: A quantum reduction is shown from SIVP to LWE problem. This reduction is in two parts,

Part 1 - shows a classical reduction from CVP to LWE (well, not quite exactly by itself)
Part 2 - shows a quantum reduction from SIVP to CVP

Also, Discrete Gaussian Sampling problem is used as a tool to show these reductions. We'll go through part 1 and outline part 2.

These are from Regev05: https://cims.nyu.edu/~regev/papers/qcrypto.pdf.

Time: 11 Nov, 2022.

Title: The Flajolet-Martin Sketch Itself Preserves Differential Privacy.

Speaker: Haoxing Lin.

Abstract: Going through selected results from https://proceedings.neurips.cc/paper/2020/hash/e3019767b1b23f82883c9850356b71d6-Abstract.html.

Time: 4 Nov, 2022.

Title: (Part 1) Do small Universal Hashing Families exist?

(Part 2) Subexponential Algorithms for Unique Games and Related problems.

Speaker: (Part 1) Maciej Obremski.

(Part 2) Philips George John.

Abstract: (Part 1) No, but almost…

(Part 2) Going through selected stories from https://www.boazbarak.org/Papers/ssesubexp.pdf.

Time: 28 Oct, 2022.

Title: How many distinct algorithms are there to count distinct elements in a stream? Might be around 3, but I'm not 100% sure.

Speaker: Eldon Chung.

Abstract: The talk will walkthrough the algorithms from http://cs.haifa.ac.il/~ilan/randomized_algorithms/bar-yosef_jayram.pdf.

Time: 21 Oct, 2022.

Title: PPP-Completeness and Extremal Combinatorics.

Speaker: Nikolaj Ignatieff Schwartzbach.

Abstract: The speaker will give a brief introduction to total search problems and go through selected results from the following paper: https://arxiv.org/abs/2209.04827.

Time: 14 Oct, 2022.

Title: Selected Results in Additive Combinatorics.

Speaker: Divesh Aggarwal.

Abstract: The talk will present results from http://www1.cs.columbia.edu/~viola/papers/add.pdf.

Time: 7 Oct, 2022.

Title: Hardness of two-party differential private functions.

Speaker: Haoxing Lin.

Abstract: In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, Mironov, Pitassi, Reingold, Talwar, and Vadhan [FOCS '10] proved that this gap is inherent, showing upper bounds on the accuracy of (any) distributed solution for these functions. These limitations can be bypassed when settling for computational differential privacy, where the data is differentially private only in the eyes of a computationally bounded observer, using public-key cryptography primitives. This result is from https://arxiv.org/abs/2108.07664.

Time: 16 Sept 2022.

Title: Dynamic algorithms in amortized O(log*n) rounds for distributed tasks.

Speaker: Zeyong Li.

Abstract: The talk will walkthrough the algorithm from http://people.csail.mit.edu/parter/papers/distAmort_cameraV5.pdf, providing an amortized analysis for the dynamic edge orientation problem in the LOCAL model in O(log*n) rounds.

Time: 2 Sept, 2022.