Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SIYAO GUO:
All reports by Author Siyao Guo:

TR24-203 | 9th December 2024
Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, Weiqiang Yuan

Direct Sums for Parity Decision Trees

Revisions: 1

Direct sum theorems state that the cost of solving k instances of a problem is at least \Omega(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 whenever (1) the ... more >>>


TR20-090 | 10th June 2020
Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian

Tight Quantum Time-Space Tradeoffs for Function Inversion

Revisions: 1

In function inversion, we are given a function f: [N] \mapsto [N], and want to prepare some advice of size S, such that we can efficiently invert any image in time T. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower ... more >>>


TR19-173 | 28th November 2019
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

Extractor Lower Bounds, Revisited

Revisions: 1

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a ``change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... more >>>


TR17-136 | 10th September 2017
Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Complete Classi fication of Generalized Santha-Vazirani Sources

Let \mathcal{F} be a finite alphabet and \mathcal{D} be a finite set of distributions over \mathcal{F}. A Generalized Santha-Vazirani (GSV) source of type (\mathcal{F}, \mathcal{D}), introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence (F_1, \dots, F_n) in \mathcal{F}^n, where F_i is a sample from ... more >>>


TR16-136 | 31st August 2016
Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer

Testing k-Monotonicity

Revisions: 1

A Boolean k-monotone function defined over a finite poset domain {\cal D} alternates between the values 0 and 1 at most k times on any ascending chain in {\cal D}. Therefore, k-monotone functions are natural generalizations of the classical monotone functions, which are the 1-monotone functions.

Motivated by the ... more >>>


TR16-131 | 21st August 2016
Andrej Bogdanov, Siyao Guo, Ilan Komargodski

Threshold Secret Sharing Requires a Linear Size Alphabet

We prove that for every n and 1 < t < n any t-out-of-n threshold secret sharing scheme for one-bit secrets requires share size \log(t + 1). Our bound is tight when t = n - 1 and n is a prime power. In 1990 Kilian and Nisan proved ... more >>>




ISSN 1433-8092 | Imprint