Publications (76)
Few-shot Scooping Under Domain Shift via Simulated Maximal Deployment Gaps
Yifan Zhu, Pranay Thangeda, Erica L Tevere +5
Autonomous lander missions on extraterrestrial bodies need to sample granular materials while coping with domain shifts, even when sampling strategies are extensively tuned on Eart…
Low Sample Complexity Participatory Budgeting
Mohak Goyal, Sukolsak Sakshuwong, Sahasrajit Sarmasarkar +1
We study low sample complexity mechanisms in participatory budgeting (PB), where each voter votes for a preferred allocation of funds to various projects, subject to project costs…
Multi-Selection for Recommendation Systems
Sahasrajit Sarmasarkar, Zhihao Jiang, Ashish Goel +2
We present the construction of a multi-selection model to answer differentially private queries in the context of recommendation systems. The server sends back multiple recommendat…
Sequential Deliberation for Social Choice
Brandon Fain, Ashish Goel, Kamesh Munagala +1
In large scale collective decision making, social choice is a normative study of how one ought to design a protocol for reaching consensus. However, in instances where the underlyi…
Widescope - A social platform for serious conversations on the Web
Noah Burbank, Debojyoti Dutta, Ashish Goel +3
There are several web platforms that people use to interact and exchange ideas, such as social networks like Facebook, Twitter, and Google+; Q&A sites like Quora and Yahoo! Answers…
Dimension Independent Similarity Computation
Reza Bosagh Zadeh, Ashish Goel
We present a suite of algorithms for Dimension Independent Similarity Computation (DISCO) to compute all pairwise similarities between very high dimensional sparse vectors. All of…
GNSS Radio Occultation on Aerial Platforms with Commercial Off-The-Shelf Receivers
Bryan C. Chan, Ashish Goel, Jonathan Kosh +8
In recent decades, GNSS Radio Occultation soundings have proven an invaluable input to global weather forecasting. The success of government-sponsored programs such as COSMIC is no…
Crowdsourcing for Participatory Democracies: Efficient Elicitation of Social Choice Functions
David Lee, Ashish Goel, Tanja Aitamurto +1
We present theoretical and empirical results demonstrating the usefulness of voting rules for participatory democracies. We first give algorithms which efficiently elicit ε-approx…
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk
Ashish Goel, Ian Post
We study the single-sink buy-at-bulk problem with an unknown cost function. We wish to route flow from a set of demand nodes to a root node, where the cost of routing x total flow…
The Hemispheric Asymmetry of Solar Activity During the Twentieth Century and the Solar Dynamo
Ashish Goel, Arnab Rai Choudhuri
We believe the Babcock--Leighton process of poloidal field generation to be the main source of irregularity in the solar cycle. The random nature of this process may make the poloi…
Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs
Ashish Goel, Michael Kapralov, Sanjeev Khanna
In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time …
Markets Beyond Nash Welfare for Leontief Utilities
Ashish Goel, Reyna Hulett, Benjamin Plaut
We study the allocation of divisible goods to competing agents via a market mechanism, focusing on agents with Leontief utilities. The majority of the economics and mechanism desig…
Flight Demonstration and Model Validation of a Prototype Variable-Altitude Venus Aerobot
Jacob S. Izraelevitz, Siddharth Krishnamoorthy, Ashish Goel +15
This paper details a significant milestone towards maturing a buoyant aerial robotic platform, or aerobot, for flight in the Venus clouds. We describe two flights of our subscale a…
Triadic Consensus: A Randomized Algorithm for Voting in a Crowd
Ashish Goel, David Lee
Typical voting rules do not work well in settings with many candidates. If there are just several hundred candidates, then even a simple task such as choosing a top candidate becom…
Monotone properties of random geometric graphs have sharp thresholds
Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari
Random geometric graphs result from taking uniformly distributed points in the unit cube, , and connecting two points if their Euclidean distance is at most , for s…
Towards large-scale deliberative decision-making: small groups and the importance of triads
Ashish Goel, David T. Lee
Though deliberation is a critical component of democratic decision-making, existing deliberative processes do not scale to large groups of people. Motivated by this, we propose a m…
Perfect Matchings in Ã(n^{1.5}) Time in Regular Bipartite Graphs
Ashish Goel, Michael Kapralov, Sanjeev Khanna
We consider the well-studied problem of finding a perfect matching in -regular bipartite graphs with vertices and edges. While the best-known algorithm for general…
Estimating Contribution Quality in Online Deliberations Using a Large Language Model
Lodewijk Gelauff, Mohak Goyal, Bhargav Dindukurthi +2
Deliberation involves participants exchanging knowledge, arguments, and perspectives and has been shown to be effective at addressing polarization. The Stanford Online Deliberation…
Knapsack Voting for Participatory Budgeting
Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong +1
We address the question of aggregating the preferences of voters in the context of participatory budgeting. We scrutinize the voting method currently used in practice, underline it…
Hybrid Keyword Search Auctions
Ashish Goel, Kamesh Munagala
Search auctions have become a dominant source of revenue generation on the Internet. Such auctions have typically used per-click bidding and pricing. We propose the use of hybrid a…
Beyond Polarization: Opinion Mixing and Social Influence in Deliberation
Mohak Goyal, Lodewijk Gelauff, Naman Gupta +2
Deliberative processes are often discussed as increasing or decreasing polarization. This approach misses a different, and arguably more diagnostic, dimension of opinion change: wh…
Graph Sparsification via Refinement Sampling
Ashish Goel, Michael Kapralov, Sanjeev Khanna
A graph G'(V,E') is an \eps-sparsification of G for some \eps>0, if every (weighted) cut in G' is within (1\pm \eps) of the corresponding cut in G. A celebrated result of Benczur a…
Differential Privacy with Multiple Selections
Ashish Goel, Zhihao Jiang, Aleksandra Korolova +2
We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a ``multi-selection'' a…
Finding the Right Curve: Optimal Design of Constant Function Market Makers
Mohak Goyal, Geoffrey Ramseyer, Ashish Goel +1
Constant Function Market Makers (CFMMs) are a tool for creating exchange markets, have been deployed effectively in prediction markets, and are now especially prominent in the Dece…
A Lightweight Space-based Solar Power Generation and Transmission Satellite
Behrooz Abiri, Manan Arya, Florian Bohn +17
We propose a novel design for a lightweight, high-performance space-based solar power array combined with power beaming capability for operation in geosynchronous orbit and transmi…
Advertising for Demographically Fair Outcomes
Lodewijk Gelauff, Ashish Goel, Kamesh Munagala +1
Online advertising on platforms such as Google or Facebook has become an indispensable outreach tool, including for applications where it is desirable to engage different demograph…
Distributed Instruments for Planetary Surface Science: Scientific Opportunities and Technology Feasibility
Federico Rossi, Robert C. Anderson, Saptarshi Bandyopadhyay +6
In this paper, we assess the scientific promise and technology feasibility of distributed instruments for planetary science. A distributed instrument is an instrument designed to c…
Liquidity in Credit Networks: A Little Trust Goes a Long Way
Pranav Dandekar, Ashish Goel, Ramesh Govindan +1
Credit networks represent a way of modeling trust between entities in a network. Nodes in the network print their own currency and trust each other for a certain amount of each oth…
AI Space Cortex: An Experimental System for Future Era Space Exploration
Thomas Touma, Ersin DaÅ, Erica Tevere +9
Our Robust, Explainable Autonomy for Scientific Icy Moon Operations (REASIMO) effort contributes to NASA's Concepts for Ocean worlds Life Detection Technology (COLDTech) program, w…
Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice
Brandon Fain, Ashish Goel, Kamesh Munagala +1
We study social choice mechanisms in an implicit utilitarian framework with a metric constraint, where the goal is to minimize \textit{Distortion}, the worst case social cost of an…
Fast Incremental and Personalized PageRank
Bahman Bahmani, Abdur Chowdhury, Ashish Goel
In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation of PageRank, personalized PageRank, and similar random walk based methods (with focus on…
Efficient Distributed Locality Sensitive Hashing
Bahman Bahmani, Ashish Goel, Rajendra Shinde
Distributed frameworks are gaining increasingly widespread use in applications that process large amounts of data. One important example application is large scale similarity searc…
Similarity Search and Locality Sensitive Hashing using TCAMs
Rajendra Shinde, Ashish Goel, Pankaj Gupta +1
Similarity search methods are widely used as kernels in various machine learning applications. Nearest neighbor search (NNS) algorithms are often used to retrieve similar entries,…
Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks
Zoe Abrams, Ashish Goel, Serge Plotkin
Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy for energy efficient monitoring in WSNs that parti…
SPEEDEX: A Scalable, Parallelizable, and Economically Efficient Decentralized EXchange
Geoffrey Ramseyer, Ashish Goel, David Mazières
SPEEDEX is a decentralized exchange (DEX) that lets participants securely trade assets without giving any single party undue control over the market. SPEEDEX offers several advanta…
Opinion Change or Differential Turnout: Changing Opinions on the Austin Police Department in a Budget Feedback Process
Lodewijk L. Gelauff, Ashish Goel
In 2020 the tragic murder of George Floyd at the hands of law enforcement ignited and intensified nationwide protests, demanding changes in police funding and allocation. This happ…
Rank, Pack, or Approve: Voting Methods in Participatory Budgeting
Lodewijk Gelauff, Ashish Goel
Participatory budgeting is a popular method to engage residents in budgeting decisions by local governments. The Stanford Participatory Budgeting platform is an online platform tha…
Implementing the Lexicographic Maxmin Bargaining Solution
Ashish Goel, Anilesh K. Krishnaswamy
There has been much work on exhibiting mechanisms that implement various bargaining solutions, in particular, the Kalai-Smorodinsky solution \cite{moulin1984implementing} and the N…
Markets for Public Decision-making
Nikhil Garg, Ashish Goel, Benjamin Plaut
A public decision-making problem consists of a set of issues, each with multiple possible alternatives, and a set of competing agents, each with a preferred alternative for each is…
Single pass sparsification in the streaming model with edge deletions
Ashish Goel, Michael Kapralov, Ian Post
In this paper we give a construction of cut sparsifiers of Benczur and Karger in the {\em dynamic} streaming setting in a single pass over the data stream. Previous constructions e…
Learning and Autonomy for Extraterrestrial Terrain Sampling: An Experience Report from OWLAT Deployment
Pranay Thangeda, Ashish Goel, Erica Tevere +6
Extraterrestrial autonomous lander missions increasingly demand adaptive capabilities to handle the unpredictable and diverse nature of the terrain. This paper discusses the deploy…
Who is in Your Top Three? Optimizing Learning in Elections with Many Candidates
Nikhil Garg, Lodewijk Gelauff, Sukolsak Sakshuwong +1
Elections and opinion polls often have many candidates, with the aim to either rank the candidates or identify a small set of winners according to voters' preferences. In practice,…
Robust Allocations with Diversity Constraints
Zeyu Shen, Lodewijk Gelauff, Ashish Goel +2
We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed to introduce diversity constraints on the items the…
Pruning based Distance Sketches with Provable Guarantees on Random Graphs
Hongyang Zhang, Huacheng Yu, Ashish Goel
Measuring the distances between vertices on graphs is one of the most fundamental components in network analysis. Since finding shortest paths requires traversing the graph, it is…
Relating Metric Distortion and Fairness of Social Choice Rules
Ashish Goel, Reyna Hulett, Anilesh K. Krishnaswamy
One way of evaluating social choice (voting) rules is through a utilitarian distortion framework. In this model, we assume that agents submit full rankings over the alternatives, a…
Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties
Ashish Goel, Anilesh Kollagunta Krishnaswamy, Kamesh Munagala
We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these co…
Personalized PageRank to a Target Node
Peter Lofgren, Ashish Goel
Personalalized PageRank uses random walks to determine the importance or authority of nodes in a graph from the point of view of a given source node. Much past work has considered…
Continuous Credit Networks and Layer 2 Blockchains: Monotonicity and Sampling
Ashish Goel, Geoffrey Ramseyer
To improve transaction rates, many cryptocurrencies have implemented so-called ''Layer-2'' transaction protocols, where payments are routed across networks of private payment chann…
The Core of the Participatory Budgeting Problem
Brandon Fain, Ashish Goel, Kamesh Munagala
In participatory budgeting, communities collectively decide on the allocation of public tax dollars for local public projects. In this work, we consider the question of fairly aggr…
Source Routing and Scheduling in Packet Networks
Matthew Andrews, Antonio Fernandez, Ashish Goel +1
We study {\em routing} and {\em scheduling} in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected.…
Biased Assimilation, Homophily and the Dynamics of Polarization
Pranav Dandekar, Ashish Goel, David Lee
Are we as a society getting more polarized, and if so, why? We try to answer this question through a model of opinion formation. Empirical studies have shown that homophily results…
Augmenting Batch Exchanges with Constant Function Market Makers
Geoffrey Ramseyer, Mohak Goyal, Ashish Goel +1
Batch auctions are a classical market microstructure, acclaimed for their fairness properties, and have received renewed interest in the context of blockchain-based financial syste…
Complexity Measures for Map-Reduce, and Comparison to Parallel Computing
Ashish Goel, Kamesh Munagala
The programming paradigm Map-Reduce and its main open-source implementation, Hadoop, have had an enormous impact on large scale data processing. Our goal in this expository writeup…
Fair Ordering in Replicated Systems via Streaming Social Choice
Geoffrey Ramseyer, Ashish Goel
Prior work studies the question of ``fairly'' ordering transactions in a replicated state machine. Each of replicas receives transactions in a possibly different order, and the…
Personalized PageRank Estimation and Search: A Bidirectional Approach
Peter Lofgren, Siddhartha Banerjee, Ashish Goel
We present new algorithms for Personalized PageRank estimation and Personalized PageRank search. First, for the problem of estimating Personalized PageRank (PPR) from a source dist…
An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk
Ashish Goel, Ian Post
We consider the single-source (or single-sink) buy-at-bulk problem with an unknown concave cost function. We want to route a set of demands along a graph to or from a designated ro…
Counteracting Inequality in Markets via Convex Pricing
Ashish Goel, Benjamin Plaut
We study market mechanisms for allocating divisible goods to competing agents with quasilinear utilities. For \emph{linear} pricing (i.e., the cost of a good is proportional to the…
Re-incentivizing Discovery: Mechanisms for Partial-Progress Sharing in Research
Anilesh Kollagunta Krishnaswamy, Ashish Goel, Siddhartha Banerjee
An essential primitive for an efficient research ecosystem is \emph{partial-progress sharing} (PPS) -- whereby a researcher shares information immediately upon making a breakthroug…
Satellite Navigation for the Age of Autonomy
Tyler G. R. Reid, Bryan Chan, Ashish Goel +6
Global Navigation Satellite Systems (GNSS) brought navigation to the masses. Coupled with smartphones, the blue dot in the palm of our hands has forever changed the way we interact…
Metric Distortion of Small-group Deliberation
Ashish Goel, Mohak Goyal, Kamesh Munagala
We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most , and these outcomes are aggregated by…
Probing the Cosmic Dark Ages with the Lunar Crater Radio Telescope
Ashish Goel, Saptarshi Bandyopadhyay, Joseph Lazio +17
The Cosmic Dark Ages represent the period in the early evolution of the Universe, starting immediately after the decoupling of CMB photons from matter, and ending with the formatio…
A Mechanism for Participatory Budgeting With Funding Constraints and Project Interactions
Mohak Goyal, Sahasrajit Sarmasarkar, Ashish Goel
Participatory budgeting (PB) has been widely adopted and has attracted significant research efforts; however, there is a lack of mechanisms for PB which elicit project interactions…
Liquidity in Credit Networks with Constrained Agents
Geoffrey Ramseyer, Ashish Goel, David Mazieres
In order to scale transaction rates for deployment across the global web, many cryptocurrencies have deployed so-called "Layer-2" networks of private payment channels. An idealized…
The Ratio Index for Budgeted Learning, with Applications
Ashish Goel, Sanjeev Khanna, Brad Null
In the budgeted learning problem, we are allowed to experiment on a set of alternatives (given a fixed experimentation budget) with the goal of picking a single alternative with th…
Question the Questions: Auditing Representation in Online Deliberative Processes
Soham De, Lodewijk Gelauff, Ashish Goel +3
A central feature of many deliberative processes, such as citizens' assemblies and deliberative polls, is the opportunity for participants to engage directly with experts. While pa…
Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs
Ashish Goel, Michael Kapralov, Sanjeev Khanna
In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The best-known algorithm for general bi…
Bidirectional PageRank Estimation: From Average-Case to Worst-Case
Peter Lofgren, Siddhartha Banerjee, Ashish Goel
We present a new algorithm for estimating the Personalized PageRank (PPR) between a source and target node on undirected graphs, with sublinear running-time guarantees over the wor…
Quality-Sensitive Matrix Factorization for Community Notes: Towards Sample Efficiency and Manipulation Resistance
Mohak Goyal, Nishka Arora, Ashish Goel
Community Notes is X's crowdsourced fact-checking program: contributors write short notes that add context to potentially misleading posts, and other contributors rate whether thos…
Iterative Local Voting for Collective Decision-making in Continuous Spaces
Nikhil Garg, Vijay Kamble, Ashish Goel +2
Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These…
When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors
Aneesh Sharma, C. Seshadhri, Ashish Goel
Finding similar user pairs is a fundamental task in social networks, with numerous applications in ranking and personalization tasks such as link prediction and tie strength detect…
BEVIO: Efficient Bird's-Eye-View based Sparse-Update Visual-Inertial Odometry for Lunar Day-Night Navigation
Mohit Singh, Shehryar Khattak, Ashish Goel +3
Visual-Inertial Odometry (VIO) provides smooth, high-rate state estimates and has been widely used for robotic navigation in both terrestrial and planetary applications. However, i…
Approximate Personalized PageRank on Dynamic Graphs
Hongyang Zhang, Peter Lofgren, Ashish Goel
We propose and analyze two algorithms for maintaining approximate Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added or deleted. Our algorithms are natur…
FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
Peter Lofgren, Siddhartha Banerjee, Ashish Goel +1
We propose a new algorithm, FAST-PPR, for estimating personalized PageRank: given start node and target node in a directed graph, and given a threshold , FAST-PPR estim…
The impossibility of low rank representations for triangle-rich complex networks
C. Seshadhri, Aneesh Sharma, Andrew Stolman +1
The study of complex networks is a significant development in modern science, and has enriched the social sciences, biology, physics, and computer science. Models and algorithms fo…
Geophysical Observations of the 24 September 2023 OSIRIS-REx Sample Return Capsule Re-Entry
Elizabeth A. Silber, Daniel C. Bowman, Chris G. Carr +79
Sample Return Capsules (SRCs) entering Earth's atmosphere at hypervelocity from interplanetary space are a valuable resource for studying meteor phenomena. The 24 September 2023 ar…
Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families
Douglas E. Carroll, Ashish Goel
It was shown recently by Fakcharoenphol et al that arbitrary finite metrics can be embedded into distributions over tree metrics with distortion O(log n). It is also known that thi…