Jun-Ting Hsieh

activity

20232026

collaborators

Showing 2024Show all

6 papers · 1 filter

cs.CC2024

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari +1

We prove that for every odd $q \geq 3$ , any $q$ -query binary, possibly non-linear locally decodable code ( $q$ -LDC) $E : {\pm 1}^{k} \to {\pm 1}^{n}$ must satisfy $k \leq \tilde{…

math.CO2024

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier

Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty +2

We construct the first explicit two-sided vertex expanders that bypass the spectral barrier. Previously, the strongest known explicit vertex expanders were given by $d$ -regular Ram…

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.DS2024

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $n$ Dimension Threshold

Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra

We consider the task of certifying that a random $d$ -dimensional subspace $X$ in $R^{n}$ is well-spread - every vector $x \in X$ satisfies $c\sqrt{n} \|x\|_2 \leq \|x\|_1 \l…

cs.DS2024

Rounding Large Independent Sets on Expanders

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

We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has…

cs.CC2024

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs

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

Given a $k$ -uniform hypergraph $H$ on $n$ vertices, an even cover in $H$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalizat…