Search

Large language models show a surprising in-context learning ability -- being able to use a prompt to form a prediction for a query, yet without additional training, in stark contrast to old-fashioned supervised learning. Providing a mechanistic interpretation and linking the empirical phenomenon to physics are thus challenging and remain unsolved. We study a simple yet expressive transformer with linear attention, and map this structure to a spin glass model with real-valued spins, where the couplings and fields explain the intrinsic disorder in data. The spin glass model explains how the weight parameters interact with each other during pre-training, and most importantly why an unseen function can be predicted by providing only a prompt yet without training. Our theory reveals that for single instance learning, increasing the task diversity leads to the emergence of the in-context learning, by allowing the Boltzmann distribution to converge to a unique correct solution of weight parameters. Therefore the pre-trained transformer displays a prediction power in a novel prompt setting. The proposed spin glass model thus establishes a foundation to understand the empirical success of large language models., Comment: 8 pages, 4 figures

The coupling of mechanical deformation and electrical stimuli at the nanoscale has been a subject of intense investigation in the realm of materials science. Recently, twisted van der Waals (vdW) materials have emerged as a platform to explore exotic quantum states. These states are intimately tied to the formation of moir\'e superlattices, which can be visualized directly exploiting the electromechanical response. However, the origin of the response, even in twisted bilayer graphene (tBLG), remains unsettled. Here, employing lateral piezoresponse force microscopy (LPFM), we investigate the electromechanical responses of marginally twisted graphene moir\'e superlattices with different layer thicknesses. We observe distinct LPFM amplitudes and spatial profiles in tBLG and twisted monolayer-bilayer graphene (tMBG), exhibiting effective in-plane piezoelectric coefficients of 0.05 pm/V and 0.35 pm/V, respectively. Force tuning experiments further underscore a marked divergence in their responses. The contrasting behaviors suggest different electromechanical couplings in tBLG and tMBG. In tBLG, the response near the domain walls is attributed to the flexoelectric effect, while in tMBG, the behaviors can be comprehended within the context of piezoelectric effect. Our results not only provide insights to electromechanical and corporative effects in twisted vdW materials with different stacking symmetries, but may also show their potential for engineering them at the nanoscale.

Most existing multi-object tracking methods typically learn visual tracking features via maximizing dis-similarities of different instances and minimizing similarities of the same instance. While such a feature learning scheme achieves promising performance, learning discriminative features solely based on visual information is challenging especially in case of environmental interference such as occlusion, blur and domain variance. In this work, we argue that multi-modal language-driven features provide complementary information to classical visual features, thereby aiding in improving the robustness to such environmental interference. To this end, we propose a new multi-object tracking framework, named LG-MOT, that explicitly leverages language information at different levels of granularity (scene-and instance-level) and combines it with standard visual features to obtain discriminative representations. To develop LG-MOT, we annotate existing MOT datasets with scene-and instance-level language descriptions. We then encode both instance-and scene-level language information into high-dimensional embeddings, which are utilized to guide the visual features during training. At inference, our LG-MOT uses the standard visual features without relying on annotated language descriptions. Extensive experiments on three benchmarks, MOT17, DanceTrack and SportsMOT, reveal the merits of the proposed contributions leading to state-of-the-art performance. On the DanceTrack test set, our LG-MOT achieves an absolute gain of 2.2\% in terms of target object association (IDF1 score), compared to the baseline using only visual features. Further, our LG-MOT exhibits strong cross-domain generalizability. The dataset and code will be available at ~\url{https://github.com/WesLee88524/LG-MOT}.

We give an algorithm for finding an $\epsilon$-fixed point of a contraction map $f:[0,1]^k\mapsto[0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k^2\log (1/\epsilon ) )$., Comment: To appear in STOC'24

Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically \emph{intersecting} families and \emph{union-closed} families. A function $f: \{0,1\}^n \to \{0,1\}$ is intersecting (respectively, union-closed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a union-closed family) of subsets of $[n]$. Our main results are that -- in sharp contrast with the property of being a monotone set system -- the property of being an intersecting set system, and the property of being a union-closed set system, both turn out to be information-theoretically difficult to test. We show that: $\bullet$ For $\epsilon \geq \Omega(1/\sqrt{n})$, any non-adaptive two-sided $\epsilon$-tester for intersectingness must make $2^{\Omega(n^{1/4}/\sqrt{\epsilon})}$ queries. We also give a $2^{\Omega(\sqrt{n \log(1/\epsilon)})}$-query lower bound for non-adaptive one-sided $\epsilon$-testers for intersectingness. $\bullet$ For $\epsilon \geq 1/2^{\Omega(n^{0.49})}$, any non-adaptive two-sided $\epsilon$-tester for union-closedness must make $n^{\Omega(\log(1/\epsilon))}$ queries. Thus, neither intersectingness nor union-closedness shares the $\mathrm{poly}(n,1/\epsilon)$-query non-adaptive testability that is enjoyed by monotonicity. To complement our lower bounds, we also give a simple $\mathrm{poly}(n^{\sqrt{n\log(1/\epsilon)}},1/\epsilon)$-query, one-sided, non-adaptive algorithm for $\epsilon$-testing each of these properties (intersectingness and union-closedness). We thus achieve nearly tight upper and lower bounds for two-sided testing of intersectingness when $\epsilon = \Theta(1/\sqrt{n})$, and for one-sided testing of intersectingness when $\epsilon=\Theta(1).$, Comment: To appear in ITCS'24

Image-to-point cloud (I2P) registration is a fundamental task for robots and autonomous vehicles to achieve cross-modality data fusion and localization. Current I2P registration methods primarily focus on estimating correspondences at the point or pixel level, often neglecting global alignment. As a result, I2P matching can easily converge to a local optimum if it lacks high-level guidance from global constraints. To improve the success rate and general robustness, this paper introduces CoFiI2P, a novel I2P registration network that extracts correspondences in a coarse-to-fine manner. First, the image and point cloud data are processed through a two-stream encoder-decoder network for hierarchical feature extraction. Second, a coarse-to-fine matching module is designed to leverage these features and establish robust feature correspondences. Specifically, In the coarse matching phase, a novel I2P transformer module is employed to capture both homogeneous and heterogeneous global information from the image and point cloud data. This enables the estimation of coarse super-point/super-pixel matching pairs with discriminative descriptors. In the fine matching module, point/pixel pairs are established with the guidance of super-point/super-pixel correspondences. Finally, based on matching pairs, the transform matrix is estimated with the EPnP-RANSAC algorithm. Experiments conducted on the KITTI Odometry dataset demonstrate that CoFiI2P achieves impressive results, with a relative rotation error (RRE) of 1.14 degrees and a relative translation error (RTE) of 0.29 meters, while maintaining real-time speed.Additional experiments on the Nuscenes datasets confirm our method's generalizability. The project page is available at \url{https://whu-usi3dv.github.io/CoFiI2P}., Comment: Accepted by IEEE RA-L 2024. Code, pretrained models and additional results are available at: https://whu-usi3dv.github.io/CoFiI2P

Trading through decentralized exchanges (DEXs) has become crucial in today's blockchain ecosystem, enabling users to swap tokens efficiently and automatically. However, the capacity of miners to strategically order transactions has led to exploitative practices (e.g., front-running attacks, sandwich attacks) and gain substantial Maximal Extractable Value (MEV) for their own advantage. To mitigate such manipulation, Ferreira and Parkes recently proposed a greedy sequencing rule such that the execution price of transactions in a block moves back and forth around the starting price. Utilizing this sequencing rule makes it impossible for miners to conduct sandwich attacks, consequently mitigating the MEV problem. However, no sequencing rule can prevent miners from obtaining risk-free profits. This paper systemically studies the computation of a miner's optimal strategy for maximizing MEV under the greedy sequencing rule, where the utility of miners is measured by the overall value of their token holdings. Our results unveil a dichotomy between the no trading fee scenario, which can be optimally strategized in polynomial time, and the scenario with a constant fraction of trading fee, where finding the optimal strategy is proven NP-hard. The latter represents a significant challenge for miners seeking optimal MEV. Following the computation results, we further show a remarkable phenomenon: Miner's optimal MEV also benefits users. Precisely, in the scenarios without trading fees, when miners adopt the optimal strategy given by our algorithm, all users' transactions will be executed, and each user will receive equivalent or surpass profits compared to their expectations. This outcome provides further support for the study and design of sequencing rules in decentralized exchanges., Comment: 14 Pages, ACM CCS Workshop on Decentralized Finance and Security (DeFi'23)

We give the first super-polynomial (in fact, mildly exponential) lower bounds for tolerant testing (equivalently, distance estimation) of monotonicity, unateness, and juntas with a constant separation between the "yes" and "no" cases. Specifically, we give $\bullet$ A $2^{\Omega(n^{1/4}/\sqrt{\varepsilon})}$-query lower bound for non-adaptive, two-sided tolerant monotonicity testers and unateness testers when the "gap" parameter $\varepsilon_2-\varepsilon_1$ is equal to $\varepsilon$, for any $\varepsilon \geq 1/\sqrt{n}$; $\bullet$ A $2^{\Omega(k^{1/2})}$-query lower bound for non-adaptive, two-sided tolerant junta testers when the gap parameter is an absolute constant. In the constant-gap regime no non-trivial prior lower bound was known for monotonicity, the best prior lower bound known for unateness was $\tilde{\Omega}(n^{3/2})$ queries, and the best prior lower bound known for juntas was $\mathrm{poly}(k)$ queries., Comment: 20 pages, 1 figure

It is shown in recent studies that in a Stackelberg game the follower can manipulate the leader by deviating from their true best-response behavior. Such manipulations are computationally tractable and can be highly beneficial for the follower. Meanwhile, they may result in significant payoff losses for the leader, sometimes completely defeating their first-mover advantage. A warning to commitment optimizers, the risk these findings indicate appears to be alleviated to some extent by a strict information advantage the manipulations rely on. That is, the follower knows the full information about both players' payoffs whereas the leader only knows their own payoffs. In this paper, we study the manipulation problem with this information advantage relaxed. We consider the scenario where the follower is not given any information about the leader's payoffs to begin with but has to learn to manipulate by interacting with the leader. The follower can gather necessary information by querying the leader's optimal commitments against contrived best-response behaviors. Our results indicate that the information advantage is not entirely indispensable to the follower's manipulations: the follower can learn the optimal way to manipulate in polynomial time with polynomially many queries of the leader's optimal commitment.

To take advantage of strategy commitment, a useful tactic of playing games, a leader must learn enough information about the follower's payoff function. However, this leaves the follower a chance to provide fake information and influence the final game outcome. Through a carefully contrived payoff function misreported to the learning leader, the follower may induce an outcome that benefits him more, compared to the ones when he truthfully behaves. We study the follower's optimal manipulation via such strategic behaviors in extensive-form games. Followers' different attitudes are taken into account. An optimistic follower maximizes his true utility among all game outcomes that can be induced by some payoff function. A pessimistic follower only considers misreporting payoff functions that induce a unique game outcome. For all the settings considered in this paper, we characterize all the possible game outcomes that can be induced successfully. We show that it is polynomial-time tractable for the follower to find the optimal way of misreporting his private payoff information. Our work completely resolves this follower's optimal manipulation problem on an extensive-form game tree.

A double moir\'e superlattice can be realized by stacking three layers of atomically thin two-dimensional materials with designer interlayer twisting or lattice mismatches. In this novel structure, atomic reconstruction of constituent layers could introduce significant modifications to the lattice symmetry and electronic structure at small twist angles. Here, we employ conductive atomic force microscopy (cAFM) to investigate symmetry breaking and local electrical properties in twisted trilayer graphene. We observe clear double moir\'e superlattices with two distinct moire periods all over the sample. At neighboring domains of the large moir\'e, the current exhibit either two- or six-fold rotational symmetry, indicating delicate symmetry breaking beyond the rigid model. Moreover, an anomalous current appears at the 'A-A' stacking site of the larger moir\'e, contradictory to previous observations on twisted bilayer graphene. Both behaviors can be understood by atomic reconstruction, and we also show that the cAFM signal of twisted graphene samples is dominated by the tip-graphene contact resistance that maps the local work function of twisted graphene and the metallic tip qualitatively. Our results unveil cAFM is an effective probe for visualizing atomic reconstruction and symmetry breaking in novel moir\'e superlattices, which could provide new insights for exploring and manipulating more exotic quantum states based on twisted van der Waals heterostructures.

The selfish mining attack, arguably the most famous game-theoretic attack in blockchain, indicates that the Bitcoin protocol is not incentive-compatible. Most subsequent works mainly focus on strengthening the selfish mining strategy, thus enabling a single strategic agent more likely to deviate. In sharp contrast, little attention has been paid to the resistant behavior against the selfish mining attack, let alone further equilibrium analysis for miners and mining pools in the blockchain as a multi-agent system. In this paper, first, we propose a strategy called insightful mining to counteract selfish mining. By infiltrating an undercover miner into the selfish pool, the insightful pool could acquire the number of its hidden blocks. We prove that, with this extra insight, the utility of the insightful pool could be strictly greater than the selfish pool's when they have the same mining power. Then we investigate the mining game where all pools can either choose to be honest or take the insightful mining strategy. We characterize the Nash equilibrium of this mining game, and derive three corollaries: (a) each mining game has a pure Nash equilibrium; (b) honest mining is a Nash equilibrium if the largest mining pool has a fraction of mining power no more than 1/3; (c) there are at most two insightful pools under equilibrium no matter how the mining power is distributed.

We study the query complexity of finding a Tarski fixed point over the $k$-dimensional grid $\{1,\ldots,n\}^k$. Improving on the previous best upper bound of $\smash{O(\log^{\lceil 2k/3\rceil} n)}$ [FPS20], we give a new algorithm with query complexity $\smash{O(\log^{\lceil (k+1)/2\rceil} n)}$. This is based on a novel decomposition theorem about a weaker variant of the Tarski fixed point problem, where the input consists of a monotone function $f:[n]^k\rightarrow [n]^k$ and a monotone sign function $b:[n]^k\rightarrow \{-1,0,1\}$ and the goal is to find an $x\in [n]^k$ that satisfies $either$ $f(x)\preceq x$ and $b(x)\le 0$ $or$ $f(x)\succeq x$ and $b(x)\ge 0$., Comment: To appear in EC 2022

Twisted double bilayer graphene (tDBG) has emerged as an especially rich platform for studying strongly correlated and topological states of matter. The material features moir\'e bands that can be continuously deformed by both perpendicular displacement field and twist angle. Here, we construct a phase diagram representing of the correlated and topological states as a function of these parameters, based on measurements on over a dozen tDBG devices encompassing the two distinct stacking configurations in which the constituent Bernal bilayer graphene sheets are rotated either slightly away from 0{\deg} or 60{\deg}. We find a hierarchy of symmetry-broken states that emerge sequentially as the twist angle approaches an apparent optimal value of $\theta \approx$ 1.34{\deg}. Among them, we discover a sequence of symmetry-broken Chern insulator (SBCI) states that arise only within a narrow range of twist angles ($\approx$ 1.33{\deg} to 1.39{\deg}). We observe an associated anomalous Hall effect at zero field in all samples supporting SBCI states, indicating spontaneous time-reversal symmetry breaking and possible moir\'e unit cell enlargement at zero magnetic field., Comment: 42 pages

This article explores the minimum approximation ratio for Nash equilibrium in bi-matrix games, focusing on the Tsaknakis and Spirakis (TS) methods. The previous SOTA, TS algorithm, achieved an approximation ratio of 0.3393, but efforts to improve the analysis of the TS algorithm have been unsuccessful. This work demonstrates that the bound of 0.3393 is tight for the TS algorithm and presents a theoretical worst-case analysis. A condition for identifying tight instances is provided, along with a generator. While most generated instances are unstable, indicating potential improvements, stable instances exist where perturbations cannot enhance the 0.3393 bound. Other approximate algorithms, such as regret-matching and fictitious play, achieve better ratios on these instances. The generated instances can serve as benchmarks for approximate Nash equilibrium algorithms. The article also mentions progress in the TS algorithm, achieving an approximation ratio of 1/3, which can be further studied using the presented techniques.