Applications of random graphs and walks

随机图和游走的应用

基本信息

  • 批准号:
    RGPIN-2020-04398
  • 负责人:
  • 金额:
    $ 5.39万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2022
  • 资助国家:
    加拿大
  • 起止时间:
    2022-01-01 至 2023-12-31
  • 项目状态:
    已结题

项目摘要

My research is interdisciplinary. Central threads of my work focus on questions from combinatorics and CS theory, algorithmic complexity and concrete applications. Probability theory plays a role in the vast majority of my work, and I often focus on randomization, its effects on a problem, and benefits in algorithms. Random graphs (networks) and random walks feature often in my work. Random networks are ubiquitous and a classical research topic in probability theory and combinatorics. Their importance stems from being a model of many natural phenomena, from social networks and interaction within communities, through computer networks, to models for genealogy of populations, and interactions of proteins in complex biological systems. Thus network analysis has a multitude of applications in many areas. Random walks are similarly common, as a model for naturally occurring processes and as a tool. A second theme of my research involves problems of optimization in random settings. While some algorithms may behave badly in the worst case, they may do better in typical settings. Recently we gave the first polynomial bound on the runtime of the FLIP algorithm for finding the a local maximum for MAX-CUT on a graph with random edge weights. Numerous fundamental questions remain open: What is the optimal polynomial degree? Current bounds are between 1 and 9.3. What if we allow flipping not one vertex at a time, but two? Only quasi-polynomial bounds are known here. What about MAX-k-CUT? There are numerous other combinatorial optimization problems, where the complexity is unknown, which I plan to study. I also work on problems from computational biology. We developed an algorithm based on random walks for extracting biologically meaningful insights from modern single cell RNA counts. Data is fitted onto a low dimension manifold; Proximity of the samples is used to generate a graph on the sample points, and its structure is analyzed. Many probabilistic and algorithmic projects arise: Devise ways to generate graphs that are more robust to the various sources of noise in the data, develop new algorithms to locate patterns in the graph, simplify these so that analysis of larger data sets becomes feasible etc. These feed back into experimental design. Another topic is variants on the bandit problem. An agent selects at each time one of several actions and receives a payoff. The goal is for the agent to identify from observed payoffs the optimal action. This problem has extensive literature and applications, yet many natural variations are not well understood. Suppose there are several agents who make decisions independently, with a penalty if they select the same action. There are variations depending on whether agents see collisions as they occur, and whether they are allowed to communicate. In the least informative model, the expected optimal regret is known to grow polynomially even for i.i.d. payoff vectors, but the optimal exponent is not known.
我的研究是跨学科的。我的工作的中心线索集中在问题从组合学和CS理论,算法复杂性和具体应用。概率论在我的大部分工作中都扮演着重要的角色,我经常关注随机化,它对问题的影响,以及算法的好处。随机图(网络)和随机漫步在我的工作中经常出现。随机网络是概率论和组合学中普遍存在的一个经典研究课题。它们的重要性源于它们是许多自然现象的模型,从社会网络和社区内的相互作用,通过计算机网络,到群体谱系的模型,以及复杂生物系统中蛋白质的相互作用。因此,网络分析在许多领域都有广泛的应用。作为自然发生过程的模型和工具,随机漫步也同样常见。我研究的第二个主题涉及随机设置中的优化问题。虽然有些算法在最坏的情况下可能表现不佳,但它们在典型设置下可能会做得更好。最近,我们给出了在随机边权图上寻找MAX-CUT的局部最大值的FLIP算法运行时的第一个多项式界。许多基本问题仍未解决:最优多项式次是多少?当前边界在1到9.3之间。如果我们允许一次翻转两个顶点,而不是一个呢?这里只有准多项式界是已知的。MAX-k-CUT怎么样?还有许多其他的组合优化问题,其复杂性是未知的,这是我打算研究的。我也研究计算生物学的问题。我们开发了一种基于随机漫步的算法,用于从现代单细胞RNA计数中提取生物学上有意义的见解。数据被拟合到一个低维歧管;利用样本的接近度在样本点上生成图,并对其结构进行分析。许多概率和算法项目出现了:设计方法来生成对数据中各种噪声源更健壮的图形,开发新的算法来定位图形中的模式,简化这些,以便对更大的数据集进行分析变得可行等等。这些反馈到实验设计中。另一个话题是土匪问题的变体。agent每次从几个动作中选择一个并获得收益。目标是让智能体从观察到的收益中识别出最优行为。这个问题有广泛的文献和应用,但许多自然变异还没有很好地理解。假设有几个独立决策的代理,如果他们选择了相同的行为,就会受到惩罚。这些变化取决于代理是否在碰撞发生时看到碰撞,以及它们是否被允许进行通信。在最小信息模型中,已知期望最优后悔即使对i. id .支付向量也是多项式增长的,但不知道最优后悔的指数。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Angel, Omer其他文献

Percolations on random maps I: Half-plane models
SHARP THRESHOLDS FOR CONTAGIOUS SETS IN RANDOM GRAPHS
  • DOI:
    10.1214/17-aap1325
  • 发表时间:
    2018-04-01
  • 期刊:
  • 影响因子:
    1.8
  • 作者:
    Angel, Omer;Kolesnik, Brett
  • 通讯作者:
    Kolesnik, Brett
Global divergence of spatial coalescents
  • DOI:
    10.1007/s00440-010-0332-5
  • 发表时间:
    2012-04-01
  • 期刊:
  • 影响因子:
    2
  • 作者:
    Angel, Omer;Berestycki, Nathanael;Limic, Vlada
  • 通讯作者:
    Limic, Vlada
Hyperbolic and Parabolic Unimodular Random Maps
  • DOI:
    10.1007/s00039-018-0446-y
  • 发表时间:
    2018-07-01
  • 期刊:
  • 影响因子:
    2.2
  • 作者:
    Angel, Omer;Hutchcroft, Tom;Ray, Gourab
  • 通讯作者:
    Ray, Gourab

Angel, Omer的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Angel, Omer', 18)}}的其他基金

Applications of random graphs and walks
随机图和游走的应用
  • 批准号:
    RGPIN-2020-04398
  • 财政年份:
    2021
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Applications of random graphs and walks
随机图和游走的应用
  • 批准号:
    RGPIN-2020-04398
  • 财政年份:
    2020
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Stochastic processes and geometry of random networks
随机过程和随机网络的几何
  • 批准号:
    RGPIN-2015-04570
  • 财政年份:
    2019
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Stochastic processes and geometry of random networks
随机过程和随机网络的几何
  • 批准号:
    RGPIN-2015-04570
  • 财政年份:
    2018
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Stochastic processes and geometry of random networks
随机过程和随机网络的几何
  • 批准号:
    RGPIN-2015-04570
  • 财政年份:
    2017
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Stochastic processes and geometry of random networks
随机过程和随机网络的几何
  • 批准号:
    RGPIN-2015-04570
  • 财政年份:
    2016
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Stochastic processes and geometry of random networks
随机过程和随机网络的几何
  • 批准号:
    RGPIN-2015-04570
  • 财政年份:
    2015
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Random spatial processes
随机空间过程
  • 批准号:
    341779-2010
  • 财政年份:
    2014
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Random spatial processes
随机空间过程
  • 批准号:
    341779-2010
  • 财政年份:
    2013
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Random spatial processes
随机空间过程
  • 批准号:
    341779-2010
  • 财政年份:
    2012
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual

相似国自然基金

大Peclect数多粒径分布球形多孔介质内流动、传质和反应特性的研究
  • 批准号:
    21276256
  • 批准年份:
    2012
  • 资助金额:
    80.0 万元
  • 项目类别:
    面上项目
基于Riemann-Hilbert方法的相关问题研究
  • 批准号:
    11026205
  • 批准年份:
    2010
  • 资助金额:
    3.0 万元
  • 项目类别:
    数学天元基金项目
不经意传输协议中的若干问题研究
  • 批准号:
    60873041
  • 批准年份:
    2008
  • 资助金额:
    30.0 万元
  • 项目类别:
    面上项目
面向Web信息检索的随机P2P拓扑模型及语义网重构技术研究
  • 批准号:
    60573142
  • 批准年份:
    2005
  • 资助金额:
    20.0 万元
  • 项目类别:
    面上项目
利用逆转录病毒siRNA随机文库在Hela细胞中批量获得TRAIL凋亡通路相关功能基因的研究
  • 批准号:
    30400080
  • 批准年份:
    2004
  • 资助金额:
    8.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Large Graph Limits of Stochastic Processes on Random Graphs
随机图上随机过程的大图极限
  • 批准号:
    EP/Y027795/1
  • 财政年份:
    2024
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Research Grant
Random Matrices and Functional Inequalities on Spaces of Graphs
图空间上的随机矩阵和函数不等式
  • 批准号:
    2331037
  • 财政年份:
    2023
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Continuing Grant
Random Matrices, Random Graphs, and Deep Neural Networks
随机矩阵、随机图和深度神经网络
  • 批准号:
    2331096
  • 财政年份:
    2023
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Standard Grant
Stochastic processes on random graphs with clustering
具有聚类的随机图上的随机过程
  • 批准号:
    EP/W033585/1
  • 财政年份:
    2023
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Research Grant
Random functions and stochastic processes on random graphs
随机图上的随机函数和随机过程
  • 批准号:
    2246575
  • 财政年份:
    2023
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Standard Grant
Successive Shortest Structures in Random Graphs
随机图中的连续最短结构
  • 批准号:
    EP/W015404/1
  • 财政年份:
    2022
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Research Grant
CAREER: Understanding the Evolution of Random Graphs with Complex Dependencies: Phase Transition and Beyond
职业:理解具有复杂依赖性的随机图的演化:相变及其他
  • 批准号:
    2225631
  • 财政年份:
    2022
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Continuing Grant
Random graphs and percolation processes
随机图和渗透过程
  • 批准号:
    RGPIN-2016-05949
  • 财政年份:
    2022
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
Spanning Structures in Random Graphs
随机图中的跨越结构
  • 批准号:
    2201590
  • 财政年份:
    2022
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Standard Grant
Problems in Randomized Algorithms, Random Graphs, and Computational Geometry
随机算法、随机图和计算几何中的问题
  • 批准号:
    RGPIN-2019-04269
  • 财政年份:
    2022
  • 资助金额:
    $ 5.39万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了