Jun-Ting Hsieh

activity

20172023

most citedLearning to Decompose and Disentangle Representations for Video Prediction

109 citations · 175 across the 9 of their papers we have counts for

collaborators

Showing 2022Show all

3 papers · 1 filter

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…

cs.DS2022

Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm

Jun-Ting Hsieh, Pravesh K. Kothari

In this note, we describe a $α_{G W} + Ω ~ (1/ d^{2})$ -factor approximation algorithm for Max-Cut on weighted graphs of degree $\leq d$ . Here, $α_{G W} \approx 0.878$ is the worst-cas…