Showing 1–50 of 82 results for author: Levin, A

Towards Objective Obstetric Ultrasound Assessment: Contrastive Representation Learning for Fetal Movement Detection

Authors: Talha Ilyas, Duong Nhu, Allison Thomas, Arie Levin, Lim Wei Yap, Shu Gong, David Vera Anaya, Yiwen Jiang, Deval Mehta, Ritesh Warty, Vinayak Smith, Maya Reddy, Euan Wallace, Wenlong Cheng, Zongyuan Ge, Faezeh Marzbanrad

Abstract: Accurate fetal movement (FM) detection is essential for assessing prenatal health, as abnormal movement patterns can indicate underlying complications such as placental dysfunction or fetal distress. Traditional methods, including maternal perception and cardiotocography (CTG), suffer from subjectivity and limited accuracy. To address these challenges, we propose Contrastive Ultrasound Video Repre… ▽ More Accurate fetal movement (FM) detection is essential for assessing prenatal health, as abnormal movement patterns can indicate underlying complications such as placental dysfunction or fetal distress. Traditional methods, including maternal perception and cardiotocography (CTG), suffer from subjectivity and limited accuracy. To address these challenges, we propose Contrastive Ultrasound Video Representation Learning (CURL), a novel self-supervised learning framework for FM detection from extended fetal ultrasound video recordings. Our approach leverages a dual-contrastive loss, incorporating both spatial and temporal contrastive learning, to learn robust motion representations. Additionally, we introduce a task-specific sampling strategy, ensuring the effective separation of movement and non-movement segments during self-supervised training, while enabling flexible inference on arbitrarily long ultrasound recordings through a probabilistic fine-tuning approach. Evaluated on an in-house dataset of 92 subjects, each with 30-minute ultrasound sessions, CURL achieves a sensitivity of 78.01% and an AUROC of 81.60%, demonstrating its potential for reliable and objective FM analysis. These results highlight the potential of self-supervised contrastive learning for fetal movement analysis, paving the way for improved prenatal monitoring and clinical decision-making. △ Less

Submitted 23 October, 2025; originally announced October 2025.

Comments: This is the preprint version of the manuscript submitted to IEEE Journal of Biomedical and Health Informatics (JBHI) for review

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

Authors: Christoph Hunkenschröder, Martin Koutecký, Asaf Levin, Tung Anh Vu

Abstract: We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mathbf{b}, \, \mathbf{l} \leq \mathbf{x} \leq \mathbf{u}, \, \mathbf{x} \in \mathbb{Z}^n\}$. The number of variables $n$ is a variable part of the input, and we consider the regime where the constraint matrix $A$ has small… ▽ More We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mathbf{b}, \, \mathbf{l} \leq \mathbf{x} \leq \mathbf{u}, \, \mathbf{x} \in \mathbb{Z}^n\}$. The number of variables $n$ is a variable part of the input, and we consider the regime where the constraint matrix $A$ has small coefficients $\|A\|_\infty$ and small primal or dual treedepth $\mathrm{td}_P(A)$ or $\mathrm{td}_D(A)$, respectively. Equivalently, we consider block-structured matrices, in particular $n$-fold, tree-fold, $2$-stage and multi-stage matrices. We ask about the possibility of near-linear time algorithms in the general case of (non-linear) separable convex functions. The techniques of previous works for the linear case are inherently limited to it; in fact, no strongly-polynomial algorithm may exist due to a simple unconditional information-theoretic lower bound of $n \log \|\mathbf{u}-\mathbf{l}\|_\infty$, where $\mathbf{l}, \mathbf{u}$ are the vectors of lower and upper bounds. Our first result is that with parameters $\mathrm{td}_P(A)$ and $\|A\|_\infty$, this lower bound can be matched (up to dependency on the parameters). Second, with parameters $\mathrm{td}_D(A)$ and $\|A\|_\infty$, the situation is more involved, and we design an algorithm with time complexity $g(\mathrm{td}_D(A), \|A\|_\infty) n \log n \log \|\mathbf{u}-\mathbf{l}\|_\infty$ where $g$ is some computable function. We conjecture that a stronger lower bound is possible in this regime, and our algorithm is in fact optimal. Our algorithms combine ideas from scaling, proximity, and sensitivity of integer programs, together with a new dynamic data structure. △ Less

Submitted 28 May, 2025; originally announced May 2025.

Comments: 28 pages, will appear at IPCO 2025

Less Context, Same Performance: A RAG Framework for Resource-Efficient LLM-Based Clinical NLP

Authors: Satya Narayana Cheetirala, Ganesh Raut, Dhavalkumar Patel, Fabio Sanatana, Robert Freeman, Matthew A Levin, Girish N. Nadkarni, Omar Dawkins, Reba Miller, Randolph M. Steinhagen, Eyal Klang, Prem Timsina

Abstract: Long text classification is challenging for Large Language Models (LLMs) due to token limits and high computational costs. This study explores whether a Retrieval Augmented Generation (RAG) approach using only the most relevant text segments can match the performance of processing entire clinical notes with large context LLMs. We begin by splitting clinical documents into smaller chunks, convertin… ▽ More Long text classification is challenging for Large Language Models (LLMs) due to token limits and high computational costs. This study explores whether a Retrieval Augmented Generation (RAG) approach using only the most relevant text segments can match the performance of processing entire clinical notes with large context LLMs. We begin by splitting clinical documents into smaller chunks, converting them into vector embeddings, and storing these in a FAISS index. We then retrieve the top 4,000 words most pertinent to the classification query and feed these consolidated segments into an LLM. We evaluated three LLMs (GPT4o, LLaMA, and Mistral) on a surgical complication identification task. Metrics such as AUC ROC, precision, recall, and F1 showed no statistically significant differences between the RAG based approach and whole-text processing (p > 0.05p > 0.05). These findings indicate that RAG can significantly reduce token usage without sacrificing classification accuracy, providing a scalable and cost effective solution for analyzing lengthy clinical documents. △ Less

Submitted 23 May, 2025; originally announced May 2025.

Deformable Linear Object Surface Placement Using Elastica Planning and Local Shape Control

Authors: I. Grinberg, A. Levin, E. D. Rimon

Abstract: Manipulation of deformable linear objects (DLOs) in constrained environments is a challenging task. This paper describes a two-layered approach for placing DLOs on a flat surface using a single robot hand. The high-level layer is a novel DLO surface placement method based on Euler's elastica solutions. During this process one DLO endpoint is manipulated by the robot gripper while a variable interi… ▽ More Manipulation of deformable linear objects (DLOs) in constrained environments is a challenging task. This paper describes a two-layered approach for placing DLOs on a flat surface using a single robot hand. The high-level layer is a novel DLO surface placement method based on Euler's elastica solutions. During this process one DLO endpoint is manipulated by the robot gripper while a variable interior point of the DLO serves as the start point of the portion aligned with the placement surface. The low-level layer forms a pipeline controller. The controller estimates the DLO current shape using a Residual Neural Network (ResNet) and uses low-level feedback to ensure task execution in the presence of modeling and placement errors. The resulting DLO placement approach can recover from states where the high-level manipulation planner has failed as required by practical robot manipulation systems. The DLO placement approach is demonstrated with simulations and experiments that use silicon mock-up objects prepared for fresh food applications. △ Less

Submitted 11 March, 2025; originally announced March 2025.

Interpretable Early Warnings using Machine Learning in an Online Game-experiment

Authors: Guillaume Falmagne, Anna B. Stephenson, Simon A. Levin

Abstract: Stemming from physics and later applied to other fields such as ecology, the theory of critical transitions suggests that some regime shifts are preceded by statistical early warning signals. Reddit's r/place experiment, a large-scale social game, provides a unique opportunity to test these signals consistently across thousands of subsystems undergoing critical transitions. In r/place, millions of… ▽ More Stemming from physics and later applied to other fields such as ecology, the theory of critical transitions suggests that some regime shifts are preceded by statistical early warning signals. Reddit's r/place experiment, a large-scale social game, provides a unique opportunity to test these signals consistently across thousands of subsystems undergoing critical transitions. In r/place, millions of users collaboratively created ''compositions'', or pixel-art drawings, in which transitions occur when one composition rapidly replaces another. We develop a machine-learning-based early warning system that combines the predictive power of multiple system-specific time series via gradient-boosted decision trees with memory-retaining features. Our method significantly outperforms standard early warning indicators. Trained on the 2022 r/place data, our algorithm detects half of the transitions occurring within 20 min at a false positive rate of just 3.6%. Its performance remains robust when tested on the 2023 r/place event, demonstrating generalizability across different contexts. Using SHapley Additive exPlanations (SHAP) for interpreting the predictions, we investigate the underlying drivers of warnings, which could be relevant to other complex systems, especially online social systems. We reveal an interplay of patterns preceding transitions, such as critical slowing down or speeding up, a lack of innovation or coordination, turbulent histories, and a lack of image complexity. These findings show the potential of machine learning indicators in socio-ecological systems for predicting regime shifts and understanding their dynamics. △ Less

Submitted 19 March, 2026; v1 submitted 13 February, 2025; originally announced February 2025.

Journal ref: PNAS 123(1), e2503493122(2026)

Dual Arm Steering of Deformable Linear Objects in 2-D and 3-D Environments Using Euler's Elastica Solutions

Authors: Aharon Levin, Itay Grinberg, Elon Rimon, Amir Shapiro

Abstract: This paper describes a method for steering deformable linear objects using two robot hands in environments populated by sparsely spaced obstacles. The approach involves manipulating an elastic inextensible rod by varying the gripping endpoint positions and tangents. Closed form solutions that describe the flexible linear object shape in planar environments, Euler's elastica, are described. The pap… ▽ More This paper describes a method for steering deformable linear objects using two robot hands in environments populated by sparsely spaced obstacles. The approach involves manipulating an elastic inextensible rod by varying the gripping endpoint positions and tangents. Closed form solutions that describe the flexible linear object shape in planar environments, Euler's elastica, are described. The paper uses these solutions to formulate criteria for non self-intersection, stability and obstacle avoidance. These criteria are formulated as constraints in the flexible object six-dimensional configuration space that represents the robot gripping endpoint positions and tangents. In particular, this paper introduces a novel criterion that ensures the flexible object stability during steering. All safety criteria are integrated into a scheme for steering flexible linear objects in planar environments, which is lifted into a steering scheme in three-dimensional environments populated by sparsely spaced obstacles. Experiments with a dual-arm robot demonstrate the method. △ Less

Submitted 11 February, 2025; originally announced February 2025.

Better and Simpler Reducibility Bounds over the Integers

Authors: Asaf Levin

Abstract: We study the settings where we are given a function of n variables defined in a given box of integers. We show that in many cases we can replace the given objective function by a new function with a much smaller domain. Our approach allows us to transform a family of weakly polynomial time algorithms into strongly polynomial time algorithms. We study the settings where we are given a function of n variables defined in a given box of integers. We show that in many cases we can replace the given objective function by a new function with a much smaller domain. Our approach allows us to transform a family of weakly polynomial time algorithms into strongly polynomial time algorithms. △ Less

Submitted 29 January, 2025; originally announced January 2025.

MSC Class: 90C10

Steering Flexible Linear Objects in Planar Environments by Two Robot Hands Using Euler's Elastica Solutions

Authors: Aharon Levin, Elon Rimon, Amir Shapiro

Abstract: The manipulation of flexible objects such as cables, wires and fresh food items by robot hands forms a special challenge in robot grasp mechanics. This paper considers the steering of flexible linear objects in planar environments by two robot hands. The flexible linear object, modeled as an elastic non-stretchable rod, is manipulated by varying the gripping endpoint positions while keeping equal… ▽ More The manipulation of flexible objects such as cables, wires and fresh food items by robot hands forms a special challenge in robot grasp mechanics. This paper considers the steering of flexible linear objects in planar environments by two robot hands. The flexible linear object, modeled as an elastic non-stretchable rod, is manipulated by varying the gripping endpoint positions while keeping equal endpoint tangents. The flexible linear object shape has a closed form solution in terms of the grasp endpoint positions and tangents, called Euler's elastica. This paper obtains the elastica solutions under the optimal control framework, then uses the elastica solutions to obtain closed-form criteria for non self-intersection, stability and obstacle avoidance of the flexible linear object. The new tools are incorporated into a planning scheme for steering flexible linear objects in planar environments populated by sparsely spaced obstacles. The scheme is fully implemented and demonstrated with detailed examples. △ Less

Submitted 6 January, 2026; v1 submitted 6 January, 2025; originally announced January 2025.

Efficient approximation schemes for scheduling on a stochastic number of machines

Authors: Leah Epstein, Asaf Levin

Abstract: We study three two-stage optimization problems with a similar structure and different objectives. In the first stage of each problem, the goal is to assign input jobs of positive sizes to unsplittable bags. After this assignment is decided, the realization of the number of identical machines that will be available is revealed. Then, in the second stage, the bags are assigned to machines. The proba… ▽ More We study three two-stage optimization problems with a similar structure and different objectives. In the first stage of each problem, the goal is to assign input jobs of positive sizes to unsplittable bags. After this assignment is decided, the realization of the number of identical machines that will be available is revealed. Then, in the second stage, the bags are assigned to machines. The probability vector of the number of machines in the second stage is known to the algorithm as part of the input before making the decisions of the first stage. Thus, the vector of machine completion times is a random variable. The goal of the first problem is to minimize the expected value of the makespan of the second stage schedule, while the goal of the second problem is to maximize the expected value of the minimum completion time of the machines in the second stage solution. The goal of the third problem is to minimize the \ell_p norm for a fixed p>1, where the norm is applied on machines' completion times vectors. Each one of the first two problems admits a PTAS as Buchem et al. showed recently. Here we significantly improve all their results by designing an EPTAS for each one of these problems. We also design an EPTAS for \ell_p norm minimization for any p>1. △ Less

Submitted 16 September, 2024; originally announced September 2024.

Contrasting Deep Learning Models for Direct Respiratory Insufficiency Detection Versus Blood Oxygen Saturation Estimation

Authors: Marcelo Matheus Gauy, Natalia Hitomi Koza, Ricardo Mikio Morita, Gabriel Rocha Stanzione, Arnaldo Candido Junior, Larissa Cristina Berti, Anna Sara Shafferman Levin, Ester Cerdeira Sabino, Flaviane Romani Fernandes Svartman, Marcelo Finger

Abstract: We contrast high effectiveness of state of the art deep learning architectures designed for general audio classification tasks, refined for respiratory insufficiency (RI) detection and blood oxygen saturation (SpO$_2$) estimation and classification through automated audio analysis. Recently, multiple deep learning architectures have been proposed to detect RI in COVID patients through audio analys… ▽ More We contrast high effectiveness of state of the art deep learning architectures designed for general audio classification tasks, refined for respiratory insufficiency (RI) detection and blood oxygen saturation (SpO$_2$) estimation and classification through automated audio analysis. Recently, multiple deep learning architectures have been proposed to detect RI in COVID patients through audio analysis, achieving accuracy above 95% and F1-score above 0.93. RI is a condition associated with low SpO$_2$ levels, commonly defined as the threshold SpO$_2$ <92%. While SpO$_2$ serves as a crucial determinant of RI, a medical doctor's diagnosis typically relies on multiple factors. These include respiratory frequency, heart rate, SpO$_2$ levels, among others. Here we study pretrained audio neural networks (CNN6, CNN10 and CNN14) and the Masked Autoencoder (Audio-MAE) for RI detection, where these models achieve near perfect accuracy, surpassing previous results. Yet, for the regression task of estimating SpO$_2$ levels, the models achieve root mean square error values exceeding the accepted clinical range of 3.5% for finger oximeters. Additionally, Pearson correlation coefficients fail to surpass 0.3. As deep learning models perform better in classification than regression, we transform SpO$_2$-regression into a SpO$_2$-threshold binary classification problem, with a threshold of 92%. However, this task still yields an F1-score below 0.65. Thus, audio analysis offers valuable insights into a patient's RI status, but does not provide accurate information about actual SpO$_2$ levels, indicating a separation of domains in which voice and speech biomarkers may and may not be useful in medical diagnostics under current technologies. △ Less

Submitted 30 July, 2024; originally announced July 2024.

Comments: 23 pages, 4 figures, in review at Journal of Biomedical Signal Processing and Control

Towards Responsible Development of Generative AI for Education: An Evaluation-Driven Approach

Authors: Irina Jurenka, Markus Kunesch, Kevin R. McKee, Daniel Gillick, Shaojian Zhu, Sara Wiltberger, Shubham Milind Phal, Katherine Hermann, Daniel Kasenberg, Avishkar Bhoopchand, Ankit Anand, Miruna Pîslar, Stephanie Chan, Lisa Wang, Jennifer She, Parsa Mahmoudieh, Aliya Rysbek, Wei-Jen Ko, Andrea Huber, Brett Wiltshire, Gal Elidan, Roni Rabin, Jasmin Rubinovitz, Amit Pitaru, Mac McAllister , et al. (49 additional authors not shown)

Abstract: A major challenge facing the world is the provision of equitable and universal access to quality education. Recent advances in generative AI (gen AI) have created excitement about the potential of new technologies to offer a personal tutor for every learner and a teaching assistant for every teacher. The full extent of this dream, however, has not yet materialised. We argue that this is primarily… ▽ More A major challenge facing the world is the provision of equitable and universal access to quality education. Recent advances in generative AI (gen AI) have created excitement about the potential of new technologies to offer a personal tutor for every learner and a teaching assistant for every teacher. The full extent of this dream, however, has not yet materialised. We argue that this is primarily due to the difficulties with verbalising pedagogical intuitions into gen AI prompts and the lack of good evaluation practices, reinforced by the challenges in defining excellent pedagogy. Here we present our work collaborating with learners and educators to translate high level principles from learning science into a pragmatic set of seven diverse educational benchmarks, spanning quantitative, qualitative, automatic and human evaluations; and to develop a new set of fine-tuning datasets to improve the pedagogical capabilities of Gemini, introducing LearnLM-Tutor. Our evaluations show that LearnLM-Tutor is consistently preferred over a prompt tuned Gemini by educators and learners on a number of pedagogical dimensions. We hope that this work can serve as a first step towards developing a comprehensive educational evaluation framework, and that this can enable rapid progress within the AI and EdTech communities towards maximising the positive impact of gen AI in education. △ Less

Submitted 2 December, 2025; v1 submitted 21 May, 2024; originally announced July 2024.

APTAS for bin packing with general cost structures

Authors: G. Jaykrishnan, Asaf Levin

Abstract: We consider the following generalization of the bin packing problem. We are given a set of items each of which is associated with a rational size in the interval [0,1], and a monotone non-decreasing non-negative cost function f defined over the cardinalities of the subsets of items. A feasible solution is a partition of the set of items into bins subject to the constraint that the total size of it… ▽ More We consider the following generalization of the bin packing problem. We are given a set of items each of which is associated with a rational size in the interval [0,1], and a monotone non-decreasing non-negative cost function f defined over the cardinalities of the subsets of items. A feasible solution is a partition of the set of items into bins subject to the constraint that the total size of items in every bin is at most 1. Unlike bin packing, the goal function is to minimize the total cost of the bins where the cost of a bin is the value of f applied on the cardinality of the subset of items packed into the bin. We present an APTAS for this strongly NP-hard problem. We also provide a complete complexity classification of the problem with respect to the choice of f. △ Less

Submitted 10 July, 2024; originally announced July 2024.

MSC Class: 68W25 ACM Class: F.2.2

Discriminant audio properties in deep learning based respiratory insufficiency detection in Brazilian Portuguese

Authors: Marcelo Matheus Gauy, Larissa Cristina Berti, Arnaldo Cândido Jr, Augusto Camargo Neto, Alfredo Goldman, Anna Sara Shafferman Levin, Marcus Martins, Beatriz Raposo de Medeiros, Marcelo Queiroz, Ester Cerdeira Sabino, Flaviane Romani Fernandes Svartman, Marcelo Finger

Abstract: This work investigates Artificial Intelligence (AI) systems that detect respiratory insufficiency (RI) by analyzing speech audios, thus treating speech as a RI biomarker. Previous works collected RI data (P1) from COVID-19 patients during the first phase of the pandemic and trained modern AI models, such as CNNs and Transformers, which achieved $96.5\%$ accuracy, showing the feasibility of RI dete… ▽ More This work investigates Artificial Intelligence (AI) systems that detect respiratory insufficiency (RI) by analyzing speech audios, thus treating speech as a RI biomarker. Previous works collected RI data (P1) from COVID-19 patients during the first phase of the pandemic and trained modern AI models, such as CNNs and Transformers, which achieved $96.5\%$ accuracy, showing the feasibility of RI detection via AI. Here, we collect RI patient data (P2) with several causes besides COVID-19, aiming at extending AI-based RI detection. We also collected control data from hospital patients without RI. We show that the considered models, when trained on P1, do not generalize to P2, indicating that COVID-19 RI has features that may not be found in all RI types. △ Less

Submitted 27 May, 2024; originally announced May 2024.

Comments: 5 pages, 2 figures, 1 table. Published in Artificial Intelligence in Medicine (AIME) 2023

Journal ref: Artificial Intellingence in Medicine Proceedings 2023, page 271-275

Tight Lower Bounds for Block-Structured Integer Programs

Authors: Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, Asaf Levin

Abstract: We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their constraint matrix yields multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to… ▽ More We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their constraint matrix yields multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to ask whether this gap is inherent. We answer this question affirmative. Assuming the Exponential Time Hypothesis, we prove lower bounds showing that the exponential difference is necessary, and that the known algorithms are near optimal. Moreover, we prove unconditional lower bounds on the norms of the Graver basis, a fundamental building block of all known algorithms to solve these IPs. This shows that none of the current approaches can be improved beyond this bound. △ Less

Submitted 27 February, 2024; originally announced February 2024.

Social media battle for attention: opinion dynamics on competing networks

Authors: Andrea Somazzi, Giuseppe Maria Ferro, Diego Garlaschelli, Simon Asher Levin

Abstract: In the age of information abundance, attention is a coveted resource. Social media platforms vigorously compete for users' engagement, influencing the evolution of their opinions on a variety of topics. With recommendation algorithms often accused of creating "filter bubbles", where like-minded individuals interact predominantly with one another, it's crucial to understand the consequences of this… ▽ More In the age of information abundance, attention is a coveted resource. Social media platforms vigorously compete for users' engagement, influencing the evolution of their opinions on a variety of topics. With recommendation algorithms often accused of creating "filter bubbles", where like-minded individuals interact predominantly with one another, it's crucial to understand the consequences of this unregulated attention market. To address this, we present a model of opinion dynamics on a multiplex network. Each layer of the network represents a distinct social media platform, each with its unique characteristics. Users, as nodes in this network, share their opinions across platforms and decide how much time to allocate in each platform depending on its perceived quality. Our model reveals two key findings. i) When examining two platforms - one with a neutral recommendation algorithm and another with a homophily-based algorithm - we uncover that even if users spend the majority of their time on the neutral platform, opinion polarization can persist. ii) By allowing users to dynamically allocate their social energy across platforms in accordance to their homophilic preferences, a further segregation of individuals emerges. While network fragmentation is usually associated with "echo chambers", the emergent multi-platform segregation leads to an increase in users' satisfaction without the undesired increase in polarization. These results underscore the significance of acknowledging how individuals gather information from a multitude of sources. Furthermore, they emphasize that policy interventions on a single social media platform may yield limited impact. △ Less

Submitted 27 October, 2023; originally announced October 2023.

Comments: 13 pages, 7 figures

MSC Class: 9110 ACM Class: J.4; J.2

Rate-Induced Transitions in Networked Complex Adaptive Systems: Exploring Dynamics and Management Implications Across Ecological, Social, and Socioecological Systems

Authors: Vítor V. Vasconcelos, Flávia M. D. Marquitti, Theresa Ong, Lisa C. McManus, Marcus Aguiar, Amanda B. Campos, Partha S. Dutta, Kristen Jovanelly, Victoria Junquera, Jude Kong, Elisabeth H. Krueger, Simon A. Levin, Wenying Liao, Mingzhen Lu, Dhruv Mittal, Mercedes Pascual, Flávio L. Pinheiro, Juan Rocha, Fernando P. Santos, Peter Sloot, Chenyang, Su, Benton Taylor, Eden Tekwa, Sjoerd Terpstra , et al. (5 additional authors not shown)

Abstract: Complex adaptive systems (CASs), from ecosystems to economies, are open systems and inherently dependent on external conditions. While a system can transition from one state to another based on the magnitude of change in external conditions, the rate of change -- irrespective of magnitude -- may also lead to system state changes due to a phenomenon known as a rate-induced transition (RIT). This st… ▽ More Complex adaptive systems (CASs), from ecosystems to economies, are open systems and inherently dependent on external conditions. While a system can transition from one state to another based on the magnitude of change in external conditions, the rate of change -- irrespective of magnitude -- may also lead to system state changes due to a phenomenon known as a rate-induced transition (RIT). This study presents a novel framework that captures RITs in CASs through a local model and a network extension where each node contributes to the structural adaptability of others. Our findings reveal how RITs occur at a critical environmental change rate, with lower-degree nodes tipping first due to fewer connections and reduced adaptive capacity. High-degree nodes tip later as their adaptability sources (lower-degree nodes) collapse. This pattern persists across various network structures. Our study calls for an extended perspective when managing CASs, emphasizing the need to focus not only on thresholds of external conditions but also the rate at which those conditions change, particularly in the context of the collapse of surrounding systems that contribute to the focal system's resilience. Our analytical method opens a path to designing management policies that mitigate RIT impacts and enhance resilience in ecological, social, and socioecological systems. These policies could include controlling environmental change rates, fostering system adaptability, implementing adaptive management strategies, and building capacity and knowledge exchange. Our study contributes to the understanding of RIT dynamics and informs effective management strategies for complex adaptive systems in the face of rapid environmental change. △ Less

Submitted 14 September, 2023; originally announced September 2023.

Comments: 25 pages, 4 figures, 1 box, supplementary information

MSC Class: 37G; 37N; 91B; 91C; 91D; 91E; 92D; 92D25; 92D40; 92F; 93A; 93A14; 93A16 ACM Class: I.6.3; I.6.m; J.3; J.4; J.m; K.4.2

Global cognitive graph properties dynamics of hippocampal formation

Authors: Konstantin Sorokin, Andrey Zaitsew, Aleksandr Levin, German Magai, Maxim Beketov, Vladimir Sotskov

Abstract: In the present study we have used a set of methods and metrics to build a graph of relative neural connections in a hippocampus of a rodent. A set of graphs was built on top of time-sequenced data and analyzed in terms of dynamics of a connection genesis. The analysis has shown that during the process of a rodent exploring a novel environment, the relations between neurons constantly change which… ▽ More In the present study we have used a set of methods and metrics to build a graph of relative neural connections in a hippocampus of a rodent. A set of graphs was built on top of time-sequenced data and analyzed in terms of dynamics of a connection genesis. The analysis has shown that during the process of a rodent exploring a novel environment, the relations between neurons constantly change which indicates that globally memory is constantly updated even for known areas of space. Even if some neurons gain cognitive specialization, the global network though remains relatively stable. Additionally we suggest a set of methods for building a graph of cognitive neural network. △ Less

Submitted 7 August, 2023; originally announced August 2023.

Comments: 12 pages, 6 figures, paper for DAMDID 2023 Conference

Scheduling with cardinality dependent unavailability periods

Authors: G. Jaykrishnan, Asaf Levin

Abstract: We consider non-preemptive scheduling problems on parallel identical machines where machines change their status from being available to being unavailable and vice versa along the time horizon. The particular form of unavailability we consider is when the starting time of each downtime depends upon the cardinality of the job subset processed on that machine since the previous downtime. We consider… ▽ More We consider non-preemptive scheduling problems on parallel identical machines where machines change their status from being available to being unavailable and vice versa along the time horizon. The particular form of unavailability we consider is when the starting time of each downtime depends upon the cardinality of the job subset processed on that machine since the previous downtime. We consider the problem of minimizing the makespan in such scenarios as well as its dual problem where we have a fixed common deadline of $1$ and the goal is to minimize the number of machines for which there is a feasible schedule. We develop an EPTAS for the first variant and an AFPTAS for the second variant. △ Less

Submitted 19 June, 2023; originally announced June 2023.

MSC Class: 68W25 ACM Class: F.2.2

Passive Micron-scale Time-of-Flight with Sunlight Interferometry

Authors: Alankar Kotwal, Anat Levin, Ioannis Gkioulekas

Abstract: We introduce an interferometric technique for passive time-of-flight imaging and depth sensing at micrometer axial resolutions. Our technique uses a full-field Michelson interferometer, modified to use sunlight as the only light source. The large spectral bandwidth of sunlight makes it possible to acquire micrometer-resolution time-resolved scene responses, through a simple axial scanning operatio… ▽ More We introduce an interferometric technique for passive time-of-flight imaging and depth sensing at micrometer axial resolutions. Our technique uses a full-field Michelson interferometer, modified to use sunlight as the only light source. The large spectral bandwidth of sunlight makes it possible to acquire micrometer-resolution time-resolved scene responses, through a simple axial scanning operation. Additionally, the angular bandwidth of sunlight makes it possible to capture time-of-flight measurements insensitive to indirect illumination effects, such as interreflections and subsurface scattering. We build an experimental prototype that we operate outdoors, under direct sunlight, and in adverse environment conditions such as machine vibrations and vehicle traffic. We use this prototype to demonstrate, for the first time, passive imaging capabilities such as micrometer-scale depth sensing robust to indirect illumination, direct-only imaging, and imaging through diffusers. △ Less

Submitted 28 March, 2023; v1 submitted 19 November, 2022; originally announced November 2022.

Spreading Processes with Mutations over Multi-layer Networks

Authors: Mansi Sood, Anirudh Sridhar, Rashad Eletreby, Chai Wah Wu, Simon A. Levin, H. Vincent Poor, Osman Yagan

Abstract: A key scientific challenge during the outbreak of novel infectious diseases is to predict how the course of the epidemic changes under different countermeasures that limit interaction in the population. Most epidemiological models do not consider the role of mutations and heterogeneity in the type of contact events. However, pathogens have the capacity to mutate in response to changing environment… ▽ More A key scientific challenge during the outbreak of novel infectious diseases is to predict how the course of the epidemic changes under different countermeasures that limit interaction in the population. Most epidemiological models do not consider the role of mutations and heterogeneity in the type of contact events. However, pathogens have the capacity to mutate in response to changing environments, especially caused by the increase in population immunity to existing strains and the emergence of new pathogen strains poses a continued threat to public health. Further, in light of differing transmission risks in different congregate settings (e.g., schools and offices), different mitigation strategies may need to be adopted to control the spread of infection. We analyze a multi-layer multi-strain model by simultaneously accounting for i) pathways for mutations in the pathogen leading to the emergence of new pathogen strains, and ii) differing transmission risks in different congregate settings, modeled as network-layers. Assuming complete cross-immunity among strains, namely, recovery from any infection prevents infection with any other (an assumption that will need to be relaxed to deal with COVID-19 or influenza), we derive the key epidemiological parameters for the proposed multi-layer multi-strain framework. We demonstrate that reductions to existing network-based models that discount heterogeneity in either the strain or the network layers can lead to incorrect predictions for the course of the outbreak. In addition, our results highlight that the impact of imposing/lifting mitigation measures concerning different contact network layers (e.g., school closures or work-from-home policies) should be evaluated in connection with their effect on the likelihood of the emergence of new pathogen strains. △ Less

Submitted 24 January, 2023; v1 submitted 10 October, 2022; originally announced October 2022.

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?

Authors: Leonid A. Levin

Abstract: I discuss issues of inverting feasibly computable functions, optimal discovery algorithms, and the constant overheads in their performance. I discuss issues of inverting feasibly computable functions, optimal discovery algorithms, and the constant overheads in their performance. △ Less

Submitted 5 February, 2026; v1 submitted 19 September, 2022; originally announced September 2022.

Comments: 4 pages

MSC Class: 68Q17 ACM Class: F.2.2

Journal ref: Invited STOC-21 talk: http://acm-stoc.org/stoc2021/STOCprogram.html video: https://zenodo.org/records/18552463

Set Theory in the Foundation of Math; Internal Classes and External Sets

Authors: Leonid A. Levin

Abstract: Usual math sets have special types: countable, compact, open, occasionally Borel, rarely projective, etc. Each such set is described by a single Set Theory formula with parameters unrelated to other formulas. Exotic expressions involving sets related to formulas of unlimited quantifiers height appear mostly in esoteric or foundational studies. Recognizing internal to math (formula-specified) and… ▽ More Usual math sets have special types: countable, compact, open, occasionally Borel, rarely projective, etc. Each such set is described by a single Set Theory formula with parameters unrelated to other formulas. Exotic expressions involving sets related to formulas of unlimited quantifiers height appear mostly in esoteric or foundational studies. Recognizing internal to math (formula-specified) and external (based on parameters in those formulas) aspects of math objects greatly simplifies foundations. I postulate external sets (not internally specified, constituting the domain of variables) to be hereditarily countable and independent of formula-defined classes, i.e. with finite algorithmic information about them. This allows to eliminate all non-integer quantifiers in Set Theory sentences. All with seemingly no need to change almost anything in mathematical papers, only to reinterpret some formalities. △ Less

Submitted 31 March, 2026; v1 submitted 15 September, 2022; originally announced September 2022.

Comments: 6 pages article + 17 pages slides; talk video: https://doi.org/10.5281/zenodo.18626525

ACM Class: F.4.1

Gacs-Kucera Theorem

Authors: Leonid A. Levin

Abstract: Gacs-Kucera Theorem, tightened by Barmpalias and Lewis-Pye, w.t.t.-reduces each infinite sequence to a Kolmogorov--Martin-Lof random one and is broadly used in various Math and CS areas. Its early proofs are somewhat cumbersome, but using some general concepts yields significant simplification illustrated here. Gacs-Kucera Theorem, tightened by Barmpalias and Lewis-Pye, w.t.t.-reduces each infinite sequence to a Kolmogorov--Martin-Lof random one and is broadly used in various Math and CS areas. Its early proofs are somewhat cumbersome, but using some general concepts yields significant simplification illustrated here. △ Less

Submitted 6 July, 2022; originally announced July 2022.

Comments: 1 page. Theoretical Computer Science, 2022

Journal ref: Theoretical Computer Science, 929C, pp. 172-173, 2022

Swept-Angle Synthetic Wavelength Interferometry

Authors: Alankar Kotwal, Anat Levin, Ioannis Gkioulekas

Abstract: We present a new imaging technique, swept-angle synthetic wavelength interferometry, for full-field micron-scale 3D sensing. As in conventional synthetic wavelength interferometry, our technique uses light consisting of two narrowly-separated optical wavelengths, resulting in per-pixel interferometric measurements whose phase encodes scene depth. Our technique additionally uses a new type of light… ▽ More We present a new imaging technique, swept-angle synthetic wavelength interferometry, for full-field micron-scale 3D sensing. As in conventional synthetic wavelength interferometry, our technique uses light consisting of two narrowly-separated optical wavelengths, resulting in per-pixel interferometric measurements whose phase encodes scene depth. Our technique additionally uses a new type of light source that, by emulating spatially-incoherent illumination, makes interferometric measurements insensitive to aberrations and (sub)surface scattering, effects that corrupt phase measurements. The resulting technique combines the robustness to such corruptions of scanning interferometric setups, with the speed of full-field interferometric setups. Overall, our technique can recover full-frame depth at a lateral and axial resolution of 5 microns, at frame rates of 5 Hz, even under strong ambient light. We build an experimental prototype, and use it to demonstrate these capabilities by scanning a variety of objects, including objects representative of applications in inspection and fabrication, and objects that contain challenging light scattering effects. △ Less

Submitted 29 March, 2023; v1 submitted 21 May, 2022; originally announced May 2022.

EPTAS for the dual of splittable bin packing with cardinality constraint

Authors: G. Jaykrishnan, Asaf Levin

Abstract: The problem considered is the splittable bin packing with cardinality constraint. It is a variant of the bin packing problem where items are allowed to be split into parts but the number of parts in each bin is at most a given upper bound. Two versions of the splittable bin packing with cardinality constraint have been studied in the literature. Among these variants we consider the dual one where… ▽ More The problem considered is the splittable bin packing with cardinality constraint. It is a variant of the bin packing problem where items are allowed to be split into parts but the number of parts in each bin is at most a given upper bound. Two versions of the splittable bin packing with cardinality constraint have been studied in the literature. Among these variants we consider the dual one where the objective is to minimize the maximum bin size while packing (may be fractional) the items to a given set of bins. We exhibit an EPTAS for the dual problem when the cardinality upper bound is part of the input. This result answers an open question raised by Epstein, Levin, and van Stee. △ Less

Submitted 10 April, 2022; originally announced April 2022.

MSC Class: 90C27 ACM Class: F.2.2; G.2.1

The near exact bin covering problem

Authors: Asaf Levin

Abstract: We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant $Δ$, and we are given a set of items each of which has a positive size. We would like to find a partition of the items into bins. We say that a bin is near exact covered if the total size of items packed into the bin is between $1$ and… ▽ More We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant $Δ$, and we are given a set of items each of which has a positive size. We would like to find a partition of the items into bins. We say that a bin is near exact covered if the total size of items packed into the bin is between $1$ and $1+Δ$. Our goal is to maximize the number of near exact covered bins. If $Δ=0$ or $Δ>0$ is given as part of the input, our problem is shown here to have no approximation algorithm with a bounded asymptotic approximation ratio (assuming that $P\neq NP$). However, for the case where $Δ>0$ is seen as a constant, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) that is our main contribution. △ Less

Submitted 22 February, 2022; originally announced February 2022.

MSC Class: 68W25; 68W40 ACM Class: F.2.2; G.2.1

Cardinality Constrained Scheduling in Online Models

Authors: Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack, Lars Rohwedder

Abstract: Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham's famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is,… ▽ More Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham's famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is, the maximum machine load. In this paper, we consider the variant with an additional cardinality constraint: The algorithm may assign at most $k$ jobs to each machine where $k$ is part of the input. While the offline (strongly NP-hard) variant of cardinality constrained scheduling is well understood and an EPTAS exists here, no non-trivial results are known for the online variant. We fill this gap by making a comprehensive study of various different online models. First, we show that there is a constant competitive algorithm for the problem and further, present a lower bound of $2$ on the competitive ratio of any online algorithm. Motivated by the lower bound, we consider a semi-online variant where upon arrival of a job of size $p$, we are allowed to migrate jobs of total size at most a constant times $p$. This constant is called the migration factor of the algorithm. Algorithms with small migration factors are a common approach to bridge the performance of online algorithms and offline algorithms. One can obtain algorithms with a constant migration factor by rounding the size of each incoming job and then applying an ordinal algorithm to the resulting rounded instance. With this in mind, we also consider the framework of ordinal algorithms and characterize the competitive ratio that can be achieved using the aforementioned approaches. △ Less

Submitted 13 January, 2022; originally announced January 2022.

Comments: An extended abstract will appear in the proceedings of STACS'22

EPTAS for parallel identical machine scheduling with time restrictions

Authors: G. Jaykrishnan, Asaf Levin

Abstract: We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of B, and even the cas… ▽ More We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of B, and even the case of non-constant values of B on one machine was not known to admit a PTAS. △ Less

Submitted 12 November, 2021; originally announced November 2021.

MSC Class: 90C27 ACM Class: F.2.2; G.2.1

The Role of Masks in Mitigating Viral Spread on Networks

Authors: Yurun Tian, Anirudh Sridhar, Chai Wah Wu, Simon A. Levin, Kathleen M. Carley, H. Vincent Poor, Osman Yagan

Abstract: Masks have remained an important mitigation strategy in the fight against COVID-19 due to their ability to prevent the transmission of respiratory droplets between individuals. In this work, we provide a comprehensive quantitative analysis of the impact of mask-wearing. To this end, we propose a novel agent-based model of viral spread on networks where agents may either wear no mask or wear one of… ▽ More Masks have remained an important mitigation strategy in the fight against COVID-19 due to their ability to prevent the transmission of respiratory droplets between individuals. In this work, we provide a comprehensive quantitative analysis of the impact of mask-wearing. To this end, we propose a novel agent-based model of viral spread on networks where agents may either wear no mask or wear one of several types of masks with different properties (e.g., cloth or surgical). We derive analytical expressions for three key epidemiological quantities: the probability of emergence, the epidemic threshold, and the expected epidemic size. In particular, we show how the aforementioned quantities depend on the structure of the contact network, viral transmission dynamics, and the distribution of the different types of masks within the population. Through extensive simulations, we then investigate the impact of different allocations of masks within the population and trade-offs between the outward efficiency and inward efficiency of the masks. Interestingly, we find that masks with high outward efficiency and low inward efficiency are most useful for controlling the spread in the early stages of an epidemic, while masks with high inward efficiency but low outward efficiency are most useful in reducing the size of an already large spread. Lastly, we study whether degree-based mask allocation is more effective in reducing the probability of epidemic as well as epidemic size compared to random allocation. The result echoes the previous findings that mitigation strategies should differ based on the stage of the spreading process, focusing on source control before the epidemic emerges and on self-protection after the emergence. △ Less

Submitted 6 June, 2023; v1 submitted 8 October, 2021; originally announced October 2021.

Comments: Accepted at Physical Review E

EPTAS for load balancing problem on parallel machines with a non-renewable resource

Authors: G. Jaykrishnan, Asaf Levin

Abstract: The problem considered is the non-preemptive scheduling of independent jobs that consume a resource (which is non-renewable and replenished regularly) on parallel uniformly related machines. The input defines the speed of machines, size of jobs, the quantity of resource required by the jobs, the replenished quantities, and replenishment dates of the resource. Every job can start processing only af… ▽ More The problem considered is the non-preemptive scheduling of independent jobs that consume a resource (which is non-renewable and replenished regularly) on parallel uniformly related machines. The input defines the speed of machines, size of jobs, the quantity of resource required by the jobs, the replenished quantities, and replenishment dates of the resource. Every job can start processing only after the required quantity of the resource is allocated to the job. The objective function is the minimization of the convex combination of the makespan and an objective that is equivalent to the $l_p$-norm of the vector of loads of the machines. We present an EPTAS for this problem. Prior to our work only a PTAS was known in this non-renewable resource settings and this PTAS was only for the special case of our problem of makespan minimization on identical machines. △ Less

Submitted 9 August, 2021; originally announced August 2021.

Comments: An earlier extended abstract version appears in proceedings of WAOA'21

Challenges in cybersecurity: Lessons from biological defense systems

Authors: Edward Schrom, Ann Kinzig, Stephanie Forrest, Andrea L. Graham, Simon A. Levin, Carl T. Bergstrom, Carlos Castillo-Chavez, James P. Collins, Rob J. de Boer, Adam Doupé, Roya Ensafi, Stuart Feldman, Bryan T. Grenfell. Alex Halderman, Silvie Huijben, Carlo Maley, Melanie Mosesr, Alan S. Perelson, Charles Perrings, Joshua Plotkin, Jennifer Rexford, Mohit Tiwari

Abstract: We explore the commonalities between methods for assuring the security of computer systems (cybersecurity) and the mechanisms that have evolved through natural selection to protect vertebrates against pathogens, and how insights derived from studying the evolution of natural defenses can inform the design of more effective cybersecurity systems. More generally, security challenges are crucial for… ▽ More We explore the commonalities between methods for assuring the security of computer systems (cybersecurity) and the mechanisms that have evolved through natural selection to protect vertebrates against pathogens, and how insights derived from studying the evolution of natural defenses can inform the design of more effective cybersecurity systems. More generally, security challenges are crucial for the maintenance of a wide range of complex adaptive systems, including financial systems, and again lessons learned from the study of the evolution of natural defenses can provide guidance for the protection of such systems. △ Less

Submitted 21 July, 2021; originally announced July 2021.

Comments: 20 pages

MSC Class: A.0

Climbing LP Algorithms

Authors: Leonid A. Levin

Abstract: NP (search) problems allow easy correctness tests for solutions. Climbing algorithms allow also easy assessment of how close to yielding the correct answer is the configuration at any stage of their run. This offers a great flexibility, as how sensible is any deviation from the standard procedures can be instantly assessed. An example is the Dual Matrix Algorithm (DMA) for linear programming, va… ▽ More NP (search) problems allow easy correctness tests for solutions. Climbing algorithms allow also easy assessment of how close to yielding the correct answer is the configuration at any stage of their run. This offers a great flexibility, as how sensible is any deviation from the standard procedures can be instantly assessed. An example is the Dual Matrix Algorithm (DMA) for linear programming, variations of which were considered by A.Y. Levin in 1965 and by Yamnitsky and myself in 1982. It has little sensitivity to numerical errors and to the number of inequalities. It offers substantial flexibility and, thus, potential for further developments. △ Less

Submitted 23 April, 2021; v1 submitted 31 December, 2020; originally announced January 2021.

Comments: 2 pages. Significant additions

MSC Class: 90C05; 90C25 ACM Class: F.2.1; G.1.3

Journal ref: STOC 2021

More on ordered open end bin packing

Authors: János Balogh, Leah Epstein, Asaf Levin

Abstract: We consider the Ordered Open End Bin Packing problem. Items of sizes in $(0,1]$ are presented one by one, to be assigned to bins in this order. An item can be assigned to any bin for which the current total size strictly below $1$. This means also that the bin can be overloaded by its last packed item. We improve lower and upper bounds on the asymptotic competitive ratio in the online case. Specif… ▽ More We consider the Ordered Open End Bin Packing problem. Items of sizes in $(0,1]$ are presented one by one, to be assigned to bins in this order. An item can be assigned to any bin for which the current total size strictly below $1$. This means also that the bin can be overloaded by its last packed item. We improve lower and upper bounds on the asymptotic competitive ratio in the online case. Specifically, we design the first algorithm whose asymptotic competitive ratio is strictly below $2$ and it is close to the lower bound. This is in contrast to the best possible absolute approximation ratio, which is equal to $2$. We also study the offline problem where the sequence of items is known in advance, while items are still assigned to bins based on their order in the sequence. For this scenario we design an asymptotic polynomial time approximation scheme. △ Less

Submitted 14 October, 2020; originally announced October 2020.

Algorithms and Complexity for Variants of Covariates Fine Balance

Authors: Dorit S. Hochbaum, Asaf Levin, Xu Rao

Abstract: We study here several variants of the covariates fine balance problem where we generalize some of these problems and introduce a number of others. We present here a comprehensive complexity study of the covariates problems providing polynomial time algorithms, or a proof of NP-hardness. The polynomial time algorithms described are mostly combinatorial and rely on network flow techniques. In additi… ▽ More We study here several variants of the covariates fine balance problem where we generalize some of these problems and introduce a number of others. We present here a comprehensive complexity study of the covariates problems providing polynomial time algorithms, or a proof of NP-hardness. The polynomial time algorithms described are mostly combinatorial and rely on network flow techniques. In addition we present several fixed-parameter tractable results for problems where the number of covariates and the number of levels of each covariate are seen as a parameter. △ Less

Submitted 17 September, 2020; originally announced September 2020.

MSC Class: 05C85 ACM Class: F.2.2; G.2.1

Truly asymptotic lower bounds for online vector bin packing

Authors: Janos Balogh, Leah Epstein, Asaf Levin

Abstract: In this work, we consider online vector bin packing. It is known that no algorithm can have a competitive ratio of $o(d/\log^2 d)$ in the absolute sense, though upper bounds for this problem were always shown in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure and since the two measures are different, we focus on the asymptotic me… ▽ More In this work, we consider online vector bin packing. It is known that no algorithm can have a competitive ratio of $o(d/\log^2 d)$ in the absolute sense, though upper bounds for this problem were always shown in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds on the asymptotic competitive ratio. The existing lower bounds prior to this work were much smaller than $3$ even for very large dimensions. We significantly improve the best known lower bounds on the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with $d \geq 3$ dimensions, for every such dimension $d$. To obtain these results, we use several different constructions, one of which is an adaptive construction showing a lower bound of $Ω(\sqrt{d})$. Our main result is that the lower bound of $Ω(d/\log^2 d)$ on the competitive ratio holds also in the asymptotic sense. The last result requires a careful adaptation of constructions for online coloring rather than simple black-box reductions. △ Less

Submitted 3 August, 2020; originally announced August 2020.

Comments: Submitted to SODA 2021

Fundamentals of Computing

Authors: Leonid A. Levin

Abstract: These are notes for the course CS-172 I first taught in the Fall 1986 at UC Berkeley and subsequently at Boston University. The goal was to introduce the undergraduates to basic concepts of Theory of Computation and to provoke their interest in further study. Model-dependent effects were systematically ignored. Concrete computational problems were considered only as illustrations of general princi… ▽ More These are notes for the course CS-172 I first taught in the Fall 1986 at UC Berkeley and subsequently at Boston University. The goal was to introduce the undergraduates to basic concepts of Theory of Computation and to provoke their interest in further study. Model-dependent effects were systematically ignored. Concrete computational problems were considered only as illustrations of general principles. The notes are skeletal: they do have (terse) proofs, but exercises, references, intuitive comments, examples are missing or inadequate. The notes can be used for designing a course or by students who want to refresh the known material or are bright and have access to an instructor for questions. Each subsection takes about a week of the course. △ Less

Submitted 29 September, 2020; v1 submitted 13 May, 2020; originally announced May 2020.

Comments: 22 pages; extended

MSC Class: 68-01; 68Q; 03-01; 03D ACM Class: F.0; G.0

Journal ref: SIGACT News. 27(3):89-110, 1996

AIOps for a Cloud Object Storage Service

Authors: Anna Levin, Shelly Garion, Elliot K. Kolodner, Dean H. Lorenz, Katherine Barabash, Mike Kugler, Niall McShane

Abstract: With the growing reliance on the ubiquitous availability of IT systems and services, these systems become more global, scaled, and complex to operate. To maintain business viability, IT service providers must put in place reliable and cost efficient operations support. Artificial Intelligence for IT Operations (AIOps) is a promising technology for alleviating operational complexity of IT systems a… ▽ More With the growing reliance on the ubiquitous availability of IT systems and services, these systems become more global, scaled, and complex to operate. To maintain business viability, IT service providers must put in place reliable and cost efficient operations support. Artificial Intelligence for IT Operations (AIOps) is a promising technology for alleviating operational complexity of IT systems and services. AIOps platforms utilize big data, machine learning and other advanced analytics technologies to enhance IT operations with proactive actionable dynamic insight. In this paper we share our experience applying the AIOps approach to a production cloud object storage service to get actionable insights into system's behavior and health. We describe a real-life production cloud scale service and its operational data, present the AIOps platform we have created, and show how it has helped us resolving operational pain points. △ Less

Submitted 6 May, 2020; originally announced May 2020.

Comments: 5 pages

Journal ref: 2019 IEEE International Congress on Big Data (BigDataCongress)

Towards Occlusion-Aware Multifocal Displays

Authors: Jen-Hao Rick Chang, Anat Levin, B. V. K. Vijaya Kumar, Aswin C. Sankaranarayanan

Abstract: The human visual system uses numerous cues for depth perception, including disparity, accommodation, motion parallax and occlusion. It is incumbent upon virtual-reality displays to satisfy these cues to provide an immersive user experience. Multifocal displays, one of the classic approaches to satisfy the accommodation cue, place virtual content at multiple focal planes, each at a di erent depth.… ▽ More The human visual system uses numerous cues for depth perception, including disparity, accommodation, motion parallax and occlusion. It is incumbent upon virtual-reality displays to satisfy these cues to provide an immersive user experience. Multifocal displays, one of the classic approaches to satisfy the accommodation cue, place virtual content at multiple focal planes, each at a di erent depth. However, the content on focal planes close to the eye do not occlude those farther away; this deteriorates the occlusion cue as well as reduces contrast at depth discontinuities due to leakage of the defocus blur. This paper enables occlusion-aware multifocal displays using a novel ConeTilt operator that provides an additional degree of freedom -- tilting the light cone emitted at each pixel of the display panel. We show that, for scenes with relatively simple occlusion con gurations, tilting the light cones provides the same e ect as physical occlusion. We demonstrate that ConeTilt can be easily implemented by a phase-only spatial light modulator. Using a lab prototype, we show results that demonstrate the presence of occlusion cues and the increased contrast of the display at depth edges. △ Less

Submitted 2 May, 2020; originally announced May 2020.

Comments: SIGGRAPH 2020

Multitype Integer Monoid Optimization and Applications

Authors: Dušan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, Shmuel Onn

Abstract: Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems since the pioneering work of Gilmore and Gomory [Oper. Res., 1961]. Configuration IPs have a variable for each possible configuration, which describes a placement of items into a location, and whose value corresponds to the number of locations with that placement. In high multiplici… ▽ More Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems since the pioneering work of Gilmore and Gomory [Oper. Res., 1961]. Configuration IPs have a variable for each possible configuration, which describes a placement of items into a location, and whose value corresponds to the number of locations with that placement. In high multiplicity problems items come in types, and are represented succinctly by a vector of multiplicities; solving the configuration IP then amounts to deciding whether the input vector of multiplicities of items of each type can be decomposed into a given number of configurations. We make this implicit notion explicit by observing that the set of all input vectors decomposable into configurations forms a monoid, and solving the configuration IP is the Monoid Decomposition problem. Motivated by applications, we enrich this problem in two ways. First, sometimes each configuration additionally has an objective value, yielding an optimization problem of finding a "best" decomposition under the given objective. Second, there are often different types of configurations for different types of locations. The resulting problem is to optimize over decompositions of the input multiplicity vector into configurations of several types, and we call it Multitype Integer Monoid Optimization, or MIMO. We develop fast exact algorithms for various MIMO with few or many location types and with various objectives. Our algorithms build on a novel proximity theorem connecting the solutions of a certain configuration IP to those of its continuous relaxation. We then cast several fundamental scheduling and bin packing problems as MIMOs, and thereby obtain new or substantially faster algorithms for them. We complement our positive algorithmic results by hardness results. △ Less

Submitted 16 September, 2019; originally announced September 2019.

Approximation schemes for the generalized extensible bin packing problem

Authors: Asaf Levin

Abstract: We present a new generalization of the extensible bin packing with unequal bin sizes problem. In our generalization the cost of exceeding the bin size depends on the index of the bin and not only on the amount in which the size of the bin is exceeded. This generalization does not satisfy the assumptions on the cost function that were used to present the existing polynomial time approximation schem… ▽ More We present a new generalization of the extensible bin packing with unequal bin sizes problem. In our generalization the cost of exceeding the bin size depends on the index of the bin and not only on the amount in which the size of the bin is exceeded. This generalization does not satisfy the assumptions on the cost function that were used to present the existing polynomial time approximation scheme (PTAS) for the extensible bin packing with unequal bin sizes problem. In this work, we show the existence of an efficient PTAS (EPTAS) for this new generalization and thus in particular we improve the earlier PTAS for the extensible bin packing with unequal bin sizes problem into an EPTAS. Our new scheme is based on using the shifting technique followed by a solution of polynomial number of $n$-fold programming instances. In addition, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) for the related bin packing type variant of the problem. △ Less

Submitted 23 May, 2019; originally announced May 2019.

Online Bin Covering with Limited Migration

Authors: Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, Lars Rohwedder

Abstract: Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor $β$: When an object $o$ of size… ▽ More Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor $β$: When an object $o$ of size $s(o)$ arrives, the decisions for objects of total size at most $β\cdot s(o)$ may be revoked. Usually $β$ should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classic problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small $\eps$). We therefore resolve the competitiveness of the bin covering problem with migration. △ Less

Submitted 13 April, 2019; originally announced April 2019.

An Algorithmic Theory of Integer Programming

Authors: Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, Shmuel Onn

Abstract: We study the general integer programming problem where the number of variables $n$ is a variable part of the input. We consider two natural parameters of the constraint matrix $A$: its numeric measure $a$ and its sparsity measure $d$. We show that integer programming can be solved in time $g(a,d)\textrm{poly}(n,L)$, where $g$ is some computable function of the parameters $a$ and $d$, and $L$ is th… ▽ More We study the general integer programming problem where the number of variables $n$ is a variable part of the input. We consider two natural parameters of the constraint matrix $A$: its numeric measure $a$ and its sparsity measure $d$. We show that integer programming can be solved in time $g(a,d)\textrm{poly}(n,L)$, where $g$ is some computable function of the parameters $a$ and $d$, and $L$ is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by $a$ and $d$, and is solvable in polynomial time for every fixed $a$ and $d$. Our results also extend to nonlinear separable convex objective functions. Moreover, for linear objectives, we derive a strongly-polynomial algorithm, that is, with running time $g(a,d)\textrm{poly}(n)$, independent of the rest of the input data. We obtain these results by developing an algorithmic framework based on the idea of iterative augmentation: starting from an initial feasible solution, we show how to quickly find augmenting steps which rapidly converge to an optimum. A central notion in this framework is the Graver basis of the matrix $A$, which constitutes a set of fundamental augmenting steps. The iterative augmentation idea is then enhanced via the use of other techniques such as new and improved bounds on the Graver basis, rapid solution of integer programs with bounded variables, proximity theorems and a new proximity-scaling algorithm, the notion of a reduced objective function, and others. As a consequence of our work, we advance the state of the art of solving block-structured integer programs. In particular, we develop near-linear time algorithms for $n$-fold, tree-fold, and $2$-stage stochastic integer programs. We also discuss some of the many applications of these classes. △ Less

Submitted 29 July, 2022; v1 submitted 2 April, 2019; originally announced April 2019.

Comments: Revision 3: - corrections to specified complexities (infinite bounds, feasibility, etc.)

MSC Class: 15A; 52B; 52C; 68Q; 68R; 68W; 90B; 90C ACM Class: F.2.2; G.1.6

A Monte Carlo Framework for Rendering Speckle Statistics in Scattering Media

Authors: Chen Bar, Marina Alterman, Ioannis Gkioulekas, Anat Levin

Abstract: We present a Monte Carlo rendering framework for the physically-accurate simulation of speckle patterns arising from volumetric scattering of coherent waves. These noise-like patterns are characterized by strong statistical properties, such as the so-called memory effect, which are at the core of imaging techniques for applications as diverse as tissue imaging, motion tracking, and non-line-of-sig… ▽ More We present a Monte Carlo rendering framework for the physically-accurate simulation of speckle patterns arising from volumetric scattering of coherent waves. These noise-like patterns are characterized by strong statistical properties, such as the so-called memory effect, which are at the core of imaging techniques for applications as diverse as tissue imaging, motion tracking, and non-line-of-sight imaging. Our framework allows for these properties to be replicated computationally, in a way that is orders of magnitude more efficient than alternatives based on directly solving the wave equations. At the core of our framework is a path-space formulation for the covariance of speckle patterns arising from a scattering volume, which we derive from first principles. We use this formulation to develop two Monte Carlo rendering algorithms, for computing speckle covariance as well as directly speckle fields. While approaches based on wave equation solvers require knowing the microscopic position of wavelength-sized scatterers, our approach takes as input only bulk parameters describing the statistical distribution of these scatterers inside a volume. We validate the accuracy of our framework by comparing against speckle patterns simulated using wave equation solvers, use it to simulate memory effect observations that were previously only possible through lab measurements, and demonstrate its applicability for computational imaging tasks. △ Less

Submitted 21 January, 2019; originally announced January 2019.

Hypergraphic Degree Sequences are Hard

Authors: Antoine Deza, Asaf Levin, Syed M. Meesum, Shmuel Onn

Abstract: We show that deciding if a given vector is the degree sequence of a 3-hypergraph is NP-complete. We show that deciding if a given vector is the degree sequence of a 3-hypergraph is NP-complete. △ Less

Submitted 8 January, 2019; originally announced January 2019.

MSC Class: 05A; 15A; 51M; 52A; 52B; 52C; 62H; 68Q; 68R; 68U; 68W; 90B; 90C

Journal ref: Bulletin of the European Association for Theoretical Computer Science, 127:63-64, 2019

A new lower bound for classic online bin packing

Authors: János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin

Abstract: We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bound… ▽ More We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403. △ Less

Submitted 15 July, 2018; originally announced July 2018.

A unified framework for designing EPTAS's for load balancing on parallel machines

Authors: Ishai Kones, Asaf Levin

Abstract: We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in particular the makespan objective and the minimization… ▽ More We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in particular the makespan objective and the minimization of the $\ell_p$-norm of the vector of loads of the machines both with possibly job rejection. We consider this general model and design an efficient polynomial time approximation scheme (EPTAS) that applies for all its previously studied special cases. This EPTAS improves the current best approximation scheme for some of these cases where only a polynomial time approximation scheme (PTAS) was known into an EPTAS. △ Less

Submitted 27 February, 2018; originally announced February 2018.

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

Authors: Martin Koutecký, Asaf Levin, Shmuel Onn

Abstract: The theory of $n$-fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an $n$-fold integer program (IP) consists of parameter $A$, dimension $n$, and numerical data of binary encoding length $L$. It was known for some time that such programs can be solved in polynomial time using $O(n^{g(A)}L)$ arithmetic operations where $g$ is an expo… ▽ More The theory of $n$-fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an $n$-fold integer program (IP) consists of parameter $A$, dimension $n$, and numerical data of binary encoding length $L$. It was known for some time that such programs can be solved in polynomial time using $O(n^{g(A)}L)$ arithmetic operations where $g$ is an exponential function of the parameter. In 2013 it was shown that it can be solved in fixed-parameter tractable (FPT) time using $O(f(A)n^3L)$ arithmetic operations for a single-exponential function $f$. This, and a faster algorithm for a special case of combinatorial $n$-fold IP, have led to several very recent breakthroughs in the parameterized complexity of scheduling, stringology, and computational social choice. In 2015 it was shown that it can be solved in strongly polynomial time using $O(n^{g(A)})$ arithmetic operations. Here we establish a result which subsumes all three of the above results by showing that $n$-fold IP can be solved in strongly polynomial FPT time using $O(f(A)n^3)$ arithmetic operations. In fact, our results are much more general, briefly outlined as follows. - There is a strongly polynomial algorithm for ILP whenever a so-called Graver-best oracle is realizable for it. - Graver-best oracles for the large classes of multi-stage stochastic and tree-fold ILPs can be realized in FPT time. Together with the previous oracle algorithm, this newly shows two large classes of ILP to be strongly polynomial; in contrast, only few classes of ILP were previously known to be strongly polynomial. - We show that ILP is FPT parameterized by the largest coefficient $\|A\|_\infty$ and the primal or dual treedepth of $A$, and that this parameterization cannot be relaxed, signifying substantial progress in understanding the parameterized complexity of ILP. △ Less

Submitted 16 February, 2018; originally announced February 2018.

ACM Class: F.2.2; G.1.6

Mixing time estimation in reversible Markov chains from a single sample path

Authors: Daniel Hsu, Aryeh Kontorovich, David A. Levin, Yuval Peres, Csaba Szepesvári

Abstract: The spectral gap $γ$ of a finite, ergodic, and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix $P$ may be unknown, yet one sample of the chain up to a fixed time $n$ may be observed. We consider here the problem of estimating $γ$ from this data. Let $π$ be the stationary distribution of $P$, and… ▽ More The spectral gap $γ$ of a finite, ergodic, and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix $P$ may be unknown, yet one sample of the chain up to a fixed time $n$ may be observed. We consider here the problem of estimating $γ$ from this data. Let $π$ be the stationary distribution of $P$, and $π_\star = \min_x π(x)$. We show that if $n = \tilde{O}\bigl(\frac{1}{γπ_\star}\bigr)$, then $γ$ can be estimated to within multiplicative constants with high probability. When $π$ is uniform on $d$ states, this matches (up to logarithmic correction) a lower bound of $\tildeΩ\bigl(\frac{d}γ\bigr)$ steps required for precise estimation of $γ$. Moreover, we provide the first procedure for computing a fully data-dependent interval, from a single finite-length trajectory of the chain, that traps the mixing time $t_{\text{mix}}$ of the chain at a prescribed confidence level. The interval does not require the knowledge of any parameters of the chain. This stands in contrast to previous approaches, which either only provide point estimates, or require a reset mechanism, or additional prior knowledge. The interval is constructed around the relaxation time $t_{\text{relax}} = 1/γ$, which is strongly related to the mixing time, and the width of the interval converges to zero roughly at a $1/\sqrt{n}$ rate, where $n$ is the length of the sample path. △ Less

Submitted 24 August, 2017; originally announced August 2017.

Comments: 34 pages, merges results of arXiv:1506.02903 and arXiv:1612.05330

Lower bounds for several online variants of bin packing

Authors: János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin

Abstract: We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1.68 to above 1.75. We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1.68 to above 1.75. △ Less

Submitted 10 August, 2017; originally announced August 2017.

Comments: WAOA 2017

A new and improved algorithm for online bin packing

Authors: János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin

Abstract: We revisit the classic online bin packing problem. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called "bins" of total sizes no larger than 1, such that every item is assigned to a bin before the next item is presented. We use online partitioning of items into classes based on sizes, as in previous work, but we also apply a new method… ▽ More We revisit the classic online bin packing problem. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called "bins" of total sizes no larger than 1, such that every item is assigned to a bin before the next item is presented. We use online partitioning of items into classes based on sizes, as in previous work, but we also apply a new method where items of one class can be packed into more than two types of bins, where a bin type is defined according to the number of such items grouped together. Additionally, we allow the smallest class of items to be packed in multiple kinds of bins, and not only into their own bins. We combine this with the approach of packing of sufficiently big items according to their exact sizes. Finally, we simplify the analysis of such algorithms, allowing the analysis to be based on the most standard weight functions. This simplified analysis allows us to study the algorithm which we defined based on all these ideas. This leads us to the design and analysis of the first algorithm of asymptotic competitive ratio strictly below 1.58, specifically, we break this barrier and provide an algorithm AH (Advanced Harmonic) whose asymptotic competitive ratio does not exceed 1.5783. △ Less

Submitted 6 July, 2017; originally announced July 2017.