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

__
TR04-003
| 22nd December 2003
__

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

__
TR08-063
| 21st April 2008
__

MÃ¼ller Moritz#### Valiant-Vazirani Lemmata for Various Logics

__
TR19-121
| 17th September 2019
__

Alexander A. Sherstov, Justin Thaler#### Vanishing-Error Approximate Degree and QMA Complexity

__
TR18-135
| 31st July 2018
__

Prasad Chaugule, Nutan Limaye, Aditya Varre#### Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

Revisions: 1

__
TR95-051
| 16th October 1995
__

Pascal Koiran#### VC Dimension in Circuit Complexity

__
TR95-055
| 24th November 1995
__

Marek Karpinski, Angus Macintyre#### VC Dimension of Sigmoidal and General Pfaffian Networks

__
TR14-039
| 28th March 2014
__

Andrzej Lingas#### Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-)

Revisions: 1

__
TR17-005
| 10th January 2017
__

Nir Bitansky#### Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

Revisions: 3

__
TR14-086
| 11th July 2014
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### Verifiable Stream Computation and Arthurâ€“Merlin Communication

__
TR10-159
| 28th October 2010
__

Graham Cormode, Justin Thaler, Ke Yi#### Verifying Computations with Streaming Interactive Proofs

__
TR13-165
| 28th November 2013
__

Michael Walfish, Andrew Blumberg#### Verifying computations without reexecuting them: from theoretical possibility to near-practicality

Revisions: 3

__
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

__
TR15-036
| 17th February 2015
__

David Gajser#### Verifying whether One-Tape Turing Machines Run in Linear Time

__
TR01-094
| 3rd December 2001
__

Jonas Holmerin#### Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon

__
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)

__
TR14-177
| 14th December 2014
__

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig#### Visibly Counter Languages and Constant Depth Circuits

__
TR96-012
| 14th December 1995
__

Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson#### Visual Cryptography for General Access Structures

Jin-Yi Cai, Vinay Choudhary

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.

Pascal Koiran

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 >>>

MÃ¼ller Moritz

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

Alexander A. Sherstov, Justin Thaler

The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing ... more >>>

Prasad Chaugule, Nutan Limaye, Aditya Varre

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>

Pascal Koiran

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 >>>

Marek Karpinski, Angus Macintyre

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 >>>

Andrzej Lingas

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 >>>

Nir Bitansky

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 >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

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 >>>

Graham Cormode, Justin Thaler, Ke Yi

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 >>>

Michael Walfish, Andrew Blumberg

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 >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

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 >>>

David Gajser

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 >>>

Jonas Holmerin

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 >>>

Irit Dinur, Venkatesan Guruswami, Subhash Khot

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 >>>

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig

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 >>>Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson

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 >>>