9 citations · 25 across the 6 of their papers we have counts for
7 papers
Arithmetics within the Linear Time Hierarchy
Chris Pollett
We identify fragments of the arithmetic that enjoy nice closure properties and have exact characterization of their definable multifunctions. To do this, in the language of $…
MRI-GAN: A Generalized Approach to Detect DeepFakes using Perceptual Image Assessment
Pratikkumar Prajapati, Chris Pollett
DeepFakes are synthetic videos generated by swapping a face of an original image with the face of somebody else. In this paper, we describe our work to develop general, deep learni…
Alternating Hierarchies for Time-Space Tradeoffs
Chris Pollett, Eric Miles
Nepomnjascii's Theorem states that for all 0 <= ε< 1 and k > 0 the class of languages recognized in nondeterministic time n^k and space n^ε, NTISP[n^k, n^ε], is contained in the li…
The weak pigeonhole principle for function classes in S^1_2
Norman Danner, Chris Pollett
It is well known that S^1_2 cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability o…
Quantum and Stochastic Branching Programs of Bounded Width
Farid Ablayev, Cristopher Moore, Chris Pollett
In this paper we show that one qubit polynomial time computations are at least as powerful as $\NC^1$ circuits. More precisely, we define syntactic models for quantum and stochasti…
Counting, Fanout, and the Complexity of Quantum ACC
Frederic Green, Steven Homer, Cristopher Moore +1
We propose definitions of $\QAC^0$, the quantum analog of the classical class $\AC^0$ of constant-depth circuits with AND and OR gates of arbitrary fan-in, and $\QACC[q]$, the anal…