OpenRaiser/Intern-Atlas huggingface dataset:
Prioritising Interactive Flows in Data Center Networks With Central Control
Venue: arXiv cs.NI 2023
Year: 2023

Data centers are on the rise and scientists are re-thinking and re-designing networks for data centers. The concept of central control which was not effective in the Internet era is now gaining popularity and is used in many data centers due to lower scale of operation (compared to Internet), structured topologies and as the entire network resources is under a single entity's control. With new opportunities, data center networks also pose new problems. Data centers require: high utilization, low median, tail latencies and fairness. In the traditional systems, the bulk traffic generally stalls the interactive flows thereby affecting their flow completion times adversely. In this thesis, we deal with two problems relating to central controller assisted prioritization of interactive flow in data center networks. Fastpass is a centralized "zero-queue" data center network. But the central arbiter of Fastpass doesn't scale well for more than 256 nodes (or 8 cores). In our test runs, it supports only about 1.5 Terabits's of network traffic. In this work, we re-design their timeslot allocator of their central arbiter so that it scales linearly till 12 cores and supports about 1024 nodes and 7.1 Terabits's of network traffic. In the second part of the thesis, we deal with the problem of congestion control in a software defined network. We propose a framework, where the controller with its global view of the network actively participates in the congestion control decisions of the end TCP hosts, by setting the ECN bits of IPV4 packets appropriately. Our framework can be deployed very easily without any change to the end node TCPs or the SDN switches. We also show 30x improvement over TCP cubic and 1.7x improvement over RED in flow completion times of interactive traffic for one implementation of this framework.
Universal Syntactic Structures: Modeling Syntax for Various Natural Languages
Venue: arXiv cs.CL 2023
Year: 2023

We aim to provide an explanation for how the human brain might connect words for sentence formation. A novel approach to modeling syntactic representation is introduced, potentially showing the existence of universal syntactic structures for all natural languages. As the discovery of DNA's double helix structure shed light on the inner workings of genetics, we wish to introduce a basic understanding of how language might work in the human brain. It could be the brain's way of encoding and decoding knowledge. It also brings some insight into theories in linguistics, psychology, and cognitive science. After looking into the logic behind universal syntactic structures and the methodology of the modeling technique, we attempt to analyze corpora that showcase universality in the language process of different natural languages such as English and Korean. Lastly, we discuss the critical period hypothesis, universal grammar, and a few other assertions on language for the purpose of advancing our understanding of the human brain.
Reinforcement learning based local path planning for mobile robot
Venue: arXiv cs.RO 2023
Year: 2023

Different methods are used for a mobile robot to go to a specific target location. These methods work in different ways for online and offline scenarios. In the offline scenario, an environment map is created once, and fixed path planning is made on this map to reach the target. Path planning algorithms such as A* and RRT (Rapidly-Exploring Random Tree) are the examples of offline methods. The most obvious situation here is the need to re-plan the path for changing conditions of the loaded map. On the other hand, in the online scenario, the robot moves dynamically to a given target without using a map by using the perceived data coming from the sensors. Approaches such as SFM (Social Force Model) are used in online systems. However, these methods suffer from the requirement of a lot of dynamic sensing data. Thus, it can be said that the need for re-planning and mapping in offline systems and various system design requirements in online systems are the subjects that focus on autonomous mobile robot research. Recently, deep neural network powered Q-Learning methods are used as an emerging solution to the aforementioned problems in mobile robot navigation. In this study, machine learning algorithms with deep Q-Learning (DQN) and Deep DQN architectures, are evaluated for the solution of the problems presented above to realize path planning of an autonomous mobile robot to avoid obstacles.
Predicting Confinement Effect of Carbon Fiber Reinforced Polymers on Strength of Concrete using Metaheuristics-based Artificial Neural Networks
Venue: arXiv cs.NE 2023
Year: 2023

This article deals with the study of predicting the confinement effect of carbon fiber reinforced polymers (CFRPs) on concrete cylinder strength using metaheuristics-based artificial neural networks. A detailed database of 708 CFRP confined concrete cylinders is developed from previously published research with information on 8 parameters including geometrical parameters like the diameter (d) and height (h) of a cylinder, unconfined compressive strength of concrete (fco'), thickness (nt), the elastic modulus of CFRP (Ef), unconfined concrete strain confined concrete strain and the ultimate compressive strength of confined concrete fcc'. Three metaheuristic models are implemented including particle swarm optimization (PSO), grey wolf optimizer (GWO), and bat algorithm (BA). These algorithms are trained on the data using an objective function of mean square error and their predicted results are validated against the experimental studies and finite element analysis. The study shows that the hybrid model of PSO predicted the strength of CFRP-confined concrete cylinders with maximum accuracy of 99.13% and GWO predicted the results with an accuracy of 98.17%. The high accuracy of axial compressive strength predictions demonstrated that these prediction models are a reliable solution to the empirical methods. The prediction models are especially suitable for avoiding full-scale time-consuming experimental tests that make the process quick and economical.
Variability-Aware Approximate Circuit Synthesis via Genetic Optimization
Venue: arXiv cs.AR 2023
Year: 2023

One of the major barriers that CMOS devices face at nanometer scale is increasing parameter variation due to manufacturing imperfections. Process variations severely inhibit the reliable operation of circuits, as the operational frequency at the nominal process corner is insufficient to suppress timing violations across the entire variability spectrum. To avoid variability-induced timing errors, previous efforts impose pessimistic and performance-degrading timing guardbands atop the operating frequency. In this work, we employ approximate computing principles and propose a circuit-agnostic automated framework for generating variability-aware approximate circuits that eliminate process-induced timing guardbands. Variability effects are accurately portrayed with the creation of variation-aware standard cell libraries, fully compatible with standard EDA tools. The underlying transistors are fully calibrated against industrial measurements from Intel 14nm FinFET in which both electrical characteristics of transistors and variability effects are accurately captured. In this work, we explore the design space of approximate variability-aware designs to automatically generate circuits of reduced variability and increased performance without the need for timing guardbands. Experimental results show that by introducing negligible functional error of merely $5.3\times 10^{-3}$, our variability-aware approximate circuits can be reliably operated under process variations without sacrificing the application performance.
TSDiT: Traffic Scene Diffusion Models With Transformers
Venue: arXiv cs.RO 2023
Year: 2023

In this paper, we introduce a novel approach to trajectory generation for autonomous driving, combining the strengths of Diffusion models and Transformers. First, we use the historical trajectory data for efficient preprocessing and generate action latent using a diffusion model with DiT(Diffusion with Transformers) Blocks to increase scene diversity and stochasticity of agent actions. Then, we combine action latent, historical trajectories and HD Map features and put them into different transformer blocks. Finally, we use a trajectory decoder to generate future trajectories of agents in the traffic scene. The method exhibits superior performance in generating smooth turning trajectories, enhancing the model's capability to fit complex steering patterns. The experimental results demonstrate the effectiveness of our method in producing realistic and diverse trajectories, showcasing its potential for application in autonomous vehicle navigation systems.
Beyond journals and peer review: towards a more flexible ecosystem for scholarly communication
Venue: arXiv cs.DL 2024
Year: 2024

This article challenges the assumption that journals and peer review are essential for developing,evaluating and disseminating scientific and other academic knowledge. It suggests a more flexible ecosystem, and examines some of the possibilities this might facilitate. The market for academic outputs should be opened up by encouraging the separation of the dissemination service from the evaluation service. Publishing research in subject-specific journals encourages compartmentalising research into rigid categories. The dissemination of knowledge would be better served by an open access, web-based repository system encompassing all disciplines. There would then be a role for organisations to assess the items in this repository to help users find relevant, high-quality work. There could be a variety of such organisations which could enable reviews from peers to be supplemented with evaluation by non-peers from a variety of different perspectives: user reviews, statistical reviews, reviews from the perspective of different disciplines, and so on. This should reduce the inevitably conservative influence of relying on two or three peers, and make the evaluation system more critical, multi-dimensional and responsive to the requirements of different audience groups, changing circumstances, and new ideas. Non-peer review might make it easier to challenge dominant paradigms, and expanding the potential audience beyond a narrow group of peers might encourage the criterion of simplicity to be taken more seriously - which is essential if human knowledge is to continue to progress. Keywords: Academic journals, Growth of knowledge, Non-peer review, Paradigm change, Peer review,Scholarly communication, Science communication, Simplicity.
Differentially Private Release and Learning of Threshold Functions
Venue: arXiv cs.CR 2024
Year: 2024

We prove new upper and lower bounds on the sample complexity of $(ε, δ)$ differentially private algorithms for releasing approximate answers to threshold functions. A threshold function $c_x$ over a totally ordered domain $X$ evaluates to $c_x(y) = 1$ if $y \le x$, and evaluates to $0$ otherwise. We give the first nontrivial lower bound for releasing thresholds with $(ε,δ)$ differential privacy, showing that the task is impossible over an infinite domain $X$, and moreover requires sample complexity $n \ge Ω(\log^*|X|)$, which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with $n \le 2^{(1+ o(1))\log^*|X|}$ samples. This improves the previous best upper bound of $8^{(1 + o(1))\log^*|X|}$ (Beimel et al., RANDOM '13). Our sample complexity upper and lower bounds also apply to the tasks of learning distributions with respect to Kolmogorov distance and of properly PAC learning thresholds with differential privacy. The lower bound gives the first separation between the sample complexity of properly learning a concept class with $(ε,δ)$ differential privacy and learning without privacy. For properly learning thresholds in $\ell$ dimensions, this lower bound extends to $n \ge Ω(\ell \cdot \log^*|X|)$. To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database $D$ of elements from $X$, the interior point problem asks for an element between the smallest and largest elements in $D$. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential privacy.
Autonomic Cloud Computing: Research Perspective
Venue: arXiv cs.DC 2024
Year: 2024

As the cloud infrastructure grows, it becomes more challenging to manage resources in such a massive, diverse, and distributed setting, despite the fact that cloud computing provides computational capabilities on-demand. Due to resource variability and unpredictability, resource allocation issues arise in a cloud setting. A Quality of Service (QoS) based autonomic resource management strategy automates resource management, delivering trustworthy, dependable, and cost-effective cloud services that efficiently execute workloads. Autonomic cloud computing aims to understand how computing systems may autonomously accomplish user-specified "control" objectives without the need for an administrator and without violating the Service Level Agreement (SLA) in a dynamic cloud computing environments. This chapter presents a research perspective and analysis on autonomic resource allocation in cloud computing based on the last decade of conducted research with a focus on QoS and SLA-aware autonomic resource management. This study delves into the current state of autonomic resource management in the cloud and introduces a conceptual model for Artificial Intelligence (AI)-driven autonomic cloud computing. This model aims to optimise server load distribution and energy consumption, thus enhancing cost savings and environmental impact. Finally, it highlights key next-generation research directions.
The Complexity of Drawing Graphs on Few Lines and Few Planes
Venue: arXiv cs.CC 2024
Year: 2024

It is well known that any graph admits a crossing-free straight-line drawing in $\mathbb{R}^3$ and that any planar graph admits the same even in $\mathbb{R}^2$. For a graph $G$ and $d \in \{2,3\}$, let $ρ^1_d(G)$ denote the smallest number of lines in $\mathbb{R}^d$ whose union contains a crossing-free straight-line drawing of $G$. For $d=2$, $G$ must be planar. Similarly, let $ρ^2_3(G)$ denote the smallest number of planes in $\mathbb{R}^3$ whose union contains a crossing-free straight-line drawing of $G$. We investigate the complexity of computing these three parameters and obtain the following hardness and algorithmic results. - For $d\in\{2,3\}$, we prove that deciding whether $ρ^1_d(G)\le k$ for a given graph $G$ and integer $k$ is ${\exists\mathbb{R}}$-complete. - Since $\mathrm{NP}\subseteq{\exists\mathbb{R}}$, deciding $ρ^1_d(G)\le k$ is NP-hard for $d\in\{2,3\}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$. - Since ${\exists\mathbb{R}}\subseteq\mathrm{PSPACE}$, both $ρ^1_2(G)$ and $ρ^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $ρ^1_2$ or $ρ^1_3$ sometimes require irrational coordinates. - We prove that deciding whether $ρ^2_3(G)\le k$ is NP-hard for any fixed $k \ge 2$. Hence, the problem is not fixed-parameter tractable with respect to $k$ unless $\mathrm{P}=\mathrm{NP}$.
XCSP3: An Integrated Format for Benchmarking Combinatorial Constrained Problems
Venue: arXiv cs.AI 2024
Year: 2024

We propose a major revision of the format XCSP 2.1, called XCSP3, to build integrated representations of combinatorial constrained problems. This new format is able to deal with mono/multi optimization, many types of variables, cost functions, reification, views, annotations, variable quantification, distributed, probabilistic and qualitative reasoning. The new format is made compact, highly readable, and rather easy to parse. Interestingly, it captures the structure of the problem models, through the possibilities of declaring arrays of variables, and identifying syntactic and semantic groups of constraints. The number of constraints is kept under control by introducing a limited set of basic constraint forms, and producing almost automatically some of their variations through lifting, restriction, sliding, logical combination and relaxation mechanisms. As a result, XCSP3 encompasses practically all constraints that can be found in major constraint solvers developed by the CP community. A website, which is developed conjointly with the format, contains many models and series of instances. The user can make sophisticated queries for selecting instances from very precise criteria. The objective of XCSP3 is to ease the effort required to test and compare different algorithms by providing a common test-bed of combinatorial constrained instances.
Post-Quantum Cryptography(PQC): Generalized ElGamal Cipher over GL(8,F251)
Venue: arXiv cs.CR 2024
Year: 2024

Post-quantum cryptography (PQC) attempts to find cryptographic protocols resistant to attacks using for instance Shor's polynomial time algorithm for numerical field problems like integer factorization (IFP) or the discrete logarithm (DLP). Other aspects are the backdoors discovered in deterministic random generators or recent advances in solving some instances of DLP. Using alternative algebraic structures like non-commutative or non-associative partial groupoids, magmas, monoids, semigroups, quasigroups or groups, are valid choices for these new protocols. This paper focuses on an asymmetric cipher based on a generalized ElGamal non-arbitrated protocol using a non-commutative general linear group. The developed protocol forces a hard subgroup membership search problem into a non-commutative structure. The protocol involves at first a generalized Diffie-Hellman key interchange and further on the private and public parameters are recursively updated each time a new cipher session is launched. Security is based on a hard variation of the Generalized Symmetric Decomposition Problem (GSDP). Working with GL(8, F251) 64-bit security is achieved, and if GL(16, F251) is chosen, the security rises to 127-bit. An appealing feature is that there is no need for big number libraries as all arithmetic is performed in Z_251. Therefore the new protocol is particularly useful for computational platforms with very limited capabilities like smartphones or smartcards.
Shift Aggregate Extract Networks
Venue: arXiv cs.LG 2024
Year: 2024

We introduce an architecture based on deep hierarchical decompositions to learn effective representations of large graphs. Our framework extends classic R-decompositions used in kernel methods, enabling nested part-of-part relations. Unlike recursive neural networks, which unroll a template on input graphs directly, we unroll a neural network template over the decomposition hierarchy, allowing us to deal with the high degree variability that typically characterize social network graphs. Deep hierarchical decompositions are also amenable to domain compression, a technique that reduces both space and time complexity by exploiting symmetries. We show empirically that our approach is able to outperform current state-of-the-art graph classification methods on large social network datasets, while at the same time being competitive on small chemobiological benchmark datasets.
Experiments of posture estimation on vehicles using wearable acceleration sensors
Venue: arXiv cs.HC 2024
Year: 2024

In this paper, we study methods to estimate drivers' posture in vehicles using acceleration data of wearable sensor and conduct a field test. Recently, sensor technologies have been progressed. Solutions of safety management to analyze vital data acquired from wearable sensor and judge work status are proposed. To prevent huge accidents, demands for safety management of bus and taxi are high. However, acceleration of vehicles is added to wearable sensor in vehicles, and there is no guarantee to estimate drivers' posture accurately. Therefore, in this paper, we study methods to estimate driving posture using acceleration data acquired from T-shirt type wearable sensor hitoe, conduct field tests and implement a sample application. Y. Yamato, "Experiments of Posture Estimation on Vehicles Using Wearable Acceleration Sensors," The 3rd IEEE International Conference on Big Data Security on Cloud (BigDataSecurity 2017), pp.14-17, DOI: 10.1109/BigDataSecurity.2017.8, May 2017. "(c) 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works."
Coalgebraic Behavioral Metrics
Venue: arXiv cs.LO 2024
Year: 2024

We study different behavioral metrics, such as those arising from both branching and linear-time semantics, in a coalgebraic setting. Given a coalgebra $α\colon X \to HX$ for a functor $H \colon \mathrm{Set}\to \mathrm{Set}$, we define a framework for deriving pseudometrics on $X$ which measure the behavioral distance of states. A crucial step is the lifting of the functor $H$ on $\mathrm{Set}$ to a functor $\overline{H}$ on the category $\mathrm{PMet}$ of pseudometric spaces. We present two different approaches which can be viewed as generalizations of the Kantorovich and Wasserstein pseudometrics for probability measures. We show that the pseudometrics provided by the two approaches coincide on several natural examples, but in general they differ. If $H$ has a final coalgebra, every lifting $\overline{H}$ yields in a canonical way a behavioral distance which is usually branching-time, i.e., it generalizes bisimilarity. In order to model linear-time metrics (generalizing trace equivalences), we show sufficient conditions for lifting distributive laws and monads. These results enable us to employ the generalized powerset construction.
Quantum Lovász Local Lemma: Shearer's Bound is Tight
Venue: arXiv cs.CC 2024
Year: 2024

The Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all bad events under some weakly dependent conditions. In a seminal paper, Ambainis, Kempe, and Sattath (JACM 2012) introduced a quantum version LLL (QLLL) which shows the possibility of avoiding all ``bad" Hamiltonians under some weakly dependent condition, and applied QLLL to the random k-QSAT problem. Sattath, Morampudi, Laumann, and Moessner (PNAS 2015) extended Ambainis, Kempe, and Sattath's result and showed that Shearer's bound is a sufficient condition for QLLL, and conjectured that Shearer's bound is indeed the tight condition for QLLL. In this paper, we affirm this conjecture. Precisely, we prove that Shearer's bound is tight for QLLL, i.e., the relative dimension of the smallest satisfying subspace is completely characterized by the independent set polynomial. Our result implies the tightness of Gilyén and Sattath's algorithm (FOCS 2017), and also implies that the lattice gas partition function fully characterizes quantum satisfiability for almost all Hamiltonians with large enough qudits (Sattath, Morampudi, Laumann and Moessner, PNAS 2015). The commuting LLL (CLLL), which focuses on commuting local Hamiltonians, is also investigated here. We prove that the tight regions of CLLL and QLLL are different in general. This result indicates that it is possible to design an algorithm for CLLL which is still efficient beyond Shearer's bound.