Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/147851
Title: INFORMATION THEORETIC AND ALGEBRAIC TECHNIQUES IN THEORETICAL COMPUTER SCIENCE
Authors: PRIYANKA MUKHOPADHYAY
Keywords: quantum communication,query complexity,algebraic complexity,lattice
Issue Date: 25-May-2018
Citation: PRIYANKA MUKHOPADHYAY (2018-05-25). INFORMATION THEORETIC AND ALGEBRAIC TECHNIQUES IN THEORETICAL COMPUTER SCIENCE. ScholarBank@NUS Repository.
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.
URI: http://scholarbank.nus.edu.sg/handle/10635/147851
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
MukhopadhyayP.pdf1.08 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

24
checked on Oct 18, 2018

Download(s)

12
checked on Oct 18, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.