15 citations · 21 across the 14 of their papers we have counts for
22 papers
Quantum Fire with Delegated Cloning
Rohit Chatterjee, Ananta Mukherjee, Vir Pathak +1
Quantum fire is a recently introduced cryptographic primitive consisting of efficiently preparable quantum states, called \emph{flames}, that admit efficient cloning but resist eff…
Learning and interpreting policies for simultaneous entanglement requests in quantum networks
Leon Rode, Sumeet Khatri, Supartha Podder
Future quantum networks will make use of entanglement to perform numerous tasks, such as sending quantum information over long distances, distributed quantum computing, and quantum…
A General Composition Theorem for Approximate Degree
Samruddhi Pednekar, Supartha Podder
A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upp…
Hardness of Pathfinding in a Welded Tree
David Miloschewsky, Supartha Podder
Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open quest…
Promises should be taken seriously: On relativization with promise problems
David Miloschewsky, Supartha Podder, Dorian Rudolph
Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of…
On the Approximate Non-Deterministic Degree of Total Boolean Functions
Samruddhi Pednekar, Supartha Podder
The approximate non-deterministic degree of a Boolean function , denoted (written for brevity), is the minimum degree of a real polynomial…
En Route to a Standard QMA1 vs. QCMA Oracle Separation
David Miloschewsky, Supartha Podder, Dorian Rudolph
We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in but not in …
A Framework for Ruling Out Quantum Speedups
Thomas Huffstutler, Upendra Kapshikar, David Miloschewsky +1
We study when partial Boolean functions can (and cannot) exhibit superpolynomial quantum query speedups, and develop a general framework for ruling out such speedups via two comple…
Modifications of Quantum Computation and Adaptive Queries to PP
David Miloschewsky, Supartha Podder
In 2004, Aaronson introduced the complexity class ( with postselection) and showed that it is equal to . Following their line of work,…
New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
David Miloschewsky, Supartha Podder
Aaronson, Bouland, Fitzsimons and Lee introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsi…
The Role of piracy in quantum proofs
Anne Broadbent, Alex B. Grilo, Supartha Podder +1
A well-known feature of quantum information is that it cannot, in general, be cloned. Recently, a number of quantum-enabled information-processing tasks have demonstrated various f…
Are uncloneable proof and advice states strictly necessary?
Rohit Chatterjee, Srijita Kundu, Supartha Podder
Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes Q…
On the Fine-Grained Query Complexity of Symmetric Functions
Supartha Podder, Penghui Yao, Zekun Ye
This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to . Our con…
Decision Tree Complexity versus Block Sensitivity and Degree
Rahul Chugh, Supartha Podder, Swagato Sanyal
Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. It is known t…
Secure Software Leasing Without Assumptions
Anne Broadbent, Stacey Jeffery, Sébastien Lord +2
Quantum cryptography is known for enabling functionalities that are unattainable using classical information alone. Recently, Secure Software Leasing (SSL) has emerged as one of th…
Symmetries, graph properties, and quantum speedups
Shalev Ben-David, Andrew M. Childs, András Gilyén +3
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: h…
Communication memento: Memoryless communication complexity
Srinivasan Arunachalam, Supartha Podder
We study the communication complexity of computing functions in the memoryless communication model. Here, Alice is given $x\in \{0…
How symmetric is too symmetric for large quantum speedups?
Shalev Ben-David, Supartha Podder
Suppose a Boolean function is symmetric under a group action acting on the bits of the input. For which does this mean does not have an exponential quantum spee…
Graph properties in node-query setting: effect of breaking symmetry
Nikhil Balaji, Samir Datta, Raghav Kulkarni +1
The query complexity of graph properties is well-studied when queries are on edges. We investigate the same when queries are on nodes. In this setting a graph on v…
Quantum Query Complexity of Subgraph Isomorphism and Homomorphism
Raghav Kulkarni, Supartha Podder
Let be a fixed graph on vertices. Let iff the input graph on vertices contains as a (not necessarily induced) subgraph. Let denote the cardin…
New Bounds for the Garden-Hose Model
Hartmut Klauck, Supartha Podder
We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unkno…
Two Results about Quantum Messages
Hartmut Klauck, Supartha Podder
We show two results about the relationship between quantum and classical messages. Our first contribution is to show how to replace a quantum message in a one-way communication pro…