Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Home

Person

Weiqiang Yuan

About
Privacy
Disclaimer

Graph Chatbot

Related publications (4)

Page 1 of 1

One-Way Functions vs. TFNP: Simpler and Improved

Mika Tapani Göös, Gilbert Théodore Maystre, Weiqiang Yuan

Simon (1998) proved that it is impossible to construct collision-resistant hash functions from one-way functions using a black-box reduction. It is conjectured more generally that one-way functions do not imply, via a black-box reduction, the hardness of a ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

Lower Bounds for Unambiguous Automata via Communication Complexity

Mika Tapani Göös, Weiqiang Yuan

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ̅L ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Generalised Linial-Nisan Conjecture Is False for DNFs

Mika Tapani Göös, Gilbert Théodore Maystre, Artur Riazanov, Ziyi Guan, Weiqiang Yuan

Aaronson (STOC 2010) conjectured that almost k-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexam ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2025

Direct Sums for Parity Decision Trees

Mika Tapani Göös, Gilbert Théodore Maystre, Weiqiang Yuan

Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(k) times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2025