Showing 1–22 of 22 results for author: Barbosa, A

Controlling Chaos Using Edge Computing Hardware

Authors: Robert M. Kent, Wendson A. S. Barbosa, Daniel J. Gauthier

Abstract: Machine learning provides a data-driven approach for creating a digital twin of a system - a digital model used to predict the system behavior. Having an accurate digital twin can drive many applications, such as controlling autonomous systems. Often the size, weight, and power consumption of the digital twin or related controller must be minimized, ideally realized on embedded computing hardware… ▽ More Machine learning provides a data-driven approach for creating a digital twin of a system - a digital model used to predict the system behavior. Having an accurate digital twin can drive many applications, such as controlling autonomous systems. Often the size, weight, and power consumption of the digital twin or related controller must be minimized, ideally realized on embedded computing hardware that can operate without a cloud-computing connection. Here, we show that a nonlinear controller based on next-generation reservoir computing can tackle a difficult control problem: controlling a chaotic system to an arbitrary time-dependent state. The model is accurate, yet it is small enough to be evaluated on a field-programmable gate array typically found in embedded devices. Furthermore, the model only requires 25.0 $\pm$ 7.0 nJ per evaluation, well below other algorithms, even without systematic power optimization. Our work represents the first step in deploying efficient machine learning algorithms to the computing "edge." △ Less

Submitted 8 May, 2024; originally announced June 2024.

Comments: 28 pages, 11 figures

Journal ref: Nat Commun 15, 3886 (2024)

Learning to rank quantum circuits for hardware-optimized performance enhancement

Authors: Gavin S. Hartnett, Aaron Barbosa, Pranav S. Mundada, Michael Hush, Michael J. Biercuk, Yuval Baum

Abstract: We introduce and experimentally test a machine-learning-based method for ranking logically equivalent quantum circuits based on expected performance estimates derived from a training procedure conducted on real hardware. We apply our method to the problem of layout selection, in which abstracted qubits are assigned to physical qubits on a given device. Circuit measurements performed on IBM hardwar… ▽ More We introduce and experimentally test a machine-learning-based method for ranking logically equivalent quantum circuits based on expected performance estimates derived from a training procedure conducted on real hardware. We apply our method to the problem of layout selection, in which abstracted qubits are assigned to physical qubits on a given device. Circuit measurements performed on IBM hardware indicate that the maximum and median fidelities of logically equivalent layouts can differ by an order of magnitude. We introduce a circuit score used for ranking that is parameterized in terms of a physics-based, phenomenological error model whose parameters are fit by training a ranking-loss function over a measured dataset. The dataset consists of quantum circuits exhibiting a diversity of structures and executed on IBM hardware, allowing the model to incorporate the contextual nature of real device noise and errors without the need to perform an exponentially costly tomographic protocol. We perform model training and execution on the 16-qubit ibmq_guadalupe device and compare our method to two common approaches: random layout selection and a publicly available baseline called Mapomatic. Our model consistently outperforms both approaches, predicting layouts that exhibit lower noise and higher performance. In particular, we find that our best model leads to a $1.8\times$ reduction in selection error when compared to the baseline approach and a $3.2\times$ reduction when compared to random selection. Beyond delivering a new form of predictive quantum characterization, verification, and validation, our results reveal the specific way in which context-dependent and coherent gate errors appear to dominate the divergence from performance estimates extrapolated from simple proxy measures. △ Less

Submitted 9 April, 2024; originally announced April 2024.

Comments: 14 pages, 5 figures

Controlling Chaotic Maps using Next-Generation Reservoir Computing

Authors: Robert M. Kent, Wendson A. S. Barbosa, Daniel J. Gauthier

Abstract: In this work, we combine nonlinear system control techniques with next-generation reservoir computing, a best-in-class machine learning approach for predicting the behavior of dynamical systems. We demonstrate the performance of the controller in a series of control tasks for the chaotic Hénon map, including controlling the system between unstable fixed-points, stabilizing the system to higher ord… ▽ More In this work, we combine nonlinear system control techniques with next-generation reservoir computing, a best-in-class machine learning approach for predicting the behavior of dynamical systems. We demonstrate the performance of the controller in a series of control tasks for the chaotic Hénon map, including controlling the system between unstable fixed-points, stabilizing the system to higher order periodic orbits, and to an arbitrary desired state. We show that our controller succeeds in these tasks, requires only 10 data points for training, can control the system to a desired trajectory in a single iteration, and is robust to noise and modeling error. △ Less

Submitted 2 February, 2024; v1 submitted 7 July, 2023; originally announced July 2023.

Comments: 9 pages, 8 figures

Journal ref: Chaos 34, 023102 (2024)

A heuristic to determine the initial gravitational constant of the GSA

Authors: Alfredo J. P. Barbosa, Edmilson M. Moreira, Carlos H. V. Moraes, Otávio A. S. Carpinteiro

Abstract: The Gravitational Search Algorithm (GSA) is an optimization algorithm based on Newton's laws of gravity and dynamics. Introduced in 2009, the GSA already has several versions and applications. However, its performance depends on the values of its parameters, which are determined empirically. Hence, its generality is compromised, because the parameters that are suitable for a particular application… ▽ More The Gravitational Search Algorithm (GSA) is an optimization algorithm based on Newton's laws of gravity and dynamics. Introduced in 2009, the GSA already has several versions and applications. However, its performance depends on the values of its parameters, which are determined empirically. Hence, its generality is compromised, because the parameters that are suitable for a particular application are not necessarily suitable for another. This paper proposes the Gravitational Search Algorithm with Normalized Gravitational Constant (GSA-NGC), which defines a new heuristic to determine the initial gravitational constant of the GSA. The new heuristic is grounded in the Brans-Dicke theory of gravitation and takes into consideration the multiple dimensions of the search space of the application. It aims to improve the final solution and reduce the number of iterations and premature convergences of the GSA. The GSA-NGC is validated experimentally, proving to be suitable for various applications and improving significantly the generality, performance, and efficiency of the GSA. △ Less

Submitted 21 April, 2022; originally announced May 2022.

Comments: 27 pages, 2 figures, 8 tables

Learning Spatiotemporal Chaos Using Next-Generation Reservoir Computing

Authors: Wendson A. S. Barbosa, Daniel J. Gauthier

Abstract: Forecasting the behavior of high-dimensional dynamical systems using machine learning requires efficient methods to learn the underlying physical model. We demonstrate spatiotemporal chaos prediction using a machine learning architecture that, when combined with a next-generation reservoir computer, displays state-of-the-art performance with a computational time $10^3-10^4$ times faster for traini… ▽ More Forecasting the behavior of high-dimensional dynamical systems using machine learning requires efficient methods to learn the underlying physical model. We demonstrate spatiotemporal chaos prediction using a machine learning architecture that, when combined with a next-generation reservoir computer, displays state-of-the-art performance with a computational time $10^3-10^4$ times faster for training process and training data set $\sim 10^2$ times smaller than other machine learning algorithms. We also take advantage of the translational symmetry of the model to further reduce the computational cost and training data, each by a factor of $\sim$10. △ Less

Submitted 30 August, 2022; v1 submitted 24 March, 2022; originally announced March 2022.

Comments: 11 pages, 10 figures

Augmenting Customer Support with an NLP-based Receptionist

Authors: André Barbosa, Alan Godoy

Abstract: In this paper, we show how a Portuguese BERT model can be combined with structured data in order to deploy a chatbot based on a finite state machine to create a conversational AI system that helps a real-estate company to predict its client's contact motivation. The model achieves human level results in a dataset that contains 235 unbalanced labels. Then, we also show its benefits considering the… ▽ More In this paper, we show how a Portuguese BERT model can be combined with structured data in order to deploy a chatbot based on a finite state machine to create a conversational AI system that helps a real-estate company to predict its client's contact motivation. The model achieves human level results in a dataset that contains 235 unbalanced labels. Then, we also show its benefits considering the business impact comparing it against classical NLP methods. △ Less

Submitted 3 December, 2021; originally announced December 2021.

Comments: 11 pages, 2 figures, Symposium in Information and Human Language Technology (STIL)

Journal ref: Anais do XIII Simpósio Brasileiro de Tecnologia da Informação e da Linguagem Humana (2021) 133-142

Next Generation Reservoir Computing

Authors: Daniel J. Gauthier, Erik Bollt, Aaron Griffith, Wendson A. S. Barbosa

Abstract: Reservoir computing is a best-in-class machine learning algorithm for processing information generated by dynamical systems using observed time-series data. Importantly, it requires very small training data sets, uses linear optimization, and thus requires minimal computing resources. However, the algorithm uses randomly sampled matrices to define the underlying recurrent neural network and has a… ▽ More Reservoir computing is a best-in-class machine learning algorithm for processing information generated by dynamical systems using observed time-series data. Importantly, it requires very small training data sets, uses linear optimization, and thus requires minimal computing resources. However, the algorithm uses randomly sampled matrices to define the underlying recurrent neural network and has a multitude of metaparameters that must be optimized. Recent results demonstrate the equivalence of reservoir computing to nonlinear vector autoregression, which requires no random matrices, fewer metaparameters, and provides interpretable results. Here, we demonstrate that nonlinear vector autoregression excels at reservoir computing benchmark tasks and requires even shorter training data sets and training time, heralding the next generation of reservoir computing. △ Less

Submitted 22 July, 2021; v1 submitted 14 June, 2021; originally announced June 2021.

Comments: New supplementary materials on noise sensitivity, dependence on training data set size and other smaller changes

Journal ref: Nat Commun 12, 5564 (2021)

Using machine learning for quantum annealing accuracy prediction

Authors: Aaron Barbosa, Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Abstract: Quantum annealers, such as the device built by D-Wave Systems, Inc., offer a way to compute solutions of NP-hard problems that can be expressed in Ising or QUBO (quadratic unconstrained binary optimization) form. Although such solutions are typically of very high quality, problem instances are usually not solved to optimality due to imperfections of the current generations quantum annealers. In th… ▽ More Quantum annealers, such as the device built by D-Wave Systems, Inc., offer a way to compute solutions of NP-hard problems that can be expressed in Ising or QUBO (quadratic unconstrained binary optimization) form. Although such solutions are typically of very high quality, problem instances are usually not solved to optimality due to imperfections of the current generations quantum annealers. In this contribution, we aim to understand some of the factors contributing to the hardness of a problem instance, and to use machine learning models to predict the accuracy of the D-Wave 2000Q annealer for solving specific problems. We focus on the Maximum Clique problem, a classic NP-hard problem with important applications in network analysis, bioinformatics, and computational chemistry. By training a machine learning classification model on basic problem characteristics such as the number of edges in the graph, or annealing parameters such as D-Wave's chain strength, we are able to rank certain features in the order of their contribution to the solution hardness, and present a simple decision tree which allows to predict whether a problem will be solvable to optimality with the D-Wave 2000Q. We extend these results by training a machine learning regression model that predicts the clique size found by D-Wave. △ Less

Submitted 31 May, 2021; originally announced June 2021.

Report number: LA-UR-21-25091

Reservoir Computing with Superconducting Electronics

Authors: Graham E. Rowlands, Minh-Hai Nguyen, Guilhem J. Ribeill, Andrew P. Wagner, Luke C. G. Govia, Wendson A. S. Barbosa, Daniel J. Gauthier, Thomas A. Ohki

Abstract: The rapidity and low power consumption of superconducting electronics makes them an ideal substrate for physical reservoir computing, which commandeers the computational power inherent to the evolution of a dynamical system for the purposes of performing machine learning tasks. We focus on a subset of superconducting circuits that exhibit soliton-like dynamics in simple transmission line geometrie… ▽ More The rapidity and low power consumption of superconducting electronics makes them an ideal substrate for physical reservoir computing, which commandeers the computational power inherent to the evolution of a dynamical system for the purposes of performing machine learning tasks. We focus on a subset of superconducting circuits that exhibit soliton-like dynamics in simple transmission line geometries. With numerical simulations we demonstrate the effectiveness of these circuits in performing higher-order parity calculations and channel equalization at rates approaching 100 Gb/s. The availability of a proven superconducting logic scheme considerably simplifies the path to a fully integrated reservoir computing platform and makes superconducting reservoirs an enticing substrate for high rate signal processing applications. △ Less

Submitted 3 March, 2021; originally announced March 2021.

Comments: 7 pages, 4 figures

Symmetry-Aware Reservoir Computing

Authors: Wendson A. S. Barbosa, Aaron Griffith, Graham E. Rowlands, Luke C. G. Govia, Guilhem J. Ribeill, Minh-Hai Nguyen, Thomas A. Ohki, Daniel J. Gauthier

Abstract: We demonstrate that matching the symmetry properties of a reservoir computer (RC) to the data being processed dramatically increases its processing power. We apply our method to the parity task, a challenging benchmark problem that highlights inversion and permutation symmetries, and to a chaotic system inference task that presents an inversion symmetry rule. For the parity task, our symmetry-awar… ▽ More We demonstrate that matching the symmetry properties of a reservoir computer (RC) to the data being processed dramatically increases its processing power. We apply our method to the parity task, a challenging benchmark problem that highlights inversion and permutation symmetries, and to a chaotic system inference task that presents an inversion symmetry rule. For the parity task, our symmetry-aware RC obtains zero error using an exponentially reduced neural network and training data, greatly speeding up the time to result and outperforming hand crafted artificial neural networks. When both symmetries are respected, we find that the network size $N$ necessary to obtain zero error for 50 different RC instances scales linearly with the parity-order $n$. Moreover, some symmetry-aware RC instances perform a zero error classification with only $N=1$ for $n\leq7$. Furthermore, we show that a symmetry-aware RC only needs a training data set with size on the order of $(n+n/2)$ to obtain such performance, an exponential reduction in comparison to a regular RC which requires a training data set with size on the order of $n2^n$ to contain all $2^n$ possible $n-$bit-long sequences. For the inference task, we show that a symmetry-aware RC presents a normalized root-mean-square error three orders-of-magnitude smaller than regular RCs. For both tasks, our RC approach respects the symmetries by adjusting only the input and the output layers, and not by problem-based modifications to the neural network. We anticipate that generalizations of our procedure can be applied in information processing for problems with known symmetries. △ Less

Submitted 22 September, 2021; v1 submitted 30 January, 2021; originally announced February 2021.

Comments: 10 pages, 7 Figures

Optimizing embedding-related quantum annealing parameters for reducing hardware bias

Authors: Aaron Barbosa, Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Abstract: Quantum annealers have been designed to propose near-optimal solutions to NP-hard optimization problems. However, the accuracy of current annealers such as the ones of D-Wave Systems, Inc., is limited by environmental noise and hardware biases. One way to deal with these imperfections and to improve the quality of the annealing results is to apply a variety of pre-processing techniques such as spi… ▽ More Quantum annealers have been designed to propose near-optimal solutions to NP-hard optimization problems. However, the accuracy of current annealers such as the ones of D-Wave Systems, Inc., is limited by environmental noise and hardware biases. One way to deal with these imperfections and to improve the quality of the annealing results is to apply a variety of pre-processing techniques such as spin reversal (SR), anneal offsets (AO), or chain weights (CW). Maximizing the effectiveness of these techniques involves performing optimizations over a large number of parameters, which would be too costly if needed to be done for each new problem instance. In this work, we show that the aforementioned parameter optimization can be done for an entire class of problems, given each instance uses a previously chosen fixed embedding. Specifically, in the training phase, we fix an embedding E of a complete graph onto the hardware of the annealer, and then run an optimization algorithm to tune the following set of parameter values: the set of bits to be flipped for SR, the specific qubit offsets for AO, and the distribution of chain weights, optimized over a set of training graphs randomly chosen from that class, where the graphs are embedded onto the hardware using E. In the testing phase, we estimate how well the parameters computed during the training phase work on a random selection of other graphs from that class. We investigate graph instances of varying densities for the Maximum Clique, Maximum Cut, and Graph Partitioning problems. Our results indicate that, compared to their default behavior, substantial improvements of the annealing results can be achieved by using the optimized parameters for SR, AO, and CW. △ Less

Submitted 1 December, 2020; v1 submitted 1 November, 2020; originally announced November 2020.

Report number: LA-UR-20-28631

The 1st Agriculture-Vision Challenge: Methods and Results

Authors: Mang Tik Chiu, Xingqian Xu, Kai Wang, Jennifer Hobbs, Naira Hovakimyan, Thomas S. Huang, Honghui Shi, Yunchao Wei, Zilong Huang, Alexander Schwing, Robert Brunner, Ivan Dozier, Wyatt Dozier, Karen Ghandilyan, David Wilson, Hyunseong Park, Junhee Kim, Sungho Kim, Qinghui Liu, Michael C. Kampffmeyer, Robert Jenssen, Arnt B. Salberg, Alexandre Barbosa, Rodrigo Trevisan, Bingchen Zhao , et al. (17 additional authors not shown)

Abstract: The first Agriculture-Vision Challenge aims to encourage research in developing novel and effective algorithms for agricultural pattern recognition from aerial images, especially for the semantic segmentation task associated with our challenge dataset. Around 57 participating teams from various countries compete to achieve state-of-the-art in aerial agriculture semantic segmentation. The Agricultu… ▽ More The first Agriculture-Vision Challenge aims to encourage research in developing novel and effective algorithms for agricultural pattern recognition from aerial images, especially for the semantic segmentation task associated with our challenge dataset. Around 57 participating teams from various countries compete to achieve state-of-the-art in aerial agriculture semantic segmentation. The Agriculture-Vision Challenge Dataset was employed, which comprises of 21,061 aerial and multi-spectral farmland images. This paper provides a summary of notable methods and results in the challenge. Our submission server and leaderboard will continue to open for researchers that are interested in this challenge dataset and task; the link can be found here. △ Less

Submitted 23 April, 2020; v1 submitted 21 April, 2020; originally announced April 2020.

Comments: CVPR 2020 Workshop

LRCN-RetailNet: A recurrent neural network architecture for accurate people counting

Authors: Lucas Massa, Adriano Barbosa, Krerley Oliveira, Thales Vieira

Abstract: Measuring and analyzing the flow of customers in retail stores is essential for a retailer to better comprehend customers' behavior and support decision-making. Nevertheless, not much attention has been given to the development of novel technologies for automatic people counting. We introduce LRCN-RetailNet: a recurrent neural network architecture capable of learning a non-linear regression model… ▽ More Measuring and analyzing the flow of customers in retail stores is essential for a retailer to better comprehend customers' behavior and support decision-making. Nevertheless, not much attention has been given to the development of novel technologies for automatic people counting. We introduce LRCN-RetailNet: a recurrent neural network architecture capable of learning a non-linear regression model and accurately predicting the people count from videos captured by low-cost surveillance cameras. The input video format follows the recently proposed RGBP image format, which is comprised of color and people (foreground) information. Our architecture is capable of considering two relevant aspects: spatial features extracted through convolutional layers from the RGBP images; and the temporal coherence of the problem, which is exploited by recurrent layers. We show that, through a supervised learning approach, the trained models are capable of predicting the people count with high accuracy. Additionally, we present and demonstrate that a straightforward modification of the methodology is effective to exclude salespeople from the people count. Comprehensive experiments were conducted to validate, evaluate and compare the proposed architecture. Results corroborated that LRCN-RetailNet remarkably outperforms both the previous RetailNet architecture, which was limited to evaluating a single image per iteration; and a state-of-the-art neural network for object detection. Finally, computational performance experiments confirmed that the entire methodology is effective to estimate people count in real-time. △ Less

Submitted 12 May, 2020; v1 submitted 20 April, 2020; originally announced April 2020.

A wireless secure key distribution system with no couriers: a One-Time-Pad Revival

Authors: Geraldo A Barbosa

Abstract: Among the problems to guarantee secrecy for in-transit information, the difficulties involved in renewing cryptographic keys in a secure way using couriers, the perfect secrecy encryption method known as One-Time-Pad (OTP) became almost obsolete. Pure quantum key distribution (QKD) ideally offers security for key distribution and could revive OTP. However, special networks that may need optical fi… ▽ More Among the problems to guarantee secrecy for in-transit information, the difficulties involved in renewing cryptographic keys in a secure way using couriers, the perfect secrecy encryption method known as One-Time-Pad (OTP) became almost obsolete. Pure quantum key distribution (QKD) ideally offers security for key distribution and could revive OTP. However, special networks that may need optical fibers, satellite, relay stations, expensive detection equipment compared with telecom technology and the slow protocol offer powerful obstacles for widespread use of QKD. Classical encryption methods flood the secure communication landscape. Many of them rely its security on historical difficulties such as factoring of large numbers -- their alleged security sometimes are presented as the difficulty to brake encryption by brute force. The possibility for a mathematical breakthrough that could make factoring trivial are poorly discussed. This work proposes a solution to bring perfect secrecy to in-transit communication and without the above problems. It shows the key distribution scheme (nicknamed KeyBITS Platform) based on classical signals carrying information but that carry with them recordings of quantum noise. Legitimate users start with a shared information of the coding bases used that gives them an information advantage that allows easy signal recovery. The recorded noise protects the legitimate users and block the attacker's access. This shared information is refreshed at the end of each batch of keys sent providing the secret shared information for the next round. With encryption keys distilled from securely transmitted signals at each round OTP can be revived and at fast speeds. △ Less

Submitted 31 May, 2020; v1 submitted 16 January, 2019; originally announced January 2019.

Comments: 19 pages, 33 figures

Interplay of Probabilistic Shaping and the Blind Phase Search Algorithm

Authors: Darli A. A. Mello, Fabio A. Barbosa, Jacklyn D. Reis

Abstract: Probabilistic shaping (PS) is a promising technique to approach the Shannon limit using typical constellation geometries. However, the impact of PS on the chain of signal processing algorithms of a coherent receiver still needs further investigation. In this work we study the interplay of PS and phase recovery using the blind phase search (BPS) algorithm, which is widely used in optical communicat… ▽ More Probabilistic shaping (PS) is a promising technique to approach the Shannon limit using typical constellation geometries. However, the impact of PS on the chain of signal processing algorithms of a coherent receiver still needs further investigation. In this work we study the interplay of PS and phase recovery using the blind phase search (BPS) algorithm, which is widely used in optical communications systems. We first investigate a supervised phase search (SPS) algorithm as a theoretical upper bound on the BPS performance, assuming perfect decisions. It is shown that PS influences the SPS algorithm, but its impact can be alleviated by moderate noise rejection window sizes. On the other hand, BPS is affected by PS even for long windows because of correlated erroneous decisions in the phase recovery scheme. The simulation results also show that the capacity-maximizing shaping is near to the BPS worst-case situation for square-QAM constellations, causing potential implementation penalties. △ Less

Submitted 12 September, 2018; v1 submitted 15 March, 2018; originally announced March 2018.

Comments: Accepted for publication in the next available issue of the IEEE/OSA Journal of Lightwave Technology (https://ieeexplore.ieee.org/document/8457202/)

Reconstruction of Electrical Impedance Tomography Using Fish School Search, Non-Blind Search, and Genetic Algorithm

Authors: Valter Augusto de Freitas Barbosa, Reiga Ramalho Ribeiro, Allan Rivalles Souza Feitosa, Victor Luiz Bezerra Araújo da Silva, Arthur Diego Dias Rocha, Rafaela Covello de Freitas, Ricardo Emmanuel de Souza, Wellington Pinheiro dos Santos

Abstract: Electrical Impedance Tomography (EIT) is a noninvasive imaging technique that does not use ionizing radiation, with application both in environmental sciences and in health. Image reconstruction is performed by solving an inverse problem and ill-posed. Evolutionary Computation and Swarm Intelligence have become a source of methods for solving inverse problems. Fish School Search (FSS) is a promisi… ▽ More Electrical Impedance Tomography (EIT) is a noninvasive imaging technique that does not use ionizing radiation, with application both in environmental sciences and in health. Image reconstruction is performed by solving an inverse problem and ill-posed. Evolutionary Computation and Swarm Intelligence have become a source of methods for solving inverse problems. Fish School Search (FSS) is a promising search and optimization method, based on the dynamics of schools of fish. In this article the authors present a method for reconstruction of EIT images based on FSS and Non-Blind Search (NBS). The method was evaluated using numerical phantoms consisting of electrical conductivity images with subjects in the center, between the center and the edge and on the edge of a circular section, with meshes of 415 finite elements. The authors performed 20 simulations for each configuration. Results showed that both FSS and FSS-NBS were able to converge faster than genetic algorithms. △ Less

Submitted 3 December, 2017; originally announced December 2017.

Journal ref: International Journal of Swarm Intelligence Research, Volume 8, Issue 2, 2017

A Human-Checkable Four-Color Theorem Proof

Authors: André Luiz Barbosa

Abstract: This paper presents a short and simple proof of the Four-Color Theorem that can be utterly checkable by human mathematicians, without computer assistance. The new key idea that has allowed it and the global structure of the proof are presented in the Introduction. This paper presents a short and simple proof of the Four-Color Theorem that can be utterly checkable by human mathematicians, without computer assistance. The new key idea that has allowed it and the global structure of the proof are presented in the Introduction. △ Less

Submitted 1 November, 2019; v1 submitted 6 June, 2017; originally announced August 2017.

Comments: 26 pages, 43 figures, 5 tables and 1 new great idea!

MSC Class: 05C10 (Primary); 05C15 (Secondary)

A wireless physically secure key distribution system

Authors: Geraldo A. Barbosa

Abstract: A secure key distribution protocol protected by light's noise was introduced in 2003 [Phys. Rev. A 68, 052307 (2003)]. That protocol utilized the shot noise of light present in the optical channel (eg., an optical fiber) to restrict information leaks to an adversary. An initial shared information between the legitimate users allowed them to extract more information from the channel than the one ob… ▽ More A secure key distribution protocol protected by light's noise was introduced in 2003 [Phys. Rev. A 68, 052307 (2003)]. That protocol utilized the shot noise of light present in the optical channel (eg., an optical fiber) to restrict information leaks to an adversary. An initial shared information between the legitimate users allowed them to extract more information from the channel than the one obtained by the adversary. That original paper recognized the need for a privacy amplification step but no specific protocol was presented. More recently that original idea was improved with a specific privacy amplification protocol [arXiv:1406.1543v2 [cs.CR] 8 Jul 2015] while keeping the use of an optical communication channel. This work merges main ideas of the protection given by the light's noise in a protocol applied to wireless channels. The use of a wireless channels together with recorded physical noise was introduced from 2005 to 2007 (see eg, arXiv:quant-ph/0510011 v2 16 Nov 2005 and arXiv:0705.2243v2 [quant-ph] 17 May 2007). This work improves those embrionary ideas of wireless channels secured by recorded optical noise. The need for specific optical channels is eliminated with the wireless variation and opens up the possibility to apply the technique to mobile devices. This work introduces this new scheme and calculates the associated security level. △ Less

Submitted 25 July, 2016; v1 submitted 1 January, 2016; originally announced January 2016.

Comments: 6 pages,10 figures, 1 table

The Dead Cryptographers Society Problem

Authors: André Luiz Barbosa

Abstract: This paper defines The Dead Cryptographers Society Problem - DCS (where several great cryptographers created many polynomial-time Deterministic Turing Machines (DTMs) of a specific type, ran them on their proper descriptions concatenated with some arbitrary strings, deleted them and left only the results from those running, after they died: if those DTMs only permute and sometimes invert the bits… ▽ More This paper defines The Dead Cryptographers Society Problem - DCS (where several great cryptographers created many polynomial-time Deterministic Turing Machines (DTMs) of a specific type, ran them on their proper descriptions concatenated with some arbitrary strings, deleted them and left only the results from those running, after they died: if those DTMs only permute and sometimes invert the bits on input, is it possible to decide the language formed by such resulting strings within polynomial time?), proves some facts about its computational complexity, and discusses some possible uses on Cryptography, such as into distance keys distribution, online reverse auction and secure communication. △ Less

Submitted 21 December, 2018; v1 submitted 15 January, 2015; originally announced January 2015.

Comments: 7 pages, 2 tables, 1 JavaScript code and some great new ideas on Cryptography!

MSC Class: 94A60 (Primary); 94A62 (Secondary)

Untappable key distribution system: a one-time-pad booster

Authors: Geraldo A. Barbosa, Jeroen van de Graaf

Abstract: One-time-pad (OTP) encryption simply cannot be cracked, even by a quantum computer. The need of sharing in a secure way supplies of symmetric random keys turned the method almost obsolete as a standing-alone method for fast and large volume telecommunication. Basically, this secure sharing of keys and their renewal, once exhausted, had to be done through couriers, in a slow and costly process. Thi… ▽ More One-time-pad (OTP) encryption simply cannot be cracked, even by a quantum computer. The need of sharing in a secure way supplies of symmetric random keys turned the method almost obsolete as a standing-alone method for fast and large volume telecommunication. Basically, this secure sharing of keys and their renewal, once exhausted, had to be done through couriers, in a slow and costly process. This paper presents a solution for this problem providing a fast and unlimited renewal of secure keys: An untappable key distribution system is presented and detailed. This fast key distribution system utilizes two layers of confidentially protection: 1) Physical noise intrinsic to the optical channel that turn the coded signals into stealth signals and 2) Privacy amplification using a bit pool of refreshed entropy run after run, to eliminate any residual information. The resulting level of security is rigorously calculated and demonstrates that the level of information an eavesdropper could obtain is completely negligible. The random bit sequences, fast and securely distributed, can be used to encrypt text, data or voice. △ Less

Submitted 8 July, 2015; v1 submitted 5 June, 2014; originally announced June 2014.

Comments: 12 pages, 16 figures

P != NP Proof

Authors: André Luiz Barbosa

Abstract: This paper demonstrates that P \not= NP. The way was to generalize the traditional definitions of the classes P and NP, to construct an artificial problem (a generalization to SAT: The XG-SAT, much more difficult than the former) and then to demonstrate that it is in NP but not in P (where the classes P and NP are generalized and called too simply P and NP in this paper, and then it is explained w… ▽ More This paper demonstrates that P \not= NP. The way was to generalize the traditional definitions of the classes P and NP, to construct an artificial problem (a generalization to SAT: The XG-SAT, much more difficult than the former) and then to demonstrate that it is in NP but not in P (where the classes P and NP are generalized and called too simply P and NP in this paper, and then it is explained why the traditional classes P and NP should be fixed and replaced by these generalized ones into Theory of Computer Science). The demonstration consists of: 1. Definition of Restricted Type X Program; 2. Definition of the General Extended Problem of Satisfiability of a Boolean Formula - XG-SAT; 3. Generalization to classes P and NP; 4. Demonstration that the XG-SAT is in NP; 5. Demonstration that the XG-SAT is not in P; 6. Demonstration that the Baker-Gill-Solovay Theorem does not refute the proof; 7. Demonstration that the Razborov-Rudich Theorem does not refute the proof; 8. Demonstration that the Aaronson-Wigderson Theorem does not refute the proof. △ Less

Submitted 28 June, 2019; v1 submitted 22 July, 2009; originally announced July 2009.

Comments: 25 pages and 3 new great ideas!

MSC Class: 68Q15 (Primary); 68Q17 (Secondary)

Automatic Face Recognition System Based on Local Fourier-Bessel Features

Authors: Yossi Zana, Roberto M. Cesar-Jr, Regis de A. Barbosa

Abstract: We present an automatic face verification system inspired by known properties of biological systems. In the proposed algorithm the whole image is converted from the spatial to polar frequency domain by a Fourier-Bessel Transform (FBT). Using the whole image is compared to the case where only face image regions (local analysis) are considered. The resulting representations are embedded in a dissi… ▽ More We present an automatic face verification system inspired by known properties of biological systems. In the proposed algorithm the whole image is converted from the spatial to polar frequency domain by a Fourier-Bessel Transform (FBT). Using the whole image is compared to the case where only face image regions (local analysis) are considered. The resulting representations are embedded in a dissimilarity space, where each image is represented by its distance to all the other images, and a Pseudo-Fisher discriminator is built. Verification test results on the FERET database showed that the local-based algorithm outperforms the global-FBT version. The local-FBT algorithm performed as state-of-the-art methods under different testing conditions, indicating that the proposed system is highly robust for expression, age, and illumination variations. We also evaluated the performance of the proposed system under strong occlusion conditions and found that it is highly robust for up to 50% of face occlusion. Finally, we automated completely the verification system by implementing face and eye detection algorithms. Under this condition, the local approach was only slightly superior to the global approach. △ Less

Submitted 27 September, 2005; originally announced September 2005.

Comments: 2005, Brazilian Symposium on Computer Graphics and Image Processing, 18 (SIBGRAPI)