Arrow Research search

Author name cluster

V.S. Subrahmanian

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

29 papers
1 author row

Possible papers

29

AIJ Journal 2025 Journal Article

Defending a city from multi-drone attacks: A sequential Stackelberg security games approach

  • Dolev Mutzari
  • Tonmoay Deb
  • Cristian Molinaro
  • Andrea Pugliese
  • V.S. Subrahmanian
  • Sarit Kraus

To counter an imminent multi-drone attack on a city, defenders have deployed drones across the city. These drones must intercept/eliminate the threat, thus reducing potential damage from the attack. We model this as a Sequential Stackelberg Security Game, where the defender first commits to a mixed sequential defense strategy, and the attacker then best responds. We develop an efficient algorithm called S2D2, which outputs a defense strategy. We demonstrate the efficacy of S2D2 in extensive experiments on data from 80 real cities, improving the performance of the defender in comparison to greedy heuristics based on prior works. We prove that under some reasonable assumptions about the city structure, S2D2 outputs an approximate Strong Stackelberg Equilibrium (SSE) with a convenient structure.

Details DOI

AAAI Conference 2025 System Paper

GODDS: The Global Online Deepfake Detection System

  • Marco Postiglione
  • Julian Baldwin
  • Natalia Denisenko
  • Luke Fosdick
  • Chongyang Gao
  • Isabel Gortner
  • Chiara Pulice
  • Sarit Kraus

Fake audios, videos, and images are now proliferating widely. We developed GODDS, the Global Online Deepfake Detection system, for a specific user community, namely journalists. GODDS leverages an ensemble of deepfake detectors, along with a human in the loop, to provide a deepfake report on each submitted video/image/audio or VIA artifact submitted to the system. To date, VIA artifacts submitted by over 50 journalists from outlets such as the New York Times, Wall Street Journal, CNN, Agence France Press, and others have been run through GODDS. Unlike other deepfake detection systems, GODDS doesn't just focus on the submitted artifact but automatically derives context about the subject of the VIA artifact. Because context is not always available on all subjects, GODDS focuses on alleged deepfakes of high profile individuals, organizations, and events, where there is likely to be considerable contextual information.

PDF Details DOI

AAAI Conference 2023 System Paper

DUCK: A Drone-Urban Cyber-Defense Framework Based on Pareto-Optimal Deontic Logic Agents

  • Tonmoay Deb
  • Jürgen Dix
  • Mingi Jeong
  • Cristian Molinaro
  • Andrea Pugliese
  • Alberto Quattrini Li
  • Eugene Santos, Jr
  • V.S. Subrahmanian

Drone based terrorist attacks are increasing daily. It is not expected to be long before drones are used to carry out terror attacks in urban areas. We have developed the DUCK multi-agent testbed that security agencies can use to simulate drone-based attacks by diverse actors and develop a combination of surveillance camera, drone, and cyber defenses against them.

PDF Details DOI

IS Journal 2020 Journal Article

The Future of AI: AI's 10 To Watch

  • V.S. Subrahmanian

IEEE Intelligent Systems is promoting young and aspiring AI scientists via its biennial "AI's 10 to Watch" special section. The 2020 group consists of 10 young stars who have demonstrated outstanding AI achievements. In April 2020, IEEE Intelligent Systems called for nominations worldwide, with the requirement that nominees with doctorates must have received their PhDs since 2014. The selection committee, made up of IEEE Intelligent Systems editorial and advisory board members, finally had to select from a pool of 20+ highly competitive nominations. After a careful and detailed selection process, they voted on a short list of 10 top candidates. This final selection was based on scientific quality, reputation, impact, expert endorsement, and diversity. The vote for the final winners was unanimous. This year's 10 to Watch are listed

Details DOI

IS Journal 2017 Journal Article

The Golden Age of AI

  • V.S. Subrahmanian

Incoming editor-in-chief V. S. Subrahmanian describes the state of AI and his plans for the magazine.

Details DOI

AIJ Journal 2016 Journal Article

Diffusion centrality: A paradigm to maximize spread in social networks

  • Chanhyun Kang
  • Sarit Kraus
  • Cristian Molinaro
  • Francesca Spezzano
  • V.S. Subrahmanian

We propose Diffusion Centrality (DC) in which semantic aspects of a social network are used to characterize vertices that are influential in diffusing a property p. In contrast to classical centrality measures, diffusion centrality of vertices varies with the property p, and depends on the diffusion model describing how p spreads. We show that DC applies to most known diffusion models including tipping, cascade, and homophilic models. We present a hypergraph-based algorithm (HyperDC) with many optimizations to exactly compute DC. However, HyperDC does not scale well to huge social networks (millions of vertices, tens of millions of edges). For scaling, we develop methods to coarsen a network and propose a heuristic algorithm called “Coarsened Back and Forth” (CBAF) to compute the top-k vertices (having the highest diffusion centrality). We report on experiments comparing DC with classical centrality measures in terms of runtime and the “spread” achieved by the k most central vertices (using 7 real-world social networks and 3 different diffusion models). Our experiments show that DC produces higher quality results and is comparable to several centrality measures in terms of runtime.

Details DOI

IS Journal 2015 Journal Article

Saving rhinos with predictive analytics

  • Noseong Park
  • Edoardo Serra
  • V.S. Subrahmanian

This article, the first entry in the new Predictive Analytics column, looks at the problem of animal poaching. The authors describe their Anti-Poaching Engine system, which builds on behavior models of both rhinos and poachers to protect as many animals as possible.

Details DOI

IS Journal 2014 Journal Article

Behavior Informatics: A New Perspective

  • Longbing Cao
  • Thorsten Joachims
  • Can Wang
  • Eric Gaussier
  • Jinjiu Li
  • Yuming Ou
  • Dan Luo
  • Reza Zafarani

This installment of Trends & Controversies provides an array of perspectives on the latest research in behavior informatics. Longbing Cao introduces the work in "Behavior Informatics: A New Perspective. " Then, in "Behavior Computing, " Longbing Cao and Thorsten Joachims provide a basic overview of the topic. Next is "Coupled Behavior Representation, Modeling, Analysis, and Reasoning" by Can Wang, Longbing Cao, Eric Gaussier, Jinjiu Li, Yuming Ou, and Dan Luo. The fourth article is "Behavior Analysis in Social Media, " by Reza Zafarani and Huan Liu. The fifth article is "Group Recommendation and Behavior, " by Guandong Xu and Zhiang Wu. Gabriella Pasi wrote the sixth article, "Web Search and Behavior. " The seventh article, "Behaviors of IPTV Users, " is by Ya Zhang, Xiaokang Yang, and Hongyuan Zha. Finally, "Should Behavioral Models of Terror Groups Be Disclosed? " is by Edoardo Serra and V. S. Subrahmanian.

Details DOI

AIJ Journal 2010 Journal Article

An AGM-style belief revision mechanism for probabilistic spatio-temporal logics

  • John Grant
  • Francesco Parisi
  • Austin Parker
  • V.S. Subrahmanian

There is now extensive interest in reasoning about moving objects. A probabilistic spatio-temporal (PST) knowledge base (KB) contains atomic statements of the form “Object o is/was/will be in region r at time t with probability in the interval [ ℓ, u ] ”. In this paper, we study mechanisms for belief revision in PST KBs. We propose multiple methods for revising PST KBs. These methods involve finding maximally consistent subsets and maximal cardinality consistent subsets. In addition, there may be applications where the user has doubts about the accuracy of the spatial information, or the temporal aspects, or about the ability to recognize objects in such statements. We study belief revision mechanisms that allow changes to the KB in each of these three components. Finally, there may be doubts about the assignment of probabilities in the KB. Allowing changes to the probability of statements in the KB yields another belief revision mechanism. Each of these belief revision methods may be epistemically desirable for some applications, but not for others. We show that some of these approaches cannot satisfy AGM-style axioms for belief revision under certain conditions. We also perform a detailed complexity analysis of each of these approaches. Simply put, all belief revision methods proposed that satisfy AGM-style axioms turn out to be intractable with the exception of the method that revises beliefs by changing the probabilities (minimally) in the KB. We also propose two hybrids of these basic approaches to revision and analyze the complexity of these hybrid methods.

Details DOI

AIJ Journal 2009 Journal Article

Computing the fault tolerance of multi-agent deployment

  • Yingqian Zhang
  • Efrat Manisterski
  • Sarit Kraus
  • V.S. Subrahmanian
  • David Peleg

A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i. e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i. e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment—these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities—these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.

Details DOI

IS Journal 2008 Journal Article

AVA: Adjective-Verb-Adverb Combinations for Sentiment Analysis

  • V.S. Subrahmanian
  • Diego Reforgiato

Most research on determining the strength of subjective expressions in a sentence or document uses single, specific parts of speech such as adjectives, adverbs, or verbs. To date, almost no research covers the development of a single comprehensive framework in which we can analyze sentiment that takes all three into account. The authors propose the AVA (adjective verb adverb) framework for identifying opinions on any given topic. In AVA, a user can select any topic t of interest and any document d. AVA will return a score that d expresses topic t. The score is expressed on a –1 (maximally negative) to +1 (maximally positive) scale.

Details DOI

IS Journal 2008 Journal Article

CONVEX: Similarity-Based Algorithms for Forecasting Group Behavior

  • V. Martinez
  • G.I. Simari
  • A. Sliva
  • V.S. Subrahmanian

A proposed framework for predicting a group's behavior associates two vectors with that group. The context vector tracks aspects of the environment in which the group functions; the action vector tracks the group's previous actions. Given a set of past behaviors consisting of a pair of these vectors and given a query context vector, the goal is to predict the associated action vector. To achieve this goal, two families of algorithms employ vector similarity. CONVEXk _NN algorithms use k-nearest neighbors in high-dimensional metric spaces; CONVEXMerge algorithms look at linear combinations of distances of the query vector from context vectors. Compared to past prediction algorithms, these algorithms are extremely fast. Moreover, experiments on real-world data sets show that the algorithms are highly accurate, predicting actions with well over 95-percent accuracy.

Details DOI

IS Journal 2007 Journal Article

CARA: A Cultural-Reasoning Architecture

  • V.S. Subrahmanian
  • Massimiliano Albanese
  • Maria Vanina Martinez
  • Dana Nau
  • Diego Reforgiato
  • Gerardo I. Simari
  • Amy Sliva
  • Jonathan Wilkenfeld

There's a constant need to reason about diverse cultures all over the world. Past cultural-reasoning research has focused primarily on techniques to organize, catalog, and reason about cultural and historical artifacts of the kind typically stored in a museum. This is extremely valuable. However, the term "cultural reasoning" as we use it in the previous examples (and in this article) focuses on understanding how different cultural groups today make decisions and what factors those decisions are based on. An architecture that supports cultural reasoning should, for example, be able to pinpoint characteristics that differentiate organizations engaging political action within legitimate frameworks from those engaging in violence and terror. Key in all this is that cultural reasoning must go hand in hand with environmental reasoning. We believe that any architecture to support cultural reasoning about a given group, political entity, business, or religious organization should contain these components: 1) a semantic Web extraction engine to elicit data about the organization, 2) an opinion-mining engine that captures the organization's opinions, 3) an algorithm to correlate environmental variables with actions that the organization takes, and 4) a simulation or game environment within which analysts and users can see what the organization has done and what it might do in hypothetical situations

Details DOI

AIJ Journal 2001 Journal Article

Temporal agent programs

  • Jürgen Dix
  • Sarit Kraus
  • V.S. Subrahmanian

The “agent program” framework introduced by Eiter, Subrahmanian and Pick [Artificial Intelligence 108 (1–2) (1999) 179], supports developing agents on top of arbitrary legacy code. Such agents are continuously engaged in an “eventoccurs→think→act→eventoccurs…” cycle. However, this framework has two major limitations: (1) all actions are assumed to have no duration, and (2) all actions are taken now, but cannot be scheduled for the future. In this paper, we present the concept of a “temporal agent program” (tap for short) and show that using taps, it is possible to build agents on top of legacy code that can reason about the past and about the future, and that can make temporal commitments for the future now. We develop a formal semantics for such agents, extending the concept of a status set proposed by Eiter et al. , and develop algorithms to compute the status sets associated with temporal agent programs. Last, but not least, we show how taps support the decision making of collaborative agents.

Details DOI

AIJ Journal 2000 Journal Article

Heterogeneous active agents, III: Polynomially implementable agents

  • Thomas Eiter
  • V.S. Subrahmanian
  • T.J. Rogers

In “Heterogeneous active agents, I” (Eiter et al. , 1999), two of the authors have introduced techniques to build agents on top of arbitrary data structures, and to “agentize” new/existing programs. They provided a series of successively more sophisticated semantics for such agent systems, and showed that as these semantics become epistemically more desirable, a computational price may need to be paid. In this paper, we identify a class of agents that are called weakly regular—this is done by first identifying a fragment of agent programs (Eiter et al. , 1999) called weakly regular agent programs (WRAPs for short). It is shown that WRAPs are definable via three parameters—checking for a property called “safety”, checking for a property called “conflict-freedom” and checking for a “deontic stratifiability” property. Algorithms for each of these are developed. A weakly regular agent is then defined in terms of these concepts, and a regular agent is one that satisfies an additional boundedness property. We then describe a polynomial algorithm that computes (under suitable assumptions) the reasonable status set semantics of regular agents—this semantics was identified by Eiter et al. (1999) as being epistemically most desirable. Though this semantics is coNP-complete for arbitrary agent programs (Eiter and Subrahmanian, 1999), it is polynomially computable via our algorithm for regular agents. Finally, we describe our implementation architecture and provide details of how we have implemented RAPs, together with experimental results.

Details DOI

AIJ Journal 1999 Journal Article

Heterogeneous active agents, I: Semantics

  • Thomas Eiter
  • V.S. Subrahmanian
  • George Pick

Over the years, many different agent programming languages have been proposed. In this paper, we propose a concept called Agent Programs using which, the way an agent should act in various situations can be declaratively specified by the creator of that agent. Agent Programs may be built on top of arbitrary pieces of software code and may be used to specify what an agent is obliged to do, what an agent may do, and what an agent may not do. In this paper, we define several successively more sophisticated and epistemically satisfying declarative semantics for agent programs. We further show that agent programs cleanly extend well understood semantics for logic programs, and thus are clearly linked to existing results on logic programming and nonmonotonic reasoning.

Details DOI

AIJ Journal 1999 Journal Article

Heterogeneous active agents, II: Algorithms and complexity

  • Thomas Eiter
  • V.S. Subrahmanian

In Part I of this series of papers, we developed a language called Agent Programs for defining the operational behavior of software agents and defined a set of successively more satisfying (epistemically) semantics for such agent programs. In Part II of this series of papers, we study the computation price to be paid (in terms of complexity) for these epistemic desiderata. In particular, we develop algorithms for the above semantics, and describe results on their computational complexity. We show that (surprisingly) the reasonable status set semantics is the easiest to compute of the semantics proposed.

Details DOI

TCS Journal 1997 Journal Article

Annotated nonmonotonic rule systems

  • A. Nerode
  • J.B. Remmel
  • V.S. Subrahmanian

Annotated logics were proposed by Subrahmanian as a unified paradigm for representing a wide variety of reasoning tasks including reasoning with uncertainty within a single theoretical framework. Subsequently, Marek, Nerode and Remmel have shown how to provide nonmonotonic extensions of arbitrary languages through their notion of a nonmonotonic rule systems. The primary aim of this paper is to define annotated nonmonotonic rule systems which merge these two frameworks into a general purpose nonmonotonic reasoning framework over arbitrary multiple-valued logics. We then show how Reiter's normal default theories may be generalized to the framework of annotated nonmonotonic rule systems.

Details DOI

TCS Journal 1996 Journal Article

Computing minimal models by partial instantiation

  • Vadim Kagan
  • Anil Nerode
  • V.S. Subrahmanian

Unlike sets of definite Horn clauses, logic programs with disjunctions of atoms in clause heads are often interpreted in terms of minimal models. It is also well known that the minimal models of logic programs are closely related to the so-called stable models of logic programs with nonmonotonic negation in clause bodies, as well as to circumscription. Methods to compute minimal models of logic programs are becoming increasingly important as an intermediate step in the computation of structures associated with nonmonotonic logic programs. However, to date, all these techniques have been restricted to the case of propositional logic programs which means that an ordinary disjunctive logic program must be “grounded out” prior to computation. Grounding out in this manner leads to a combinatorial explosion in the number of clauses, and hence, is unacceptable. In this paper, we show how, given any method M which correctly computes the set of minimal models of a propositional logic program, we can develop a strategy to compute truth in a minimal model of a disjunctive logic program P. The novel feature of our method is that it works on an “instantiate-by-need” basis, and thus avoids unnecessary grounding.

Details DOI

AIJ Journal 1995 Journal Article

Complexity, decidability and undecidability results for domain-independent planning

  • Kutluhan Erol
  • Dana S. Nau
  • V.S. Subrahmanian

In this paper, we examine how the complexity of domain-independent planning with STRIPS-style operators depends on the nature of the planning operators. We show conditions under which planning is decidable and undecidable. Our results on this topic solve an open problem posed by Chapman (1987), and clear up some difficulties with his undecidability theorems. For those cases where planning is decidable, we explain how the time complexity varies depending on a wide variety of conditions: • • whether or not function symbols are allowed; • • whether or not delete lists are allowed; • • whether or not negative preconditions are allowed; • • whether or not the predicates are restricted to be propositional (i. e. , 0-ary); • • whether the planning operators are given as part of the input to the planning problem, or instead are fixed in advance. • • whether or not the operators can have conditional effects.

Details DOI

I&C Journal 1995 Journal Article

Computing Circumscriptive Databases

  • A. Nerode
  • R.T. Ng
  • V.S. Subrahmanian

Though circumscription was introduced by McCarthy over a decade ago, there has been relatively little work on algorithms for computing circumscriptive databases. In this paper, we develop algorithms to compute the preferred models of circumscriptive databases at compile-time using mixed integer linear programming techniques. Two advantages of this (bottom-up) approach are that it makes efficient re-use of previous computations and it provides much faster run-time performance. Some other advantages of using linear programming to automate deduction at compile time are that its re-optimization facilities elegantly accommodate database updates and also that it leads to a completely declarative formulation in which ordering of rules and literals in rule bodies plays no real role. Finally, we plan to use a standard relational database system as our run-time environment; this should yield relatively fast run-time processing, and provide a more expressive query language in which aggregates and the like can be expressed easily.

Details DOI

I&C Journal 1994 Journal Article

Stable Semantics for Probabilistic Deductive Databases

  • R. Ng
  • V.S. Subrahmanian

In this paper we study the semantics of non-monotonic negation in probabilistic deductive databases. Based on the stable semantics for classical logic programming, we examine three natural notions of stability: stable formula functions, stable families of probabilistic interpretations, and stable probabilistic models. We show that stable formula functions are minimal fixpoints of operators associated with probabilistic logic programs. We also prove that each member in a stable family of probabilistic interpretations is a probabilistic model of the program. Then we show that stable formula functions and stable families behave as duals of each other, tying together elegantly the fixpoint and model theories for probabilistic logic programs with negation. Furthermore, since a probabilistic logic program may not necessarily have a stable family of probabilistic interpretations, we provide a stable class semantics for such programs. Finally, we investigate the notion of stable probabilistic model. We show that this notion, though natural, is too weak in the probabilistic framework.

Details DOI

TCS Journal 1992 Journal Article

Paraconsistent disjunctive deductive databases

  • V.S. Subrahmanian

Databases and knowledge bases could be inconsistent in many ways. The semantical characterization of deductive databases that contain disjunctive or indefinite information has been investigated by Minker and his co-workers (1982, 1987, 1988) and by Henschen and his co-workers (1985, 1988). In both cases, there is one salient feature: the databases are assumed to consist of sentences of the form: A 1 ∨ ⋯ ∨, A n ← B 1&⋯&Bm, where each Ai and each Bj is an atom and n⩾ 1. Thus, the database is implicitly assumed to be consistent (it is easy to construct a model for any set of such formulas). What we study here is a method for reasoning about such databases when they are not necessarily consistent. Intuitively, this occurs when the Ai 's are restricted not just to atomic formulas, but also to negated atoms. We use the device of annotated atoms introduced by Blair and Subrahmanian (1987, 1988) to achieve this effect. Our semantics is closely related to the existing work of Newton da Costa (1974–1987), whose pioneering work on paraconsistency provides the semantical basis for our formal development.

Details DOI

I&C Journal 1992 Journal Article

Probabilistic logic programming

  • Raymond Ng
  • V.S. Subrahmanian

Of all scientific investigations into reasoning with uncertainty and chance, probability theory is perhaps the best understood paradigm. Nevertheless, all studies conducted thus far into the semantics of quantitative logic programming have restricted themselves to non-probabilistic semantic characterizations. In this paper, we take a few steps towards rectifying this situation. We define a logic programming language that is syntactically similar to the annotated logics of Blair and Subrahmanian (Theoret. Comput. Sci. 68 (1987), 35–54; J. Non-Classical Logic 5 (1988), 45–73) but in which the truth values are interpreted probabilistically. A probabilistic model theory and fixpoint theory is developed for such programs. This probabilistic model theory satisfies the requirements proposed by Fenstad (in “Studies in Inductive Logic and Probabilities” (R. C. Jeffrey, Ed.), Vol. 2, pp. 251–262, Univ. of California Press, Berkeley, 1980) for a function to be called probabilistic. The logical treatment of probabilities is complicated by two facts: first, that the connectives cannot be interpreted truth-functionally when truth values are regarded as probabilities; second, that negation-free definite-clause-like sentences can be inconsistent when interpreted probabilistically. We address these issues here and propose a formalism for probabilistic reasoning in logic programming. To our knowledge, this is the first probabilistic characterization of logic programming semantics.

Details DOI

TCS Journal 1992 Journal Article

The relationship between stable, supported, default and autoepistemic semantics for general logic programs

  • W. Marek
  • V.S. Subrahmanian

We investigate the relationship between various alternative semantics for logic programming, viz. the stable model semantics of Gelfond and Lifschitz (1988), the supported model semantics as developed by Apt, Blair and Walker (1988), autoepistemic translations (cf. Moore (1985)) of general logic programs and default translations of general logic programs, Reiter (1980).

Details DOI

TCS Journal 1989 Journal Article

Paraconsistent logic programming

  • Howard A. Blair
  • V.S. Subrahmanian

This paper makes two contributions. First, we give a semantics for sets of clauses of the syntactic form L0 ⇍ L1 &⋯& Ln where each Li is a literal. We call such clauses generally Horn clauses. Any such endeavour has to give a coherent, formal treatment of inconsistency (in the sense of two-valued logic). Thus, as a second contribution, we give a robust semantics for generally Horn programs that allows us to “make sense” of sets of generally Horn clauses that are inconsistent (in the two-valued logic sense). This applies to the design of very large knowledge bases where inconsistent information is often present.

Details DOI

AIIM Journal 1989 Journal Article

Paraconsistent logics as a formalism for reasoning about inconsistent knowledge bases

  • Newton C.A. da Costa
  • V.S. Subrahmanian

Inconsistency is a natural phenomenon of the world. Thus, we need methods to reason about systems that may be inconsistent. Paraconsistent logics are a family of logics proposed initially by da Costa [3, 4, 5, 6] as a framework for reasoning in the presence of inconsistency. In this paper, we discuss various alternative schemes for paraconsistent reasoning and show how it applies to the design of large knowledge bases and databases in expert systems where incosistent information may often be present.

Details DOI
v2026.09.13