research
∙
09/23/2022
Quantum Locally Testable Code with Exotic Parameters
In this paper, we present a few simple constructions of quantum locally ...
share
research
∙
05/09/2022
Repeated Averages on Graphs
Sourav Chatterjee, Persi Diaconis, Allan Sly and Lingfu Zhang, prompted ...
research
∙
01/27/2022
Budgeted Steiner Networks: Three Terminals with Equal Path Weights
Given a set of terminals in 2D/3D, the network with the shortest total l...
research
∙
02/12/2020
On Rearrangement of Items Stored in Stacks
There are n > 2 stacks, each filled with d items (its full capacity), an...
research
∙
02/13/2019
Explicit lower bounds on strong simulation of quantum circuits in terms of T-gate count
We investigate Clifford+T quantum circuits with a small number of T-gate...
research
∙
04/27/2018
Explicit lower bounds on strong quantum simulation
We consider the problem of strong (amplitude-wise) simulation of n-qubit...
research
∙
05/06/2016
A Graph-based Model for GPU Caching Problems
Modeling data sharing in GPU programs is a challenging task because of t...
research
∙
06/22/2015
An O(n^0.4732) upper bound on the complexity of the GKS communication game
We give an 5· n^_305 upper bund on the complexity of the communication g...
research
∙
06/01/2015
Impossibility Theorems and the Universal Algebraic Toolkit
We elucidate a close connection between the Theory of Judgment Aggregati...
research
∙
12/27/2013
The Garden Hose Complexity for the Equality Function
The garden hose complexity is a new communication complexity introduced ...
research
∙
02/05/2007