Abstract: We study a new type of separation between quantum and classical communication complexity, a separation which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented
Abstract: Secure computation allows a set of mutually distrusting parties to compute a joint function of their private inputs such that the parties only learn the output of the functionality and nothing else about the inputs of th
Abstract: Ultra Large-scale Linear Programming refers to class of problems where number of linear inequality constraints grows exponentially w.r.t. the number of variables.
Abstract: Matroids are combinatorial objects that generalize the notion of linear independence. They have several applications in design and analysis of algorithms.
Abstract: An Algebraic Branching Program (ABP) is a layered graph where each edge is labeled by an affine linear form and the first and the last layer have one vertex each, called the “start” and the “end” vertex respectively.
