Jun-Ting Hsieh

collaborators

6 papers

quant-ph2024

Predicting quantum channels over general product distributions

Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh +3

We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an $n$ -qubit channel $E$ and an observable $O$ , we aim to learn the…

cs.DS2023

New SDP Roundings and Certifiable Approximation for Cubic Optimization

Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti +1

We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the $n$ -dimensional hypercube. In both cases, the resulti…

cs.CC2023

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari +1

We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst-case an…

math.PR2023

Ellipsoid Fitting Up to a Constant

Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin +1

In [Sau11,SPW13], Saunderson, Parrilo and Willsky asked the following elegant geometric question: what is the largest $m = m (d)$ such that there is an ellipsoid in $R^{d}$ th…

cs.DS2022

Polynomial-Time Power-Sum Decomposition of Polynomials

Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari +1

We give efficient algorithms for finding power-sum decomposition of an input polynomial $P (x) = \sum_{i \leq m} p_{i} (x)^{d}$ with component $p_{i}$ s. The case of linear $p_{i}$ s is equivale…

math.CO2022

A simple and sharper proof of the hypergraph Moore bound

Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty

The hypergraph Moore bound is an elegant statement that characterizes the extremal trade-off between the girth - the number of hyperedges in the smallest cycle or even cover (a sub…