This content will become publicly available on June 12, 2024
 Award ID(s):
 1839116
 NSFPAR ID:
 10482062
 Publisher / Repository:
 COLT 2013
 Date Published:
 Journal Name:
 COLT 2013
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $E(S)/S$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are wellstudied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a nonnegative supermodular function $f: 2^V \rightarrow \mathbb{R}_+$, maximize $f(S)/S$. For \dsg we describe a simple flowbased algorithm that outputs a $(1\eps)$approximation in deterministic $\tilde{O}(m/\eps)$ time where $m$ is the number of edges. Our algorithm is the first to have a nearlinear dependence on $m$ and $1/\eps$ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed \dsg. Greedy peeling algorithms have been very popular for \dsg and several variants due to their efficiency, empirical performance, and worstcase approximation guarantees. We describe a simple peeling algorithm for \dssp and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al.\ \cite{bgpstww20} developed an \emph{iterative} peeling algorithm for \dsg which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a $(1\eps)$approximation for \emph{any} supermodular function $f$; the key to our proof is to consider an LP formulation that is derived via the \Lovasz extension of a supermodular function. For \dsg the bound on the number of iterations we prove is $O(\frac{\Delta \ln V}{\lambda^*}\cdot \frac{1}{\eps^2})$ where $\Delta$ is the maximum degree and $\lambda^*$ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature. Finally, we show that the $2$approximation for densestatleast$k$ subgraph \cite{ks09} extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of \dssp to maximize $f(S)/g(S)$ for a concave function $g$.more » « less

Abstract The 4 N {4N} carpets are a class of infinitely ramified selfsimilar fractals with a large group of symmetries. For a 4 N {4N} carpet F , let { F n } n ≥ 0 {\{F_{n}\}_{n\geq 0}} be the natural decreasing sequence of compact prefractal approximations with ⋂ n F n = F {\bigcap_{n}F_{n}=F} . On each F n {F_{n}} , let ℰ ( u , v ) = ∫ F N ∇ u ⋅ ∇ v d x {\mathcal{E}(u,v)=\int_{F_{N}}\nabla u\cdot\nabla v\,dx} be the classical Dirichlet form and u n {u_{n}} be the unique harmonic function on F n {F_{n}} satisfying a mixed boundary value problem corresponding to assigning a constant potential between two specific subsets of the boundary. Using a method introduced by [M. T. Barlow and R. F. Bass,On the resistance of the Sierpiński carpet, Proc. Roy. Soc. Lond. Ser. A 431 (1990), no. 1882, 345–360], we prove a resistance estimate of the following form: there is ρ = ρ ( N ) > 1 {\rho=\rho(N)>1} such that ℰ ( u n , u n ) ρ n {\mathcal{E}(u_{n},u_{n})\rho^{n}} is bounded above and below by constants independent of n . Such estimates have implications for the existence and scaling properties of Brownian motion on F .more » « less

Neurotransmitters are small molecules involved in neuronal signaling and can also serve as stress biomarkers.^{1}Their abnormal levels have been also proposed to be indicative of several neurological diseases such as Alzheimer’s disease, Parkinson’s disease, Huntington disease, among others. Hence, measuring their levels is highly important for early diagnosis, therapy, and disease prognosis. In this work, we investigate facile functionalization methods to tune and enhance sensitivity of printed graphene sensors to neurotransmitters. Sensors based on direct laser scribing and screenprinted graphene ink are studied. These printing methods offer ease of prototyping and scalable fabrication at low cost.
The effect of functionalization of laser induced graphene (LIG) by electrodeposition and solutionbased deposition of TMDs (molybdenum disulfide^{2}and tungsten disulfide) and metal nanoparticles is studied. For different processing methods, electrochemical characteristics (such as electrochemically active surface area: ECSA and heterogenous electron transfer rate: k^{0}) are extracted and correlated to surface chemistry and defect density obtained respectively using Xray photoelectron spectroscopy (XPS) and Raman spectroscopy. These functionalization methods are observed to directly impact the sensitivity and limit of detection (LOD) of the graphene sensors for the studied neurotransmitters. For example, as compared to bare LIG, it is observed that electrodeposition of MoS_{2}on LIG improves ECSA by 3 times and k^{0}by 1.5 times.^{3}Electrodeposition of MoS_{2}also significantly reduces LOD of serotonin and dopamine in saliva, enabling detection of their physiologically relevant concentrations (in pMnM range). In addition, chemical treatment of LIG sensors is carried out in the form of acetic acid treatment. Acetic acid treatment has been shown previously to improve CC bonds improving the conductivity of LIG sensors.^{4}In our work, in particular, acetic acid treatment leads to larger improvement of LOD of norepinephrine compared to MoS_{2}electrodeposition.
In addition, we investigate the effect of plasma treatment to tune the sensor response by modifying the defect density and chemistry. For example, we find that oxygen plasma treatment of screenprinted graphene ink greatly improves LOD of norepinephrine up to three orders of magnitude, which may be attributed to the increased defects and oxygen functional groups on the surface as evident by XPS measurements. Defects are known to play a key role in enhancing the sensitivity of 2D materials to surface interactions, and have been explored in tuning/enhancing the sensor sensitivity.^{5}Building on our previous work,^{3}we apply a custom machine learningbased data processing method to further improve that sensitivity and LOD, and also to automatically benchmark different moleculematerial pairs.
Future work includes expanding the plasma chemistry and conditions, studying the effect of precursor mixture in laserinduced solutionbased functionalization, and understanding the interplay between moleculematerial system. Work is also underway to improve the machine learning model by using nonlinear learning models such as neural networks to improve the sensor sensitivity, selectivity, and robustness.
References A. J. Steckl, P. Ray, (2018), doi:10.1021/acssensors.8b00726.
Y. Lei, D. Butler, M. C. Lucking, F. Zhang, T. Xia, K. Fujisawa, T. GranzierNakajima, R. CruzSilva, M. Endo, H. Terrones, M. Terrones, A. Ebrahimi,
Sci. Adv. 6 , 4250–4257 (2020).V. Kammarchedu, D. Butler, A. Ebrahimi,
Anal. Chim. Acta .1232 , 340447 (2022).H. Yoon, J. Nah, H. Kim, S. Ko, M. Sharifuzzaman, S. C. Barman, X. Xuan, J. Kim, J. Y. Park,
Sensors Actuators B Chem. 311 , 127866 (2020).T. Wu, A. Alharbi, R. Kiani, D. Shahrjerdi,
Adv. Mater. 31 , 1–12 (2019). 
null (Ed.)We study the application of iterative firstorder methods to the problem of computing equilibria of largescale twoplayer extensiveform games. Firstorder methods must typically be instantiated with a regularizer that serves as a distancegenerating function for the decision sets of the players. For the case of twoplayer zerosum games, the stateoftheart theoretical convergence rate for Nash equilibrium is achieved by using the dilated entropy function. In this paper, we introduce a new entropybased distancegenerating function for twoplayer zerosum games, and show that this function achieves significantly better strong convexity properties than the dilated entropy, while maintaining the same easilyimplemented closedform proximal mapping. Extensive numerical simulations show that these superior theoretical properties translate into better numerical performance as well. We then generalize our new entropy distance function, as well as general dilated distance functions, to the scaled extension operator. The scaled extension operator is a way to recursively construct convex sets, which generalizes the decision polytope of extensiveform games, as well as the convex polytopes corresponding to correlated and team equilibria. By instantiating firstorder methods with our regularizers, we develop the first accelerated firstorder methods for computing correlated equilibra and exante coordinated team equilibria. Our methods have a guaranteed 1/T rate of convergence, along with lineartime proximal updates.more » « less

Abstract We present observations of ≳10–100 keV nucleon −1 suprathermal (ST) H, He, O, and Fe ions associated with crossings of the heliospheric current sheet (HCS) at radial distances of <0.1 au from the Sun. Our key findings are as follows: (1) very few heavy ions are detected during the first full crossing, the heavyion intensities are reduced during the second partial crossing and peak just after the second crossing; (2) ion arrival times exhibit no velocity dispersion; (3) He pitchangle distributions track the magnetic field polarity reversal and show up to ∼10:1 antisunward, fieldaligned flows and beams closer to the HCS that become nearly isotropic farther from the HCS; (4) the He spectrum steepens either side of the HCS, and the He, O, and Fe spectra exhibit power laws of the form ∼ E −4 – E 6 ; and (5) maximum energies E X increase with the ion’s chargetomass ( Q / M ) ratio as E X / E H ∝ ( Q X / M X ) δ , where δ ∼ 0.65–0.76, assuming that the average Q states are similar to those measured in gradual and impulsive solar energetic particle events at 1 au. The absence of velocity dispersion in combination with strong fieldaligned anisotropies closer to the HCS appears to rule out solar flares and nearSun coronalmassejectiondriven shocks. These new observations present challenges not only for mechanisms that employ direct parallel electric fields and organize maximum energies according to E / Q but also for local diffusive and magneticreconnectiondriven acceleration models. Reevaluation of our current understanding of the production and transport of energetic ions is necessary to understand this nearsolar, currentsheetassociated population of ST ions.more » « less