Theory

Asymptotic notation, multiple variables
Last June I posted an announcement of my paper, "On Asymptotic Notation with Multiple Variables." In this paper I showed that several of the commonly-used properties of big-O notation are inconsistent when applied to functions on more than one variable. I then proposed a new definition that (I claimed) implies thes... 18 Jan 2008 15:36

Could anyone help me with this math problem please?
Hi all, I am doing a decryption and have some math problems. Hope you guys could help me out, thanks in advance! ===================== Let k be a 128-bit binary number. k1 is the leftmost 64 bits of k, and k2 is the rightmost 64 bits of k. k3 is the left cyclic shift of k1 (e.g. if k1=001011, then k3= 010110) k... 18 Jan 2008 10:22

Questions about Parity SAT
Hi everyone, I've constructed a way to reduce Parity SAT (that is, the question whether a SAT instance has an odd number of satisfying assignments; a complete problem for Parity P if I'm not mistaken) to its special case (which looks much easier) in polynomial time and space. The special case, which I'll here ... 23 Jan 2008 20:58

Hamiltonian cycle problem in 2-connected bipartite cubic graph is Polynomial
Zhu Guohun <ccghzhu(a)hrt.dis.titech.ac.jp> writes: <snip> The MAX2SAT problem is solved in polynomial, and I have been submit it to http://arxiv.org/abs/0801.2447 (maybe it also show a little later). Just a "heads up": For me, the link takes me to a log-in page, and my attempt to register failed. -- ... 21 Jan 2008 08:23

CFP: 8th International Conference on Hybrid Intelligent Systems (HIS2008)
-- Apologies for cross postings -- HIS 2008 - First Call for Papers http://his2008.lsi.upc.edu/ The 8th Hybrid Intelligent Systems Conference -- HIS 2008 will be held at the Technical University of Catalonia, UPC Barcelona, Spain 10--12 September 2008 -- HIS 2008 is Technicaly Co-sponsored by -- IEE... 14 Jan 2008 10:22

*** Grand Challenges 6 Town Meeting, 4 February, 4.30pm-8pm, BCS Offices, London, UK ***
(** Apologies if you receive multiple copies of this announcement **) Grand Challenges 6 Town Meeting 4 February 2008 4.30pm BCS London Offices First Floor The Davidson Building 5 Southampton Street London WC2E 7HA ... 13 Jan 2008 16:13

How to proof primitive recursive?
I have trouble in proving this function f(0) = 0 f(1) = 1 f(x+2) = f(x)^2 + f(x+1) assume n belongs N ... 14 Jan 2008 09:13

Final Call for papers
Final Call for papers The 2008 International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-08) (website: www.PromoteResearch.org ) will be held during July 7-10 2008 in Orlando, FL, USA. We invite draft paper submissions and the deadline for paper submission is just few weeks ... 13 Jan 2008 00:56

CFP - The 1st International Workshop on Bit-Precise Reasoning (BPR 2008)
CALL FOR PAPERS BPR'08 - The 1st International Workshop on Bit-Precise Reasoning Location: Princeton, New Jersey. July 14th, 2008. (Affiliated with CAV 2008.) Website: http://www.bit-precise-reasoning.org/ Bit-Precise Reasoning is increasingly being used for the analysis of many real world hardware and so... 8 Jan 2008 20:14

multi-dimensional knapsack problem (MKP) instance generation
Hi, I am interested in developing heuristic algorithms (e.g., GA) for solving large-scale MKPs, but found little public problem instances of large size for benchmark purpose. Those included in ORLIB are usually small. Anyone knows where to find such info.? Another question is how to generate large-sized proble... 7 Jan 2008 17:56