Research
I'd rather know a square guy than own a square mile.
My research interests mainly lie in graph theory, optimization theory, discrete geometry, and combinatorics. Besides, I am also enjoying thinking about fine-grained algorithms, but at a less advanced level (usually contributed to programming contests). Network Verification: SDP VerifierNetwork verification always suffer from the trade-off between completeness and soundness, expressity and tractability. Popular methods include MILP, Zonotope Approximation and DeepPoly Approximation. In our work, we formulate this work as a semi-definite programming scheme and resolve it in its dual space, which is referred as linear matrix inequality. Neural Architecture Search: ROMEThe popular differentiable architecture search namely DARTS is largely hindered by its substantial memory cost since the entire supernet resides in the memory. This is where the single-path DARTS comes in, which only chooses a single-path submodel at each step. While being memory-friendly, it also comes with low computational costs. Nonetheless, we discover a critical issue of single-path DARTS that has not been primarily noticed. Namely, it also suffers from severe performance collapse since too many parameter-free operations like skip connections are derived, just like DARTS does. According to that, we propose a new algorithm called RObustifying Memory-Efficient NAS (ROME) to give a cure. Polyhedral Combinatorics: USO PolytopeA unique sink orientation is an orientation of the hypercube such that for each subcube, there exists a unique sink. Up to now, many efforts have been committed to understand the structure of the USO itself and propose fine-grained algorithm to efficiently find the unique sink of the hypercube. Nonetheless, the relation between different USOs has not been discussed a lot and only a little knowledge is already known about the universal set of all possible USOs. Therefore, we try to aggregate all possible USOs together to formulate the USO polytope, of which each vertex is a single USO. In our paper, we propose several aspects to analyze the structure of the USO polytope, both locally and globally, which will better our understanding of the relationship between different USOs. Computational Geometry: Hidden Point SetThe hidden point problem, is to arrange as many as possible points in a given polygon, such that any two of them are invisible to each other. When these points must be positioned on the vertices of the polygon, it is called the hidden vertex problem. Our results are highlighted in a 2/3-approximation algorithm of the maximum hidden vertex set in a pseudotriangle, and an exact algorithm for maximum hidden point set in a terrain or fan-shaped polygon. Ongoing Projects |