skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Sun, A."

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ; ; ; ; ; ( , Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2022))
    There has been a flurry of recent literature studying streaming algorithms for which the input stream is chosen adaptively by a black-box adversary who observes the output of the streaming algorithm at each time step. However, these algorithms fail when the adversary has access to the internal state of the algorithm, rather than just the output of the algorithm. We study streaming algorithms in the white-box adversarial model, where the stream is chosen adaptively by an adversary who observes the entire internal state of the algorithm at each time step. We show that nontrivial algorithms are still possible. We firstmore »give a randomized algorithm for the L1-heavy hitters problem that outperforms the optimal deterministic Misra-Gries algorithm on long streams. If the white-box adversary is computationally bounded, we use cryptographic techniques to reduce the memory of our L1-heavy hitters algorithm even further and to design a number of additional algorithms for graph, string, and linear algebra problems. The existence of such algorithms is surprising, as the streaming algorithm does not even have a secret key in this model, i.e., its state is entirely known to the adversary. One algorithm we design is for estimating the number of distinct elements in a stream with insertions and deletions achieving a multiplicative approximation and sublinear space; such an algorithm is impossible for deterministic algorithms. We also give a general technique that translates any two-player deterministic communication lower bound to a lower bound for randomized algorithms robust to a white-box adversary. In particular, our results show that for all p ≥ 0, there exists a constant Cp > 1 such that any Cp-approximation algorithm for Fp moment estimation in insertion-only streams with a white-box adversary requires Ω(n) space for a universe of size n. Similarly, there is a constant C > 1 such that any C-approximation algorithm in an insertion-only stream for matrix rank requires Ω(n) space with a white-box adversary. These results do not contradict our upper bounds since they assume the adversary has unbounded computational power. Our algorithmic results based on cryptography thus show a separation between computationally bounded and unbounded adversaries. Finally, we prove a lower bound of Ω(log n) bits for the fundamental problem of deterministic approximate counting in a stream of 0’s and 1’s, which holds even if we know how many total stream updates we have seen so far at each point in the stream. Such a lower bound for approximate counting with additional information was previously unknown, and in our context, it shows a separation between multiplayer deterministic maximum communication and the white-box space complexity of a streaming algorithm« less
    Free, publicly-accessible full text available January 1, 2023
  2. ; ; ; ; ; ; ; ; ; ; et al ( , Physical Review Letters)
    Free, publicly-accessible full text available March 1, 2023
  3. ; ; ; ; ; ; ; ; ; ; et al ( , Physical Review Letters)
    Free, publicly-accessible full text available October 1, 2022
  4. ; ; ; ; ; ; ; ; ; ; et al ( , Physical review letters)
    Quasielastic C12(e,e′p) scattering was measured at spacelike 4-momentum transfer squared Q2=8, 9.4, 11.4, and 14.2  (GeV/c)2, the highest ever achieved to date. Nuclear transparency for this reaction was extracted by comparing the measured yield to that expected from a plane-wave impulse approximation calculation without any final state interactions. The measured transparency was consistent with no Q2 dependence, up to proton momenta of 8.5  GeV/c, ruling out the quantum chromodynamics effect of color transparency at the measured Q2 scales in exclusive (e,e′p) reactions. These results impose strict constraints on models of color transparency for protons.
    Accepted Manuscript Full Text Available
  5. ; ; ; ; ; ; ; ; ; ; et al ( , Physical review letters)
    Accepted Manuscript Full Text Available
  6. ; ; ; ; ; ; ; ; ; ; et al ( , Physical review letters)
    Accepted Manuscript Full Text Available
  7. ; ; ; ; ; ; ; ; ; ; et al ( , Physical Review Letters)
    Full Text Available