Search

In a Note in this Monthly, Klazar raised the question of whether the alternating sum of the Stirling numbers of the second kind $B^\pm(n)=\sum_{k=0}^n(-1)^kS(n,k)$ is ever zero for $n\neq 2$. In this article, we present an exposition of the history of this problem, and an economical account of a recent proof that there is at most one $n\neq 2$ for which $B^\pm(n)=0$., Comment: 19 page, 1 figure

We introduce a new infinite family of regular graphs admitting nested solutions in the edge-isoperimetric problem for all their Cartesian powers. The obtained results include as special cases most of previously known results in this area.

We define an extension of predicate logic, called Binding Logic, where variables can be bound in terms and in propositions. We introduce a notion of model for this logic and prove a soundness and completeness theorem for it. This theorem is obtained by encoding this logic back into predicate logic and using the classical soundness and completeness theorem there., Comment: Colloque avec actes et comit{\'e} de lecture. internationale

The origins of proof-theoretic semantics lie in the question of what constitutes the meaning of the logical connectives and its response: the rules of inference that govern the use of the connective. However, what if we go a step further and ask about the meaning of a proof as a whole? In this paper we address this question and lay out a framework to distinguish sense and denotation of proofs. Two questions are central here. First of all, if we have two (syntactically) different derivations, does this always lead to a difference, firstly, in sense, and secondly, in denotation? The other question is about the relation between different kinds of proof systems (here: natural deduction vs. sequent calculi) with respect to this distinction. Do the different forms of representing a proof necessarily correspond to a difference in how the inferential steps are given? In our framework it will be possible to identify denotation as well as sense of proofs not only within one proof system but also between different kinds of proof systems. Thus, we give an account to distinguish a mere syntactic divergence from a divergence in meaning and a divergence in meaning from a divergence of proof objects analogous to Frege's distinction for singular terms and sentences., Comment: Post-peer-review, pre-copyedit version of article, published version available open access under DOI: 10.1007/s10992-020-09577-2

Modifying standard gradient boosting by replacing the embedded weak learner in favor of a strong(er) one, we present SyRBo: Symbolic-Regression Boosting. Experiments over 98 regression datasets show that by adding a small number of boosting stages -- between 2--5 -- to a symbolic regressor, statistically significant improvements can often be attained. We note that coding SyRBo on top of any symbolic regressor is straightforward, and the added cost is simply a few more evolutionary rounds. SyRBo is essentially a simple add-on that can be readily added to an extant symbolic regressor, often with beneficial results.

Aggregate signatures are used to create one short proof of authenticity and integrity from a set of digital signatures. However, one invalid signature in the set invalidates the entire aggregate, giving no information on which signatures are valid. Hartung et al. (2016) propose a fault-tolerant aggregate signature scheme based on combinatorial group testing. Given a bound $d$ on the number of invalid signatures among $n$ signatures to be aggregated, this scheme uses $d$-cover-free families to determine which signatures are invalid. These combinatorial structures guarantee a moderate increase on the size of the aggregate signature that can reach the best possible compression ratio of $O(\frac{n}{\log n})$, for fixed $d$, coming from an information theoretical bound. The case where the total number of signatures grows dynamically (unbounded scheme) was not satisfactorily solved in their original paper, since explicit constructions had constant compression ratios. In the present paper, we propose efficient solutions for the unbounded scheme, relying on sequences of $d$-cover-free families that we call {\em nested families}. Some of our constructions yield high compression ratio close to \rmv{the information theoretical bound}\todo{the best known upper bound}. We also propose the use of $(d,\lambda)$-cover-free families to support the loss of up to $\lambda-1$ parts of the aggregate., Comment: 30 pages

State grammars are context-free grammars where the productions have states associated with them, and a production can only be applied to a nonterminal if the current state matches the state in the production. Once states are added to grammars, it is natural to add various stores, similar to machine models. With such extensions, productions can only be applied if both the state and the value read from each store matches between the current sentential form and the production. Here, generative capacity results are presented for different derivation modes, with and without additional stores. In particular, with the standard derivation relation, it is shown that adding reversal-bounded counters does not increase the capacity, and states are enough. Also, state grammars with reversal-bounded counters that operate using leftmost derivations are shown to coincide with languages accepted by one-way machines with a pushdown and reversal-bounded counters, and these are surprisingly shown to be strictly weaker than state grammars with the standard derivation relation (and no counters). The complexity of the emptiness problem involving state grammars with reversal-bounded counters is also studied., Comment: 21 pages

We prove an asymptotic formula for the number of representations of squares by nonsingular cubic forms in six or more variables. The main ingredients of the proof are Heath-Brown's form of the Circle Method and various exponential sum results. The depth of the exponential sum results is comparable to Hooley's work on cubic forms in nine variables, in particular we prove an analogue of Katz' bound., Comment: 29 pages. Arxiv upload of older paper. Published in Isr. J. Math

A finite dynamical system with $n$ components is a function $f:X\to X$ where $X=X_1\times\dots\times X_n$ is a product of $n$ finite intervals of integers. The structure of such a system $f$ is represented by a signed digraph $G$, called interaction graph: there are $n$ vertices, one per component, and the signed arcs describe the positive and negative influences between them. Finite dynamical systems are usual models for gene networks. In this context, it is often assumed that $f$ is {\em degree-bounded}, that is, the size of each $X_i$ is at most the out-degree of $i$ in $G$ plus one. Assuming that $G$ is connected and that $f$ is degree-bounded, we prove the following: if $G$ is not a cycle, then $f^{n+1}$ may be a constant. In that case, $f$ describes a very simple dynamics: a global convergence toward a unique fixed point in $n+1$ iterations. This shows that, in the degree-bounded case, the fact that $f$ describes a complex dynamics {\em cannot} be deduced from its interaction graph. We then widely generalize the above result, obtaining, as immediate consequences, other limits on what can be deduced from the interaction graph only, as the following weak converses of Thomas' rules: if $G$ is connected and has a positive (negative) cycle, then $f$ may have two (no) fixed points., Comment: 21 pages

We consider the following oblivious sketching problem: given $\epsilon \in (0,1/3)$ and $n \geq d/\epsilon^2$, design a distribution $\mathcal{D}$ over $\mathbb{R}^{k \times nd}$ and a function $f: \mathbb{R}^k \times \mathbb{R}^{nd} \rightarrow \mathbb{R}$, so that for any $n \times d$ matrix $A$, $$\Pr_{S \sim \mathcal{D}} [(1-\epsilon) \|A\|_{op} \leq f(S(A),S) \leq (1+\epsilon)\|A\|_{op}] \geq 2/3,$$ where $\|A\|_{op}$ is the operator norm of $A$ and $S(A)$ denotes $S \cdot A$, interpreting $A$ as a vector in $\mathbb{R}^{nd}$. We show a tight lower bound of $k = \Omega(d^2/\epsilon^2)$ for this problem. Our result considerably strengthens the result of Nelson and Nguyen (ICALP, 2014), as it (1) applies only to estimating the operator norm, which can be estimated given any OSE, and (2) applies to distributions over general linear operators $S$ which treat $A$ as a vector and compute $S(A)$, rather than the restricted class of linear operators corresponding to matrix multiplication. Our technique also implies the first tight bounds for approximating the Schatten $p$-norm for even integers $p$ via general linear sketches, improving the previous lower bound from $k = \Omega(n^{2-6/p})$ [Regev, 2014] to $k = \Omega(n^{2-4/p})$. Importantly, for sketching the operator norm up to a factor of $\alpha$, where $\alpha - 1 = \Omega(1)$, we obtain a tight $k = \Omega(n^2/\alpha^4)$ bound, matching the upper bound of Andoni and Nguyen (SODA, 2013), and improving the previous $k = \Omega(n^2/\alpha^6)$ lower bound. Finally, we also obtain the first lower bounds for approximating Ky Fan norms., Comment: Appeared in the Proceedings of RANDOM/APPROX 2016. The current version corrects the proof of Corollary 7

We propose a notion of alternating bisimulation for strategic abilities under imperfect information. The bisimulation preserves formulas of ATL$^*$ for both the {\em objective} and {\em subjective} variants of the state-based semantics with imperfect information, which are commonly used in the modeling and verification of multi-agent systems. Furthermore, we apply the theoretical result to the verification of coercion-resistance in the ThreeBallot voting system, a voting protocol that does not use cryptography. In particular, we show that natural simplifications of an initial model of the protocol are in fact bisimulations of the original model, and therefore satisfy the same ATL$^*$ properties, including coercion-resistance. These simplifications allow the model-checking tool MCMAS to terminate on models with a larger number of voters and candidates, compared with the initial model.

The Orienteering Problem with Time Window and Delay ( OPTiWinD ) is a variant of the online orienteering problem. A series of requests appear in various locations while a vehicle moves within the territory to serve them. Each request has a time window during which it can be served and a weight which describes its importance. There is also a minimum delay T between successive requests. The objective is to find a path for the vehicles that maximises the sum of the weights of the requests served. We further assume that the length of each time window is equal to the diameter of the territory. We study the optimal performance and competitive ratio for the set of instances with n requests. We obtain complete resolution for T at least half of the diameter, small values of T or small values of n, as well as partial results in the remaining cases.

In this note, I find a new property of the congruence lattice, $${{\,\mathrm{Con}\,}}L$$, of an SPS lattice L (slim, planar, semimodular, where “slim” is the absence of $${\mathsf {M}}_3$$ sublattices) with more than 2 elements: there are at least two dual atoms in$${{\,\mathrm{Con}\,}}L$$. So the three-element chain cannot be represented as the congruence lattice of an SPS lattice, supplementing a result of G. Czedli.

We study finite groups $G$ having a normal subgroup $H$ and $D \subset G \setminus H, D \cap D^{-1}=\emptyset,$ such that the multiset $\{ xy^{-1}:x,y \in D\}$ has every non-identity element occur the same number of times (such a $D$ is called a {\it DRAD difference set}). We show that there are no such groups of order $4p^2$, where $p$ is an odd prime., Comment: 15 pages

Coflow scheduling improves data-intensive application performance by improving their networking performance. State-of-the-art Coflow schedulers in essence approximate the classic online Shortest-Job-First (SJF) scheduling, designed for a single CPU, in a distributed setting, with no coordination among how the flows of a Coflow at individual ports are scheduled, and as a result suffer two performance drawbacks: (1) The flows of a Coflow may suffer the out-of-sync problem -- they may be scheduled at different times and become drifting apart, negatively affecting the Coflow completion time (CCT); (2) FIFO scheduling of flows at each port bears no notion of SJF, leading to suboptimal CCT. We propose SAATH, an online Coflow scheduler that overcomes the above drawbacks by explicitly exploiting the spatial dimension of Coflows. In SAATH, the global scheduler schedules the flows of a Coflow using an all-or-none policy which mitigates the out-of-sync problem. To order the Coflows within each queue, SAATH resorts to a Least-Contention-First (LCoF) policy which we show extends the gist of SJF to the spatial dimension, complemented with starvation freedom. Our evaluation using an Azure testbed and simulations of two production cluster traces show that compared to Aalo, SAATH reduces the CCT in median (P90) cases by 1.53x (4.5x) and 1.42x (37x), respectively.

Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these values right for a particular problem (parameter tuning) is a challenging task. This task becomes even more complicated when the optimal parameter values change significantly during the run of the algorithm since then a dynamic parameter choice (parameter control) is necessary. In this work, we propose a lazy but effective solution, namely choosing all parameter values (where this makes sense) in each iteration randomly from a suitably scaled power-law distribution. To demonstrate the effectiveness of this approach, we perform runtime analyses of the $(1+(\lambda,\lambda))$ genetic algorithm with all three parameters chosen in this manner. We show that this algorithm on the one hand can imitate simple hill-climbers like the $(1+1)$ EA, giving the same asymptotic runtime on problems like OneMax, LeadingOnes, or Minimum Spanning Tree. On the other hand, this algorithm is also very efficient on jump functions, where the best static parameters are very different from those necessary to optimize simple problems. We prove a performance guarantee that is comparable to the best performance known for static parameters. For the most interesting case that the jump size $k$ is constant, we prove that our performance is asymptotically better than what can be obtained with any static parameter choice. We complement our theoretical results with a rigorous empirical study confirming what the asymptotic runtime results suggest., Comment: Extended version of the paper that appeared at GECCO 2021. To appear in Algorithmica

We study computational aspects of a well-known single-winner voting rule called the Schulze method [Schulze, 2003] which is used broadly in practice. In this method the voters give (weak) ordinal preference ballots which are used to define the weighted majority graph (WMG) of direct comparisons between pairs of candidates. The choice of the winner comes from indirect comparisons in the graph, and more specifically from considering directed paths instead of direct comparisons between candidates. When the input is the WMG, to our knowledge, the fastest algorithm for computing all winners in the Schulze method uses a folklore reduction to the All-Pairs Bottleneck Paths problem and runs in $O(m^{2.69})$ time, where $m$ is the number of candidates. It is an interesting open question whether this can be improved. Our first result is a combinatorial algorithm with a nearly quadratic running time for computing all winners. This running time is essentially optimal. If the input to the Schulze winners problem is not the WMG but the preference profile, then constructing the WMG is a bottleneck that increases the running time significantly; in the special case when there are $m$ candidates and $n=O(m)$ voters, the running time is $O(m^{2.69})$, or $O(m^{2.5})$ if there is a nearly-linear time algorithm for multiplying dense square matrices. To address this bottleneck, we prove a formal equivalence between the well-studied Dominance Product problem and the problem of computing the WMG. We prove a similar connection between the so called Dominating Pairs problem and the problem of finding a winner in the Schulze method. Our paper is the first to bring fine-grained complexity into the field of computational social choice. Using it we can identify voting protocols that are unlikely to be practical for large numbers of candidates and/or voters, as their complexity is likely, say at least cubic., Comment: 19 pages, 2 algorithms, 2 tables. A previous version of this work appears in EC 2021. In this version we strengthen Theorem 6.2 which now holds also for the problem of finding a Schulze winner

We construct the generating function for products of inverse central binomial coefficients with harmonic numbers., Comment: 9 pages

We study theta-joins in general and join predicates with conjunctions and disjunctions of inequalities in particular, focusing on ranked enumeration where the answers are returned incrementally in an order dictated by a given ranking function. Our approach achieves strong time and space complexity properties: with $n$ denoting the number of tuples in the database, we guarantee for acyclic full join queries with inequality conditions that for every value of $k$, the $k$ top-ranked answers are returned in $\mathcal{O}(n \operatorname{polylog} n + k \log k)$ time. This is within a polylogarithmic factor of $\mathcal{O}(n + k \log k)$, i.e., the best known complexity for equi-joins, and even of $\mathcal{O}(n+k)$, i.e., the time it takes to look at the input and return $k$ answers in any order. Our guarantees extend to join queries with selections and many types of projections (namely those called "free-connex" queries and those that use bag semantics). Remarkably, they hold even when the number of join results is $n^\ell$ for a join of $\ell$ relations. The key ingredient is a novel $\mathcal{O}(n \operatorname{polylog} n)$-size factorized representation of the query output, which is constructed on-the-fly for a given query and database. In addition to providing the first non-trivial theoretical guarantees beyond equi-joins, we show in an experimental study that our ranked-enumeration approach is also memory-efficient and fast in practice, beating the running time of state-of-the-art database systems by orders of magnitude., Comment: 21 pages

We study the communication complexity of incentive compatible auction-protocols between a monopolist seller and a single buyer with a combinatorial valuation function over $n$ items. Motivated by the fact that revenue-optimal auctions are randomized [Tha04,MV10,BCKW10,Pav11,HR15] (as well as by an open problem of Babaioff, Gonczarowski, and Nisan [BGN17]),we focus on the randomized communication complexity of this problem (in contrast to most prior work on deterministic communication). We design simple, incentive compatible, and revenue-optimal auction-protocols whose expected communication complexity is much (in fact infinitely) more efficient than their deterministic counterparts. We also give nearly matching lower bounds on the expected communication complexity of approximately-revenue-optimal auctions. These results follow from a simple characterization of incentive compatible auction-protocols that allows us to prove lower bounds against randomized auction-protocols. In particular, our lower bounds give the first approximation-resistant, exponential separation between communication complexity of incentivizing vs implementing a Bayesian incentive compatible social choice rule, settling an open question of Fadel and Segal [FS09].

Esparza and Reiter have recently conducted a systematic comparative study of models of distributed computing consisting of a network of identical finite-state automata that cooperate to decide if the underlying graph of the network satisfies a given property. The study classifies models according to four criteria, and shows that twenty initially possible combinations collapse into seven equivalence classes with respect to their decision power, i.e. the properties that the automata of each class can decide. However, Esparza and Reiter only show (proper) inclusions between the classes, and so do not characterise their decision power. In this paper we do so for labelling properties, i.e. properties that depend only on the labels of the nodes, but not on the structure of the graph. In particular, majority (whether more nodes carry label $a$ than $b$) is a labelling property. Our results show that only one of the seven equivalence classes identified by Esparza and Reiter can decide majority for arbitrary networks. We then study the expressive power of the classes on bounded-degree networks, and show that three classes can. In particular, we present an algorithm for majority that works for all bounded-degree networks under adversarial schedulers, i.e. even if the scheduler must only satisfy that every node makes a move infinitely often, and prove that no such algorithm can work for arbitrary networks., Various minor revisions

Designing optimal soft modular robots is difficult, due to non-trivial interactions between morphology and controller. Evolutionary algorithms (EAs), combined with physical simulators, represent a valid tool to overcome this issue. In this work, we investigate algorithmic solutions to improve the Quality Diversity of co-evolved designs of Tensegrity Soft Modular Robots (TSMRs) for two robotic tasks, namely goal reaching and squeezing trough a narrow passage. To this aim, we use three different EAs, i.e., MAP-Elites and two custom algorithms: one based on Viability Evolution (ViE) and NEAT (ViE-NEAT), the other named Double Map MAP-Elites (DM-ME) and devised to seek diversity while co-evolving robot morphologies and neural network (NN)-based controllers. In detail, DM-ME extends MAP-Elites in that it uses two distinct feature maps, referring to morphologies and controllers respectively, and integrates a mechanism to automatically define the NN-related feature descriptor. Considering the fitness, in the goal-reaching task ViE-NEAT outperforms MAP-Elites and results equivalent to DM-ME. Instead, when considering diversity in terms of "illumination" of the feature space, DM-ME outperforms the other two algorithms on both tasks, providing a richer pool of possible robotic designs, whereas ViE-NEAT shows comparable performance to MAP-Elites on goal reaching, although it does not exploit any map., Comment: To be published in the proceedings of ACM Genetic and Evolutionary Computation Conference (GECCO) 2021

Multiparty sessions with asynchronous communications and global types play an important role for the modelling of interaction protocols in distributed systems. In designing such calculi the aim is to enforce, by typing, good properties for all participants, maximising, at the same time, the accepted behaviours. Our type system improves the state-of-the-art by typing all asynchronous sessions and preserving the key properties of Subject Reduction, Session Fidelity and Progress when some well-formedness conditions are satisfied. The type system comes together with a sound and complete type inference algorithm. The well-formedness conditions are undecidable, but an algorithm checking an expressive restriction of them recovers the effectiveness of typing.

In the load balancing problem, each node in a network is assigned a load, and the goal is to equally distribute the loads among the nodes, by preforming local load exchanges. While load balancing was extensively studied in static networks, only recently a load balancing algorithm for dynamic networks with a bounded convergence time was presented. In this paper, we further study the time complexity of load balancing in the context of dynamic networks. First, we show that randomness is not necessary, and present a deterministic algorithm which slightly improves the running time of the previous algorithm, at the price of not being matching-based. Then, we consider integral loads, i.e., loads that cannot be split indefinitely, and prove that no matching-based algorithm can have a bounded convergence time for this case. To circumvent both this impossibility result, and a known one for the non-integral case, we apply the method of smoothed analysis, where random perturbations are made over the worst-case choices of network topologies. We show both impossibility results do not hold under this kind of analysis, suggesting that load-balancing in real world systems might be faster than the lower bounds suggest., Comment: To be presented in SPAA 2021

We review probabilistic models known as majority dynamics (also known as threshold Voter Models) and discuss their possible applications for achieving consensus in cryptocurrency systems. In particular, we show that using this approach straightforwardly for practical consensus in Byzantine setting can be problematic and requires extensive further research. We then discuss the FPC consensus protocol which circumvents the problems mentioned above by using external randomness., Comment: revised version, accepted in Annals of Telecommunications

There is a local ring $E$ of order $4,$ without identity for the multiplication, defined by generators and relations as $E=\langle a,b \mid 2a=2b=0,\, a^2=a,\, b^2=b,\,ab=a,\, ba=b\rangle.$ We study a special construction of self-orthogonal codes over $E,$ based on combinatorial matrices related to two-class association schemes, Strongly Regular Graphs (SRG), and Doubly Regular Tournaments (DRT). We construct quasi self-dual codes over $E,$ and Type IV codes, that is, quasi self-dual codes whose all codewords have even Hamming weight. All these codes can be represented as formally self-dual additive codes over $\F_4.$ The classical invariant theory bound for the weight enumerators of this class of codesimproves the known bound on the minimum distance of Type IV codes over $E.$, Comment: 18 pages

Column replacement techniques for creating covering arrays rely on the construction of perfect and distributing hash families with few rows, having as many columns as possible for a specified number of symbols. To construct distributing hash families in which the number of rows is less than the strength, we examine a method due to Blackburn and extend it in three ways. First, the method is generalized from homogeneous hash families (in which every row has the same number of symbols) to heterogeneous ones. Second, the extension treats distributing hash families, in which only separation into a prescribed number of parts is required, rather than perfect hash families, in which columns must be completely separated. Third, the requirements on one of the main ingredients are relaxed to permit the use of a large class of distributing hash families, which we call fractal. Constructions for fractal perfect and distributing hash families are given, and applications to the construction of perfect hash families of large strength are developed., Comment: 21 pages, 0 figures

In this paper, we generalize to the context of algebras some recent results on the existence of common hypercyclic vectors for families of products of backward shift operators. We also give, in a multi-dimensional setting, a positive answer to a question raised by F. Bayart, D. Papathanasiou and the author about the existence of a common hypercyclic algebra on l 1 ( N ) with the convolution product for the family of backward shifts ( B w ( λ ) ) λ > 0 induced by the weights w n ( λ ) = 1 + λ / n .

Differential MAP-Elites is a novel algorithm that combines the illumination capacity of CVT-MAP-Elites with the continuous-space optimization capacity of Differential Evolution. The algorithm is motivated by observations that illumination algorithms, and quality-diversity algorithms in general, offer qualitatively new capabilities and applications for evolutionary computation yet are in their original versions relatively unsophisticated optimizers. The basic Differential MAP-Elites algorithm, introduced for the first time here, is relatively simple in that it simply combines the operators from Differential Evolution with the map structure of CVT-MAP-Elites. Experiments based on 25 numerical optimization problems suggest that Differential MAP-Elites clearly outperforms CVT-MAP-Elites, finding better-quality and more diverse solutions.

For non-negative integers $$l_{1}, l_{2},\ldots , l_{n}$$ , we define character sums $$\varphi _{(l_{1}, l_{2},\ldots , l_{n})}$$ and $$\psi _{(l_{1}, l_{2},\ldots , l_{n})}$$ over a finite field which are generalizations of Jacobsthal and modified Jacobsthal sums, respectively. We express these character sums in terms of Greene’s finite field hypergeometric series. We then express the number of points on the hyperelliptic curves $$y^2=(x^m+a)(x^m+b)(x^m+c)$$ and $$y^2=x(x^m+a)(x^m+b)(x^m+c)$$ over a finite field in terms of the character sums $$\varphi _{(l_{1}, l_{2}, l_{3})}$$ and $$\psi _{(l_{1}, l_{2}, l_{3})}$$ , and finally obtain expressions in terms of the finite field hypergeometric series.

It is well known that for all $n\geq1$ the number $n+ 1$ is a divisor of the central binomial coefficient ${2n\choose n}$. Since the $n$th central binomial coefficient equals the number of lattice paths from $(0,0)$ to $(n,n)$ by unit steps north or east, a natural question is whether there is a way to partition these paths into sets of $n+ 1$ paths or $n+1$ equinumerous sets of paths. The Chung-Feller theorem gives an elegant answer to this question. We pose and deliver an answer to the analogous question for $2n-1$, another divisor of ${2n\choose n}$. We then show our main result follows from a more general observation regarding binomial coefficients ${n\choose k}$ with $n$ and $k$ relatively prime. A discussion of the case where $n$ and $k$ are not relatively prime is also given, highlighting the limitations of our methods. Finally, we come full circle and give a novel interpretation of the Catalan numbers., Comment: 16 pages, 11 figures, 1 table

Genetic Programming (GP) is known to suffer from the burden of being computationally expensive by design. While, over the years, many techniques have been developed to mitigate this issue, data vectorization, in particular, is arguably still the most attractive strategy due to the parallel nature of GP. In this work, we employ a series of benchmarks meant to compare both the performance and evolution capabilities of different vectorized and iterative implementation approaches across several existing frameworks. Namely, TensorGP, a novel open-source engine written in Python, is shown to greatly benefit from the TensorFlow library to accelerate the domain evaluation phase in GP. The presented performance benchmarks demonstrate that the TensorGP engine manages to pull ahead, with relative speedups above two orders of magnitude for problems with a higher number of fitness cases. Additionally, as a consequence of being able to compute larger domains, we argue that TensorGP performance gains aid the discovery of more accurate candidate solutions.

A numerical semigroup $S$ is cyclotomic if its semigroup polynomial $P_S$ is a product of cyclotomic polynomials. The number of irreducible factors of $P_S$ (with multiplicity) is the polynomial length $\ell(S)$ of $S.$ We show that a cyclotomic numerical semigroup is complete intersection if $\ell(S)\le 2$. This establishes a particular case of a conjecture of Ciolan, Garc\'{i}a-S\'{a}nchez and Moree (2016) claiming that every cyclotomic numerical semigroup is complete intersection. In addition, we investigate the relation between $\ell(S)$ and the embedding dimension of $S.$, Comment: 15 pages

The concept of balancedly splittable orthogonal designs is introduced along with a recursive construction. As an application, equiangular tight frames over the real, complex, and quaternions meeting the Delsarte-Goethals-Seidel upper bound is obtained., Comment: 17 pages

Science Information Network (SINET) is a Japanese academic backbone network for more than 800 research institutions and universities. In this paper, we present a multi-GPU-driven pipeline for handling huge session data of SINET. Our pipeline consists of ELK stack, multi-GPU server, and Splunk. A multi-GPU server is responsible for two procedures: discrimination and histogramming. Discrimination is dividing session data into ingoing/outgoing with subnet mask calculation and network address matching. Histogramming is grouping ingoing/outgoing session data into bins with map-reduce. In our architecture, we use GPU for the acceleration of ingress/egress discrimination of session data. Also, we use a tiling design pattern for building a two-stage map-reduce of CPU and GPU. Our multi-GPU-driven pipeline has succeeded in processing huge workloads of about 1.2 to 1.6 billion session streams (500GB-650GB) within 24 hours., Comment: This is an Accepted Manuscript of an article published by Taylor & Francis Group in the International Journal of Parallel, Emergent & Distributed Systems on 24/06/2021 av lable online: http://www.tandfonline.com/ DOI: 10.1080/17445760.2021.1941009

Over the last few years, the concept of Artificial Intelligence has become central in different tasks concerning both our daily life and several working scenarios. Among these tasks automated planning has always been central in the AI research community. In particular, this manuscript is focused on a specialized kind of planning known as Multi-agent Epistemic Planning (MEP). Epistemic Planning (EP) refers to an automated planning setting where the agent reasons in the space of knowledge/beliefs states and tries to find a plan to reach a desirable state from a starting one. Its general form, the MEP problem, involves multiple agents who need to reason about both the state of the world and the information flows between agents. To tackle the MEP problem several tools have been developed and, while the diversity of approaches has led to a deeper understanding of the problem space, each proposed tool lacks some abilities and does not allow for a comprehensive investigation of the information flows. That is why, the objective of our work is to formalize an environment where a complete characterization of the agents' knowledge/beliefs interaction and update is possible. In particular, we aim to achieve such goal by defining a new action-based language for multi-agent epistemic planning and to implement an epistemic planner based on it. This solver should provide a tool flexible enough to reason on different domains, e.g., economy, security, justice and politics, where considering others' knowledge/beliefs could lead to winning strategies., Comment: In Proceedings ICLP 2021, arXiv:2109.07914. arXiv admin note: substantial text overlap with arXiv:1909.08259

Recently, Haynes, Hedetniemi and Henning published the book Topics in Domination in Graphs, which comprises 16 contributions that present advanced topics in graph domination, featuring open problems, modern techniques, and recent results. One of these contributions is the chapter Multiple Domination, by Hansberg and Volkmann, where they put into context all relevant research results on multiple domination that have been found up to 2020. In this note, we show how to improve some results on double domination that are included in the book.

Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths – also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths.

In this paper, we present two sharp upper bounds for the spectral radius of (bipartite) graphs with forbidden a star forest and characterize all extremal graphs. Moreover, the minimum least eigenvalue of the adjacency matrix of graph with forbidden a star forest and all extremal graphs for graphs are obtained., Comment: 15 pages

We propose to demonstrate a network slice placement optimization solution based on Deep Reinforcement Learning (DRL), referred to as Heuristically-controlled DRL, which uses a heuristic to control the DRL algorithm convergence. The solution is adapted to realistic networks with large scale and under non-stationary traffic conditions (namely, the network load). We demonstrate the applicability of the proposed solution and its higher and stable performance over a non-controlled DRL-based solution. Demonstration scenarios include full online learning with multiple volatile network slice placement request arrivals., Comment: arXiv admin note: substantial text overlap with arXiv:2010.08295

This paper introduces a novel entanglement-based QKD protocol, that makes use of a modified symmetric version of the Bernstein-Vazirani algorithm, in order to achieve a secure and efficient key distribution. Two variants of the protocol, one fully symmetric and one semi-symmetric, are presented. In both cases, the spatially separated Alice and Bob share multiple EPR pairs, one qubit of the pair each. The fully symmetric version allows both parties to input a secret key from the irrespective location and, finally, acquire in the end a totally new and original key, an idea which was inspired by the Diffie-Hellman key exchange protocol. In the semi-symmetric version, Alice sends her chosen secret key to Bob (or vice versa). Furthermore, their performance against an eavesdropper's attack is analyzed. Finally, in order to illustrate the operation of the protocols in practice, two small scale but detailed examples are given., Comment: 16 pages, 8 figures

For a finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in the parameterized complexity of ${\cal F}$-M-DELETION when the parameter is the treewidth of $G$, denoted by $tw$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{{\cal F}}$ such that ${\cal F}$-M-DELETION can be solved in time $f_{{\cal F}}(tw) \cdot n^{O(1)}$ on $n$-vertex graphs. We provide lower bounds under the ETH on $f_{{\cal F}}$ for several collections ${\cal F}$. We first prove that for any ${\cal F}$ containing connected graphs of size at least two, $f_{{\cal F}}(tw)= 2^{\Omega(tw)}$, even if the input graph $G$ is planar. Our main contribution consists of superexponential lower bounds for a number of collections ${\cal F}$, inspired by a reduction of Bonnet et al.~[IPEC, 2017]. In particular, we prove that when ${\cal F}$ contains a single connected graph $H$ that is either $P_5$ or is not a minor of the banner (that is, the graph consisting of a $C_4$ plus a pendent edge), then $f_{{\cal F}}(tw)= 2^{\Omega(tw \cdot \log tw)}$. This is the third of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of $\{H\}$-M-DELETION, in terms of $H$, when $H$ is connected., Comment: 41 pages, 20 figures. arXiv admin note: substantial text overlap with arXiv:1907.04442, arXiv:1704.07284

Constraint acquisition systems such as QuAcq and MultiAcq can assist non-expert users to model their problems as constraint networks by classifying (partial) examples as positive or negative. For each negative example, the former focuses on one constraint of the target network, while the latter can learn a maximum number of constraints. Two bottlenecks of the acquisition process where both these algorithms encounter problems are the large number of queries required to reach convergence, and the high cpu times needed to generate queries, especially near convergence. In this paper we propose algorithmic and heuristic methods to deal with both these issues. We first describe an algorithm, called MQuAcq, that blends the main idea of MultiAcq into QuAcq resulting in a method that learns as many constraints as MultiAcq does after a negative example, but with a lower complexity. A detailed theoretical analysis of the proposed algorithm is also presented. %We also present a technique that boosts the performance of constraint acquisition by reducing the number of queries significantly. Then we turn our attention to query generation which is a significant but rather overlooked part of the acquisition process. We describe %in detail how query generation in a typical constraint acquisition system operates, and we propose heuristics for improving its efficiency. Experiments from various domains demonstrate that our resulting algorithm that integrates all the new techniques does not only generate considerably fewer queries than QuAcq and MultiAcq, but it is also by far faster than both of them, in average query generation time as well as in total run time, and also largely alleviates the premature convergence problem.

Let $k$ be a field. We show that locally presentable, $k$-linear categories $\mathcal{C}$ dualizable in the sense that the identity functor can be recovered as $\coprod_i x_i\otimes f_i$ for objects $x_i\in \mathcal{C}$ and left adjoints $f_i$ from $\mathcal{C}$ to $\mathrm{Vect}_k$ are products of copies of $\mathrm{Vect}_k$. This partially confirms a conjecture by Brandenburg, the author and T. Johnson-Freyd. Motivated by this, we also characterize the Grothendieck categories containing an object $x$ with the property that every object is a copower of $x$: they are precisely the categories of non-singular injective right modules over simple, regular, right self-injective rings of type I or III., Comment: 11 pages + references

A communication network is a graph in which each node has only local information about the graph and nodes communicate by passing messages along its edges. Here, we consider the {\it geometric communication network} where the nodes also occupy points in space and the distance between points is the Euclidean distance. Our goal is to understand the communication cost needed to solve several fundamental geometry problems, including Convex Hull, Diameter, Closest Pair, and approximations of these problems, in the asynchronous CONGEST KT1 model. This extends the 2011 result of Rajsbaum and Urrutia for finding a convex hull of a planar geometric communication network to networks of arbitrary topology., Comment: A version of this work was submitted to ICDCN 2021

In this paper, we advance an ideal-theoretic analogue of a "finite factorization domain" (FFD), giving such a domain the moniker "finite molecularization domain" (FMD). We characterize FMD's as those factorable domains (termed "molecular domains" in the paper) for which every nonzero ideal is divisible by only finitely many nonfactorable ideals (termed "molecules" in the paper) and the monoid of nonzero ideals of the domain is unit-cancellative, in the language of Fan, Geroldinger, Kainrath, and Tringali. We develop a number of connections, particularly at the local level, amongst the concepts of "FMD", "FFD", and the "finite superideal domains" (FSD's) of Hetzel and Lawson. Characterizations of when $k[X^2, X^3]$, where $k$ is a field, and the classical $D+M$ construction are FMD's are provided. We also demonstrate that if $R$ is a Dedekind domain with the finite norm property, then $R[X]$ is an FMD.

We present a variety of numerical data related to the growth of terms in aliquot sequences, iterations of the function $s(n) = \sigma(n) - n$. First, we compute the geometric mean of the ratio $s_k(n)/s_{k-1}(n)$ of $k$th iterates for $n \leq 2^{37}$ and $k=1,\dots,10.$ Second, we extend the computation of numbers not in the range of $s(n)$ (called untouchable) by Pollack and Pomerance to the bound of $2^{40}$ and use these data to compute the geometric mean of the ratio of consecutive terms limited to terms in the range of $s(n).$ Third, we give an algorithm to compute $k$-untouchable numbers ($k-1$st iterates of $s(n)$ but not $k$th iterates) along with some numerical data. Finally, inspired by earlier work of Devitt, we estimate the growth rate of terms in aliquot sequences using a Markov chain model based on data extracted from thousands of sequences., Comment: This is an Accepted Manuscript of an article published by Taylor & Francis in Experimental Mathematics on June 18, 2018, available online: https://www.tandfonline.com/doi/abs/10.1080/10586458.2018.1477077

Model complexity is a fundamental problem in deep learning. In this paper, we conduct a systematic overview of the latest studies on model complexity in deep learning. Model complexity of deep learning can be categorized into expressive capacity and effective model complexity. We review the existing studies on those two categories along four important factors, including model framework, model size, optimization process, and data complexity. We also discuss the applications of deep learning model complexity including understanding model generalization, model optimization, and model selection and design. We conclude by proposing several interesting future directions.

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster., Comment: 22 pages, 11 figures (21 subfigures), accepted by sigspatial 2021

Public goods games in undirected networks are generally known to have pure Nash equilibria, which are easy to find. In contrast, we prove that, in directed networks, a broad range of public goods games have intractable equilibrium problems: The existence of pure Nash equilibria is NP-hard to decide, and mixed Nash equilibria are PPAD-hard to find. We define general utility public goods games, and prove a complexity dichotomy result for finding pure equilibria, and a PPAD-completeness proof for mixed Nash equilibria. Even in the divisible goods variant of the problem, where existence is easy to prove, finding the equilibrium is PPAD-complete. Finally, when the treewidth of the directed network is appropriately bounded, we prove that polynomial-time algorithms are possible.