@inproceedings{6340, abstract = {We present a secure approach for maintaining andreporting credit history records on the Blockchain. Our ap-proach removes third-parties such as credit reporting agen-cies from the lending process and replaces them with smartcontracts. This allows customers to interact directly with thelenders or banks while ensuring the integrity, unmalleabilityand privacy of their credit data. Additionally, each customerhas full control over complete or selective disclosure of hercredit records, eliminating the risk of privacy violations or databreaches. Moreover, our approach provides strong guaranteesfor the lenders as well. A lender can check both correctness andcompleteness of the credit data disclosed to her. This is the firstapproach that can perform all credit reporting tasks withouta central authority or changing the financial mechanisms*.}, author = {Goharshady, Amir Kafshdar and Behrouz, Ali and Chatterjee, Krishnendu}, booktitle = {Proceedings of the IEEE International Conference on Blockchain}, isbn = {978-1-5386-7975-3 }, location = {Halifax, Canada}, pages = {1343--1348}, publisher = {IEEE}, title = {{Secure Credit Reporting on the Blockchain}}, doi = {10.1109/Cybermatics_2018.2018.00231}, year = {2018}, } @article{461, abstract = {Turbulence is the major cause of friction losses in transport processes and it is responsible for a drastic drag increase in flows over bounding surfaces. While much effort is invested into developing ways to control and reduce turbulence intensities, so far no methods exist to altogether eliminate turbulence if velocities are sufficiently large. We demonstrate for pipe flow that appropriate distortions to the velocity profile lead to a complete collapse of turbulence and subsequently friction losses are reduced by as much as 90%. Counterintuitively, the return to laminar motion is accomplished by initially increasing turbulence intensities or by transiently amplifying wall shear. Since neither the Reynolds number nor the shear stresses decrease (the latter often increase), these measures are not indicative of turbulence collapse. Instead, an amplification mechanism measuring the interaction between eddies and the mean shear is found to set a threshold below which turbulence is suppressed beyond recovery.}, author = {Kühnen, Jakob and Song, Baofang and Scarselli, Davide and Budanur, Nazmi B and Riedl, Michael and Willis, Ashley and Avila, Marc and Hof, Björn}, journal = {Nature Physics}, pages = {386--390}, publisher = {Nature Publishing Group}, title = {{Destabilizing turbulence in pipe flow}}, doi = {10.1038/s41567-017-0018-3}, volume = {14}, year = {2018}, } @article{11066, abstract = {Recent studies have shown that a subset of nucleoporins (Nups) can detach from the nuclear pore complex and move into the nuclear interior to regulate transcription. One such dynamic Nup, called Nup98, has been implicated in gene activation in healthy cells and has been shown to drive leukemogenesis when mutated in patients with acute myeloid leukemia (AML). Here we show that in hematopoietic cells, Nup98 binds predominantly to transcription start sites to recruit the Wdr82–Set1A/COMPASS (complex of proteins associated with Set1) complex, which is required for deposition of the histone 3 Lys4 trimethyl (H3K4me3)-activating mark. Depletion of Nup98 or Wdr82 abolishes Set1A recruitment to chromatin and subsequently ablates H3K4me3 at adjacent promoters. Furthermore, expression of a Nup98 fusion protein implicated in aggressive AML causes mislocalization of H3K4me3 at abnormal regions and up-regulation of associated genes. Our findings establish a function of Nup98 in hematopoietic gene activation and provide mechanistic insight into which Nup98 leukemic fusion proteins promote AML.}, author = {Franks, Tobias M. and McCloskey, Asako and Shokhirev, Maxim Nikolaievich and Benner, Chris and Rathore, Annie and HETZER, Martin W}, issn = {0890-9369}, journal = {Genes & Development}, keywords = {Developmental Biology, Genetics}, number = {22}, pages = {2222--2234}, publisher = {Cold Spring Harbor Laboratory}, title = {{Nup98 recruits the Wdr82–Set1A/COMPASS complex to promoters to regulate H3K4 trimethylation in hematopoietic progenitor cells}}, doi = {10.1101/gad.306753.117}, volume = {31}, year = {2017}, } @article{1110, abstract = {The phytohormone auxin is a major determinant and regulatory component important for plant development. Auxin transport between cells is mediated by a complex system of transporters such as AUX1/LAX, PIN, and ABCB proteins, and their localization and activity is thought to be influenced by phosphatases and kinases. Flavonols have been shown to alter auxin transport activity and changes in flavonol accumulation in the Arabidopsis thaliana rol1-2 mutant cause defects in auxin transport and seedling development. A new mutation in ROOTS CURL IN NPA 1 (RCN1), encoding a regulatory subunit of the phosphatase PP2A, was found to suppress the growth defects of rol1-2 without changing the flavonol content. rol1-2 rcn1-3 double mutants show wild type-like auxin transport activity while levels of free auxin are not affected by rcn1-3. In the rol1-2 mutant, PIN2 shows a flavonol-induced basal-to-apical shift in polar localization which is reversed in the rol1-2 rcn1-3 to basal localization. In vivo analysis of PINOID action, a kinase known to influence PIN protein localization in a PP2A-antagonistic manner, revealed a negative impact of flavonols on PINOID activity. Together, these data suggest that flavonols affect auxin transport by modifying the antagonistic kinase/phosphatase equilibrium.}, author = {Kuhn, Benjamin and Nodzyński, Tomasz and Errafi, Sanae and Bucher, Rahel and Gupta, Shibu and Aryal, Bibek and Dobrev, Petre and Bigler, Laurent and Geisler, Markus and Zažímalová, Eva and Friml, Jirí and Ringli, Christoph}, issn = {2045-2322}, journal = {Scientific Reports}, publisher = {Nature Publishing Group}, title = {{Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity}}, doi = {10.1038/srep41906}, volume = {7}, year = {2017}, } @inproceedings{1116, abstract = {Time-triggered switched networks are a deterministic communication infrastructure used by real-time distributed embedded systems. Due to the criticality of the applications running over them, developers need to ensure that end-to-end communication is dependable and predictable. Traditional approaches assume static networks that are not flexible to changes caused by reconfigurations or, more importantly, faults, which are dealt with in the application using redundancy. We adopt the concept of handling faults in the switches from non-real-time networks while maintaining the required predictability. We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. For a given network with a forwarding scheme and a constant ℓ, we compute the {\em score} of the scheme, namely the probability (induced by faults) that at least ℓ messages arrive on time. We reduce the scoring problem to a reachability problem on a Markov chain with a "product-like" structure. Its special structure allows us to reason about it symbolically, and reduce the scoring problem to #SAT. Our solution is generic and can be adapted to different networks and other contexts. Also, we show the computational complexity of the scoring problem is #P-complete, and we study methods to estimate the score. We evaluate the effectiveness of our techniques with an implementation. }, author = {Avni, Guy and Goel, Shubham and Henzinger, Thomas A and Rodríguez Navas, Guillermo}, issn = {0302-9743}, location = {Uppsala, Sweden}, pages = {169 -- 187}, publisher = {Springer}, title = {{Computing scores of forwarding schemes in switched networks with probabilistic faults}}, doi = {10.1007/978-3-662-54580-5_10}, volume = {10206}, year = {2017}, } @article{1146, abstract = {Aim: The present study was to compare the effects of nicotinic acid and nicotinamide on the plasma methyl donors, choline and betaine. Methods: Thirty adult subjects were randomly divided into three groups of equal size, and orally received purified water (C group), nicotinic acid (300 mg, NA group) or nicotinamide (300 mg, NM group). Plasma nicotinamide, N 1-methylnicotinamide, homocysteine, betaine and choline levels before and 1.5-h and 3-h post-dosing, plasma normetanephrine and metanephrine concentrations at 3-h post-dosing, and the urinary excretion of N 1-methyl-2-pyridone-5-carboxamide during the test period were examined. Results: The level of 3-h plasma nicotinamide, N 1-methylnicotinamide, homocysteine, the urinary excretion of N 1-methyl-2-pyridone-5-carboxamide and pulse pressure (PP) in the NM group was 221%, 3972%, 61%, 1728% and 21.2% higher than that of the control group (P < 0.01, except homocysteine and PP P < 0.05), while the 3-h plasma betaine, normetanephrine and metanephrine level in the NM group was 24.4%, 9.4% and 11.7% lower (P < 0.05, except betaine P < 0.01), without significant difference in choline levels. Similar but less pronounced changes were observed in the NA group, with a lower level of 3-h plasma N 1-methylnicotinamide (1.90 ± 0.20 μmol/l vs. 3.62 ± 0.27 μmol/l, P < 0.01) and homocysteine (12.85 ± 1.39 μmol/l vs. 18.08 ± 1.02 μmol/l, P < 0.05) but a higher level of betaine (27.44 ± 0.71 μmol/l vs. 23.52 ± 0.61 μmol/l, P < 0.05) than that of the NM group. Conclusion: The degradation of nicotinamide consumes more betaine than that of nicotinic acid at identical doses. This difference should be taken into consideration in niacin fortification. © 2016 Elsevier Ltd and European Society for Clinical Nutrition and Metabolism.}, author = {Sun, Wuping and Zhai, Ming-Zhu and Li, Da and Zhou, Yiming and Chen, Nana and Guo, Ming and Zhou, Shisheng}, issn = {0261-5614}, journal = {Clinical Nutrition}, number = {4}, pages = {1136--1142}, publisher = {Elsevier}, title = {{Comparison of the effects of nicotinic acid and nicotinamide degradation on plasma betaine and choline levels}}, doi = {10.1016/j.clnu.2016.07.016}, volume = {36}, year = {2017}, } @article{11561, abstract = {We present a sample of ∼1000 emission-line galaxies at z = 0.4–4.7 from the ∼0.7deg2 High-z Emission-Line Survey in the Boötes field identified with a suite of six narrow-band filters at ≈0.4–2.1 μm. These galaxies have been selected on their Ly α (73), [O II] (285), H β/[O III] (387) or H α (362) emission line, and have been classified with optical to near-infrared colours. A subsample of 98 sources have reliable redshifts from multiple narrow-band (e.g. [O II]–H α) detections and/or spectroscopy. In this survey paper, we present the observations, selection and catalogues of emitters. We measure number densities of Ly α, [O II], H β/[O III] and H α and confirm strong luminosity evolution in star-forming galaxies from z ∼ 0.4 to ∼5, in agreement with previous results. To demonstrate the usefulness of dual-line emitters, we use the sample of dual [O II]–H α emitters to measure the observed [O II]/H α ratio at z = 1.47. The observed [O II]/H α ratio increases significantly from 0.40 ± 0.01 at z = 0.1 to 0.52 ± 0.05 at z = 1.47, which we attribute to either decreasing dust attenuation with redshift, or due to a bias in the (typically) fibre measurements in the local Universe that only measure the central kpc regions. At the bright end, we find that both the H α and Ly α number densities at z ≈ 2.2 deviate significantly from a Schechter form, following a power law. We show that this is driven entirely by an increasing X-ray/active galactic nucleus fraction with line luminosity, which reaches ≈100 per cent at line luminosities L ≳ 3 × 1044 erg s−1.}, author = {Matthee, Jorryt J and Sobral, David and Best, Philip and Smail, Ian and Bian, Fuyan and Darvish, Behnam and Röttgering, Huub and Fan, Xiaohui}, issn = {0035-8711}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics galaxies, active, galaxies, evolution, galaxies, high-redshift, galaxies, luminosity function, mass function, galaxies: star formation}, number = {1}, pages = {629--649}, publisher = {Oxford University Press}, title = {{Boötes-HiZELS: An optical to near-infrared survey of emission-line galaxies at z = 0.4–4.7}}, doi = {10.1093/mnras/stx1569}, volume = {471}, year = {2017}, } @article{11562, abstract = {We present the CAlibrating LYMan-α with Hα (CALYMHA) pilot survey and new results on Lyman α (Lyα) selected galaxies at z ∼ 2. We use a custom-built Lyα narrow-band filter at the Isaac Newton Telescope, designed to provide a matched volume coverage to the z = 2.23 Hα HiZELS survey. Here, we present the first results for the COSMOS and UDS fields. Our survey currently reaches a 3σ line flux limit of ∼4 × 10−17 erg s−1 cm−2, and a Lyα luminosity limit of ∼1042.3 erg s−1. We find 188 Lyα emitters over 7.3 × 105 Mpc3, but also find significant numbers of other line-emitting sources corresponding to He II, C III] and C IV emission lines. These sources are important contaminants, and we carefully remove them, unlike most previous studies. We find that the Lyα luminosity function at z = 2.23 is very well described by a Schechter function up to LLy α ≈ 1043 erg s−1 with L∗=1042.59+0.16−0.08 erg s−1, ϕ∗=10−3.09+0.14−0.34 Mpc−3 and α = −1.75 ± 0.25. Above LLy α ≈ 1043 erg s−1, the Lyα luminosity function becomes power-law like, driven by X-ray AGN. We find that Lyα-selected emitters have a high escape fraction of 37 ± 7 per cent, anticorrelated with Lyα luminosity and correlated with Lyα equivalent width. Lyα emitters have ubiquitous large (≈40 kpc) Lyα haloes, ∼2 times larger than their Hα extents. By directly comparing our Lyα and Hα luminosity functions, we find that the global/overall escape fraction of Lyα photons (within a 13 kpc radius) from the full population of star-forming galaxies is 5.1 ± 0.2 per cent at the peak of the star formation history. An extra 3.3 ± 0.3 per cent of Lyα photons likely still escape, but at larger radii.}, author = {Sobral, David and Matthee, Jorryt J and Best, Philip and Stroe, Andra and Röttgering, Huub and Oteo, Iván and Smail, Ian and Morabito, Leah and Paulino-Afonso, Ana}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: haloes, galaxies: high-redshift, galaxies: luminosity function, mass function, galaxies: statistics, cosmology: observations}, number = {1}, pages = {1242--1258}, publisher = {Oxford University Press}, title = {{The CALYMHA survey: Lyα luminosity function and global escape fraction of Lyα photons at z = 2.23}}, doi = {10.1093/mnras/stw3090}, volume = {466}, year = {2017}, } @article{11564, abstract = {We study the production rate of ionizing photons of a sample of 588 Hα emitters (HAEs) and 160 Lyman-α emitters (LAEs) at z = 2.2 in the COSMOS field in order to assess the implied emissivity from galaxies, based on their ultraviolet (UV) luminosity. By exploring the rest-frame Lyman Continuum (LyC) with GALEX/NUV data, we find fesc < 2.8 (6.4) per cent through median (mean) stacking. By combining the Hα luminosity density with intergalactic medium emissivity measurements from absorption studies, we find a globally averaged 〈fesc〉 of 5.9+14.5−4.2 per cent at z = 2.2 if we assume HAEs are the only source of ionizing photons. We find similarly low values of the global 〈fesc〉 at z ≈ 3–5, also ruling out a high 〈fesc〉 at z < 5. These low escape fractions allow us to measure ξion, the number of produced ionizing photons per unit UV luminosity, and investigate how this depends on galaxy properties. We find a typical ξion ≈ 1024.77 ± 0.04 Hz erg−1 for HAEs and ξion ≈ 1025.14 ± 0.09 Hz erg−1 for LAEs. LAEs and low-mass HAEs at z = 2.2 show similar values of ξion as typically assumed in the reionization era, while the typical HAE is three times less ionizing. Due to an increasing ξion with increasing EW(Hα), ξion likely increases with redshift. This evolution alone is fully in line with the observed evolution of ξion between z ≈ 2 and 5, indicating a typical value of ξion ≈ 1025.4 Hz erg−1 in the reionization era.}, author = {Matthee, Jorryt J and Sobral, David and Best, Philip and Khostovan, Ali Ahmad and Oteo, Iván and Bouwens, Rychard and Röttgering, Huub}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: high-redshift, cosmology: observations, dark ages, reionization, first stars}, number = {3}, pages = {3637--3655}, publisher = {Oxford University Press}, title = {{The production and escape of Lyman-Continuum radiation from star-forming galaxies at z ∼ 2 and their redshift evolution}}, doi = {10.1093/mnras/stw2973}, volume = {465}, year = {2017}, } @article{11572, abstract = {We present spectroscopic follow-up of candidate luminous Ly α emitters (LAEs) at z = 5.7–6.6 in the SA22 field with VLT/X-SHOOTER. We confirm two new luminous LAEs at z = 5.676 (SR6) and z = 6.532 (VR7), and also present HST follow-up of both sources. These sources have luminosities LLy α ≈ 3 × 1043 erg s−1, very high rest-frame equivalent widths of EW0 ≳ 200 Å and narrow Ly α lines (200–340 km s−1). VR7 is the most UV-luminous LAE at z > 6.5, with M1500 = −22.5, even brighter in the UV than CR7. Besides Ly α, we do not detect any other rest-frame UV lines in the spectra of SR6 and VR7, and argue that rest-frame UV lines are easier to observe in bright galaxies with low Ly α equivalent widths. We confirm that Ly α line widths increase with Ly α luminosity at z = 5.7, while there are indications that Ly α lines of faint LAEs become broader at z = 6.6, potentially due to reionization. We find a large spread of up to 3 dex in UV luminosity for >L⋆ LAEs, but find that the Ly α luminosity of the brightest LAEs is strongly related to UV luminosity at z = 6.6. Under basic assumptions, we find that several LAEs at z ≈ 6–7 have Ly α escape fractions ≳ 100  per cent, indicating bursty star formation histories, alternative Ly α production mechanisms, or dust attenuating Ly α emission differently than UV emission. Finally, we present a method to compute ξion, the production efficiency of ionizing photons, and find that LAEs at z ≈ 6–7 have high values of log10(ξion/Hz erg−1) ≈ 25.51 ± 0.09 that may alleviate the need for high Lyman-Continuum escape fractions required for reionization.}, author = {Matthee, Jorryt J and Sobral, David and Darvish, Behnam and Santos, Sérgio and Mobasher, Bahram and Paulino-Afonso, Ana and Röttgering, Huub and Alegre, Lara}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution – galaxies: high-redshift, dark ages, reionization, first stars, cosmology: observations}, number = {1}, pages = {772--787}, publisher = {Oxford University Press}, title = {{Spectroscopic properties of luminous Ly α emitters at z ≈ 6–7 and comparison to the Lyman-break population}}, doi = {10.1093/mnras/stx2061}, volume = {472}, year = {2017}, } @unpublished{11633, abstract = {Our understanding of stars through asteroseismic data analysis is limited by our ability to take advantage of the huge amount of observed stars provided by space missions such as CoRoT, Kepler , K2, and soon TESS and PLATO. Global seismic pipelines provide global stellar parameters such as mass and radius using the mean seismic parameters, as well as the effective temperature. These pipelines are commonly used automatically on thousands of stars observed by K2 for 3 months (and soon TESS for at least ∼ 1 month). However, pipelines are not immune from misidentifying noise peaks and stellar oscillations. Therefore, new validation techniques are required to assess the quality of these results. We present a new metric called FliPer (Flicker in Power), which takes into account the average variability at all measured time scales. The proper calibration of FliPer enables us to obtain good estimations of global stellar parameters such as surface gravity that are robust against the influence of noise peaks and hence are an excellent way to find faults in asteroseismic pipelines.}, author = {Bugnet, Lisa Annabelle and Garcia, R. A. and Davies, G. R. and Mathur, S. and Corsaro, E.}, booktitle = {arXiv}, keywords = {asteroseismology - methods, data analysis - stars, oscillations}, title = {{FliPer: Checking the reliability of global seismic parameters from automatic pipelines}}, doi = {10.48550/arXiv.1711.02890}, year = {2017}, } @inproceedings{1176, abstract = {The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the "paranoid" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A.}, author = {Alwen, Joel F and Blocki, Jeremiah}, isbn = {978-150905761-0}, location = {Paris, France}, publisher = {IEEE}, title = {{Towards practical attacks on Argon2i and balloon hashing}}, doi = {10.1109/EuroSP.2017.47}, year = {2017}, } @inproceedings{11772, abstract = {A dynamic graph algorithm is a data structure that supports operations on dynamically changing graphs.}, author = {Henzinger, Monika H}, booktitle = {44th International Conference on Current Trends in Theory and Practice of Computer Science}, isbn = {9783319731162}, issn = {0302-9743}, location = {Krems, Austria}, pages = {40–44}, publisher = {Springer Nature}, title = {{The state of the art in dynamic graph algorithms}}, doi = {10.1007/978-3-319-73117-9_3}, volume = {10706}, year = {2017}, } @inproceedings{1178, abstract = {For any pair (X, Z) of correlated random variables we can think of Z as a randomized function of X. If the domain of Z is small, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as simulating auxiliary inputs. This idea of simulating auxiliary information turns out to be a very usefull tool, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: (a) We present a novel boosting algorithm for constructing the simulator. This boosting proof is of independent interest, as it shows how to handle “negative mass” issues when constructing probability measures by shifting distinguishers in descent algorithms. Our technique essentially fixes the flaw in the TCC’14 paper “How to Fake Auxiliary Inputs”. (b) The complexity of our simulator is better than in previous works, including results derived from the uniform min-max theorem due to Vadhan and Zheng. To achieve (s,ϵ) -indistinguishability we need the complexity O(s⋅25ℓϵ−2) in time/circuit size, which improve previous bounds by a factor of ϵ−2. In particular, with we get meaningful provable security for the EUROCRYPT’09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like }, author = {Skórski, Maciej}, pages = {159 -- 179}, publisher = {Springer}, title = {{Simulating auxiliary inputs, revisited}}, doi = {10.1007/978-3-662-53641-4_7}, volume = {9985}, year = {2017}, } @inproceedings{11829, abstract = {In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity. In this paper we prove conditional lower bounds for these and additional problems in a sensitivity setting. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the (4/3-\varepsilon)-approximate diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible. We further show under the BMM conjecture that many problems, such as reachability or approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We extend our reduction from BMM to Diameter to give a reduction from All Pairs Shortest Paths to Diameter under one deletion in weighted graphs. This is intriguing, as in the static setting it is a big open problem whether Diameter is as hard as APSP. We further get a nearly tight lower bound for shortest paths after two edge deletions based on the APSP conjecture. We give more lower bounds under the Strong Exponential Time Hypothesis. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required. Finally, we give the first algorithm for the (1+\varepsilon)-approximate radius, diameter, and eccentricity problems in directed or undirected unweighted graphs in case of single edges failures. The algorithm has a truly subcubic running time for graphs with a truly subquadratic number of edges; it is tight w.r.t. the conditional lower bounds we obtain.}, author = {Henzinger, Monika H and Lincoln, Andrea and Neumann, Stefan and Vassilevska Williams, Virginia}, booktitle = {8th Innovations in Theoretical Computer Science Conference}, isbn = {9783959770293}, issn = {1868-8969}, location = {Berkley, CA, United States}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Conditional hardness for sensitivity problems}}, doi = {10.4230/LIPICS.ITCS.2017.26}, volume = {67}, year = {2017}, } @inproceedings{11831, abstract = {Graph Sparsification aims at compressing large graphs into smaller ones while (approximately) preserving important characteristics of the input graph. In this work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. Given a weighted graph G=(V,E), and a terminal set K with |K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in V_H that preserves the value of minimum cuts separating any bipartition of K, up to a factor of q. We show that planar graphs with all the k terminals lying on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are also planar. Our result extends to vertex flow and distance sparsifiers. It improves the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by an exponential factor, and matches an Omega(k^2) lower-bound for this class of graphs. We also study vertex reachability sparsifiers for directed graphs. Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability information among terminal pairs. We introduce the notion of reachability-preserving minors, i.e., we require H to be a minor of G. Among others, for general planar digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k). We complement our upper-bound by showing that there exists an infinite family of acyclic planar digraphs such that any reachability-preserving minor must have Omega(k^2) vertices.}, author = {Goranci, Gramoz and Henzinger, Monika H and Peng, Pan}, booktitle = {25th Annual European Symposium on Algorithms}, isbn = {978-3-95977-049-1}, issn = {1868-8969}, location = {Vienna, Austria}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Improved guarantees for vertex sparsification in planar graphs}}, doi = {10.4230/LIPICS.ESA.2017.44}, volume = {87}, year = {2017}, } @inproceedings{11832, abstract = {In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem.}, author = {Henzinger, Monika H and Leniowski, Dariusz and Mathieu, Claire}, booktitle = {25th Annual European Symposium on Algorithms}, isbn = {978-3-95977-049-1}, issn = {1868-8969}, location = {Vienna, Austria}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Dynamic clustering to minimize the sum of radii}}, doi = {10.4230/LIPICS.ESA.2017.48}, volume = {87}, year = {2017}, } @inproceedings{11833, abstract = {We introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsification, which is a way to compress large graphs into small ones that well preserve relevant properties among a subset of vertices and has previously mainly been used in the design of approximation algorithms. Using this framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 + epsilon)-approximating the energy of electrical flows in n-vertex planar graphs with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r}) epsilon^{-2}) worst-case query time, for any r larger than some constant. For r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3} epsilon^{-2}) query time. We also extend this algorithm to work for minor-free graphs with similar approximation and running time guarantees. Furthermore, we illustrate our framework on the all-pairs max flow and shortest path problems by giving corresponding dynamic algorithms in minor-free graphs with both sublinear update and query times. To the best of our knowledge, our results are the first to systematically establish such a connection between dynamic graph algorithms and vertex sparsification. We also present both upper bound and lower bound for maintaining the energy of electrical flows in the incremental subgraph model, where updates consist of only vertex activations, which might be of independent interest.}, author = {Goranci, Gramoz and Henzinger, Monika H and Peng, Pan}, booktitle = {25th Annual European Symposium on Algorithms}, isbn = {978-3-95977-049-1}, issn = {1868-8969}, location = {Vienna, Austria}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The power of vertex sparsifiers in dynamic graph algorithms}}, doi = {10.4230/LIPICS.ESA.2017.45}, volume = {87}, year = {2017}, } @article{1187, abstract = {We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol.}, author = {Kiltz, Eike and Pietrzak, Krzysztof Z and Venturi, Daniele and Cash, David and Jain, Abhishek}, journal = {Journal of Cryptology}, number = {4}, pages = {1238 -- 1275}, publisher = {Springer}, title = {{Efficient authentication from hard learning problems}}, doi = {10.1007/s00145-016-9247-3}, volume = {30}, year = {2017}, } @inproceedings{11874, abstract = {We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + ∊) and worst case update time O(m1/4/ ∊2), where m is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio (1+ ∊) and worst case update time No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised update time O(log2 n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O(1). We bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + ∊) and worst case update time O(log3 n), for all sufficiently small constants ∊.}, author = {Bhattacharya, Sayan and Henzinger, Monika H and Nanongkai, Danupon}, booktitle = {28th Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Barcelona, Spain}, pages = {470 -- 489}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time}}, doi = {10.1137/1.9781611974782.30}, year = {2017}, }