11
$\begingroup$

I have been developing a SAT algorithm for a while, and have reached a point where I'd like to share it. I don't know many people in computer science, and I'm not sure exactly where to turn.

I'm wondering what resources are available for someone with an algorithm who is considering publishing. I also need help analyzing the runtime and correctness of my algorithm.

My major problem is in analyzing the runtime. I need help with a detailed analysis of this. I'm fairly certain that the algorithm is correct, but it would be helpful if someone would verify this as well.

So is there anyone who would be willing to analyze my algorithm? Additionally, what resources are available for a task like this?

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you talking about publishing or checking your idea? What do you mean by "resources"; journals or means of checking? $\endgroup$
    – Raphael
    Commented Oct 6, 2010 at 22:04
  • 12
    $\begingroup$ It seems to me that if publishing is the goal, then you have to have at least a runtime analysis, and a sense of "how" correct your algorithm is, assuming it's a heuristic. You'd also have to compare what your algorithm does to prior work - without that, publication is a no-no. In fact, I'd recommend doing that first. $\endgroup$
    – Suresh Venkat
    Commented Oct 6, 2010 at 22:11
  • $\begingroup$ I'm considering publishing, but for now I'm really looking for help with analysis. I realize that this site may help with specific questions, but I'm hoping to find places where I can meet people that would be willing to help with analysis. Also, I don't have a lot of background regarding other algorithms, but I wonder if my approach may be somewhat unique. $\endgroup$
    – Matt Groff
    Commented Oct 6, 2010 at 23:17
  • $\begingroup$ See also related question cstheory.stackexchange.com/questions/7600/… $\endgroup$
    – András Salamon
    Commented Aug 6, 2011 at 16:07

3 Answers 3

Reset to default
32
$\begingroup$

If your SAT algorithm is meant to be practical, then you should run the SAT competition benchmarks on it. The SAT solving community is going to take your work much more seriously if you can show that your approach is competitive with existing solvers. Your solver doesn't have to be faster than every solver, or solve more instances, but it should be a serious competitor. You don't need a very fast or powerful machine to run the benchmarks; you can simply compare runtime against one of the free SAT solvers like MiniSAT or PicoSAT. These solvers will also allow you to see what the answers should look like.

If you are working on a practical solver that uses new techniques, and your approach is not yet competitive, I would still suggest trying these benchmarks. They would help you to understand the kinds of problems that you should be aiming to solve, and the kind of performance you should be aiming for. You might also want to read some of the key chapters of the Handbook of Satisfiability, or the recent survey

  • Knot Pipatsrisawat and Adnan Darwiche, On Modern Clause-Learning Satisfiability Solvers, Journal of Automated Reasoning 44 277–301, 2010. (PDF)

to see the kinds of arguments that support the major solvers. If you have new ideas that are not yet optimized to perform as well as the top solvers, you would need to explain the potential advantages of your approach to someone who knows the long sequence of theoretical reasoning that has led to the current set of "best practice" design decisions.

If your contribution is purely theoretical, then you need to be aware of the many papers in this area, and explain in your paper why your approach is better in at least some way. Have a look at recent work by for instance Amin Coja-Oghlan or Alan Frieze to get a feel for the state of the art and for useful pointers to important papers.

Improve this answer
$\endgroup$
2
2
$\begingroup$

Since you now want to share your algorithm, my personal suggestion is the following: build a very simple web site. The site should make available these 2 things:

  1. The source code of the algorithm.
  2. A document briefly describing your approach. Where your approach is different? Which is the new idea behind it? This document doesn't need to be a perfectly-written technical paper, nor it needs to contain any formal proof: a power point presentation would be enough to "transmit" the core of your idea. Just explain us why you think your algorithm is different. Maybe it's unique, who knows.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't think creating a website is a very good idea. Because a lot many people build a website when they 'think' they have solved big problems or have found TOE. e.g. dharwadker.org/tevet/isomorphism matpitka.blogspot.com Theorem: "For every unsolved problem there is at least one guy who claims he solved it and builds a website." Bad idea -1 :( $\endgroup$
    – Pratik Deoghare
    Commented Jan 9, 2011 at 16:50
  • $\begingroup$ @TheMachineCharmer: I didn't mean something like that. The website was just a way to let people download the code and read the document describing the algorithm. I didn't mean a "celebrating" website. Instead, I meant a website to merely share material, without any "triumphant" claim (something similar to what you said in your answer, although yours has a somewhat more "official" flavour). $\endgroup$
    – Giorgio Camerani
    Commented Jan 28, 2011 at 10:19
1
$\begingroup$
  1. You can write your ideas down in standard paper format.
  2. Publish it on ArXiv.
  3. Share source code on github.
  4. Spend some time learning run time analysis and update your paper when you are done.

e.g. You can write a survey paper and at the end suggest your solution as new promising approach. But without proof of correctness and run time analysis not many people will take it seriously (but some will).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.