[Lowerbounds, Upperbounds]

First, I thank Anupam for telling me about this.

By subscribing to the arXiv mailing list on the subjects that you are interested in, you will get to know what has been submitted to arXiv recently.

Go to http://arxiv.org/archive/cs/cssub.html for more information on how to subscribe and what areas are available.

For example, this is my subscription email.

To: cs@arXiv.org
Subject: subscribe Maverick Woo

add Data Structures and Algorithms
add Discrete Mathematics
add Computational Complexity

And this is what I got yesterday:

From: send mail ONLY to cs 
To: cs daily title/abstract distribution 
Date: Tue, 19 Apr 2005 07:51:40 -0400
Subject: cs daily Subj-class mailing 42 1

------------------------------------------------------------------------------
------------------------------------------------------------------------------
send mail only to cs@arXiv.org, do not reply to no-reply@...
send any complaints regarding submissions directly to submitter.
use a single `get' to request multiple papers, `list macros' for available
macro packages, and `help' for a list of available commands and other info.
------------------------------------------------------------------------------
point your www client at http://arXiv.org/
To unsubscribe, e-mail To: cs@arXiv.org, Subject: cancel
------------------------------------------------------------------------------
 Submissions to:
Computational Complexity
Discrete Mathematics
 received from  Fri 15 Apr 05 20:00:02 GMT  to  Mon 18 Apr 05 20:00:01 GMT
------------------------------------------------------------------------------
------------------------------------------------------------------------------
\
Paper: cs.DM/0504082
Date: Mon, 18 Apr 2005 13:45:09 GMT   (11kb)

Title: Coloring Artemis graphs
Authors: Benjamin L'{e}v\^{e}que (Leibniz - IMAG), Fr'{e}d'{e}ric Maffray
  (Leibniz - IMAG), Bruce Reed, Nicolas Trotignon (Leibniz - IMAG)
Proxy: ccsd ccsd-00004741
Subj-class: Discrete Mathematics
ACM-class: G.2.2
\
  We consider the class A of graphs that contain no odd hole, no antihole, and
no ``prism'' (a graph consisting of two disjoint triangles with three disjoint
paths between them). We show that the coloring algorithm found by the second
and fourth author can be implemented in time O(n^2m) for any graph in A with n
vertices and m edges, thereby improving on the complexity proposed in the
original paper.
\ ( http://arXiv.org/abs/cs/0504082 ,  11kb)
%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-
------------------------------------------------------------------------------
\
Paper (*cross-listing*): cond-mat/0504070
Date: Mon, 4 Apr 2005 09:42:16 GMT   (21kb)

Title: Clustering of solutions in the random satisfiability problem
Authors: M. Mezard, T. Mora, R. Zecchina
Comments: 4 pages, 1 figure
Subj-class: Disordered Systems and Neural Networks; Computational Complexity
\
  Using elementary rigorous methods we prove the existence of a clustered phase
in the random $K$-SAT problem, for $K\geq 8$. In this phase the solutions are
grouped into clusters which are far away from each other. The results are in
agreement with previous predictions of the cavity method and give a rigorous
confirmation to one of its main building blocks. It can be generalized to other
systems of both physical and computational interest.
\ ( http://arXiv.org/abs/cond-mat/0504070 ,  21kb)
------------------------------------------------------------------------------
\
Paper: cs.GT/0504075
Date: Fri, 15 Apr 2005 22:11:55 GMT   (120kb,S)

Title: Dichotomy for Voting Systems
Authors: Edith Hemaspaandra and Lane A. Hemaspaandra
Report-no: URCS-TR-2005-861
Subj-class: Computer Science and Game Theory; Computational Complexity;
  Multiagent Systems
ACM-class: I.2.11; F.1.3; F.2.2
\
  Scoring protocols are a broad class of voting systems. Each is defined by a
vector $(\alpha_1,\alpha_2,...,\alpha_m)$, $\alpha_1 \geq \alpha_2 \geq >...
\geq \alpha_m$, of integers such that each voter contributes $\alpha_1$ points
to his/her first choice, $\alpha_2$ points to his/her second choice, and so on,
and any candidate receiving the most points is a winner.
  What is it about scoring-protocol election systems that makes some have the
desirable property of being NP-complete to manipulate, while others can be
manipulated in polynomial time? We find the complete, dichotomizing answer:
Diversity of dislike. Every scoring-protocol election system having two or more
point values assigned to candidates other than the favorite--i.e., having
$||\{\alpha_i \condition 2 \leq i \leq m\}||\geq 2$--is NP-complete to
manipulate. Every other scoring-protocol election system can be manipulated in
polynomial time. In effect, we show that--other than trivial systems (where all
candidates alway tie), plurality voting, and plurality voting's transparently
disguised translations--\emph{every} scoring-protocol election system is
NP-complete to manipulate.
\ ( http://arXiv.org/abs/cs/0504075 ,  120kb)
%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%
------------------------------------------------------------------------------
\
Paper: cs.DM/0405059
replaced with revised version Mon, 18 Apr 2005 05:40:46 GMT   (11kb)

Title: Coloring Meyniel graphs in linear time
Authors: Benjamin L'{e}v\^{e}que (Leibniz - IMAG), Fr'{e}d'{e}ric Maffray
  (Leibniz - IMAG)
Proxy: ccsd ccsd-00001574
Subj-class: Discrete Mathematics; Combinatorics
ACM-class: G.2.2
\ ( http://arXiv.org/abs/cs/0405059 ,  11kb)
%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---