Search Results

Documents authored by Zhan, Wei

Document
DOI: 10.4230/LIPIcs.ITCS.2024.99
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions

Authors: Huacheng Yu and Wei Zhan

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of n elements in [n], outputs O(n) elements, such that: - There exists a randomized oblivious algorithm with space O(log n), time O(nlog n) and one-way access to randomness, that computes the function with probability 1-O(1/n); - Any deterministic oblivious branching program with space S and time T that computes the function must satisfy T²S ≥ Ω(n^{2.5}/log n). This implies that logspace randomized algorithms for multi-output functions cannot be black-box derandomized without an Ω̃(n^{1/4}) overhead in time. Since previously all the polynomial time-space tradeoffs of multi-output functions are proved via the Borodin-Cook method, which is a probabilistic method that inherently gives the same lower bound for randomized and deterministic branching programs, our lower bound proof is intrinsically different from previous works. We also examine other natural candidates for proving such separations, and show that any polynomial separation for these problems would resolve the long-standing open problem of proving n^{1+Ω(1)} time lower bound for decision problems with polylog(n) space.
Cite as

Huacheng Yu and Wei Zhan. Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 99:1-99:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{yu_et_al:LIPIcs.ITCS.2024.99,
  author =	{Yu, Huacheng and Zhan, Wei},
  title =	{{Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{99:1--99:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.99},
  URN =		{urn:nbn:de:0030-drops-196270},
  doi =		{10.4230/LIPIcs.ITCS.2024.99},
  annote =	{Keywords: Time-space tradeoffs, Randomness, Borodin-Cook method}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.100
Sampling, Flowers and Communication

Authors: Huacheng Yu and Wei Zhan

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Given a distribution over [n]ⁿ such that any k coordinates need k/log^{O(1)}n bits of communication to sample, we prove that any map that samples this distribution from uniform cells requires locality Ω(log(n/k)/log log(n/k)). In particular, we show that for any constant δ > 0, there exists ε = 2^{-Ω(n^{1-δ})} such that Ω(log n/log log n) non-adaptive cell probes on uniform cells are required to: - Sample a uniformly random permutation on n elements with error 1-ε. This provides an exponential improvement on the Ω(log log n) cell probe lower bound by Viola. - Sample an n-vector with each element independently drawn from a random n^{1-δ}-vector, with error 1-ε. This provides the first adaptive vs non-adaptive cell probe separation for sampling. The major technical component in our proof is a new combinatorial theorem about flower with small kernel, i.e. a collection of sets where few elements appear more than once. We show that in a family of n sets, each with size O(log n/log log n), there must be k = poly(n) sets where at most k/log^{O(1)}n elements appear more than once. To show the lower bound on sampling permutation, we also prove a new Ω(k) communication lower bound on sampling uniformly distributed disjoint subsets of [n] of size k, with error 1-2^{-Ω(k²/n)}. This result unifies and subsumes the lower bound for k = Θ(√n) by Ambainis et al., and the lower bound for k = Θ(n) by Göös and Watson.
Cite as

Huacheng Yu and Wei Zhan. Sampling, Flowers and Communication. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 100:1-100:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{yu_et_al:LIPIcs.ITCS.2024.100,
  author =	{Yu, Huacheng and Zhan, Wei},
  title =	{{Sampling, Flowers and Communication}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{100:1--100:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.100},
  URN =		{urn:nbn:de:0030-drops-196288},
  doi =		{10.4230/LIPIcs.ITCS.2024.100},
  annote =	{Keywords: Flower, Sampling, Cell probe, Communcation complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.56
Is Untrusted Randomness Helpful?

Authors: Uma Girish, Ran Raz, and Wei Zhan

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Randomized algorithms and protocols assume the availability of a perfect source of randomness. In real life, however, perfect randomness is rare and is almost never guaranteed. The gap between these two facts motivated much of the work on randomness and derandomization in theoretical computer science. In this work, we define a new type of randomized algorithms (and protocols), that we call robustly-randomized algorithms (protocols). Such algorithms have access to two separate (read-once) random strings. The first string is trusted to be perfectly random, but its length is bounded by some parameter k = k(n) (where n is the length of the input). We think of k as relatively small, say sub-linear or poly-logarithmic in n. The second string is of unbounded length and is assumed to be random, but its randomness is not trusted. The output of the algorithm is either an output in the set of possible outputs of the problem, or a special symbol, interpreted as do not know and denoted by ⊥. On every input for the algorithm, the output of the algorithm must satisfy the following two requirements: 1) If the second random string is perfectly random then the algorithm must output the correct answer with high probability. 2) If the second random string is an arbitrary string, even adversarially chosen after seeing the input, the algorithm must output with high probability either the correct answer or the special symbol ⊥. We discuss relations of this new definition to several previously studied notions in randomness and derandomization. For example, when considering polynomial-time algorithms, if k is logarithmic we get the complexity class ZPP, while if k is unbounded we get the complexity class BPP, and for a general k, the algorithm can be viewed as an interactive proof with a probabilistic polynomial-time prover and a probabilistic polynomial-time verifier, where the prover is allowed an unlimited number of random bits and the verifier is limited to at most k random bits. Every previously-studied class of randomized algorithms or protocols, and more generally, every previous use of randomness in theoretical computer science, can be revisited and redefined in light of our new definition, by replacing each random string with a pair of random strings, the first is trusted to be perfectly random but is relatively short and the second is of unlimited length but its randomness is not trusted. The main question that we ask is: In which settings and for which problems is the untrusted random string helpful? Our main technical observation is that every problem in the class BPL (of problems solvable by bounded-error randomized logspace algorithms) can be solved by a robustly-randomized logspace algorithm with k = O(log n), that is with just a logarithmic number of trusted random bits. We also give query complexity separations that show cases where the untrusted random string is provenly helpful. Specifically, we show that there are promise problems that can be solved by robustly-randomized protocols with only one query and just a logarithmic number of trusted random bits, whereas any randomized protocol requires either a linear number of random bits or an exponential number of queries, and any zero-error randomized protocol requires a polynomial number of queries.
Cite as

Uma Girish, Ran Raz, and Wei Zhan. Is Untrusted Randomness Helpful?. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 56:1-56:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.ITCS.2023.56,
  author =	{Girish, Uma and Raz, Ran and Zhan, Wei},
  title =	{{Is Untrusted Randomness Helpful?}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{56:1--56:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.56},
  URN =		{urn:nbn:de:0030-drops-175593},
  doi =		{10.4230/LIPIcs.ITCS.2023.56},
  annote =	{Keywords: Untrusted, Randomness, Verifiable, ZPL, BPL, ZPP, BPP}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.6
Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs

Authors: Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
We prove that for every 3-player (3-prover) game G with value less than one, whose query distribution has the support S = {(1,0,0), (0,1,0), (0,0,1)} of Hamming weight one vectors, the value of the n-fold parallel repetition G^{⊗n} decays polynomially fast to zero; that is, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every 3-player game G over binary questions and arbitrary answer lengths, with value less than 1, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Our proof technique is new and requires many new ideas. For example, we make use of the Level-k inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.
Cite as

Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan. Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2022.6,
  author =	{Girish, Uma and Mittal, Kunal and Raz, Ran and Zhan, Wei},
  title =	{{Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.6},
  URN =		{urn:nbn:de:0030-drops-171286},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.6},
  annote =	{Keywords: Parallel repetition, Multi-prover games, Fourier analysis}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.52
Lower Bounds for XOR of Forrelations

Authors: Uma Girish, Ran Raz, and Wei Zhan

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
The Forrelation problem, first introduced by Aaronson [Scott Aaronson, 2010] and Aaronson and Ambainis [Scott Aaronson and Andris Ambainis, 2015], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [Scott Aaronson and Andris Ambainis, 2015]; the first separation between poly-logarithmic quantum query complexity and bounded-depth circuits of super-polynomial size, a result that also implied an oracle separation of the classes BQP and PH [Ran Raz and Avishay Tal, 2019]; and improved separations between quantum and classical communication complexity [Uma Girish et al., 2021]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than ≈ 1/√N, that is, the success probability is larger than ≈ 1/2 + 1/√N. This is unavoidable as ≈ 1/√N is the correlation between two coordinates of an input that is sampled from the Forrelation distribution, and hence there are simple classical protocols that achieve advantage ≈ 1/√N, in all these models. To achieve separations when the classical protocol has smaller advantage, we study in this work the xor of k independent copies of (a variant of) the Forrelation function (where k≪ N). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level 2k is bounded by α^k (that is, the sum of the absolute values of all Fourier coefficients at level 2k is bounded by α^k), cannot compute the xor of k independent copies of the Forrelation function with advantage better than O((α^k)/(N^{k/2})). This is a strengthening of a result of [Eshan Chattopadhyay et al., 2019], that gave a similar statement for k = 1, using the technique of [Ran Raz and Avishay Tal, 2019]. We give several applications of our result. In particular, we obtain the following separations: Quantum versus Classical Communication Complexity. We give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where Alice and Bob also share polylog(N) EPR pairs), and such that, any classical randomized protocol of communication complexity at most õ(N^{1/4}), with any number of rounds, has quasipolynomially small advantage over a random guess. Previously, only separations where the classical protocol has polynomially small advantage were known between these models [Dmitry Gavinsky, 2016; Uma Girish et al., 2021]. Quantum Query Complexity versus Bounded Depth Circuits. We give the first example of a partial Boolean function that has a quantum query algorithm with query complexity polylog(N), and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess. Previously, only separations where the constant-depth circuit has polynomially small advantage were known [Ran Raz and Avishay Tal, 2019].
Cite as

Uma Girish, Ran Raz, and Wei Zhan. Lower Bounds for XOR of Forrelations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.52,
  author =	{Girish, Uma and Raz, Ran and Zhan, Wei},
  title =	{{Lower Bounds for XOR of Forrelations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.52},
  URN =		{urn:nbn:de:0030-drops-147453},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.52},
  annote =	{Keywords: Forrelation, Quasipolynomial, Separation, Quantum versus Classical, Xor}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.62
Parallel Repetition for the GHZ Game: A Simpler Proof

Authors: Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n^{-Ω(1)}. This was first established by Holmgren and Raz [Holmgren and Raz, 2020]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [Greenberger et al., 1989] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [Dinur et al., 2017] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.
Cite as

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan. Parallel Repetition for the GHZ Game: A Simpler Proof. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.62,
  author =	{Girish, Uma and Holmgren, Justin and Mittal, Kunal and Raz, Ran and Zhan, Wei},
  title =	{{Parallel Repetition for the GHZ Game: A Simpler Proof}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.62},
  URN =		{urn:nbn:de:0030-drops-147551},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.62},
  annote =	{Keywords: Parallel Repetition, GHZ, Polynomial, Multi-player}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.73
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Authors: Uma Girish, Ran Raz, and Wei Zhan

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary n× n contraction matrix A, and a parameter T ≤ poly(n) and outputs the entries of A^T, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements. We show various implications and applications of this result: First, we use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space O(S + log T) that takes as an input the description of a quantum algorithm with quantum space S and time T, with intermediate measurements (without classical memory), and simulates it unitarily with polynomially small error, without intermediate measurements. Since unitary transformations are reversible (while measurements are irreversible) an interesting aspect of this result is that it shows that any quantum logspace algorithm (without classical memory) can be simulated by a reversible quantum logspace algorithm. This proves a quantum analogue of the result of Lange, McKenzie and Tapp that deterministic logspace is equal to reversible logspace [Lange et al., 2000]. Finally, we use our results to show non-trivial classical simulations of quantum logspace learning algorithms.
Cite as

Uma Girish, Ran Raz, and Wei Zhan. Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.ICALP.2021.73,
  author =	{Girish, Uma and Raz, Ran and Zhan, Wei},
  title =	{{Quantum Logspace Algorithm for Powering Matrices with Bounded Norm}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{73:1--73:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.73},
  URN =		{urn:nbn:de:0030-drops-141426},
  doi =		{10.4230/LIPIcs.ICALP.2021.73},
  annote =	{Keywords: BQL, Matrix Powering, Quantum Circuit, Reversible Computation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.20
The Random-Query Model and the Memory-Bounded Coupon Collector

Authors: Ran Raz and Wei Zhan

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We study a new model of space-bounded computation, the random-query model. The model is based on a branching-program over input variables x_1,…,x_n. In each time step, the branching program gets as an input a random index i ∈ {1,…,n}, together with the input variable x_i (rather than querying an input variable of its choice, as in the case of a standard (oblivious) branching program). We motivate the new model in various ways and study time-space tradeoff lower bounds in this model. Our main technical result is a quadratic time-space lower bound for zero-error computations in the random-query model, for XOR, Majority and many other functions. More precisely, a zero-error computation is a computation that stops with high probability and such that conditioning on the event that the computation stopped, the output is correct with probability 1. We prove that for any Boolean function f: {0,1}^n → {0,1}, with sensitivity k, any zero-error computation with time T and space S, satisfies T ⋅ (S+log n) ≥ Ω(n⋅k). We note that the best time-space lower bounds for standard oblivious branching programs are only slightly super linear and improving these bounds is an important long-standing open problem. To prove our results, we study a memory-bounded variant of the coupon-collector problem that seems to us of independent interest and to the best of our knowledge has not been studied before. We consider a zero-error version of the coupon-collector problem. In this problem, the coupon-collector could explicitly choose to stop when he/she is sure with zero-error that all coupons have already been collected. We prove that any zero-error coupon-collector that stops with high probability in time T, and uses space S, satisfies T⋅(S+log n) ≥ Ω(n^2), where n is the number of different coupons.
Cite as

Ran Raz and Wei Zhan. The Random-Query Model and the Memory-Bounded Coupon Collector. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 20:1-20:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.ITCS.2020.20,
  author =	{Raz, Ran and Zhan, Wei},
  title =	{{The Random-Query Model and the Memory-Bounded Coupon Collector}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{20:1--20:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.20},
  URN =		{urn:nbn:de:0030-drops-117053},
  doi =		{10.4230/LIPIcs.ITCS.2020.20},
  annote =	{Keywords: random-query model, time-space trade-offs, branching programs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.49
Odd Yao-Yao Graphs are Not Spanners

Authors: Yifei Jin, Jian Li, and Wei Zhan

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
It is a long standing open problem whether Yao-Yao graphs YY_{k} are all spanners [Li et al. 2002]. Bauer and Damian [Bauer and Damian, 2012] showed that all YY_{6k} for k >= 6 are spanners. Li and Zhan [Li and Zhan, 2016] generalized their result and proved that all even Yao-Yao graphs YY_{2k} are spanners (for k >= 42). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer k >= 1, there exist odd Yao-Yao graph YY_{2k+1} instances, which are not spanners.
Cite as

Yifei Jin, Jian Li, and Wei Zhan. Odd Yao-Yao Graphs are Not Spanners. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jin_et_al:LIPIcs.SoCG.2018.49,
  author =	{Jin, Yifei and Li, Jian and Zhan, Wei},
  title =	{{Odd Yao-Yao Graphs are Not Spanners}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.49},
  URN =		{urn:nbn:de:0030-drops-87621},
  doi =		{10.4230/LIPIcs.SoCG.2018.49},
  annote =	{Keywords: Odd Yao-Yao Graph, Spanner, Counterexample}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.11
k-Regret Minimizing Set: Efficient Algorithms and Hardness

Authors: Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
We study the k-regret minimizing query (k-RMS), which is a useful operator for supporting multi-criteria decision-making. Given two integers k and r, a k-RMS returns r tuples from the database which minimize the k-regret ratio, defined as one minus the worst ratio between the k-th maximum utility score among all tuples in the database and the maximum utility score of the r tuples returned. A solution set contains only r tuples, enjoying the benefits of both top-k queries and skyline queries. Proposed in 2012, the query has been studied extensively in recent years. In this paper, we advance the theory and the practice of k-RMS in the following aspects. First, we develop efficient algorithms for k-RMS (and its decision version) when the dimensionality is 2. The running time of our algorithms outperforms those of previous ones. Second, we show that k-RMS is NP-hard even when the dimensionality is 3. This provides a complete characterization of the complexity of k-RMS, and answers an open question in previous studies. In addition, we present approximation algorithms for the problem when the dimensionality is 3 or larger.
Cite as

Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan. k-Regret Minimizing Set: Efficient Algorithms and Hardness. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ICDT.2017.11,
  author =	{Cao, Wei and Li, Jian and Wang, Haitao and Wang, Kangning and Wang, Ruosong and Chi-Wing Wong, Raymond and Zhan, Wei},
  title =	{{k-Regret Minimizing Set: Efficient Algorithms and Hardness}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.11},
  URN =		{urn:nbn:de:0030-drops-70569},
  doi =		{10.4230/LIPIcs.ICDT.2017.11},
  annote =	{Keywords: multi-criteria decision-making, regret minimizing set, top-k query}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.62
Almost All Even Yao-Yao Graphs Are Spanners

Authors: Jian Li and Wei Zhan

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
It is an open problem whether Yao-Yao graphs YY_{k} (also known as sparse-Yao graphs) are all spanners when the integer parameter k is large enough. In this paper we show that, for any integer k >= 42, the Yao-Yao graph YY_{2k} is a t_k-spanner, with stretch factor t_k = 6.03+O(k^{-1}) when k tends to infinity. Our result generalizes the best known result which asserts that all YY_{6k} are spanners for k >= 6 [Bauer and Damian, SODA'13]. Our proof is also somewhat simpler.
Cite as

Jian Li and Wei Zhan. Almost All Even Yao-Yao Graphs Are Spanners. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 62:1-62:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ESA.2016.62,
  author =	{Li, Jian and Zhan, Wei},
  title =	{{Almost All Even Yao-Yao Graphs Are Spanners}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{62:1--62:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.62},
  URN =		{urn:nbn:de:0030-drops-64033},
  doi =		{10.4230/LIPIcs.ESA.2016.62},
  annote =	{Keywords: Yao-Yao graph, geometric spanner, curved trapezoid}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact