Search

In the general max-min fair allocation problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c /1-C , where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c((sic) )+ O(delta c((sic)2))), where c circumflex expressionccent is the maximum ratio of the largest utility to the smallest positive utility of any resource.

We present a novel full hardware implementation of Streamlined NTRU Prime, with two variants: a high-speed, high-area implementation and a slower, low-area implementation. We introduce several new techniques that improve performance, including a batch inversion for key generation, a high-speed schoolbook polynomial multiplier, an NTT polynomial multiplier combined with a CRT map, a new DSP-free modular reduction method, a high-speed radix sorting module, and new encoders and decoders. With the high-speed design, we achieve the to-date fastest speeds for Streamlined NTRU Prime, with speeds of 5007, 10,989, and 64,026 cycles for encapsulation, decapsulation, and key generation, respectively, while running at 285 MHz on a Xilinx Zynq Ultrascale+. The entire design uses 40,060 LUT, 26,384 flip-flops, 36.5 Bram, and 31 DSP.

We study the power of uncontrolled random molecular movement in a model of self-assembly called the nubots model. The nubots model is an asynchronous nondeterministic cellular automaton augmented with rigid-body movement rules (push/pull, deterministically and programmatically applied to specific monomers) and random agitations (nondeterministically applied to every monomer and direction with equal probability all of the time). Previous work on nubots showed how to build simple shapes such as lines and squares quickly—in expected time that is merely logarithmic of their size. These results crucially make use of the programmable rigid-body movement rule: the ability for a single monomer to push or pull large objects quickly, and only at a time and place of the programmers’ choosing. However, in engineered molecular systems, molecular motion is largely uncontrolled and fundamentally random. This raises the question of whether similar results can be achieved in a more restrictive, and perhaps easier to justify, model where uncontrolled random movements, or agitations, are happening throughout the self-assembly process and are the only form of rigid-body movement. We show that this is indeed the case: we give a polylogarithmic expected time construction for squares using agitation, and a sublinear expected time construction to build a line. Such results are impossible in an agitation-free (and movement-free) setting and thus show the benefits of exploiting uncontrolled random movement.

Winfree’s abstract Tile Assembly Model (aTAM) is a model of molecular self-assembly of DNA complexes known as tiles, which float freely in solution and attach one at a time to a growing “seed” assembly based on specific binding sites on their four sides. We show that there is a polynomial-time algorithm that, given an n ×n square, finds the minimal tile system (i.e., the system with the smallest number of distinct tile types) that uniquely self-assembles the square, answering an open question of Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanés, and Rothemund (Combinatorial Optimization Problems in Self-Assembly, STOC 2002). Our investigation leading to this algorithm reveals other positive and negative results about the relationship between the size of a tile system and its “temperature” (the binding strength threshold required for a tile to attach).

DNA tile self-assembly has emerged as a rich and promising primitive for nano-technology. This paper studies the problems of minimizing assembly time and error rate by changing the tile concentrations because changing the tile concentrations is easy to implement in actual lab experiments. We prove that setting the concentration of tile T_i proportional to the square root of N_i where N_i is the number of times T_i appears outside the seed structure in the final assembled shape minimizes the rate of growth errors for rectilinear tile systems. We also show that t he same concentrations minimize the expected assembly time for a feasible class of tile systems. Moreover, for general tile systems, given tile concentrations, we can approximate the expected assembly time with high accuracy and probability by running only a polynomial number of simulations in the size of the target shape.