TY - JOUR
AB - In this paper we construct a family of exact functors from the category of Whittaker modules of the simple complex Lie algebra of type to the category of finite-dimensional modules of the graded affine Hecke algebra of type . Using results of Backelin [2] and of Arakawa-Suzuki [1], we prove that these functors map standard modules to standard modules (or zero) and simple modules to simple modules (or zero). Moreover, we show that each simple module of the graded affine Hecke algebra appears as the image of a simple Whittaker module. Since the Whittaker category contains the BGG category as a full subcategory, our results generalize results of Arakawa-Suzuki [1], which in turn generalize Schur-Weyl duality between finite-dimensional representations of and representations of the symmetric group .
AU - Brown, Adam
ID - 6828
JF - Journal of Algebra
SN - 0021-8693
TI - Arakawa-Suzuki functors for Whittaker modules
VL - 538
ER -
TY - CONF
AB - When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability.
AU - Aichholzer, Oswin
AU - Akitaya, Hugo A
AU - Cheung, Kenneth C
AU - Demaine, Erik D
AU - Demaine, Martin L
AU - Fekete, Sandor P
AU - Kleist, Linda
AU - Kostitsyna, Irina
AU - Löffler, Maarten
AU - Masárová, Zuzana
AU - Mundilova, Klara
AU - Schmidt, Christiane
ID - 6989
T2 - Proceedings of the 31st Canadian Conference on Computational Geometry
TI - Folding polyominoes with holes into a cube
ER -
TY - JOUR
AB - Using the geodesic distance on the n-dimensional sphere, we study the expected radius function of the Delaunay mosaic of a random set of points. Specifically, we consider the partition of the mosaic into intervals of the radius function and determine the expected number of intervals whose radii are less than or equal to a given threshold. We find that the expectations are essentially the same as for the Poisson–Delaunay mosaic in n-dimensional Euclidean space. Assuming the points are not contained in a hemisphere, the Delaunay mosaic is isomorphic to the boundary complex of the convex hull in Rn+1, so we also get the expected number of faces of a random inscribed polytope. As proved in Antonelli et al. [Adv. in Appl. Probab. 9–12 (1977–1980)], an orthant section of the n-sphere is isometric to the standard n-simplex equipped with the Fisher information metric. It follows that the latter space has similar stochastic properties as the n-dimensional Euclidean space. Our results are therefore relevant in information geometry and in population genetics.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
ID - 87
IS - 5
JF - Annals of Applied Probability
TI - Random inscribed polytopes have similar radius functions as Poisson-Delaunay mosaics
VL - 28
ER -
TY - CONF
AB - Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex.
AU - Edelsbrunner, Herbert
AU - Virk, Ziga
AU - Wagner, Hubert
ID - 188
TI - Smallest enclosing spheres and Chernoff points in Bregman geometry
VL - 99
ER -
TY - CONF
AB - We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.
AU - Alwen, Joel F
AU - Gazi, Peter
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Osang, Georg F
AU - Pietrzak, Krzysztof Z
AU - Reyzin, Lenoid
AU - Rolinek, Michal
AU - Rybar, Michal
ID - 193
T2 - Proceedings of the 2018 on Asia Conference on Computer and Communication Security
TI - On the memory hardness of data independent password hashing functions
ER -
TY - THES
AB - We describe arrangements of three-dimensional spheres from a geometrical and topological point of view. Real data (fitting this setup) often consist of soft spheres which show certain degree of deformation while strongly packing against each other. In this context, we answer the following questions: If we model a soft packing of spheres by hard spheres that are allowed to overlap, can we measure the volume in the overlapped areas? Can we be more specific about the overlap volume, i.e. quantify how much volume is there covered exactly twice, three times, or k times? What would be a good optimization criteria that rule the arrangement of soft spheres while making a good use of the available space? Fixing a particular criterion, what would be the optimal sphere configuration? The first result of this thesis are short formulas for the computation of volumes covered by at least k of the balls. The formulas exploit information contained in the order-k Voronoi diagrams and its closely related Level-k complex. The used complexes lead to a natural generalization into poset diagrams, a theoretical formalism that contains the order-k and degree-k diagrams as special cases. In parallel, we define different criteria to determine what could be considered an optimal arrangement from a geometrical point of view. Fixing a criterion, we find optimal soft packing configurations in 2D and 3D where the ball centers lie on a lattice. As a last step, we use tools from computational topology on real physical data, to show the potentials of higher-order diagrams in the description of melting crystals. The results of the experiments leaves us with an open window to apply the theories developed in this thesis in real applications.
AU - Iglesias Ham, Mabel
ID - 201
TI - Multiple covers with balls
ER -
TY - GEN
AB - We prove that any convex body in the plane can be partitioned into m convex parts of equal areas and perimeters for any integer m≥2; this result was previously known for prime powers m=pk. We also give a higher-dimensional generalization.
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
AU - Karasev, Roman
ID - 75
TI - Convex fair partitions into arbitrary number of pieces
ER -
TY - JOUR
AB - Inclusion–exclusion is an effective method for computing the volume of a union of measurable sets. We extend it to multiple coverings, proving short inclusion–exclusion formulas for the subset of Rn covered by at least k balls in a finite set. We implement two of the formulas in dimension n=3 and report on results obtained with our software.
AU - Edelsbrunner, Herbert
AU - Iglesias Ham, Mabel
ID - 530
JF - Computational Geometry: Theory and Applications
TI - Multiple covers with balls I: Inclusion–exclusion
VL - 68
ER -
TY - JOUR
AB - Inside a two-dimensional region (``cake""), there are m nonoverlapping tiles of a certain kind (``toppings""). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same ``certain kind,"" such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axis-parallel rectangles. (4) The cake is an axis-parallel rectilinear polygon and the toppings are axis-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks.
AU - Akopyan, Arseniy
AU - Segal Halevi, Erel
ID - 58
IS - 3
JF - SIAM Journal on Discrete Mathematics
TI - Counting blanks in polygonal arrangements
VL - 32
ER -
TY - JOUR
AB - We prove that any cyclic quadrilateral can be inscribed in any closed convex C1-curve. The smoothness condition is not required if the quadrilateral is a rectangle.
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
ID - 6355
JF - Forum of Mathematics, Sigma
SN - 2050-5094
TI - Any cyclic quadrilateral can be inscribed in any closed convex smooth curve
VL - 6
ER -