Showing 1–50 of 59 results for author: Shubhangi

Vision-Language-Guided Pseudo-Labels for Unsupervised Domain Adaptation in Semantic Segmentation for Waste Sorting

Authors: Udo Schlegel, Shubhangi, Gabriel Dax, Sai Rahul Kaminwar, Florian Karl, Thomas Seidl

Abstract: Obtaining labeled data for semantic segmentation in applied settings (e.g., autonomous driving, industrial waste sorting) is expensive and often infeasible at scale. We present a cross-modal pseudo-labeling pipeline that enables unsupervised domain adaptation without any target-domain annotations. The pipeline is built on two core foundation models: SAM generates class-agnostic region proposals, a… ▽ More Obtaining labeled data for semantic segmentation in applied settings (e.g., autonomous driving, industrial waste sorting) is expensive and often infeasible at scale. We present a cross-modal pseudo-labeling pipeline that enables unsupervised domain adaptation without any target-domain annotations. The pipeline is built on two core foundation models: SAM generates class-agnostic region proposals, and EVA-CLIP assigns semantic labels based on region-text similarity, with confidence filtering ensuring that only reliable pseudo-labels are used for self-training a segmentation model. As an optional extension, BLIP provides language-grounded verification for ambiguous regions, thereby improving pseudo-label quality without altering the overall pipeline. Evaluated on two domain shifts, synthetic-to-real autonomous driving and, with a primary focus, lab-to-factory industrial waste sorting, the pipeline consistently improves over source-only baselines. Our results demonstrate that pseudo-label quality, not quantity, is a decisive factor in self-training under domain shift, and that cross-modal language grounding offers a practical path to reliable automatic annotation in deployment-critical applications. △ Less

Submitted 1 September, 2026; originally announced September 2026.

Comments: 18 pages, 2 figures, 2 tables, accepted at ECML-PKDD 2026

On the CGGRT Criterion for Detecting Bipartite Perfect Matchings in NC

Authors: Swastik Kopparty, Shubhangi Saraf

Abstract: The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the NC detection criterion of [CGGRT26], with improved parameters. The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the NC detection criterion of [CGGRT26], with improved parameters. △ Less

Submitted 16 July, 2026; originally announced July 2026.

Comments: 8 pages

Deterministic Algorithms for Low Individual Degree Factors of Sparse Polynomials

Authors: Somnath Bhattacharjee, Rishabh Kothary, Shanthanu S. Rai, Shubhangi Saraf

Abstract: We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results. 1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains all factors of $f$, although there might be additional spu… ▽ More We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results. 1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains all factors of $f$, although there might be additional spurious circuits in the list. The algorithm runs in time $\operatorname{poly}(n, s^d)$. Additionally, every circuit in the list has constant depth. Our algorithm works over all fields of characteristic 0 or sufficiently large characteristic. Our result generalizes a recent result of Chuyoon and Shpilka that gives a $\operatorname{poly}(n, s^d)$-time algorithm for recovering all sparse factors of $f$ (without spurious factors). As a corollary, we can also recover all factors of $f$ in time $\operatorname{poly}(n, s^{d^2 \log n})$, and recover the algorithmic result of Bhargava, Saraf and Volkovich and its improvement by Chuyoon and Shpilka. Both the above consequences follow from known interpolation and divisibility testing techniques. 2. We give a deterministic quasipolynomial-time algorithm which takes as input a general $n$-variate $s$-sparse polynomial $f$ of (unbounded) individual degree $D$ and outputs a list of polynomials which contains all factors of $f$ that have bounded individual degree $d$. The algorithm runs in time $\operatorname{poly}(D^{d \log s}, s^{d^2 \log n})$ and works over arbitrary fields. The list may again contain spurious elements. Our result strengthens results of Dutta, Sinhababu and Thierauf and Kumar, Ramanathan and Saptharishi which give algorithms to recover all factors of $f$ of bounded total degree. A consequence of our algorithm is a new upper bound on the total number of bounded individual degree factors of a sparse polynomial. △ Less

Submitted 25 June, 2026; originally announced June 2026.

Test-Time Adaptation via Many-Shot Prompting: Benefits, Limits, and Pitfalls

Authors: Shubhangi Upasani, Chen Wu, Jay Rainton, Bo Li, Urmish Thakker, Changran Hu, Qizheng Zhang

Abstract: Test-time adaptation enables large language models (LLMs) to modify their behavior at inference without updating model parameters. A common approach is many-shot prompting, where large numbers of in-context learning (ICL) examples are injected as an input-space test-time update. Although performance can improve as more demonstrations are added, the reliability and limits of this update mechanism r… ▽ More Test-time adaptation enables large language models (LLMs) to modify their behavior at inference without updating model parameters. A common approach is many-shot prompting, where large numbers of in-context learning (ICL) examples are injected as an input-space test-time update. Although performance can improve as more demonstrations are added, the reliability and limits of this update mechanism remain poorly understood, particularly for open-source models. We present an empirical study of many-shot prompting across tasks and model backbones, analyzing how performance varies with update magnitude, example ordering, and selection policy. We further study Dynamic and Reinforced ICL as alternative test-time update strategies that control which information is injected and how it constrains model behavior. We find that many-shot prompting is effective for structured tasks where demonstrations provide high information gain, but is highly sensitive to selection strategy and often shows limited benefits for open-ended generation tasks. Overall, we characterize the practical limits of prompt-based test-time adaptation and outline when input-space updates are beneficial versus harmful. △ Less

Submitted 17 March, 2026; v1 submitted 5 March, 2026; originally announced March 2026.

Cross-Family Speculative Prefill: Training-Free Long-Context Compression with Small Draft Models

Authors: Shubhangi Upasani, Ravi Shanker Raju, Bo Li, Mengmeng Ji, John Long, Chen Wu, Urmish Thakker, Guangtao Wang

Abstract: Prompt length is a major bottleneck in agentic large language model (LLM) workloads, where repeated inference steps and multi-call loops incur substantial prefill cost. Recent work on speculative prefill demonstrates that attention-based token importance estimation can enable training-free prompt compression, but this assumes the existence of a draft model that shares the same tokenizer as the tar… ▽ More Prompt length is a major bottleneck in agentic large language model (LLM) workloads, where repeated inference steps and multi-call loops incur substantial prefill cost. Recent work on speculative prefill demonstrates that attention-based token importance estimation can enable training-free prompt compression, but this assumes the existence of a draft model that shares the same tokenizer as the target model. In practice, however, agentic pipelines frequently employ models without any smaller in-family draft model. In this work, we study cross-family speculative prefill, where a lightweight draft model from one model family is used to perform prompt compression for a target model from a different family. Using the same speculative prefill mechanism as prior work, we evaluate a range of cross-family draft-target combinations, including Qwen, LLaMA, and DeepSeek models. Across a broad diversity of tasks, we find that attention-based token importance estimation transfers reliably across different model families despite differences in model architectures and tokenizers between draft and target models. Cross-model prompt compression largely retains 90~100% of full-prompt baseline performance and, in some cases, slightly improves accuracy due to denoising effects, while delivering substantial reductions in time to first token (TTFT). These results suggest that speculative prefill depends mainly on task priors and semantic structure, thus serving as a generalizable prompt compression primitive. We discuss the implications of our findings for agentic systems, where repeated long-context inference and heterogeneous model stacks make cross-model prompt compression both necessary and practical. △ Less

Submitted 12 March, 2026; v1 submitted 3 March, 2026; originally announced March 2026.

Journal ref: ICLR 2026 (WS)

The Limits of Long-Context Reasoning in Automated Bug Fixing

Authors: Ravi Raju, Mengmeng Ji, Shubhangi Upasani, Bo Li, Urmish Thakker

Abstract: Rapidly increasing context lengths have led to the assumption that large language models (LLMs) can directly reason over entire codebases. Concurrently, recent advances in LLMs have enabled strong performance on software engineering benchmarks, particularly when paired with agentic workflows. In this work, we systematically evaluate whether current LLMs can reliably perform long-context code debug… ▽ More Rapidly increasing context lengths have led to the assumption that large language models (LLMs) can directly reason over entire codebases. Concurrently, recent advances in LLMs have enabled strong performance on software engineering benchmarks, particularly when paired with agentic workflows. In this work, we systematically evaluate whether current LLMs can reliably perform long-context code debugging and patch generation. Using SWE-bench Verified as a controlled experimental setting, we first evaluate state-of-the-art models within an agentic harness (mini-SWE-agent), where performance improves substantially: GPT-5-nano achieves up to a 31\% resolve rate on 100 samples, and open-source models such as Deepseek-R1-0528 obtain competitive results. However, token-level analysis shows that successful agentic trajectories typically remain under 20k-30k tokens, and that longer accumulated contexts correlate with lower success rates, indicating that agentic success primarily arises from task decomposition into short-context steps rather than effective long-context reasoning. To directly test long-context capability, we construct a data pipeline where we artificially inflate the context length of the input by placing the relevant files into the context (ensuring perfect retrieval recall); we then study single-shot patch generation under genuinely long contexts (64k tokens). Despite this setup, performance degrades sharply: Qwen3-Coder-30B-A3B achieves only a 7\% resolve rate at 64k context, while GPT-5-nano solves none of the tasks. Qualitative analysis reveals systematic failure modes, including hallucinated diffs, incorrect file targets, and malformed patch headers. Overall, our findings highlight a significant gap between nominal context length and usable context capacity in current LLMs, and suggest that existing agentic coding benchmarks do not meaningfully evaluate long-context reasoning. △ Less

Submitted 6 March, 2026; v1 submitted 17 February, 2026; originally announced February 2026.

Comments: Accepted to ICLR 2026 ICBINB workshop

Imperfect Influence, Preserved Rankings: A Theory of TRAK for Data Attribution

Authors: Han Tong, Shubhangi Ghosh, Haolin Zou, Arian Maleki

Abstract: Data attribution, tracing a model's prediction back to specific training data, is an important tool for interpreting sophisticated AI models. The widely used TRAK algorithm addresses this challenge by first approximating the underlying model with a kernel machine and then leveraging techniques developed for approximating the leave-one-out (ALO) risk. Despite its strong empirical performance, the t… ▽ More Data attribution, tracing a model's prediction back to specific training data, is an important tool for interpreting sophisticated AI models. The widely used TRAK algorithm addresses this challenge by first approximating the underlying model with a kernel machine and then leveraging techniques developed for approximating the leave-one-out (ALO) risk. Despite its strong empirical performance, the theoretical conditions under which the TRAK approximations are accurate as well as the regimes in which they break down remain largely unexplored. In this paper, we provide a theoretical analysis of the TRAK algorithm, characterizing its performance and quantifying the errors introduced by the approximations on which the method relies. We show that although the approximations incur significant errors, TRAK's estimated influence remains highly correlated with the original influence and therefore largely preserves the relative ranking of data points. We corroborate our theoretical results through extensive simulations and empirical studies. △ Less

Submitted 1 February, 2026; originally announced February 2026.

A Lightweight CNN-Attention-BiLSTM Architecture for Multi-Class Arrhythmia Classification on Standard and Wearable ECGs

Authors: Vamsikrishna Thota, Hardik Prajapati, Yuvraj Joshi, Shubhangi Rathi

Abstract: Early and accurate detection of cardiac arrhythmias is vital for timely diagnosis and intervention. We propose a lightweight deep learning model combining 1D Convolutional Neural Networks (CNN), attention mechanisms, and Bidirectional Long Short-Term Memory (BiLSTM) for classifying arrhythmias from both 12-lead and single-lead ECGs. Evaluated on the CPSC 2018 dataset, the model addresses class imb… ▽ More Early and accurate detection of cardiac arrhythmias is vital for timely diagnosis and intervention. We propose a lightweight deep learning model combining 1D Convolutional Neural Networks (CNN), attention mechanisms, and Bidirectional Long Short-Term Memory (BiLSTM) for classifying arrhythmias from both 12-lead and single-lead ECGs. Evaluated on the CPSC 2018 dataset, the model addresses class imbalance using a class-weighted loss and demonstrates superior accuracy and F1- scores over baseline models. With only 0.945 million parameters, our model is well-suited for real-time deployment in wearable health monitoring systems. △ Less

Submitted 11 November, 2025; originally announced November 2025.

SnapStream: Efficient Long Sequence Decoding on Dataflow Accelerators

Authors: Jonathan Li, Nasim Farahini, Evgenii Iuliugin, Magnus Vesterlund, Christian Häggström, Guangtao Wang, Shubhangi Upasani, Ayush Sachdeva, Rui Li, Faline Fu, Chen Wu, Ayesha Siddiqua, John Long, Tuowen Zhao, Matheen Musaddiq, Håkan Zeffer, Yun Du, Mingran Wang, Qinghua Li, Bo Li, Urmish Thakker, Raghu Prabhakar

Abstract: The proliferation of 100B+ parameter Large Language Models (LLMs) with 100k+ context length support have resulted in increasing demands for on-chip memory to support large KV caches. Techniques such as StreamingLLM and SnapKV demonstrate how to control KV cache size while maintaining model accuracy. Yet, these techniques are not commonly used within industrial deployments using frameworks like vLL… ▽ More The proliferation of 100B+ parameter Large Language Models (LLMs) with 100k+ context length support have resulted in increasing demands for on-chip memory to support large KV caches. Techniques such as StreamingLLM and SnapKV demonstrate how to control KV cache size while maintaining model accuracy. Yet, these techniques are not commonly used within industrial deployments using frameworks like vLLM or SGLang. The reason is twofold: on one hand, the static graphs and continuous batching methodology employed by these frameworks make it difficult to admit modifications to the standard multi-head attention algorithm, while on the other hand, the accuracy implications of such techniques on modern instruction-following and reasoning models are not well understood, obfuscating the need for implementing these techniques. In this paper, we explore these accuracy implications on Llama-3.1-8B-Instruct and DeepSeek-R1, and develop SnapStream, a KV cache compression method that can be deployed at scale. We demonstrate the efficacy of SnapStream in a 16-way tensor-parallel deployment of DeepSeek-671B on SambaNova SN40L accelerators running at 128k context length and up to 1832 tokens per second in a real production setting. SnapStream enables $4\times$ improved on-chip memory usage and introduces minimal accuracy degradation on LongBench-v2, AIME24 and LiveCodeBench. To the best of our knowledge, this is the first implementation of sparse KV attention techniques deployed in a production inference system with static graphs and continuous batching. △ Less

Submitted 8 April, 2026; v1 submitted 4 November, 2025; originally announced November 2025.

Patient-Centered Summarization Framework for AI Clinical Summarization: A Mixed-Methods Design

Authors: Maria Lizarazo Jimenez, Ana Gabriela Claros, Kieran Green, David Toro-Tobon, Felipe Larios, Sheena Asthana, Camila Wenczenovicz, Kerly Guevara Maldonado, Luis Vilatuna-Andrango, Cristina Proano-Velez, Satya Sai Sri Bandi, Shubhangi Bagewadi, Megan E. Branda, Misk Al Zahidy, Saturnino Luz, Mirella Lapata, Juan P. Brito, Oscar J. Ponce-Ponte

Abstract: Large Language Models (LLMs) are increasingly demonstrating the potential to reach human-level performance in generating clinical summaries from patient-clinician conversations. However, these summaries often focus on patients' biology rather than their preferences, values, wishes, and concerns. To achieve patient-centered care, we propose a new standard for Artificial Intelligence (AI) clinical s… ▽ More Large Language Models (LLMs) are increasingly demonstrating the potential to reach human-level performance in generating clinical summaries from patient-clinician conversations. However, these summaries often focus on patients' biology rather than their preferences, values, wishes, and concerns. To achieve patient-centered care, we propose a new standard for Artificial Intelligence (AI) clinical summarization tasks: Patient-Centered Summaries (PCS). Our objective was to develop a framework to generate PCS that capture patient values and ensure clinical utility and to assess whether current open-source LLMs can achieve human-level performance in this task. We used a mixed-methods process. Two Patient and Public Involvement groups (10 patients and 8 clinicians) in the United Kingdom participated in semi-structured interviews exploring what personal and contextual information should be included in clinical summaries and how it should be structured for clinical use. Findings informed annotation guidelines used by eight clinicians to create gold-standard PCS from 88 atrial fibrillation consultations. Sixteen consultations were used to refine a prompt aligned with the guidelines. Five open-source LLMs (Llama-3.2-3B, Llama-3.1-8B, Mistral-8B, Gemma-3-4B, and Qwen3-8B) generated summaries for 72 consultations using zero-shot and few-shot prompting, evaluated with ROUGE-L, BERTScore, and qualitative metrics. Patients emphasized lifestyle routines, social support, recent stressors, and care values. Clinicians sought concise functional, psychosocial, and emotional context. The best zero-shot performance was achieved by Mistral-8B (ROUGE-L 0.189) and Llama-3.1-8B (BERTScore 0.673); the best few-shot by Llama-3.1-8B (ROUGE-L 0.206, BERTScore 0.683). Completeness and fluency were similar between experts and models, while correctness and patient-centeredness favored human PCS. △ Less

Submitted 31 October, 2025; originally announced October 2025.

Comments: The first two listed authors contributed equally Pages: 21; Figures:2; Tables:3

Integer points in dilates of polytopes

Authors: Shubhangi Saraf, Narmada Varadarajan

Abstract: In this paper we study how the number of integer points in a polytope grows as we dilate the polytope. We prove new and essentially tight bounds on this quantity by specifically studying dilates of the Hadamard polytope. Our motivation for studying this quantity comes from the problem of understanding the maximal number of monomials in a factor of a multivariate polynomial with $s$ monomials. A… ▽ More In this paper we study how the number of integer points in a polytope grows as we dilate the polytope. We prove new and essentially tight bounds on this quantity by specifically studying dilates of the Hadamard polytope. Our motivation for studying this quantity comes from the problem of understanding the maximal number of monomials in a factor of a multivariate polynomial with $s$ monomials. A recent result by Bhargava, Saraf, and Volkovich showed that if $f$ is an $n$-variate polynomial, where each variable has degree $d$, and $f$ has $s$ monomials, then any factor of $f$ has at most $s^{O(d^2 \log n)}$ monomials. The key technical ingredient of their proof was to show that any polytope with $s$ vertices, where each vertex lies in $\{0,..,d\}^n$, can have at most $s^{O(d^2 \log n)}$ integer points. The precise dependence on $d$ of the number of integer points was left open. We show that this bound, particularly the dependence on $d$, is essentially tight by studying dilates of the Hadamard polytope and proving new lower bounds on the number of its integer points. △ Less

Submitted 18 October, 2025; originally announced October 2025.

Agentic Context Engineering: Evolving Contexts for Self-Improving Language Models

Authors: Qizheng Zhang, Changran Hu, Shubhangi Upasani, Boyuan Ma, Fenglu Hong, Vamsidhar Kamanuru, Jay Rainton, Chen Wu, Mengmeng Ji, Hanchen Li, Urmish Thakker, James Zou, Kunle Olukotun

Abstract: Large language model (LLM) applications such as agents and domain-specific reasoning increasingly rely on context adaptation: modifying inputs with instructions, strategies, or evidence, rather than weight updates. Prior approaches improve usability but often suffer from brevity bias, which drops domain insights for concise summaries, and from context collapse, where iterative rewriting erodes det… ▽ More Large language model (LLM) applications such as agents and domain-specific reasoning increasingly rely on context adaptation: modifying inputs with instructions, strategies, or evidence, rather than weight updates. Prior approaches improve usability but often suffer from brevity bias, which drops domain insights for concise summaries, and from context collapse, where iterative rewriting erodes details over time. We introduce ACE (Agentic Context Engineering), a framework that treats contexts as evolving playbooks that accumulate, refine, and organize strategies through a modular process of generation, reflection, and curation. ACE prevents collapse with structured, incremental updates that preserve detailed knowledge and scale with long-context models. Across agent and domain-specific benchmarks, ACE optimizes contexts both offline (e.g., system prompts) and online (e.g., agent memory), consistently outperforming strong baselines: +10.6% on agents and +8.6% on finance, while significantly reducing adaptation latency and rollout cost. Notably, ACE could adapt effectively without labeled supervision and instead by leveraging natural execution feedback. On the AppWorld leaderboard, ACE matches the top-ranked production-level agent on the overall average and surpasses it on the harder test-challenge split, despite using a smaller open-source model. These results show that comprehensive, evolving contexts enable scalable, efficient, and self-improving LLM systems with low overhead. △ Less

Submitted 29 March, 2026; v1 submitted 6 October, 2025; originally announced October 2025.

Comments: ICLR 2026; 32 pages

Constant-depth circuits for polynomial GCD over any characteristic

Authors: Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Abstract: We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews & Wigderson who showed such an upper bound over fields of zero or large characteristic. Our proofs are based on a recent work of Bhattacharjee, Kumar… ▽ More We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews & Wigderson who showed such an upper bound over fields of zero or large characteristic. Our proofs are based on a recent work of Bhattacharjee, Kumar, Rai, Ramanathan, Saptharishi \& Saraf that shows closure of constant depth algebraic circuits under factorization. On our way to the proof, we show that any $n$-variate symmetric polynomial $P$ that has a small constant depth algebraic circuit can be written as the composition of a small constant depth algebraic circuit with elementary symmetric polynomials. This statement is a constant depth version of a result of Bläser & Jindal, who showed this for algebraic circuits of unbounded depth. As an application of our techniques, we also strengthen the closure results for factors of constant-depth circuits in the work of Bhattacharjee et al. over fields for small characteristic. △ Less

Submitted 29 June, 2025; originally announced June 2025.

Closure under factorization from a result of Furstenberg

Authors: Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Abstract: We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively. Our result turns out to be an elementary consequence of a fundamenta… ▽ More We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively. Our result turns out to be an elementary consequence of a fundamental and surprising result of Furstenberg from the 1960s, which gives a non-iterative description of the power series roots of a bivariate polynomial. Combined with standard structural ideas in algebraic complexity, we observe that this theorem yields the desired closure results. As applications, we get alternative (and perhaps simpler) proofs of various known results and strengthen the quantitative bounds in some of them. This includes a unified proof of known closure results for algebraic models (circuits, branching programs and VNP), an extension of the analysis of the Kabanets-Impagliazzo hitting set generator to formulas and constant-depth circuits, and a (significantly) simpler proof of correctness as well as stronger guarantees on the output in the subexponential time deterministic algorithm for factorization of constant-depth circuits from a recent work of Bhattacharjee, Kumar, Ramanathan, Saptharishi & Saraf. △ Less

Submitted 29 June, 2025; originally announced June 2025.

CLAMP: Crowdsourcing a LArge-scale in-the-wild haptic dataset with an open-source device for Multimodal robot Perception

Authors: Pranav N. Thakkar, Shubhangi Sinha, Karan Baijal, Yuhan, Bian, Leah Lackey, Ben Dodson, Heisen Kong, Jueun Kwon, Amber Li, Yifei Hu, Alexios Rekoutis, Tom Silver, Tapomayukh Bhattacharjee

Abstract: Robust robot manipulation in unstructured environments often requires understanding object properties that extend beyond geometry, such as material or compliance-properties that can be challenging to infer using vision alone. Multimodal haptic sensing provides a promising avenue for inferring such properties, yet progress has been constrained by the lack of large, diverse, and realistic haptic dat… ▽ More Robust robot manipulation in unstructured environments often requires understanding object properties that extend beyond geometry, such as material or compliance-properties that can be challenging to infer using vision alone. Multimodal haptic sensing provides a promising avenue for inferring such properties, yet progress has been constrained by the lack of large, diverse, and realistic haptic datasets. In this work, we introduce the CLAMP device, a low-cost (<\$200) sensorized reacher-grabber designed to collect large-scale, in-the-wild multimodal haptic data from non-expert users in everyday settings. We deployed 16 CLAMP devices to 41 participants, resulting in the CLAMP dataset, the largest open-source multimodal haptic dataset to date, comprising 12.3 million datapoints across 5357 household objects. Using this dataset, we train a haptic encoder that can infer material and compliance object properties from multimodal haptic data. We leverage this encoder to create the CLAMP model, a visuo-haptic perception model for material recognition that generalizes to novel objects and three robot embodiments with minimal finetuning. We also demonstrate the effectiveness of our model in three real-world robot manipulation tasks: sorting recyclable and non-recyclable waste, retrieving objects from a cluttered bag, and distinguishing overripe from ripe bananas. Our results show that large-scale, in-the-wild haptic data collection can unlock new capabilities for generalizable robot manipulation. Website: https://emprise.cs.cornell.edu/clamp/ △ Less

Submitted 12 January, 2026; v1 submitted 27 May, 2025; originally announced May 2025.

A Case Study of Cross-Lingual Zero-Shot Generalization for Classical Languages in LLMs

Authors: V. S. D. S. Mahesh Akavarapu, Hrishikesh Terdalkar, Pramit Bhattacharyya, Shubhangi Agarwal, Vishakha Deulgaonkar, Pralay Manna, Chaitali Dangarikar, Arnab Bhattacharya

Abstract: Large Language Models (LLMs) have demonstrated remarkable generalization capabilities across diverse tasks and languages. In this study, we focus on natural language understanding in three classical languages -- Sanskrit, Ancient Greek and Latin -- to investigate the factors affecting cross-lingual zero-shot generalization. First, we explore named entity recognition and machine translation into En… ▽ More Large Language Models (LLMs) have demonstrated remarkable generalization capabilities across diverse tasks and languages. In this study, we focus on natural language understanding in three classical languages -- Sanskrit, Ancient Greek and Latin -- to investigate the factors affecting cross-lingual zero-shot generalization. First, we explore named entity recognition and machine translation into English. While LLMs perform equal to or better than fine-tuned baselines on out-of-domain data, smaller models often struggle, especially with niche or abstract entity types. In addition, we concentrate on Sanskrit by presenting a factoid question-answering (QA) dataset and show that incorporating context via retrieval-augmented generation approach significantly boosts performance. In contrast, we observe pronounced performance drops for smaller LLMs across these QA tasks. These results suggest model scale as an important factor influencing cross-lingual generalization. Assuming that models used such as GPT-4o and Llama-3.1 are not instruction fine-tuned on classical languages, our findings provide insights into how LLMs may generalize on these languages and their consequent utility in classical studies. △ Less

Submitted 31 May, 2025; v1 submitted 19 May, 2025; originally announced May 2025.

Comments: Accepted to ACL 2025 Findings

ACM Class: I.2.7

Deterministic factorization of constant-depth algebraic circuits in subexponential time

Authors: Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Abstract: While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when it is a constant-depth circuit. Indeed, no effi… ▽ More While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when it is a constant-depth circuit. Indeed, no efficient deterministic algorithms are known even for the seemingly easier problem of factoring sparse polynomials or even the problem of testing the irreducibility of sparse polynomials. In this work, we make progress on these questions: we design a deterministic algorithm that runs in subexponential time, and when given as input a constant-depth algebraic circuit $C$ over the field of rational numbers, it outputs algebraic circuits (of potentially unbounded depth) for all the irreducible factors of $C$, together with their multiplicities. In particular, we give the first subexponential time deterministic algorithm for factoring sparse polynomials. For our proofs, we rely on a finer understanding of the structure of power series roots of constant-depth circuits and the analysis of the Kabanets-Impagliazzo generator. In particular, we show that the Kabanets-Impagliazzo generator constructed using low-degree hard polynomials (explicitly constructed in the work of Limaye, Srinivasan & Tavenas) preserves not only the non-zeroness of small constant-depth circuits (as shown by Chou, Kumar & Solomon), but also their irreducibility and the irreducibility of their factors. △ Less

Submitted 14 June, 2025; v1 submitted 10 April, 2025; originally announced April 2025.

Comments: Some changes in Section 8.1 to reflect a subtle issue regarding the underlying field in the reduction from irreducibility to divisibility

LLMs Know What to Drop: Self-Attention Guided KV Cache Eviction for Efficient Long-Context Inference

Authors: Guangtao Wang, Shubhangi Upasani, Chen Wu, Darshan Gandhi, Jonathan Li, Changran Hu, Bo Li, Urmish Thakker

Abstract: Efficient long-context inference is critical as large language models (LLMs) adopt context windows of ranging from 128K to 1M tokens. However, the growing key-value (KV) cache and the high computational complexity of attention create significant bottlenecks in memory usage and latency. In this paper, we find that attention in diverse long-context tasks exhibits sparsity, and LLMs implicitly "know"… ▽ More Efficient long-context inference is critical as large language models (LLMs) adopt context windows of ranging from 128K to 1M tokens. However, the growing key-value (KV) cache and the high computational complexity of attention create significant bottlenecks in memory usage and latency. In this paper, we find that attention in diverse long-context tasks exhibits sparsity, and LLMs implicitly "know" which tokens can be dropped or evicted at the head level after the pre-filling stage. Based on this insight, we propose Self-Attention Guided Eviction~(SAGE-KV), a simple and effective KV eviction cache method for long-context inference. After prefilling, our method performs a one-time top-k selection at both the token and head levels to compress the KV cache, enabling efficient inference with the reduced cache. Evaluations on LongBench and three long-context LLMs (Llama3.1-8B-Instruct-128k, Llama3-8B-Prolong-512k-Instruct, and Qwen2.5-7B-Instruct-128k) show that SAGE-KV maintains accuracy comparable to full attention while significantly improving efficiency. Specifically, SAGE-KV achieves 4x higher memory efficiency with improved accuracy over the static KV cache selection method StreamLLM, and 2x higher memory efficiency with better accuracy than the dynamic KV cache selection method Quest. △ Less

Submitted 11 March, 2025; originally announced March 2025.

REPeat: A Real2Sim2Real Approach for Pre-acquisition of Soft Food Items in Robot-assisted Feeding

Authors: Nayoung Ha, Ruolin Ye, Ziang Liu, Shubhangi Sinha, Tapomayukh Bhattacharjee

Abstract: The paper presents REPeat, a Real2Sim2Real framework designed to enhance bite acquisition in robot-assisted feeding for soft foods. It uses `pre-acquisition actions' such as pushing, cutting, and flipping to improve the success rate of bite acquisition actions such as skewering, scooping, and twirling. If the data-driven model predicts low success for direct bite acquisition, the system initiates… ▽ More The paper presents REPeat, a Real2Sim2Real framework designed to enhance bite acquisition in robot-assisted feeding for soft foods. It uses `pre-acquisition actions' such as pushing, cutting, and flipping to improve the success rate of bite acquisition actions such as skewering, scooping, and twirling. If the data-driven model predicts low success for direct bite acquisition, the system initiates a Real2Sim phase, reconstructing the food's geometry in a simulation. The robot explores various pre-acquisition actions in the simulation, then a Sim2Real step renders a photorealistic image to reassess success rates. If the success improves, the robot applies the action in reality. We evaluate the system on 15 diverse plates with 10 types of food items for a soft food diet, showing improvement in bite acquisition success rates by 27\% on average across all plates. See our project website at https://emprise.cs.cornell.edu/repeat. △ Less

Submitted 13 October, 2024; originally announced October 2024.

Plug-in for visualizing 3D tool tracking from videos of Minimally Invasive Surgeries

Authors: Shubhangi Nema, Abhishek Mathur, Leena Vachhani

Abstract: This paper tackles instrument tracking and 3D visualization challenges in minimally invasive surgery (MIS), crucial for computer-assisted interventions. Conventional and robot-assisted MIS encounter issues with limited 2D camera projections and minimal hardware integration. The objective is to track and visualize the entire surgical instrument, including shaft and metallic clasper, enabling safe n… ▽ More This paper tackles instrument tracking and 3D visualization challenges in minimally invasive surgery (MIS), crucial for computer-assisted interventions. Conventional and robot-assisted MIS encounter issues with limited 2D camera projections and minimal hardware integration. The objective is to track and visualize the entire surgical instrument, including shaft and metallic clasper, enabling safe navigation within the surgical environment. The proposed method involves 2D tracking based on segmentation maps, facilitating creation of labeled dataset without extensive ground-truth knowledge. Geometric changes in 2D intervals express motion, and kinematics based algorithms process results into 3D tracking information. Synthesized and experimental results in 2D and 3D motion estimates demonstrate negligible errors, validating the method for labeling and motion tracking of instruments in MIS videos. The conclusion underscores the proposed 2D segmentation technique's simplicity and computational efficiency, emphasizing its potential as direct plug-in for 3D visualization in instrument tracking and MIS practices. △ Less

Submitted 12 January, 2024; originally announced January 2024.

Lower Bounds for Set-Multilinear Branching Programs

Authors: Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

Abstract: In this paper, we prove super-polynomial lower bounds for the model of \emph{sum of ordered set-multilinear algebraic branching programs}, each with a possibly different ordering ($\sum \mathsf{smABP}$). Specifically, we give an explicit $nd$-variate polynomial of degree $d$ such that any $\sum \mathsf{smABP}$ computing it must have size $n^{ω(1)}$ for $d$ as low as $ω(\log n)$. Notably, this cons… ▽ More In this paper, we prove super-polynomial lower bounds for the model of \emph{sum of ordered set-multilinear algebraic branching programs}, each with a possibly different ordering ($\sum \mathsf{smABP}$). Specifically, we give an explicit $nd$-variate polynomial of degree $d$ such that any $\sum \mathsf{smABP}$ computing it must have size $n^{ω(1)}$ for $d$ as low as $ω(\log n)$. Notably, this constitutes the first such lower bound in the low degree regime. Moreover, for $d = \poly(n)$, we demonstrate an exponential lower bound. This result generalizes the seminal work of Nisan (STOC, 1991), which proved an exponential lower bound for a single ordered set-multilinear ABP. The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (to appear in TAMC, 2024), which showed that super-polynomial lower bounds against a sum of ordered set-multilinear branching programs -- for a polynomial of sufficiently low degree -- would imply super-polynomial lower bounds against general ABPs, thereby resolving Valiant's longstanding conjecture that the permanent polynomial can not be computed efficiently by ABPs. More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by $O(\log n/ \log \log n)$, then it would imply super-polynomial lower bounds against general ABPs. Our results strengthen the works of Arvind \& Raja (Chic. J. Theor. Comput. Sci., 2016) and Bhargav, Dwivedi \& Saxena (to appear in TAMC, 2024), as well as the works of Ramya \& Rao (Theor. Comput. Sci., 2020) and Ghoshal \& Rao (International Computer Science Symposium in Russia, 2021), each of which established lower bounds for related or restricted versions of this model. They also strongly answer a question from the former two, which asked to prove super-polynomial lower bounds for general $\sum \mathsf{smABP}$. △ Less

Submitted 19 February, 2024; v1 submitted 25 December, 2023; originally announced December 2023.

Independent Mechanism Analysis and the Manifold Hypothesis

Authors: Shubhangi Ghosh, Luigi Gresele, Julius von Kügelgen, Michel Besserve, Bernhard Schölkopf

Abstract: Independent Mechanism Analysis (IMA) seeks to address non-identifiability in nonlinear Independent Component Analysis (ICA) by assuming that the Jacobian of the mixing function has orthogonal columns. As typical in ICA, previous work focused on the case with an equal number of latent components and observed mixtures. Here, we extend IMA to settings with a larger number of mixtures that reside on a… ▽ More Independent Mechanism Analysis (IMA) seeks to address non-identifiability in nonlinear Independent Component Analysis (ICA) by assuming that the Jacobian of the mixing function has orthogonal columns. As typical in ICA, previous work focused on the case with an equal number of latent components and observed mixtures. Here, we extend IMA to settings with a larger number of mixtures that reside on a manifold embedded in a higher-dimensional than the latent space -- in line with the manifold hypothesis in representation learning. For this setting, we show that IMA still circumvents several non-identifiability issues, suggesting that it can also be a beneficial principle for higher-dimensional observations when the manifold hypothesis holds. Further, we prove that the IMA principle is approximately satisfied with high probability (increasing with the number of observed mixtures) when the directions along which the latent components influence the observations are chosen independently at random. This provides a new and rigorous statistical interpretation of IMA. △ Less

Submitted 20 December, 2023; originally announced December 2023.

Comments: 6 pages, Accepted at Neurips Causal Representation Learning 2023

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes

Authors: Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Abstract: In this note, we give very simple constructions of unique neighbor expander graphs starting from spectral or combinatorial expander graphs of mild expansion. These constructions and their analysis are simple variants of the constructions of LDPC error-correcting codes from expanders, given by Sipser-Spielman [SS96] (and Tanner [Tan81]), and their analysis. We also show how to obtain expanders with… ▽ More In this note, we give very simple constructions of unique neighbor expander graphs starting from spectral or combinatorial expander graphs of mild expansion. These constructions and their analysis are simple variants of the constructions of LDPC error-correcting codes from expanders, given by Sipser-Spielman [SS96] (and Tanner [Tan81]), and their analysis. We also show how to obtain expanders with many unique neighbors using similar ideas. There were many exciting results on this topic recently, starting with Asherov-Dinur [AD23] and Hsieh-McKenzie-Mohanty-Paredes [HMMP23], who gave a similar construction of unique neighbor expander graphs, but using more sophisticated ingredients (such as almost-Ramanujan graphs) and a more involved analysis. Subsequent beautiful works of Cohen-Roth-TaShma [CRT23] and Golowich [Gol23] gave even stronger objects (lossless expanders), but also using sophisticated ingredients. The main contribution of this work is that we get much more elementary constructions of unique neighbor expanders and with a simpler analysis. △ Less

Submitted 25 January, 2024; v1 submitted 29 October, 2023; originally announced October 2023.

Comments: Updated introduction, corrected minor typos

Evaluation of NR-Sidelink for Cooperative Industrial AGVs

Authors: Shubhangi Bhadauria, Klea Plaku, Yash Deshpande, Wolfgang Kellerer

Abstract: Industry 4.0 has brought to attention the need for a connected, flexible, and autonomous production environment. The New Radio (NR)-sidelink, which was introduced by the third-generation partnership project (3GPP) in Release 16, can be particularly helpful for factories that need to facilitate cooperative and close-range communication. Automated Guided Vehicles (AGVs) are important for material ha… ▽ More Industry 4.0 has brought to attention the need for a connected, flexible, and autonomous production environment. The New Radio (NR)-sidelink, which was introduced by the third-generation partnership project (3GPP) in Release 16, can be particularly helpful for factories that need to facilitate cooperative and close-range communication. Automated Guided Vehicles (AGVs) are important for material handling and carriage within these environments, and using NR-sidelink communication can further enhance their performance. An efficient resource allocation mechanism is required to ensure reliable communication and avoid interference between AGVs and other wireless systems in the factory using NR-sidelink. This work evaluates the 3GPP standardized resource allocation algorithm for NR-sidelink for a use case of cooperative carrying AGVs. We suggest further improvements that are tailored to the quality of service (QoS) requirements of an indoor factory communication scenario with cooperative AGVs.The use of NR-sidelink communication has the potential to help meet the QoS requirements for different Industry 4.0 use cases. This work can be a foundation for further improvements in NR-sidelink in 3GPP Release 18 and beyond. △ Less

Submitted 6 September, 2023; originally announced September 2023.

Investigation of Deep Learning-Based Filtered Density Function for Large Eddy Simulation of Turbulent Scalar Mixing

Authors: Shubhangi Bansude, Reza Sheikhi

Abstract: A filtered density function (FDF) model based on deep neural network (DNN), termed DNN-FDF, is introduced for large eddy simulation (LES) of turbulent flows involving conserved scalar transport. The primary objectives of this study are to develop the DNN-FDF models and evaluate their predictive capability in accounting for various filtered moments, including that of non-linear source terms. A syst… ▽ More A filtered density function (FDF) model based on deep neural network (DNN), termed DNN-FDF, is introduced for large eddy simulation (LES) of turbulent flows involving conserved scalar transport. The primary objectives of this study are to develop the DNN-FDF models and evaluate their predictive capability in accounting for various filtered moments, including that of non-linear source terms. A systematic approach is proposed to select DNN training sample size and architecture via learning curves to minimize bias and variance. Two DNN-FDF models are developed, one utilizing FDF data from Direct Numerical Simulations (DNS) of constant-density temporal mixing layer, and the other from zero-dimensional pairwise mixing stirred reactor simulations. The latter is particularly intended for cases where generating DNS data is computationally infeasible. DNN-FDF models are applied for LES of a variable-density temporal mixing layer. The accuracy and consistency of both DNN-FDF models are established by comparing their predicted filtered scalar moments with those of conventional LES, where moment transport equations are directly solved. The DNN-FDF models are shown to outperform a widely used presumed-FDF model, especially for multi-modal FDFs and higher variance values. Results are further assessed against DNS and the transported FDF method. The latter couples LES with Monte Carlo for mixture fraction FDF computation. Most importantly, the study shows that DNN-FDF models can accurately filter highly non-linear functions within variable-density flows, highlighting their potential for turbulent reacting flow simulations. Overall, the DNN-FDF approach is shown to offer an accurate yet computationally economical approach for describing turbulent scalar transport. △ Less

Submitted 29 September, 2023; v1 submitted 14 July, 2023; originally announced July 2023.

iPAL: A Machine Learning Based Smart Healthcare Framework For Automatic Diagnosis Of Attention Deficit/Hyperactivity Disorder (ADHD)

Authors: Abhishek Sharma, Arpit Jain, Shubhangi Sharma, Ashutosh Gupta, Prateek Jain, Saraju P. Mohanty

Abstract: ADHD is a prevalent disorder among the younger population. Standard evaluation techniques currently use evaluation forms, interviews with the patient, and more. However, its symptoms are similar to those of many other disorders like depression, conduct disorder, and oppositional defiant disorder, and these current diagnosis techniques are not very effective. Thus, a sophisticated computing model h… ▽ More ADHD is a prevalent disorder among the younger population. Standard evaluation techniques currently use evaluation forms, interviews with the patient, and more. However, its symptoms are similar to those of many other disorders like depression, conduct disorder, and oppositional defiant disorder, and these current diagnosis techniques are not very effective. Thus, a sophisticated computing model holds the potential to provide a promising diagnosis solution to this problem. This work attempts to explore methods to diagnose ADHD using combinations of multiple established machine learning techniques like neural networks and SVM models on the ADHD200 dataset and explore the field of neuroscience. In this work, multiclass classification is performed on phenotypic data using an SVM model. The better results have been analyzed on the phenotypic data compared to other supervised learning techniques like Logistic regression, KNN, AdaBoost, etc. In addition, neural networks have been implemented on functional connectivity from the MRI data of a sample of 40 subjects provided to achieve high accuracy without prior knowledge of neuroscience. It is combined with the phenotypic classifier using the ensemble technique to get a binary classifier. It is further trained and tested on 400 out of 824 subjects from the ADHD200 data set and achieved an accuracy of 92.5% for binary classification The training and testing accuracy has been achieved upto 99% using ensemble classifier. △ Less

Submitted 1 February, 2023; originally announced February 2023.

Probing the Robustness of Independent Mechanism Analysis for Representation Learning

Authors: Joanna Sliwa, Shubhangi Ghosh, Vincent Stimper, Luigi Gresele, Bernhard Schölkopf

Abstract: One aim of representation learning is to recover the original latent code that generated the data, a task which requires additional information or inductive biases. A recently proposed approach termed Independent Mechanism Analysis (IMA) postulates that each latent source should influence the observed mixtures independently, complementing standard nonlinear independent component analysis, and taki… ▽ More One aim of representation learning is to recover the original latent code that generated the data, a task which requires additional information or inductive biases. A recently proposed approach termed Independent Mechanism Analysis (IMA) postulates that each latent source should influence the observed mixtures independently, complementing standard nonlinear independent component analysis, and taking inspiration from the principle of independent causal mechanisms. While it was shown in theory and experiments that IMA helps recovering the true latents, the method's performance was so far only characterized when the modeling assumptions are exactly satisfied. Here, we test the method's robustness to violations of the underlying assumptions. We find that the benefits of IMA-based regularization for recovering the true sources extend to mixing functions with various degrees of violation of the IMA principle, while standard regularizers do not provide the same merits. Moreover, we show that unregularized maximum likelihood recovers mixing functions which systematically deviate from the IMA principle, and provide an argument elucidating the benefits of IMA-based regularization. △ Less

Submitted 13 July, 2022; originally announced July 2022.

Comments: 10 pages, 14 figures, UAI CRL 2022 final camera-ready version

Improved Low-Depth Set-Multilinear Circuit Lower Bounds

Authors: Deepanshu Kush, Shubhangi Saraf

Abstract: We prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $Δ$ set-multilinear formula computing $f$ has size at least $n^{Ω\left( n^{1/Δ}/Δ\right)}$. The hard polynomial $f$ comes from the class of Nisan-Wigderson… ▽ More We prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $Δ$ set-multilinear formula computing $f$ has size at least $n^{Ω\left( n^{1/Δ}/Δ\right)}$. The hard polynomial $f$ comes from the class of Nisan-Wigderson (NW) design-based polynomials. Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form $(\log n)^{Ω(Δn^{1/Δ})}$ was shown for the size of product-depth $Δ$ set-multilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as $f$. Moreover, our lower bounds are novel for any $Δ\geq 2$. For general set-multilinear formulas, a lower bound of the form $ n^{Ω(\log n)}$ was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form $(\log n)^{Ω(\log n)}$ for the size of general set-multilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form $n^{Ω(\log n)}$, albeit for the same polynomial $f$ in VNP (the NW polynomial). As observed by LST, if the same $n^{Ω(\log n)}$ size lower bounds for unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas. △ Less

Submitted 1 May, 2022; originally announced May 2022.

Comments: 14 pages, To appear in Computational Complexity Conference (CCC) 2022

On Pitfalls of Identifiability in Unsupervised Learning. A Note on: "Desiderata for Representation Learning: A Causal Perspective"

Authors: Shubhangi Ghosh, Luigi Gresele, Julius von Kügelgen, Michel Besserve, Bernhard Schölkopf

Abstract: Model identifiability is a desirable property in the context of unsupervised representation learning. In absence thereof, different models may be observationally indistinguishable while yielding representations that are nontrivially related to one another, thus making the recovery of a ground truth generative model fundamentally impossible, as often shown through suitably constructed counterexampl… ▽ More Model identifiability is a desirable property in the context of unsupervised representation learning. In absence thereof, different models may be observationally indistinguishable while yielding representations that are nontrivially related to one another, thus making the recovery of a ground truth generative model fundamentally impossible, as often shown through suitably constructed counterexamples. In this note, we discuss one such construction, illustrating a potential failure case of an identifiability result presented in "Desiderata for Representation Learning: A Causal Perspective" by Wang & Jordan (2021). The construction is based on the theory of nonlinear independent component analysis. We comment on implications of this and other counterexamples for identifiable representation learning. △ Less

Submitted 14 February, 2022; originally announced February 2022.

Comments: 5 pages, 1 figure

VerSaChI: Finding Statistically Significant Subgraph Matches using Chebyshev's Inequality

Authors: Shubhangi Agarwal, Sourav Dutta, Arnab Bhattacharya

Abstract: Approximate subgraph matching, which is an important primitive for many applications like question answering, community detection, and motif discovery, often involves large labeled graphs such as knowledge graphs, social networks, and protein sequences. Effective methods for extracting matching subgraphs, in terms of label and structural similarities to a query, should depict accuracy, computation… ▽ More Approximate subgraph matching, which is an important primitive for many applications like question answering, community detection, and motif discovery, often involves large labeled graphs such as knowledge graphs, social networks, and protein sequences. Effective methods for extracting matching subgraphs, in terms of label and structural similarities to a query, should depict accuracy, computational efficiency, and robustness to noise. In this paper, we propose VerSaChI for finding the top-k most similar subgraphs based on 2-hop label and structural overlap similarity with the query. The similarity is characterized using Chebyshev's inequality to compute the chi-square statistical significance for measuring the degree of matching of the subgraphs. Experiments on real-life graph datasets showcase significant improvements in terms of accuracy compared to state-of-the-art methods, as well as robustness to noise. △ Less

Submitted 18 August, 2021; originally announced August 2021.

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

Authors: Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Abstract: We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in random… ▽ More We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over the reals and the complex numbers for the following classes: (1) Set-multilinear depth-$3$ circuits of constant top fan-in $ΣΠΣ\{\sqcup_j X_j\}(k)$ circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for $d$ dimensional tensors for any $d$, but is interesting even for $d=3$. (2) Sums of powers of constantly many linear forms ($Σ\wedgeΣ$ circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. (3) Multilinear depth-3 circuits of constant top fan-in (multilinear $ΣΠΣ(k)$ circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09'). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of $ΣΠΣ(k)$ circuits that also work over large/infinite fields were for the setting when the top fan-in $k$ is at most $2$ (see Sinha 16' and Sinha 20'). △ Less

Submitted 4 May, 2021; originally announced May 2021.

MSC Class: 68Q25; 68Q32; 68Q06; 68W30; 68W40; 14N07 ACM Class: F.2.0; I.2.6

V2X in 3GPP Standardization: NR Sidelink in Rel-16 and Beyond

Authors: Mehdi Harounabadi, Dariush Mohammad Soleymani, Shubhangi Bhadauria, Martin Leyh, Elke Roth-Mandutz

Abstract: The 5G mobile network brings several new features that can be applied to existing and new applications. High reliability, low latency, and high data rate are some of the features which fulfill the requirements of vehicular networks. Vehicular networks aim to provide safety for road users and several additional advantages such as enhanced traffic efficiency and in-vehicle infotainment services. Thi… ▽ More The 5G mobile network brings several new features that can be applied to existing and new applications. High reliability, low latency, and high data rate are some of the features which fulfill the requirements of vehicular networks. Vehicular networks aim to provide safety for road users and several additional advantages such as enhanced traffic efficiency and in-vehicle infotainment services. This paper summarizes the most important aspects of NR-V2X, which is standardized by 3GPP, focusing on sidelink communication. The main part of this work belongs to the 3GPP Rel-16, which is the first 3GPP release for NR-V2X, and the work/study items of the future Rel-17 △ Less

Submitted 22 April, 2021; originally announced April 2021.

Addressing Purchase-Impression Gap through a Sequential Re-ranker

Authors: Shubhangi Tandon, Saratchandra Indrakanti, Amit Jaiswal, Svetlana Strunjas, Manojkumar Rangasamy Kannadasan

Abstract: Large scale eCommerce platforms such as eBay carry a wide variety of inventory and provide several buying choices to online shoppers. It is critical for eCommerce search engines to showcase in the top results the variety and selection of inventory available, specifically in the context of the various buying intents that may be associated with a search query. Search rankers are most commonly powere… ▽ More Large scale eCommerce platforms such as eBay carry a wide variety of inventory and provide several buying choices to online shoppers. It is critical for eCommerce search engines to showcase in the top results the variety and selection of inventory available, specifically in the context of the various buying intents that may be associated with a search query. Search rankers are most commonly powered by learning-to-rank models which learn the preference between items during training. However, they score items independent of other items at runtime. Although the items placed at top of the results by such scoring functions may be independently optimal, they can be sub-optimal as a set. This may lead to a mismatch between the ideal distribution of items in the top results vs what is actually impressed. In this paper, we present methods to address the purchase-impression gap observed in top search results on eCommerce sites. We establish the ideal distribution of items based on historic shopping patterns. We then present a sequential reranker that methodically reranks top search results produced by a conventional pointwise scoring ranker. The reranker produces a reordered list by sequentially selecting candidates trading off between their independent relevance and potential to address the purchase-impression gap by utilizing specially constructed features that capture impression distribution of items already added to a reranked list. The sequential reranker enables addressing purchase impression gap with respect to multiple item aspects. Early version of the reranker showed promising lifts in conversion and engagement metrics at eBay. Based on experiments on randomly sampled validation datasets, we observe that the reranking methodology presented produces around 10% reduction in purchase-impression gap at an average for the top 20 results, while making improvements to conversion metrics. △ Less

Submitted 27 October, 2020; originally announced October 2020.

GraphReach: Position-Aware Graph Neural Network using Reachability Estimations

Authors: Sunil Nishad, Shubhangi Agarwal, Arnab Bhattacharya, Sayan Ranu

Abstract: Majority of the existing graph neural networks (GNN) learn node embeddings that encode their local neighborhoods but not their positions. Consequently, two nodes that are vastly distant but located in similar local neighborhoods map to similar embeddings in those networks. This limitation prevents accurate performance in predictive tasks that rely on position information. In this paper, we develop… ▽ More Majority of the existing graph neural networks (GNN) learn node embeddings that encode their local neighborhoods but not their positions. Consequently, two nodes that are vastly distant but located in similar local neighborhoods map to similar embeddings in those networks. This limitation prevents accurate performance in predictive tasks that rely on position information. In this paper, we develop GraphReach, a position-aware inductive GNN that captures the global positions of nodes through reachability estimations with respect to a set of anchor nodes. The anchors are strategically selected so that reachability estimations across all the nodes are maximized. We show that this combinatorial anchor selection problem is NP-hard and, consequently, develop a greedy (1-1/e) approximation heuristic. Empirical evaluation against state-of-the-art GNN architectures reveal that GraphReach provides up to 40% relative improvement in accuracy. In addition, it is more robust to adversarial attacks. △ Less

Submitted 20 August, 2021; v1 submitted 19 August, 2020; originally announced August 2020.

Journal ref: IJCAI 2021

6G White Paper on Machine Learning in Wireless Communication Networks

Authors: Samad Ali, Walid Saad, Nandana Rajatheva, Kapseok Chang, Daniel Steinbach, Benjamin Sliwa, Christian Wietfeld, Kai Mei, Hamid Shiri, Hans-Jürgen Zepernick, Thi My Chinh Chu, Ijaz Ahmad, Jyrki Huusko, Jaakko Suutala, Shubhangi Bhadauria, Vimal Bhatia, Rangeet Mitra, Saidhiraj Amuru, Robert Abbas, Baohua Shao, Michele Capobianco, Guanghui Yu, Maelick Claes, Teemu Karvonen, Mingzhe Chen , et al. (2 additional authors not shown)

Abstract: The focus of this white paper is on machine learning (ML) in wireless communications. 6G wireless communication networks will be the backbone of the digital transformation of societies by providing ubiquitous, reliable, and near-instant wireless connectivity for humans and machines. Recent advances in ML research has led enable a wide range of novel technologies such as self-driving vehicles and v… ▽ More The focus of this white paper is on machine learning (ML) in wireless communications. 6G wireless communication networks will be the backbone of the digital transformation of societies by providing ubiquitous, reliable, and near-instant wireless connectivity for humans and machines. Recent advances in ML research has led enable a wide range of novel technologies such as self-driving vehicles and voice assistants. Such innovation is possible as a result of the availability of advanced ML models, large datasets, and high computational power. On the other hand, the ever-increasing demand for connectivity will require a lot of innovation in 6G wireless networks, and ML tools will play a major role in solving problems in the wireless domain. In this paper, we provide an overview of the vision of how ML will impact the wireless communication systems. We first give an overview of the ML methods that have the highest potential to be used in wireless networks. Then, we discuss the problems that can be solved by using ML in various layers of the network such as the physical layer, medium access layer, and application layer. Zero-touch optimization of wireless networks using ML is another interesting aspect that is discussed in this paper. Finally, at the end of each section, important research questions that the section aims to answer are presented. △ Less

Submitted 28 April, 2020; originally announced April 2020.

Influence of Neighborhood on the Preference of an Item in eCommerce Search

Authors: Saratchandra Indrakanti, Svetlana Strunjas, Shubhangi Tandon, Manojkumar Rangasamy Kannadasan

Abstract: Surfacing a ranked list of items for a search query to help buyers discover inventory and make purchase decisions is a critical problem in eCommerce search. Typically, items are independently predicted with a probability of sale with respect to a given search query. But in a dynamic marketplace like eBay, even for a single product, there are various different factors distinguishing one item from a… ▽ More Surfacing a ranked list of items for a search query to help buyers discover inventory and make purchase decisions is a critical problem in eCommerce search. Typically, items are independently predicted with a probability of sale with respect to a given search query. But in a dynamic marketplace like eBay, even for a single product, there are various different factors distinguishing one item from another which can influence the purchase decision for the user. Users have to make a purchase decision by considering all of these options. Majority of the existing learning to rank algorithms model the relative relevance between labeled items only at the loss functions like pairwise or list-wise losses. But they are limited to point-wise scoring functions where items are ranked independently based on the features of the item itself. In this paper, we study the influence of an item's neighborhood to its purchase decision. Here, we consider the neighborhood as the items ranked above and below the current item in search results. By adding delta features comparing items within a neighborhood and learning a ranking model, we are able to experimentally show that the new ranker with delta features outperforms our baseline ranker in terms of Mean Reciprocal Rank (MRR). The ranking models with proposed delta features result in $3-5\%$ improvement in MRR over the baseline model. We also study impact of different sizes for neighborhood. Experimental results show that neighborhood size $3$ perform the best based on MRR with an improvement of $4-5\%$ over the baseline model. △ Less

Submitted 17 October, 2019; v1 submitted 10 August, 2019; originally announced August 2019.

DEEP-FRI: Sampling outside the box improves soundness

Authors: Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Abstract: Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. We first show a sharp quantitative form of a theorem which says that if an affine space $U$ is $δ$-far in relative Hamming distance from a linear code $V$ - this is the worst-case assumption - then most el… ▽ More Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. We first show a sharp quantitative form of a theorem which says that if an affine space $U$ is $δ$-far in relative Hamming distance from a linear code $V$ - this is the worst-case assumption - then most elements of $U$ are almost $δ$-far from $V$ - this is the average case. This leads to an optimal analysis of the soundness of the FRI protocol of [Ben-Sasson, et.al., eprint 2018] for proving proximity to Reed-Solomon codes. To further improve soundness, we sample outside the box. We suggest a new protocol which asks a prover for values of a polynomial at points outside the domain of evaluation of the Reed-Solomon code. We call this technique Domain Extending for Eliminating Pretenders (DEEP). We use the DEEP technique to devise two new protocols: (1) An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. This soundness of the protocol improves upon that of the FRI protocol while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. (2) An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant $< 1/8$ to a constant arbitrarily close to $1$. △ Less

Submitted 28 March, 2019; originally announced March 2019.

Comments: 36 pages

Neural MultiVoice Models for Expressing Novel Personalities in Dialog

Authors: Shereen Oraby, Lena Reed, Sharath TS, Shubhangi Tandon, Marilyn Walker

Abstract: Natural language generators for task-oriented dialog should be able to vary the style of the output utterance while still effectively realizing the system dialog actions and their associated semantics. While the use of neural generation for training the response generation component of conversational agents promises to simplify the process of producing high quality responses in new domains, to our… ▽ More Natural language generators for task-oriented dialog should be able to vary the style of the output utterance while still effectively realizing the system dialog actions and their associated semantics. While the use of neural generation for training the response generation component of conversational agents promises to simplify the process of producing high quality responses in new domains, to our knowledge, there has been very little investigation of neural generators for task-oriented dialog that can vary their response style, and we know of no experiments on models that can generate responses that are different in style from those seen during training, while still maintain- ing semantic fidelity to the input meaning representation. Here, we show that a model that is trained to achieve a single stylis- tic personality target can produce outputs that combine stylistic targets. We carefully evaluate the multivoice outputs for both semantic fidelity and for similarities to and differences from the linguistic features that characterize the original training style. We show that contrary to our predictions, the learned models do not always simply interpolate model parameters, but rather produce styles that are distinct, and novel from the personalities they were trained on. △ Less

Submitted 5 September, 2018; originally announced September 2018.

Comments: Interspeech 2018

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

Authors: Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Abstract: In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ is a polynomial with $s$ monomials, with individual degrees of its variables bounded by $d$, then $f$ can be deterministically factored in time $s^{\mathrm{poly}(d) \log n}$. Prior to our work, the only efficient factoring algorithms known for this… ▽ More In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ is a polynomial with $s$ monomials, with individual degrees of its variables bounded by $d$, then $f$ can be deterministically factored in time $s^{\mathrm{poly}(d) \log n}$. Prior to our work, the only efficient factoring algorithms known for this class of polynomials were randomized, and other than for the cases of $d=1$ and $d=2$, only exponential time deterministic factoring algorithms were known. A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular we show if $f$ is an $s$-sparse polynomial in $n$ variables, with individual degrees of its variables bounded by $d$, then the sparsity of each factor of $f$ is bounded by $s^{O({d^2\log{n}})}$. This is the first nontrivial bound on factor sparsity for $d>2$. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Carathéodory's Theorem. Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials. △ Less

Submitted 20 August, 2018; originally announced August 2018.

MSC Class: 13P05; 12Y05 ACM Class: F.2.1

Arithmetic Circuits with Locally Low Algebraic Rank

Authors: Mrinal Kumar, Shubhangi Saraf

Abstract: In recent years, there has been a flurry of activity towards proving lower bounds for homogeneous depth-4 arithmetic circuits, which has brought us very close to statements that are known to imply $\textsf{VP} \neq \textsf{VNP}$. It is open if these techniques can go beyond homogeneity, and in this paper we make some progress in this direction by considering depth-4 circuits of low algebraic rank,… ▽ More In recent years, there has been a flurry of activity towards proving lower bounds for homogeneous depth-4 arithmetic circuits, which has brought us very close to statements that are known to imply $\textsf{VP} \neq \textsf{VNP}$. It is open if these techniques can go beyond homogeneity, and in this paper we make some progress in this direction by considering depth-4 circuits of low algebraic rank, which are a natural extension of homogeneous depth-4 circuits. A depth-4 circuit is a representation of an $N$-variate, degree-$n$ polynomial $P$ as \[ P = \sum_{i = 1}^T Q_{i1}\cdot Q_{i2}\cdot \cdots \cdot Q_{it} \; , \] where the $Q_{ij}$ are given by their monomial expansion. Homogeneity adds the constraint that for every $i \in [T]$, $\sum_{j} \operatorname{deg}(Q_{ij}) = n$. We study an extension, where, for every $i \in [T]$, the algebraic rank of the set $\{Q_{i1}, Q_{i2}, \ldots ,Q_{it}\}$ of polynomials is at most some parameter $k$. Already for $k = n$, these circuits are a generalization of the class of homogeneous depth-4 circuits, where in particular $t \leq n$ (and hence $k \leq n$). We study lower bounds and polynomial identity tests for such circuits and prove the following results. We show an $\exp{(Ω(\sqrt{n}\log N))}$ lower bound for such circuits for an explicit $N$ variate degree $n$ polynomial family when $k \leq n$. We also show quasipolynomial hitting sets when the degree of each $Q_{ij}$ and the $k$ are at most $\operatorname{poly}(\log n)$. A key technical ingredient of the proofs, which may be of independent interest, is a result which states that over any field of characteristic zero, up to a translation, every polynomial in a set of polynomials can be written as a function of the polynomials in a transcendence basis of the set. We combine this with methods based on shifted partial derivatives to obtain our final results. △ Less

Submitted 15 June, 2018; originally announced June 2018.

MSC Class: 68Q15; 68Q17 ACM Class: F.1.3

Journal ref: Theory of Computing 13(6):1-33, 2017

Controlling Personality-Based Stylistic Variation with Neural Natural Language Generators

Authors: Shereen Oraby, Lena Reed, Shubhangi Tandon, T. S. Sharath, Stephanie Lukin, Marilyn Walker

Abstract: Natural language generators for task-oriented dialogue must effectively realize system dialogue actions and their associated semantics. In many applications, it is also desirable for generators to control the style of an utterance. To date, work on task-oriented neural generation has primarily focused on semantic fidelity rather than achieving stylistic goals, while work on style has been done in… ▽ More Natural language generators for task-oriented dialogue must effectively realize system dialogue actions and their associated semantics. In many applications, it is also desirable for generators to control the style of an utterance. To date, work on task-oriented neural generation has primarily focused on semantic fidelity rather than achieving stylistic goals, while work on style has been done in contexts where it is difficult to measure content preservation. Here we present three different sequence-to-sequence models and carefully test how well they disentangle content and style. We use a statistical generator, Personage, to synthesize a new corpus of over 88,000 restaurant domain utterances whose style varies according to models of personality, giving us total control over both the semantic content and the stylistic variation in the training data. We then vary the amount of explicit stylistic supervision given to the three models. We show that our most explicit model can simultaneously achieve high fidelity to both semantic and stylistic goals: this model adds a context vector of 36 stylistic parameters as input to the hidden state of the encoder at each time step, showing the benefits of explicit stylistic supervision, even when the amount of training data is large. △ Less

Submitted 21 May, 2018; originally announced May 2018.

Comments: To appear at SIGDIAL 2018

Improved decoding of Folded Reed-Solomon and Multiplicity Codes

Authors: Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

Abstract: In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions of codes known to achieve list-decoding capacity; multivariate multipli… ▽ More In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions of codes known to achieve list-decoding capacity; multivariate multiplicity codes were the first constructions of high-rate locally correctable codes; and univariate multiplicity codes are also known to achieve list-decoding capacity. However, previous analyses of the error-correction properties of these codes did not yield optimal results. In particular, in the list-decoding setting, the guarantees on the list-sizes were polynomial in the block length, rather than constant; and for multivariate multiplicity codes, local list-decoding algorithms could not go beyond the Johnson bound. In this paper, we show that Folded Reed-Solomon codes and multiplicity codes are in fact better than previously known in the context of list-decoding and local list-decoding. More precisely, we first show that Folded RS codes achieve list-decoding capacity with constant list sizes, independent of the block length; and that high-rate univariate multiplicity codes can also be list-recovered with constant list sizes. Using our result on univariate multiplicity codes, we show that multivariate multiplicity codes are high-rate, locally list-recoverable codes. Finally, we show how to combine the above results with standard tools to obtain capacity achieving locally list decodable codes with query complexity significantly lower than was known before. △ Less

Submitted 3 May, 2018; originally announced May 2018.

Summarizing Dialogic Arguments from Social Media

Authors: Amita Misra, Shereen Oraby, Shubhangi Tandon, Sharath TS, Pranav Anand, Marilyn Walker

Abstract: Online argumentative dialog is a rich source of information on popular beliefs and opinions that could be useful to companies as well as governmental or public policy agencies. Compact, easy to read, summaries of these dialogues would thus be highly valuable. A priori, it is not even clear what form such a summary should take. Previous work on summarization has primarily focused on summarizing wri… ▽ More Online argumentative dialog is a rich source of information on popular beliefs and opinions that could be useful to companies as well as governmental or public policy agencies. Compact, easy to read, summaries of these dialogues would thus be highly valuable. A priori, it is not even clear what form such a summary should take. Previous work on summarization has primarily focused on summarizing written texts, where the notion of an abstract of the text is well defined. We collect gold standard training data consisting of five human summaries for each of 161 dialogues on the topics of Gay Marriage, Gun Control and Abortion. We present several different computational models aimed at identifying segments of the dialogues whose content should be used for the summary, using linguistic features and Word2vec features with both SVMs and Bidirectional LSTMs. We show that we can identify the most important arguments by using the dialog context with a best F-measure of 0.74 for gun control, 0.71 for gay marriage, and 0.67 for abortion. △ Less

Submitted 31 October, 2017; originally announced November 2017.

Comments: Proceedings of the 21th Workshop on the Semantics and Pragmatics of Dialogue (SemDial 2017)

A Dual Encoder Sequence to Sequence Model for Open-Domain Dialogue Modeling

Authors: Sharath T. S., Shubhangi Tandon, Ryan Bauer

Abstract: Ever since the successful application of sequence to sequence learning for neural machine translation systems, interest has surged in its applicability towards language generation in other problem domains. Recent work has investigated the use of these neural architectures towards modeling open-domain conversational dialogue, where it has been found that although these models are capable of learnin… ▽ More Ever since the successful application of sequence to sequence learning for neural machine translation systems, interest has surged in its applicability towards language generation in other problem domains. Recent work has investigated the use of these neural architectures towards modeling open-domain conversational dialogue, where it has been found that although these models are capable of learning a good distributional language model, dialogue coherence is still of concern. Unlike translation, conversation is much more a one-to-many mapping from utterance to a response, and it is even more pressing that the model be aware of the preceding flow of conversation. In this paper we propose to tackle this problem by introducing previous conversational context in terms of latent representations of dialogue acts over time. We inject the latent context representations into a sequence to sequence neural network in the form of dialog acts using a second encoder to enhance the quality and the coherence of the conversations generated. The main task of this research work is to show that adding latent variables that capture discourse relations does indeed result in more coherent responses when compared to conventional sequence to sequence models. △ Less

Submitted 28 October, 2017; originally announced October 2017.

Topic Based Sentiment Analysis Using Deep Learning

Authors: Sharath T. S., Shubhangi Tandon

Abstract: In this paper , we tackle Sentiment Analysis conditioned on a Topic in Twitter data using Deep Learning . We propose a 2-tier approach : In the first phase we create our own Word Embeddings and see that they do perform better than state-of-the-art embeddings when used with standard classifiers. We then perform inference on these embeddings to learn more about a word with respect to all the topics… ▽ More In this paper , we tackle Sentiment Analysis conditioned on a Topic in Twitter data using Deep Learning . We propose a 2-tier approach : In the first phase we create our own Word Embeddings and see that they do perform better than state-of-the-art embeddings when used with standard classifiers. We then perform inference on these embeddings to learn more about a word with respect to all the topics being considered, and also the top n-influencing words for each topic. In the second phase we use these embeddings to predict the sentiment of the tweet with respect to a given topic, and all other topics under discussion. △ Less

Submitted 28 October, 2017; originally announced October 2017.

Towards an algebraic natural proofs barrier via polynomial identity testing

Authors: Joshua A. Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

Abstract: We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under… ▽ More We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity. △ Less

Submitted 6 January, 2017; originally announced January 2017.

MSC Class: 68Q15; 68Q17; 68W30; 14Q20 ACM Class: F.1.3; F.2.2

On the number of ordinary lines determined by sets in complex space

Authors: Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf

Abstract: Kelly's theorem states that a set of $n$ points affinely spanning $\mathbb{C}^3$ must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least $3n/2$ ordinary lines, unless the configuration has $n-1$ points in a plane and one point outside the plane (in which case there are at least $n-1$ ordinary lin… ▽ More Kelly's theorem states that a set of $n$ points affinely spanning $\mathbb{C}^3$ must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least $3n/2$ ordinary lines, unless the configuration has $n-1$ points in a plane and one point outside the plane (in which case there are at least $n-1$ ordinary lines). In addition, when at most $2n/3$ points are contained in any plane, we prove a theorem giving stronger bounds that take advantage of the existence of lines with 4 and more points (in the spirit of Melchior's and Hirzebruch's inequalities). Furthermore, when the points span 4 or more dimensions, with at most $2n/3$ points contained in any three dimensional affine subspace, we show that there must be a quadratic number of ordinary lines. △ Less

Submitted 10 November, 2021; v1 submitted 26 November, 2016; originally announced November 2016.

Comments: Appeared in Discrete Comput. Geom. This version corrects some errors from the previous version, and clarifies the analysis

Journal ref: Discrete Comput Geom 61, 778-808 (2019)

Maximally Recoverable Codes for Grid-like Topologies

Authors: Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin

Abstract: The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Yet, the codes being deployed in practice are fairly short. In this work, we address what we view as the main coding theoretic barrier to deploying longer codes in storage: at large lengths, failures are not independent and correlated failures are inev… ▽ More The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Yet, the codes being deployed in practice are fairly short. In this work, we address what we view as the main coding theoretic barrier to deploying longer codes in storage: at large lengths, failures are not independent and correlated failures are inevitable. This motivates designing codes that allow quick data recovery even after large correlated failures, and which have efficient encoding and decoding. We propose that code design for distributed storage be viewed as a two-step process. The first step is choose a topology of the code, which incorporates knowledge about the correlated failures that need to be handled, and ensures local recovery from such failures. In the second step one specifies a code with the chosen topology by choosing coefficients from a finite field. In this step, one tries to balance reliability (which is better over larger fields) with encoding and decoding efficiency (which is better over smaller fields). This work initiates an in-depth study of this reliability/efficiency tradeoff. We consider the field-size needed for achieving maximal recoverability: the strongest reliability possible with a given topology. We propose a family of topologies called grid-like topologies which unify a number of topologies considered both in theory and practice, and prove a collection of results about maximally recoverable codes in such topologies including the first super-polynomial lower bound on the field size. △ Less

Submitted 20 September, 2016; v1 submitted 17 May, 2016; originally announced May 2016.

Sums of products of polynomials in few variables : lower bounds and polynomial identity testing

Authors: Mrinal Kumar, Shubhangi Saraf

Abstract: We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$ such that each $Q_{ij}$ is an arbitrary polynomial that depends on at most $s$ variables. We prove the following results. 1. Over fields of characteristic zero, for every constant $μ$ such that… ▽ More We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$ such that each $Q_{ij}$ is an arbitrary polynomial that depends on at most $s$ variables. We prove the following results. 1. Over fields of characteristic zero, for every constant $μ$ such that $0 \leq μ< 1$, we give an explicit family of polynomials $\{P_{N}\}$, where $P_{N}$ is of degree $n$ in $N = n^{O(1)}$ variables, such that any representation of the above type for $P_{N}$ with $s = N^μ$ requires $Td \geq n^{Ω(\sqrt{n})}$. This strengthens a recent result of Kayal and Saha [KS14a] which showed similar lower bounds for the model of sums of products of linear forms in few variables. It is known that any asymptotic improvement in the exponent of the lower bounds (even for $s = \sqrt{n}$) would separate VP and VNP[KS14a]. 2. We obtain a deterministic subexponential time blackbox polynomial identity testing (PIT) algorithm for circuits computed by the above model when $T$ and the individual degree of each variable in $P$ are at most $\log^{O(1)} N$ and $s \leq N^μ$ for any constant $μ< 1/2$. We get quasipolynomial running time when $s < \log^{O(1)} N$. The PIT algorithm is obtained by combining our lower bounds with the hardness-randomness tradeoffs developed in [DSY09, KI04]. To the best of our knowledge, this is the first nontrivial PIT algorithm for this model (even for the case $s=2$), and the first nontrivial PIT algorithm obtained from lower bounds for small depth circuits. △ Less

Submitted 23 April, 2015; originally announced April 2015.

High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Authors: Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

Abstract: In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant relative distance, and query complexity… ▽ More In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant relative distance, and query complexity $\exp(\tilde{O}(\sqrt{\log n}))$. Previously such codes were known to exist only with $Ω(n^β)$ query complexity (for constant $β> 0$), and there were several, quite different, constructions known. Our codes are based on a general distance-amplification method of Alon and Luby~\cite{AL96_codes}. We show that this method interacts well with local correctors and testers, and obtain our main results by applying it to suitably constructed LCCs and LTCs in the non-standard regime of \emph{sub-constant relative distance}. Along the way, we also construct LCCs and LTCs over large alphabets, with the same query complexity $\exp(\tilde{O}(\sqrt{\log n}))$, which additionally have the property of approaching the Singleton bound: they have almost the best-possible relationship between their rate and distance. This has the surprising consequence that asking for a large alphabet error-correcting code to further be an LCC or LTC with $\exp(\tilde{O}(\sqrt{\log n}))$ query complexity does not require any sacrifice in terms of rate and distance! Such a result was previously not known for any $o(n)$ query complexity. Our results on LCCs also immediately give locally-decodable codes (LDCs) with the same parameters. △ Less

Submitted 22 April, 2015; originally announced April 2015.