Arrow Research search

Author name cluster

Anne Condon

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.

10 papers
2 author rows

Possible papers

10

AIJ Journal 2011 Journal Article

Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions

  • Baharak Rastegari
  • Anne Condon
  • Kevin Leyton-Brown

In combinatorial auctions using VCG, a seller can sometimes increase revenue by dropping bidders. In this paper we investigate the extent to which this counterintuitive phenomenon can also occur under other deterministic, dominant-strategy combinatorial auction mechanisms. Our main result is that such failures of “revenue monotonicity” can occur under any such mechanism that is weakly maximal—meaning roughly that it chooses allocations that cannot be augmented to cause a losing bidder to win without hurting winning bidders—and that allows bidders to express arbitrary known single-minded preferences. We also give a set of other impossibility results as corollaries, concerning revenue when the set of goods changes, false-name-proofness, and the core. 1 1 We previously published a six-page preliminary version of our main result at a conference (Rastegari et al. , 2007) [24]. Among other differences, this work considered a very limited version of our weak maximality condition that can be understood as requiring Pareto efficiency with respect to bidder valuations (i. e. , ignoring payments).

Details DOI

TCS Journal 2009 Journal Article

Computational prediction of nucleic acid secondary structure: Methods, applications, and challenges

  • Anne Condon
  • Hosna Jabbari

RNA molecules are crucial in different levels of cellular function, ranging from translation and regulating genes to coding for proteins. Additionally, nucleic acids (RNA and DNA molecules) are designed for novel applications in biotechnology. Understanding the structure of a molecule is important in inferring its function, and computational methods for structure prediction have captured the interest of many researchers. Some functions of RNA molecules in cells, such as gene regulation, result from the binding of one RNA molecule to another, so-called target RNA molecule. This has led to recent interest in prediction of the secondary structure formed from interacting molecules. In this paper, we provide a brief overview of methods, applications, and challenges in computational prediction of nucleic acid secondary structure, both for single strands and for interacting strands.

Details DOI

TCS Journal 2004 Journal Article

Classifying RNA pseudoknotted structures

  • Anne Condon
  • Beth Davy
  • Baharak Rastegari
  • Shelly Zhao
  • Finbarr Tarrant

Computational prediction of the minimum free energy (mfe) secondary structure of an RNA molecule from its base sequence is valuable in understanding the structure and function of the molecule. Since the general problem of predicting pseudoknotted secondary structures is NP-hard, several algorithms have been proposed that find the mfe secondary structure from a restricted class of secondary structures. In this work, we order the algorithms by generality of the structure classes that they handle. We provide simple characterizations of the classes of structures handled by four algorithms, as well as linear time methods to test whether a given secondary structure is in three of these classes. We report on the percentage of biological structures from the PseudoBase and Gutell databases that are handled by these three algorithms.

Details DOI

AIJ Journal 2003 Journal Article

On the undecidability of probabilistic planning and related stochastic optimization problems

  • Omid Madani
  • Steve Hanks
  • Anne Condon

Automated planning, the problem of how an agent achieves a goal given a repertoire of actions, is one of the foundational and most widely studied problems in the AI literature. The original formulation of the problem makes strong assumptions regarding the agent's knowledge and control over the world, namely that its information is complete and correct, and that the results of its actions are deterministic and known. Recent research in planning under uncertainty has endeavored to relax these assumptions, providing formal and computation models wherein the agent has incomplete or noisy information about the world and has noisy sensors and effectors. This research has mainly taken one of two approaches: extend the classical planning paradigm to a semantics that admits uncertainty, or adopt another framework for approaching the problem, most commonly the Markov Decision Process (MDP) model. This paper presents a complexity analysis of planning under uncertainty. It begins with the “probabilistic classical planning” problem, showing that problem to be formally undecidable. This fundamental result is then applied to a broad class of stochastic optimization problems, in brief any problem statement where the agent (a) operates over an infinite or indefinite time horizon, and (b) has available only probabilistic information about the system's state. Undecidability is established for policy-existence problems for partially observable infinite-horizon Markov decision processes under discounted and undiscounted total reward models, average-reward models, and state-avoidance models. The results also apply to corresponding approximation problems with undiscounted objective functions. The paper answers a significant open question raised by Papadimitriou and Tsitsiklis [Math. Oper. Res. 12 (3) (1987) 441–450] about the complexity of infinite horizon POMDPs.

Details DOI

TCS Journal 2002 Journal Article

Strand design for biomolecular computation

  • Arwen Brenneman
  • Anne Condon

The design of DNA or RNA strands for DNA computations poses many new questions in algorithms and coding theory. DNA strand design also arises in use of molecular bar codes to manipulate and identify individual molecules in complex chemical libraries, and to attach molecules to DNA chips. We survey several formulations of the DNA strand design problem, along with results and open questions in this area.

Details DOI

FOCS Conference 1989 Conference Paper

On the Complexity of Space Bounded Interactive Proofs (Extended Abstract)

  • Anne Condon
  • Richard J. Lipton

Two results on interactive proof systems with two-way probabilistic finite-state verifiers are proved. The first is a lower bound on the power of such proof systems if they are not required to halt with high probability on rejected inputs: it is shown that they can accept any recursively enumerable language. The second is an upper bound on the power of interactive proof systems that halt with high probability on all inputs. The proof method for the lower bound also shows that the emptiness problem for one-way probabilistic finite-state machines is undecidable. In the proof of the upper bound some results of independent interest on the rate of convergence of time-varying Markov chains to their halting states are obtained. >

Details