Computer Science and Engineering

Computer Science and Engineering

Recent Submissions

  • Das, Bireswar; Enduri, Murali Krishna; Misra, Neeldhara; Vinod Reddy, I. (Springer International Publishing, 2017)
    Structural parameterizations for hard problems have proven to be a promising venture for discovering scenarios where the problem is tractable. In particular, when a problem is already known to be polynomially solvable for ...
  • Garg, Dinesh; Kakkar, Vishal; Shevade, Shirish K.; Sundararajan, S. (Cornell University Library, 2016-12)
    AUC (Area under the ROC curve) is an important performance measure for applications where the data is highly imbalanced. Learning to maximize AUC performance is thus an important research problem. Using a max-margin based ...
  • Garg, Dinesh; Jain, Alankar; Borkar, Vivek (Springer Vienna, 2016-08)
    We consider the problem of inferring the source of a rumor in a given large network. We assume that the rumor propagates in the network through a discrete time susceptible-infected model. Input to our problem includes ...
  • Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod (Springer, 2016-07)
    The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism ...
  • Das, Bireswar; Scharpfenecker, Patrick; Toran, Jacobo (Elsevier, 2016-06)
    It is well-known that succinct encodings of computational problems – using circuits or formulas to encode large instances – generally result in an exponential complexity blow-up compared to their original complexity. We ...
  • Dey, Palash; Misra, Neeldhara (Cornell University Library, 2016-04)
    The Coalitional Manipulation problem has been studied extensively in the literature for many voting rules. However, most studies have focused on the complete information setting, wherein the manipulators know the votes of ...
  • Dey, Palash; Misra, Neeldhara (Cornell University Library, 2016-04)
    Eliciting the preferences of a set of agents over a set of alternatives is a problem of fundamental importance in social choice theory. Prior work on this problem has studied the query complexity of preference elicitation ...
  • Goyal, Navin; Gupta, Manoj (Cornell University Library, 2016-01)
    In their seminal paper [Sleator and Tarjan, J.ACM, 1985], the authors conjectured that the splay tree is dynamically optimal binary search tree (BST). In spite of decades of intensive research, the problem remains open. ...
  • Chierichetti, Flavio; Dasgupta, Anirban; Kumar, Ravi; Lattanzi, Silvio; Sarlos, Tamas (2016-04)
  • Moody, Dustin; Paul, Souradyuti; Smith-Tone, Daniel (De Gruyter, 2016-01)
    A hash function secure in the indifferentiability framework (TCC 2004) is able to resist all meaningful generic attacks. Such hash functions also play a crucial role in establishing the security of protocols that use them ...
  • Moody, Dustin; Paul, Souradyuti; Smith-Tone, Daniel (Springer, 2016-02)
    Indifferentiability security of a hash mode of operation guarantees the mode's resistance against all generic attacks. It is also useful to establish the security of protocols that use hash functions as random functions. ...
  • Vaish, Rohit; Misra, Neeldhara (EXPLORE, 2016-05)
  • Misra, Neeldhara (2016-06)
  • Dey, Palash; Misra, Neeldhara (New York Hilton Midtown, 2016-07)
  • Dey, Palash; Misra, Neeldhara (New York Hilton Midtown, 2016-07)
  • Chierichetti, Flavio; Das, Abhimanyu; Dasgupta, Anirban; Kumar, Ravi (IEEE, 2015-10-17)
    A set function on a ground set of size n is approximately modular if it satisfies every modularity requirement to within an additive error, approximate modularity is the set analog of approximate linearity. In this paper ...
  • Dey, Palash; Misra, Neeldhara; Narahari, Y. (Elsevier, 2016-02)
    In the Possible winner problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences ...
  • Vaish, Rohit; Misra, Neeldhara; Agarwal, Shivani; Blum, Avrim (AAMAS, 2016-05-09)
    Standard voting rules usually assume that the preferences of voters are provided in the form of complete rankings over a xed set of alternatives. This assumption does not hold in applications like recommendation ...
  • Tinna, Pallav; Karlapalem, Kamalakar (Society for Imaging Science and Technology, 2016-02-14)
    Interactive visualization and analysis of the class boundaries is important because it tells us how and why the classes differ. However, the problem of modeling the boundary of classes of arbitrary size, shape and density ...
  • Kalyanakrishnan, Shivaram; Misra, Neeldhara; Gopalan, Aditya (AAAI, 2016-02-12)

View more