On piercing (pseudo)lines and boxes

We say a family of geometric objects C has (l;k)-property if every subfamily C0C of cardinality at most lisk- piercable. In this paper we investigate the existence of g(k;d)such that if any family of objects C in Rd has the (g(k;d);k)-property, then C is k-piercable. Danzer and Gr̈ unbaum showed that g(k;d)is infinite for fami-lies of boxes and translates of centrally symmetric convex hexagons. In this paper we show that any family of pseudo-lines(lines) with (k2+k+ 1;k)-property is k-piercable and extend this result to certain families of objects with discrete intersections. This is the first positive result for arbitrary k for a general family of objects. We also pose a relaxed ver-sion of the above question and show that any family of boxes in Rd with (k2d;k)-property is 2dk- piercable.

Upper Bounds on the Size of Grain-Correcting Codes

In this paper, we revisit the combinatorial error model of Mazumdar et al. that models errors in high-density magnetic recording caused by lack of knowledge of grain boundaries in the recording medium. We present new upper bounds on the cardinality/rate of binary block codes that correct errors within this model. All our bounds, except for one, are obtained using combinatorial arguments based on hypergraph fractional coverings. The exception is a bound derived via an information-theoretic argument. Our bounds significantly improve upon existing bounds from the prior literature.

SEPARATION DIMENSION OF BOUNDED DEGREE GRAPHS

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in R-k such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Theta(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least d/2]

Novel Design of Honeycombs Using a Seamless Combination of Auxetic and Conventional Cores Toward Phononic Band Gap Engineering

A novel design for the geometric configuration of honeycombs using a seamless combination of auxetic and conventional cores- elements with negative and positive Possion ratios respectively, has been presented. The proposed design has been shown to generate a superior band gap property while retaining all major advantages of a purely conventional or purely auxetic honeycomb structure. Seamless combination ensures that joint cardinality is also retained. Several configurations involving different degree of auxeticity and different proportions auxetic and conventional elements have been analyzed. It has been shown that the preferred configurations open up wide and clean band gap at a significantly lower frequency ranges compared to their pure counterparts. In view of existence of band gaps being desired feature for the phononic applications, reported results might be appealing. Use of such design may enable superior vibration control as well. Proposed configurations can be made isovolumic and iso-weight giving designers a fairer ground of applying such configurations without significantly changing size and weight criteria.

On the Bounds of Certain Maximal Linear Codes in a Projective Space

The set of all subspaces of F-q(n) is denoted by P-q(n). The subspace distance d(S)(X, Y) = dim(X) + dim(Y)-2dim(X boolean AND Y) defined on P-q(n) turns it into a natural coding space for error correction in random network coding. A subset of P-q(n) is called a code and the subspaces that belong to the code are called codewords. Motivated by classical coding theory, a linear coding structure can be imposed on a subset of P-q(n). Braun et al. conjectured that the largest cardinality of a linear code, that contains F-q(n), is 2(n). In this paper, we prove this conjecture and characterize the maximal linear codes that contain F-q(n).

Efficient Protocol for Authenticated Email Search

Executing authenticated computation on outsourced data is currently an area of major interest in cryptology. Large databases are being outsourced to untrusted servers without appreciable verification mechanisms. As adversarial server could produce erroneous output, clients should not trust the server's response blindly. Primitive set operations like union, set difference, intersection etc. can be invoked on outsourced data in different concrete settings and should be verifiable by the client. One such interesting adaptation is to authenticate email search result where the untrusted mail server has to provide a proof along with the search result. Recently Ohrimenko et al. proposed a scheme for authenticating email search. We suggest significant improvements over their proposal in terms of client computation and communication resources by properly recasting it in two-party settings. In contrast to Ohrimenko et al. we are able to make the number of bilinear pairing evaluation, the costliest operation in verification procedure, independent of the result set cardinality for union operation. We also provide an analytical comparison of our scheme with their proposal which is further corroborated through experiments.

On Fast Bilateral Filtering Using Fourier Kernels

It was demonstrated in earlier work that, by approximating its range kernel using shiftable functions, the nonlinear bilateral filter can be computed using a series of fast convolutions. Previous approaches based on shiftable approximation have, however, been restricted to Gaussian range kernels. In this work, we propose a novel approximation that can be applied to any range kernel, provided it has a pointwise-convergent Fourier series. More specifically, we propose to approximate the Gaussian range kernel of the bilateral filter using a Fourier basis, where the coefficients of the basis are obtained by solving a series of least-squares problems. The coefficients can be efficiently computed using a recursive form of the QR decomposition. By controlling the cardinality of the Fourier basis, we can obtain a good tradeoff between the run-time and the filtering accuracy. In particular, we are able to guarantee subpixel accuracy for the overall filtering, which is not provided by the most existing methods for fast bilateral filtering. We present simulation results to demonstrate the speed and accuracy of the proposed algorithm.