Berkeley CSUA MOTD:Entry 26446
Berkeley CSUA MOTD
 
WIKI | FAQ | Tech FAQ
http://csua.com/feed/
2025/07/08 [General] UID:1000 Activity:popular
7/8     

2002/11/6-7 [Computer/Theory] UID:26446 Activity:very high
11/6    Strongly polynomial time algorithm found for linear programming.
        News at 11.
        \_ Uhm, that was 1979. Or are you using some non-standard definition
           of "strongly"?
           \_ 1979 ellipsoid algorithm was weak polynomial time, i.e. it was
              polynomial in the size of the constraint matrix, not polynomial
              in the size of largest number in the matrix.  The current
              algorithm is polynomial in both, which is the standard definition.
              What definition are you using?
              algorithm is polynomial in both, which is the standard
              definition. What definition are you using?
              \_ The same one; I hadn't considered the numerical behavior
                 of the data. So, enlighten me, are you saying the ellipsoid
                 algorithm can't handle in polytime, say, a matrix with
                 floats in [0,1]?
                 \_ No, the ellipsoid algorithm can't handle in
                    polytime a matrix with really really large
                    numbers.  An easy example of weakly polytime
                    problem is factoring a dot product vector of
                    integers.  If the integers are small, this problem
                    is clearly solvable in time linear in the length
                    of the vector.  The problem is that factoring
                    integers is hard, so there are no (known)
                    solutions which have polynomial runtime in the
                    size of the largest integer in the vector.  The
                    ellipsoid algorithm has a similar problem with
                    numbers in the constraint matrix.
                    \_ You misunderstood my question. Yes, I know what you
                       mean by "strongly polytime." What about LP over data
                       in a fixed range of reals?
                       mean by "strongly polytime." What about LP when all
                       parameters are in a fixed range of reals?
                       \_ I am not sure.  If the float is very small, or has
                          high precision, it will take a lot of bits to
                          represent it.  It may be that in fact the ellipsoid
                          algorithm has exponential behavior for any number
                          that needs a lot of bits, large or small.  (Note
                          that this clearly isn't true for factoring).
                    \- is this one of stephen smale's problems for the next
                       century? --psb
2025/07/08 [General] UID:1000 Activity:popular
7/8     

You may also be interested in these entries...
2012/1/24-3/3 [Computer/SW/Languages/C_Cplusplus, Computer/SW/Languages/Misc] UID:54296 Activity:nil
1/24    http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html
        Amusing "history" of computer science.
        \_ Where's the mentioning of Al Gore the inventor of AlGorithm?
	...
2011/6/29-7/21 [Computer/SW/Database, Computer/SW] UID:54133 Activity:nil
6/29    "An Israeli algorithm sheds light on the Bible"
        http://www.csua.org/u/tq4 (news.yahoo.com)
        "Software developed by an Israeli team is giving intriguing new hints
        about what researchers believe to be the multiple hands that wrote the
        Bible."
        \_ "Hype developed by an American OnLine News Feed is giving
	...
2010/8/9-19 [Computer/SW/Security] UID:53917 Activity:nil
8/9     I got two files, one is size 522190848 and the other is size
        521648128.  Both sha256 to the same number.  (and sha1 too).
        I don't think this is supposed to happen, right? (least not with
        sha256).
        \_ how are you checking?
           \_ I burned one file to cd, so i mounted /cdrom and
	...
2010/1/20-29 [Computer/SW/Languages/Misc, Computer/SW/Security] UID:53649 Activity:nil
1/20    Did Chinese come up with new way of quicksort?
        http://www.nytimes.com/2010/01/20/technology/20cyber.html
        Joe Stewart, a malware specialist with SecureWorks, a computer
        security company based in Atlanta, said he determined the main
        program used in the attack contained a module based on an unusu
        al algorithm from a Chinese technical paper that has been
	...
2009/10/24-11/3 [Computer/HW/Laptop] UID:53466 Activity:kinda low
10/24   How well do you see color? I got 8, how about you?
        http://www.xrite.com/custom_page.aspx?PageID=77
        \_ 7
           \_ what monitor did you use?
              \_ LCD on thinkpad x32, under not so great lighting conditions.
        \_ I scored 101, which seems impossible. Then again, I didn't
	...
2009/1/13-22 [Computer/Theory] UID:52367 Activity:kinda low
1/13    I am writing a commandline parser for a class and I could use some
        tips for algorithms to use. (The project is over and done so I am
        not cheating, but I am dissatisfied with my end result.) I STFW and
        didn't come up with too much I liked. I read the source for some
        shells like tcsh and that is *WAY* too complicated and relies on
        a lot of other code. I know that browsers and other apps have
	...
2008/12/2-6 [Computer/SW/Apps, Academia/Berkeley/CSUA/Motd] UID:52140 Activity:kinda low
12/1    Just curious -- what do you guys generally use soda for? Why do you
        log on? Personally, I use it to keep a presence on IRC and AIM/gTalk
        at all times, and mess around with some Python programming (been
        setting up Twisted and such so I can play with making an irc bot).
        --toulouse
        \_ I use it to post SHIT, er, I mean, spill my guts about the company
	...
2008/11/25-28 [Computer/Theory] UID:52108 Activity:nil
11/25   Holy crap! I was the one asking how to open a locked up masterlock a
        few days ago. I tried the algorithm on this webpage:
        http://www.wikihow.com/Crack-a-%22Master-Lock%22-Combination-Lock
        and it worked! Thanks to whoever suggested it.
        \_ Good to know, thanks for the reply.
	...