Browsing by Author "Rojas González, Luis Cristóbal"

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    Computability in Harmonic Analysis
    (SPRINGER, 2021) Binder, Ilia; Glucksam, Adi; Rojas González, Luis Cristóbal; Yampolsky, Michael
    We study the question of constructive approximation of the harmonic measure omega(Omega)(x) of a bounded domain Omega with respect to a point x is an element of Omega. In particular, using a new notion of computable harmonic approximation, we show that for an arbitrary such Omega, computability of the harmonic measure omega(Omega)(x) for a single point x is an element of Omega implies computability of omega(Omega)(y) for any y is an element of Omega. This may require a different algorithm for different points y, which leads us to the construction of surprising natural examples of continuous functions that arise as solutions to a Dirichlet problem, whose values can be computed at any point, but cannot be computed with the use of the same algorithm on all of their domains. We further study the conditions under which the harmonic measure is computable uniformly, that is by a single algorithm, and characterize them for regular domains with computable boundaries.
  • Thumbnail Image
    Item
    Find a witness or shatter: the landscape of computable PAC learning
    (2023) Delle Rose, Valentino; Kozachinskiy, Alexander; Rojas González, Luis Cristóbal; Steifer, Tomasz
    This paper contributes to the study of CPAC learnability -- a computable version of PAC learning -- by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a decidable class of hypothesis which is properly CPAC learnable, but only with uncomputably fast growing sample complexity. This solves a question from Sterkenburg (COLT 2022). Finally, we construct a decidable class of finite Littlestone dimension which is not improperly CPAC learnable, strengthening a recent result of Sterkenburg (2022) and answering a question posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our results provide a complete landscape for the learnability problem in the CPAC setting.
  • Thumbnail Image
    Item
    Multiscale entropy analysis of retinal signals reveals reduced complexity in a mouse model of Alzheimer's disease
    (NATURE PORTFOLIO, 2022) Araya-Arriagada, Joaquín; Garay, Sebastián; Rojas González, Luis Cristóbal; Duran-Aniotz, Claudia; Palacios, Adrián G.; Chacón, Max; Medina, Leonel E.
    Alzheimer's disease (AD) is one of the most significant health challenges of our time, affecting a growing number of the elderly population. In recent years, the retina has received increased attention as a candidate for AD biomarkers since it appears to manifest the pathological signatures of the disease. Therefore, its electrical activity may hint at AD-related physiological changes. However, it is unclear how AD affects retinal electrophysiology and what tools are more appropriate to detect these possible changes. In this study, we used entropy tools to estimate the complexity of the dynamics of healthy and diseased retinas at different ages. We recorded microelectroretinogram responses to visual stimuli of different nature from retinas of young and adult, wild-type and 5xFAD-an animal model of AD-mice. To estimate the complexity of signals, we used the multiscale entropy approach, which calculates the entropy at several time scales using a coarse graining procedure. We found that young retinas had more complex responses to different visual stimuli. Further, the responses of young, wild-type retinas to natural-like stimuli exhibited significantly higher complexity than young, 5xFAD retinas. Our findings support a theory of complexity-loss with aging and disease and can have significant implications for early AD diagnosis.
  • Thumbnail Image
    Item
    No Agreement Without Loss: Learning and Social Choice in Peer Review
    (2023) Barcelo Baeza, Pablo; Duarte, Mauricio; Rojas González, Luis Cristóbal; Steifer, Tomasz
    In peer review systems, reviewers are often asked toevaluate various features of submissions, such as technical qualityor novelty. A score is given to each of the predefined features andbased on these the reviewer has to provide an overall quantitativerecommendation. It may be assumed that each reviewer has her ownmapping from the set of features to a recommendation, and thatdifferent reviewers have different mappings in mind. This introducesan element of arbitrariness known as commensuration bias. In thispaper we discuss a framework, introduced by Noothigattu, Shah andProcaccia, and then applied by the organizers of the AAAI 2022conference. Noothigattu, Shah and Procaccia proposed to aggregatereviewer’s mapping by minimizing certain loss functions, and studiedaxiomatic properties of this approach, in the sense of social choicetheory. We challenge several of the results and assumptions used intheir work and report a number of negative results. On the one hand,we study a trade-off between some of the axioms proposed and theability of the method to properly capture agreements of the majorityof reviewers. On the other hand, we show that dropping a certainunrealistic assumption has dramatic effects, including causing themethod to be discontinuous.
  • Thumbnail Image
    Item
    Realizing semicomputable simplices by computable dynamical systems
    (2022) Coronel Soto, Álvaro Daniel; Frank, Alexander; Hoyrup, Mathieu; Rojas González, Luis Cristóbal
    We study the computability of the set of invariant measures of a computable dynamical system. It is known to be semicomputable but not computable in general, and we investigate which semicomputable simplices can be realized in this way. We prove that every semicomputable finite-dimensional simplex can be realized, and that every semicomputable finite-dimensional convex set is the projection of the set of invariant measures of a computable dynamical system. In particular, there exists a computable system having exactly two ergodic measures, none of which is computable. Moreover, all the dynamical systems that we build are minimal Cantor systems. (C) 2022 Elsevier B.V. All rights reserved.
  • Thumbnail Image
    Item
    Subshifts on groups and computable analysis
    (2024) Carrasco Vargas, Nicanor; Rojas González, Luis Cristóbal; Pontificia Universidad Católica de Chile. Facultad de Matemáticas
    Subshifts are a fundamental class of topological dynamical systems. The study of subshifts on groups different from $\mathbb{Z}$, such as $\mathbb{Z}^d$, $d\geq 2$, has been a subject of intense research in recent years. These investigations have unveiled aremarkable connection between dynamics and recursion theory. That is, different questions about the dynamics of these systems have been answered in recursion-theoretical terms. In this work we further explore this connection. We use the framework of computable analysis to explore the class of effective dynamical systems on metric spaces, and relate these systems to subshifts of finite type (SFTs) on groups. We prove that every effective dynamical system on a general metric space is the topological factor of an effective dynamical system with topological dimension zero. We combine this result with existing simulation results to obtain new examples of systems that are factors of SFTsWe also study a conjugacy invariant for subshifts on groups called Medvedev degree. This invariant is a complexity measure of algorithmic nature. We develop the basic theory of these degrees for subshifts on arbitrary finitely generated groups. Using these tools we are able to classify the values that this invariant attains for SFTs and other classes of subshifts on several groups. Furthermore, we establish a connection between these degrees and the distribution of isolated points in the space of all subshifts. Motivated by the study of Medvedev degrees of subshifts, we also consider translation-like actions of groups on graphs. We prove that every connected, locally finite, and infinite graph admits a translation by $\mathbb{Z}$, and that this action can be chosen transitive exactly when the graph has one or two ends. This generalizes a result of Seward about translation-like action of $\mathbb{Z}$ on finitely generated groups. Our proof is constructive, and allows us to prove that under natural hypotheses, translation-like actions by $\mathbb{Z}$ on groups and graphs can be effectively computed.
  • Thumbnail Image
    Item
    Three iterations of (d − 1)-WL test distinguish non isometric clouds of d-dimensional points
    (2023) Delle Rose, Valentino; Kozachinskiy, Alexander; Rojas González, Luis Cristóbal; Petrache, Mircea Alexandru; Barceló Baeza, Pablo
    The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose capabilities and performance can be understood in terms of the expressive power of this test. Motivated by recent developments in machine learning applications to datasets involving three-dimensional objects, we study when the WL test is {\em complete} for clouds of euclidean points represented by complete distance graphs, i.e., when it can distinguish, up to isometry, any arbitrary such cloud.Our main result states that the (d−1)-dimensional WL test is complete for point clouds in d-dimensional Euclidean space, for any d≥2, and that only three iterations of the test suffice. Our result is tight for d=2,3. We also observe that the d-dimensional WL test only requires one iteration to achieve completeness.