INFORMATION THEORETIC AND ALGEBRAIC TECHNIQUES IN THEORETICAL COMPUTER SCIENCE

Abstract

This thesis can be divided into four independent parts.

1.We give a one-round entanglement assisted quantum compression protocol that allows Alice and Bob (players) to sample from a common distribution known only to Alice. We also provide a quantum analogue of the widely used classical correlated-sampling protocol.

2.We prove some lower bounds on the randomized query complexity of composed relations.

3.We show that the deterministic interpolation of sparse polynomials with integer coefficients in the Schubert basis can be done in polynomial time, given an oracle computing Schubert polynomials. Also, computing both skew Schubert and Schubert polynomials on non-negative integral points is in #P and VNP (algebraic complexity).

4.We give a new sieving procedure with a linear sieve, that significantly improves the running time of the algorithm for Shortest Vector Problem and Closest Vector Problem on lattices in infinity norm.