Quantum query complexity is a widely studied model for understanding the capabilities and limitations of quantum computers. In this dissertation, we aim to better understand this complexity measure with respect to many natural models that are not well-studied. In particular, we are interested in the following concrete questions.

1) How powerful are quantum computers that could make multiple queries in parallel relative to analogous classical computers? 

2) Can there be a simple quantum algorithmic primitive that inherently combines quantum walks and quantum search? 

3) How are problems with constant-sized 1-certificates such as k-sum and triangle detection related with each other?