Consider a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included iid so that the average degree is $n^\delta$. The projection of a hypergraph is a graph on the same $n$ vertices where an edge connects two vertices if and only if they belong to some hyperedge. The goal is to reconstruct the hypergraph given its projection. An earlier work of Bresler, Guo, and Polyanskiy (COLT 2024) showed that exact recovery for $d=3$ is possible if and only if $\delta < 2/5$. This work completely resolves the question for all values of $d$ for both exact and partial recovery and for both cases of whether multiplicity information about each edge is available or not. In addition, we show that the reconstruction fidelity undergoes an all-or-nothing transition at a threshold. In particular, this resolves all conjectures from Bresler, Guo, and Polyanskiy (COLT 2024).

Advanced Driver Assistance Systems (ADAS) are designed to prevent collisions, identify the condition of drivers while operating vehicles, and provide additional information to enhance drivers’ awareness of potential hazards on the road. Today, ADAS are capable of predicting drivers’ actions several seconds in advance, preparing for potential future hazards to prevent accidents or reduce injuries to occupants. Most previous works have achieved prediction results by analyzing and processing a vast amount of driving data from multiple drivers, based on the macro intention preferences of multiple drivers and external environmental features, collectively referred to as the generalized intention prediction network. This network utilizes extensive driving data to predict the common driving intentions of the overall driving population, without considering individualized driving styles. However, according to our research, different drivers exhibit distinct latent preferences in real-world driving scenarios. The generalized intention prediction network is influenced by these latent preferences, resulting in poor generalization capabilities and inaccurate predictions across different drivers. In this study, we propose a individualized driver intention prediction network. Based on Inverse Reinforcement Learning (IRL), it extracts individualized driving intention feature preferences that influence driving intentions from the driver’s historical behavior to improve generalized prediction results and achieve individualized driving intention prediction. We demonstrate that preferences vary among different drivers in the driving domain, leading to biases in model predictions. Upon experimental validation, the method we have proposed demonstrates remarkable efficacy on both the Brain4Cars and IESDD datasets, thereby showcasing its enhanced applicability in real-world scenarios.

The graph projection of a hypergraph is a simple graph with the same vertex set and with an edge between each pair of vertices that appear in a hyperedge. We consider the problem of reconstructing a random $d$-uniform hypergraph from its projection. Feasibility of this task depends on $d$ and the density of hyperedges in the random hypergraph. For $d=3$ we precisely determine the threshold, while for $d\ge 4$ we give bounds. All of our feasibility results are obtained by exhibiting an efficient algorithm for reconstructing the original hypergraph, while infeasibility is information-theoretic. Our results also apply to mildly inhomogeneous random hypergrahps, including hypergraph stochastic block models (HSBM). A consequence of our results is an optimal HSBM recovery algorithm, improving on Gaudio and Joshi (2023a).

We give the first quasipolynomial upper bound φnpolylog(n) for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width) under the full perturbation model, where n is the number of nodes in the graph and φ is a parameter that measures the magnitude of perturbations applied on its edge weights. More generally, we show that the same quasipolynomial upper bound holds for the smoothed complexity of the 2-FLIP algorithm for any binary Maximum Constraint Satisfaction Problem, including local Max-Cut, for which similar bounds were only known for 1-FLIP. Our results are based on an analysis of a new notion of useful cycles in the multigraph formed by long sequences of double flips, showing that it is unlikely for every double flip in a long sequence to incur a positive but small improvement in the cut weight.

We aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erdős-Rényi $G(n, p)$, which has independent edges, we take the ambient graph to be the random graph with triangles (RGT) obtained by adding triangles to $G(n, p)$. We show that the RGT can be efficiently mapped to the corresponding $G(n, p)$, and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erdős-Rényi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations.

Since enormous hazards are caused by traffic crashes every year, ensuring safe driving is a hot topic in transportation. Technologies related to the Advanced Driver Assistance System (ADAS) are evolving rapidly. But without an adequate understanding of driving intention, ADAS usually can’t help the driver prepare for the danger in advance. This paper focuses on the fusion strategy of driver and environment information and proposes a lightweight end-to-end model, temporal information fusion network (TIFN). Driving behavior is the interactive result of the driver and the external world. To better understand the driver’s intention, the state update cell (STU) is proposed to introduce the influence of environment information into the driver’s state modeling, inspired by the selective attention of the human cognition process. Meanwhile, semantic segmentation features are extracted to offer clear clues affecting driver attention in place of motion optical flow images and binary value vectors. Finally, the driver’s intention and environment state are combined to make a joint prediction. The experiments evaluated on Brain4cars and IESDD show that the proposed approach has superior performance than other approaches that only use camera data.

This paper explores a theory of generalization for learning problems on product distributions, complementing the existing learning theories in the sense that it does not rely on any complexity measures of the hypothesis classes. The main contributions are two general sample complexity bounds: (1) $\tilde{O} \big( \frac{nk}{\epsilon^2} \big)$ samples are sufficient and necessary for learning an $\epsilon$-optimal hypothesis in \emph{any problem} on an $n$-dimensional product distribution, whose marginals have finite supports of sizes at most $k$; (2) $\tilde{O} \big( \frac{n}{\epsilon^2} \big)$ samples are sufficient and necessary for any problem on $n$-dimensional product distributions if it satisfies a notion of strong monotonicity from the algorithmic game theory literature. As applications of these theories, we match the optimal sample complexity for single-parameter revenue maximization (Guo et al., STOC 2019), improve the state-of-the-art for multi-parameter revenue maximization (Gonczarowski and Weinberg, FOCS 2018) and prophet inequality (Correa et al., EC 2019; Rubinstein et al., ITCS 2020), and provide the first and tight sample complexity bound for Pandora’s problem.

We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most φ n O(√logn), where n is the number of nodes in the graph and φ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of φ n O(logn) by Etscheid and Roglin. Our result is based on an analysis of long sequences of flips, which shows that it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems.

This paper settles the sample complexity of single-parameter revenue maximization by showing matching upper and lower bounds, up to a poly-logarithmic factor, for all families of value distributions that have been considered in the literature. The upper bounds are unified under a novel framework, which builds on the strong revenue monotonicity by Devanur, Huang, and Psomas (STOC 2016), and an information theoretic argument. This is fundamentally different from the previous approaches that rely on either constructing an є-net of the mechanism space, explicitly or implicitly via statistical learning theory, or learning an approximately accurate version of the virtual values. To our knowledge, it is the first time information theoretical arguments are used to show sample complexity upper bounds, instead of lower bounds. Our lower bounds are also unified under a meta construction of hard instances.

Fog computing has changed the distributed computing rapidly by including the smart devices widely distributed at the network edges. It is able to provide less latency and is more capable of decreasing traffic jam in the network. However, it will bring more difficulties for resource managing and task scheduling especially in a decentralized ad hoc network. In this paper, we propose a method that takes advantages of the immune mechanism to schedule tasks in a decentralized way for fog computing. By using forward propagation and backward propagation in the ad hoc network, the power of distributed schedulers is used to generate the optimized scheduler strategies to deal with computing nodes overloaded and achieve the optimal task finishing time reducing. The experiment results show that our approach can beat similar methods.