Source author record

Chengyu Lin

Chengyu Lin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Cryptography and Security Data Structures and Algorithms eess.SY Machine Learning Systems and Control

Catalog footprint

What is connected

4works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

On Discrete Age of Information of Status Updating System With General Packet Arrival Processes

Characterizing Age of Information (AoI) in status updating systems with general arrival and service processes has great significance considering that the interarrival and service time of updates can possibly be arbitrary in a real world. While expressions of average continuous AoI under G/G/1/1 queues have been derived in the paper by Soysal and Ulukus, the discrete case remained unsolved. To address it, this paper gives a fully characterization of probability generation functions (PGF) of discrete AoI under G/G/1/1 settings when preemption is allowed. In the non-preemptive case, this paper gives the expressions of PGF of discrete AoI under G/Geo/1/1 settings, which also extends the former results. The average discrete AoI is derived and discussed based on these new theoretical findings.

preprint2022arXiv

New Distinguishers for Negation-Limited Weak Pseudorandom Functions

We show how to distinguish circuits with $\log k$ negations (a.k.a $k$-monotone functions) from uniformly random functions in $\exp\left(\tilde{O}\left(n^{1/3}k^{2/3}\right)\right)$ time using random samples. The previous best distinguisher, due to the learning algorithm by Blais, Cannone, Oliveira, Servedio, and Tan (RANDOM'15), requires $\exp\big(\tilde{O}(n^{1/2} k)\big)$ time. Our distinguishers are based on Fourier analysis on \emph{slices of the Boolean cube}. We show that some "middle" slices of negation-limited circuits have strong low-degree Fourier concentration and then we apply a variation of the classic Linial, Mansour, and Nisan "Low-Degree algorithm" (JACM'93) on slices. Our techniques also lead to a slightly improved weak learner for negation limited circuits under the uniform distribution.

preprint2016arXiv

Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers

The Sensitivity Conjecture and the Log-rank Conjecture are among the most important and challenging problems in concrete complexity. Incidentally, the Sensitivity Conjecture is known to hold for monotone functions, and so is the Log-rank Conjecture for $f(x \wedge y)$ and $f(x\oplus y)$ with monotone functions $f$, where $\wedge$ and $\oplus$ are bit-wise AND and XOR, respectively. In this paper, we extend these results to functions $f$ which alternate values for a relatively small number of times on any monotone path from $0^n$ to $1^n$. These deepen our understandings of the two conjectures, and contribute to the recent line of research on functions with small alternating numbers.

preprint2013arXiv

A Simple FPTAS for Counting Edge Covers

An edge cover of a graph is a set of edges such that every vertex has at least an adjacent edge in it. Previously, approximation algorithm for counting edge covers is only known for 3 regular graphs and it is randomized. We design a very simple deterministic fully polynomial-time approximation scheme (FPTAS) for counting the number of edge covers for any graph. Our main technique is correlation decay, which is a powerful tool to design FPTAS for counting problems. In order to get FPTAS for general graphs without degree bound, we make use of a stronger notion called computationally efficient correlation decay, which is introduced in [Li, Lu, Yin SODA 2012].