OpenRaiser/Intern-Atlas huggingface dataset:
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast
Venue: arXiv cs.DS 2023
Year: 2023

Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as $h$-length flows which are defined as flows whose flow paths are restricted to have length at most $h$. Many well-studied algorithmic primitives -- such as maximal and maximum length-constrained disjoint paths -- are special cases of $h$-length flows. Likewise the optimal $h$-length flow is a fundamental quantity in network optimization, characterizing, up to poly-log factors, how quickly a network can accomplish numerous distributed primitives. In this work, we give the first efficient algorithms for computing $(1 - ε)$-approximate $h$-length flows. We give deterministic algorithms that take $\tilde{O}(\text{poly}(h, \frac{1}ε))$ parallel time and $\tilde{O}(\text{poly}(h, \frac{1}ε) \cdot 2^{O(\sqrt{\log n})})$ distributed CONGEST time. We also give a CONGEST algorithm that succeeds with high probability and only takes $\tilde{O}(\text{poly}(h, \frac{1}ε))$ time. Using our $h$-length flow algorithms, we give the first efficient deterministic CONGEST algorithms for the maximal length-constrained disjoint paths problem -- settling an open question of Chang and Saranurak (FOCS 2020) -- as well as essentially-optimal parallel and distributed approximation algorithms for maximum length-constrained disjoint paths. The former greatly simplifies deterministic CONGEST algorithms for computing expander decompositions. We also use our techniques to give the first efficient $(1-ε)$-approximation algorithms for bipartite $b$-matching in CONGEST. Lastly, using our flow algorithms, we give the first algorithms to efficiently compute $h$-length cutmatches, an object at the heart of recent advances in length-constrained expander decompositions.
Likelihood-Free Inference in State-Space Models with Unknown Dynamics
Venue: arXiv cs.LG 2023
Year: 2023

Likelihood-free inference (LFI) has been successfully applied to state-space models, where the likelihood of observations is not available but synthetic observations generated by a black-box simulator can be used for inference instead. However, much of the research up to now have been restricted to cases, in which a model of state transition dynamics can be formulated in advance and the simulation budget is unrestricted. These methods fail to address the problem of state inference when simulations are computationally expensive and the Markovian state transition dynamics are undefined. The approach proposed in this manuscript enables LFI of states with a limited number of simulations by estimating the transition dynamics, and using state predictions as proposals for simulations. In the experiments with non-stationary user models, the proposed method demonstrates significant improvement in accuracy for both state inference and prediction, where a multi-output Gaussian process is used for LFI of states, and a Bayesian Neural Network as a surrogate model of transition dynamics.
Introducing a Framework to Enable Anonymous Secure Multi-Party Computation in Practice (Extended Version)
Venue: arXiv cs.CR 2023
Year: 2023

Secure Multi-Party Computation (SMPC) allows a set of parties to securely compute a functionality in a distributed fashion without the need for any trusted external party. Usually, it is assumed that the parties know each other and have already established authenticated channels among each other. However, in practice the parties sometimes must stay anonymous. In this paper, we conceptualize a framework that enables the repeated execution of an SMPC protocol for a given functionality such that the parties can keep their participation in the protocol executions private and at the same time be sure that only authorized parties may take part in a protocol execution. We identify the security properties that an implementation of our framework must meet and introduce a first implementation of the framework that achieves these properties.
LTL under reductions with weaker conditions than stutter-invariance
Venue: arXiv cs.CL 2023
Year: 2023

Verification of properties expressed as-regular languages such as LTL can benefit hugely from stutter-insensitivity, using a diverse set of reduction strategies. However properties that are not stutter-insensitive, for instance due to the use of the neXt operator of LTL or to some form of counting in the logic, are not covered by these techniques in general. We propose in this paper to study a weaker property than stutter-insensitivity. In a stutter insensitive language both adding and removing stutter to a word does not change its acceptance, any stuttering can be abstracted away; by decomposing this equivalence relation into two implications we obtain weaker conditions. We define a shortening insensitive language where any word that stutters less than a word in the language must also belong to the language. A lengthening insensitive language has the dual property. A semi-decision procedure is then introduced to reliably prove shortening insensitive properties or deny lengthening insensitive properties while working with a reduction of a system. A reduction has the property that it can only shorten runs. Lipton's transaction reductions or Petri net agglomerations are examples of eligible structural reduction strategies. An implementation and experimental evidence is provided showing most nonrandom properties sensitive to stutter are actually shortening or lengthening insensitive. Performance of experiments on a large (random) benchmark from the model-checking competition indicate that despite being a semi-decision procedure, the approach can still improve state of the art verification tools.
The eXtreme Mesh deformation approach (X-MESH) for the Stefan phase-change model
Venue: arXiv cs.CE 2023
Year: 2023

The eXtreme Mesh deformation approach (X-MESH) is a new paradigm to follow sharp interfaces without remeshing and without changing the mesh topology. Even though the mesh does not change its topology, it can follow interfaces that do change their topology (nucleation, coalescence, splitting). To make this possible, the key X-MESH idea is to allow elements to reach zero measure. This permits interface relaying between nodes as well as interface annihilation and seeding in a time continuous manner. The paper targets the Stefan phase change model in which the interface (front) is at a given temperature. Several examples demonstrate the capability of the approach.
Academic vs. Biological Age in Research on Academic Careers: A Large-scale Study with Implications for Scientifically Developing Systems
Venue: arXiv cs.DL 2023
Year: 2023

Biological age is an important sociodemographic factor in studies on academic careers (research productivity, scholarly impact, and collaboration patterns). It is assumed that the academic age, or the time elapsed from the first publication, is a good proxy for biological age. In this study, we analyze the limitations of the proxy in academic career studies, using as an example the entire population of Polish academic scientists visible in the last decade in global science and holding at least a PhD (N = 20,569). The proxy works well for science, technology, engineering, mathematics, and medicine (STEMM) disciplines; however, for non-STEMM disciplines (particularly for humanities and social sciences), it has a dramatically worse performance. This negative conclusion is particularly important for systems that have only become recently visible in global academic journals. The micro-level data suggest a delayed participation of social scientists and humanists in global science networks, with practical implications for predicting biological age from academic age. We calculate correlation coefficients, present contingency analysis of academic career stages with academic positions and age groups, and create a linear multivariate regression model. Our research suggests that in scientifically developing countries, academic age as a proxy for biological age should be used more cautiously than in advanced countries: ideally, it should be used only for STEMM disciplines.
Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems
Venue: arXiv cs.DS 2023
Year: 2023

We study nearly-linear time approximation algorithms for non-preemptive scheduling problems in two settings: the unrelated machine setting, and the identical machine with job precedence constraints setting, under the well-studied objectives such as makespan and weighted completion time. For many problems, we develop nearly-linear time approximation algorithms with approximation ratios matching the current best ones achieved in polynomial time. Our main technique is linear programming relaxation. For the unrelated machine setting, we formulate mixed packing and covering LP relaxations of nearly-linear size, and solve them approximately using the nearly-linear time solver of Young. For the makespan objective, we develop a rounding algorithm with $(2+ε)$-approximation ratio. For the weighted completion time objective, we prove the LP is as strong as the rectangle LP used by Im and Li, leading to a nearly-linear time $(1.45 + ε)$-approximation for the problem. For problems in the identical machine with precedence constraints setting, the precedence constraints can not be formulated as packing or covering constraints. To achieve the nearly-linear running time, we define a polytope for the constraints, and leverage the multiplicative weight update (MWU) method with an oracle which always returns solutions in the polytope.
Area Rate Efficiency in Multi-Link Molecular Communications
Venue: arXiv cs.IT 2023
Year: 2023

We consider a multi-link diffusion-based molecular communication (MC) system where multiple spatially distributed transmitter (TX)-receiver (RX) pairs establish point-to-point communication links employing the same type of signaling molecules. To exploit the full potential of such a system, an in-depth understanding of the interplay between the spatial link density and inter-link interference (ILI) and its impact on system performance is needed. In this paper, we consider a three-dimensional unbounded domain with multiple spatially distributed point-to-point non-cooperative transmission links, where both the TXs and RXs are positioned on a regular fixed grid. For this setup, we first derive an analytical expression for the channel impulse responses (CIRs) between the TXs and RXs in the system. Then, we derive the maximum likelihood (ML) detector for the RXs and show that it reduces to a threshold-based detector. Moreover, we derive an analytical expression for the corresponding detection threshold which depends on the statistics of the desired signal from the dedicated TX, the statistics of the MC channel, and the statistics of the ILI. Finally, we propose two new performance metrics, namely area rate efficiency (ARE) and area and time rate efficiency (ARTE), suitable for holistically evaluating spatially distributed multi-link MC systems. In particular, ARE and ARTE capture the tradeoff between transmission link density and achievable rate per link and the tradeoff between transmission link density, achievable rate per link, and inter-symbol interference (ISI), respectively. Hence, ARE and ARTE can be exploited to determine the optimal transmission link density for maximizing the throughput of the entire system.
Understanding the Generalization Benefit of Model Invariance from a Data Perspective
Venue: arXiv cs.LG 2023
Year: 2023

Machine learning models that are developed with invariance to certain types of data transformations have demonstrated superior generalization performance in practice. However, the underlying mechanism that explains why invariance leads to better generalization is not well-understood, limiting our ability to select appropriate data transformations for a given dataset. This paper studies the generalization benefit of model invariance by introducing the sample cover induced by transformations, i.e., a representative subset of a dataset that can approximately recover the whole dataset using transformations. Based on this notion, we refine the generalization bound for invariant models and characterize the suitability of a set of data transformations by the sample covering number induced by transformations, i.e., the smallest size of its induced sample covers. We show that the generalization bound can be tightened for suitable transformations that have a small sample covering number. Moreover, our proposed sample covering number can be empirically evaluated, providing a practical guide for selecting transformations to develop model invariance for better generalization. We evaluate the sample covering numbers for commonly used transformations on multiple datasets and demonstrate that the smaller sample covering number for a set of transformations indicates a smaller gap between the test and training error for invariant models, thus validating our propositions.
On the parameterized complexity of Compact Set Packing
Venue: arXiv cs.CC 2023
Year: 2023

The Set Packing problem is, given a collection of sets $\mathcal{S}$ over a ground set $\mathcal{U}$, to find a maximum collection of sets that are pairwise disjoint. The problem is among the most fundamental NP-hard optimization problems that have been studied extensively in various computational regimes. The focus of this work is on parameterized complexity, Parameterized Set Packing (PSP): Given $r \in {\mathbb N}$, is there a collection $ \mathcal{S}' \subseteq \mathcal{S}: |\mathcal{S}'| = r$ such that the sets in $\mathcal{S}'$ are pairwise disjoint? Unfortunately, the problem is not fixed parameter tractable unless $\mathsf{W[1] = FPT}$, and, in fact, an "enumeration" running time of $|\mathcal{S}|^{Ω(r)}$ is required unless the exponential time hypothesis (ETH) fails. This paper is a quest for tractable instances of Set Packing from parameterized complexity perspectives. We say that the input $(\mathcal{U},\mathcal{S})$ is "compact" if $|\mathcal{U}| = f(r)\cdotΘ(\textsf{poly}( \log |\mathcal{S}|))$, for some $f(r) \ge r$. In the Compact Set Packing problem, we are given a compact instance of PSP. In this direction, we present a "dichotomy" result of PSP: When $|\mathcal{U}| = f(r)\cdot o(\log |\mathcal{S}|)$, PSP is in $\textsf{FPT}$, while for $|\mathcal{U}| = r\cdotΘ(\log (|\mathcal{S}|))$, the problem is $W[1]$-hard; moreover, assuming ETH, Compact PSP does not even admit $|\mathcal{S}|^{o(r/\log r)}$ time algorithm. Although certain results in the literature imply hardness of compact versions of related problems such as Set $r$-Covering and Exact $r$-Covering, these constructions fail to extend to Compact PSP. A novel contribution of our work is the identification and construction of a gadget, which we call Compatible Intersecting Set System pair, that is crucial in obtaining the hardness result for Compact PSP.
Edge-Native Intelligence for 6G Communications Driven by Federated Learning: A Survey of Trends and Challenges
Venue: arXiv cs.NI 2023
Year: 2023

New technological advancements in wireless networks have enlarged the number of connected devices. The unprecedented surge of data volume in wireless systems empowered by artificial intelligence (AI) opens up new horizons for providing ubiquitous data-driven intelligent services. Traditional cloudcentric machine learning (ML)-based services are implemented by centrally collecting datasets and training models. However, this conventional training technique encompasses two challenges: (i) high communication and energy cost and (ii) threatened data privacy. In this article, we introduce a comprehensive survey of the fundamentals and enabling technologies of federated learning (FL), a newly emerging technique coined to bring ML to the edge of wireless networks. Moreover, an extensive study is presented detailing various applications of FL in wireless networks and highlighting their challenges and limitations. The efficacy of FL is further explored with emerging prospective beyond fifth-generation (B5G) and sixth-generation (6G) communication systems. This survey aims to provide an overview of the state-ofthe-art FL applications in key wireless technologies that will serve as a foundation to establish a firm understanding of the topic. Lastly, we offer a road forward for future research directions.
Combined Scaling for Zero-shot Transfer Learning
Venue: arXiv cs.LG 2023
Year: 2023

We present a combined scaling method - named BASIC - that achieves 85.7% top-1 accuracy on the ImageNet ILSVRC-2012 validation set without learning from any labeled ImageNet example. This accuracy surpasses best published similar models - CLIP and ALIGN - by 9.3%. Our BASIC model also shows significant improvements in robustness benchmarks. For instance, on 5 test sets with natural distribution shifts such as ImageNet-{A,R,V2,Sketch} and ObjectNet, our model achieves 84.3% top-1 average accuracy, only a small drop from its original ImageNet accuracy. To achieve these results, we scale up the contrastive learning framework of CLIP and ALIGN in three dimensions: data size, model size, and batch size. Our dataset has 6.6B noisy image-text pairs, which is 4x larger than ALIGN, and 16x larger than CLIP. Our largest model has 3B weights, which is 3.75x larger in parameters and 8x larger in FLOPs than ALIGN and CLIP. Finally, our batch size is 65536 which is 2x more than CLIP and 4x more than ALIGN. We encountered two main challenges with the scaling rules of BASIC. First, the main challenge with implementing the combined scaling rules of BASIC is the limited memory of accelerators, such as GPUs and TPUs. To overcome the memory limit, we propose two simple methods which make use of gradient checkpointing and model parallelism. Second, while increasing the dataset size and the model size has been the defacto method to improve the performance of deep learning models like BASIC, the effect of a large contrastive batch size on such contrastive-trained image-text models is not well-understood. To shed light on the benefits of large contrastive batch sizes, we develop a theoretical framework which shows that larger contrastive batch sizes lead to smaller generalization gaps for image-text models such as BASIC.
Sparsified Block Elimination for Directed Laplacians
Venue: arXiv cs.DS 2023
Year: 2023

We show that the sparsified block elimination algorithm for solving undirected Laplacian linear systems from [Kyng-Lee-Peng-Sachdeva-Spielman STOC'16] directly works for directed Laplacians. Given access to a sparsification algorithm that, on graphs with $n$ vertices and $m$ edges, takes time $\mathcal{T}_{\rm S}(m)$ to output a sparsifier with $\mathcal{N}_{\rm S}(n)$ edges, our algorithm solves a directed Eulerian system on $n$ vertices and $m$ edges to $ε$ relative accuracy in time $$ O(\mathcal{T}_{\rm S}(m) + {\mathcal{N}_{\rm S}(n)\log {n}\log(n/ε)}) + \tilde{O}(\mathcal{T}_{\rm S}(\mathcal{N}_{\rm S}(n)) \log n), $$ where the $\tilde{O}(\cdot)$ notation hides $\log\log(n)$ factors. By previous results, this implies improved runtimes for linear systems in strongly connected directed graphs, PageRank matrices, and asymmetric M-matrices. When combined with slower constructions of smaller Eulerian sparsifiers based on short cycle decompositions, it also gives a solver that runs in $O(n \log^{5}n \log(n / ε))$ time after $O(n^2 \log^{O(1)} n)$ pre-processing. At the core of our analyses are constructions of augmented matrices whose Schur complements encode error matrices.
DyFormer: A Scalable Dynamic Graph Transformer with Provable Benefits on Generalization Ability
Venue: arXiv cs.LG 2023
Year: 2023

Transformers have achieved great success in several domains, including Natural Language Processing and Computer Vision. However, its application to real-world graphs is less explored, mainly due to its high computation cost and its poor generalizability caused by the lack of enough training data in the graph domain. To fill in this gap, we propose a scalable Transformer-like dynamic graph learning method named Dynamic Graph Transformer (DyFormer) with spatial-temporal encoding to effectively learn graph topology and capture implicit links. To achieve efficient and scalable training, we propose temporal-union graph structure and its associated subgraph-based node sampling strategy. To improve the generalization ability, we introduce two complementary self-supervised pre-training tasks and show that jointly optimizing the two pre-training tasks results in a smaller Bayesian error rate via an information-theoretic analysis. Extensive experiments on the real-world datasets illustrate that DyFormer achieves a consistent 1%-3% AUC gain (averaged over all time steps) compared with baselines on all benchmarks.
Distinguishing Engagement Facets: An Essential Component for AI-based Interactive Healthcare
Venue: arXiv cs.HC 2023
Year: 2023

Engagement in Human-Machine Interaction is the process by which entities participating in the interaction establish, maintain, and end their perceived connection. It is essential to monitor the engagement state of patients in various AI-based interactive healthcare paradigms. This includes medical conditions that alter social behavior such as Autism Spectrum Disorder (ASD) or Attention-Deficit/Hyperactivity Disorder (ADHD). Engagement is a multi-faceted construct which is composed of behavioral, emotional, and mental components. Previous research has neglected this multi-faceted nature of engagement and focused on the detection of engagement level or binary engagement label. In this paper, a system is presented to distinguish these facets using contextual and relational features. This can facilitate further fine-grained analysis. Several machine learning classifiers including traditional and deep learning models are compared for this task. An F-Score of 0.74 was obtained on a balanced dataset of 22242 instances with neural network-based classification. The proposed framework shall serve as a baseline for further research on engagement facets recognition, and its integration is socially assistive robotic applications.
DABS: A Domain-Agnostic Benchmark for Self-Supervised Learning
Venue: arXiv cs.LG 2023
Year: 2023

Self-supervised learning algorithms, including BERT and SimCLR, have enabled significant strides in fields like natural language processing, computer vision, and speech processing. However, these algorithms are domain-specific, meaning that new self-supervised learning algorithms must be developed for each new setting, including myriad healthcare, scientific, and multimodal domains. To catalyze progress toward domain-agnostic methods, we introduce DABS: a Domain-Agnostic Benchmark for Self-supervised learning. To perform well on DABS, an algorithm is evaluated on seven diverse domains: natural images, multichannel sensor data, English text, speech recordings, multilingual text, chest x-rays, and images with text descriptions. Each domain contains an unlabeled dataset for pretraining; the model is then is scored based on its downstream performance on a set of labeled tasks in the domain. We also present e-Mix and ShED: two baseline domain-agnostic algorithms; their relatively modest performance demonstrates that significant progress is needed before self-supervised learning is an out-of-the-box solution for arbitrary domains. Code for benchmark datasets and baseline algorithms is available at https://github.com/alextamkin/dabs.