Arrow Research search

Author name cluster

Girish Varma

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

AAAI Conference 2023 Conference Paper

City-Scale Pollution Aware Traffic Routing by Sampling Max Flows Using MCMC

  • Shreevignesh Suriyanarayanan
  • Praveen Paruchuri
  • Girish Varma

A significant cause of air pollution in urban areas worldwide is the high volume of road traffic. Long-term exposure to severe pollution can cause serious health issues. One approach towards tackling this problem is to design a pollution-aware traffic routing policy that balances multiple objectives of i) avoiding extreme pollution in any area ii) enabling short transit times, and iii) making effective use of the road capacities. We propose a novel sampling-based approach for this problem. We give the first construction of a Markov Chain that can sample integer max flow solutions of a planar graph, with theoretical guarantees that the probabilities depend on the aggregate transit length. We designed a traffic policy using diverse samples and simulated traffic on real-world road maps using the SUMO traffic simulator. We observe a considerable decrease in areas with severe pollution when experimented with maps of large cities across the world compared to other approaches.

PDF Details DOI

UAI Conference 2021 Conference Paper

Generalized parametric path problems

  • Kshitij Gajjar
  • Girish Varma
  • Prerona Chatterjee
  • Jaikumar Radhakrishnan

Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation is applicable in these domains. We study the complexity of the general problem, and a variant of it where preprocessing is allowed. We show that when the parametric weights are linear functions, algorithms remain tractable even under our relaxed assumptions. Furthermore, we show that if the weights are allowed to be non-linear, the problem becomes NP-hard. We also study the multi-dimensional version of the problem where the weight functions are parameterized by multiple parameters. We show that even with two parameters, this problem is NP-hard.

Details

IROS Conference 2018 Conference Paper

City-Scale Road Audit System using Deep Learning

  • Sudhir Yarram
  • Girish Varma
  • C. V. Jawahar

Road networks in cities are massive and is a critical component of mobility. Fast response to defects, that can occur not only due to regular wear and tear but also because of extreme events like storms, is essential. Hence there is a need for an automated system that is quick, scalable and cost-effective for gathering information about defects. We propose a system for city-scale road audit, using some of the most recent developments in deep learning and semantic segmentation. For building and benchmarking the system, we curated a dataset which has annotations required for road defects. However, many of the labels required for road audit have high ambiguity which we overcome by proposing a label hierarchy. We also propose a multi-step deep learning model that segments the road, subdivide the road further into defects, tags the frame for each defect and finally localizes the defects on a map gathered using GPS. We analyze and evaluate the models on image tagging as well as segmentation at different levels of the label hierarchy.

Details

TCS Journal 2013 Journal Article

Streaming algorithms for language recognition problems

  • Ajesh Babu
  • Nutan Limaye
  • Jaikumar Radhakrishnan
  • Girish Varma

We study the complexity of the following problems in the streaming model. Membership testing for DLIN. We show that every language in DLIN can be recognized by a randomized one-pass O ( log n ) space algorithm with an inverse polynomial one-sided error and by a deterministic p -pass O ( n / p ) space algorithm. We show that these algorithms are optimal. Membership testing for LL ( k ). For languages generated by LL ( k ) grammars with a bound of r on the number of nonterminals at any stage in the left-most derivation, we show that membership can be tested by a randomized one-pass O ( r log n ) space algorithm with an inverse polynomial (in n ) one-sided error. Membership testing for DCFL. We show that randomized algorithms as efficient as the ones described above for DLIN and LL ( k ) (which are subclasses of DCFL) cannot exist for all of DCFL: there is a language in VPL (a subclass of DCFL) for which any randomized p -pass algorithm with an error bounded by ϵ < 1 / 2 must use Ω ( n / p ) space. Degree sequence problem. We study the problem of determining, given a sequence d 1, d 2, …, d n and a graph G, whether the degree sequence of G is precisely d 1, d 2, …, d n. We give a randomized one-pass O ( log n ) space algorithm with an inverse polynomial one-sided error probability. We show that our algorithms are optimal. Our randomized algorithms are based on the recent work of Magniez et al. [1]; our lower bounds are obtained by considering related communication complexity problems.

Details DOI