Search

This work presents global random walk approximations of solutions to one-dimensional Stefan-type moving-boundary problems. We are particularly interested in the case when the moving boundary is driven by an explicit representation of its speed. This situation is usually referred to in the literature as moving-boundary problem with kinetic condition. As a direct application, we propose a numerical scheme to forecast the penetration of small diffusants into a rubber-based material. To check the quality of our results, we compare the numerical results obtained by global random walks either using the analytical solution to selected benchmark cases or relying on finite element approximations with a priori known convergence rates. It turns out that the global random walk concept can be used to produce good quality approximations of the weak solutions to the target class of problems., Comment: 13 pages, 2 Figures, 5 Tables

The tensor programming abstraction has become a foundational paradigm for modern computing. This framework allows users to write high performance programs for bulk computation via a high-level imperative interface. Recent work has extended this paradigm to sparse tensors (i.e. tensors where most entries are not explicitly represented) with the use of sparse tensor compilers. These systems excel at producing efficient code for computation over sparse tensors, which may be stored in a wide variety of formats. However, they require the user to manually choose the order of operations and the data formats at every step. Unfortunately, these decisions are both highly impactful and complicated, requiring significant effort to manually optimize. In this work, we present Galley, a system for declarative sparse tensor programming. Galley performs cost-based optimization to lower these programs to a logical plan then to a physical plan. It then leverages sparse tensor compilers to execute the physical plan efficiently. We show that Galley achieves high performance on a wide variety of problems including machine learning algorithms, subgraph counting, and iterative graph algorithms.

We demonstrate QirK, a system for answering natural language questions on Knowledge Graphs (KG). QirK can answer structurally complex questions that are still beyond the reach of emerging Large Language Models (LLMs). It does so using a unique combination of database technology, LLMs, and semantic search over vector embeddings. The glue for these components is an intermediate representation (IR). The input question is mapped to IR using LLMs, which is then repaired into a valid relational database query with the aid of a semantic search on vector embeddings. This allows a practical synthesis of LLM capabilities and KG reliability. A short video demonstrating QirK is available at https://youtu.be/6c81BLmOZ0U.

We consider the (sub-Riemannian type) control problem of finding a path going from an initial point $x$ to a target point $y$, by only moving in certain admissible directions. We assume that the corresponding vector fields satisfy the bracket-generating (H\"ormander) condition, so that the classical Chow-Rashevskii theorem guarantees the existence of such a path. One natural way to try to solve this problem is via a gradient flow on control space. However, since the corresponding dynamics may have saddle points, any convergence result must rely on suitable (e.g. random) initialisation. We consider the case when this initialisation is irregular, which is conveniently formulated via Lyons' rough path theory. We show that one advantage of this initialisation is that the saddle points are moved to infinity, while minima remain at a finite distance from the starting point. In the step $2$-nilpotent case, we further manage to prove that the gradient flow converges to a solution, if the initial condition is the path of a Brownian motion (or rougher). The proof is based on combining ideas from Malliavin calculus with {\L}ojasiewicz inequalities. A possible motivation for our study comes from the training of deep Residual Neural Nets, in the regime when the number of trainable parameters per layer is smaller than the dimension of the data vector.

The purpose of the paper is to examine the perceptions of entrepreneurship of graduate students enrolled in a digital-oriented entrepreneurship course, focusing on the challenges and opportunities related to starting a business. In today's digital era, businesses heavily depend on tailored software solutions to facilitate their operational processes, foster expansion, and enhance their competitive edge, thus assuming, to a certain degree, the characteristics of software companies. For data gathering, we used online exploratory surveys. The findings indicated that although entrepreneurship was considered an attractive option by students, very few of them declared that they intended to start a business soon. The main issues raised by the students were internal traits and external obstacles, such as lack of resources and support. Gender discrimination and cultural biases persist, limiting opportunities and equality for women. In terms of gender, women face limited representation in leadership roles, are expected to do more unpaid 'family work', are perceived as less capable in ding business, and need to prove their skills. Even if women are less discriminated now, both genders agree that women still face discrimination in business domain. In terms of percentages, women mentioned gender discrimination in higher percentages. Addressing these issues requires awareness, education, and policy changes to ensure fair treatment and opportunities for women., Comment: In Proceedings of the 16th International Conference on Computer Supported Education - Volume 1, ISBN 978-989-758-697-2, ISSN 2184-5026, pages 347-354

Graph workloads pose a particularly challenging problem for query optimizers. They typically feature large queries made up of entirely many-to-many joins with complex correlations. This puts significant stress on traditional cardinality estimation methods which generally see catastrophic errors when estimating the size of queries with only a handful of joins. To overcome this, we propose COLOR, a framework for subgraph cardinality estimation which applies insights from graph compression theory to produce a compact summary that captures the global topology of the data graph. Further, we identify several key optimizations that enable tractable estimation over this summary even for large query graphs. We then evaluate several designs within this framework and find that they improve accuracy by up to 10$^3$x over all competing methods while maintaining fast inference, a small memory footprint, efficient construction, and graceful degradation under updates.

We analyze how well pre-trained large language models (e.g., Llama2, GPT-4, Claude 3, etc) can do linear and non-linear regression when given in-context examples, without any additional training or gradient updates. Our findings reveal that several large language models (e.g., GPT-4, Claude 3) are able to perform regression tasks with a performance rivaling (or even outperforming) that of traditional supervised methods such as Random Forest, Bagging, or Gradient Boosting. For example, on the challenging Friedman #2 regression dataset, Claude 3 outperforms many supervised methods such as AdaBoost, SVM, Random Forest, KNN, or Gradient Boosting. We then investigate how well the performance of large language models scales with the number of in-context exemplars. We borrow from the notion of regret from online learning and empirically show that LLMs are capable of obtaining a sub-linear regret., Comment: 55 pages, 48 figures COLM camera-ready version; Changes include: (i) added real-world datasets (Appendix I), (ii) fixed typos

A complex hyperplane arrangement $\mathcal{A}$ is said to be decomposable if there are no elements in the degree 3 part of its holonomy Lie algebra besides those coming from the rank 2 flats. When this purely combinatorial condition is satisfied, it is known that the associated graded Lie algebra of the arrangement group $G$ decomposes (in degrees greater than 1) as a direct product of free Lie algebras. It follows that the $I$-adic completion of the Alexander invariant $B(G)$ also decomposes as a direct sum of "local" invariants and the Chen ranks of $G$ are the sums of the local contributions. Moreover, if $B(G)$ is separated, then the degree 1 cohomology jump loci of the complement of $\mathcal{A}$ have only local components, and the algebraic monodromy of the Milnor fibration is trivial in degree 1., Comment: 56 pages

Each complex hyperplane arrangement gives rise to a Milnor fibration of its complement. Although the Betti numbers of the Milnor fiber $F$ can be expressed in terms of the jump loci for rank 1 local systems on the complement, explicit formulas are still lacking in full generality, even for $b_1(F)$. We study here the "generic" case (in which $b_1(F)$ is as small as possible), and look deeper into the algebraic topology of such Milnor fibrations with trivial algebraic monodromy. Our main focus is on the cohomology jump loci and the lower central series quotients of $\pi_1(F)$. In the process, we produce a pair of arrangements for which the respective Milnor fibers have the same Betti numbers, yet non-isomorphic fundamental groups: the difference is picked by the higher-depth characteristic varieties and by the Schur multipliers of the second nilpotent quotients., Comment: 52 pages; to appear in a special issue of Revue Roumaine de Math\'ematiques Pures et Appliqu\'ees

In recent years, several information-theoretic upper bounds have been introduced on the output size and evaluation cost of database join queries. These bounds vary in their power depending on both the type of statistics on input relations and the query plans that they support. This motivated the search for algorithms that can compute the output of a join query in times that are bounded by the corresponding information-theoretic bounds. In this paper, we describe PANDA, an algorithm that takes a Shannon-inequality that underlies the bound, and translates each proof step into an algorithmic step corresponding to some database operation. PANDA computes answers to a conjunctive query in time given by the the submodular width plus the output size of the query. The version in this paper represents a significant simplification of the original version [ANS, PODS'17].

Numerical solutions for flows in partially saturated porous media pose challenges related to the non-linearity and elliptic-parabolic degeneracy of the governing Richards' equation. Iterative methods are therefore required to manage the complexity of the flow problem. Norms of successive corrections in the iterative procedure form sequences of positive numbers. Definitions of computational orders of convergence and theoretical results for abstract convergent sequences can thus be used to evaluate and compare different iterative methods. We analyze in this frame Newton's and $L$-scheme methods for an implicit finite element method (FEM) and the $L$-scheme for an explicit finite difference method (FDM). We also investigate the effect of the Anderson Acceleration (AA) on both the implicit and the explicit $L$-schemes. Considering a two-dimensional test problem, we found that the AA halves the number of iterations and renders the convergence of the FEM scheme two times faster. As for the FDM approach, AA does not reduce the number of iterations and even increases the computational effort. Instead, being explicit, the FDM $L$-scheme without AA is faster and as accurate as the FEM $L$-scheme with AA.

In this note, we present a conjecture on intersections of set families, and a rephrasing of the conjecture in terms of principal downsets of Boolean lattices. The conjecture informally states that, whenever we can express the measure of a union of sets in terms of the measure of some of their intersections using the inclusion-exclusion formula, then we can express the union as a set from these same intersections via the set operations of disjoint union and subset complement. We also present a partial result towards establishing the conjecture., Comment: 30 pages

We study the dynamic query evaluation problem: Given a full conjunctive query Q and a sequence of updates to the input database, we construct a data structure that supports constant-delay enumeration of the tuples in the query output after each update. We show that a sequence of N insert-only updates to an initially empty database can be executed in total time O(N^w(Q)), where w(Q) is the fractional hypertree width of Q. This matches the complexity of the static query evaluation problem for Q and a database of size N. One corollary is that the amortized time per single-tuple insert is constant for acyclic full conjunctive queries. In contrast, we show that a sequence of N inserts and deletes can be executed in total time O(N^w(Q')), where Q' is obtained from Q by extending every relational atom with extra variables that represent the "lifespans" of tuples in the database. We show that this reduction is optimal in the sense that the static evaluation runtime of Q' provides a lower bound on the total update time for the output of Q. Our approach achieves amortized optimal update times for the hierarchical and Loomis-Whitney join queries.

For a certain class of McKean--Vlasov processes, we introduce proxy processes that substitute the mean-field interaction with self-interaction, employing a weighted occupation measure. Our study encompasses two key achievements. First, we demonstrate the ergodicity of the self-interacting dynamics, under broad conditions, by applying the reflection coupling method. Second, in scenarios where the drifts are negative intrinsic gradients of convex mean-field potential functionals, we use entropy and functional inequalities to demonstrate that the stationary measures of the self-interacting processes approximate the invariant measures of the corresponding McKean--Vlasov processes. As an application, we show how to learn the optimal weights of a two-layer neural network by training a single neuron., Comment: 42 pages, 1 figure; contains a minor correction

Each connected graded, graded-commutative algebra $A$ of finite type over a field $\Bbbk$ of characteristic zero defines a complex of finitely generated, graded modules over a symmetric algebra, whose homology graded modules are called the (higher) Koszul modules of $A$. In this note, we investigate the geometry of the support loci of these modules, called the resonance schemes of the algebra. When $A=\Bbbk\langle \Delta \rangle$ is the exterior Stanley-Reisner algebra associated to a finite simplicial complex $\Delta$, we show that the resonance schemes are reduced. We also compute the Hilbert series of the Koszul modules and give bounds on the regularity and projective dimension of these graded modules. This leads to a relationship between resonance and Hilbert series that generalizes a known formula for the Chen ranks of a right-angled Artin group., Comment: 17 pages; accepted for publication in Journal of Algebraic Combinatorics

We present an investigation regarding the challenges faced by student teams across four consecutive iterations of a team-focused, project-based course in software engineering. The studied period includes the switch to fully online activities in the spring of 2020, and covers the return to face-to-face teaching two years later. We cover the feedback provided by over 1,500 students, collected in a free-text form on the basis of a survey. A qualitative research method was utilized to discern and examine the challenges and perceived benefits of a course that was conducted entirely online. We show that technical challenges remain a constant in project-based courses, with time management being the most affected by the move to online. Students reported that the effective use of collaborative tools eased team organization and communication while online. We conclude by providing a number of action points regarding the integration of online activities in face-to-face course unfolding related to project management, communication tools, the importance of teamwork, and of active mentor participation., Comment: 12 pages, 2 figures

In this paper we investigate the problem of quantifying the contribution of each variable to the satisfying assignments of a Boolean function based on the Shapley value. Our main result is a polynomial-time equivalence between computing Shapley values and model counting for any class of Boolean functions that are closed under substitutions of variables with disjunctions of fresh variables. This result settles an open problem raised in prior work, which sought to connect the Shapley value computation to probabilistic query evaluation. We show two applications of our result. First, the Shapley values can be computed in polynomial time over deterministic and decomposable circuits, since they are closed under OR-substitutions. Second, there is a polynomial-time equivalence between computing the Shapley value for the tuples contributing to the answer of a Boolean conjunctive query and counting the models in the lineage of the query. This equivalence allows us to immediately recover the dichotomy for Shapley value computation in case of self-join-free Boolean conjunctive queries; in particular, the hardness for non-hierarchical queries can now be shown using a simple reduction from the #P-hard problem of model counting for lineage in positive bipartite disjunctive normal form., Comment: 22 pages

Estimating the output size of a query is a fundamental yet longstanding problem in database query processing. Traditional cardinality estimators used by database systems can routinely underestimate the true output size by orders of magnitude, which leads to significant system performance penalty. Recently, upper bounds have been proposed that are based on information inequalities and incorporate sizes and max-degrees from input relations, yet they their main benefit is limited to cyclic queries, because they degenerate to rather trivial formulas on acyclic queries. We introduce a significant extension of the upper bounds, by incorporating $\ell_p$-norms of the degree sequences of join attributes. Our bounds are significantly lower than previously known bounds, even when applied to acyclic queries. These bounds are also based on information theory, they come with a matching query evaluation algorithm, are computable in exponential time in the query size, and are provably tight when all degrees are "simple".

In previous work, we introduced the notion of binomial cup-one algebras, which are differential graded algebras endowed with Steenrod $\cup_1$-products and compatible binomial operations. Given such an $R$-dga, $(A,d_A)$, defined over the ring $R=\mathbb{Z}$ or $\mathbb{Z}_p$ (for $p$ a prime), with $H^0(A)=R$ and with $H^1(A)$ a finitely generated, free $R$-module, we show that $A$ admits a functorially defined 1-minimal model, $\rho\colon (\mathcal{M}(A),d)\to (A,d_A)$, which is unique up to isomorphism. Furthermore, we associate to this model a pronilpotent group, $G(A)$, which only depends on the 1-quasi-isomorphism type of $A$. These constructions, which refine classical notions from rational homotopy theory, allow us to distinguish spaces with isomorphic (torsion-free) cohomology rings that share the same rational 1-minimal model, yet whose integral 1-minimal models are not isomorphic., Comment: 74 pages

Among all the sub-sections in a typical radiology report, the Clinical Indications, Findings, and Impression often reflect important details about the health status of a patient. The information included in Impression is also often covered in Findings. While Findings and Impression can be deduced by inspecting the image, Clinical Indications often require additional context. The cognitive task of interpreting medical images remains the most critical and often time-consuming step in the radiology workflow. Instead of generating an end-to-end radiology report, in this paper, we focus on generating the Findings from automated interpretation of medical images, specifically chest X-rays (CXRs). Thus, this work focuses on reducing the workload of radiologists who spend most of their time either writing or narrating the Findings. Unlike past research, which addresses radiology report generation as a single-step image captioning task, we have further taken into consideration the complexity of interpreting CXR images and propose a two-step approach: (a) detecting the regions with abnormalities in the image, and (b) generating relevant text for regions with abnormalities by employing a generative large language model (LLM). This two-step approach introduces a layer of interpretability and aligns the framework with the systematic reasoning that radiologists use when reviewing a CXR., Comment: Information Technology and Quantitative Management (ITQM 2023)

We apply foundation models to data discovery and exploration tasks. Foundation models include large language models (LLMs) that show promising performance on a range of diverse tasks unrelated to their training. We show that these models are highly applicable to the data discovery and data exploration domain. When carefully used, they have superior capability on three representative tasks: table-class detection, column-type annotation and join-column prediction. On all three tasks, we show that a foundation-model-based approach outperforms the task-specific models and so the state of the art. Further, our approach often surpasses human-expert task performance. We investigate the fundamental characteristics of this approach including generalizability to several foundation models and the impact of non-determinism on the outputs. All in all, this suggests a future direction in which disparate data management tasks can be unified under foundation models., Comment: To appear in VLDB 2024

The paper describes several applications of information inequalities to problems in database theory. The problems discussed include: upper bounds of a query's output, worst-case optimal join algorithms, the query domination problem, and the implication problem for approximate integrity constraints. The paper is self-contained: all required concepts and results from information inequalities are introduced here, gradually, and motivated by database problems., Comment: This paper was invited for LICS'2023

Quantum communications bring a paradigm change in internet security by using quantum resources to establish secure keys between parties. Present-day quantum communications networks are mainly point-to-point and use trusted nodes and key management systems to relay the keys. Future quantum networks, including the quantum internet, will have complex topologies in which groups of users are connected and communicate with each-other. Here we investigate several architectures for quantum communication networks. We show that photonic orbital angular momentum (OAM) can be used to route quantum information between different nodes. Starting from a simple, point-to-point network, we will gradually develop more complex architectures: point-to-multipoint, fully-connected and entanglement-distribution networks. As a particularly important result, we show that an $n$-node, fully-connected network can be constructed with a single OAM sorter and $n-1$ OAM values. Our results pave the way to construct complex quantum communication networks with minimal resources., Comment: updated to the published version

The resonance varieties are cohomological invariants that are studied in a variety of topological, combinatorial, and geometric contexts. We discuss their scheme structure in a general algebraic setting and introduce various properties that ensure the reducedness of the associated projective resonance scheme. We prove an asymptotic formula for the Hilbert series of the associated Koszul module, then discuss applications to vector bundles on algebraic curves and to Chen ranks formulas for finitely generated groups, with special emphasis on K\"ahler and right-angled Artin groups., Comment: 36 pages. Final version, to appear in the Journal fuer die reine und angewandte Mathematik (Crelle)

The number of disclosed vulnerabilities has been steadily increasing over the years. At the same time, organizations face significant challenges patching their systems, leading to a need to prioritize vulnerability remediation in order to reduce the risk of attacks. Unfortunately, existing vulnerability scoring systems are either vendor-specific, proprietary, or are only commercially available. Moreover, these and other prioritization strategies based on vulnerability severity are poor predictors of actual vulnerability exploitation because they do not incorporate new information that might impact the likelihood of exploitation. In this paper we present the efforts behind building a Special Interest Group (SIG) that seeks to develop a completely data-driven exploit scoring system that produces scores for all known vulnerabilities, that is freely available, and which adapts to new information. The Exploit Prediction Scoring System (EPSS) SIG consists of more than 170 experts from around the world and across all industries, providing crowd-sourced expertise and feedback. Based on these collective insights, we describe the design decisions and trade-offs that lead to the development of the next version of EPSS. This new machine learning model provides an 82\% performance improvement over past models in distinguishing vulnerabilities that are exploited in the wild and thus may be prioritized for remediation.

Over the last decade, worst-case optimal join (WCOJ) algorithms have emerged as a new paradigm for one of the most fundamental challenges in query processing: computing joins efficiently. Such an algorithm can be asymptotically faster than traditional binary joins, all the while remaining simple to understand and implement. However, they have been found to be less efficient than the old paradigm, traditional binary join plans, on the typical acyclic queries found in practice. Some database systems that support WCOJ use a hypbrid approach: use WCOJ to process the cyclic subparts of the query (if any), and rely on traditional binary joins otherwise. In this paper we propose a new framework, called Free Join, that unifies the two paradigms. We describe a new type of plan, a new data structure (which unifies the hash tables and tries used by the two paradigms), and a suite of optimization techniques. Our system, implemented in Rust, matches or outperforms both traditional binary joins and Generic Join on standard query benchmarks.

We give precise asymptotics to the number of random walks in the standard orthogonal lattice in $\mathbb{R}^d$ that return to the starting point at step $2n$, both for all such walks and for the ones that return for the first time. The first set of asymptotics is obtained in an elementary way, by using a combinatorial and geometric multiplication principle together with the classical theory of Legendre polynomials. As an easy consequence we obtain a unified proof of P\'{o}lya's theorem. By showing that the relevant generating functions are $\Delta$-analytic, we use the deeper Tauberian theory of singularity analysis to obtain the asymptotics for the first return paths., Comment: 26 pages, 6 figures

We propose quasi-stable coloring, an approximate version of stable coloring. Stable coloring, also called color refinement, is a well-studied technique in graph theory for classifying vertices, which can be used to build compact, lossless representations of graphs. However, its usefulness is limited due to its reliance on strict symmetries. Real data compresses very poorly using color refinement. We propose the first, to our knowledge, approximate color refinement scheme, which we call quasi-stable coloring. By using approximation, we alleviate the need for strict symmetry, and allow for a tradeoff between the degree of compression and the accuracy of the representation. We study three applications: Linear Programming, Max-Flow, and Betweenness Centrality, and provide theoretical evidence in each case that a quasi-stable coloring can lead to good approximations on the reduced graph. Next, we consider how to compute a maximal quasi-stable coloring: we prove that, in general, this problem is NP-hard, and propose a simple, yet effective algorithm based on heuristics. Finally, we evaluate experimentally the quasi-stable coloring technique on several real graphs and applications, comparing with prior approximation techniques. A reference implementation and the experiment code are available at https://github.com/mkyl/QuasiStableColors.jl ., Comment: To be presented at VLDB 2023

Recent work has reemphasized the importance of cardinality estimates for query optimization. While new techniques have continuously improved in accuracy over time, they still generally allow for under-estimates which often lead optimizers to make overly optimistic decisions. This can be very costly for expensive queries. An alternative approach to estimation is cardinality bounding, also called pessimistic cardinality estimation, where the cardinality estimator provides guaranteed upper bounds of the true cardinality. By never underestimating, this approach allows the optimizer to avoid potentially inefficient plans. However, existing pessimistic cardinality estimators are not yet practical: they use very limited statistics on the data, and cannot handle predicates. In this paper, we introduce SafeBound, the first practical system for generating cardinality bounds. SafeBound builds on a recent theoretical work that uses degree sequences on join attributes to compute cardinality bounds, extends this framework with predicates, introduces a practical compression method for the degree sequences, and implements an efficient inference algorithm. Across four workloads, SafeBound achieves up to 80% lower end-to-end runtimes than PostgreSQL, and is on par or better than state of the art ML-based estimators and pessimistic cardinality estimators, by improving the runtime of the expensive queries. It also saves up to 500x in query planning time, and uses up to 6.8x less space compared to state of the art cardinality estimation methods.