OpenRaiser/Intern-Atlas huggingface dataset:
Design, Configuration, Implementation, and Performance of a Simple 32 Core Raspberry Pi Cluster
Venue: arXiv cs.DC 2024
Year: 2024

In this report, I describe the design and implementation of an inexpensive, eight node, 32 core, cluster of raspberry pi single board computers, as well as the performance of this cluster on two computational tasks, one that requires significant data transfer relative to computational time requirements, and one that does not. We have two use-cases for the cluster: (a) as an educational tool for classroom usage, such as covering parallel algorithms in an algorithms course; and (b) as a test system for use during the development of parallel metaheuristics, essentially serving as a personal desktop parallel computing cluster. Our preliminary results show that the slow 100 Mbps networking of the raspberry pi significantly limits such clusters to parallel computational tasks that are either long running relative to data communications requirements, or that which requires very little internode communications. Additionally, although the raspberry pi 3 has a quad-core processor, parallel speedup degrades during attempts to utilize all four cores of all cluster nodes for a parallel computation, likely due to resource contention with operating system level processes. However, distributing a task across three cores of each cluster node does enable linear (or near linear) speedup.
Stability of the Lanczos Method for Matrix Function Approximation
Venue: arXiv cs.DS 2024
Year: 2024

The ubiquitous Lanczos method can approximate $f(A)x$ for any symmetric $n \times n$ matrix $A$, vector $x$, and function $f$. In exact arithmetic, the method's error after $k$ iterations is bounded by the error of the best degree-$k$ polynomial uniformly approximating $f(x)$ on the range $[λ_{min}(A), λ_{max}(A)]$. However, despite decades of work, it has been unclear if this powerful guarantee holds in finite precision. We resolve this problem, proving that when $\max_{x \in [λ_{min}, λ_{max}]}|f(x)| \le C$, Lanczos essentially matches the exact arithmetic guarantee if computations use roughly $\log(nC\|A\|)$ bits of precision. Our proof extends work of Druskin and Knizhnerman [DK91], leveraging the stability of the classic Chebyshev recurrence to bound the stability of any polynomial approximating $f(x)$. We also study the special case of $f(A) = A^{-1}$, where stronger guarantees hold. In exact arithmetic Lanczos performs as well as the best polynomial approximating $1/x$ at each of $A$'s eigenvalues, rather than on the full eigenvalue range. In seminal work, Greenbaum gives an approach to extending this bound to finite precision: she proves that finite precision Lanczos and the related CG method match any polynomial approximating $1/x$ in a tiny range around each eigenvalue [Gre89]. For $A^{-1}$, this bound appears stronger than ours. However, we exhibit matrices with condition number $κ$ where exact arithmetic Lanczos converges in $polylog(κ)$ iterations, but Greenbaum's bound predicts $Ω(κ^{1/5})$ iterations. It thus cannot offer significant improvement over the $O(κ^{1/2})$ bound achievable via our result. Our analysis raises the question of if convergence in less than $poly(κ)$ iterations can be expected in finite precision, even for matrices with clustered, skewed, or otherwise favorable eigenvalue distributions.
A Comprehensive Low and High-level Feature Analysis for Early Rumor Detection on Twitter
Venue: arXiv cs.SI 2024
Year: 2024

Recent work have done a good job in modeling rumors and detecting them over microblog streams. However, the performance of their automatic approaches are not relatively high when looking early in the diffusion. A first intuition is that, at early stage, most of the aggregated rumor features (e.g., propagation features) are not mature and distinctive enough. The objective of rumor debunking in microblogs, however, are to detect these misinformation as early as possible. In this work, we leverage neural models in learning the hidden representations of individual rumor-related tweets at the very beginning of a rumor. Our extensive experiments show that the resulting signal improves our classification performance over time, significantly within the first 10 hours. To deepen the understanding of these low and high-level features in contributing to the model performance over time, we conduct an extensive study on a wide range of high impact rumor features for the 48 hours range. The end model that engages these features are shown to be competitive, reaches over 90% accuracy and out-performs strong baselines in our carefully cured dataset.
Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
Venue: arXiv cs.CG 2024
Year: 2024

Visibility graph of a polygon corresponds to its internal diagonals and boundary edges. For each vertex on the boundary of the polygon, we have a vertex in this graph and if two vertices of the polygon see each other there is an edge between their corresponding vertices in the graph. Two vertices of a polygon see each other if and only if their connecting line segment completely lies inside the polygon, and they are externally visible if and only if this line segment completely lies outside the polygon. Recognizing visibility graphs is the problem of deciding whether there is a simple polygon whose visibility graph is isomorphic to a given input graph. This problem is well-known and well-studied, but yet widely open in geometric graphs and computational geometry. Existential Theory of the Reals is the complexity class of problems that can be reduced to the problem of deciding whether there exists a solution to a quantifier-free formula F(X1,X2,...,Xn), involving equalities and inequalities of real polynomials with real variables. The complete problems for this complexity class are called Existential Theory of the Reals Complete. In this paper we show that recognizing visibility graphs of polygons with holes is Existential Theory of the Reals Complete. Moreover, we show that recognizing visibility graphs of simple polygons when we have the internal and external visibility graphs, is also Existential Theory of the Reals Complete.
Boolean functions on high-dimensional expanders
Venue: arXiv cs.CC 2024
Year: 2024

We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high-dimensional expansion, which coincides with the earlier definition in terms of two-sided link expanders. Using this definition, we describe an analog of the Fourier expansion and the Fourier levels of the Boolean hypercube for simplicial complexes. Our analog is a decomposition into approximate eigenspaces of random walks associated with the simplicial complexes. Our random-walk definition and the decomposition have the additional advantage that they extend to the more general setting of posets, encompassing both high-dimensional expanders and the Grassmann poset, which appears in recent work on the unique games conjecture. We then use this decomposition to extend the Friedgut-Kalai-Naor theorem to high-dimensional expanders. Our results demonstrate that a constant-degree high-dimensional expander can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing only $|X(k-1)|=O(n)$ points in contrast to $\binom{n}{k}$ points in the $(k)$-slice (which consists of all $n$-bit strings with exactly $k$ ones).
Quantum Büchi Automata
Venue: arXiv cs.LO 2024
Year: 2024

Quantum finite automata (QFAs) have been extensively studied in the literature. In this paper, we define and systematically study quantum Büchi automata (QBAs) over infinite words to model the long-term behavior of quantum systems, which extend QFAs. We introduce the classes of $ω$-languages recognized by QBAs in probable, almost sure, strict and non-strict threshold semantics. Several pumping lemmas and closure properties for QBAs are proved. Some decision problems for QBAs are investigated. In particular, we show that there are surprisingly only at most four substantially different classes of $ω$-languages recognized by QBAs (out of uncountably infinite). The relationship between classical $ω$-languages and QBAs is clarified using our pumping lemmas. We also find an $ω$-language recognized by QBAs under the almost sure semantics, which is not $ω$-context-free.
An optimized KE-tableau-based system for reasoning in the description logic $\mathcal{DL}_{\mathbf{D}}^{4,\!\times}$ (Extended Version)
Venue: arXiv cs.LO 2024
Year: 2024

We present a KE-tableau-based procedure for the main TBox and ABox reasoning tasks for the description logic $\mathcal{DL}\langle \mathsf{4LQS^{R,\!\times}}\rangle(\mathbf{D})$, in short $\mathcal{DL}_{\mathbf{D}}^{4,\!\times}$. The logic $\mathcal{DL}_{\mathbf{D}}^{4,\!\times}$, representable in the decidable multi-sorted quantified set-theoretic fragment $\mathsf{4LQS^R}$, combines the high scalability and efficiency of rule languages such as the Semantic Web Rule Language (SWRL) with the expressivity of description logics. Our algorithm is based on a variant of the KE-tableau system for sets of universally quantified clauses, where the KE-elimination rule is generalized in such a way as to incorporate the $γ$-rule. The novel system, called KE$^γ$-tableau, turns out to be an improvement of the system introduced in \cite{RR2017} and of standard first-order KE-tableau \cite{dagostino94}. Suitable benchmark test sets executed on C++ implementations of the three mentioned systems show that the performances of the KE$^γ$-tableau-based reasoner are often up to about 400% better than the ones of the other two systems. This a first step towards the construction of efficient reasoners for expressive OWL ontologies based on fragments of computable set-theory.
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
Venue: arXiv cs.CC 2024
Year: 2024

$ \newcommand{\inparen}[1]{\left( #1 \right)} \newcommand{\pfrac}[2]{\inparen{\frac{1}{2}}} \newcommand{\ilog}[1]{\log^{\circ #1}} \newcommand{\F}{\mathbb{F}} $The Polynomial Identity Lemma (also called the "Schwartz--Zippel lemma") states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on any grid $S^n \subseteq \F^n$ with $|S| > s$. Thus, there is an explicit hitting set for all $n$-variate degree-$s$, size-$s$ algebraic circuits of size $(s+1)^n$. In this paper, we prove the following results: $\bullet$ Let $ε> 0$ be a constant. For a sufficiently large constant $n$, and all $s > n$, if we have an explicit hitting set of size $(s+1)^{n-ε}$ for the class of $n$-variate degree-$s$ polynomials that are computable by algebraic circuits of size $s$, then for all large $s$, we have an explicit hitting set of size $s^{\exp(\exp (O(\log^\ast s)))}$ for $s$-variate circuits of degree $s$ and size $s$. That is, if we can obtain a barely non-trivial exponent (a factor-$s^{Ω(1)} $ improvement) compared to the trivial $(s+1)^{n}$-size hitting set even for constant-variate circuits, we can get an almost complete derandomization of PIT. $\bullet$ The above result holds when "circuits" are replaced by "formulas" or "algebraic branching programs." This extends a recent surprising result of Agrawal, Ghosh and Saxena (STOC 2018, PNAS 2019) who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most $\inparen{s^{n^{0.5 - δ}}}$ (where $δ> 0$ is any constant). Hence, our work significantly weakens the hypothesis of Agrawal, Ghosh and Saxena to only require a slightly non-trivial saving over the trivial hitting set, and also presents the first such result for algebraic formulas.
Universal Proof Theory: Semi-analytic Rules and Craig Interpolation
Venue: arXiv cs.LO 2024
Year: 2024

We provide a general and syntactically-defined family of sequent calculi, called \emph{semi-analytic}, to formalize the informal notion of a "nice" sequent calculus. We show that any sufficiently strong (multimodal) substructural logic with a semi-analytic sequent calculus enjoys the Craig Interpolation Property, CIP. As a positive application, our theorem provides a uniform and modular method to prove the CIP for several multimodal substructural logics, including many fragments and variants of linear logic. More interestingly, on the negative side, it employs the lack of the CIP in almost all substructural, superintuitionistic and modal logics to provide a formal proof for the well-known intuition that almost all logics do not have a "nice" sequent calculus. More precisely, we show that many substructural logics including $\mathsf{UL^-}$, $\mathsf{MTL}$, $\mathsf{R}$, $\mathsf{L}_n$ (for $n \geq 3$), $\mathsf{G}_n$ (for $n \geq 4$), and almost all extensions of $\mathsf{IMTL}$, $\mathsf{L}$, $\mathsf{BL}$, $\mathsf{RM^e}$, $\mathsf{IPC}$, $\mathsf{S4}$, and $\mathsf{Grz}$, (except for at most 1, 1, 3, 8, 7, 37, and 6 of them, respectively) do not have a semi-analytic calculus. Keywords. Craig interpolation, sequent calculi, substructural logics, linear logics, subexponential modalities
Learning to Importance Sample in Primary Sample Space
Venue: arXiv cs.LG 2024
Year: 2024

Importance sampling is one of the most widely used variance reduction strategies in Monte Carlo rendering. In this paper, we propose a novel importance sampling technique that uses a neural network to learn how to sample from a desired density represented by a set of samples. Our approach considers an existing Monte Carlo rendering algorithm as a black box. During a scene-dependent training phase, we learn to generate samples with a desired density in the primary sample space of the rendering algorithm using maximum likelihood estimation. We leverage a recent neural network architecture that was designed to represent real-valued non-volume preserving ('Real NVP') transformations in high dimensional spaces. We use Real NVP to non-linearly warp primary sample space and obtain desired densities. In addition, Real NVP efficiently computes the determinant of the Jacobian of the warp, which is required to implement the change of integration variables implied by the warp. A main advantage of our approach is that it is agnostic of underlying light transport effects, and can be combined with many existing rendering techniques by treating them as a black box. We show that our approach leads to effective variance reduction in several practical scenarios.
Holistic generational offsets: Fostering a primitive online abstraction for human vs. machine cognition
Venue: arXiv cs.DC 2024
Year: 2024

We propose a unified architecture for next generation cognitive, low cost, mobile internet. The end user platform is able to scale as per the application and network requirements. It takes computing out of the data center and into end user platform. Internet enables open standards, accessible computing and applications programmability on a commodity platform. The architecture is a super-set to present day infrastructure web computing. The Java virtual machine (JVM) derives from the stack architecture. Applications can be developed and deployed on a multitude of host platforms. O(1) <-> O(N). Computing and the internet today are more accessible and available to the larger community. Machine learning has made extensive advances with the availability of modern computing. It is used widely in NLP, Computer Vision, Deep learning and AI. A prototype device for mobile could contain N compute and N MB of memory.
Unifying lower bounds for algebraic machines, semantically
Venue: arXiv cs.CC 2024
Year: 2024

This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological and measurable entropy for dynamical systems, it is shown to generalise three previous lower bounds results from the literature in algebraic complexity. We use it to prove that maxflow, a Ptime complete problem, is not computable in polylogarithmic time on parallel random access machines (prams) working with real numbers. This improves, albeit slightly, on a result of Mulmuley since the class of machines considered extends the class "prams without bit operations", making more precise the relationship between Mulmuley's result and similar lower bounds on real prams. More importantly, we show our method captures previous lower bounds results from the literature, thus providing a unifying framework for "topological" proofs of lower bounds: Steele and Yao's lower bounds for algebraic decision trees, Ben-Or's lower bounds for algebraic computation trees, Cucker's proof that NC is not equal to Ptime in the real case, and Mulmuley's lower bounds for "prams without bit operations".
MDU-Net: Multi-scale Densely Connected U-Net for biomedical image segmentation
Venue: arXiv cs.CV 2024
Year: 2024

Biomedical image segmentation plays a central role in quantitative analysis, clinical diagnosis, and medical intervention. In the light of the fully convolutional networks (FCN) and U-Net, deep convolutional networks (DNNs) have made significant contributions to biomedical image segmentation applications. In this paper, we propose three different multi-scale dense connections (MDC) for the encoder, the decoder of U-shaped architectures, and across them. Based on three dense connections, we propose a multi-scale densely connected U-Net (MDU-Net) for biomedical image segmentation. MDU-Net directly fuses the neighboring feature maps with different scales from both higher layers and lower layers to strengthen feature propagation in the current layer. Multi-scale dense connections, which contain shorter connections between layers close to the input and output, also make a much deeper U-Net possible. Besides, we introduce quantization to alleviate the potential overfitting in dense connections, and further improve the segmentation performance. We evaluate our proposed model on the MICCAI 2015 Gland Segmentation (GlaS) dataset. The three MDC improve U-Net performance by up to 1.8% on test A and 3.5% on test B in the MICCAI Gland dataset. Meanwhile, the MDU-Net with quantization obviously improves the segmentation performance of original U-Net.
Internet of Things Security, Device Authentication and Access Control: A Review
Venue: arXiv cs.CR 2024
Year: 2024

The Internet of Things (IoT) is one of the emerging technologies that has grabbed the attention of researchers from academia and industry. The idea behind Internet of things is the interconnection of internet enabled things or devices to each other and to humans, to achieve some common goals. In near future IoT is expected to be seamlessly integrated into our environment and human will be wholly solely dependent on this technology for comfort and easy life style. Any security compromise of the system will directly affect human life. Therefore security and privacy of this technology is foremost important issue to resolve. In this paper we present a thorough study of security problems in IoT and classify possible cyberattacks on each layer of IoT architecture. We also discuss challenges to traditional security solutions such as cryptographic solutions, authentication mechanisms and key management in IoT. Device authentication and access controls is an essential area of IoT security, which is not surveyed so far. We spent our efforts to bring the state of the art device authentication and access control techniques on a single paper.
NeurAll: Towards a Unified Visual Perception Model for Automated Driving
Venue: arXiv cs.CV 2024
Year: 2024

Convolutional Neural Networks (CNNs) are successfully used for the important automotive visual perception tasks including object recognition, motion and depth estimation, visual SLAM, etc. However, these tasks are typically independently explored and modeled. In this paper, we propose a joint multi-task network design for learning several tasks simultaneously. Our main motivation is the computational efficiency achieved by sharing the expensive initial convolutional layers between all tasks. Indeed, the main bottleneck in automated driving systems is the limited processing power available on deployment hardware. There is also some evidence for other benefits in improving accuracy for some tasks and easing development effort. It also offers scalability to add more tasks leveraging existing features and achieving better generalization. We survey various CNN based solutions for visual perception tasks in automated driving. Then we propose a unified CNN model for the important tasks and discuss several advanced optimization and architecture design techniques to improve the baseline model. The paper is partly review and partly positional with demonstration of several preliminary results promising for future research. We first demonstrate results of multi-stream learning and auxiliary learning which are important ingredients to scale to a large multi-task model. Finally, we implement a two-stream three-task network which performs better in many cases compared to their corresponding single-task models, while maintaining network size.
Deep Learning in Cardiology
Venue: arXiv cs.CV 2024
Year: 2024

The medical field is creating large amount of data that physicians are unable to decipher and use efficiently. Moreover, rule-based expert systems are inefficient in solving complicated medical tasks or for creating insights using big data. Deep learning has emerged as a more accurate and effective technology in a wide range of medical problems such as diagnosis, prediction and intervention. Deep learning is a representation learning method that consists of layers that transform the data non-linearly, thus, revealing hierarchical relationships and structures. In this review we survey deep learning application papers that use structured data, signal and imaging modalities from cardiology. We discuss the advantages and limitations of applying deep learning in cardiology that also apply in medicine in general, while proposing certain directions as the most viable for clinical use.
Albatross: An optimistic consensus algorithm
Venue: arXiv cs.CR 2024
Year: 2024

The consensus protocol is a critical component of distributed ledgers and blockchains. Achieving consensus over a decentralized network poses challenges to transaction finality and performance. Currently, the highest-performing consensus algorithms are speculative BFT algorithms, which, however, compromise on the transaction finality guarantees offered by their non-speculative counterparts. In this paper, we introduce Albatross, a Proof-of-Stake (PoS) blockchain consensus algorithm that aims to combine the best of both worlds. At its heart, Albatross is a high-performing, speculative BFT algorithm that offers strong probabilistic finality. We complement this by periodically guaranteeing finality through the Tendermint protocol. We prove our protocol to be secure under standard BFT assumptions and analyze its performance both on a theoretical and practical level. For that, we provide an open-source Rust implementation of Albatross. Our real-world measurements support that our protocol has a performance close to the theoretical maximum for single-chain Proof-of-Stake consensus algorithms.
A Simple Joint Model for Improved Contextual Neural Lemmatization
Venue: arXiv cs.CL 2024
Year: 2024

English verbs have multiple forms. For instance, talk may also appear as talks, talked or talking, depending on the context. The NLP task of lemmatization seeks to map these diverse forms back to a canonical one, known as the lemma. We present a simple joint neural model for lemmatization and morphological tagging that achieves state-of-the-art results on 20 languages from the Universal Dependencies corpora. Our paper describes the model in addition to training and decoding procedures. Error analysis indicates that joint morphological tagging and lemmatization is especially helpful in low-resource lemmatization and languages that display a larger degree of morphological complexity. Code and pre-trained models are available at https://sigmorphon.github.io/sharedtasks/2019/task2/.