Search

Malicious actors exploit the DNS namespace to launch spam campaigns, phishing attacks, malware, and other harmful activities. Combating these threats requires visibility into domain existence, ownership and nameservice activity that the DNS protocol does not itself provide. To facilitate visibility and security-related study of the expanding gTLD namespace, ICANN introduced the Centralized Zone Data Service (CZDS) that shares daily zone file snapshots of new gTLD zones. However, a remarkably high concentration of malicious activity is associated with domains that do not live long enough make it into these daily snapshots. Using public and private sources of newly observed domains, we discover that even with the best available data there is a considerable visibility gap in detecting short-lived domains. We find that the daily snapshots miss at least 1% of newly registered and short-lived domains, which are frequently registered with likely malicious intent. In reducing this critical visibility gap using public sources of data, we demonstrate how more timely access to TLD zone changes can provide valuable data to better prevent abuse. We hope that this work sparks a discussion in the community on how to effectively and safely revive the concept of sharing Rapid Zone Updates for security research. Finally, we release a public live feed of newly registered domains, with the aim of enabling further research in abuse identification., Comment: Accepted at IMC2024, Madrid

As a response to the Russian aggression against Ukraine, the European Union (EU), through the notion of "digital sovereignty", imposed sanctions on organizations and individuals affiliated with the Russian Federation that prohibit broadcasting content, including online distribution. In this paper, we interrogate the implementation of these sanctions and interpret them as a means to translate the union of states' governmental edicts into effective technical countermeasures. Through longitudinal traffic analysis, we construct an understanding of how ISPs in different EU countries attempted to enforce these sanctions, and compare these implementations to similar measures in other western countries. We find a wide variation of blocking coverage, both internationally and within individual member states. We draw the conclusion that digital sovereignty through sanctions in the EU has a concrete but distinctly limited impact on information flows., Comment: Accepted to Free and Open Communications on the Internet (FOCI) 2024

New technologies have the power to revolutionize science. It has happened in the past and is happening again with the emergence of new computational tools, such as artificial intelligence and machine learning. Despite the documented impact of these technologies, there remains a significant gap in understanding the process of their adoption within the scientific community. In this paper, we draw on theories of scientific and technical human capital to study the integration of AI in scientific research, focusing on the human capital of scientists and the external resources available within their network of collaborators and institutions. We validate our hypotheses on a large sample of publications from OpenAlex, covering all sciences from 1980 to 2020, and identify a set key drivers and inhibitors of AI adoption and use in science. Our results suggest that AI is pioneered by domain scientists with a `taste for exploration' and who are embedded in a network rich of computer scientists, experienced AI scientists and early-career researchers; they come from institutions with high citation impact and a relatively strong publication history on AI. The access to computing resources only matters for a few scientific disciplines, such as chemistry and medical sciences. Once AI is integrated into research, most adoption factors continue to influence its subsequent reuse. Implications for the organization and management of science in the evolving era of AI-driven discovery are discussed.

We discuss model-checking problems as formal models of algorithmic law. Specifically, we ask for an algorithmically tractable general purpose model-checking problem that naturally models the European transport Regulation 561, and discuss the reaches and limits of a version of discrete time stopwatch automata.

We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory V$^0_2$ is consistent with the conjecture that NEXP $\not\subseteq$ P/poly, i.e., some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. The same techniques establish the same results with NEXP replaced by the class of problems that are decidable in non-deterministic barely superpolynomial time such as NTIME$(n^{O(\log\log\log n)})$. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds., Comment: An extended abstract of part of this work appeared in the Proceedings of the 55th ACM Symposium on Theory of Computation (STOC 2023). This is a small revision of the earlier long version that includes some minor corrections, a revised introduction, and some additional observations

We study the parameterized complexity of the problem to decide whether a given natural number $n$ satisfies a given $\Delta_0$-formula $\varphi(x)$; the parameter is the size of $\varphi$. This parameterization focusses attention on instances where $n$ is large compared to the size of $\varphi$. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf{AC}^0$. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $I\Delta_0$ proves the MRDP theorem in a certain weak sense., Comment: 25 pages

We investigate ferroelectric- and resistive switching behavior in 18-nm-thick epitaxial BaTiO$_3$ (BTO) films in a model electrolyte-ferroelectric-semiconductor (EFS) configuration. The system is explored for its potential as a ferroelectric microelectrode in bioelectronics. The BTO films are grown by pulsed laser deposition (PLD) on semiconducting Nb-doped (0.5 wt\%) SrTiO$_{3}$ (Nb:STO) single crystal substrates. The ferroelectric properties of the bare BTO films are demonstrated by piezoresponse force microscopy (PFM) measurements. Cyclic voltammetry (CV) measurements in EFS configuration, with phosphate buffered saline (PBS) acting as the liquid electrolyte top contact, indicate characteristic ferroelectric switching peaks in the bipolar current-voltage loop. The ferroelectric nature of the observed switching peaks is confirmed by analyzing the current response of the EFS devices to unipolar voltage signals. Moreover, electrochemical impedance spectroscopy (EIS) measurements indicate bipolar resisitive switching behavior of the EFS devices, which is controlled by the remanent polarization state of the BTO layer. Our results represent a constitutive step towards the realization of neuroprosthetic implants and hybrid neurocomputational systems based on ferroelectric microelectrodes.

How has the science system reacted to the early stages of the COVID-19 pandemic? Here we compare the (growing) international network for coronavirus research with the broader international health science network. Our findings show that, before the outbreak, coronavirus research realized a relatively small and rather peculiar niche within the global health sciences. As a response to the pandemic, the international network for coronavirus research expanded rapidly along the hierarchical structure laid out by the global health science network. Thus, in face of the crisis, the global health science system proved to be structurally stable yet versatile in research. The observed versatility supports optimistic views on the role of science in meeting future challenges. However, the stability of the global core-periphery structure may be worrying, because it reduces learning opportunities and social capital of scientifically peripheral countries -- not only during this pandemic but also in its "normal" mode of operation.

We define typical forcings encompassing many informal forcing arguments in bounded arithmetic and give general conditions for such forcings to produce models of the universal variant of relativized $T^1_2$. We apply this result to study the relative complexity of total (type 2) NP search problems associated to finitary combinatorial principles. Complexity theory compares such problems with respect to polynomial time many-one or Turing reductions. From a logical perspective such problems are graded according to the bounded arithmetic theories that prove their totality. The logical analogue of a reduction is to prove the totality of one problem from the totality of another. The link between the two perspectives is tight for what we call universal variants of relativized bounded arithmetics. We strengthen a theorem of Buss and Johnson (2012) that infers relative bounded depth Frege proofs of totality from polynomial time Turing reducibility. As an application of our general forcing method we derive a strong form of Riis' finitization theorem (1993). We extend it by exhibiting a simple model-theoretic property that implies independence from the universal variant of relativized $T^1_2$ plus the weak pigeonhole principle. More generally, we show that the universal variant of relativized $T^1_2$ does not prove (the totality of the total NP search problem associated to) a strong finitary combinatorial principle from a weak one. Being weak or strong are simple model-theoretic properties based on the behaviour of the principles with respect to finite structures that are only partially defined.

Much of the recent success of Artificial Intelligence (AI) has been spurred on by impressive achievements within a broader family of machine learning methods, commonly referred to as Deep Learning (DL). This paper provides insights on the diffusion and impact of DL in science. Through a Natural Language Processing (NLP) approach on the arXiv.org publication corpus, we delineate the emerging DL technology and identify a list of relevant search terms. These search terms allow us to retrieve DL-related publications from Web of Science across all sciences. Based on that sample, we document the DL diffusion process in the scientific system. We find i) an exponential growth in the adoption of DL as a research tool across all sciences and all over the world, ii) regional differentiation in DL application domains, and iii) a transition from interdisciplinary DL applications to disciplinary research within application domains. In a second step, we investigate how the adoption of DL methods affects scientific development. Therefore, we empirically assess how DL adoption relates to re-combinatorial novelty and scientific impact in the health sciences. We find that DL adoption is negatively correlated with re-combinatorial novelty, but positively correlated with expectation as well as variance of citation performance. Our findings suggest that DL does not (yet?) work as an autopilot to navigate complex knowledge landscapes and overthrow their structure. However, the 'DL principle' qualifies for its versatility as the nucleus of a general scientific method that advances science in a measurable way.

Recent core-hole-clock experiments [Phys. Rev. Lett. $\textbf{112}$, 086801 (2014)] showed that the spin dependence of electron injection times at Ar/Co(0001) and Ar/Fe(110) interfaces is at variance with the expectations based on previous calculations for related systems. Here we reconcile theory and experiment, and demonstrate that the observed dependence is rooted in the details of the spin-split surface band structures. Our ab initio calculations back that minority electrons are injected significantly faster than majority electrons in line with the experimentally reported ultrashort injection times. The dynamics is particularly sensitive to the size (in reciprocal-space) of the projected band gaps around $\overline{\Gamma}$ for both substrates at the resonance energies. A simple tunneling model incorporating the spin-dependent gap sizes further supports these findings., Comment: 5+6 pages, 4+4 figures

We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is not automatizable unless P = NP. Indeed, we show it is NP-hard to distinguish between formulas that have Resolution refutations of polynomial length and those that do not have subexponential length refutations. This also implies that Resolution is not automatizable in subexponential time or quasi-polynomial time unless NP is included in SUBEXP or QP, respectively.

X-ray absorption spectroscopy yields direct access to the electronic and geometric structure of hybrid inorganic-organic interfaces formed upon adsorption of complex molecules at metal surfaces. The unambiguous interpretation of corresponding spectra is challenged by the intrinsic geometric flexibility of the adsorbates and the chemical interactions with the interface. Density-functional theory (DFT) calculations of the extended adsorbate-substrate system are an established tool to guide peak assignment in X-ray photoelectron spectroscopy (XPS) of complex interfaces. We extend this to the simulation and interpretation of X-ray absorption spectroscopy (XAS) data in the context of functional organic molecules on metal surfaces using dispersion-corrected DFT calculations within the transition potential approach. On the example of X-ray absorption signatures for the prototypical case of 2H-porphine adsorbed on Ag(111) and Cu(111) substrates, we follow the two main effects of the molecule/surface interaction on XAS: (1) the substrate-induced chemical shift of the 1s core levels that dominates in physisorbed systems and (2) the hybridization-induced broadening and loss of distinct resonances that dominates in more chemisorbed systems., Comment: 13 pages, 4 figures

The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational structure (database); the parameter is the length of the sentence. We study the parameterized space complexity of the model-checking problem for queries with a bounded number of variables. For each bound on the quantifier alternation rank the problem becomes complete for the corresponding level of what we call the tree hierarchy, a hierarchy of parameterized complexity classes defined via space bounded alternating machines between parameterized logarithmic space and fixed-parameter tractable time. We observe that a parameterized logarithmic space model-checker for existential bounded variable queries would allow to improve Savitch's classical simulation of nondeterministic logarithmic space in deterministic space $O(\log^2n)$. Further, we define a highly space efficient model-checker for queries with a bounded number of variables and bounded quantifier alternation rank. We study its optimality under the assumption that Savitch's Theorem is optimal.

The embedding problem is to decide, given an ordered pair of structures, whether or not there is an injective homomorphism from the first structure to the second. We study this problem using an established perspective in parameterized complexity theory: the universe size of the first structure is taken to be the parameter, and we define the embedding problem relative to a class ${\cl A}$ of structures to be the restricted version of the general problem where the first structure must come from ${\cl A}$. We initiate a systematic complexity study of this problem family, by considering classes whose structures are what we call rooted path structures; these structures have paths as Gaifman graphs. Our main theorem is a dichotomy theorem on classes of rooted path structures., Comment: Final publication in Theory of Computing Systems. The final publication is available at Springer via http://dx.doi.org/10.1007/s00224-016-9728-7

We employ dispersion-corrected density-functional theory to study the adsorption of tetrapyrrole 2H-porphine (2H-P) at Cu(111) and Ag(111). Various contributions to adsorbate-substrate and adsorbate-adsorbate interactions are systematically extracted to analyze the self-assembly behavior of this basic building block to porphyrin-based metal-organic nanostructures. This analysis reveals a surprising importance of substrate-mediated van der Waals interactions between 2H-P molecules, in contrast to negligible direct dispersive interactions. The resulting net repulsive interactions rationalize the experimentally observed tendency for single molecule adsorption., Comment: 16 pages, 8 figures, 3 tables