Search

Failed Error Propagation (FEP) can reduce test effectiveness and recent work proposed an information theoretic measure, Squeeziness, as the theoretical basis for avoiding FEP. This paper demonstrates that Squeeziness is not suitable for comparing programs with different input domains. We then extend Squeeziness to Normalised Squeeziness and demonstrate that this is more generally useful.

This note extends the first-order truncated differentials found by Das, Maitra, and Meier [1] on 2 rounds of the NORX 32 permutation. These lead to stronger 2.5-round differential biases for NORX and BLAKE2's permutation, and for 5 rounds of the ChaCha permutation. These biases lead to efficient “inside-out” distinguishers on 4 rounds of the NORX and BLAKE2 permutations, and 8 rounds of the ChaCha permutation. These distinguishers do not directly affect the security claims of NORX , BLAKE2, or ChaCha in their respective modes of operation.

We show how to construct a set S of O ( 1 / e 1.5 ) points such that for any convex set C contained in the unit square, the convex hull of the points in S that are contained in C has area at least | C | − e . We present two algorithmic applications, for geometric shape matching and area approximation.

The problem of modifying a given graph to satisfy certain properties has been one of the central topics in parameterized tractability study. In this paper, we investigate the cycle contraction problem, which makes a graph into a cycle by edge contractions. The problem was raised by Belmonte et al. [IPEC 2013] and they obtained a linear kernel with at most 6 k + 6 vertices for it. We provide an improved kernel with at most 5 k + 4 vertices for the problem in this paper. Our result showcases how to design kernelization algorithm for one problem by exploiting kernels of another problem.

In ICALP 2016, Bai, Stehle and Wen showed that for polynomially bounded parameter γ, the Bounded Distance Decoding (BDD) problem with parameter 1 / ( 2 γ ) can be probabilistically reduced to the unique Shortest Vector Problem (uSVP) with parameter γ. Their reduction is based on the lattice sparsification and embedding techniques. In this paper, we improve their analysis for specific values of the parameter and prove that BDD 1 / ( 2 γ ) can be reduced to uSVP γ 1 with a slightly larger gap. The improvement follows from a careful study of the radius of a sphere which contains at most polynomial number of vectors, then a proper choice of the parameter in the embedding lattice is used to obtain a unique lattice with a larger gap. Our result shows that the equivalence between BDD 1 / ( 2 γ ) and uSVPγ does not hold under the assumption that uSVPγ does not reduce to uSVP γ ′ for any two constants γ γ ′ .

Healthy diet and physical activity practice are well-known required behaviors for preventing noncommunicable diseases. However, sometimes it is difficult for people to change life-styles by themselves, once they are subject to environment and social networks influences. Nowadays plenty of devices and applications are offered promising to help patients, but the solely use and spreading of ubiquitous computing devices are not enough to help patients to reach their health goals. Strategies are needed to integrate people, technology and the data generated by them, to patients overcome their health issues. So, this article presents an scalable model that aims to integrate people, data and technology for improving health care. This model was designed with noncommunicable diseases prevention in mind, but it can be generalized to other domains. Furthermore, available current technologies can be used to implement the proposed model.

We present a Gray code for the set of involutions of the symmetric group, where the difference between two consecutive involutions is a transposition, or a rotation of three letters. Our code improves previous constructions, and it is proven to be optimal in relation to the Hamming distance between consecutive elements of the code. We also show that the transitions made using a transposition are more frequent than those made using a rotation of three elements.

We cast two algorithms to generate the inorder and preorder of the labels of a binary tree in the context of reversible computing nearly three decades after they were first examined in the light of program inversion. The reversible traversals directly define the inverse algorithms that reconstruct the binary tree and have the same linear time and space requirements as the traversals. A reversible while-language is extended with reversible recursion.

This letter presents a new scheme for the identification of the agent causing information leakage. The methodology is based on threshold measure and an efficient distribution strategy. A threshold value of every data object is calculated on the basis of data sensitivity in order to control the allocation of these objects. Data is distributed by selecting the agents in round-robin pattern and further the object with the positive threshold value is selected. The performance of the scheme is measured using average probability, average success rate, and detection rate. The results show an improvement up to 75% for aforementioned parameters as compared to the prior work.

It is shown that for a given ordered node-labelled tree of size n and with s different node labels, one can construct in linear time a top dag of height O ( log ⁡ n ) and size bounded by O ( n / log σ ⁡ n ) and O ( d ⋅ log ⁡ n ) , where σ = max ⁡ { 2 , s } and d is the size of the minimal dag. The size bound O ( n / log σ ⁡ n ) is optimal and improves on previous bounds.

Key regression is a primitive that allows a content publisher to give a small amount of keying material, for time stamp i, to a party such that they can derive key k i and all keys k j for time stamps j i , but not for time stamps j > i . Existing key-regression schemes based on random oracles, pseudorandom permutations, and pseudorandom generators require a publisher to maintain state of size linear in the number of potential keys. In previous work, constant sized publisher state has only been accessible through the use of trapdoor permutations (e.g., RSA). This paper presents a novel key-regression scheme where the publisher must store only a constant amount of state information without trapdoor permutations. This is achieved through the use of constrained pseudorandom functions, a primitive that allows for the delegation of partial evaluation without revealing the key.

SIMECK is a family of lightweight block ciphers that relies on Feistel structure. Being proposed at CHES in 2015, the round function of SIMECK is slightly modified from SIMON. A cipher in this family with K-bit key and n-bit block is called SIMECK n / K , for n / K ∈ { 32 / 64 , 48 / 96 , 64 / 128 } . SIMECK has already received a number of third-party analyses. However, the security level on SIMECK against the related-key impossible differential has never been evaluated. In this paper, we consider related-key impossible differential distinguishers for the variants of SIMECK. We first propose some distinguishers on SIMECK using the miss-in-the-middle approach. More specifically, 15/16/19-round related-key impossible differential distinguishers on SIMECK32/48/64 are presented first while the best previously known results were 11/15/17-round on SIMECK32/48/64 in the single-key setting. Afterwards, thanks to MILP approach, we automatically prove that these characteristics are the best related-key impossible differentials of SIMECK when we limit the input and output differences to 1 active bit.

Auctions are an important theoretical and practical tool in economics, and well studied in the literature. Their procurement siblings, reverse auctions, have received less attention, and are sometimes tacitly assumed to be exact counterparts. We show that for correlated bidders, reverse auctions behave differently from auctions. For two bidders we discuss a simplification of the problem of finding the optimal reverse auction. For k ≥ 3 bidders, we show that the optimal reverse auction must sometimes buy k copies of the item (and discard all but one of them).

Rotation symmetric Boolean functions have been used as components of different cryptosystems. How to construct rotation symmetric Boolean functions with good cryptographic properties is an interesting and significant problem. So far little attempt has been made to provide secondary constructions of rotation symmetric Boolean function. In this paper, based on indirect sum, Maiorana-McFarland functions and concatenation, we propose secondary constructions of rotation symmetric Boolean functions with resiliency, bentness and high algebraic immunity.

This paper proposes an improved Zhang neural network (IZNN) for time-varying linear system of equations solving. Such a neural network is activated by an array of continuous sign-bi-power function. Theoretical analysis is provided to show the desired finite-time convergence property of the proposed IZNN. As compared to Zhang neural network activated by an array of discontinuous signum-function, the solution synthesized by the proposed neural network can converge to theoretical solution, while the solution synthesized by the latter oscillates to some extent around the equilibrium point. Moreover, the remarkable finite-time convergence of the proposed IZNN model is corroborated by a simulative example. Simulation results also demonstrate that the proposed neural network is more suitable in engineering applications than Zhang neural network activated by the array of discontinuous signum-function.

Consider the problem of finding a point in a metric space ( { 1 , 2 , … , n } , d ) with the minimum sum of distances to all points. We show that this problem has a randomized algorithm that (1) always outputs a ( 2 + ϵ ) -approximate solution in expected O ( n / ϵ 2 ) time and that (2) inherits Indyk's [8] , [9] algorithm to output a ( 1 + ϵ ) -approximate solution in O ( n / ϵ 2 ) time with probability Ω ( 1 ) , where ϵ ∈ ( 0 , 1 ) . As a by-product, the average distance in ( { 1 , 2 , … , n } , d ) can be approximated in O ( n / ϵ ) time to within a multiplicative factor in [ 1 / 2 − ϵ , 1 ] with probability 1 / 2 + Ω ( 1 ) , where ϵ > 0 .

Multi-view learning aims to solve multi-view data set which consists of multiple instances with different views. Traditional multi-view learning approaches always encounter small-scale label-known multi-view instances problem and insufficient discriminant information problem. Although some label-unknown multi-view data set generation approaches are developed to enhance useful discriminant information, the weights of views and features are not considered. This paper proposes a weight-based label-unknown multi-view data set generation approach (WLM) to overcome such a disadvantage. The procedure of WLM consists of three main steps. First, get the weights of views and features. Second, get similar instances of each label-known instance. Third, generate and select feasible label-unknown instances which are applied to multi-view learning approaches along with the original label-known multi-view instances. Further, comparisons and analysis about classification performance, clustering performance, bipartite ranking performance, image retrieval performance, significance on some multi-view data sets with some multi-view learning approaches validate the usefulness of WLM.

The PI index of a graph G is defined by P I ( G ) = ∑ e = ( u , v ) ∈ E [ m u ( e | G ) + m v ( e | G ) ] where m u ( e | G ) be the number of edges in G lying closer to the vertex u than to the vertex v. In this paper, we give the upper bound on the PI index of connected bicyclic graphs with even number of edges and characterize the extremal graphs with maximum PI index.

The fresh re-keying scheme is a countermeasure designed to protect low-cost devices against side-channel attacks. In this paper, we present a new birthday-type attack based on a refined reduction to Ring-LPN with a reducible polynomial. Compared with the previous research, our algorithm significantly reduces the time complexity in the 128-bit leakage model—with an SNR equal to 8.21 and at most 220 traces, for instance, the key can be recovered using 241.96 bit-operations.

With the advancement of smart-phones equipped with a geographical location determination system, most clients of these devices are eager to use location based services in a variety of applications for their daily activities. One of the popular location based services is the selection of a meeting location for a group of multiple users with different preferred meeting locations to gather at a certain location through a Meeting Location Determination Server (MLDS). In such services, in addition to minimizing the total cost for all group users, the location privacy of the group users must be preserved. Recently, Wang et al. proposed a practical meeting location determination protocol for a group of users called as Privacy-Preserving Fair Meeting Location Determination (PPFMLD) protocol. This protocol requires light computation and only one-round communication. Wang et al. claim that a group user and the MLDS separately cannot learn the group users' preferred meeting location by performing passive attacks. In this paper, we show that PPFMLD protocol cannot preserve the location privacy for the users against passive attacks performed by the group users or the MLDS which are curious and intend to learn information regarding the group users' preferred meeting locations.

We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and an integer k with 1 ≤ k ≤ n , the problem asks to find a minimum-width annulus that contains at least n − k input points. The k excluded points are considered as outliers of the input points. In this paper, we are interested in particular in annuli of three different shapes: circular, square, and rectangular annuli. For the three cases, we present first and improved algorithms to the problem.

We propose simple algorithms for computing st-numberings and st-edge-numberings of graphs with running time O ( m ) . Unlike previous serial algorithms, these are not dependent on an initially chosen DFS-tree. Instead, we compute st-(edge-)numberings that are consistent with any open ear decomposition D of a graph in the sense that every ear of D is numbered increasingly or decreasingly. Recent applications need such st-numberings, and the only two linear-time algorithms that are known for this task use a complicated order data structure as black box. We avoid using this data structure by introducing a new and light-weight numbering scheme. In addition, we greatly simplify the recent algorithms for computing (the much less known) st-edge-numberings.

Let G = ( V , E ) be a graph. A subset D of vertices of G is called a dominating set of G if for every u ∈ V ∖ D , there exists a vertex v ∈ D such that u v ∈ E . A dominating set D of a graph G is called a secure dominating set of G if for every u ∈ V ∖ D , there exists a vertex v ∈ D such that u v ∈ E and ( D ∖ { v } ) ∪ { u } is a dominating set of G. The secure domination number of G, denoted by γ s ( G ) , is the minimum cardinality of a secure dominating set of G. In this paper, we present an O ( n + m ) time algorithm to compute the secure domination number of a cograph having n vertices and m edges.

The greedy algorithm for approximating dominating sets is a simple method that is known to compute a factor ( ln ⁡ n + 1 ) approximation of a minimum dominating set on any graph with n vertices. We show that a small modification of the greedy algorithm can be used to compute a factor O ( t ⋅ ln ⁡ k ) approximation, where k is the size of a minimum dominating set, on graphs that exclude the complete bipartite graph K t , t as a subgraph.

Motivated by previous work, we prove that, given a graph G and a positive integer k, deciding whether the geodetic number of the complementary prism of G is at most k is an NP -complete problem. We also show lower and upper bounds for the geodetic number of a complementary prism, and determine the geodetic number of a complementary prism when it is defined over a split graph.

Many term-weighting models have been proposed for information retrieval. In this paper we investigate the extent to how retrieval effectiveness of term-weighting models is affected by the presence of spam Web pages. We perform retrieval experiments on the ClueWeb09-English (Category A) dataset – a substantial fraction of which are spam pages that are deliberately designed to manipulate commercial search engines – as well as the ClueWeb12 (Category A) dataset. Ad hoc tasks of TREC Web tracks 2009 through 2012 are completed to examine the spam sensitivity of the state-of-the-art retrieval models using Apache Lucene as the retrieval engine. Moreover, ad hoc tasks of two Web tracks and two Tasks tracks 2013 through 2016 are also included in a part of the experiment where the number of documents that are explicitly judged as spam in the search results returned by each retrieval model is inspected. Our experimental results show that hypergeometric models of information retrieval are more immune than other models to spam content. All the results presented in this article are fully repeatable and reproducible with data and code available online at a public GitHub repository.

Consider a regular expression r of length m and a text string T of length n over an alphabet Σ. Then, the RE shortest substring search problem is to find all shortest substrings of T matching r. The previous algorithm proposed by Clarke and Cormack uses an e-free nondeterministic finite automaton (NFA) and runs in O ( k s n ) time and O ( s ) space, where k is the maximum number of outgoing transitions for any state and symbol, and s is the number of states. Generally, an e-free NFA obtained from a regular expression has s = O ( m ) and k = O ( m ) ; thus the algorithm takes O ( m 2 n ) time and O ( m ) space. We propose a faster algorithm that runs in O ( m n ) time and O ( m ) space. The proposed algorithm is based on a Thompson automaton which is an NFA with e-transitions.

In this note we consider the concept of alphabet ordering in the context of string factoring. We propose a greedy algorithm that produces Lyndon factorizations with small numbers of factors which can be modified to produce large numbers of factors. For the technique we introduce the Exponent Parikh vector. Applications and research directions derived from circ-UMFFs are discussed.

Let G be a graph of order n with δ ( G ) ≥ a + 1 , and 3 ≤ a ≤ b be integers. In this paper, we first show that if G satisfies max ⁡ { d G ( x ) , d G ( y ) } ≥ a ( n + 1 ) a + b for each pair of nonadjacent vertices x , y of G, then G is a fractional [ a , b ] -covered graph. It is a generalization of the known result with a = b = k which is given by Zhou. Furthermore, we show that this result is best possible in some sense.

Semi-bent functions play an important role in the construction of orthogonal variable spreading factor codes used in code-division multiple-access (CDMA) systems as well as in certain cryptographic applications. In this article we provide several infinite classes of semi-bent functions, where each class is characterized by either a different decomposition of such a function with respect to the Walsh spectra of its subfunctions, or by the method used for its derivation. In particular, we also give the exact number of possibilities of decomposing bent functions, in a subclass of the Maiorana–McFarland class.

Merker and Postle showed that any graph that can be decomposed into a forest and a star forest has a decomposition into two forests with diameter at most 18. Using this result, they proved any planar graph of girth at least 6 has two edge-disjoint 18 19 -thin spanning trees. By using a simpler version of their techniques, given a graph that can be decomposed into a forest and a matching, in polynomial time, we decompose the graph into two forests with diameter at most 12. Using this result, we are able to show that any 8-edge-connected planar graph has two edge-disjoint 12 13 -thin spanning trees.

This paper studies an online revenue management problem of accepting and assigning two classes of customers to two levels of resources with capacity constraints. A customer's request may be either accepted or rejected immediately upon its arrival without the information of further demand. One class of customers can be served either by a low-level resource at the resource's regular price, or by a high-level resource at the customer's reservation price. Another class of customers can be served by either level of resource at the regular price of the corresponding resource. Given the capacities of both levels of resources, the objective is to accept appropriate customers and assign them to appropriate resources so as to maximize the total revenue. From the perspective of competitive analysis, we derive an upper bound of competitive ratio for the problem and develop an optimal online strategy whose competitive ratio matches the upper bound.

The n-dimensional folded crossed cube F C Q n is obtained from the crossed cube C Q n by adding extra 2 n − 1 edges. The super connectivity (resp. super edge-connectivity) of a connected graph G is the cardinality of a minimum vertex set (resp. edge set), if any, whose deletion disconnects G and the remaining graph contains no isolated vertex. In this paper we show that the super connectivity and the super edge-connectivity of F C Q n are 2n for n ≥ 4 .

A ( β , ϵ ) -hopset is, informally, a weighted edge set that, when added to a graph, allows one to get from point a to point b using a path with at most β edges (“hops”) and length ( 1 + ϵ ) dist ( a , b ) . In this paper we observe that Thorup and Zwick's sublinear additive emulators are also actually ( O ( k / ϵ ) k , ϵ ) -hopsets for every ϵ > 0 , and that with a small change to the Thorup–Zwick construction, the size of the hopset can be made O ( n 1 + 1 2 k + 1 − 1 ) . As corollaries, we also shave “k” factors off the size of Thorup and Zwick's [20] sublinear additive emulators and the sparsest known ( 1 + ϵ , O ( k / ϵ ) k − 1 ) -spanners, due to Abboud, Bodwin, and Pettie [1] .

Given two disjoint vertex sets S = { s } and T = { t 1 , t 2 , t 3 } of a connected graph, a one-to-many 3-disjoint path cover joining S and T is a vertex-disjoint path cover { P 1 , P 2 , P 3 } such that each path P i joins s and t i . In this paper, we present an efficient algorithm that builds, if exists, a one-to-many 3-disjoint path cover in the cube of a connected graph G joining the two terminal sets. Interestingly enough, we show that a carefully selected spanning tree or spanning unicyclic subgraph of G is all we need to find the desired disjoint path cover in time linear to the size of G.

In the Edge-Disjoint Triangle Packing problem ( Etp ), we are given a graph G and an integer k, and asked to check whether G contains at least k edge-disjoint triangles. This problem is NP-hard and has been well studied in the parameterized complexity. A vertex kernel of size 4k was proved many years ago. Recently, the size of the vertex kernel was improved to 3.5k. In this paper, we further improve the kernel size. We show that for any fixed ϵ > 0 , there is a polynomial-time algorithm that can reduce the input instance to an equivalent instance of at most ( 3 + ϵ ) k vertices.

For a graph G, we let γ ( G ) denote the domination number of G. A graph G is 3-edge-critical if γ ( G ) = 3 and γ ( G + x y ) ≤ 2 for all x , y ∈ V ( G ) with x y ∉ E ( G ) . In this note, we show that the order of a connected 3-edge-critical planar graph is at most 23.

For purpose of solving system of linear equations (SoLE) more efficiently, a fast convergent gradient neural network (FCGNN) model is designed and discussed in this paper. Different from the design of the conventional gradient neural network (CGNN), the design of the FCGNN model is based on a nonlinear activation function, and thus the better convergence speed can be reached. In addition, the convergence upper bound of the FCGNN model is estimated and provided in details. Simulative results validate the superiority of the FCGNN model, as compared to the CGNN model for finding SoLE.

In this work, we investigate the problem of single machine lot scheduling where each lot contains one or more jobs and is of identical processing time. Jobs with different sizes are splittable and shall be processed in consecutive lots. Any completed (part of a) job is delivered to the customer on its completion. We prove that the WSPT (Weighted Shortest Processing Time first) rule is optimal for both models of minimizing total weighted completion time and minimizing total weighted discounted completion time.

The distributed multi-level multi-server paging problem (DMLMSP) defined in this paper extends and generalizes the classical distributed paging problem [3] to a distributed concurrent multi-level setting, in which multiple servers share caches at multiple levels. The DMLMSP can be used for modeling algorithms for efficient distributed storage systems, in which multiple servers use caches for accelerating access to a centralized storage, maintaining cache coherency across multiple nodes while minimizing access latency and optimizing cache-hit ratio. The DMLMSP model fits basic principles of Non-Uniform Cache Architectures (NUCAs) and can be used for analyzing multiple-level centralized storage. We present an optimal offline algorithm for the DMLMSP model, with minimum number of page faults and minimum makespan, whose time complexity is polynomial in the length of the servers' page request sequences. The new algorithm generalizes and simplifies the state of the art algorithms [3] , [1] .

In a finite undirected graph G, a vertex v dominates itself and its neighbors. A vertex set D is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is well known to be NP -complete for graphs of maximum degree 3. We say that an e.d.s. D of G is k-bounded (k-b.e.d.s. for short) if the degree of every vertex in D is at most k in G. The task of the k-Bounded Weighted Efficient Domination (k-BWED) problem is to determine whether a given vertex-weighted graph G admits a k-b.e.d.s., and if so, to compute one of minimum weight. It easily follows from the NP -completeness of ED for graphs of maximum degree 3 that the k-BWED problem is NP -complete for every k ≥ 3 , and clearly, the k-BWED problem is solvable in linear time for k ≤ 1 . In this note, we show that the 2-BWED problem is solvable in time O ( | V ( G ) | ( | V ( G ) | + | E ( G ) | ) ) , thus obtaining a dichotomy of the complexity status of k-BWED over all k ≥ 0 .

We prove upper bounds on deterministic communication complexity in terms of log of the rank and simple versions of the corruption bound. Our bounds are a simplified version of the results of Gavinsky and Lovett [8] , using the same set of tools. We also give an elementary proof for the upper bound on communication complexity in terms of rank proved by Lovett [18] .

For the analysis of access control networks, where capability lists, access control matrices, or RBAC permissions are available, it can be very useful to be able to determine which subjects can be able to know, or which objects can be able to store, data originating from objects in the network. This information can be used in order to answer questions of secrecy, integrity and privacy, related to the data flow analysis problem. On the basis of a logical method, we present a graphical formalism capable to represent such networks and for which the data flow problems can be defined. We present algorithms to calculate answers to data flow questions. Complexity analysis and simulations show that these questions can be practically answered for networks of sizes up to several tens of thousands of subjects and objects, which is the size of many real-life organizations. We also show that the results obtained can be used in the process of role engineering in Role based access control, for determining secrecy levels, as well as for eliminating or combining roles or objects. Finally, a method is demonstrated to go from capability lists to Label-based access control systems.

We investigate the relations between different variants of the LZ77 parsing existing in the literature. All of them are defined as greedily constructed parsings encoding each phrase by reference to a string occurring earlier in the input. They differ by the phrase encodings: encoded by pairs (length + position of an earlier occurrence) or by triples (length + position of an earlier occurrence + the letter following the earlier occurring part); and they differ by allowing or not allowing overlaps between the phrase and its earlier occurrence. For a given string of length $n$ over an alphabet of size $\sigma$, denote the numbers of phrases in the parsings allowing (resp., not allowing) overlaps by $z$ (resp., $\hat{z}$) for "pairs", and by $z_3$ (resp., $\hat{z}_3$) for "triples". We prove the following bounds and provide series of examples showing that these bounds are tight: $\bullet$ $z \le \hat{z} \le z \cdot O(\log\frac{n}{z\log_\sigma z})$ and $z_3 \le \hat{z}_3 \le z_3 \cdot O(\log\frac{n}{z_3\log_\sigma z_3})$; $\bullet$ $\frac{1}2\hat{z} < \hat{z}_3 \le \hat{z}$ and $\frac{1}2 z < z_3 \le z$., Comment: 6 pages

We show that geometric hitting set with axis-parallel rectangles is APX -hard even when all rectangles share a common point. We also show that geometric hitting set problem is APX -hard for several classes of objects given in [3] such as axis-parallel ellipses with a shared point, axis-parallel cubes sharing a common point, etc. Further, we give a polynomial time approximation scheme ( PTAS ) for the weighted hitting set problem with axis-parallel rectangles when all rectangles have integer side lengths bounded by a constant C. Finally, we show that the problem is NP -hard for rectangles of size 1 × 2 and 2 × 1 even when every rectangle intersects a given unit height horizontal strip.

Let $P$ be a set of points in $\mathbb{R}^d$, $B$ a bicoloring of $P$ and $\Oo$ a family of geometric objects (that is, intervals, boxes, balls, etc). An object from $\Oo$ is called balanced with respect to $B$ if it contains the same number of points from each color of $B$. For a collection $\B$ of bicolorings of $P$, a geometric system of unbiased representatives (G-SUR) is a subset $\Oo'\subseteq\Oo$ such that for any bicoloring $B$ of $\B$ there is an object in $\Oo'$ that is balanced with respect to $B$. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives., Comment: Appears in the Proceedings of the 31st Canadian Conference on Computational Geometry (CCCG 2019)

An upward drawing of a rooted tree is a drawing such that no parents are below their children. It is well-known that every rooted tree has a planar straight-line upward drawing of width at most log 2 ⁡ ( n + 1 ) . This is class-optimal, i.e., there are rooted trees that require log 2 ⁡ ( n + 1 ) width, but not instance-optimal, i.e., for some trees the drawing uses much more width than required. In this paper, we study how to find upward drawings with instance-optimal width. It turns out that their width is the same as the so-called Horton-Strahler number, which in turn is equivalent to the so-called rooted pathwidth. We give other properties of these graph parameters as well.

A graph is k-connected if it has k pairwise internally node disjoint paths between every pair of its nodes. A subset S of nodes in a graph G is a k-connected set if the subgraph G [ S ] induced by S is k-connected; S is an m-dominating set if every v ∈ V ∖ S has at least m neighbors in S. If S is both k-connected and m-dominating then S is a k-connected m-dominating set, or ( k , m ) -cds for short. In the k -Connected m -Dominating Set ( ( k , m ) -CDS ) problem the goal is to find a minimum weight ( k , m ) -cds in a node-weighted graph. We consider the case m ≥ k and obtain the following approximation ratios. For unit disc graphs we obtain ratio O ( k ln ⁡ k ) , improving the ratio O ( k 2 ln ⁡ k ) of [1] , [2] . For general graphs we obtain the first non-trivial approximation ratio O ( k 2 ln ⁡ n ) .

A set D of vertices in a graph G is an efficient dominating set (e.d.s. for short) of G if D is an independent set and every vertex not in D is adjacent to exactly one vertex in D. The efficient domination (ED) problem asks for the existence of an e.d.s. in G. The minimum weighted efficient domination problem (MIN-WED for short) is the problem of finding an e.d.s. of minimum weight in a given vertex-weighted graph. Brandstadt, Ficur, Leitert and Milanic (2015) [3] stated the running times of the fastest known polynomial-time algorithms for the MIN-WED problem on some graphs classes by using a Hasse diagram. In this paper, we update this Hasse diagram by showing that, while for every integer d such that d = 3 k or d = 3 k + 2 , where k ≥ 1 , the ED problem remains NP-complete for graphs of diameter d, the weighted version of the problem is solvable in time O ( | V ( G ) | + | E ( G ) | ) in the class of diameter three bipartite graphs and in time O ( | V ( G ) | 5 ) in the class of diameter three planar graphs.

Bitcoin smart contracts allow the development of new protocols on top of Bitcoin itself. This usually involves the definition of complex scripts, far beyond the requirement of a single signature. In this paper we introduce the concept of private key locked transactions, a novel type of transactions that allows the atomic verification of a given private key (belonging to an asymmetric key pair) during the payment execution.