More Like this

1. A general framework for handling commitment in online throughput maximization

   https://doi.org/10.1007/s10107-020-01469-2  

   Chen, Lin; Eberle, Franziska; Megow, Nicole; Schewior, Kevin; Stein, Cliff (September 2020, Mathematical Programming)

   Abstract We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least $$1+\varepsilon $$ 1 + ε times its processing time, for some $$\varepsilon >0$$ ε > 0 . We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio of  $$\mathcal {O}(1/\varepsilon )$$ O ( 1 / ε ) is the best possible (deterministic) for this problem. For commitment models, we give the first non-trivial performance bounds. If the commitment decisions must be made before a job’s slack becomes less than a $$\delta $$ δ -fraction of its size, we prove a competitive ratio of $$\mathcal {O}(\varepsilon /((\varepsilon -\delta )\delta ^2))$$ O ( ε / ( ( ε - δ ) δ 2 ) ) , for $$0<\delta <\varepsilon $$ 0 < δ < ε . When a provider must commit upon starting a job, our bound is  $$\mathcal {O}(1/\varepsilon ^2)$$ O ( 1 / ε 2 ) . Finally, we observe that for scheduling with commitment the restriction to the “unweighted” throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms. 

   more » « less
2. Breakdown of Regularity of Scattering for Mass-Subcritical NLS

   https://doi.org/10.1093/imrn/rnaa072  

   Lee, Gyu Eun (April 2020, International Mathematics Research Notices)

   null (Ed.)

   Abstract We study the scattering problem for the nonlinear Schrödinger equation $$i\partial _t u + \Delta u = |u|^p u$$ on $$\mathbb{R}^d$$, $$d\geq 1$$, with a mass-subcritical nonlinearity above the Strauss exponent. For this equation, it is known that asymptotic completeness in $L^2$ with initial data in $$\Sigma$$ holds and the wave operator is well defined on $$\Sigma$$. We show that there exists $$0<\beta <p$$ such that the wave operator and the data-to-scattering-state map do not admit extensions to maps $$L^2\to L^2$$ of class $$C^{1+\beta }$$ near the origin. This constitutes a mild form of ill-posedness for the scattering problem in the $L^2$ topology. 

   more » « less
3. On lower bounds for Erdős-Szekeres products

   https://doi.org/10.1090/proc/15503  

   Billsborough, C.; Freedman, M.; Hart, S.; Kowalsky, G.; Lubinsky, D.; Pomeranz, A.; Sammel, A. (October 2021, Proceedings of the American Mathematical Society)

   Let { s j } j = 1 n \left \{ s_{j}\right \} _{j=1}^{n} be positive integers. We show that for any 1 ≤ L ≤ n , 1\leq L\leq n, ‖ ∏ j = 1 n ( 1 − z s j ) ‖ L ∞ ( | z | = 1 ) ≥ exp ⁡ ( 1 2 e L ( s 1 s 2 … s L ) 1 / L ) . \begin{equation*} \left \Vert \prod _{j=1}^{n}\left ( 1-z^{s_{j}}\right ) \right \Vert _{L_{\infty }\left ( \left \vert z\right \vert =1\right ) }\geq \exp \left ( \frac {1}{2e}\frac {L}{\left ( s_{1}s_{2}\ldots s_{L}\right ) ^{1/L}}\right ) . \end{equation*} In particular, this gives geometric growth if a positive proportion of the { s j } \left \{ s_{j}\right \} are bounded. We also show that when the { s j } \left \{ s_{j}\right \} grow regularly and faster than j ( log ⁡ j ) 2 + ε j\left ( \log j\right ) ^{2+\varepsilon } , some ε > 0 \varepsilon >0 , then the norms grow faster than exp ⁡ ( ( log ⁡ n ) 1 + δ ) \exp \left ( \left ( \log n\right ) ^{1+\delta }\right ) for some δ > 0 \delta >0 . 

   more » « less
4. A trade-off between classical and quantum circuit size for an attack against CSIDH

   https://doi.org/10.1515/jmc-2020-0070  

   Biasse, Jean-François; Bonnetain, Xavier; Pring, Benjamin; Schrottenloher, André; Youmans, William (November 2020, Journal of Mathematical Cryptology)

   null (Ed.)

   Abstract We propose a heuristic algorithm to solve the underlying hard problem of the CSIDH cryptosystem (and other isogeny-based cryptosystems using elliptic curves with endomorphism ring isomorphic to an imaginary quadratic order 𝒪). Let Δ = Disc(𝒪) (in CSIDH, Δ = −4 p for p the security parameter). Let 0 < α < 1/2, our algorithm requires: A classical circuit of size 2 O ˜ log ( | Δ | ) 1 − α . $$2^{\tilde{O}\left(\log(|\Delta|)^{1-\alpha}\right)}.$$ A quantum circuit of size 2 O ˜ log ( | Δ | ) α . $$2^{\tilde{O}\left(\log(|\Delta|)^{\alpha}\right)}.$$ Polynomial classical and quantum memory. Essentially, we propose to reduce the size of the quantum circuit below the state-of-the-art complexity 2 O ˜ log ( | Δ | ) 1 / 2 $$2^{\tilde{O}\left(\log(|\Delta|)^{1/2}\right)}$$ at the cost of increasing the classical circuit-size required. The required classical circuit remains subexponential, which is a superpolynomial improvement over the classical state-of-the-art exponential solutions to these problems. Our method requires polynomial memory, both classical and quantum. 

   more » « less
5. Physical limits to sensing material properties

   https://doi.org/10.1038/s41467-020-18995-4  

   Beroz, Farzan; Zhou, Di; Mao, Xiaoming; Lubensky, David K. (December 2020, Nature Communications)

   null (Ed.)

   Abstract All materials respond heterogeneously at small scales, which limits what a sensor can learn. Although previous studies have characterized measurement noise arising from thermal fluctuations, the limits imposed by structural heterogeneity have remained unclear. In this paper, we find that the least fractional uncertainty with which a sensor can determine a material constant λ 0 of an elastic medium is approximately $$\delta {\lambda }_{0}/{\lambda }_{0} \sim ({\Delta }_{\lambda }^{1/2}/{\lambda }_{0}){(d/a)}^{D/2}{(\xi /a)}^{D/2}$$ δ λ 0 / λ 0 ~ ( Δ λ 1 / 2 / λ 0 ) ( d / a ) D / 2 ( ξ / a ) D / 2 for a  ≫  d  ≫  ξ , $${\lambda }_{0}\gg {\Delta }_{\lambda }^{1/2}$$ λ 0 ≫ Δ λ 1 / 2 , and D  > 1, where a is the size of the sensor, d is its spatial resolution, ξ is the correlation length of fluctuations in λ 0 , Δ λ is the local variability of λ 0 , and D is the dimension of the medium. Our results reveal how one can construct devices capable of sensing near these limits, e.g. for medical diagnostics. We use our theoretical framework to estimate the limits of mechanosensing in a biopolymer network, a sensory process involved in cellular behavior, medical diagnostics, and material fabrication. 

   more » « less