Skip to content

Gopiandcode/query-complexity-framework

Repository files navigation

Query Complexity Framework

The following is a simple framework for the empirical exploration of query complexity questions.

The project consists of an abstract framework for programatically analyzing query complexity functions, and provides a number of example instantiations of the framework on a few generalizations of GPW to 3D.

Project structure

.
|-- dune
|-- dune-project
|-- gpw.ml
|-- majority_gpw.ml
|-- majority_alg.ml
|-- generalized_gpw.ml
|-- utils.ml
|-- main.ml
`-- readme.md

The framework is logically decomposed into small modular reusable components by file:

  • gpw.ml - Defines the abstract interface of a query complexity problem generator - any such component should provide functions to generate true, false and random values.
  • majority_gpw.ml - Implementation of a problem generator for an extension of the Göös-Pitassi-Watson function to 3D by taking the majority of multiple instances of 2D GPW on seperate planes.
  • majority_alg.ml - Implementation of a solver algorithm for majority GPW, implementing Muks et al.'s 1-sided GPW solution strategy internally for each plane.
  • generalized_gpw.ml - Implementation of a problem generator for an extension of the Göös-Pitassi-Watson function to 3D by replacing columns with sub-cubes of the input instead.
  • utils.ml - Utility functions used throughout the project
  • main.ml - Example instantiations of the framework to run some experiments

Requirements

In order to run this project, you must have OCaml installed (version >= 4.09.0) with opam, and the following packages installed:

  • core
  • gnuplot

Running

To run the sample experiments, simply run the following from the project root:

dune exec ./main.exe

About

Framework for empirically exploring query complexity questions

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published