Sign in
Chic. J. Theor. Comput. Sci.
1995
2003
2012
2020
1995
2020
Keyphrases
Publications
volume 2020, 2020
Vikraman Arvind
,
Abhranil Chatterjee
,
Rajit Datta
,
Partha Mukhopadhyay
On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials.
Chic. J. Theor. Comput. Sci.
2020 (2020)
Dmitry Gavinsky
The communication complexity of the inevitable intersection problem.
Chic. J. Theor. Comput. Sci.
2020 (2020)
Rohit Agrawal
Coin Theorems and the Fourier Expansion.
Chic. J. Theor. Comput. Sci.
2020 (2020)
Arkadev Chattopadhyay
,
Meena Mahajan
,
Nikhil S. Mande
,
Nitin Saurabh
Lower bounds for linear decision lists.
Chic. J. Theor. Comput. Sci.
2020 (2020)
volume 2019, 2019
Ilias Diakonikolas
,
Themis Gouleakis
,
John Peebles
,
Eric Price
Collision-Based Testers are Optimal for Uniformity and Closeness.
Chic. J. Theor. Comput. Sci.
2019 (2019)
Ishay Haviv
,
Michael Langberg
H-wise Independence.
Chic. J. Theor. Comput. Sci.
2019 (2019)
Guillaume Lagarde
,
Guillaume Malod
,
Sylvain Perifel
Non-commutative computations: lower bounds and polynomial identity testing.
Chic. J. Theor. Comput. Sci.
2019 (2019)
volume 2018, 2018
Markus Bläser
,
Matthias Christandl
,
Jeroen Zuiddam
The border support rank of two-by-two matrix multiplication is seven.
Chic. J. Theor. Comput. Sci.
2018 (2018)
Steven D. Galbraith
,
Joel Laity
,
Barak Shani
Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations.
Chic. J. Theor. Comput. Sci.
2018 (2018)
Oded Goldreich
,
Tom Gur
Universal Locally Testable Codes.
Chic. J. Theor. Comput. Sci.
2018 (2018)
Jan Krajícek
,
Igor Carboni Oliveira
On monotone circuits with local oracles and clique lower bounds.
Chic. J. Theor. Comput. Sci.
2018 (2018)
Matthew B. Hastings
Local Maxima and Improved Exact Algorithm for MAX-2-SAT.
Chic. J. Theor. Comput. Sci.
2018 (2018)
Vincent Russo
,
John Watrous
Extended Nonlocal Games from Quantum-Classical Games.
Chic. J. Theor. Comput. Sci.
2018 (2018)
volume 2017, 2017
François Le Gall
,
Harumichi Nishimura
Quantum Algorithms for Matrix Products over Semirings.
Chic. J. Theor. Comput. Sci.
2017 (2017)
Rajko Nenadov
,
Pascal Pfister
,
Angelika Steger
Unique reconstruction threshold for random jigsaw puzzles.
Chic. J. Theor. Comput. Sci.
2017 (2017)
volume 2016, 2016
Vikraman Arvind
,
S. Raja
Some Lower Bound Results for Set-Multilinear Arithmetic Computations.
Chic. J. Theor. Comput. Sci.
2016 (2016)
André Chailloux
,
Gus Gutoski
,
Jamie Sikora
Optimal bounds for semi-honest quantum oblivious transfer.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Cécilia Lancien
,
Andreas J. Winter
Parallel repetition and concentration for (sub-)no-signalling games via a flexible constrained de Finetti reduction.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Alex B. Grilo
,
Iordanis Kerenidis
,
Jamie Sikora
QMA with Subset State Witnesses.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Thomas Watson
Nonnegative Rank vs. Binary Rank.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Penghui Yao
Parity Decision Tree Complexity and 4-Party Communication Complexity of XOR-functions Are Polynomially Equivalent.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Yuval Filmus
Friedgut-Kalai-Naor Theorem for Slices of the Boolean Cube.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Arnaud Durand
,
Meena Mahajan
,
Guillaume Malod
,
Nicolas de Rugy-Altherre
,
Nitin Saurabh
Homomorphism Polynomials Complete for VP.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Christopher T. Chubb
,
Steven T. Flammia
Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Arkadev Chattopadhyay
,
Frederic Green
,
Howard Straubing
Circuit Complexity of Powering in Fields of Odd Characteristic.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Vida Dujmovic
,
Anastasios Sidiropoulos
,
David R. Wood
Layouts of Expander Graphs.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Laura Mancinska
,
David E. Roberson
,
Antonios Varvitsiotis
On deciding the existence of perfect entangled strategies for nonlocal games.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Raghav Kulkarni
,
Avishay Tal
On Fractional Block Sensitivity.
Chic. J. Theor. Comput. Sci.
2016 (2016)
Divesh Aggarwal
,
Oded Regev
A Note on Discrete Gaussian Combinations of Lattice Vectors.
Chic. J. Theor. Comput. Sci.
2016 (2016)
volume 2015, 2015
Louay Bazzi
Entropy of weight distributions of small-bias spaces and pseudobinomiality.
Chic. J. Theor. Comput. Sci.
2015 (2015)
Naman Agarwal
,
Guy Kindler
,
Alexandra Kolla
,
Luca Trevisan
Unique Games on the Hypercube.
Chic. J. Theor. Comput. Sci.
2015 (2015)
Ilias Diakonikolas
,
Ragesh Jaiswal
,
Rocco A. Servedio
,
Li-Yang Tan
,
Andrew Wan
Noise Stable Halfspaces are Close to Very Small Juntas.
Chic. J. Theor. Comput. Sci.
2015 (2015)
Girish Varma
Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions.
Chic. J. Theor. Comput. Sci.
2015 (2015)
volume 2014, 2014
Mark Huber
Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction.
Chic. J. Theor. Comput. Sci.
2014 (2014)
Avraham Ben-Aroya
,
Igor Shinkar
A Note on Subspace Evasive Sets.
Chic. J. Theor. Comput. Sci.
2014 (2014)
Thomas Thierauf
,
Fabian Wagner
-free Graphs is in Unambiguous Logspace.
Chic. J. Theor. Comput. Sci.
2014 (2014)
B. V. Raghavendra Rao
,
Jayalal Sarma
Complexity of Testing Reachability in Matroids.
Chic. J. Theor. Comput. Sci.
2014 (2014)
Ansis Rosmanis
Quantum Adversary Lower Bound for Element Distinctness with Small Range.
Chic. J. Theor. Comput. Sci.
2014 (2014)
Peter J. Cameron
,
Ben Fairbairn
,
Maximilien Gadouleau
Computing in Permutation Groups Without Memory.
Chic. J. Theor. Comput. Sci.
2014 (2014)
Peter J. Cameron
,
Ben Fairbairn
,
Maximilien Gadouleau
Computing in Matrix Groups Without Memory.
Chic. J. Theor. Comput. Sci.
2014 (2014)
Ashley Montanaro
A composition theorem for decision tree complexity.
Chic. J. Theor. Comput. Sci.
2014 (2014)
Thomas Watson
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem.
Chic. J. Theor. Comput. Sci.
2014 (2014)
Hirotada Kobayashi
,
Keiji Matsumoto
,
Seiichiro Tani
Simpler Exact Leader Election via Quantum Reduction.
Chic. J. Theor. Comput. Sci.
2014 (2014)
volume 2013, 2013
Ilir Çapuni
,
Péter Gács
A Turing Machine Resisting Isolated Bursts Of Faults.
Chic. J. Theor. Comput. Sci.
2013 (2013)
Tom Gur
,
Omer Tamuz
Testing Booleanity and the Uncertainty Principle.
Chic. J. Theor. Comput. Sci.
2013 (2013)
Parinya Chalermsook
,
Shiva Kintali
,
Richard J. Lipton
,
Danupon Nanongkai
Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs.
Chic. J. Theor. Comput. Sci.
2013 (2013)
Eric Allender
,
George Davie
,
Luke Friedman
,
Samuel Hopkins
,
Iddo Tzameret
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.
Chic. J. Theor. Comput. Sci.
2013 (2013)
Alexandr Kazda
Complexity of the homomorphism extension problem in the random case.
Chic. J. Theor. Comput. Sci.
2013 (2013)
John Watrous
Simpler semidefinite programs for completely bounded norms.
Chic. J. Theor. Comput. Sci.
2013 (2013)
Debbie W. Leung
,
Benjamin Toner
,
John Watrous
Coherent state exchange in multi-prover quantum interactive proof systems.
Chic. J. Theor. Comput. Sci.
2013 (2013)