2 citations · 3 across the 4 of their papers we have counts for
5 papers
Learning Clifford-structured quantum unitaries and Hamiltonians
Arkopal Dutt, Dale Jacobs, John Jeang +2
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attent…
Complexity Aspects of the Extension of Wagner's Hierarchy to -Partitions
Vladimir Podolskii, Victor Selivanov
It is known that the Wadge reducibility of regular -languages is efficiently decidable (Krishnan et al., 1995), (Wilke, Yoo, 1995). In this paper we study analogous problem for…
Nearest Neighbor Complexity and Boolean Circuits
Mason DiCicco, Vladimir Podolskii, Daniel Reichman
A nearest neighbor representation of a Boolean function is a set of vectors (anchors) labeled by or such that if and only if the closest anchor to $\ve…
Towards Simpler Sorting Networks and Monotone Circuits for Majority
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii
In this paper, we study the problem of computing the majority function by low-depth monotone circuits and a related problem of constructing low-depth sorting networks. We consider…
Logical Languages Accepted by Transformer Encoders with Hard Attention
Pablo Barcelo, Alexander Kozachinskiy, Anthony Widjaja Lin +1
We contribute to the study of formal languages that can be recognized by transformer encoders. We focus on two self-attention mechanisms: (1) UHAT (Unique Hard Attention Transforme…