Scheduling Algorithms for the Broadcast Delivery of Multimedia Products (2008)
Abstract Free bandwidth in television channels which is avail-able in the form of the Vertical Blanking Interval (VBI) is currently being utilized to broadcast programme informa-tion, HTML pages and...
1 Introduction Circuits, Pebbling and Expressibility (Extended Abstract) (2008)
We give characterizations of nondeterministic com-
A Combinatorial Algorithm for Pfaffians 1 (2008)
Meena Mahajan, P. R. Subramanya, V. Vinay
The Pfaffian of an oriented graph is closely linked to Perfect Matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfaffian and...
Arithmetic Circuits: A Chasm at Depth Four (2008)
We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized...
Hariharan, Ramesh, Mukund, Madhavan, Vinay, V
This volume contains the proceedings of the 28th international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), organized under the auspices of the...
Hariharan, Ramesh, Mukund, Madhavan, Vinay, V
This volume contains the proceedings of the 28th international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), organized under the auspices of the...
Logspace Verifiers, NC, and NP (Extended Abstract) (2007)
S.V. Lokam, M. Mahajan, Satyanarayana V. Lokam, Meena Mahajan, V. Vinay
) Satyanarayana V. Lokam 1 , Meena Mahajan 2 , V Vinay 3? 1 Department of Computer Science, The University of Chicago Chicago, IL 60637, U. S. A. . E-mail: satya@cs.uchicago.edu 2 The Institute of...
Hansen Peter, Bro Miltersen, V Vinay
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a #2
We show how to determine whether a given pattern p of length m occurs in a given text t of length n in ~ O(
Eric Allender, Michal Kouck Y, V Vinay
We extend the lower bound techniques of [14], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjasci's theorem from the Boolean setting to the...
Meena Mahajan, P. R. Subramanya, V. Vinay
Abstract. The Pfaffian of a graph is closely linked to Perfect Matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfaffian and...
Quantum Finite Automata and Weighted Automata (2007)
Rao, M. V. Panduranga, Vinay, V.
Quantum finite automata derive their strength by exploiting interference in complex valued probability amplitudes. Of particular interest is the 2-way model of Ambainis and Watrous that has both...
Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Vinay, V
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching pro-grams. We show that every function computed by a...
Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Vinay, V
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching pro-grams. We show that every function computed by a...
The combinatorial approach yields an NC algorithm for computing Pfaffians (2004)
Mahajan, Meena, Subramanya, PR, Vinay, V
The Pfaffian of an oriented graph is closely linked to perfect matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfaffian and...
Clustering Large Graphs via the Singular Value Decomposition (2004)
Drineas, P, Frieze, A, Kannan, R, Vempala, S, Vinay, V
We consider the problem of partitioning a set of m points in the n-dimensional Euclidean space into k clusters (usually m and n are variable, while k is fixed), so as to minimize the sum of squared...
The combinatorial approach yields an NC algorithm for computing Pfaffians (2004)
Mahajan, Meena, Subramanya, PR, Vinay, V
The Pfaffian of an oriented graph is closely linked to perfect matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfaffian and...
Clustering Large Graphs via the Singular Value Decomposition (2004)
P. Drineas, A. Frieze, R. Kannan, S. Vempala, V. Vinay
We consider the problem of partitioning a set of m points in the n-dimensional Euclidean space into k clusters (usually m and n are variable, while k is fixed), so as to minimize the sum of squared...
Clustering large graphs via the Singular Value Decomposition (2004)
P. Drineas, A. Frieze, R. Kannan, S. Vempala, V. Vinay
Abstract. We consider the problem of partitioning a set of m points in the n-dimensional Euclidean space into k clusters (usually m and n are variable, while k is fixed), so as to minimize the sum of...
This document in subdirectoryRS/02/50/ Circuits on Cylinders (2002)
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay, Copyright C, Kristoffer Arnsfelt Hansen, Peter Bro, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Time-space tradeoffs in the counting hierarchy (2001)
Eric Allender, Michal Kouck ´y, Detlef Ronneburger, Sambuddha Roy, V Vinay
We extend the lower bound techniques of [17], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjaˇsčiĭ’s theorem from the Boolean setting to...
String Matching in ${\tilde O}(\sqrt{n}+\sqrt{m})$ Quantum Time (2000)
We show how to determine whether a given pattern p of length m occurs in a given text t of length n in ${\tilde O}(\sqrt{n}+\sqrt{m})$\footnote{${\tilde O}$ allows for logarithmic factors in m and...
Scheduling Algorithms for the Broadcast Delivery of Multimedia Products (2000)
V. Vinay, Vinay Krithi Ramamritham
Free bandwidth in television channels which is available in the form of the Vertical Blanking Interval (VBI) is currently being utilized to broadcast programme information, HTML pages and closed...
Determinant: old algorithms, new insights (1999)
In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the coeffcients of...
Determinant: old algorithms, new insights (1999)
In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the coeffcients of...
Clustering in Large Graphs and Matrices (1999)
Drineas Alan Frieze, P. Drineas, Ravi Kannan, Santosh Vempala, V. Vinay
We consider the problem of dividing a set of m points in Euclidean n\Gammaspace into k clusters (m; n are variable while k is fixed), so as to minimize the sum of distances squared of each point to...
Clustering in Large Graphs and Matrices (1999)
P. Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, V. Vinay
We consider the problem of dividing a set of m points in Euclidean n\Gammaspace into k clusters (m; n are variable while k is fixed), so as to minimize the sum of distance squared of each point to...
Clustering in Large Graphs and Matrices (1999)
P. Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, V. Vinay
We consider the problem of dividing a set of m points in Euclidean n space into k clusters (m; n are variable while k is xed), so as to minimize the sum of distances squared of each point to its...
Circuits and Context-free Languages (1999)
Pierre Mckenzie, Klaus Reinhardt, V Vinay
Simpler proofs that DAuxPDA-TIME(polynomial) equals LOGDCFL and that SAC 1 equals LOGCFL are given which avoid Sudborough's multi-head automata [Sud78]. The first characterization of LOGDCFL in...
Clustering in Large Graphs and Matrices (1999)
P. Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, V. Vinay
We consider the problem of dividing a set of m points in Euclidean n-space into k clusters (m, n are variable while k is fixed), so as to minimize the sum of distances squared of each point to its...
A combinatorial algorithm for Pfaffians (1999)
Meena Bhaskar Mahajan, P R Subramanya, V Vinay
The Pfa#an of an oriented graph is closely linked to Perfect Matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfa#an and determinant...
Determinant: Old algorithms, new insights (1998)
Abstract. In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the...
Determinant: Old Algorithms, New Insights (1998)
In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the coefficients...
A combinatorial algorithm for the determinant (1997)
We show the first efficient combinatorial algorithm for the computation of the determinant. Hitherto, all (known) algorithms for determinant have been based on linear algebra. In contrast, our...
Determinant: Combinatorics, Algorithms, and Complexity (1997)
<F4.793e+05> We prove a new combinatorial characterization of the<F3.928e+05> determi-<F2.522e+05> Abstract-1<F3.928e+05><F4.793e+05> nant. The characterization yields a...
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds (1996)
Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay
We investigate the phenomenon of depth-reduction in commutative and non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of...
Algorithms for the optimal loading of recursive neural nets (1995)
Chandru, V, Dattasharma, A, Keerthi, SS, Sancheti, NK, Vinay, V
The authors address the problem of choosing synaptic weights in a recursive (Hopfield) neural network so as to “optimize�? the performance of the network on the recognition of binary strings. The...
Algorithms for the optimal loading of recursive neural nets (1995)
Chandru, V, Dattasharma, A, Keerthi, SS, Sancheti, NK, Vinay, V
The authors address the problem of choosing synaptic weights in a recursive (Hopfield) neural network so as to “optimize�? the performance of the network on the recognition of binary strings. The...
Algorithms for the optimal loading of recursive neural nets (1995)
V Chandru, A Dattasharma, S S Keerthi, N K Sancheti, V Vinay
We address the problem of choosing synaptic weights in a recursive (Hopfield) neural network so as to "optimize " the performance of the network on the recognition of binary...
Branching Rules for Satisfiability (1995)
Recent experience suggests that branching algorithms are among the most attractive for solving propositional satisfiability problems. A key factor in their success is the rule they use to decide on...
Counting Auxiliary Pushdown Automata and Semi-unbounded Arithmetic Circuits (1991)
We examine various counting measures on space bounded nondeterministic auxiliary pushdown machines. Hitherto, counting measures on nondeterministic time bounded [Val 79,KST 89] and space bounded [AJ...
Is BP.(+)P a probabilistic class? (1991)
The author shows a uniform circuit characterization of BP.⊕𝒫 without using probabilistic bits. The proof of the result is extremely simple, yet unknown. To the best of the author's knowledge,...
Counting Auxiliary Pushdown Automata and Semi-unbounded Arithmetic Circuits (1991)
We examine various counting measures on space bounded nondeterministic auxiliary pushdown machines. Hitherto, counting measures on nondeterministic time bounded [Val 79,KST 89] and space bounded [AJ...
Is BP.(+)P a probabilistic class? (1991)
The author shows a uniform circuit characterization of BP.⊕𝒫 without using probabilistic bits. The proof of the result is extremely simple, yet unknown. To the best of the author's knowledge,...
Circuits, Pebbling and Expressibility (1990)
Vinay, V, Venkateswaran, H, Madhavan, Veni CE
We give characterizations of nondeterministic complexity classes such as NP and PSPACE and the classes in the polynomial time hierarchy in the two person pebble game model [VT89]. These...
Two aspects of nondeterministic auxiliary stack automata (NAuxSA) are studied. The first is the expressibility of NAuxSA. More specifically, it is shown that the polynomial hierarchy can be...
Circuits, Pebbling and Expressibility (1990)
Vinay, V, Venkateswaran, H, Madhavan, Veni CE
We give characterizations of nondeterministic complexity classes such as NP and PSPACE and the classes in the polynomial time hierarchy in the two person pebble game model [VT89]. These...
Two aspects of nondeterministic auxiliary stack automata (NAuxSA) are studied. The first is the expressibility of NAuxSA. More specifically, it is shown that the polynomial hierarchy can be...
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay
We investigate the phenomenon of depth-reduction in commutativeand non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of...
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay
We investigate the phenomenon of depth-reduction in commutative and non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of...