research
∙
05/04/2022
Sketching Approximability of (Weak) Monarchy Predicates
We analyze the sketching approximability of constraint satisfaction prob...
share
research
∙
12/03/2021
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Demonstrating quantum advantage requires experimental implementation of ...
research
∙
08/13/2021
Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond
Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019], we stu...
research
∙
08/06/2021
Quantum Meets the Minimum Circuit Size Problem
In this work, we initiate the study of the Minimum Circuit Size Problem ...
research
∙
06/24/2021
Linear Space Streaming Lower Bounds for Approximating CSPs
We consider the approximability of constraint satisfaction problems in t...
research
∙
05/03/2021
Approximability of all finite CSPs in the dynamic streaming setting
A constraint satisfaction problem (CSP), Max-CSP( F), is specified by a ...
research
∙
02/24/2021
Approximability of all Boolean CSPs in the dynamic streaming setting
A Boolean constraint satisfaction problem (CSP), Max-CSP(f), is a maximi...
research
∙
06/11/2020
A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
We present a general framework for analyzing high-probability bounds for...
research
∙
05/05/2020
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
The linear cross-entropy benchmark (Linear XEB) has been used as a test ...
research
∙
04/24/2020
Optimal Streaming Approximations for all Boolean Max-2CSPs
We prove tight upper and lower bounds on approximation ratios of all Boo...
research
∙
11/04/2019
ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA
Oja's rule [Oja, Journal of mathematical biology 1982] is a well-known b...
research
∙
03/06/2019
Closure of VP under taking factors: a short and simple proof
In this note, we give a short, simple and almost completely self contain...
research
∙
07/17/2018
Tracking the ℓ_2 Norm with Constant Update Time
The ℓ_2 tracking problem is the task of obtaining a streaming algorithm ...
research
∙
07/09/2018
Personalized Difficulty Adjustment for Countering the Double-Spending Attack in Proof-of-Work Consensus Protocols
Bitcoin is the first secure decentralized electronic currency system. Ho...
research
∙
05/07/2018
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
We give a quasipolynomial time algorithm for the graph matching problem ...
research
∙
03/28/2018
On the Algorithmic Power of Spiking Neural Networks
Spiking Neural Networks (SNN) are mathematical models in neuroscience to...
research
∙
03/15/2018