Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Li-Yang Tan:

TR21-012 | 9th February 2021
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

On the Power and Limitations of Branch and Cut

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

TR20-027 | 26th February 2020
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

The Power of Many Samples in Query Complexity

The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we ... more >>>

ISSN 1433-8092 | Imprint