26838 research outputs found
Sort by
Connecting de Bruijn graphs
Get PDFWe study the problem of making a de Bruijn graph (dBG), constructed from a collection of strings, weakly connected while minimizing the total cost of edge additions. The input graph is a dBG that can be made weakly connected by adding edges (along with extra nodes if needed) from the underlying complete dBG. The problem arises from genome reconstruction, where the dBG is constructed from a set of sequences generated from a genome sample by a sequencing experiment. Due to sequencing errors, the dBG is never Eulerian in practice and is often not even weakly connected. We show the following results for a dBG G(V, E) of order k consisting of d weakly connected components: 1. Making G weakly connected by adding a set of edges of minimal total cost is NP-hard. 2. No PTAS exists for making G weakly connected by adding a set of edges of minimal total cost (unless the unique games conjecture fails). We complement this result by showing that there does exist a polynomial-time (2 − 2/d)-approximation algorithm for the problem. 3. We consider a restricted version of the above problem, where we are asked to make G weakly connected by only adding directed paths between pairs of components. We show that making G weakly connected by adding d− 1 such paths of minimal total cost can be done in O(k|V |α(|V |) + |E|) time, where α(·) is the inverse Ackermann function. This improves on the O(k|V | log(|V |) + |E|)-time algorithm proposed by Bernardini et al. [CPM 2022] for the same restricted problem. 4. An ILP formulation of polynomial size for making G Eulerian with minimal total cost
OpenIVM: A SQL-to-SQL compiler for Incremental Computations
Get PDFThis demonstration presents a new Open Source SQL-to-SQL compiler for Incremental View Maintenance (IVM). While previous systems, such as DBToaster, implemented computational functionality for IVM in a separate system, the core principle of OpenIVM is to make use of existing SQL query processing engines and perform all IVM computations via SQL. This approach enables the integration of IVM in these systems without code duplication. Also, it eases its use in cross-system IVM, i.e. to orchestrate an HTAP system in which one (OLTP) DBMS provides insertions/updates/deletes (deltas), which are propagated using SQL into another (OLAP) DBMS, hosting materialized views. Our system compiles view definitions into SQL to eventually propagate deltas into the table that materializes the view, following the principles of DBSP. Under the hood, OpenIVM uses the DuckDB library to compile (parse, transform, optimize) the materialized view maintenance logic. We demonstrate OpenIVM in action (i) as the core of a DuckDB extension module that adds IVM functionality to it and (ii) powering cross-system IVM for HTAP, with PostgreSQL handling updates on base tables and DuckDB hosting materialized views on these
Virtual mitigation of coherent non-adiabatic transitions by echo verification
Get PDFTransitions out of the ground space limit the performance of quantum adiabatic algorithms, while hardware imperfections impose stringent limitations on the circuit depth. We propose an adiabatic echo verification protocol which mitigates both coherent and incoherent errors, arising from non-adiabatic transitions and hardware noise, respectively. Quasiadiabatically evolving forward and backward allows for an echo-verified measurement of any observable. In addition to mitigating hardware noise, our method uses positive-time dynamics only. Crucially, the estimator bias of the observable is reduced when compared to standard adiabatic preparation, achieving up to a quadratic improvement
Noisy decoding by shallow circuits with parities: Classical and quantum (extended abstract)
Get PDFWe consider the problem of decoding corrupted error correcting codes with NC0[⊕] circuits in the
classical and quantum settings. We show that any such classical circuit can correctly recover only a
vanishingly small fraction of messages, if the codewords are sent over a noisy channel with positive
error rate. Previously this was known only for linear codes with large dual distance, whereas our
result applies to any code. By contrast, we give a simple quantum circuit that correctly decodes the
Hadamard code with probability Ω(ε2) even if a (1/2 − ε)-fraction of a codeword is adversarially
corrupted.
Our classical hardness result is based on an equidistribution phenomenon for multivariate
polynomials over a finite field under biased input-distributions. This is proved using a structure-
versus-randomness strategy based on a new notion of rank for high-dimensional polynomial maps
that may be of independent interest.
Our quantum circuit is inspired by a non-local version of the Bernstein-Vazirani problem, a
technique to generate “poor man’s cat states” by Watts et al., and a constant-depth quantum circuit
for the OR function by Takahashi and Tani
Cognitive biases in fact-checking and their countermeasures: A review
No full textThe increase of the amount of misinformation spread every day online is a huge threat to the society. Organizations and researchers are working to contrast this misinformation plague. In this setting, human assessors are indispensable to correctly identify, assess and/or revise the truthfulness of information items, i.e., to perform the fact-checking activity. Assessors, as humans, are subject to systematic errors that might interfere with their fact-checking activity. Among such errors, cognitive biases are those due to the limits of human cognition. Although biases help to minimize the cost of making mistakes, they skew assessments away from an objective perception of information. Cognitive biases, hence, are particularly frequent and critical, and can cause errors that have a huge potential impact as they propagate not only in the community, but also in the datasets used to train automatic and semi-automatic machine learning models to fight misinformation. In this work, we present a review of the cognitive biases which might occur during the fact-checking process. In more detail, inspired by PRISMA – a methodology used for systematic literature reviews – we manually derive a list of 221 cognitive biases that may affect human assessors. Then, we select the 39 biases that might manifest during the fact-checking process, we group them into categories, and we provide a description. Finally, we present a list of 11 countermeasures that can be adopted by researchers, practitioners, and organizations to limit the effect of the identified cognitive biases on the fact-checking activity
Sequential learning of the Pareto front for multi-objective bandits
Get PDFWe study the problem of sequential learning of the Pareto front in multi-objective multi-armed bandits. An agent is faced with ĸ possible arms to pull. At each turn she picks one, and receives a vector-valued reward. When she thinks she has enough information to identify the Pareto front of the different arm means, she stops the game and gives an answer. We are interested in designing algorithms such that the answer given is correct with probability at least 1−δ. Our main contribution is an efficient implementation of an algorithm achieving the optimal sample complexity when the risk δ is small. With ĸ arms in d dimensions p of which are in the Pareto set, the algorithm runs in time Ο(ĸpd) per round
Sequential value passing yields a Kleene theorem for processes
Get PDFCommunication with value passing has received ample attention in
process theory. Value passing through a sequential composition has received much
less attention. In recent work, we found that sequential value passing is the essen-
tial ingredient to prove the analogue of the classical theorem of the equivalence
of pushdown automata and context-free grammars in a setting of interactive pro-
cesses and bisimulation. Subsequently, we found that the treatment of sequential
value passing in the process setting can be simplified considerably. We report on
this simplification here, and find another application of sequential value passing,
viz. a Kleene theorem for processes
Foreword - MMVE 2024 - Proceedings of the 2024 16th International Workshop on Immersive Mixed and Virtual Environment Systems
No full textAn analysis of the ingredients for learning interpretable symbolic regression models with Human-in-The-loop and Genetic Programming
Get PDFInterpretability is a critical aspect to ensure a fair and responsible use of machine learning (ML) in high-stakes applications. Genetic programming (GP) has been used to obtain interpretable ML models because it operates at the level of functional building blocks: if these building blocks are interpretable, there is a chance that their composition (i.e., the entire ML model) is also interpretable. However, the degree to which a model is interpretable depends on the observer. Motivated by this, we study a recently-introduced human-in-The-loop system that allows the user to steer GP's generation process to their preferences, which shall be online-learned by an artificial neural network (ANN). We focus on the generation of ML models as analytical functions (i.e., symbolic regression) as this is a key problem in interpretable ML, and propose a two-fold contribution. First, we devise more general representations for the ML models for the ANN to learn upon, to enable the application of the system to a wider range of problems. Second, we delve into a deeper analysis of the system's components. To this end, we propose an incremental experimental evaluation, aimed at (1) studying the effectiveness by which an ANN can capture the perceived interpretability for simulated users, (2) investigating how the GP's outcome is affected across different simulated user feedback profiles, and (3) determining whether humans participants would prefer models that were generated with or without their involvement. Our results pose clarity on pros and cons of using a human-in-The-loop approach to discover interpretable ML models with GP