OpenRaiser/Intern-Atlas huggingface dataset:
Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
Venue: arXiv cs.DS 2023
Year: 2023

We investigate pseudopolynomial-time algorithms for Bounded Knapsack and Bounded Subset Sum. Recent years have seen a growing interest in settling their fine-grained complexity with respect to various parameters. For Bounded Knapsack, the number of items $n$ and the maximum item weight $w_{\max}$ are two of the most natural parameters that have been studied extensively in the literature. The previous best running time in terms of $n$ and $w_{\max}$ is $O(n + w^3_{\max})$ [Polak, Rohwedder, Wegrzycki '21]. There is a conditional lower bound of $O((n + w_{\max})^{2-o(1)})$ based on $(\min,+)$-convolution hypothesis [Cygan, Mucha, Wegrzycki, Wlodarczyk '17]. We narrow the gap significantly by proposing a $\tilde{O}(n + w^{12/5}_{\max})$-time algorithm. Note that in the regime where $w_{\max} \approx n$, our algorithm runs in $\tilde{O}(n^{12/5})$ time, while all the previous algorithms require $Ω(n^3)$ time in the worst case. For Bounded Subset Sum, we give two algorithms running in $\tilde{O}(nw_{\max})$ and $\tilde{O}(n + w^{3/2}_{\max})$ time, respectively. These results match the currently best running time for 0-1 Subset Sum. Prior to our work, the best running times (in terms of $n$ and $w_{\max}$) for Bounded Subset Sum is $\tilde{O}(n + w^{5/3}_{\max})$ [Polak, Rohwedder, Wegrzycki '21] and $\tilde{O}(n + μ_{\max}^{1/2}w_{\max}^{3/2})$ [implied by Bringmann '19 and Bringmann, Wellnitz '21], where $μ_{\max}$ refers to the maximum multiplicity of item weights.
Execution at RISC: Stealth JOP Attacks on RISC-V Applications
Venue: arXiv cs.CR 2023
Year: 2023

RISC-V is a recently developed open instruction set architecture gaining a lot of attention. To achieve a lasting security on these systems and design efficient countermeasures, a better understanding of vulnerabilities to novel and potential future attacks is mandatory. This paper demonstrates that RISC-V is sensible to Jump-Oriented Programming, a class of complex code-reuse attacks. We provide an analysis of new dispatcher gadgets we discovered, and show how they can be used together in order to build a stealth attack, bypassing existing protections. A proof-of-concept attack is implemented on an embedded web server compiled for RISC-V, in which we introduced a vulnerability, allowing an attacker to remotely read an arbitrary file from the host machine.
Safety Performance of Neural Networks in the Presence of Covariate Shift
Venue: arXiv cs.LG 2023
Year: 2023

Covariate shift may impact the operational safety performance of neural networks. A re-evaluation of the safety performance, however, requires collecting new operational data and creating corresponding ground truth labels, which often is not possible during operation. We are therefore proposing to reshape the initial test set, as used for the safety performance evaluation prior to deployment, based on an approximation of the operational data. This approximation is obtained by observing and learning the distribution of activation patterns of neurons in the network during operation. The reshaped test set reflects the distribution of neuron activation values as observed during operation, and may therefore be used for re-evaluating safety performance in the presence of covariate shift. First, we derive conservative bounds on the values of neurons by applying finite binning and static dataflow analysis. Second, we formulate a mixed integer linear programming (MILP) constraint for constructing the minimum set of data points to be removed in the test set, such that the difference between the discretized test and operational distributions is bounded. We discuss potential benefits and limitations of this constraint-based approach based on our initial experience with an implemented research prototype.
CarPatch: A Synthetic Benchmark for Radiance Field Evaluation on Vehicle Components
Venue: arXiv cs.CV 2023
Year: 2023

Neural Radiance Fields (NeRFs) have gained widespread recognition as a highly effective technique for representing 3D reconstructions of objects and scenes derived from sets of images. Despite their efficiency, NeRF models can pose challenges in certain scenarios such as vehicle inspection, where the lack of sufficient data or the presence of challenging elements (e.g. reflections) strongly impact the accuracy of the reconstruction. To this aim, we introduce CarPatch, a novel synthetic benchmark of vehicles. In addition to a set of images annotated with their intrinsic and extrinsic camera parameters, the corresponding depth maps and semantic segmentation masks have been generated for each view. Global and part-based metrics have been defined and used to evaluate, compare, and better characterize some state-of-the-art techniques. The dataset is publicly released at https://aimagelab.ing.unimore.it/go/carpatch and can be used as an evaluation guide and as a baseline for future work on this challenging topic.
An algorithm with improved complexity for pebble motion/multi-agent path finding on trees
Venue: arXiv cs.MA 2023
Year: 2023

The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT. We propose a simple and easy to implement procedure, which finds solutions of length O(knc + n^2), where n is the number of nodes, $k$ is the number of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n^3), which is equal to our result in the worst case, but does not capture the dependency on c and k.
Imperfect CSI: A Key Factor of Uncertainty to Over-the-Air Federated Learning
Venue: arXiv cs.IT 2023
Year: 2023

Over-the-air computation (AirComp) has recently been identified as a prominent technique to enhance communication efficiency of wireless federated learning (FL). This letter investigates the impact of channel state information (CSI) uncertainty at the transmitter on an AirComp enabled FL (AirFL) system with the truncated channel inversion strategy. To characterize the performance of the AirFL system, the weight divergence with respect to the ideal aggregation is analytically derived to evaluate learning performance loss. We explicitly reveal that the weight divergence deteriorates as $\mathcal{O}(1/ρ^2)$ as the level of channel estimation accuracy $ρ$ vanishes, and also has a decay rate of $\mathcal{O}(1/K^2)$ with the increasing number of participating devices, $K$. Building upon our analytical results, we formulate the channel truncation threshold optimization problem to adapt to different $ρ$, which can be solved optimally. Numerical results verify the analytical results and show that a lower truncation threshold is preferred with more accurate CSI.
Multiscale Video Pretraining for Long-Term Activity Forecasting
Venue: arXiv cs.CV 2023
Year: 2023

Long-term activity forecasting is an especially challenging research problem because it requires understanding the temporal relationships between observed actions, as well as the variability and complexity of human activities. Despite relying on strong supervision via expensive human annotations, state-of-the-art forecasting approaches often generalize poorly to unseen data. To alleviate this issue, we propose Multiscale Video Pretraining (MVP), a novel self-supervised pretraining approach that learns robust representations for forecasting by learning to predict contextualized representations of future video clips over multiple timescales. MVP is based on our observation that actions in videos have a multiscale nature, where atomic actions typically occur at a short timescale and more complex actions may span longer timescales. We compare MVP to state-of-the-art self-supervised video learning approaches on downstream long-term forecasting tasks including long-term action anticipation and video summary prediction. Our comprehensive experiments across the Ego4D and Epic-Kitchens-55/100 datasets demonstrate that MVP out-performs state-of-the-art methods by significant margins. Notably, MVP obtains a relative performance gain of over 20% accuracy in video summary forecasting over existing methods.
Stochastic Step-wise Feature Selection for Exponential Random Graph Models (ERGMs)
Venue: arXiv cs.SI 2023
Year: 2023

Statistical analysis of social networks provides valuable insights into complex network interactions across various scientific disciplines. However, accurate modeling of networks remains challenging due to the heavy computational burden and the need to account for observed network dependencies. Exponential Random Graph Models (ERGMs) have emerged as a promising technique used in social network modeling to capture network dependencies by incorporating endogenous variables. Nevertheless, using ERGMs poses multiple challenges, including the occurrence of ERGM degeneracy, which generates unrealistic and meaningless network structures. To address these challenges and enhance the modeling of collaboration networks, we propose and test a novel approach that focuses on endogenous variable selection within ERGMs. Our method aims to overcome the computational burden and improve the accommodation of observed network dependencies, thereby facilitating more accurate and meaningful interpretations of network phenomena in various scientific fields. We conduct empirical testing and rigorous analysis to contribute to the advancement of statistical techniques and offer practical insights for network analysis.
Visual Analytics for Understanding Draco's Knowledge Base
Venue: arXiv cs.GR 2023
Year: 2023

Draco has been developed as an automated visualization recommendation system formalizing design knowledge as logical constraints in ASP (Answer-Set Programming). With an increasing set of constraints and incorporated design knowledge, even visualization experts lose overview in Draco and struggle to retrace the automated recommendation decisions made by the system. Our paper proposes an Visual Analytics (VA) approach to visualize and analyze Draco's constraints. Our VA approach is supposed to enable visualization experts to accomplish identified tasks regarding the knowledge base and support them in better understanding Draco. We extend the existing data extraction strategy of Draco with a data processing architecture capable of extracting features of interest from the knowledge base. A revised version of the ASP grammar provides the basis for this data processing strategy. The resulting incorporated and shared features of the constraints are then visualized using a hypergraph structure inside the radial-arranged constraints of the elaborated visualization. The hierarchical categories of the constraints are indicated by arcs surrounding the constraints. Our approach is supposed to enable visualization experts to interactively explore the design rules' violations based on highlighting respective constraints or recommendations. A qualitative and quantitative evaluation of the prototype confirms the prototype's effectiveness and value in acquiring insights into Draco's recommendation process and design constraints.
FoodWise: Food Waste Reduction and Behavior Change on Campus with Data Visualization and Gamification
Venue: arXiv cs.HC 2023
Year: 2023

Food waste presents a substantial challenge with significant environmental and economic ramifications, and its severity on campus environments is of particular concern. In response to this, we introduce FoodWise, a dual-component system tailored to inspire and incentivize campus communities to reduce food waste. The system consists of a data storytelling dashboard that graphically displays food waste information from university canteens, coupled with a mobile web application that encourages users to log their food waste reduction actions and rewards active participants for their efforts. Deployed during a two-week food-saving campaign at The Hong Kong University of Science and Technology (HKUST) in March 2023, FoodWise engaged over 200 participants from the university community, resulting in the logging of over 800 daily food-saving actions. Feedback collected post-campaign underscores the system's efficacy in elevating user consciousness about food waste and prompting behavioral shifts towards a more sustainable campus. This paper also provides insights for enhancing our system, contributing to a broader discourse on sustainable campus initiatives.
Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems
Venue: arXiv cs.LG 2023
Year: 2023

For a real-world decision-making problem, the reward function often needs to be engineered or learned. A popular approach is to utilize human feedback to learn a reward function for training. The most straightforward way to do so is to ask humans to provide ratings for state-action pairs on an absolute scale and take these ratings as reward samples directly. Another popular way is to ask humans to rank a small set of state-action pairs by preference and learn a reward function from these preference data. Recently, preference-based methods have demonstrated substantial success in empirical applications such as InstructGPT. In this work, we develop a theoretical comparison between these human feedback approaches in offline contextual bandits and show how human bias and uncertainty in feedback modelings can affect the theoretical guarantees of these approaches. Through this, our results seek to provide a theoretical explanation for the empirical successes of preference-based methods from a modeling perspective.
Evaluating the Ripple Effects of Knowledge Editing in Language Models
Venue: arXiv cs.CL 2023
Year: 2023

Modern language models capture a large body of factual knowledge. However, some facts can be incorrectly induced or become obsolete over time, resulting in factually incorrect generations. This has led to the development of various editing methods that allow updating facts encoded by the model. Evaluation of these methods has primarily focused on testing whether an individual fact has been successfully injected, and if similar predictions for other subjects have not changed. Here we argue that such evaluation is limited, since injecting one fact (e.g. ``Jack Depp is the son of Johnny Depp'') introduces a ``ripple effect'' in the form of additional facts that the model needs to update (e.g.``Jack Depp is the sibling of Lily-Rose Depp''). To address this issue, we propose a novel set of evaluation criteria that consider the implications of an edit on related facts. Using these criteria, we then construct RippleEdits, a diagnostic benchmark of 5K factual edits, capturing a variety of types of ripple effects. We evaluate prominent editing methods on RippleEdits, showing that current methods fail to introduce consistent changes in the model's knowledge. In addition, we find that a simple in-context editing baseline obtains the best scores on our benchmark, suggesting a promising research direction for model editing.
A Systematic Survey of Prompt Engineering on Vision-Language Foundation Models
Venue: arXiv cs.CV 2023
Year: 2023

Prompt engineering is a technique that involves augmenting a large pre-trained model with task-specific hints, known as prompts, to adapt the model to new tasks. Prompts can be created manually as natural language instructions or generated automatically as either natural language instructions or vector representations. Prompt engineering enables the ability to perform predictions based solely on prompts without updating model parameters, and the easier application of large pre-trained models in real-world tasks. In past years, Prompt engineering has been well-studied in natural language processing. Recently, it has also been intensively studied in vision-language modeling. However, there is currently a lack of a systematic overview of prompt engineering on pre-trained vision-language models. This paper aims to provide a comprehensive survey of cutting-edge research in prompt engineering on three types of vision-language models: multimodal-to-text generation models (e.g. Flamingo), image-text matching models (e.g. CLIP), and text-to-image generation models (e.g. Stable Diffusion). For each type of model, a brief model summary, prompting methods, prompting-based applications, and the corresponding responsibility and integrity issues are summarized and discussed. Furthermore, the commonalities and differences between prompting on vision-language models, language models, and vision models are also discussed. The challenges, future directions, and research opportunities are summarized to foster future research on this topic.
Improved Solution Search Performance of Constrained MOEA/D Hybridizing Directional Mating and Local Mating
Venue: arXiv cs.NE 2023
Year: 2023

In this study, we propose an improvement to the direct mating method, a constraint handling approach for multi-objective evolutionary algorithms, by hybridizing it with local mating. Local mating selects another parent from the feasible solution space around the initially selected parent. The direct mating method selects the other parent along the optimal direction in the objective space after the first parent is selected, even if it is infeasible. It shows better exploration performance for constraint optimization problems with coupling NSGA-II, but requires several individuals along the optimal direction. Due to the lack of better solutions dominated by the optimal direction from the first parent, direct mating becomes difficult as the generation proceeds. To address this issue, we propose a hybrid method that uses local mating to select another parent from the neighborhood of the first selected parent, maintaining diversity around good solutions and helping the direct mating process. We evaluate the proposed method on three mathematical problems with unique Pareto fronts and two real-world applications. We use the generation histories of the averages and standard deviations of the hypervolumes as the performance evaluation criteria. Our investigation results show that the proposed method can solve constraint multi-objective problems better than existing methods while maintaining high diversity.
Software development in startup companies: A systematic mapping study
Venue: arXiv cs.SE 2023
Year: 2023

Context: Software startups are newly created companies with no operating history and fast in producing cutting-edge technologies. These companies develop software under highly uncertain conditions, tackling fast-growing markets under severe lack of resources. Therefore, software startups present an unique combination of characteristics which pose several challenges to software development activities. Objective: This study aims to structure and analyze the literature on software development in startup companies, determining thereby the potential for technology transfer and identifying software development work practices reported by practitioners and researchers. Method: We conducted a systematic mapping study, developing a classification schema, ranking the selected primary studies according their rigor and relevance, and analyzing reported software development work practices in startups. Results: A total of 43 primary studies were identified and mapped, synthesizing the available evidence on software development in startups. Only 16 studies are entirely dedicated to software development in startups, of which 10 result in a weak contribution (advice and implications (6); lesson learned (3); tool (1)). Nineteen studies focus on managerial and organizational factors. Moreover, only 9 studies exhibit high scientific rigor and relevance. From the reviewed primary studies, 213 software engineering work practices were extracted, categorized and analyzed. Conclusion: This mapping study provides the first systematic exploration of the state-of-art on software startup research. The existing body of knowledge is limited to a few high quality studies. Furthermore, the results indicate that software engineering work practices are chosen opportunistically, adapted and configured to provide value under the constrains imposed by the startup context.
SusTrainable: Promoting Sustainability as a Fundamental Driver in Software Development Training and Education. 2nd Teacher Training, January 23-27, 2023, Pula, Croatia. Revised lecture notes
Venue: arXiv cs.CY 2023
Year: 2023

This volume exhibits the revised lecture notes of the 2nd teacher training organized as part of the project Promoting Sustainability as a Fundamental Driver in Software Development Training and Education, held at the Juraj Dobrila University of Pula, Croatia, in the week January 23-27, 2023. It is the Erasmus+ project No. 2020-1-PT01-KA203-078646 - Sustrainable. More details can be found at the project web site https://sustrainable.github.io/ One of the most important contributions of the project are two summer schools. The 2nd SusTrainable Summer School (SusTrainable - 23) will be organized at the University of Coimbra, Portugal, in the week July 10-14, 2023. The summer school will consist of lectures and practical work for master and PhD students in computing science and closely related fields. There will be contributions from Babeş-Bolyai University, Eötvös Loránd University, Juraj Dobrila University of Pula, Radboud University Nijmegen, Roskilde University, Technical University of Košice, University of Amsterdam, University of Coimbra, University of Minho, University of Plovdiv, University of Porto, University of Rijeka. To prepare and streamline the summer school, the consortium organized a teacher training in Pula, Croatia. This was an event of five full days, organized by Tihana Galinac Grbac and Neven Grbac. The Juraj Dobrila University of Pula is very concerned with the sustainability issues. The education, research and management are conducted with sustainability goals in mind. The contributions in the proceedings were reviewed and provide a good overview of the range of topics that will be covered at the summer school. The papers in the proceedings, as well as the very constructive and cooperative teacher training, guarantee the highest quality and beneficial summer school for all participants.
RoboChop: Autonomous Framework for Fruit and Vegetable Chopping Leveraging Foundational Models
Venue: arXiv cs.RO 2023
Year: 2023

With the goal of developing fully autonomous cooking robots, developing robust systems that can chop a wide variety of objects is important. Existing approaches focus primarily on the low-level dynamics of the cutting action, which overlooks some of the practical real-world challenges of implementing autonomous cutting systems. In this work we propose an autonomous framework to sequence together action primitives for the purpose of chopping fruits and vegetables on a cluttered cutting board. We present a novel technique to leverage vision foundational models SAM and YOLO to accurately detect, segment, and track fruits and vegetables as they visually change through the sequences of chops, finetuning YOLO on a novel dataset of whole and chopped fruits and vegetables. In our experiments, we demonstrate that our simple pipeline is able to reliably chop a variety of fruits and vegetables ranging in size, appearance, and texture, meeting a variety of chopping specifications, including fruit type, number of slices, and types of slices.