CS297-298 Project News Feed

Items Covered:
probability distribution for syndrome grid
details of circuit inputs and outputs

Next Meeting:
office hours, Tuesday 23rd, 4:00

Deliverables:
finish circuits to create DNF

   

Meeting 11/02/04

Items covered:
Nisan-Wigderson pseudorandom generator (overview)
Circuit class design

Deliverables:
Initial l-sparse grid class
Initial Circuit class

Questions:
Each circuit appears to take multiple inputs and have multiple outputs. 
How are the circuits divided to get inputs for Tau tautology generator?
Is i a fixed number or is a circuit generated for each row of the grid?

   

Items covered:
- deliverable submission format
- possible architectures for Tau tautology generator inclusion in applet
- possible refinements of DPLL implementation
- Tau tautology definition

Deliverables:
- interation 1 of Applet (with code as zip text instead of PDF)
- intial class for circuits

   

Update

Finished:
-revised code and UI for deliverable 1
-emailed first deliverable (iteration 1 of Applet), with
validated html

In Progress:
-implementation of DPLL
-not(DNF) to CNF format conversion and UI change

Items Covered:
- DNF negation
- DPLL details
- typical DPLL heuristic for choosing variable
- weekly blog

Deliverables:
- prototype 1 of Applet (via email)
- change user entry format to DNF
- conversion of not(DNF) to CNF
- implementation of DPLL
- printout of last blog’s reading

   

Items Covered:
-review of gui interface
-discussion of conversion of DNF to CNF 
-discussion of using brute force to check satisfiability

Deliverables:
- gui interface modifications (user information, justification)
- polynomial view
- change interface to allow for DNF entry and internal conversion to CNF
- implement brute force algorithm to check CNF satisfiability
- implement storage and display format for disjunctions as vectors of coefficients
- develop way to multiply vectors of coefficients
- prototype of Applet to put online

Reading:
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of 
circuit lower bounds , J. of Symbolic Logic, 69(1), (2004), pp.265-286.  

   

Items Covered:

- proposal needs revision
- a proof exists showing that DPLL is faster than brute force ( can look up)
- initial Applet reviewed (list of additions under deliverables)
- discussed format of polynomials
- for pretty printer show polynomials before multiplication
- internal representation as vector of coefficients

Next Meeting: Tuesday, September 21st, 3:00 – 4:00

Deliverables:
- brute force algorithm to check if a particular CNF formula is always true. 
Allow for selection of multiple sentences and check the conjunction. 
- implement method for mapping CNF formula to polynomial as a vector of coefficients
- implement pretty printer for polynomials
- allow addition and deletion of a sentence
- add text field entry for multiple CNF entry via cut/paste


Finished:
- Applet allowing user to enter and store CNF clauses

   

Items Covered:
- course set-up (blog, bio, 180H paperwork)
- my initial PowerPoint presentation (ch 7 in AI book, Groebner Basis article)
- CNF
- project (implementation of DPLL and Groebner Basis algorithms)
- definition of Tau tautologies
- conversion of CNF formula to polynomial (T -> 0, F->1, *-> v, + -> ^)


Next Meeting: Tuesday, September 7th, 11:00

Deliverables:
- Applet allowing user to enter and store CNF clauses
- Brute force algorithm to check if a particular CNF formula is always true
- (optional) method for mapping CNF formula to polynomial