1 citations · 1 across the 4 of their papers we have counts for
6 papers
Counting Distinct Elements Under Person-Level Differential Privacy
Alexander Knop, Thomas Steinke
We study the problem of counting the number of distinct elements in a dataset subject to the constraint of differential privacy. We consider the challenging setting of person-level…
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies
Kamil Khadiev, Aliya Khadieva, Alexander Knop
In this paper, we study quantum Ordered Binary Decision Diagrams() model; it is a restricted version of read-once quantum branching programs, with respect to "width" complexi…
Adversarial Manifold Estimation
Eddie Aamari, Alexander Knop
This paper studies the statistical query (SQ) complexity of estimating -dimensional submanifolds in . We propose a purely geometric algorithm called Manifold Propa…
Log-rank and lifting for AND-functions
Alexander Knop, Shachar Lovett, Sam McGuire +1
Let be a boolean function, and let denote the AND-function of , where denotes bit-wise AND. We study the…
Proof complexity of systems of (non-deterministic) decision trees and branching programs
Sam Buss, Anupam Das, Alexander Knop
This paper studies propositional proof systems in which lines are sequents of decision trees or branching programs - deterministic and nondeterministic. The systems LDT and LNDT ar…
Strategies for Stable Merge Sorting
Sam Buss, Alexander Knop
We introduce new stable natural merge sort algorithms, called -merge sort and -merge sort. We prove upper and lower bounds for several merge sort algorithms, including Timsor…