Search

A γ -quasi-clique is a simple and undirected graph with edge density of at least γ . Given a graph G , the maximum γ -quasi-clique problem ( γ -QCP) consists of finding an induced γ -quasi-clique with the maximum number of vertices. γ -QCP generalizes the well-known maximum clique problem and its solution is useful for detecting dense subgraphs. After reviewing known integer linear programming formulations and dual bounds for γ -QCP, a new formulation obtained by decomposing star inequalities and combining edge inequalities is proposed. The model has an exponential number of variables but a linear number of constraints and its linear relaxation allows the computation by column generation of dual bounds for large and dense graphs. The connectivity of γ -quasi-cliques is also discussed and a new sufficient connectivity condition presented. An extensive computational experience shows the quality of the computed dual bounds and their performance in a branch-and-price framework, as well as the practical effectiveness of the connectivity condition.

We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one with strictly convex faces while maintaining planarity at all times. Our morph is convexity-increasing, meaning that once an angle is convex, it remains convex. We give an efficient algorithm that constructs such a morph as a composition of a linear number of steps where each step either moves vertices along horizontal lines or moves vertices along vertical lines. Moreover, we show that a linear number of steps is worst-case optimal. To obtain our result, we use a well-known technique by Hong and Nagamochi for finding redrawings with convex faces while preserving y-coordinates. Using a variant of Tutte's graph drawing algorithm, we obtain a new proof of Hong and Nagamochi's result which comes with a better running time. This is of independent interest, as Hong and Nagamochi's technique serves as a building block in existing morphing algorithms., Preliminary version in Proc. WG 2018

We show that for every graph $G$ and every graph $H$ obtained by subdividing each edge of $G$ at least $\Omega(\log |V(G)|)$ times, $H$ is nonrepetitively 3-colorable. In fact, we show that $\Omega(\log \pi'(G))$ subdivisions per edge are enough, where $\pi'(G)$ is the nonrepetitive chromatic index of $G$. This answers a question of Wood and improves a similar result of Pezarski and Zmarz that stated the existence of at least one 3-colorable subdivision with a linear number of subdivision vertices per edge.

Children’s early numerical knowledge establishes a foundation for later development of mathematics achievement and playing linear number board games is effective in improving basic numerical abilities. Besides the visuo-spatial cues provided by traditional number board games, learning companion robots can integrate multi-sensory information and offer social cues that can support children’s learning experiences. We explored how young children experience sensory feedback (audio and visual) and social expressions from a robot when playing a linear number board game, “RoboMath.” We present the interaction design of the game and our investigation of children’s (n = 19, aged 4) and parents’ experiences under three conditions: (1) visual-only, (2) audio-visual, and (3) audio-visual-social robot interaction. We report our qualitative analysis, including the themes observed from interviews with families on their perceptions of the game and the interaction with the robot, their child’s experiences, and their design recommendations.

A total of 189 middle school 8th gradestudents participated in this study and it was aimed to determine the problemposing performances of these students that can be solved by the look for apattern strategy which is one of the problem solving strategies. For thispurpose, students are asked to pose problems that can be solved with the lookfor a pattern strategy and to explain step by step what they are doing in theprocess of posing this problem. Clinical inter-views were conducted with 6students who were volunteers from the study participants and who differedaccording to their level of achievement. Descriptive and semantic analysistechniques were used in the analysis of the data obtained from the study.According to the results of the study it can be concluded that the vastmajority of participants tended to give pattern examples rather than theproblems that could be solved by the look for a pattern problem solvingstrategy. When we look at the structure of the problems that can be solved bythe loook for a pattern strategy, it is seen that the students apply morelinear number patterns., Bu çalışmaya toplam 189ortaokul 8. sınıf öğrencisi katılmış olup, bu öğrencilerin problem çözmestratejilerinden biri olan örüntü arama stratejisi ile çözülebilecek problemkurma performanslarının belirlenmesi amaçlanmıştır. Bu amaç doğrultusundaöğrencilere örüntü arama stratejisi ile çözülebilecek problem kurmaları ve buproblem kurma sürecinde neler yaptıklarını adım adım anlatmaları istenmiştir.Çalışmaya katılan öğrencilerden gönüllü olan ve başarı düzeylerine görefarklılık gösteren toplam 6 öğrenci ile de klinik görüşmelergerçekleştirilmiştir. Çalışmadan elde edilen verilerin analizinde semantik vebetimsel analiz teknikleri kullanılmıştır. Araştırmadan elde edilen sonuçlarabakıldığında, katılımcıların büyük çoğunluğu örüntü arama stratejisi ileçözülebilecek problem kurma yerine örüntü oluşturma yoluna gitmişlerdir. Örüntüarama stratejisi ile çözülebilecek problemlerin yapısına bakıldığında iseöğrencilerin daha çok lineer sayı örüntüsü türüne başvurdukları görülmektedir.

Although polyhedra can have much fewer edges than triangulations, many results about hamiltonicity proven for triangulations also hold for polyhedra. The most famous of these results is surely Whitney’s result from 1931 that 4-connected triangulations are hamiltonian, which was 25 years later generalised to 4-connected polyhedra by Tutte. Nevertheless the only known bounds for the number of hamiltonian cycles in 4-connected polyhedra are constant, though for triangulations a lower bound of | V | ∕ ( log 2 | V | ) was already proven in 1979 and improved to a linear bound in 2018. In this article we prove linear lower bounds for 4-connected polyhedra and polyhedra with at most one 3-cut and sufficiently many edges.

Recent new constructions of rate-1 OT [Dottling, Garg, Ishai, Malavolta, Mour, and Ostrovsky, CRYPTO 2019] have brought this primitive under the spotlight and the techniques have led to new feasibility results for private-information retrieval, and homomorphic encryption for branching programs. The receiver communication of this construction consists of a quadratic (in the sender’s input size) number of group elements for a single instance of rate-1 OT. Recently [Garg, Hajiabadi, Ostrovsky, TCC 2020] improved the receiver communication to a linear number of group elements for a single string-OT. However, most applications of rate-1 OT require executing it multiple times, resulting in large communication costs for the receiver.

Knowledge graphs (KGs) provide information in machine interpretable form. In cases where multiple KGs are used in the same system, that information needs to be integrated. This is usually done by automated matching systems. Most of those systems consider only 1:1 (binary) matching tasks. Thus, matching a larger number of knowledge graphs with such systems would lead to quadratic efforts. In this paper, we empirically analyze different approaches to reduce the task of multi-source matching to a linear number of executions of binary matching systems. We show that the matching order of KGs and the multi-source strategy actually matter and that near-optimal results can be achieved with linear efforts.

We enumerate the connected graphs that contain a linear number of edges with respect to the number of vertices. So far, only the first term of the asymptotics was known. Using analytic combinatorics, i.e. generating function manipulations, we derive the complete asymptotic expansion., presented as a talk at FPSAC 2016 12 pages + 3 pages of appendix, 4 figures

A tolerant tester with one-sided error for a property is a tester that accepts every input that is close to the property, with probability 1, and rejects every input that is far from the property, with positive probability. In this note we show that such testers require a linear number of queries.

A fan-planar graph is a graph that admits a drawing, in which each edge can cross only edges with a common endvertex, and this endvertex is on the same side of the edge. Hence, by definition, fan-planar graphs extend the class of 1-planar graphs, but still form a proper subclass of 3-quasiplanar graphs, as they cannot contain three mutually crossing edges. Similarly to several other classes of beyond-planar graphs, fan-planar graphs have a linear number of edges, it is NP-hard to recognize them (both in general and in the fixed rotation system setting), while polynomial-time recognition and drawing algorithms are known only for special variants of them. In this chapter, we review known combinatorial and algorithmic results on fan-planar graphs and we identify several open problems in the field.

Causal interaction models such as the noisy-or model, are used in Bayesian networks to simplify probability acquisition for variables with large numbers of modelled causes. These models essentially prescribe how to complete an exponentially large probability table from a linear number of parameters. Yet, typically the full probability tables are required for inference with Bayesian networks in which such interaction models are used, although inference algorithms tailored to specific types of network exist that can directly exploit the decomposition properties of the interaction models. In this paper we revisit these decomposition properties in view of general inference algorithms and demonstrate that they allow an alternative representation of causal interaction models that is quite concise, even with large numbers of causes involved. In addition to forestalling the need of tailored algorithms, our alternative representation brings engineering benefits beyond those widely recognised.

Let $H_n$ be a graph on $n$ vertices and let $\overline{H_n}$ denote the complement of $H_n$. Suppose that $\Delta = \Delta(n)$ is the maximum degree of $\overline{H_n}$. We analyse three algorithms for sampling $d$-regular subgraphs ($d$-factors) of $H_n$. This is equivalent to uniformly sampling $d$-regular graphs which avoid a set $E(\overline{H_n})$ of forbidden edges. Here $d=d(n)$ is a positive integer which may depend on $n$. Two of these algorithms produce a uniformly random $d$-factor of $H_n$ in expected runtime which is linear in $n$ and low-degree polynomial in $d$ and $\Delta$. The first algorithm applies when $(d+\Delta)d\Delta = o(n)$. This improves on an earlier algorithm by the first author, which required constant $d$ and at most a linear number of edges in $\overline{H_n}$. The second algorithm applies when $H_n$ is regular and $d^2+\Delta^2 = o(n)$, adapting an approach developed by the first author together with Wormald. The third algorithm is a simplification of the second, and produces an approximately uniform $d$-factor of $H_n$ in time $O(dn)$. Here the output distribution differs from uniform by $o(1)$ in total variation distance, provided that $d^2+\Delta^2 = o(n)$.

We show that every orthogonal polyhedron of genus at most 2 can be unfolded without overlap while using only a linear number of orthogonal cuts (parallel to the polyhedron edges). This is the first result on unfolding general orthogonal polyhedra beyond genus-0. Our unfolding algorithm relies on the existence of at most 2 special leaves in what we call the "unfolding tree" (which ties back to the genus), so unfolding polyhedra of genus 3 and beyond requires new techniques., Comment: 22 pages, 10 figures

The study evaluates the linear number board game 100 House. Taking into account Krajewski's (2003, 2013) development model of mathematical competencies, this game supports the development of mathem...

We show that, when a linear number of vertices are removed from a generalized exchanged hypercube, its surviving graph consists of a large connected component and smaller component(s) containing altogether a rather limited number of vertices. This result can be applied to obtain a number of fault tolerant properties of this interesting structure.

Three different methacrylic monomers (γ-butyrolactone methacrylate (GBLMA), 3-hydroxyl-1-adamantyl methacrylate (HAMA) and 2-methyl-2-adamantyl methacrylate (MAMA)), that are most often terpolymerized for 193 nm photoresists, were studied individually by nitroxide mediated polymerization (NMP) with succinimidyl ester terminated BlocBuilder (NHS-BlocBuilder) using a small fraction ∼ 0.05 mol/mol 5 mol % in the initial mixture of 2,3,4,5,6 pentafluorostyrene (PFS) controlling co-monomer. The copolymerizations were done in 0.35 g/g (35 wt%) dioxane solution and were studied as functions of temperature (75 versus 90 °C) and added free SG1 nitroxide (none versus SG1:NHS-BlocBuilder molar ratio ≈ 0.15) with the objective of minimizing the dispersity (M‾w/M‾n). MAMA/PFS copolymerizations were not strongly influenced by temperature or addition of free nitroxide, with relatively linear number average molecular weight M‾n versus conversion plots and M‾w/M‾n=1.28−1.55. Further, MAMA/PFS polymerization kinetics was notably slower compared to GBLMA or HAMA copolymerizations with PFS. For GBLMA/PFS and HAMA/PFS copolymerizations, M‾w/M‾n was reduced the lower temperature of 75 °C but added SG1 did not play a strong role. For GBLMA/PFS, M‾w/M‾n was reduced from 1.70–1.71 at 90 °C to 1.42–1.50 at 75 °C and for HAMA/PFS, M‾w/M‾n was reduced from 1.36–1.47 at 90 °C to 1.22–1.31 at 75 °C. This article is protected by copyright. All rights reserved

In this paper, we consider the unconstrained submodular maximization problem. We propose the first algorithm for this problem that achieves a tight $(1/2-\varepsilon)$-approximation guarantee using $\tilde{O}(\varepsilon^{-1})$ adaptive rounds and a linear number of function evaluations. No previously known algorithm for this problem achieves an approximation ratio better than $1/3$ using less than $\Omega(n)$ rounds of adaptivity, where $n$ is the size of the ground set. Moreover, our algorithm easily extends to the maximization of a non-negative continuous DR-submodular function subject to a box constraint and achieves a tight $(1/2-\varepsilon)$-approximation guarantee for this problem while keeping the same adaptive and query complexities., Comment: Authors are listed in alphabetical order

In this paper, we study arrangements of orthogonal circles, that is, arrangements of circles where every pair of circles must either be disjoint or intersect at a right angle. Using geometric arguments, we show that such arrangements have only a linear number of faces. This implies that orthogonal circle intersection graphs have only a linear number of edges. When we restrict ourselves to orthogonal unit circles, the resulting class of intersection graphs is a subclass of penny graphs (that is, contact graphs of unit circles). We show that, similarly to penny graphs, it is NP-hard to recognize orthogonal unit circle intersection graphs.

Pesin sets are measurable sets along which the behavior of a matrix cocycle above a measure-preserving dynamical system is explicitly controlled. In uniformly hyperbolic dynamics, we study how often points return to Pesin sets under suitable conditions on the cocycle: if it is locally constant, or if it admits invariant holonomies and is pinching and twisting, we show that the measure of points that do not return a linear number of times to Pesin sets is exponentially small. We discuss applications to the exponential mixing of contact Anosov flows and consider counterexamples illustrating the necessity of suitable conditions on the cocycle.

MQuAcq is an algorithm for active constraint acquisition that has been shown to outperform previous algorithms such as QuAcq and MultiAcq. In this paper, we exhibit two important drawbacks of MQuAcq. First, for each negative example, the number of recursive calls to the main procedure of MQuAcq can be non-linear, making it impractical for large problems. Second, MQuAcq, as well as QuAcq and MultiAcq, does not take into account the structure of the learned problem. We propose MQuAcq-2, a new algorithm based on MQuAcq that integrates solutions to both these problems. MQuAcq-2 exploits the structure of the learned problem by focusing the queries it generates to quasi-cliques of constraints. When dealing with a negative query, it only requires a linear number of iterations. MQuAcq-2 outperforms MQuAcq, especially on large problems.

The study examined effects of playing number games (linear number board game, circular number board game, and nonlinear numerical activities) on the development of number knowledge and early arithm ...

We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a dense k-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemer\'edi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight., Comment: 17 pages, 2 figures. Addressed referee's comments, streamlined proof of Lemma 6

Contains fulltext : 192025.pdf (Publisher’s version ) (Open Access) Children's early numerical capacities form the building blocks for later arithmetic proficiency. Linear number placements and counting skills are indicative of mapping, as an important precursor to arithmetic skills, and have been suggested to be of vital importance to arithmetic development. The current study investigated whether fostering mapping skills is more efficient through a counting or a number line training programme. Effects of both programmes were compared through a quasi-experimental design, and moderation effects of age and SES were investigated. Ninety kindergartners were divided into three conditions: a counting, a number line, and a control condition. Pretests and posttests included an arithmetic (addition) task and a battery of number sense tasks (comparison, number lines and counting). Results showed significantly greater gains in arithmetic, counting, and symbolic number lines in the counting training group than in the control group. The number line training group did not make significantly greater gains than the control group. Training gains were moderated by age, but not SES. We concluded that counting training improved numerical capacities effectively, whereas no such improvements could be found for the number line training. This suggests that only a counting approach is effective for fostering number sense and early arithmetic skills in kindergarten. Future research should elaborate on the parameters of training programmes and the consequences of variation in these parameters. 11 p.

We study the entanglement game, which is a version of cops and robbers, on sparse graphs. While the minimum degree of a graph G is a lower bound for the number of cops needed to catch a robber in G, we show that the required number of cops can be much larger, even for graphs with small maximum degree. In particular, we show that there are 3-regular graphs where a linear number of cops are needed.

Motivated by airborne intruder detection and defence systems, we examine sparse random graphs with linear number of connections. We establish theoretical bounds on domination number and our analysis gives a partial solution of the problem posed in [6]. Our computer simulations are based on the integer linear programming optimization method. The experimental results verify our analytical estimations and suggest a direction for the future research.

This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the second decomposition. We show that every graph in each of the following classes has a tree decomposition and a linear-sized path decomposition with bounded intersections: (1) every proper minor-closed class, (2) string graphs with a linear number of crossings in a fixed surface, (3) graphs with linear crossing number in a fixed surface. Here `linear size' means that the total size of the bags in the path decomposition is $O(n)$ for $n$-vertex graphs. We then show that every $n$-vertex graph that has a tree decomposition and a linear-sized path decomposition with bounded intersections has $O(\sqrt{n})$ treewidth. As a corollary, we conclude a new lower bound on the crossing number of a graph in terms of its treewidth. Finally, we consider graph classes that have two path decompositions with bounded intersections. Trees and outerplanar graphs have this property. But for the next most simple class, series parallel graphs, we show that no such result holds.

Let G be an \(m\times n\) rectangular grid graph. We study the problem of transforming Hamiltonian cycles on G under two basic operations we call flip and transpose. We introduce a new complexity measure, the bend complexity, for Hamiltonian cycles. Given any two Hamiltonian cycles \(C_1\) and \(C_2\) of bend complexity 1, we show that \(C_1\) can be transformed to \(C_2\) using only a linear number of flips and transposes.

We introduce a new geometric spanner, \(\delta \)-Greedy, whose construction is based on a generalization of the known Path-Greedy and Gap-Greedy spanners. The \(\delta \)-Greedy spanner combines the most desirable properties of geometric spanners both in theory and in practice. More specifically, it has the same theoretical and practical properties as the Path-Greedy spanner: a natural definition, small degree, linear number of edges, low weight, and strong \((1+\varepsilon )\)-spanner for every \(\varepsilon >0\). The \(\delta \)-Greedy algorithm is an improvement over the Path-Greedy algorithm with respect to the number of shortest path queries and hence with respect to its construction time. We show how to construct such a spanner for a set of n points in the plane in \(O(n^2 \log n)\) time.

The well-separated pair decomposition (WSPD) of the complete Euclidean graph defined on points in \(\mathbb {R}^2\) (Callahan and Kosaraju [JACM, 42 (1): 67-90, 1995]) is a technique for partitioning the edges of the complete graph based on length into a linear number of sets. Among the many different applications of WSPDs, Callahan and Kosaraju proved that the sparse subgraph that results by selecting an arbitrary edge from each set (called WSPD-spanner) is a \(1+8/(s-4)\)-spanner, where \(s>4\) is the separation ratio used for partitioning the edges.

Eliminating the possible redundancy from a set of candidate motifs occurring in an input string is fundamental in many applications. The existing techniques proposed to extract irredundant motifs are not suitable when the motifs to search for are structured, i.e., they are made of two (or several) subwords that co-occur in a text string s of length n. The main effort of this work is studying and characterizing a compact class of tandem motifs, that is, pairs of substrings {m1, m2} occurring in tandem within a maximum distance of d symbols in s, where d is an integer constant given in input. To this aim, we first introduce the concept of maximality, related to four specific conditions that hold only for this class of motifs. Then, we eliminate the remaining redundancy by defining the notion of irredundancy for tandem motifs. We prove that the number of non-overlapping irredundant tandem motifs is O(d2n) which, considering d as a constant, leads to a linear number of tandems in the length of the input string. This is an order of magnitude less than previously developed compact indexes for tandem extraction. The notions and bounds provided for tandem motifs are generalized for the case r≥2, if r is the number of subwords composing the motifs. Finally, we also provide an algorithm to extract irredundant tandem motifs.

Let S be a set of n points in general position in the plane. Together with S we are given a set of parity constraints, that is, every point of S is labeled either even or odd. A graph G on S satisfies the parity constraint of a point $${p\in S}$$ if the parity of the degree of p in G matches its label. In this paper, we study how well various classes of planar graphs can satisfy arbitrary parity constraints. Specifically, we show that we can always find a plane tree, a two-connected outerplanar graph, or a pointed pseudo-triangulation that satisfy all but at most three parity constraints. For triangulations we can satisfy about 2/3 of the parity constraints and we show that in the worst case there is a linear number of constraints that cannot be fulfilled. In addition, we prove that for a given simple polygon H with polygonal holes on S, it is NP-complete to decide whether there exists a triangulation of H that satisfies all parity constraints.

In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a nonmalleable extractor. A nonmalleable extractor dramatically strengthens the notion of a strong extractor. A strong extractor takes two inputs, a weakly random $x$ and a uniformly random seed $y$, and outputs a string which appears uniform, even given $y$. For a nonmalleable extractor ${\mathsf{nmExt}}$, the output ${\mathsf{nmExt}}(x,y)$ should appear uniform given $y$ as well as ${\mathsf{nmExt}}(x,{\mathcal A}(y))$, where ${\mathcal A}$ is an arbitrary function with ${\mathcal A}(y) \neq y$. We show that an extractor introduced by Chor and Goldreich is nonmalleable when the entropy rate (the ratio between the entropy and the length of the weakly random string) is above half. It outputs a linear number of bits when the entropy rate is $1/2 + \alpha$ for any $\alpha>0$. Previously, no explicit construction was known for any entropy rate less than 1. To achieve a polynomial running ti...

It has been shown that, when a linear number of vertices are removed from a Generalized Exchanged Hypercube (GEH), a generalized version of the interesting exchanged hypercube, its surviving graph consists of a large connected component and smaller component(s) containing altogether a rather limited number of vertices. In this chapter, we further apply the above connectivity result to derive several fault-tolerance related structural parameters for GEH, including its restricted connectivity, cyclic vertex-connectivity, component connectivity, and its conditional diagnosability in terms of the comparison diagnosis model.

Trees with labelled leaves and with all other vertices of degree three play an important role in systematic biology and other areas of classification. A classical combinatorial result ensures that such trees can be uniquely reconstructed from the distances between the leaves (when the edges are given any strictly positive lengths). Moreover, a linear number of these pairwise distance values suffices to determine both the tree and its edge lengths. A natural set of pairs of leaves is provided by any `triplet cover' of the tree (based on the fact that each non-leaf vertex is the median vertex of three leaves). In this paper we describe a number of new results concerning triplet covers of minimum size. In particular, we characterize such covers in terms of an associated graph being a 2-tree. Also, we show that minimum triplet covers are `shellable' and thereby provide a set of pairs for which the inter-leaf distance values will uniquely determine the underlying tree and its associated branch lengths., 11 pages, 4 figures

For a finite relational structure A, let CSP(A) denote the CSP instances whose constraint relations are taken from A. The resulting family of problems CSP(A) has been considered heavily in a variety of computational contexts. In this article, we consider this family from the perspective of property testing: given an instance of a CSP and query access to an assignment, one wants to decide whether the assignment satisfies the instance, or is far from so doing. While previous works on this scenario studied concrete templates or restricted classes of structures, this article presents comprehensive classification theorems. Our first contribution is a dichotomy theorem completely characterizing the structures A such that CSP(A) is constant-query testable: (i) If A has a majority polymorphism and a Maltsev polymorphism, then CSP(A) is constant-query testable with one-sided error. (ii) Else, testing CSP(A) requires a super-constant number of queries. Let $\exists$CSP(A) denote the extension of CSP(A) to instances which may include existentially quantified variables. Our second contribution is to classify all structures A in terms of the number of queries needed to test assignments to instances of $\exists$CSP(A), with one-sided error. More specifically, we show the following trichotomy: (i) If A has a majority polymorphism and a Maltsev polymorphism, then $\exists$CSP(A) is constant-query testable with one-sided error. (ii) Else, if A has a $(k + 1)$-ary near-unanimity polymorphism for some $k \geq 2$, and no Maltsev polymorphism then $\exists$CSP(A) is not constant-query testable (even with two-sided error) but is sublinear-query testable with one-sided error. (iii) Else, testing $\exists$CSP(A) with one-sided error requires a linear number of queries., Comment: An extended abstract will appear in the proceedings of FOCS'16

We revisit the regular-expression matching problem with respect to prefix-freeness of the pattern. It is known that a prefix-free pattern gives only a linear number of matching substrings in the size of an input text. We improve the previous algorithm and suggest an efficient algorithm that finds all pairs (start, end) of start and end positions of all matching substrings with a single scan of the input when the pattern is a prefix-free regular expression.

We introduce a new geometric spanner whose construction is based on a generalization of the known Stable Roommates problem. The Stable Roommates Spanner combines the most desirable properties of geometric spanners: a natural definition, small degree, linear number of edges, strong ( 1 + ? ) -spanner for every ? 0 , and an efficient construction algorithm. It is an improvement over the well-known Yao graph and ?-graph and their variants. We show how to construct such a spanner for a set of points in the plane in O ( n log 10 n ) expected time. We introduce a variant of the Stable Roommates Spanner called the Stable Roommates ?-Spanner which we can generalize to higher dimensions and construct more efficiently in O ( n log d n ) time. This variant possesses all the properties of the Stable Roommates Spanner except that it is no longer a strong spanner.