Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > V:
A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

V
TR05-118 | 16th October 2005
Jin-Yi Cai, Vinay Choudhary

#### Valiant's Holant Theorem and Matchgate Tensors

We propose matchgate tensors as a natural and proper language
to develop Valiant's new theory of Holographic Algorithms.
We give a treatment of the central theorem in this theory---the Holant
Theorem---in terms of matchgate tensors.
Some generalizations are presented.

more >>>

TR04-003 | 22nd December 2003
Pascal Koiran

#### Valiant's model and the cost of computing integers

Let $\tau(k)$ be the minimum number of arithmetic operations
required to build the integer $k \in \N$ from the constant 1.
A sequence $x_k$ is said to be easy to compute'' if
there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$
for all $k \geq ... more >>> TR08-063 | 21st April 2008 Müller Moritz #### Valiant-Vazirani Lemmata for Various Logics We show analogues of a theorem due to Valiant and Vazirani for intractable parameterized complexity classes such as W[P], W[SAT] and the classes of the W-hierarchy as well as those of the A-hierarchy. We do so by proving a general logical'' version of it which may be of independent interest ... more >>> TR95-051 | 16th October 1995 Pascal Koiran #### VC Dimension in Circuit Complexity The main result of this paper is a Omega(n^{1/4}) lower bound on the size of a sigmoidal circuit computing a specific AC^0_2 function. This is the first lower bound for the computation model of sigmoidal circuits with unbounded weights. We also give upper and lower bounds for the ... more >>> TR95-055 | 24th November 1995 Marek Karpinski, Angus Macintyre #### VC Dimension of Sigmoidal and General Pfaffian Networks We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, that the VC Dimension of analog neural networks with the sigmoidal activation function$\sigma(y)=1/1+e^{-y}$... more >>> TR14-039 | 28th March 2014 Andrzej Lingas #### Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-) Revisions: 1 We observe that if we allow for the use of division and the floor function besides multiplication, addition and subtraction then we can compute the arithmetic convolution of two n-dimensional integer vectors in O(n) steps and perform the arithmetic matrix multiplication of two integer n times n matrices ... more >>> TR17-005 | 10th January 2017 Nir Bitansky #### Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs Revisions: 3 Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function's value$y$at any point$x$, can also generate a non-interactive proof$\pi$that$y$is correct (relative to so), without compromising pseudorandomness at other points. Being a natural primitive with ... more >>> TR14-086 | 11th July 2014 Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian #### Verifiable Stream Computation and Arthur–Merlin Communication In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling ... more >>> TR10-159 | 28th October 2010 Graham Cormode, Justin Thaler, Ke Yi #### Verifying Computations with Streaming Interactive Proofs Applications based on outsourcing computation require guarantees to the data owner that the desired computation has been performed correctly by the service provider. Methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a ... more >>> TR13-165 | 28th November 2013 Michael Walfish, Andrew Blumberg #### Verifying computations without reexecuting them: from theoretical possibility to near-practicality Revisions: 3 How can we trust results computed by a third party, or the integrity of data stored by such a party? This is a classic question in systems security, and it is particularly relevant in the context of cloud computing. Various solutions have been proposed that make assumptions about the class ... more >>> TR12-079 | 14th June 2012 Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer #### Verifying Proofs in Constant Depth In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>> TR15-036 | 17th February 2015 David Gajser #### Verifying whether One-Tape Turing Machines Run in Linear Time We discuss the following family of problems, parameterized by integers$C\geq 2$and$D\geq 1$: Does a given one-tape non-deterministic$q$-state Turing machine make at most$Cn+D$steps on all computations on all inputs of length$n$, for all$n$? Assuming a fixed tape and input alphabet, we show that ... more >>> TR01-094 | 3rd December 2001 Jonas Holmerin #### Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon We prove that Minimum vertex cover on 4-regular hyper-graphs (or in other words, hitting set where all sets have size exactly 4), is hard to approximate within 2 - \epsilon. We also prove that the maximization version, in which we are allowed to pick ... more >>> TR02-027 | 30th April 2002 Irit Dinur, Venkatesan Guruswami, Subhash Khot #### Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon) Given a$k$-uniform hypergraph, the E$k$-Vertex-Cover problem is to find a minimum subset of vertices that hits'' every edge. We show that for every integer$k \geq 5$, E$k$-Vertex-Cover is NP-hard to approximate within a factor of$(k-3-\epsilon)$, for an arbitrarily small constant$\epsilon > 0$. This almost matches the ... more >>> TR14-177 | 14th December 2014 Andreas Krebs, Klaus-Joern Lange, Michael Ludwig #### Visibly Counter Languages and Constant Depth Circuits We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+]. more >>> TR96-012 | 14th December 1995 Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson #### Visual Cryptography for General Access Structures A visual cryptography scheme for a set$\cal P $of$n$participants is a method to encode a secret image$SI$into$n$shadow images called shares, where each participant in$\cal P\$ receives one share. Certain qualified subsets of participants
can visually'' recover the secret image, but
other, ... more >>>

ISSN 1433-8092 | Imprint