654 research outputs found
Monetary policy and the banking sector in Turkey
No full textWe find that monetary policy influenced Turkish bank lending between 1991 and 2007 through the money and bank lending channels. While capital and GDP growth have positive and significant long-run effects on bank loan growth, inflation, bank size and efficiency are not significant determinants. The latter is despite our finding that all Turkish banks' efficiency improved over the period. Domestic banks are unexpectedly found to be more efficient than foreign banks. With no evident dynamics or fixed-effects in loan growth we prefer the pooled-OLS estimator. We caution against assuming fixed-effects and dynamics are present as this may adversely affect inference. © 2013 Elsevier B.V
Computing many faces in arrangements of lines and segments
No full textWe present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. pn The main new idea is a simple randomized O(n log n) expected time algorithm for computing root n cells in an arrangement of n lines.A part of this work was done while the first and third authors were visiting Charles University and while the first author was visiting Utrecht University. The first author has been supported by National Science Foundation Grant CCR-93-01259 and an NYI aword. The second author has been supported by Charles University grant No. 351 and Czech Republic Grant GACR 201/93/2167. The third author has been supported by the Netherlands' Organization for Scientific Research (NWO) and partially supported by ESPRIT Basic Research Action No. 7141 (project ALCOM 2:Algorithms and Complexity)
ON RAY SHOOTING IN CONVEX POLYTOPES
No full textLet P be a convex polytope with n facets in the Euclidean space of a (small) fixed dimension d. We consider the membership problem for P (given a query point, decide whether it lies in P) and the ray shooting problem in P (given a query ray originating inside P, determine the first facet of P hit by it). It was shown in [AM2] that a data structure for the membership problem satisfying certain mild assumptions can also be used for the ray shooting problem, with a logarithmic overhead in query time, Here we show that some specific data structures for the membership problem can be used for ray shooting in a more direct way, reducing the overhead in the query time and eliminating the use of parametric search. We also describe an improved static solution for the membership problem, approaching the conjectured lower bounds more tightly
From Disruption to Post-pandemic Scenario
No full textFollowing the previous Chapter 18, this concluding this chapter (Part 2 of two) puts forward options for regulators triggered by COVID-19, bringing to the conclusion that the pandemic is an unprecedented opportunity to redefining boundaries and refocusing the priority on innovation for transparency. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2021
Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
No full textWe present optimal deterministic algorithms for constructing shallow cuttings in an arrangement of lines in two dimensions or planes in three dimensions. Our results improve the deterministic polynomial-time algorithm of Matousek (1992) and the optimal but randomized algorithm of Ramos (1999). This leads to efficient derandomization of previous algorithms for numerous well-studied problems in computational geometry, including halfspace range reporting in 2-d and 3-d, k nearest neighbors search in 2-d, (<= k)-levels in 3-d, order-k Voronoi diagrams in 2-d, linear programming with k violations in 2-d, dynamic convex hulls in 3-d, dynamic nearest neighbor search in 2-d, convex layers (onion peeling) in 3-d, epsilon-nets for halfspace ranges in 3-d, and more. As a side product we also describe an optimal deterministic algorithm for constructing standard (non-shallow) cuttings in two dimensions, which is arguably simpler than the known optimal algorithms by Matousek (1991) and Chazelle (1993)
Curves in R-d intersecting every hyperplane at most d+1 times
No full textBy a curve in R-d we mean a continuous map gamma : I -> R-d, where I subset of R is a closed interval. We call a curve gamma in R-d (<= k)-crossing if it intersects every hyperplane at most k times (counted with multiplicity). The (<= d)-crossing curves in R-d are often called convex curves and they form an important class; a primary example is the moment curve {(t, t(2) , . . . , t(d) ) : t is an element of[0, 1]}. They are also closely related to Chebyshev systems, which is a notion of considerable importance, e.g., in approximation theory. Our main result is that for every d there is M = M (d) such that every (<= d+1)-crossing curve in R-d can be subdivided into at most M (<= d)-crossing curve segments. As a consequence, based on the work of Elias, Roldan, Safernova, and the second author, we obtain an essentially tight lower bound for a geometric Ramsey-type problem in R-d concerning order-type homogeneous sequences of points, investigated in several previous papers
Quantum sign permutation polytopes
No full textConvex polytopes are convex hulls of point sets in the n-dimensional space E n that generalize 2-dimensional convex polygons and 3-dimensional convex polyhedra. We concentrate on the class of n-dimensional polytopes in E n called sign permutation polytopes. We characterize sign permutation polytopes before relating their construction to constructions over the space of quantum density matrices. Finally, we consider the problem of state identication and show how sign permutation polytopes may be useful in addressing issues of robustness
On Galleries With No Bad Points
No full textFor any k we construct a simply connected compact set (art gallery) in IR 3 whose every point sees a positive fraction (in fact, more than 5 9 ) of the gallery, but the whole gallery cannot be guarded by k guards. This disproves a conjecture of Kavraki, Latombe, Motwani, and Raghavan. 1 Introduction Consider an art gallery (i.e., compact set) X of Lebesgue measure 1 in IR d ; d 2, such that a guard placed anywhere in the gallery sees a region of Lebesgue measure at least ". Kavraki, Latombe, Motwani, and Raghavan [KLMR] conjectured that if X has at most h holes then it can be guarded by at most f d (h; ") guards, for some function f d polynomial in h and 1 " . Kalai and Matousek [KM] proved a weaker form of the planar version of the conjecture (their function f 2 was not polynomial in h). Following some ideas of Kalai and Matousek, the author [Va] proved the planar version of the conjecture with f 2 (h; ") = (2 + o(1)) 1 " log 1 " log 2 (h + 2). Kalai and Matousek [KM]..
ClassBench-ng: Benchmarking Packet Classification Algorithms in the OpenFlow Era
No full textPacket classification, i.e., the process of categorizing packets into flows, is a first-class citizen in any networking device. Every time a new packet has to be processed, one or more header fields need to be compared against a set of pre-installed rules. This is done for basic forwarding operations, to apply security policies, application-specific processing, or quality-of-service guarantees. A lot of research efforts have identified better lookup techniques, i.e., finding the best match between packet headers and rules, by capitalizing on the rule sets characteristics. Here, ClassBench has greatly served the community by enabling the generation of IPv4 rule sets. In this paper, we present a new tool, ClassBench-ng, that creates synthetic IPv4, IPv6, and OpenFlow rules. We start from an analysis of classification rules deployed in-the-wild and we use the findings to craft our solution. ClassBench-ng can generate a user-defined number of rules as well as an associated header trace matching them. Compared to state-of-the-art solutions, the rule set generation process is usually more accurate and it is able to produce rules matching a number of different use cases, i.e., from an IPv4 router to an OpenFlow switch, which is unique among current rule set generation tools
A lower bound on the size of Lipschitz subsets in dimension 3
No full textA set S R is C-Lipschitz in the x i -coordinate, where C > 0 is a real number, if for every two points a; b 2 S, we have ja i b i j C maxfja j b j j : j = 1; 2; : : : ; d; j 6= ig. Motivated by a problem of Laczkovich, the author asked whether every n-point set in R contains a subset of size at least cn that is C-Lipschitz in one of the coordinates, for suitable constants C and c > 0 (depending on d). This wa
- …
