Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATION:
Reports tagged with Approximation:
TR95-024 | 23rd May 1995
Mihir Bellare, Oded Goldreich, Madhu Sudan

Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

This paper continues the investigation of the connection between proof
systems and approximation. The emphasis is on proving ``tight''
non-approximability results via consideration of measures like the
``free bit complexity'' and the ``amortized free bit complexity'' of
proof systems.

The first part of the paper presents a collection of new ... more >>>


TR95-025 | 8th May 1995
Günter Hotz, Gero Vierke, Bjoern Schieffer

Analytic Machines

Comments: 1

In this paper the $R$-machines defined by Blum, Shub and Smale
are generalized by allowing infinite convergent computations.
The description of real numbers is infinite.
Therefore, considering arithmetic operations on real numbers should
also imply infinite computations on {\em analytic machines}.
We prove that $\R$-computable functions are $\Q$-analytic.
We show ... more >>>


TR97-059 | 22nd December 1997
Jin-Yi Cai, Ajay Nerurkar

Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions

Recently Ajtai showed that
to approximate the shortest lattice vector in the $l_2$-norm within a
factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large
constant $k$, is NP-hard under randomized reductions.
We improve this result to show that
to approximate a shortest lattice vector within a
factor $(1+ \mbox{dim}^{-\epsilon})$, for any
$\epsilon>0$, ... more >>>


TR98-008 | 15th January 1998
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

Proof verification and the hardness of approximation problems.


We show that every language in NP has a probablistic verifier
that checks membership proofs for it using
logarithmic number of random bits and by examining a
<em> constant </em> number of bits in the proof.
If a string is in the language, then there exists a proof ... more >>>


TR98-009 | 25th November 1997
Bruce Edward Litow

Parallel complexity of integer coprimality

Comments: 3

It is shown that integer coprimality is in NC.

more >>>

TR98-010 | 22nd January 1998
Phong Nguyen, Jacques Stern

A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications

Revisions: 1


Recently, Ajtai discovered a fascinating connection
between the worst-case complexity and the average-case
complexity of some well-known lattice problems.
Later, Ajtai and Dwork proposed a cryptosystem inspired
by Ajtai's work, provably secure if a particular lattice
problem is difficult. We show that there is a converse
to the ... more >>>


TR98-034 | 23rd June 1998
Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

A tight characterization of NP with 3 query PCPs


It is known that there exists a PCP characterization of NP
where the verifier makes 3 queries and has a {\em one-sided}
error that is bounded away from 1; and also that 2 queries
do not suffice for such a characterization. Thus PCPs with
3 ... more >>>


TR98-040 | 24th July 1998
Madhu Sudan, Luca Trevisan

Probabilistically checkable proofs with low amortized query complexity

The error probability of Probabilistically Checkable Proof (PCP)
systems can be made exponentially small in the number of queries
by using sequential repetition. In this paper we are interested
in determining the precise rate at which the error goes down in
an optimal protocol, and we make substantial progress toward ... more >>>


TR98-066 | 3rd November 1998
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

This paper strengthens the low-error PCP characterization of NP, coming
closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for
membership in any NP language can be verified with a constant
number of accesses, and with an error probability exponentially
small in the ... more >>>


TR99-011 | 14th April 1999
Matthias Krause, Petr Savicky, Ingo Wegener

Approximations by OBDDs and the variable ordering problem


Ordered binary decision diagrams (OBDDs) and their variants
are motivated by the need to represent Boolean functions
in applications. Research concerning these applications leads
also to problems and results interesting from theoretical
point of view. In this paper, methods from communication
complexity and ... more >>>


TR00-042 | 21st June 2000
Lars Engebretsen

Lower Bounds for non-Boolean Constraint Satisfaction

Revisions: 1

We show that the k-CSP problem over a finite Abelian group G
cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for
any constant epsilon>0, unless P=NP. This lower bound matches
well with the best known upper bound, |G|^{k-1}, of Serna,
Trevisan and Xhafa. The proof uses a combination of PCP
techniques---most notably a ... more >>>


TR00-058 | 1st August 2000
Martin Sauerhoff

Approximation of Boolean Functions by Combinatorial Rectangles

This paper deals with the number of monochromatic combinatorial
rectangles required to approximate a Boolean function on a constant
fraction of all inputs, where each rectangle may be defined with
respect to its own partition of the input variables. The main result
of the paper is that the number of ... more >>>


TR01-038 | 14th May 2001
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

Approximating Schedules for Dynamic Graphs Efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG),
is investigated under graph-theoretic and complexity aspects.
Such graphs embed constructors for parallel programs,
synchronization mechanisms as well as conditional branches.
They are capable of representing all possible executions of a
parallel or distributed program ... more >>>


TR02-030 | 3rd June 2002
Lars Engebretsen, Jonas Holmerin, Alexander Russell

Inapproximability Results for Equations over Finite Groups

Revisions: 1

An equation over a finite group G is an expression of form
w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted
variable, or a constant from G; such an equation is satisfiable
if there is a setting of the variables to values in G ... more >>>


TR02-040 | 20th June 2002
Lars Engebretsen, Jonas Holmerin

Three-Query PCPs with Perfect Completeness over non-Boolean Domains

We study non-Boolean PCPs that have perfect completeness and read
three positions from the proof. For the case when the proof consists
of values from a domain of size d for some integer constant d
>= 2, we construct a non-adaptive PCP with perfect completeness
more >>>


TR03-020 | 27th March 2003
Elad Hazan, Shmuel Safra, Oded Schwartz

On the Hardness of Approximating k-Dimensional Matching

We study bounded degree graph problems, mainly the problem of
k-Dimensional Matching \emph{(k-DM)}, namely, the problem of
finding a maximal matching in a k-partite k-uniform balanced
hyper-graph. We prove that k-DM cannot be efficiently approximated
to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$.
This ... more >>>


TR03-077 | 4th September 2003
Till Tantau

Logspace Optimisation Problems and their Approximation Properties

This paper introduces logspace optimisation problems as
analogues of the well-studied polynomial-time optimisation
problems. Similarly to them, logspace
optimisation problems can have vastly different approximation
properties, even though the underlying existence and budget problems
have the same computational complexity. Numerous natural problems
are presented that exhibit such a varying ... more >>>


TR04-039 | 21st April 2004
Andrzej Lingas, Martin Wahlén

On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>


TR04-048 | 21st April 2004
André Lanka, Andreas Goerdt

An approximation hardness result for bipartite Clique

Assuming 3-SAT formulas are hard to refute
on average, Feige showed some approximation hardness
results for several problems like min bisection, dense
$k$-subgraph, max bipartite clique and the 2-catalog segmentation
problem. We show a similar result for
max bipartite clique, but under the assumption, 4-SAT formulas
are hard to refute ... more >>>


TR04-092 | 3rd November 2004
Oded Lachish, Ilan Newman

Testing Periodicity

A string $\alpha\in\Sigma^n$ is called {\it p-periodic},
if for every $i,j \in \{1,\dots,n\}$, such that $i\equiv j \bmod p$,
$\alpha_i = \alpha_{j}$, where $\alpha_i$ is the $i$-th place of $\alpha$.
A string $\alpha\in\Sigma^n$ is said to be $period(\leq g)$,
if there exists $p\in \{1,\dots,g\}$ such that $\alpha$ ... more >>>


TR05-058 | 24th May 2005
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

On Non-Approximability for Quadratic Programs

This paper studies the computational complexity of the following type of
quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ... more >>>


TR05-073 | 14th July 2005
Oded Goldreich, Dana Ron

Approximating Average Parameters of Graphs.


Inspired by Feige ({\em 36th STOC}, 2004),
we initiate a study of sublinear randomized algorithms
for approximating average parameters of a graph.
Specifically, we consider the average degree of a graph
and the average distance between pairs of vertices in a graph.
Since our focus is on sublinear algorithms, ... more >>>


TR05-098 | 4th September 2005
Oded Goldreich

Bravely, Moderately: A Common Theme in Four Recent Results


We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
more >>>


TR06-030 | 17th January 2006
Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar

Packing to angles and sectors

In our problem we are given a set of customers, their positions on the
plane and their demands. Geometrically, directional antenna with
parameters $\alpha,\rho,R$ is a set
of points with radial coordinates $(\theta,r)$ such that
$\alpha \le \theta \le \alpha+\rho$ and $r \le R$. Given a set of
possible directional ... more >>>


TR06-053 | 6th April 2006
Eldar Fischer, Orly Yahalom

Testing Convexity Properties of Tree Colorings

A coloring of a graph is {\it convex} if it
induces a partition of the vertices into connected subgraphs.
Besides being an interesting property from a theoretical point of
view, tests for convexity have applications in various areas
involving large graphs. Our results concern the important subcase
of testing for ... more >>>


TR06-068 | 6th April 2006
Patrick Briest, Piotr Krysta

Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing

We investigate non-parametric unit-demand pricing problems, in which the goal is to find revenue maximizing prices for a set of products based on consumer profiles obtained, e.g., from an e-Commerce website. A consumer profile consists of a number of non-zero budgets and a ranking of all the products the consumer ... more >>>


TR07-120 | 5th October 2007
Sharon Feldman, Guy Kortsarz, Zeev Nutov

Improved approximation algorithms for directed Steiner forest

We consider the k-Directed Steiner Forest} (k-dsf) problem:
given a directed graph G=(V,E) with edge costs, a collection D subseteq V \times V
of ordered node pairs, and an integer k leq |D|, find a minimum cost subgraph
H of G
that contains an st-path for (at least) k ... more >>>


TR11-028 | 24th February 2011
Richard Beigel, Bin Fu

A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

The bin packing problem is to find the minimum
number of bins of size one to pack a list of items with sizes
$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects
a random element from the input list each time, we develop a
randomized $O({n(\log n)(\log\log n)\over ... more >>>


TR12-062 | 17th May 2012
Ilan Komargodski, Ran Raz

Average-Case Lower Bounds for Formula Size

Revisions: 2

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation.

The same ... more >>>


TR13-051 | 2nd April 2013
Eric Blais, Li-Yang Tan

Approximating Boolean functions with depth-2 circuits

We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function.
In the first direction, our main positive results are the first non-trivial universal upper bounds on ... more >>>


TR13-136 | 27th September 2013
Paul Goldberg, Aaron Roth

Bounds for the Query Complexity of Approximate Equilibria

We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the ... more >>>


TR14-180 | 22nd December 2014
Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Space-Efficient Approximations for Subset Sum

SUBSET SUM is a well known NP-complete problem:
given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ... more >>>


TR18-122 | 3rd July 2018
Igor Carboni Oliveira, Rahul Santhanam

Pseudo-derandomizing learning and approximation

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser
[GG11]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed
output with high probability. We explore pseudo-determinism in the settings of learning and ap-
proximation. Our goal is to simulate known randomized algorithms in these settings ... more >>>




ISSN 1433-8092 | Imprint