70 papers:
STOC-2015-AbboudWY- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture (AA, VVW, HY), pp. 41–50.
- STOC-2015-DingSS #proving #satisfiability #scalability
- Proof of the Satisfiability Conjecture for Large k (JD, AS, NS), pp. 59–68.
- STOC-2015-HenzingerKNS #multi #online #problem
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture (MH, SK, DN, TS), pp. 21–30.
ICALP-v2-2015-KariS #algebra #approach #geometry- An Algebraic Geometric Approach to Nivat’s Conjecture (JK, MS), pp. 273–285.
LATA-2015-GonzeJ #on the #probability- On the Synchronizing Probability Function and the Triple Rendezvous Time — New Approaches to Černý’s Conjecture (FG, RMJ), pp. 212–223.
PODS-2014-AmelootKNZ #declarative #fine-grained #network- Weaker forms of monotonicity for declarative networking: a more fine-grained answer to the calm-conjecture (TJA, BK, FN, DZ), pp. 64–75.
- STOC-2014-GavinskyMWW #approach #bound #complexity #composition #towards
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture (DG, OM, OW, AW), pp. 213–222.
- ICALP-v1-2014-GavinskyL #reduction
- En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations (DG, SL), pp. 514–524.
- ICALP-v2-2014-Parter #hybrid
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners (MP), pp. 608–619.
SAT-2014-KonevL #satisfiability- A SAT Attack on the Erdős Discrepancy Conjecture (BK, AL), pp. 219–226.
- PODS-2013-GogaczM #on the
- On the BDD/FC conjecture (TG, JM), pp. 127–138.
CIAA-2013-KisielewiczS #automaton #generative- Generating Small Automata and the Černý Conjecture (AK, MS), pp. 340–348.
- ICALP-v1-2013-AbboudL
- Exact Weight Subgraphs and the k-Sum Conjecture (AA, KL), pp. 1–12.
- ICALP-v1-2013-ODonnellT #composition #fourier #theorem
- A Composition Theorem for the Fourier Entropy-Influence Conjecture (RO, LYT), pp. 780–791.
DUXU-PMT-2013-FrancaSM #parallel- Is Reality Real? Thoughts and Conjectures about Culture, Self, Intersubjectivity and Parallel Worlds in Digital Technologies (ACPdF, MMS, LRdLM), pp. 68–73.
- STOC-2012-HeilmanJN
- Solution of the propeller conjecture in R3 (SH, AJ, AN), pp. 269–276.
DLT-2012-Kari #automaton- Cellular Automata, the Collatz Conjecture and Powers of 3/2 (JK), pp. 40–49.
- ICALP-v1-2012-HughesPRS #problem
- A Thirty Year Old Conjecture about Promise Problems (AH, AP, NR, ALS), pp. 473–484.
LICS-2012-ChenF #on the #order- On the Ordered Conjecture (YC, JF), pp. 225–234.
- DLT-J-2010-Berlinkov11 #on the
- On a Conjecture by Carpi and d’Alessandro (MVB), pp. 1565–1576.
- DLT-J-2010-Steinberg11
- The Averaging Trick and the černý Conjecture (BS), pp. 1697–1706.
- DLT-2011-GusevP #on the #set
- On Non-complete Sets and Restivo’s Conjecture (VVG, EVP), pp. 239–250.
- DLT-2011-PlyushchenkoS #on the
- On Brzozowski’s Conjecture for the Free Burnside Semigroup Satisfying x2 = x3 (ANP, AMS), pp. 362–373.
- ICALP-v1-2011-ODonnellWZ #fourier
- The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions (RO, JW, YZ), pp. 330–341.
- PODS-2010-Hellerstein #datalog #experience
- Datalog redux: experience and conjecture (JMH), pp. 1–2.
- STOC-2010-RaghavendraS #game studies #graph
- Graph expansion and the unique games conjecture (PR, DS), pp. 755–764.
- DLT-2010-Berlinkov #on the
- On a Conjecture by Carpi and D’Alessandro (MVB), pp. 66–75.
- DLT-2010-Steinberg
- The Averaging Trick and the Cerný Conjecture (BS), pp. 423–431.
- STOC-2009-KawarabayashiR #decidability
- Hadwiger’s conjecture is decidable (KiK, BAR), pp. 445–454.
- STOC-2009-KunS
- A new line of attack on the dichotomy conjecture (GK, MS), pp. 725–734.
- STOC-2009-Shapira #invariant #testing
- Green’s conjecture and testing linear-invariant properties (AS), pp. 159–166.
- DLT-2009-AlmeidaS #matrix
- Matrix Mortality and the Cerný-Pin Conjecture (JA, BS), pp. 67–80.
- LATA-2009-Blanchet-SadriMRW #algorithm #using #word
- An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms (FBS, RM, AR, EW), pp. 188–199.
- STOC-2008-GoyalOS
- The vpn conjecture is true (NG, NO, FBS), pp. 443–450.
- STOC-2008-LovettMS
- Inverse conjecture for the gowers norm is false (SL, RM, AS), pp. 547–556.
- LATA-2008-Volkov #automaton
- Synchronizing Automata and the Cerny Conjecture (MVV), pp. 11–27.
- STOC-2006-Gurvits #algorithm #approach #bound #proving
- Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications (LG), pp. 417–426.
- ICALP-2005-GairingLMT #equilibrium #nash
- Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture (MG, TL, BM, KT), pp. 51–65.
- STOC-2004-Ajtai #polynomial
- A conjecture about polynomial time computable lattice-lattice functions (MA), pp. 486–493.
- DLT-2004-EpifanioMSV #graph
- Sturmian Graphs and a Conjecture of Moser (CE, FM, JS, IV), pp. 175–187.
IJCAR-2004-SteelBM #induction #protocol- Attacking a Protocol for Group Key Agreement by Refuting Incorrect Inductive Conjectures (GS, AB, MM), pp. 137–151.
- STOC-2003-Friedman #proving
- A proof of Alon’s second eigenvalue conjecture (JF), pp. 720–724.
- DLT-2003-GomezP #on the
- On a Conjecture of Schnoebelen (ACG, JÉP), pp. 35–54.
- DLT-2003-HarjuN
- About Duval’s Conjecture (TH, DN), pp. 316–324.
LOPSTR-2003-AlexandreBD #induction #proving #synthesis- Predicate Synthesis from Inductive Proof Attempt of Faulty Conjectures (FA, KB, MD), pp. 20–33.
- STOC-2002-Smyth #difference
- Reimer’s inequality and tardos’ conjecture (CDS), pp. 218–221.
- LICS-2001-BarringtonILST
- The Crane Beach Conjecture (DAMB, NI, CL, NS, DT), pp. 187–196.
ASE-2000-Monroy #abduction #recursion- The Use of Abduction and Recursion-Editor Techniques for the Correction of Faulty Conjectures (RM), pp. 91–100.
CADE-1999-ZhangJ #modelling- System Description: MCS: Model-based Conjecture Searching (JZ0), pp. 393–397.
- ICALP-1998-GrafV #proving
- Reducing Simple Polygons to Triangles — A Proof for an Improved Conjecture (TG, KV), pp. 130–139.
KR-1998-McIlraith- Explanatory Diagnosis: Conjecturing Actions to Explain Observations (SAM), pp. 167–179.
- DLT-1997-KarhumakiPM #bound #constant
- A lower bound for a constant in Shallit’s conjecture (JK, WP, FM), pp. 103–118.
- ICALP-1997-Cassaigne #on the
- On a Conjecture of J. Shallit (JC), pp. 693–704.
FME-1997-Gregoire #protocol #proving #using- TLA + PROMELA: Conjecture, Check, Proof, Engineering New Protocols Using Methods and Formal Notations (JCG), pp. 378–397.
RTA-1997-Perlo-FreemanP- Scott’s Conjecture is True, Position Sensitive Weights (SMHWPF, PP), pp. 217–227.
- STOC-1996-KushilevitzLO #communication #complexity
- The Linear-Array Conjecture in Communication Complexity is False (EK, NL, RO), pp. 1–10.
- CADE-1996-Protzen
- Patching Faulty Conjectures (MP), pp. 77–91.
- DLT-1995-CurrieS #set
- Cantor Sets and Dejean’s Conjecture (JDC, ROS), pp. 35–43.
- LICS-1994-GurevichIS
- McColm’s Conjecture (YG, NI, SS), pp. 10–19.
- STOC-1992-DorT #composition #graph #proving
- Graph Decomposition Is NPC-A Complete Proof of Holyer’s Conjecture (DD, MT), pp. 252–263.
- CADE-1992-Protzen
- Disproving Conjectures (MP), pp. 340–354.
- STOC-1991-CoffmanG #proving #scheduling
- Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling (EGCJ, MRG), pp. 241–248.
- STOC-1990-Cole #on the
- On the Dynamic Finger Conjecture for Splay Trees (Extended Abstract) (RC0), pp. 8–17.
- LICS-1990-Clote
- ALOGTIME and a Conjecture of S. A. Cook (Extended Abstract) (PC), pp. 181–189.
- STOC-1989-Birget #proving
- Proof of a Conjecture of R. Kannan (JCB), pp. 445–453.
- STOC-1989-Bshouty #on the
- On the Extended Direct Sum Conjecture (NHB), pp. 177–185.
- STOC-1989-KurtzMR #morphism #random
- The Isomorphism Conjecture Fails Relative to a Random Oracle (Extended Abstract) (SAK, SRM, JSR), pp. 157–166.
- STOC-1986-LubotzkyPS
- Explicit Expanders and the Ramanujan Conjectures (AL, RP, PS), pp. 240–246.
- ICALP-1982-Culik #on the #testing
- On Test Sets and the Ehrenfeucht Conjecture (KCI), pp. 128–140.
- STOC-1975-RivestV #proving
- A Generalization and Proof of the Aanderaa-Rosenberg Conjecture (RLR, JV), pp. 6–11.
